From Wikipedia, the free encyclopedia
Una Xarxa de Petri, també coneguda com una xarxa de lloc / transició, és un llenguatge matemàtic de modelatge per a la descripció de sistemes distribuïts discrets. Van ser ideades cap al 1960 per Carl Adam Petri. Són una generalització de la teoria d'autòmats que permet expressar activitats concurrents. També són conegudes com a PN (Petri Net).
Aquest article o secció necessita millorar una traducció deficient. |
En la seva tesi doctoral "kommunikation mitautomaten"[1] (Comunicació amb autòmats), estableix els fonaments per al desenvolupament teòric dels conceptes bàsics de les PN.
Una xarxa de petri es un graf dirigit bipartit, en el qual els nodes representen transicions (representades amb una barra vertical) i llocs (representats amb un cercle). Els arcs, descriuen la relació entre transicions i llocs.
Les xarxes de Petri ofereixen una notació gràfica de processos pas a pas, que inclouen decisions, iteracions, i execucions concurrents. A diferència d'altres estàndards, com per exemple diagrames UML o els Model i Notació de Processos de Negoci (Business Process Model and Notation), les xarxes de petri tenen una notació matemàtica exacta de la seva semàntica d'execució, a més de teoria matemàtica per a l'anàlisi de processos.
Una xarxa de Petri està formada per llocs, transicions i arcs. Els arcs es dirigeixen des d'un lloc fins a una transició i viceversa, però no entre llocs o transicions. Els llocs els quals un arc es dirigeix a una transició s'anomenen llocs d'entrada d'una transició. Els arcs que s'originen en una transició s'anomenen llocs de sortida d'una transició.
Parlant abstractament de les xarxes de Petri, una transició d'una xarxa de Petri s'iniciarà si aquesta està habilitada, per exemple, si hi ha suficients tokens en els llocs d'entrada corresponents; quan la transició s'inicia, aquesta consumeix els tokens d'entrada requerits i en conseqüència crea tokens en el lloc de sortida. Aquesta transició es atòmica.
L'execucció d'una xarxa de Petri en general no es determinística, tot i que s'hi pot determinar una política d'execució definida prèviament. El no determinisme vol dir que, en cas que múltiples accions estiguin disponibles al mateix temps, qualsevol pot ser executada.
Com que la transició no es deteministica i múltiples tokens poden estar en el mateix lloc, les xarxes de Petri son adequades per model·lar el comportament concurrent de sistemes distribuïts.
Regla de l'evolució. Un lloc és un lloc d'entrada d'una transició si existeix un arc orientat que connecta aquest lloc a la transició. Un lloc és un lloc de sortida d'una transició si existeix un arc orientat que connecta aquesta transició al lloc.
La circulació per una xarxa de petri, es fa mitjançant unes fitxes o tokens. Gràficament, els llocs d'una xarxa de Petri poden contenir un nombre discret de fitxes. Qualsevol distribució de tokens als llocs representen una configuració anomenada marcatge.
En la seva forma més bàsica, les fitxes que circulen en una xarxa de Petri són totes idèntiques. Es pot definir una variant de les xarxes de Petri en les quals les fitxes poden tenir un color (una informació que les distingeix), un temps d'activació i una jerarquia a la xarxa.
La majoria dels problemes sobre xarxes de Petri són decidibles, com ara el caràcter tancat i la cobertura. Per a resoldre'ls s'utilitza un arbre de Karp-Miller.[2] Se sap que el problema d'abast és decidible, almenys en un temps exponencial.
Les xarxes de Petri son sistemes basats en estats i transicions que estenen una classe de xarxes anomenades xarxes elementals.[3]
Definició 1. Una xarxa es una 3-pla on:
Definició 2. Donada una xarxa , una configuració és un conjunt tal que ⊆ .
Definició 3. Una xarxa elemental és aquella en la qual EN = (N, C) on:
Definició 4. Una xarxa de Petri és aquella la qual té forma PN = (N, M, W) i estén aquesta xarxa elemental tal que:
Si una xarxa de petri és equivalent a una xarxa elemental, llavors pot ser un conjunt numerable {0,1} i aquells elements en que mapejen a 1 sota M forma una configuració. Similarment, si una xarxa de Petri no és una xarxa elemental, a llavors un multiconjunt pot ser interpretat com una representació no singletó d'un conjunt de configuracions. En referència a això, estén el concepte de configuració de xarxes elementals a xarxes de Petri.
En el diagrama d'una xarxa de Petri, els llocs són representats com a cercles, les transicions com a rectangles allargats i els arcs com a fletxes unidireccionals que mostren les connexions de llocs a transicions i viceversa. Si el diagrama fos d'una xarxa elemental, llavors els llocs en una configuració serien representats com a cercles, on cada cercle conté un únic punt anomenat token. En el diagrama de la xarxa de Petri, el cercle pot contenir més d'un token per tal de mostrar el nombre de vegades que un lloc apareix en una configuració.
A la figura de dalt, el lloc p1 és un lloc d'entrada de la transició t; mentres que, el lloc ₂ és un lloc de sortida de la mateixa transició. Suposem 0 com una xarxa de Petri amb un marcatge configurat com a 0 i 1 com una xarxa de Petri amb un marcatge configurat com a 1. La configuració de N0 habilita la transició t a través de la propietat que fa que tots els llocs d'entrada tenen un nombre de tokens suficients (representats com a punts) “igual o major” que la multiplicitat dels seus arcs respectius. Quan es dona el cas esmentat, la transició s'habilitará i iniciará. En aquest exemple, l'inici de la transició t genera un mapa que té el marcatge configurat 1 en la imatge de 0 i resulta en la xarxa de Petri 1, vista en el diagram de sota.
Al diagrama, la regla d'inici per una transició pot ser caracteritzada per una subtracció d'un nombre de tokens d'un lloc d'entrada igual a la multiplicitat dels respectius arcs d'entrada i acumulant un nombre de tokens als llocs de sortida igual a la multiplicitat dels arcs de sortida respectius.
Observació. El significat precís de “igual o major” dependrá de les propietats algebraiques de la suma aplicades en en la regla d'inici, on subtils variacions de les propietats algebraiques poden dirigir a altres classes de xarxes de Petri; com per exemple les xarxes de Petri Algebraiques.
Un graf d'una xarxa de Petri és una 3-pla , on:
La relació de flux és el conjunt d'arcs: . En multiples llibres, els arcs només poden tenir multiplicitat 1. Aquests llibres usualment defineixen xarxes de Petri utilitzant en canvi de . Quan utilitzem aquesta convenció, un graf d'una xarxa de Petri és un multigraf bipartit amb particions de nodes i .
La preselecció d'una transició t és un conjunt de llocs d'entrada ; la postselecció és el conjunt dels seus llocs de sortida: . Definicions de pre i postseleccions de llocs són anàlogues.
El marcament d'una xarxa de Petri (graf) és un multiconjunt de llocs, és a dir, un mapeig . Diem que el marcatge assigna a cada lloc un nombre de tokens.
Una xarxa de Petri marcada és una 4-pla , on:
En paraules:
Generalment, estem interessats en el qual pot succeir quan les transicions poden iniciarse contínuament en un ordre arbitrari.
Diem que el marcatge M’ és accesible des d'un marcatge M en un pas si ; podem dir que és accesible des d'M si , on és el tancament transitiu reflexiu de ; és a dir, que pot ser accesible en 0 o més passos.
Per a una xarxa de Petri (marcada) , estem interessats en les inicialitzacions que poden ser realitzades començant amb el marcament inicial . El conjunt de marcatges accesibles és el conjunt
L'accesibilitat d'un graf de N és la relació de la transició restringida al seus marcatges accesibles . És l'espai d'estats de la xarxa.
Una seqüència d'inicialització per una xarxa de Petri amb un graf G i marcatge inicial és una seqüència de transicions tal que . El conjunt de seqüències d'inicialització es pot denotar amb
Com s'ha comentat, una variació comú és la de no permetre la multiplicitat d'arcs i reemplaçar el multiconjunt d'arcs amb un conjunt simple, anomenada la relació de flux,
Un altre variació comú, per exemple en Jörge Desel and Gabriel Juhás (2001),[4] és la de permetre capacitats ser definides com a llocs. Això es discutit a les extensions d'avall.
Els marcatges d'una xarxa de Petri poden ser considerats com a vectors d'enters no negatius amb llargada [5]
La seva relació de transició pot ser descrita com un parell de per matrius:
Llavors la seva diferència
pot ser utilitzada per descriure els marcatges accesibles en termes de multiplicació de matrius, com segueix. Per qualsevol seqüència de transicions , s'escriu per al vector que mapeja cada transició al seu nombre d'ocurrències en . Llavors, tenim
Es requeriment que sigui una seqüència d'inici; permetre seqüències arbitraries de transicions usualment generarà un conjunt més gran.
Una de les propietats més interessants de les xarxes de petri és que donen un balanç entre poder de modelatge i d'anàlisi. Moltes aplicacions de sistemes concurrents es poden determinar mitjançant xarxes de Petri, encara que el cost de les operacions sigui molt costós. S'ha determinat que multiples subclasses de xarxes de Petri poden modelar diferent classes de sistemes concurrents, a la vegada que aquests problemes es fan més senzills.
Una revisió d'aquests problemes de decisió, amb resultats de decidibilitat o complexitat per a xarxes de Petri i algunes subclasses, pot ser trobat a Javier Esparza i Mogens Nielsen (1995)[6]
El problema d'accessibilitat per a xarxes de Petri es decidir, donada una xarxa de Petri i un marcatge , si
Clarament, aquest és un problema on recorrem el graf d'accessibilitat definit a dalt, fins que arribem al marcatge demanat o sapiguem que no es pot trobar. Aquesta tasca és més complexa del que sembla a primera vista: el graf d'accessibilitat és generalment infinit, per això és difícil determinar quan es pot aturar.
De fet, aquest problema s'ha determinat que és EXSPACE-hard anys abans que es determinés si era decidible.
Tot i que l'accessibilitat sembla una bona eina per trobar estats incorrectes, el graf construït usualment té massa estats que hem de calcular. Per tal d'alleujar aquest problema, es fa servir lògica lineal temporal en conjunt amb un mètode de Tableau per demostrar que no es pot arribar a aquests estats. La lógica lineal temporal utilitza una tècnica de semi-decisió per trobar si un estat és accessible, mitjançant la cerca d'un conjunt de condicions necessàries per a arribar a l'estat i provant que aquestes condicions no poden ser satisfetes.
Les xarxes de Petri poden tenir diferents nivells de vida .
Una xarxa de Petri es anomenada -viva només si totes les seves transicions son -viva, on una transició és:
Com es pot veure, aquest requeriments son cada vegada més rigorosos que l'anterior:-viva implica -viva per a
Aquestes definicions estan en concordança amb la revisió de Mirata, que utilitza -viva com a terme per mort.
Un lloc a una xarxa de Petri es anomenada k-limitada si no conté més de k tokens en tots els seus marcatges accessibles, inclòs el marcatge inicial; es pot dir que és segura si és 1-limitada; és un conjunt limitat si és k-limitat per alguna k.
Una xarxa de Petri marcada s'anomena k-limitada, segura o limitada quan tots els seus llocs ho són. Una xarxa de Petri (graf) s'anomena (estructuralment) limitada si és limitada per tots els possibles marcatges inicials.
Una xarxa de Petri és limitada només si el seu graf d'accessibilitat és finit.
La delimitació és decidible mirant al recobrent, mitjançant la construcció d'un arbre Karp-Miller.
Pot ser útil el fet d'imposar limts en certs llocs d'una xarxa. Aquesta limitació pot ser utilitzada per model·lar sistemes de recursos limitats.
Algunes definicions de les xarxes de Petri permeten aquest fet com un distintiu sintàctic. Formalment, xarxes de Petri amb capacitats de lloc poden ser definides com tuples on és una xarxa de Petri, una assignació de capacitats per a alguns o tots els llocs, i la relació de transició és l'usual restringida als marcatges on cada lloc amb una capacitat té com a molt tots aquells tokens.
Per exemple, si en una xarxa N, ambdós llocs són assignats una capacitat de 2, obtenim una xarxa de Petri amb capacitats als llocs d'N2; el seu graf d'accessibilitat es mostra a la dreta.
Alternativament, podem limitar certs llocs estenen la xarxa. Per ser exacte, es pot fer que un lloc sigui k-limitat afegint un “contra-lloc” amb un flux davant el lloc original, i afegint tokens fent que el total sigui k a ambdós llocs.
Així com existeixen Xarxes de petri per events discrets, també existeixen Xarxes de Petri per processos continus i també per a esdeveniments híbrids (combinació d'events discrets-continus), que s'utilitzen en la teoria de control discreta, contínua i híbrida i per la teoria d'autómats mencionada anteriorment.
Les xarxes de Petri acolorides (CPN) pertanyen a la família de les PN, la diferència és que les consideracions en CPN de colors i de funcions lineals associades als seus arcs. Els tokens de color poden representar un atribut o distintiu, si cal definir dos atributs llavors sorgeix la idea de colors composts.
Una transició en CPN és en estat ACCESIBLE si tots els seus nodes d'entrada contenen un nombre de colors igual o major que els definits per Φ on Φ és una funció lineal associada al node amb la transició . Llavors a més deL concepte de color, aquestes xarxes manegen una funció associada per als elements de les funcions I,O de la PN.
Hi ha una gran quantitat d'extensions respecte les xarxes de Petri. Algunes d'aquestes tenen compatibilitat amb versions anteriors de les xarxes de Petri (p.e xarxes de Petri acolorida), algunes afegeixen propietats que no podien ser modelades en les originals (p.e xarxes de Petri amb temps). Encara que els models que posseeixen compatibilitat amb versions anteriors no estenen el poder computacional de les xarxes de Petri, poden tenir representacions més concises i més convenients per modelatge. Extensions que no poden ser transformades en xarxes de Petri poden ser potents, però, no tenen accés al rang d'eines matemàtiques que posseeixen les xarxes de Petri ordinàries.[7]
El terme xarxa Petri d'alt nivell es usualment utilitzat per referir-se a xarxes que estenen el formalisme bàsic P/T; això inclou xarxes de Petri acolorida, xarxes jeràrquiques com les xarxes dins de xarxes, i totes les extensions mencionades en aquesta secció.
Una llista de possibles extensions:
Hi ha altres tipus d'extensions de xarxes de Petri, però, es important tenir present que a mesura que la complexitat de la xarxa augmenta en termes de noves propietats, més difícil es fa utilitzar eines estandarditzades per a avaluar certes propietats de la xarxa. Per aquesta raó, es una bona idea utilitzar el tipus de xarxes més simple per modelar una tasca donada.
En comptes d'estendre el formalisme de les xarxes de Petri, també podem restringir la sintaxi d'aquestes per tal d'obtenir certs tipus de xarxes de Petri. Anomenem xarxes de Petri aquelles les quals tots els seus arcs tenen un pes de 1. Amb més restriccions, els següents tipus de xarxes de Petri son estudiades i utilitzades:
Les xarxes de flux de treball son una subclasse de les xarxes de Petri creades amb la intenció de modelar el flux de treball de les activitats procés. Les transicions de les xarxes de flux de treball son assignades a tasques o activitats, i els llocs son assignats a les pre/post condicions. Les xarxes de flux de treball tenen requeriments estructurals i operacionals addicionals, principalment l'addició d'una únic lloc d'entrada sense transicions prèvies i un lloc de sortida sense transicions addicionals. D'aquesta manera, els marcatges d'inici i finalització representen l'estat del procés.
Les xarxes de flux de treball tenen la propietat de solidesa, indicant que un procés el qual s'inicia amb un marcatge de k tokens en el lloc d'inici, pot arribar al lloc final amb un total de k tokens. Addicionalment, totes les transicions del procés podrien iniciar-se (p.e. per a cada transició hi ha un estat accessible en el qual la transició està habilitada).
Un camí dirigit en una xarxa de Petri està definit com una seqüència de nodes (llocs i transicions) enllaçats pels arcs dirigits. Un camí elemental inclou cada node en la seqüència una única vegada.
Una xarxa de Petri ben manejada es una xarxa en la qual no hi ha camins elementals totalment distints entre un lloc i una transició (o viceversa), p.e., si hi ha dos camins entre un parell de nodes, a llavors, aquests camins comparteixen un node. Una xarxa de flux de treball ben manejada i acíclica és sòlida.
Les xarxes de flux de treball esteses son xarxes de Petri compostes de xarxes de flux de treball amb una transició addicional t. El lloc de sortida esta connectat com el lloc d'entrada de la transició t i el lloc d'origen del lloc de sortida. L'inici de la transició causa la iteració del procés.
La matriu d'estructura de disseny (DSM) pot modelar les relacions de procés i poden servir per planejament de procés. Les xarxes DSM són la realització de plans basat en DSM transformats en processos de flux per a xarxes de Petri. La construcció de xarxes DSM asseguren la propietat de solides de la xarxa resultant.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.