Diszkrét és hibrid diagnosztikai és irányítórendszerek Diszkrét Eseményu˝ Rendszerek Diagnosztikája és Irányítása Hangos Katalin ¨ ´ ´ Kozleked esautomatika Tanszek ´ Irany´ ´ ıtaselm ´ ´ ´ Rendszer- es eleti Kutato´ Laboratorium ´ ıtastechnikai ´ ´ Automatizal ´ asi ´ Kutato´ Intezete ´ MTA Szam´ es e-mail:
[email protected]
DesHyb-05 – p. 1/32
Modellezés diagnosztikai és irányítási célra
DesHyb-05 – p. 2/32
´ szinkron kompoz´ıcioja ´ Automatak Adott: két automata (állapot-leírása) A1 = (Q1 , Σ1 , δ1 ; qI1 ) , A2 = (Q2 , Σ2 , δ2 ; qI2 )
Az A = A1 || A2 automata A = (Q, Σ, δ; qI ) formális leírása: • Q = Q1 × Q2 • Σ = Σ1 ∪ Σ2 • qI = [qI1 , qI2 ] • állapot-átmeneti függvény
[δ1 (σ, q1 ), δ2 (σ, q2 )] if σ ∈ e1 (q1 ) ∩ e2 (q2 ) [δ1 (σ, q1 ), q2 ] if σ ∈ e1 (q1 ) \ Σ2 δ(σ, [q1 , q2 ]) = [q1 , δ2 (σ, q2 )] if σ ∈ e2 (q2 ) \ Σ1 undefined otherwise DesHyb-05 – p. 3/32
Automata modellek kimenettel Moore automata: a ϕ : Q → ΣO kimeneti függvénnyel megadva AM oore = (Q, Σ, δ; qI ; ΣO , ϕ)
Mealy automata: a Σ ABC módosításával megadva, ΣM ealy = Σ × {ΣO ∪ ε}, ahol ε az üres esemény AM ealy = (Q, ΣM ealy , δ; qI )
Konverzió 01
02
a 1
a / 02
2 b
1
2
a
b
b / 01 b / 02
c 3 03
a / 03
c / 01 3
DesHyb-05 – p. 4/32
´ Pelda: Egyszeru˝ szelep Moore automata leírás NO_FLOW
open one_turn
Valve_closed close one_turn
PARTIAL_FLOW Valve_partially open close one_turn
open one_turn
emergency shut_off Valve_open MAXIMUM_FLOW
DesHyb-05 – p. 5/32
´ ok ´ kimenettel Petri hal Rendszerelméleti leírás: • állapot: jelölés (egy adott idopillanatban) ˝ • bemenet: ◦ nulla be-fokú hely (forrás hely) ◦ nulla be-fokú átmenet (forrás átmenet) • kimenet: (megfigyelheto) ˝ események, azaz tüzelo˝
átmenetek ˝ Egy Petri háló muködési ˝ sorozat nyoma: egy átmenetekbol (mint szimbólumokból) álló string.
DesHyb-05 – p. 6/32
´ Nem-determinisztikus automatak Formális leírás: And = (Q, Σ ∪ ε, δnd ; QI , QF ) • üres esemény • nem egyértelmu˝ hatású esemény ⇒ δnd (qi , σj ) ⊆ Q
Átmeneti (függvény) reláció string inputra: s string, σ szimbólum δnd (q, sσ) = {q ′ : q ′ = δnd (y, σ), y ∈ δnd (q, s) ⊆ Q} • Értéke állapotok halmaza • Argumentuma is lehet állapotok halmaza
DesHyb-05 – p. 7/32
´ Egyszeru˝ pelda Nem determinisztikus automata a a 0
1 b
Állapot átmeneti függvény δnd (0, a) = {0, 1} δnd (0, aa) = {0, 1}
δnd (0, ab) = {0} δnd (0, aab) = {0}
DesHyb-05 – p. 8/32
´ Egyszeru˝ szelep hibaallapotokkal Moore automata leírás 01 b 1h
a
2ah
a
a ε
b
ε
2fh
a 1
ε
2 b
01
a
b
b
a
c
b 3 03
3h
ε 03
DesHyb-05 – p. 9/32
Állapotbecslés
DesHyb-05 – p. 10/32
˝ ege ´ LTI rendszerek megfigyelhetos Problémafelvetés Adott: • állapottér modell (A, B, C) (vagy (Φ, Γ, C)) paraméterekkel • u és y jelek véges idointervallumon ˝ mért értékei
Kiszámítandó: ˝ az állapotváltozó vektor (x) értékei a véges idointervallumon Elegendo˝ kiszámítani: x(t0 ) = x0
DesHyb-05 – p. 11/32
´ Allapot megfigyelo˝ automata Adott: • (nem-determinisztikus) automata • kezdoállapot ˝ • megfigyelt eseménysorozatok (stringek), természetes
projekció P (ε) := ∅ ; P (σ) := σ ha σ = 6 ε P (sσ) := P (s)P (σ) ha σ ∈ Σ, s ∈ Σ∗
Meghatározandó: egy olyan automata, Aobs , amely minden lehetséges s′ = P (s) megfigyelésre meghatározza az azzal összeegyeztetheto˝ állapotokat. Algoritmus: 1. q0obs = {q0 } 2.
qiobs
=
obs , εε....s′ ε...ε δnd qi−1 i
⊆Q DesHyb-05 – p. 12/32
´ szelep allapot ´ Hibas megfigyelo˝ automata
Az automata állapot átmeneti gráfjának része
DesHyb-05 – p. 13/32
¨ es ´ megfigyeles ´ Petri hal ´ okra ´ ´ Jelol – Feladatkituz ˝ es Adott: • egy PN = (P, T, I, O) Petri háló szerkezete, n = |P | • makro-jelölés, azaz V(V, b) = {µ ∈ Nn | V T µ = b} a V
hely-súlyokkal • megfigyelt tüzelési sorozat (string): w = ti1 ti2 ...tik
Meghatározandó: egy olyan µ∗ jelölés, amelyet a valódi µ(k) jelölés lefed (µ∗ℓ (k) ≤ µℓ (k) , ℓ = 1, ..., n) és összeegyeztetheto˝ a megfigyelt stringgel. Algoritmus: 1. µ∗ (0) = 0, j = 1, B0 = b 2. tij tüzel 3. javítjuk a becslést: µ′p (j) = max{µ∗p (j − 1), I(p, tij )}, majd µ∗ (j) = µ′ (j) + µO(tij ) − µI(tij ) 4. javítjuk a korlátot: Bj = Bj−1 − V T (µ′ (j) − µ∗ (j − 1))
DesHyb-05 – p. 14/32
¨ es ´ megfigyeles ´ Petri hal ´ okra ´ Jelol –2
Egyszeru˝ példa: makro-jelölés V T = [1 1 1] és b = 3 (3 jelölo˝ pontunk van)
0. lépés: µ∗ (1) = [0 0 0], B0 = 3 1. lépés: w1 = t1 , µ′ (1) = [0 0 1]T , µ∗ (1) = [1 0 0], B1 = 2
DesHyb-05 – p. 15/32
¨ es ´ megfigyeles ´ Petri hal ´ okra ´ Jelol –3 ˝ Megfigyelo˝ lefedhetoségi gráf (OCG) korlátos Petri hálókra ˝ meg, ahol Csúcsok: (µ∗ /u) pároknak feleltethetok • µ∗ jelölés (a kezdeti valódi µ(0) jelölés nem ismert) • u a becslési hiba (kezdetben u(0) = µ∗ (0))
˝ Élek: az engedélyezett átmenetek tüzelésének feleltethetok meg, élsúly az átmenet azonosítója Az OCG az állapot megfigyelo˝ automata állapot átmeneti gráfjának felel meg egy adott (kísérleti) µ∗ (0) kezdeti becslés mellett.
DesHyb-05 – p. 16/32
¨ es ´ megfigyeles ´ Petri hal ´ okra ´ Jelol –4
!
"
"
!
! "
"
!
!
"
"
! "
"
#
!
"
"
!
! "
"
#
#
"
!
Egyszeru˝ példa OCG gráfja
DesHyb-05 – p. 17/32
Diagnosztika
DesHyb-05 – p. 18/32
´ ´ Diagnosztika allapot megfigyelessel –1 Automata modellel: az állapot megfigyelo˝ automata módosításával Adott: • (nem-determinisztikus) automata (=rendszer modell) Mealy
leírása • kezdoállapot ˝ • nem-megfigyelheto˝ események halmaza (Σuo ⊂ Σ, ε ∈ Σuo ) • megfigyelt eseménysorozatok (stringek): Σ \ Σuo -beli
karakterekkel • diagnosztizálandó nem-megfigyelheto˝ esemény ed
Meghatározandó: egy olyan automata, Adiag , amely minden lehetséges megfigyelésre meghatározza, hogy biztosan megtörtént-e, illetve megtörténhetett-e ed . DesHyb-05 – p. 19/32
´ ´ Diagnosztika allapot megfigyelessel –2 Módosított természetes projekció P (e) := ∅ ha e ∈ Σuo ; P (e) := e ha e ∈ (Σ \ Σuo ) P (se) := P (s)P (e) ha e ∈ Σ, s ∈ Σ∗
Példa: szelep automata c nem megfigyelheto˝ diagnosztizálandó eseménnyel Σuo = {ε, c} a 1
2 b a
b c 3
egy megfigyelés: y = P (aacaacaa) = aaaaaa
DesHyb-05 – p. 20/32
´ ´ Diagnosztika allapot megfigyelessel –3 A Adiag diagnosztizáló automata: az állapot megfigyelo˝ automata olyan módosítása, ahol címkékkel látjuk el az állapotokat (ed nem megfigyelheto˝ diagnosztizálandó esemény) • "N" címkét kapnak azok az állapotok, amelyeket a QI
˝ kezdoállapotból a (Σuo \ ed )-beli nem-megfigyelheto˝ karaktereket is tartalmazó stringekkel lehet elérni • "Y" címkét kapnak azok, amelyekhez vezeto˝ stringekben az
ed legalább egyszer szerepel • ha egy állapot mind "N" mind "Y" féleképpen elérheto, ˝ akkor
mindkét címkéju˝ változatot szerepeltetjük. Adiag -nak (sokkal) több állapota lehet, mint Aobs -nek
DesHyb-05 – p. 21/32
´ ´ Diagnosztika allapot megfigyelessel –4 Diagnosztikai eredmény a k -adik lépésben: ha a Adiag kurrens állapotabeli valamennyi állapot • "N" címkéju, ˝ akkor ed biztos nem következett be (eddig) • "Y" címkéju, ˝ akkor ed legalább egyszer bekövetkezett
valamikor a múltban
DesHyb-05 – p. 22/32
-
/. 3 5 4
,
,
(
$
&
2
&
2
&
%
0
6
*
%
2
+
)
*
*
1
(
$
) &
2
'
$
&
2
$
%
)
)
*
1
(
$
&
0
$
'
&
0
$
%
)
)
+
)
*
&
$
'
*
&
$
%
)
)
´ Egyszeru˝ szelep pelda
a 1
2 b b
a
c
Σuo = {ε, c} , ed = c
3
DesHyb-05 – p. 23/32
¨ ´ Diagnosztika kovetkeztet essel –1 Rendszermodell: 1. lokális ok-okozati összefüggések leírása szabályokkal 2. Petri háló reprezentáció • helyek: predikátumok • átmenetek: szabályok, elofeltétel ˝ és következmény rész ˝ leírása az elofeltételi és következmény függvénnyel
DesHyb-05 – p. 24/32
¨ ´ Diagnosztika kovetkeztet essel –2 Egyszeru˝ példa: autó indítási probléma (nem indul) Szabályok: Gyújtáskapcsoló rossz Biztosíték kiégett Akku üres Akku üres Benzin hiány Nincs gyújtás
⇒ ⇒ ⇒ ⇒ ⇒ ⇒
Nincs gyújtás Nem ég a lámpa Nem ég a lámpa Nincs gyújtás Nem indul a motor Nem indul a motor
(t3 ) (t1 ) (t2 ) (t2 ) (t4 ) (t5 )
Helyek: • gyökér okok: Gyújtáskapcsoló rossz, Biztosíték kiégett,
Akku üres, Benzin hiány. • szimptómák: Nincs gyújtás, Nem ég a lámpa,
Nem indul a motor. DesHyb-05 – p. 25/32
¨ ´ Diagnosztika kovetkeztet essel –3
N P
N
T
I
G O D
B
U
@
T
S
?
S
J
H DI
E
R
G
M J
@
I I
D L
T
DO
R D
?
8
7
T
?
R
KB
?
K
?
B I J
N
A
:
9
G P ? J
Q K K G
; 9
S B
J J
A
P N
O N
N
M J
L
I
J DK
E
G H DI
> B
F
=
9
<
9
?
E
@
C DB
B A
@
@
?
>
Egyszeru˝ példa: autó indítási probléma – Petri háló reprezentáció
DesHyb-05 – p. 26/32
Felügyel˝o irányítás
DesHyb-05 – p. 27/32
´ ıtas: ´ az altal ´ anos ´ ´ Irany´ problema Adott • rendszermodell • irányítási cél
Kiszámítandó bemeneti jelsorozat, amellyel teljesül az irányítási cél Néhány irányítási cél: • stabilizálás • zavarelhárítás • optimális irányítás
DesHyb-05 – p. 28/32
´ ıtasi ´ problema ´ Automata irany´ Rendszer leírás: automata modellel Irányítási cél: • irányítás nélküli (open-loop) viselkedés: L(A) megadásával • kívánt (closed-loop) viselkedés: La specifikáció
megadásával, ahol Lr ⊂ La ⊆ L(A) Felügyelo˝ szabályozó: S • rendszer kimenetek: megfigyelheto˝ események • rendszer bemenetek: Σ ABC feletti stringek (esemény
sorozatok) • beavatkozások: irányítható események • szabályozó muködése ˝ dinamikus: S minden lépésben
kijelöli, hogy a lehetséges események közül melyik ˝ engedélyezett (csak tiltani tud a lehetoségek közül) DesHyb-05 – p. 29/32
´ ıtas ´ Petri hal ´ o´ modellel – 1 Irany´ Irányítási cél: specifikáció • eloírt ˝ feltételek a megengedett/megkívánt jelölésekre (pl.
˝ elérhetoségi feladat – optimális irányítás) • nem kívánt jelölések tiltása
Szabályozó: kiegészítés a szabályozás nélküli Petri hálóhoz (állapot visszacsatolásos szabályozó) • rendszer állapotok: jelölések • beavatkozások: "irányítható" átmenetek tüzelési
feltételeinek módosítása • belso˝ (slack) változók, dinamikus visszacsatolás
DesHyb-05 – p. 30/32
´ ıtas ´ Petri hal ´ o´ modellel – 2 Irany´
Y
V
Z X V Z
V W
V \
\ X
[
V
V Y
Y X [ X
\ X V \
[ X
[
V
Z
W
V
V
Z X
Y X
] X
Specifikáció: a p2 és p3 helyeken ne legyen több két ˝ jelzopontnál (µ(p2 ) + µ(p3 ) ≤ 2)
DesHyb-05 – p. 31/32
Köszönöm a figyelmet!
DesHyb-05 – p. 32/32
