Diszkrét eseményu˝ folyamatrendszerek modellezése Hangos Katalin ´ ıtastudom ´ ´ Alkalmazasa ´ Tanszek ´ Szam´ any ´ Egyetem Veszpremi ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 1/36 ”Halado”
Tartalom • Diszkrét eseményu˝ rendszerek jellemzése • Véges automata modellek • Petri háló modellek ˝ • közönséges, idozített, színes, hierarchikus • Diszkrét eseményu˝ modellek megoldása • Diszkrét eseményu˝ modellek dinamikus analízise ˝ • elérhetoség, végesség, holtpontok, ciklikus viselkedés
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 2/36 ”Halado”
Diszkrét eseményu˝ rendszerek jellemzése
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 3/36 ”Halado”
Diszkrét eseményu˝ rendszerek Jellemzo˝ tulajdonságok: • a jelek (bemenet, kimenet, állapot) érték-készlete diszkrét: x(t) ∈ X = {x0 , x1 , ..., xn } • esemény : egy diszkrét jelérték-változás bekövetkezése • az ido˝ diszkrét: T = {x0 , x1 , ..., xn } = {0, 1, ..., n} Csak az események sorrendje számít • soros és párhuzamos események leírása • alkalmazási területek: ütemezés, operátori eljárások, ˝ eroforrás-kezelés
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 4/36 ”Halado”
Egyszeru˝ példa: reaktor-szur ˝ o˝ rendszer Fresh solvent
Raw material
Reactor
Product
Product
Filters
Recycle pump
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 5/36 ”Halado”
Véges automata modellek
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 6/36 ”Halado”
Véges automata modell Absztrakt leírás: A = (Q, Σ, δ) • Állapotok halmaza: Q • a bemeneti szalag véges ABC (alphabet)-je: Σ = {#; a, b, ...} • Állapot-átmeneti függvény: δ : Q × Σ → Q • Kezdeti és végállapotok halmaza: QI , QF Grafikus ábrázolás: súlyozott irányított gráffal • Csúcsok: állapotok (Q) • élek: állapot-átmenetek (δ) • élsúlyok: bemeno˝ szimbólum (Σ)
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 7/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Véges automata modell – 1 Fresh solvent
Seeem
Raw material
Reactor
"r"
"nil"
"r" Sreen
Product
Product
"r"
"nil"
Seern
Seren
Filters
Recycle pump
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 8/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Véges automata modell – 2 Absztrakt leírás A = (Q, Σ, δ) • Állapotok halmaza: Q = {Seeen , Sreen , Seern , Seren } • a bemeneti szalag véges ABC-je: Σ = {#; ”r”, ”nil”} • Állapot-átmeneti függvény: δ : Q × Σ → Q • Kezdeti és végállapotok halmaza: QI = {Seeen }, QF = {Seern , Seren }
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 9/36 ”Halado”
Petri háló modellek
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 10/36 ”Halado”
Petri háló modellek • Diszkrét eljárások soros és párhuzamos lépésekkel ˝ • Események elofeltételekkel és következményekkel • Alapeset és kiterjesztései ˝ • idozített, színes, hierarchikus • Hatékony megoldó és analízis módszerek
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 11/36 ”Halado”
Petri háló modell – absztrakt leírás: C = (P, T, I, O) Statikus leírás (szerkezet) • Helyek (feltételek) halmaza: P • Átmenetek (események) halmaza: T ˝ • Bemeneti (elofeltétel) függvény: I : T → P ∞ • Kimeneti (következmény) függvény: O : T → P ∞ Grafikus ábrázolás: páros irányított gráffal • Csúcsok: helyek (P ) és átmenetek (T ) (partíciók) • élek: bemeneti és kimeneti függvény (I, O) ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 12/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Reaktor muködés ˝ –1 Grafikus leírás Psr
Prr
Prr tr
tr
PRr
tr "fires"
PRr
tR
tR Ppr
Psr
Ppr
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 13/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Reaktor muködés ˝ –2 Formális leírás: szerkezet CS = (PS , TS , IS , OS ) ahol PS TS IS (tr ) IS (tR ) OS (tr ) OS (tR )
= = = = = =
{prr , psr , pRr , ppr } {tr , tR } {prr , psr } {pRr , pRr } {pRr , pRr } {ppr , psr } ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 14/36 ”Halado”
Petri hálók dinamikája ˝ ˝ Jelölofüggvény: jelölopontok (token-ek) µ:P→N ,
µ(pi ) = µi ≥ 0
µT = [µ1 , µ2 , . . . , µn ] ,
n = |P|
˝ Átmenet tüzel (muködik): ˝ ha az elofeltételek "igaz"-ak (van token a bemeneti helyeken) µ(i) [tj > µ(i+1) tüzelés után a következmény-ek lesznek "igaz"-ak Tüzelési (muködési) ˝ sorozat µ(0) [tj0 > µ(1) [tj1 > ...[tjk > µ(k+1)
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 15/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Reaktor muködés ˝ –3 Tüzelés leírása: µTS = [µrr , µsr , µRr , µpr ] = [1, 1, 0, 0] , µ(0)T S
µ(1)T = [0, 0, 2, 0] S (1) µ(0) [t > µ r S S
Psr
Prr
Prr tr
tr
PRr
tr "fires"
PRr
tR
tR Ppr
Psr
Ppr ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 16/36 ”Halado”
Párhuzamos események Egynél több engedélyezett átmenet: konkurencia (független feltételek), konfliktus, konfúzió p1
...
p5
p4
t1
t2
p2 ...
...
p3
t3
t2
p2 ...
p3
...
t1
t3
p1
p4 a,
b,
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 17/36 ”Halado”
Konfliktus feloldás Inhibitor nyilakkal: felhasználó által beállított prioritás ˝ Teszt nyilak: nem veszi el a jelzopontot
p ready
p ready t drain
p pump
p tank
t drain
p tank
p pump a,
b,
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 18/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Konfliktus helyzet praw
pRempt
psolv
tGR
Fresh solvent
psemi
pf1empt
pf2empt
Raw material
Reactor
tGf1 Product
tGf2
Product
Filters
pproduct Recycle pump
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 19/36 ”Halado”
Hierarchikus Petri hálók ˝ Foháló (super net) - alhálók (subnets): beépítés: bármelyik hely vagy átmenet helyére ˝ o˝ hasonló hálórészek ismétlod p fill_up p rA
ta d d A
t heat
pA t fill
p rB
ta d d B
t reaction p react
p ready t cool
p filled
pB
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 20/36 ”Halado”
Kiterjesztett Petri háló modellek ˝ Petri hálók: feliratokkal • Idozített • óra (megvalósítható spec. "forrás" hellyel) • átmenetekhez tüzelési ido˝ • helyekhez várakozási ido˝ • Színezett Petri hálók: feliratokkal ˝ • jelzopontok (token-ek) diszkrét értékkészletuek ˝ ("szín") • helyekhez megengedett színhalmaz • átmenetekhez és élekhez (diszkrét) függvények ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 21/36 ”Halado”
Vészleállító operátori eljárás ˝ Idozített Peri háló modell pneutr_ready pvess_poiss
(30 sec)
pstart
pT_normal
tfill_neutr
pp_normal
(10 sec) t cooling
pvess_neutr
pvess_cool telectr_off
pready
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 22/36 ”Halado”
Reaktor-szur ˝ o˝ rendszer Reaktormuködés ˝ –4 Színezett Peri háló modell: "feliratok" a1 : if val(praw ) ∈ {”1b”, ”2b”, ”3b”} then ”true” praw pRempt
psolv
1b yy
2b a3
a1
a2
a4
tGR
psemi
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 23/36 ”Halado”
Diszkrét eseményu˝ rendszermodellek megoldása
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 24/36 ”Halado”
DES modellek megoldása Elvi problémakituzés ˝ Adott: • a diszkrét eseményu˝ rendszer modelljének formális leírása • kezdeti állapot(ok) • külso˝ események : rendszer inputok Kiszámítandó: • a belso˝ (állapot és kimenet) események szekvenciája A megoldás algoritmikus! A feladat NP-nehéz! ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 25/36 ”Halado”
Automata modellek megoldása Állapot-átmeneti gráf Megoldás: rendszerállapot szekvenciák állapot-átmeneti gráf (súlyozott irányított gráf) • csúcsok : rendszerállapotok • élek : állapot-átmenetek (modell végrehajtása) • élsúlyok : külso˝ események (rendszer inputok) ˝ Eloállítás: 1. start: az adott kezdeti állapotból 2. új csúcs hozzávétele: a modell végrehajtásával (input hatása is!) ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 26/36 ”Halado”
Lehet NP-nehéz (sztochasztikus és/vagy nem egyértelmu˝ δ állapot-átmeneti
Petri háló modellek megoldása Elérheto˝ ségi gráf Megoldás: jelölés (rendszerállapot) szekvenciák ˝ elérhetoségi gráf (fa) (súlyozott irányított gráf) • csúcsok : jelölések ˝ • élek : ha van átmenet, aminek tüzelése összeköti oket • élsúlyok : az átmenet és a külso˝ események ˝ Eloállítás: 1. start: az adott kezdeti jelölés 2. új csúcs hozzávétele: az egyik engedélyezett átmenet tüzelésével (input hatása is!) ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 27/36 ”Halado”
Lehet NP-nehéz (konfliktushelyzet vagy nem véges muködés ˝ esetén)
Petri háló modellek megoldása Elérheto˝ ségi gráfok Véges eset (1, 0) t1 p1
p2
t1 a,
(0, 1) b,
Nem véges eset t1 p3
p1
p2 t
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 28/36 ”Halado”
Petri háló modellek megoldása Nem véges elérheto˝ ségi gráf Redukció: az ω szimbólummal (1, 0, 0)
t1 p3
t1 (0, 1, 1)
p1
p2
t2 (1, 0, ω)
t2
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 29/36 ”Halado”
Állapot-átmeneti gráf és elérheto˝ ségi gráf ˝ A Petri háló modell elérhetoségi gráfja megegyezik az automata modell állapot-átmeneti gráfjával praw
pRempt
psolv
tGR
psemi
pf1empt
pf2empt
Seeem "r"
tGf1
Sreen
tGf2
pproduct
"nil"
"r"
"r"
"nil"
Seern
Seren
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 30/36 ”Halado”
Diszkrét eseményu˝ rendszermodellek analízise
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 31/36 ”Halado”
Petri háló modellek dinamikus analízise Dinamikus tulajdonságok • viselkedési (kezdeti állapot független) • szerkezeti (struktúrális) (csak a szerkezeti gráftól függ) Viselkedési tulajdonságok ˝ ˝ • elérhetoség (lefedhetoség, irányíthatóság) ˝ • hotpontok, éloség, végesség Szerkezeti tulajdonságok • hely és átmenet invariánsok : ciklikus viselkedés ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 32/36 ”Halado”
Petri háló modellek viselkedési tulajdonságai ˝ ˝ Elérhetoség vizsgálata: elérhetoségi gráf vizsgálatával • adott [kezdeti állapot (µ(I) ), végállapot (µ(F ) )] párhoz • létezik-e egy tüzelési sorozat, úgy, hogy µ(I) [tj0 > µ(1) [tj1 > ...[tjk > µ(F ) Egyéb viselkedési tulajdonságok ˝ • végesség (korlátosság): minden kezdoállapotra ˝ korlátos-e a jelzopontok száma? ˝ • holtpontok (éloség): nem szándékolt jelölés, amelyben nincs engedélyezett átmenet
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 33/36 ”Halado”
Petri háló modellek Példák Holtpont: a (0, 1) jelölés (1, 0) t1 p1
p2
t1 a,
(0, 1) b,
Nem korlátos hely: p3 (1, 0, 0)
t1 p3
t1 (0, 1, 1)
p1
p2
t2 (1, 0, ω)
t2
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 34/36 ”Halado”
Petri háló modellek dinamikus analízisének módszerei Viselkedési tulajdonságok ˝ • megkonstruáljuk az elérhetoségi gráfot ˝ • a definíciónak megfeleloen keresünk a gráf csúcsain • lehet NP-nehéz Szerkezeti tulajdonságok ˝ • megkonstruáljuk a Petri háló gráfjának elofordulási mártixát • lineáris egyenletrendszer megoldását igénylik • polinomiális ideju, ˝ gyakorlatban korlátozott fontosságú ´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 35/36 ”Halado”
Köszönöm a figyelmet!
´ Folyamatmodellezes ´ es ´ modell anal´ızis – PhD kurzus – p. 36/36 ”Halado”
