Petrijeve mreže
Petrijeve mreže predstavljaju sredstvo za prikaz i modeliranje dinamičkih sustava u svrhu analize njihovih ponašanja u različitim okolnostima. Ime su dobile po svom izumitelju Carlu Adamu Petriju.Njihov najveći razvoj uočava se na području modeliranja i provjere funkcionalnosti informacijskog sustava.Grafički opisuju strukturu distribuiranog sustava kao usmjereni, otežani graf koji sadrži dvije vrste čvorova, mjesta (places) i prijelaze (transitions), povezane usmjerenim spojnicama (directed arcs). Petrijeve mreže omogućavaju definiranje i simuliranje različitih stanja i procesa u promatranom sustavu te opisivanje toka informacija i objekata kroz sustav.
Definicija
Petrijeve mreže su metoda za apstraktni prikaz svih tipova procesa (npr. upravljanje strojevima, proizvodna traka...).Važno je da kod opisa procesa treba točno definirati vremenske i uzročne međuodnose. Formalno se Petrijeve mreže definiraju kao uređena šestorka (S, T, F, K, W, M0), pri čemu je:
- S... neprazan konačan skup pozicija; S = {s1,s2,...,s|S|}
- T... neprazan konačan skup tranzicija ; T = {t1,t2,...,t|T|}
- F... neprazan skup strelica ;
- K... kapacitet pozicija; S→N \{0}
- W... težine strelica; F→N\{0}
- M0... početni položaj marki; S→N
Jednostavnije; razlikuje se pozicija (skup S) od tranzicije (skup T). Niti jedan objekt se ne može nalaziti u oba skupa, te između dva objekta (koji se nalaze u različitim skupovima) može postojati relacijski tok (strelica F). Pozicijama se dodjeljuju dva prirodna broja K i M0 , a strelicama prirodni broj F. U primjeni se koriste pozicije koje mogu sadržavati jednu ili više marki. Koliko marki može sadržavati pozicija govori kapacitet K, a koliko stvarno sadrži pokazuje broj marki M. Za razliku od pozicija, tranzicije nemaju dodatne parametre. One predstavljaju aktivne elemente, jer se njihovom aktivacijom mijenja raspored marki u pozicijama, što se naziva okidanje .Uz strelice navodi se broj, tj. faktor koji kod prekidanja utječe na tok marki, a naziva se težina strelice.
Krugovi predstavljaju pozicije, a marke se označavaju točkama unutar kruga, u slučaju velikog broja marki njihova se količina upisuje brojkom, također unutar kruga. Kapacitet se zapisuje kod kruga, a ukoliko on nije naveden radi se o negraničeno velikom kapacitetu. Pozicije se mogu i imenovati radi jednostavnijeg razumijevanja i rukovanja, za naziv se može koristiti redni broj pozicije ili opis onoga što se modelira pozicijom.
Pravokutnici predstavljaju tranzicije i ispod njh se nalazi njihov naziv. Pozicije i tranzicije su povezane pomoću strelica, pri čemu te strelice ne moraju biti ravne. Vrh strelice se nalazi na onom kraju koji je drugi naveden u relaciji F. Strelica ima svoju težinu i ona se upisuje uz strelicu. Ako težina nije navedena njena pretpostavljena vrijednost iznosi 1.
Tekstualno, grafički prikaz izgledao bi:
- S = {s1,s2}
- T = {t1}
- F = {(s1,t1), (t1,s2)}
- K = {(s1,20), (s2,20)}
- W = {((s1,t1),1), ((t1,s2),1)}
- M0 ={(s1,10), (s2,0)}
Područje ispred
Kad strelica pokazuje na neki čvor x, tada čvor y, od kojeg počinje strelica pripada području ispred 'x čvora x. ( 'x je područje ispred x). Područje ispred tranzicije sastoji se samo od elemenata različitog tipa, odnosno samo od pozicija.
Područje iza
Kada strelica pokazuje od čvora x prema čvoru y, tada čvor y pripada području iza x' čvora x (x' je područje iza x). Područje iza tranzicije sastoji se samo od elemenata različitog tipa, odnosno samo od pozicija.
Područje ispred i područje iza se ne isključuju međusobno. Neki elementi mogu istovremeno biti područje ispred nekog elementa, ali i područje iza nekog drugog ili istog elementa, kao što je to kod mreže kruga.
Okidanje
Okidanjem se mijenja raspored marki u pozicijama, tj. mijenja se položaj marki u mreži. Pozicija ne može okinuti, to može samo tranzicija. Kada tranzicija okine, uzima onoliko marki iz područja ispred koliko je navedeno težinom strelice, te ih premjesti u pozicije područja iza, ovisno o težini druge strelice. Koliko u pozicijama područja ispred ima marki, toliko i u pozicijama područja iza mora biti mjesta za nove marke. Tranzicija koja zadovoljava ovaj uvjet je aktivna tranzicija, međutim ona ne mora okinuti. Kad u mreži nema nijedne aktivne tranzicije onda je mreža mrtva.
Sekvenca i paralelizam
Slijed koji se najčešće javlja u procesu obično izgleda : A→B→C. To znači da se prvo odvija aktivnost A, nakon nje slijedi aktivnost B i na kraju C. Kad se ta ovisnost prikazuje Petrijevim mrežama aktivnosti A, B i C postaju tranzicije. Da B slijedi nakon A, tj. C nakon B prenosi se kao uvjet. To ima značenje ˝A je okinuto˝ odnosno ˝sad je B na redu˝. To se ostvaruje na način da se nemarkirana pozicija ˝sad je B na redu˝ stavlja između tranzicija A i B, kao područje iza tranzicije A i područje ispred tranzicije B. Na taj se način ostvaruje i da C slijedi nakon B. Potrebno je još dodati samo uvjet za aktivnost A, tako da se ona može okinuti. Ova sekvenca će se izvršiti točno jednom prema odabranom redoslijedu (Slika 1)
Kada se nešto prikazuje pomoću sekvence, u Petrijevoj mreži se u jednom trenutku okida samo jedna tranzicija, tj. u jednom trenutku se odvija samo jedan događaj. Međutim kada se istovremeno odvija dva ili više događaja, tada se na različitim mjestima u Petrijevoj mreži okida više tranzicija. Da li neka tranzicija može okinuti ovisi o području ispred i području iza. Kada se odvijaju dvije ili više međusobno neovisne sekvence, radi se o paralelizmu (slika 2).
Grananja
Aktivnosti se ne odvijaju uvijek samo paralelno ili u sekvencama, već se njih tijek često odvija kao kombinacija ova dva načina. Razlikuju se:
- razdvajanje,
- spajanje,
- sinkronizacija.
Razdvajanje
Do razdvajanja dolazi kada se na jednu sekvencu nastavljaju dvije sekvence koje teku paralelno. Takva se Petrijeva mreža modelira pomoću tri pozicije i isto toliko tranzicija.Prva pozicija (p1) «zajednička priprema završena» predstavlja uvjet za okidanje prve tranzicije (t1). Druga i treća pozicija (p2 i p3) predstavljaju uvjet da «aktivnosti 1 i 2 mogu početi». Prva tranzicija okidanjem prikazuje prijelaz iz «zajednička priprema završena» u «aktivnost 1 i 2 mogu početi», tj. uzima marku iz pozicije «zajednička priprema završena» i stavlja po marku u pozicije «aktivnost 1 i 2 mogu početi» (iz jedne marke nastaju dvije marke). Tranzicije koje slijede (t2 i t3) drugoj i trećoj poziciji predstavljaju aktivnosti 1 i 2.
Spajanje
Spajanje je obrnuti postupak od razdvajanja. U takvoj Petrijevoj mreži od dvije zasebne sekvence nastaje jedna.Tranzicija (t1) će okinuti kada se u pozicijama (p2 i p3), koje završavaju dvije paralelne sekvence, pojave marke. Značenje ovih marki biti će da su aktivnosti 1 i 2 završene, tj. biti će zadovoljen uvjet za početak procesa koji slijedi. Kod okidanja tranzicije iz dvije marke, što se nalaze u pozicijama područja ispred tranzicije, nastat će jedna u poziciji područja iza tranzicije.
Sinkronizacija
Postoje procesi koji međusobno neovisno rade, ali u nekom trenutku trebaju međurezultat onog drugog. Zato se ti procesi moraju sinkronizirati. Tranzicija, koja sinkronizira, čeka da svi procesi koje treba sinkronizirati stignu do točke sinkronizacije.Kada su svi procesi stigli do točke sinkronizacije ona okidanjem započinje nastavak tijeka svih procesa u granama.Tranzicija «Sinkrono» čeka da procesi A i B stignu do točke sinkronizacije. Proces A stiže prije nego proces B, ali on se neće nastaviti odvijati tako dugo dok proces B isto ne dođe do točke sinkronizacije. Kada oba procesa budu u točki sinkronizacije, tranzicija će moći okinuti i tako nastaviti tijek procesa A i procesa B.
Konflikt i konfuzija
Konflikt
U Petrijevim mrežama dolazi do konflikta onda kada obje grane žele učiniti nešto što se međusobno isključuje. On često nije pogreška, već samo prikazuje odabir jedne mogućnosti između više mogućnosti. Do konflikta područja ispred dolazi kada dvije tranzicije trebaju istu marku da bi okinule (slika 3). Do konflikta područja iza, za razliku od konflikta područja ispred, dolazi kada dvije tranzicije žele staviti marku u jednu te istu poziciju, a kapacitet pozicije nije dovoljan za obje marke. Dvije tranzicije su aktivne, ali može okinuti samo jedan (slika 4). Prema strategiji upravljanja konfliktima (po nekom redosljedu, sinkronizirano, slučajnim izborom...) ovisi kakav će biti rezultat, odnosno koja će od sukobljenih tranzicija okinuti.
Konfuzija
Konfuzija je «dvostruki konflikt», tj. neka se tranzicija istovremeno nalazi u konfliktu s dvije različite tranzicije. Tranzicija 2 (t2) se istovremeno nalazi u konfliktu s tranzicijama 1 i 3 (t1 i t3). U konfliktu s tranzicijom 1 se bori za marku na poziciji 1 (p1), a u konfliktu s tranzicijom 3 za marku na poziciji 3 (p3). Konfuzija će nastati okidanjem bilo koje tranzicije. Ako okine tranzicija 1, tranzicija 2 više nije aktivna, a time nestaje i konflikt između tranzicija 2 i 3. Ista stvar će se dogoditi i kada okine tranzicija 3. U slučaju da okine tranzicija 2, obje se marke troše i više ne može okinuti niti tranzicija 1, niti tranzicija 3, također nestaje konflikt.
Izomorfnost
Izomorfne mreže su one mreže koje se razlikuju samo u redoslijedu grafičkog prikaza, tj. razlikuju se samo u smještaju pozicija i tranzicija, dok su im struktura i značenje jednaki. Postoji nekoliko kriterija kojima se utvrđuje izomorfnost mreža. Ti kriteriji su :
- obje Petrijeve mreže moraju imati isti broj tranzicija i pozicija,
- u obje mreže mora biti isti broj elemenata s jednakim područjem ispred i područjem iza,
- ako na temelju prethodna dva kriterija nije isključena mogućnost izomorfnosti, tada se pokušavaju elementi jedne mreže preslikati u elemente druge mreže. Ako ovaj proces u potpunosti uspije, tada su te dvije Petrijeve mreže izomorfne.
Klasifikacija Petrijevih mreža
Klasifikacija prikazuje brzi pregled osnovnih razlika između mnogobrojnih vrsta Petrijevih mreža. Osnovna podjela je na Petrijeve mreže prve, druge i treće razine.
- Za Petrijeve mreže prve razine karakteristične su pozicije koje mogu biti markirane najviše jednom nestrukturiranom markom (binarne vrijednosti).
- Za Petrijeve mreže druge razine karakteristične su pozicije koje mogu biti markirane nekim cjelobrojnim brojem marki (vrijednosti prirodnih brojeva uključujući 0, tj. pozicije kao brojači).
- Za Petrijeve mreže treće razine karakteristične su pozicije koje mogu biti markirane višeskupnim strukturnim markama kojima je informacija pridružena.
Vanjske poveznice
- http://www.petrinets.info/
- http://en.wikipedia.org/wiki/Petri_net
- http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri_eng.html
Izvori
- Čerić, V., Simulacijsko modeliranje, Školska knjiga, Zagreb, 1993.
- Hržić, T., Diplomski rad: Konceptualno modeliranje uz primjenu Petrijevih mreža, Varaždin, 2004.
- S. Ribarić, J. Šnajder. Mapping Petri Net-Based Temporal Knowledge Representation Scheme into CP-Net Model. In Proc. of MIPRO 2005
- Carl Adam Petri and Wolfgang Reisig (2008) Petri net. Scholarpedia,