Lineární algebra Petriho sítí 1) Notace Definice: Nezna ená PN je taková tve ice Q = P, T, Pre, Post , kde • • •
•
P = {P1, .... Pn} je množina míst (kone ná nenulová) T = {T1, ..... Tm} je množina p echod (kone ná nenulová) Pre: P × T → {0,1} vstupní inciden ní relace, Pre(Pi,Tj) je váha hrany p Pi → Tj, Pre(Pi,Tj) = p když hrana existuje, Pre(Pi,Tj) = 0, když hrana neexistuje Post: P × T → {0,1} výstupní inciden ní relace, Post(Pi,Tj) je váha p hrany Tj → Pi, Post(Pi,Tj) = p když hrana existuje, Post(Pi,Tj) = 0, když hrana neexistuje
2) Inciden ní matice • • •
Vstupní inciden ní matice W- = [wij-], kde wij- = Pre(Pi,Tj) Výstupní inciden ní matice W+ = [wij+], kde wij+ = Post(Pi,Tj) Inciden ní matice W = W+ - W- = [wij]
Vlastnosti inciden ní matice • • • •
Sloupec v matici odpovídá modifikaci aktuálního markingu p i zapálení p íslušného p echodu Inciden ní matice je nezávislá na markingu Je-li PN istá (nemá vlastní smy ky), tak ji lze zrekonstruovat z inciden ní matice Užitím inciden ní matice lze vypo ítat P a T invarianty
P íklad: P1
T1
P2
P3
Vstupní inciden ní matice Pi → Tj
Výstupní inciden ní matice T j → Pi
Inciden ní matice
1 0 W = 0 1
0 1 W = 1 0
−1 1 W =W + −W − = 1 −1
0 1
1 0
−
T2
+
1
−1
3) Fundamentální rovnice • •
Nech S je zapalovací sekvence z Mi taková, že Mi [ S > Mk Charakteristický vektor sekvence S je takové S = (n1, n2,.....), že , kde ni je po et odpálení p echodu Ti v sekvenci S
Definice: Fundamentální rovnici pro zapalovací sekvenci S takovou, že platí Mi [ S > Mk nazýváme rovnici
Mk = Mi + W S P íklad: Máme PN z p edchozího p íkladu, a po áte ní marking M0 = (1,0,0). Chceme ur it marking M1 po odpálení p echodu S1 = T1. P1
T1
P2
P3
Inciden ní matice
Fundamentální rovnice
M 0 = (1,0,0)T ,
M 1 = M 0 + WS ,
−1 1 W = 1 −1 .
1
1
−1
−1
M1 = 0 + 1 0 1
1
1 −1 . 0 −1
T2
4) Konzervativní komponenty • •
Vektor vah pro místa F = (q1, q2,.....qn), qi p irozené nenulové íslo, i = 1 .... n. Nech P(F) je podmnožinou P (množina míst PN), pro které je qi nenulové nezáporné. V ta: P(F) je konzervativní komponenta, platí-li
FT W = 0. •
•
Potom vektor F nazýváme P-invariant (nezáporný vektor), sou in FTMi nazýváme marking invariant (po et token v místech P(F) vážený F je konstantní). P-invarianty jsou nezávislé na markingu.
P íklad: Máme PN z p edchozího p íkladu, a po áte ní marking M0 = (1,0,0). Chceme ur it a) konzervativní komponenty PN, b) marking invarianty PN.
Rovnice pro Pinvarianty
P1
F T W = W T F = 0. T
F1T M i = konst ,
T
F2T M i = konst.
F1 = (1,1,0) ,
T1
F2 = (1,0,1) . P2
P3
Marking invarianty
P ( F1 ) = {P1 , P2 }, P ( F2 ) = {P1 , P3 }.
m1 + m2 = konst , m1 + m3 = konst.
T2
5) Repetitivní komponenty Definice: T(S) je množina p echod (podmnožina T), které tvo í statickou repetitivní komponentu tehdy, když existuje zapalovací sekvence S taková (repetitivní sekvence), že
W S = 0. Vlastnosti: • • • •
Charakteristický vektor S je potom T-invariant. Pokud platí W S > 0, T(S) je rostoucí repetitivní komponenta (tokeny se množí). T-invarianty jsou nezávislé na markingu. T-invariantu odpovídá alespo jedna repetitivní sekvence (ne všem Tinvariant m musí odpovídat repetitivní sekvence).
P íklad: Máme PN podle obrázku. Chceme ur it repetitivní komponenty a p íslušné repetitivní sekvence. P1
Inciden ní matice
T1
T
−1 T3
T4
WS = 0.
M 0 = (1,0,0) ,
P2
W= 1 0
T2
0
Rovnice pro T-invarianty
1
0
1 . −1 0 1 −1 −1
S1 = (1,1,1,0)T , S 2 = (0,1,0,1)T . S1 = T1T2T3 , S 2 = T2T4 . T ( S1 ) = {T1 , T2 , T3 }, T ( S 2 ) = {T2 , T4 }.
P3
6) Souvislost PT-invariant a vlastností Petriho sítí A. Živá Petriho sí Nech je dána oby ejná Petriho sí . Je-li Petriho sí konzervativní komponenta a repetitivní komponenta. Obsahuje-li každý P-invariant alespo jeden token, potom je Petriho sí živá.
B. Omezená Petriho sí Nech je dána oby ejná Petriho sí . Je-li Petriho sí konzervativní komponenta, potom je Petriho sí omezená a konzervativní.
C. Reverzibilní Petriho sí Nech je dána oby ejná Petriho sí . Je-li Petriho sí repetitivní komponenta, a je-li Petriho sí živá, potom je Petriho sí reverzibilní a repetitivní.
Úlohy Úloha 5.1: Pro Petriho sítˇ na obrázku, ur ete: a) b) c) d) e)
P-invarianty a konzervativní komponenty. T-invarianty a repetitivní komponenty. Marking po odpálení zapalovací sekvence S = T1T2 a S = T1T4 Je Petriho sí omezená a konzervativní? Je Petriho sí reverzibilní a repetitivní? Obsahuje deadlock a je živá? P1
P2
T1
T2
T4 T3 P3
Úloha 5.2: Pro Petriho sítˇ na obrázku, ur ete: a) b) c) d) e)
P-invarianty a konzervativní komponenty. T-invarianty a repetitivní komponenty. Marking po odpálení zapalovací sekvence S = T4T3T1 Je Petriho sí omezená a konzervativní? Je Petriho sí reverzibilní a repetitivní? Obsahuje deadlock a je živá? P1
P2
T1
T4 T3 P3
T2
Úloha 5.3: Pro Petriho sítˇ na obrázku, ur ete: a) b) c) d) e)
P-invarianty a konzervativní komponenty. T-invarianty a repetitivní komponenty. Marking po odpálení zapalovací sekvence S = T1T2T3. Je Petriho sí omezená a konzervativní? Je Petriho sí reverzibilní a repetitivní? Obsahuje deadlock a je živá? P1
P2
T1
2
2
T2
T4 T3 P3
Úloha 5.4: Pro Petriho sítˇ na obrázku, ur ete: a) b) c) d) e)
P-invarianty a konzervativní komponenty. T-invarianty a repetitivní komponenty. Marking po odpálení zapalovací sekvence S = T1. Je Petriho sí omezená a konzervativní? Je Petriho sí reverzibilní a repetitivní? Obsahuje deadlock a je živá? P1
P4
T1
T3 P2
T2
P3
P5
T4
Úloha 5.5: Dva vozíky A a B se pohybují na trati mezi stanicemi, konkrétn vozík A mezi stanicí PA a Q, vozík B mezi stanicemi PB a Q. ást trati je spole ná, na této ásti m že jet pouze jeden vozík. Konkrétn mezi místy TA a Q smí jet vozík A, v tomto p ípad musí být vozík B blokován. Mezi místy TB a Q smí jet vozík B, vozík A je v tomto p ípad blokován. Pro sdílení a p epínání tratí slouží výhybka, která je ovládána pulsním signálem (AIGA*, AIGB*). Pohyb vozík je realizován pomocí motor , pohyb doprava na trati odpovídá ídícím signál m GA nebo GB, pohyb doleva signál m DA nebo DB. K ízení pohybu používají operáto i tla ítek DCYA a DCYB. Vstupem do ídicího systému jsou binární signály tla ítek DCYA a DCYB, binární signály koncových spína PA, PB, TA, TB a Q. Výstupem z ídicího systému jsou ak ní binární signály GA, GB, DA, DB a impulsní signály AIGA* a AIGB*. V klidovém stavu se nacházejí vozíky v místech PA a PB. Dva operáto i, první na stanici PA, druhý na stanici PB, mohou nezávisle pomocí tla ítek aktivovat pohyb vozíku sm rem k míst m TA resp. TB. V P ípad , že na trati mezi místy TA resp. TB a Q, jede vozík do místa Q a zp t do výchozí klidové polohy PA resp. PB. V opa ném p ípad vy ká v míst TA resp. TB do té doby, kdy je druhý vozík na spole né ásti trati. V p ípad žádosti obou vozík o pohyb do místa Q, má prioritu vozík A. Po návratu do výchozích míst PA resp. PB lze cyklus opakovat stiskem tla ítek.
Vypracujte: a) Namodelujte funkci vozík pomocí oby ejné autonomní Petriho sít . b) Vytvo te inciden ní matici. c) Ur ete PT-invarianty konzervativní a repetitivní komponenty. d) Diskutujte vlastnosti Petriho sít . e) Jaký by byl funk ní rozdíl v p ípad , že bychom modelovali systém pomocí synchronizované Petriho sít ?
