Diszkrét eseményű rendszerek felügyeleti irányításának alapjai

Kovács Gábor

Diszkrét eseményű rendszerek felügyeleti irányításának alapjai Egyetemi jegyzet

BME Irányítástechnika és Informatika Tanszék 2011

2 A munka szakmai tartalma kapcsolódik a "Minőségorientált, összehangolt oktatási és K+F+I stratégia, valamint működési modell kidolgozása a Műegyetemen" c. projekt szakmai célkitűzéseinek megvalósításához. A projekt megvalósítását az Új Széchenyi Terv TÁMOP- 4.2.1/B-09/1/KMR-2010-0002 programja támogatja.

Tartalomjegyzék 1. Bevezetés

5

2. A diszkrét eseményű rendszerek osztálya

7

3. Diszkrét eseményű rendszerek modellezése 3.1. Nyelvek és automaták . . . . . . . . . . . . 3.2. Modellezés véges állapotú automatákkal . . 3.3. Diszkrét eseményű rendszerek nyelvei . . . . 3.4. Összetett rendszerek modellezése . . . . . . 3.5. Alapvető rendszertulajdonságok . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

11 12 19 21 22 25

4. Felügyeleti irányítás 4.1. Az irányítási architektúra . . . . . . . 4.2. Specifikációk megadása . . . . . . . . . 4.3. Irányíthatóság . . . . . . . . . . . . . 4.4. A felügyeleti irányítás meghatározása .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

29 29 32 39 50

5. Felügyeleti irányítások megvalósítása 5.1. Determinisztikus irányítás . . . . . . . . 5.2. Az irányítható események forrása . . . . 5.3. A zárt kör modelljének transzformációja 5.4. A felügyeleti irányítás implementálása .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

53 53 55 56 60

3

4

TARTALOMJEGYZÉK

1. fejezet

Bevezetés Az elmúlt évtizedekben a technológia fejlődésével mind nagyobb és komplexebb rendszerekkel találkozhatunk mind ipari környezetben, mind a kommersz termékek között. Ezek az eszközök, berendezések egyre több funkciót látnak el, egyre több érzékelővel és beavatkozó szervvel rendelkeznek, amelynek köszönhetően irányításuk is egyre nehezebb feladat. Egy korszerű gépkocsiban számos szabályozási kör található, amelyek a blokkolásgátló, az elektronikus fékerőelosztó és differenciálzár, a kipörgésgátló, az adaptív tempomat, vagy éppen az automatikus légkondícionáló megfelelő működéséért felelősek. Ezek mindegyikének megtervezése külön-külön is kihívást jelentő szabályozástechnikai feladat, azonban ezen köröknek egyszerre kell működniük. Néhány közülük egymástól függetlenül (mint például a légkondícionáló és a tempomat), több viszont egymással szorosan együttműködve (a stabilitásért felelős ESP rendszert alkotó ABS, kipörgésgátló, blokkolásgátló és vészfékasszisztens) dolgozik. Előfordulhat, hogy ezen szabályozási körök közül több éppen egymással ellentétes beavatkozó jelet adna ki, például az adaptív tempomat gyorsítana, míg az ESP éppenséggel fékezné az egyik kereket. Együttes működésük leírása, irányítása nem könnyű feladat, még akkor sem, ha az egyes egységek viselkedését jelentősen leegyszerűsítve tekintjük. A megfelelő összhang biztosítása akkor is nehéz feladat elé állíthatja az irányítástechnikust, ha nem a fentiekhez hasonlóan bonyolult, hanem egészen egyszerű alrendszereket, például futószalagokat és pneumatikus munkahengereket kell kezelnie. Ekkor is előfordulhat ugyanis, hogy az alrendszerek nagy száma miatt szinte áttekinthetetlen problémával kell megküzdenie – gondoljunk például egy repülőtéri csomagszállító- és osztályozó rendszerre. A londoni Heathrow repülőtéren közel 48 kilométernyi futószalag szolgál a napi 150 000 csomag szállítására, amelyeket még megfelelően szortírozni, illetve esetenként tárolni is kell. Ilyen méretekben már gondolni kell arra is, hogy a rendszer adott pontján előforduló torlódás vagy meghibásodás esetén milyen más, tartalék utakon juttathatjuk el a poggyászt a rendeltetési helyére. Ugyan a rendszer egyes elemei önmagukban egyszerűen kezelhetők (egy futószalag szabályozása standard feladat), a nagyszámú irányítási kör a teljes rendszer működésének koordinálását 5

6

1. FEJEZET. BEVEZETÉS

jelentősen megnehezíti. Az előzőekben említett rendszerek közös tulajdonsága, hogy olyan önálló részegységekből, alrendszerekből állnak, amelyeket nem csak önmagukban szükséges irányítani, hanem működésük összehangolása is szükséges egy globális cél érdekében. Feltételezve, hogy az alrendszerek szükség esetén már önálló, alsó szintű irányítással rendelkeznek, a diszkrét eseményű rendszerek felügyeleti irányításának eszköztárával ez a feladat megoldható. Első, autóipari példánk esetén különösen kell ügyelnünk a biztonságra, az ilyen rendszerekben az irányítás hibája megengedhetetlen, hiszen egy baleset során akár emberéletekben is eshet kár. Mint látni fogjuk, a megfelelően megtervezett felügyeleti irányítás képes garantálni, hogy a zárt körű működés megfeleljen a tervezési előírásoknak. Természetesen ez kétélű fegyver – amennyiben az irányítási rendszer specifikációja során hibázunk, a szabályozónk zárt körben éppen az előírt hibás működés betartására törekszik majd. Második, repülőtéri példánkban a nehézséget a rendszer nagysága, emberi szem számára áttekinthetetlen mérete okozta. Ezekben az esetekben célszerű a problémát alproblémák együttesére bontani, majd ezeket egyenként megoldani, illetve mindeközben igénybe venni a számítógép segítségét. Természetesen ez csak akkor lehetséges, ha a használt eszköztárunk megfelelően formalizált és jól algoritmizálható. A későbbiekben a felügyeleti irányítások elméletének számos olyan tulajdonságát megvizsgáljuk majd, ami lehetővé teszi, hogy éljünk ezekkel a megoldásokkal. A következőkben a diszkrét eseményű rendszerekre Ramadge és Wonham által kidolgozott felügyeleti irányítások elméletének (Supervisory Control Theory, SCT ) alapjait tárgyaljuk. A 2. fejezet a rendszerosztály lehatárolásával, a diszkrét eseményű rendszerek alapvető tulajdonágaival foglalkozik. A formális leíráshoz szükséges eszközöket a diszkrét eseményű rendszerek modellezéséről szóló 3. fejezet foglalja össze, míg a felügyeleti irányítás fogalmát és tervezését a 4. fejezet mutatja be. Az 5. fejezet röviden kitér néhány olyan kérdésre, ami akkor merül fel, ha az elmélet szerint megtervezett szabályozónkat a gyakorlatban, egy fizikai eszközön szeretnénk megvalósítani. Természetesen ez a jegyzet nem vállalkozhat arra, hogy a felügyeleti irányítás minden területét, a tervezés minden csínját-bínját részletesen bemutassa. A cél az, hogy az olvasó megismerje a megfelelő jelölésrendszert, elsajátítsa a terület alapvető fogalmait és módszereit, valamint azt a szemléletmódot, amelyet a felügyeleti irányítások tervezése megkíván. Ebben szándékoznak segíteni a szöveget kiegészítő ábrák és a témakörökhöz kapcsolódó példák is. Kérem, hogy amennyiben az olvasó a jegyzetben hibát találna, vagy bármilyen észrevétele lenne, jelezze azt a szerzőnek a [email protected] email-címen!

2. fejezet

A diszkrét eseményű rendszerek osztálya Mielőtt belekezdenénk a diszkrét eseményű rendszerek modellezésének és irányításának tárgyalásába, először le kell határolnunk a rendszerosztályt, azaz meg kell határoznunk, mit is értünk pontosan diszkrét eseményű rendszer alatt. Az irányítástechnikai témájú kurzusokban eddig nagyrészt kétféle rendszerosztállyal találkozhattunk. Az első a folytonos idejű rendszereké, amelyek dinamikáját az x˙ = f (x, u, t) differenciálegyenlet írja le. Ezen rendszerek állapottere folytonos, az állapotváltozók vektorára általában igaz, hogy X ∈ Rn . A rendszer működése az időben folytonosan zajlik, a rendszer állapota minden egyes időpillanatban megváltozhat, akár a bemenetek állandósága esetén is. A folytonos idejű rendszerekhez hasonló a diszkrét idejű, avagy mintavételes rendszerek osztálya. Az állapottér itt is folytonosnak tekinthető (habár a digitális rendszerek az adott bitszámú kvantálás miatt valójában nem folytonos és véges állapottérrel dolgoznak), a rendszer dinamikáját a mintavételi időpontokban az xk+1 = f (xk , kT, uk ) differenciaegyenlet írja le. A folytonos idejű rendszerekkel ellentétben itt az állapotok közötti átmenet csak a mintavételi időpontokban, szinkron módon, az órajelhez igazodva mehet végbe. A diszkrét eseményű rendszerek osztálya az előbbiektől két lényeges szempontból is különbözik. Egyrészt állapottere diszkrét, egymástól élesen elkülönülő állapotokból áll: X = {S1 , S2 , . . . , Sn }, amelyek absztrakt, általában nem egy adott állapotváltozó numerikus értékéhez köthető állapotok. Az állapottér lehet véges és végtelen is, azonban a továbbiakban feltételezzük, hogy az állapotok száma véges. Ez a korlátozás a gyakorlat szempontjából nem érdemi megkötés, azonban lehetővé teszi, hogy a továbbiakban ismertetett eszközökkel és módszerekkel kezeljük a diszkrét eseményű rendszereket. A másik lényeges különbség, hogy az állapotok közötti átmeneteket aszinkron módon bekövetkező események indukálják. Az események bekövetkezése azonnali, nulla ideig tart, leginkább tehát egy aszinkron jel felfutó vagy lefutó éléhez hasonlítható. Az állapotváltások eseményekhez kötése azt jelenti, hogy 7

8

2. FEJEZET. A DISZKRÉT ESEMÉNYŰ RENDSZEREK OSZTÁLYA

(a)

(b)

(c)

2.1. ábra. A rendszerosztályok összehasonlítása: folytonos (a), mintavételes (b) és diszkrét eseményű (c)

9 amíg be nem kövezkezik egy esemény, addig a rendszer állapota nem változhat meg. Fontos tulajdonság még, ami az események nulla időtartamából következik, hogy két esemény nem következhet be egyidőben, közöttük mindenképpen fennáll valamilyen sorrendiség. Éppen ezért az eddigi transzformáns rendszerekkel szemben a diszkrét eseményű rendszerek a reaktív rendszerek körébe sorolhatók, hiszen dinamikájuk valamilyen eseményre válaszolva következik be. A három rendszerosztály közötti különbségeket a 2.1. ábra foglalja össze. Az előbbiekben ismertetett tulajdonságokat a következő definícióban foglalhatjuk össze. 2.1. definíció. A diszkrét eseményű rendszerek (DER) olyan, diszkrét állapotokkal rendelkező, eseményvezérelt rendszerek, melyek időbeli alakulása teljes mértékben az aszinkron események bekövetkeztétől függ. Tekintsünk például egy lámpával védett gyalogátkelőhelyet, ahol az átkelőhöz érkező gyalogosoknak a szabad jelzéshez egy gombot kell megnyomniuk (ilyen megoldással gyakran találkozunk nagy forgalmú utakat keresztező, csekélyebb kihasználtságú gyalogátkelőknél), és gondoljuk végig működését! Alapesetben a forgalomirányító rendszer az autóútnak ad szabad jelzést, majd amenynyiben egy érkező gyalogos megnyomja a gombot, számára biztosít szabad utat. Bizonyos idő elteltével, mely alatt a gyalogos feltehetően átér a túloldalra, ismét elindulhat a forgalom, a gyalogosok pedig tilos jelzést kapnak. Világos, hogy ezt a rendszert differenciál- vagy differenciaegyenlettel leírni nem csak nehézkes, hanem felesleges is. Ellenben ha belegondolunk, a rendszer néhány, kitüntetett állapotával már jól jellemezhető. A fenti megfogalmazásból adódóan az állapotok lehetnek például a következők: szabad jelzés az autóúton, váltás a gyalogút szabad jelzésére, szabad jelzés a gyalogúton, váltás az autóút szabad jelzésére. Ugyanakkor a rendszer állapotai jellemezhezők a forgalomirányító lámpák jelzéseivel is: az előző állapotok az autóútról nézve a zöld, sárga, piros, piros-sárga, míg a gyalogátkelő felől a piros, piros, zöld, villogó zöld jelzőlámpa-állapotokat jelentik. Tehát a rendszer állapotai a zöld-piros, sárga-piros, piros-zöld, villogó zöld–piros-sárga kombinációkkal írhatók le. Ez utóbbi állapotfelosztás azonban lehetővé teszi a zöld-zöld pár leírását is, ami természetesen hibás (és remélhetőleg soha be nem következő) működést jelent. Látható, hogy egy rendszer állapotainak felosztása csupán a legritkább esetben egyértelmű, a modellben szereplő állapotoknak és azok számának csak az irányítástechnikus fantáziája és józan belátása szab határt. Természetesen célszerű minél egyszerűbb, minél kevesebb állapotot tartalmazó modellt felállítani, azonban tekintettel kell lenni arra is, hogy ezzel a rendszer egyetlen lényeges tulajdonságát se hagyjuk figyelmen kívül. Gondoljuk most végig, hogy az állapotok közti váltást milyen események indokolhatják! Amennyiben az átkelőhöz gyalogos érkezik, és megnyomja a gombot, az állapotváltást indukál, meg kell állítanunk az autóforgalmat, át kell lépnünk a váltás a gyalogút szabad jelzésére állapotba. Innen egy további lámpaállítással léphetünk a szabad jelzés a gyalogúton állapotba, onnan pedig hasonlóan a továbbiakba. Természetesen fizikailag van lehetőség arra is, hogy

10

2. FEJEZET. A DISZKRÉT ESEMÉNYŰ RENDSZEREK OSZTÁLYA

amint a gyalogos megnyomja a gombot, rögtön villogó zöld jelzést kapjon – a rendszerben ezt nem tiltja semmi, ennek elkerülésére majd megfelelő irányítást alkalmazva nekünk kell ügyelnünk. Mivel a rendszerek irányítása a célunk, így kulcsfontosságú, hogy meghatározzuk, milyen beavatkozási módunk van a rendszer működésébe. Folytonos és mintavételes rendszerek esetében az u beavatkozó jel szerepelt a rendszer differeciál- illetve differenciaegyenletében, így közvetlenül lehetőséget nyújtott az állapotváltásra. Mint láttuk, ez utóbbi a diszkrét eseményű rendszerekben az eseményekhez kötődik, tehát adódik, hogy ezen rendszerosztályt az események bekövetkeztét befolyásolva irányítsuk. Természetesen nem minden eseményre lehetünk hatással, így érdemes a rendszer eseményeit irányítható és nem irányítható események diszjunkt részhalmazára bontani. Irányíthatónak azon eseményeket nevezzük, amelyek bekövetkeztét megtilthatjuk illetve engedélyezhetjük. Tipikusan ilyenek a beavatkozó szervekhez kapcsolódó események, mint például egy motor elindítása vagy leállítása. A nem irányítható események körébe tartoznak azok, amelyekre nincs hatásunk, ilyenek tipikusan a környezeti események, a szenzorok jelei, illetve a felhasználói beavatkozások. Egyszerű példánkban a nyomógomb jele nem irányítható, hiszen a gyalogos szándékaira, mozdulataira nem lehet hatása a szabályozónak. Ezzel szemben a lámpaállításra igen, így az ehhez kapcsolódó események mind irányíthatók. Fontos már most leszögezni, hogy a felügyeleti irányítások elmélete csupán azt engedi meg, hogy a szabályozó az irányítható események bekövetkeztét megtiltsa, azokat azonban a rendszer továbbra is önmaga generálja! Ez azt jelenti, hogy az elmélet szerint a beavatkozó jelünk csupán engedélyező jel, maga a beavatkozás a rendszer kénye-kedve szerint, meghatározatlan, akár végtelen távoli időpillanatban történhet, azaz semmi nem garantálja, hogy beavatkozásunk azonnal (vagy véges időn belül) érvényre jut. Természetesen a szabályozótervezés során ez utóbbi alapkövetelmény, így a felügyeleti irányítás implementációja során kénytelenek leszünk kilépni az elmélet meghatározta keretekből. Mint a fentiekből is látható, ha egy rendszert diszkrét eseményű rendszerként kezelünk, akkor távolról tekintünk rá, és számos részletet nem foglalunk a modellünkbe. Ha egy motornak csupán áll és forog állapotát különböztetjük meg, nem foglalkozunk a fordulatszámmal, leggyakrabban azért, mert feltételezzük, hogy egy folytonos (vagy mintavételes) alacsony szintű szabályozó a motort állandó fordulatszámon tartja. Amennyiben az egyes állapotokon belül a rendszer működésének leírását differenciál- vagy differenciaegyenletekkel tovább finomítjuk, immáron a folytonos tartományban, akkor hibrid rendszerekről beszélhetünk. Ezek tárgyalása azonban jelen jegyzet témakörén kívül esik.

3. fejezet

Diszkrét eseményű rendszerek modellezése Mint az előző fejezetben láttuk, a diszkrét eseményű rendszereket diszkrét állapotterű, az állapotok közötti átmeneteket eseményekhez kötő objektumokként értelmezzük. Ennek következtében olyan eszközre van szükségünk a modellezésükhöz, mely ezeket a tulajdonságokat képes megfelelően leírni. Világos, hogy a folytonos és mintavételes rendszereknél használt differenciál- és differenciaegyenletek nem megfelelőek erre a célra. A matematika és a számítástudomány eszköztárát áttekintve több olyan megközelítést is találunk, mely alkalmas lehet a diszkrét eseményű rendszerek modellezésére. Ezek közül is kiemelkedik azonban a véges állapotú automaták és a reguláris nyelvek eszköztára, ami nem csak hogy megfelel az elvárásoknak, hanem jól ismert és gyakran alkalmazott eszköz az informatika és a mérnöki tudományok területén. A rendszereket modellező, ahhoz irányítást tervező mérnök munkája során olyan eszközöket, például különféle folyamatábrákat alkalmaz, amelyek nem állnak távol a véges állapotú automatáktól, így a diszkrét eseményű rendszerek modellezése során is követheti eddig is alkalmazott gondolatmenetet. A reguláris nyelvek értelmezése már nem áll ilyen közel a mindennapi gondolkodáshoz, azonban segítségükkel számos tulajdonság és művelet pontosan és egyszerűen definiálható, bizonyítható. Ebben a fejezetben először a nyelvekről és automatákról szóló alapismereteket elevenítjük fel, kitérve néhány, szempontunkból különösen lényeges fogalomra. Ezután megvizsgáljuk, miképpen feleltethető meg egy diszkrét eseményű rendszer egy véges állapotú automatának, illetve milyen reguláris nyelveket köthetünk hozzá. A fejezet végén néhány olyan tulajdonságot definiálunk, amely lényeges a diszkrét eseményű rendszerek további vizsgálatának szempontjából. 11

12 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE

3.1. Nyelvek és automaták Nyelvek A formális nyelvek, mint ahogyan a természetes nyelvek is, szimbólumokból (betűkből) épülnek fel. Általánosan egy szimbólumot σ-val jelölünk. 3.1. definíció. Egy nyelv szimbólumainak véges, nem üres készletét a nyelv abcjének tevezzük és Σ-val jelöljük. A természetes nyelvekhez hasonlóan a szimbólumokból szavakat (avagy mondatokat, szimbólumsorozatokat) képezhetünk azok egymás után írásával. 3.2. definíció. Egy szó egy abc szimbólumainak véges sorozata, azaz az s szót szimbólumok egymás után fűzésével kapjuk: s = σ1 σ2 . . . σn , ∀i : σi ∈ Σ. 3.3. definíció. Az ǫ-nal jelölt üres szó egyetlen szimbólumot sem tartalmaz. Az üres szó bármely abc-ből kiválasztható. 3.4. definíció. Egy szó hossza a benne előforduló szimbólum-előfordulások száma. Az s szó hosszát |s|-sel jelöljük. Az üres szó hossza nulla, azaz |ǫ| = 0. A szavak természetesen egyetlen szimbólumot többször is tartalmazhatnak. Az s = σ1 σ2 . . . σn , ∀i : σi ∈ Σ, n > 0 szó hossza az összefűzött karakterek száma: |s| = n. 3.5. definíció. Egy abc k-ik hatványának az adott abc-ből képezhető, k hosszúságú karaktersorozatok összességét nevezzük: Σk = {s = σ1 σ2 . . . σk |∀i : σi ∈ Σ}. Bármely abc nulladik hatványa az üres szót adja vissza: Σ0 = {ǫ}. 3.6. definíció. Egy Σ nyelvből képezhető összes véges szimbólumsorozatot, mely S az ǫ üres szimbólumot is tartalmazza, Σ∗ -gal jelöljük: Σ∗ = i Σi .

3.7. definíció. Egy Σ nyelvbőlSképezhető összes véges, nem üres szimbólumsorozatot Σ+ -szal jelöljük: Σ+ = i6=0 Σi . Σ∗ tehát megadja egy adott abc-ből képezhető összes szó halmazát. Ugyan a Σ∗ ot alkotó szimbólumsorozatok végesek, maga a Σ∗ megszámlálhatóan végtelen sok elemet tartalmaz. 3.1. példa. Legyen Σ = {α, β, γ}. Ekkor Σ0 Σ1 Σ2 Σ∗

= = = =

{ǫ} {α, β, γ} {αα, αβ, αγ, βα, ββ, βγ, γα, γβ, γγ} {ǫ, α, β, γ, αα, αβ, αγ, βα, ββ, βγ, γα, γβ, γγ, ααα, ααβ, . . .}

Egy abc szavainak definiálása után megadhatjuk az egy abc felett értelmezett nyelv értelmezését is.

3.1. NYELVEK ÉS AUTOMATÁK

13

3.8. definíció. A Σ abc felett értelmezett L nyelv az abc-ből képezhető véges hosszúságú szavak egy részhalmaza: L ⊆ Σ∗ . Talán furcsának tűnik, hogy egy nyelvet a szavaival definiálunk, de gondoljuk el, hogy ha az abc-nk például {ajtók, az, záródnak }, akkor a magyar nyelvet ezen szimbólumkészlet felett megadhatjuk az értelmes szimbólumsorozatokkal: Lmagyar = {az ajtók záródnak, záródnak az ajtók }, mely az összes, magyar nyelven értelmezhető kombinációt tartalmazza. Világos, hogy például az ajtók az záródnak az az ajtók mondat nem értelmes. Nyilvánvalóan természetes nyelveket nem érdemes így leírni, és a nyelvtanulásnak is a lehető legrosszabb módja ez, mégis látható, hogy működőképes elgondolás a nyelvet az értelmes szimbólumsorozatok felsorolásával megadni. A következőkben néhány olyan műveletet definiálunk, melyeket a későbbiekben gyakran használunk majd. 3.9. definíció. Legyen u ∈ Σ∗ és v ∈ Σ∗ két szó ugyanazon abc felett, u = σ1 σ2 . . . σn , ∀i = 1 . . . n : σi ∈ Σ és v = τ1 τ2 . . . τm , ∀j = 1 . . . m : τj ∈ Σ. A két szó összefűzése (láncolása, konkatenációja) a cat : Σ∗ × Σ∗ → Σ∗ operátorral írható le, amit a két szóra alkalmazva cat(u, v) = uv = σ1 σ2 . . . σn τ1 τ2 . . . τm ∈ Σ∗ A szavak összefűzése, hasonlóan a szimbólumok összefűzéséhez, egyszerűen úgy történik, hogy az adott szavakat egymás után írjuk. Az összefűzés műveletére a következő tulajdonságok igazak: • cat(s, ǫ) = cat(ǫ, s) = s, ∀s ∈ Σ∗ , tehát az üres szimbólum az összefűzés egységeleme • Az összefűzés nem kommutatív: cat(s, t) 6= cat(t, s), ∀s, t ∈ Σ∗ \ ǫ, s 6= t • Az összefűzés asszociatív: cat(cat(s, t), u) = cat(s, cat(t, u)), ∀s, t, u ∈ Σ∗ • Az összefüggés eredménye is egy szimbólumsorozat, így Σ∗ zárt az összefűzésre nézve, és az összefűzés (szorzás) művelettel együtt Σ∗ egységelemű multiplikatív félcsoportot (monoidot) alkot Az összefűzés műveletét kiterjeszthetjük nem csak szimbólumsorozatokra, hanem nyelvekre is. 3.10. definíció. Az L1 , L2 ⊆ Σ∗ nyelvek összefűzése cat(La , Lb ) = {s = cat(u, v) ∈ Σ∗ |u ∈ La , v ∈ Lb } Két nyelv összefűzésekor tehát az első nyelv minden egyes szavát összefűzzük a második nyelv minden egyes szavával. 3.2. példa. Legyen Σ = {α, β, γ} az abc, a két nyelv pedig L1 = {αβ, αγ} és L2 = {γβ, αα}. Ekkor a két nyelv összefűzése cat(L1 , L2 ) = {αβγβ, αβαα, αγγβ, αγαα}.

14 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE Az elkövetkezőkben a rövidség okán az összefűzés műveletét úgy jelöljük, hogy az adott szimbólumsorozatokat vagy nyelveket egymás után írjuk, pl. s = uv. 3.11. definíció. Egy L ⊆ Σ∗ nyelv Kleene-zárása L∗ ⊆ Σ∗ , amit a következő módon definiálunk: L∗ = {ǫ} ∪ L ∪ LL ∪ LLL . . . A nyelv Kleene-zárása tehát hasonló az abc hatványhalmazához, csak éppen itt nem szimbólumok, hanem nyelvek az elemek. 3.3. példa. Legyen L = {α, αβ, γ}. Ekkor L∗ = {ǫ, α, αβ, γ, αα, αβα, γα, ααβ, αβαβ, γαβ, . . .} Lényeges lehet, hogy ha adott egy karaktersorozatunk, azt vajon tudjuk-e úgy folytatni az abc karaktereinek hozzáfűzésével, hogy egy adott nyelv valamely szavát kapjuk. Ennek eldöntését segíti az adott nyelv prefix-zárásának meghatározása. 3.12. definíció. Egy L ⊆ Σ∗ nyelv prefix-zárása L = {s ∈ Σ∗ |∃t ∈ Σ∗ : st ∈ L} Az L nyelv szimbólumsorozatait az L nyelv prefixeinek nevezzük. Az L nyelv prefixei tehát azon szimbólumsorozatok, amelyek után a Σ abcből képezhető valamely szimbólumsorozatot (beleértve az üres ǫ-t is) fűzve az L egyik szavát kapjuk. Vegyük észre, hogy ǫ minden nyelv prefix-zárásában szerepel! 3.4. példa. Legyen Σ = {α, β, γ}, L = {αβγ, βγ}. Ekkor az L nyelv prefixzárása L = {ǫ, α, αβ, αβγ, β, βγ}, hiszen α után a βγ, αβ után a γ, β után pedig a γ szimbólumsorozatokat fűzve L szavait kapjuk. Vegyük észre, hogy L bármely eleme, esetünkben αβγ illetve βγ után az ǫ üres karaktert fűzve a nyelv adott elemét kapjuk vissza. Általában is igaz, hogy L ⊆ L. 3.13. definíció. Az L nyelvet prefix-zártnak nevezzük, ha L = L. Egy nyelvet tehát akkor nevezünk prefix-zártnak, ha összes prefixét tartalmazza, azaz a nyelv bármely szavát megkaphatjuk úgy, hogy egy másik szava után megfelelő (akár üres) szimbólumokat fűzünk. 3.5. példa. A 3.4. példában szereplő nyelv nem prefix-zárt. Ugyanakkor az L′ = {α, αβ, αβγ, β, βγ} nyelv már prefix-zárt, hiszen L′ = L′ . A későbbiekben több alrendszert tartalmazó diszkrét eseményű rendszerek leírásakor fontos lesz a természetes projekció és annak inverzének értelmezése.


15

3.14. definíció. Egy Σ abc felett értelmezett L nyelv természetes projekciója a Σ′ ⊆ Σ abc-re egy P : Σ∗ → Σ′∗ leképezés, amit a következő módon definiálunk: PΣ′ (ǫ)

=

PΣ′ (σ)

=

PΣ′ (sσ)

=

ǫ

ǫ σ

ha σ ∈ / Σ′ ha σ ∈ Σ′

PΣ′ (s)PΣ′ (σ), ∀s ∈ Σ∗ , ∀σ ∈ Σ

Látható, hogy a természetes projekció tulajdonképpen annyit jelent, hogy az L nyelv szavaiban a Σ′ abc-ben szereplő szimbólumokat ugyanolyan sorrendben szerepeltetjük PΣ′ (L)-ben, míg a Σ′ -ben nem szereplő szimbólumokat egyszerűen kihagyjuk. A természetes projekció művelete ahhoz hasonló, mint amikor egy szerény szókincsű turista egy idegen város repülőterén a bemondásból csupán annyit ért, hogy "Lyon 12", a szöveg többi részét nem képes értelmezni. 3.6. példa. Legyen az abc Σ = {α, β, γ, δ}, az abc felett definiált nyelv pedig L = {αβδ, γαα, βδα, γ}. Határozzuk meg L természetes projekcióját a Σ′ = {α, δ} abc-re! A definíció szerint a természetes projekció az egyes szimbólumokra a következő módon hat: PΣ′ (α) PΣ′ (β)

= =

α ǫ

PΣ′ (γ) PΣ′ (δ)

= =

ǫ δ

Az L nyelv egy szavának természetes projekcióját a definíció harmadik egyenlete alapján képezzük: PΣ′ (αβδ)

= =

PΣ′ (αβ)PΣ′ (δ) = PΣ′ (α)PΣ′ (β)PΣ′ (δ) =

= =

αǫδ = αδ

Vegyük észre, hogy az utolsó sorban kihasználtuk az ǫ üres szó egységelem–tulajdonságát. A teljes L nyelv természetes projekcióját úgy kapjuk, hogy minden egyes szavát levetítjük Σ′ -re: PΣ′ (L)

=

PΣ′ ({αβδ, γαα, βδα, γ}) =

= =

{PΣ′ (αβδ), PΣ′ (γαα), PΣ′ (βδα), PΣ′ (γ)} = {αǫδ, ǫαα, δα, ǫ} =

=

{αδ, αα, δα, ǫ}

16 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE A természetes projekciónak létezik inverze, amire általában röviden csak inverz projekcióként hivatkozunk. ∗

3.15. definíció. A PΣ′ : Σ∗ → Σ′∗ természetes projekció inverze a PΣ−1 : Σ′ → ∗ Σ∗ leképezés, amit az alábbiak szerint definiálunk az L ⊆ Σ′ nyelvre: PΣ−1 (L′ ) = {s ∈ Σ∗ |PΣ′ (s) ∈ L′ } Az inverz projekció tehát azt a nyelvet adja meg, amelyet Σ′ -re vetítve visszakapjuk L′ -t. Vegyük észre, hogy a természetes projekció definíciója értelmében amennyiben létezik olyan σ szimbólum, amelyik szerepel L-ben de nem eleme Σ′ -nek, akkor PΣ−1 (PΣ′ (L)) ⊃ L, tehát a természetes projekciót követő inverz projekció után az eredetinél bővebb nyelvet kapunk. Ennek oka, hogy a természetes projekció a Σ′ -ben nem szereplő σ szimbólumokat L bármely szimbólumsorozatának bármely helyére tetszőlegesen beillesztve PΣ′ (L) nem változik. Ugyanakkor a mind Σ, mind Σ′ abc-ben szereplő szimbólumok pontosan ugyanolyen sorrendben szerepelnek L-ben és L′ -ben. Mindennapi példánkhoz visszatérve ha a turista a "Lyon 12" szavakból szeretne visszakövetkeztetni, hogy mi lehetett az idegen nyelvű bemondás, ugyanúgy gondolhat az "A Lyonból érkező járat 12 percet késik" mint az "A lyoni járathoz beszállás a 12-es számú kapunál" szövegre, hiszen mindkettőből pontosan ugyanazokat a szavakat (és ugyanolyan sorrendben) értette meg. 3.7. példa. Tekintsük a 3.6 péda végeredményeként kapott L′ = {αδ, αα, δα, ǫ} nyelvet, és vetítsük vissza Σ-ra! A Σ abc Σ′ -ben nem szereplő szimbólumai: Σ \ Σ′ = {β, γ}, tehát a β és γ karakterek tetszőleges sorrendben és számban szerepelhetnek az α és δ szimbólumok között. Ez alapján az L′ nyelv szavainak inverz projekciói: PΣ−1 (αδ) PΣ−1 (αα)

= =

(β ∗ γ ∗ )∗ α(β ∗ γ ∗ )∗ δ(β ∗ γ ∗ )∗ (β ∗ γ ∗ )∗ α(β ∗ γ ∗ )∗ α(β ∗ γ ∗ )∗

PΣ−1 (δα) PΣ−1 (ǫ)

= =

(β ∗ γ ∗ )∗ δ(β ∗ γ ∗ )∗ α(β ∗ γ ∗ )∗ (β ∗ γ ∗ )∗

Jól látható, hogy esetünkben is PΣ−1 (L′ ) ⊃ L. A nyelvek, mint ismeretes, négy Chomsky-osztályba sorolhatók. Ezek közül számunkra a harmadik osztályba tartozók (hármas típusú nyelvek), a reguláris nyelvek különös jelentőséggel bírnak. 3.16. definíció. A reguláris nyelvek osztályát egy Σ abc felett az alábbiak szerint definiálhatjuk: 1. Az ∅ üres nyelv reguláris nyelv 2. A csupán az ǫ üres szimbólumot tartalmazó nyelv reguláris nyelv 3. Az abc-nek csupán egyetlen σ ∈ Σ karakterét tartalmazó nyelv reguláris nyelv


17

4. Ha L1 és L2 is reguláris nyelvek, akkor L1 ∪L2 , cat(L1 , L2 ) és L∗1 valamint L∗2 is reguláris nyelvek 5. Semmilyen más Σ feletti nyelv nem reguláris A reguláris nyelvek osztályába tartozó nyelvek számos tulajdonsága közül számunkra kettő az, ami kitüntetett. Az egyik, hogy ezek leírhatók reguláris kifejezésekkel, amik megkönnyítik kezelésüket. A másik, esetünkben még ennél is jelentősebb tulajdonságuk pedig az, hogy leírhatók véges állapotú automatákkal.

Véges állapotú automaták A véges állapotú automaták az emberi gondolkodásmódhoz közel álló, vizuálisan is könnyen ábrázolható, átlátható formalizmust kínálnak, nem véletlen, hogy használatuk a mérnöki gyakorlatban is mindennapos. Sokszor már egy rendszer tervezésekor is állapotgép formájában fogalmazzuk meg a lehetséges működést, de a fejlesztési folyamat végén, a szabályozót valamilyen folyamatábrára alapuló nyelven implementálva is állapotgépeket használunk a háttérben. Kézenfekvő tehát, hogy a véges állapotú automaták eszköztárát használjuk nyelvek megadására. A következőkben áttekintjük a véges állapotú automaták felépítését, működését, és bevezetjük a továbbiakban is használt jelölésrendszert. 3.17. definíció. Egy véges állapotú automata a G = (Q, Σ, ρ, q0 , F ) ötössel írható le, ahol • Q az állapotok véges halmaza • Σ a szimbólumok véges halmaza • ρ : Q × Σ → Q az állapotátmeneti függvény • q0 ∈ Q a kezdeti állapot • F ⊆ Q az elfogadó állapotok (végállapotok) halmaza A véges állapotú automata kiindulási állapota a q0 kezdeti állapot, ahonnan a beérkező σ ∈ Σ szimbólumok hatására a ρ állapotátmeneti függvény által meghatározott mozgási szabályok szerint halad végig a q ∈ Q állapotokon: a ρ(q, σ) függvény azt az állapotot adja meg, ahová q-ból a σ szimbólum hatására kerülünk. Amennyiben az automata egy adott szimbólumsorozat hatására az F elfogadó állapotok valamelyikébe érkezik, akkor azt mondjuk, az automata az adott szimbólumsorozatot elfogadta a nyelv egy szavának. A véges állapotú automaták a reguláris nyelvek osztályát fogadják el. Az automatákat állapotátmeneti diagramként a 3.1. ábrán látható módon ábrázoljuk. Az automaták állapotait körökkel, míg a lehetséges átmeneteket az állapotok közötti nyilakkal jelöljük. Az elfogadó állapotokat kettős körvonallal, míg a kezdeti állapotot egy belé vezető, de nem másik állapotból induló nyíllal jelöljük.

18 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE α S1

S2

α

S3

β γ

δ S4 β

3.1. ábra. Véges állapotú automata 3.8. példa. Határozzuk meg a 3.1. ábrán látható automatát leíró ötöst! • Q = {S1, S2, S3, S4} • Σ = {α, β, γ, δ} • Az állapotátmeneti függvény: ρ(S1, α)

=

S2

ρ(S2, β) ρ(S3, α) ρ(S3, γ)

= = =

S3 S2 S4

ρ(S4, β) ρ(S4, δ)

= =

S4 S1

A δ állapotátmeneti függvény más esetekben nem definiált! • q0 = S1 • F = {S1} 3.18. definíció. Egy automatát determinisztikusnak nevezünk, ha állapotátmeneti függvénye egyértelmű, azaz |ρ(q, σ)| = {0, 1}, ∀q ∈ Q, ∀σ ∈ Σ. A determinizmus tehát azt jelenti, hogy az automata egy állapotból egy adott szimbólum hatására csakis egyetlen állapotba kerülhet (amennyiben egyáltalán definiált átmenet az adott szimbólum hatására – természetesen ezt nem követeljük meg). Ugyanazt a nyelvet egy determinisztikus és egy nem determinisztikus automata is elfogadhatja, a kettő pedig átalakítható egymásba. Mivel célunk a szabályozótervezés, ezért a továbbiakban csak determinisztikus automatákkal foglalkozunk.

3.2. MODELLEZÉS VÉGES ÁLLAPOTÚ AUTOMATÁKKAL

19

3.9. példa. Határozzuk meg a 3.1 ábrán látható automata által elfogadott nyelvet! Az automata abc-je Σ = {α, β, γ, δ}, így az általa elfogadott nyelvben is ezek a szimbólumok szerepelhetnek. Az automata kezdeti állapota az S1 állapot, mely egyúttal az egyetlen elfogadó állapot is. A kezdeti állapotból az automata az α szimbólum hatására az S2 állapotba kerül, ahonnan csak β hatására mozoghat tovább, az S3 állapotba. Eddig tehát az egyetlen olyan karaktersorozat, aminek elfogadására esély látszik, αβ. Az S3 állapotból az automata az α szimbólum hatására visszakerülhet az S2 állapotba, ahonnan viszont csak az S3 állapotba léphet tovább, mégpedig a β szimbólum érkeztekor. Itt tehát egy hurokról van szó, ha az αβ szimbólumsorozat után akárhányszor (beleértve a nullát is!) αβ szimbólumsorozat érkezik, akkor ugyanúgy az S3 állapot lesz az aktív. Tehát az a szimbólumsorozat, amivel eljuthatunk az S3 állapotba, nem más, mint αβ(αβ)∗ . Vegyük észre, hogy ez nem azonos (αβ)∗ -gal, ez utóbbi ugyanis megengeni, hogy az αβ sorozat egyszer se következzen be, amivel nem jutnánk el az S3 állapotba. Az S3 állapotból a β szimbólum mellett a γ is kimozdítja az automatát, mégpedig az S4 állapotba. Ott egy hurkot (önhurok, self-loop) is találunk, azaz egy olyan átmenetet, aminek kezdő- és végállapota is ugyanaz az állapot. Ez esetünkben azt jelenti, hogy az S4 állapotban akárhány alkalommal érkezik a β szimbólum, az automata az S4 állapotban marad. Továbblépni az S1 állapotba a δ szimbólum érkezésével tud. Mivel az S1 állapot elfogadó állapot, így az a karaktersorozat, amivel a kezdeti állapotból egy elfogadó állapotba (esetünkben vissza a kezdőállapotba) jutunk: αβ(αβ)∗ γβ ∗ δ. Mivel a példánkban a kezdeti és az elfogadó állapot megegyezik, ezért az előbbi karaktersorozatot akárhányszor (a nullát is megengedve) ismételve elfogadó állapotba jutunk, így az automata által elfogadott nyelv: (αβ(αβ)∗ γβ ∗ δ)∗ . Az automaták és nyelvek közötti megfeleltetés a determinizmus kérdésén túl sem egy-egy értelmű. Egyetlen determinisztikus automata csak egy nyelvet fogadhat el, az adott nyelvet viszont több automata is elfogadhatja. Ezek közül azonban létezik egy minimális állapotszámú.

3.2. Modellezés véges állapotú automatákkal A diszkrét eseményű rendszerek modelljét a mérnöki gondolkodáshoz közel álló véges állapotú automatával szokás megadni, ami lehetővé teszi, hogy a rendszer eseményeit tartalmazó, absztraktabb nyelvi leírás helyett az állapotokra koncentráló, gyakorlatiasabb eszközt használjunk erre a célra. A rendszer állapotai egyértelműen megfeleltethetők az automata állapotainak, szimbólumkészletként pedig az események halmazát használhatjuk. Jelentős különbség azonban, hogy míg az előzőekben egy nyelvet elfogadó automatáról beszéltünk, most azt a nyelvet generáló automataként tekintjük. Ez a különbség a leírásban és a tulajdonságokban nem jelentkezik élesen, inkább csak szemléletbeli különbségről van szó. Az elfogadó automatánál azt feltételezzük, hogy a szimbólumok valahonnan kívülről érkeznek, mivel azonban mi

20 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE olyan rendszereket szeretnénk modellezni, amelyek eseményeiket maguk generálják, érdemes változtatni a nézőpontunkon. 3.19. definíció. Egy G diszkrét eseményű rendszert a G = (Q, Σ, ρ, q0 , Qm ) ötös írja le, ahol • Q az állapotok halmaza • Σ az események irányítható és nem irányítható események diszjunkt részhalmazaira osztható halmaza: Σ = Σc ∪ Σu , Σc ∩ Σu = ∅ • ρ : Q × Σ → Q a részleges állapotátmeneti függvény • q0 ∈ Q a rendszer kezdeti állapota • Qm ⊆ Q a jelölt állapotok halmaza Látható, hogy a leírás valóban egy véges állapotú automatát takar. Fontos azonban, hogy a szimbólumok halmazát az eseményekhez kötöttük, így azt két diszjunkt részhalmazra bonthatjuk. Másik különbség, hogy a véges állapotú automatáknál használt végállapot (avagy elfogadó állapot) helyett a jelölt állapot (marking state vagy marked state) fogalmát vezetjük be. A változás oka az, hogy egy diszkrét idejű rendszer működése során nem feltétlenül tekinthetők végállapotnak a kitüntetett állapotok. Fontos kiemelni, hogy az állapotátmeneti függvény csak részleges, azaz előfordulhat, hogy egy adott állapotban egy adott szimbólumra nem értelmezett. Ha a rendszer q állapotában a σ esemény értelmezett, akkor azt ∃ρ(q, σ) módon jelöljük. A későbbi vizsgálatokhoz érdemes kiterjeszteni az állapotátmeneti függvényt úgy, hogy azt ne csak szimbólumokon, hanem szimbólumsorozatokon is értelmezzük. 3.20. definíció. A G diszkrét eseményű rendszer kiterjesztett állapotátmeneti függvénye a ρ′ : Q × Σ∗ → Q leképezés, amit a következő módon definiálunk: ρ′ (q, σ) ρ′ (q, sσ)

= =

ρ(q, σ), ∀q ∈ Q, ∀σ ∈ Σ ρ′ (ρ′ (q, s), σ), ∀q ∈ Q, ∀s ∈ Σ∗ , ∀σ ∈ Σ

A következőkben állapotátmeneti függvény alatt mindig a kiterjesztett állapotátmeneti függvényt értjük, és a ρ szimbólumot is ρ : Q × Σ∗ → Q értelemben használjuk. 3.10. példa. Képzeljünk el egy egyszerű masinát, például egy szerszámgépet. A gépnek három állapota van: tétlen (Idle), dolgozik (Working) és meghibásodott (Down). A masina generátora tehát ezt a három állapotot fogja tartalmazni: Q = {I, W, D}. A gép működését a következő módon írjuk le: amennyiben utasítást kap, a gép elkezd dolgozni, majd amikor a munkadarabot kellőképpen megmunkálta (például megfelelő mélységű lyukat fúrt belé), önműködően leáll. A megmunkálás

3.3. DISZKRÉT ESEMÉNYŰ RENDSZEREK NYELVEI

21

W α |

λ β |

I

µ

D

3.2. ábra. A masina modellje közben a gép lerobbanhat, a hibát aztán a kezelőszemélyzet hárítja el. A működést végiggondolva a következő négy eseményt köthetjük a masinához: elindul (α), leáll (β), elromlik (λ), megjavítják (µ). Az események közül az indításra és a javításra van hatásunk, ugyanakkor a gép önműködően áll le, és (sajnálatos módon) a meghibásodás eseményének bekövetkeztét sem tudjuk meggátolni. Így hát Σc = {α, µ} és Σu = {β, λ}. Az állapotátmeneti függvényt szintén a gép működése alapján állíthatjuk öszsze. A masina az I állapotból az α (elindul) eseményt generálva a W állapotba kerül, majd onnan a β (leáll) esemény generálásával az I, vagy λ (lerobban) eseménnyel a D állapotba jut. A D állapotból a µ (javítás) eseményt generálva juthat vissza az I állapotba. A fentiekben már kihasználtuk, hogy a masina kezdeti állapota a tétlen (I). Jelölt állapotnak is ezt érdemes választani, hiszen ez az állapot jelenti azt, hogy masinánk készen áll egy újabb munkadarab megmunkálásra. Így q0 = I és Qm = {I}. A masina generátora a 3.2 ábrán látható. Figyeljük meg, hogy a jelölt állapotokat az eddigiekhez hasonlóan kettős körvonal jelzi, és ugyanígy jelöli a kezdeti állapotot a belé forrás nélkül vezető nyíl. Szokás az irányítható eseményekhez tartozó átmeneteket a jobb átláthatóság érdekében egy vonallal áthúzni – itt is ez látható az α és µ címkéjű átmenetek nyilain.

3.3. Diszkrét eseményű rendszerek nyelvei Mivel a diszkrét eseményű rendszereket generátoraikkal írjuk le, természetesen nyelveket is rendelhetünk hozzájuk. 3.21. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer által generált nyelvet L(G)-vel jelöljük és a következő módon definiáljuk: L(G) = {s ∈ Σ∗ |∃ρ(q0 , s)}

22 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE Látható, hogy a rendszer által generált nyelven azon szimbólumsorozatokat értjük, amelyek a rendszer működése során előfordulhatnak. Természetesen lehetséges, hogy ez a leírás túlzottan bőséges, így érdemes bevezetnünk egy, a kiemelten fontos állapotokhoz tartozó nyelvet is. 3.22. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer által jelölt nyelvet Lm (G)-vel jelöljük és a következő módon definiáljuk: Lm (G) = {s ∈ Σ∗ |ρ(q0 , s) ∈ Qm } A rendszer által jelölt nyelv tehát azon szimbólumsorozatokat adja meg, amelyeket generálva a kezdeti állapotból a jelölt állapotok valamelyikébe juthatunk. A rendszerhez köthető nyelvek között az alábbi reláció áll fenn: Lm (G) ⊆ Lm (G) ⊆ L(G) ⊆ Σ∗ Vegyük észre, hogy mivel L(G)-t a véges állapotú automatával modellezett rendszer generálja, a következő fontos tulajdonságot állapíthatjuk meg. 3.1. tétel. Egy diszkrét eseményű rendszer által generált L(G) nyelv mindig prefix-zárt, azaz L(G) = L(G). A prefix-zártság azonban általában nem áll fenn a rendszer által jelölt Lm (G) nyelvre. 3.11. példa. Tekintsük ismét a 3.2. ábrán látható masinát! Mi a rendszer által generált és jelölt nyelv? A masina kezdeti állapota az I állapot, onnan az α eseményt generálva a W állapotba jut. A W állapotból β generálásával vagy λµ generálásával a D állapoton keresztül jut vissza az I állapotba. Így tehát a masina az α(β|λµ) eseménysorozatot generálja ciklukusan, folyamatos működés esetén. Azonban a generált nyelv minden olyan eseménysort is tartalmaz, amit egy köztes állapotban generál a rendszer, így a masina által generált nyelv: L(G) = (α(β|λµ))∗ . A masina által jelölt nyelv az, amivel jelölt állapotba, tehát esetünkben a kezdeti állapotba jutunk. Következésképpen a generált nyelvvel szemben nem tartalmaz minden prefixet: Lm (G) = (α(β|λµ))∗ .

3.4. Összetett rendszerek modellezése Gyakran előfordul, hogy egy diszkrét eseményű rendszer több alrendszerből épül fel, melyek egymástól többé-kevésbé függetlenül működnek. Ezekben a helyzetekben alkalmazható a szinkron szorzat vagy szinkron kompozíció művelete, mely a két alrendszer közös működését írja le. 3.23. definíció. Adott két diszkrét eseményű rendszer, G1 és G2 . A két rendszer együttes működését leíró L(G1 k G2 ) nyelvet a következőképpen definiáljuk: L(G1 k G2 ) = PΣ−1 (L(G1 )) ∩ PΣ−1 (L(G2 )) 1 ∪Σ2 1 ∪Σ2

3.4. ÖSSZETETT RENDSZEREK MODELLEZÉSE

23

A szinkron szorzat működésének megértéséhez az alábbi informális gondolatmenettel élhetünk. Az inverz projekció 3.15. definíciójára visszagondolva vegyük észre, hogy PΣ−1 (L(G1 )) a Σ1 abc-ben szereplő eseményeket olyan 1 ∪Σ2 sorrendben tartalmazza, ahogy L(G1 )-ben szerepelnek, míg a csak Σ2 -ben szereplő eseményekre az inverz projekció nem ad megkötést. Hasonló a helyzet G2 esetén is. Mivel a szinkron szorzat a két nyelv metszetét veszi, ezért a csak a Σ1 -ben meglévő események valójában csak olyan sorrendben következhetnek, ahogy L(G1 )-ben, és ugyanez igaz Σ2 eseményeire is. A közös események, tehát amik Σ1 ∩ Σ2 -ben szerepelnek, csak olyan sorrendben következhetnek, amit mindkét alrendszer nyelve lehetővé tesz, tehát olyan módon, ahogyan mindkét rendszer egyenként is generálná őket. Ezáltal természetesen egyik rendszer sem generálhatja szabadon saját eseménysorát, amennyiben egy, a másik rendszerrel közös eseményhez ér, be kell várnia azt, így gyakorlatilag a két rendszert a szorzat műveletével szinkronizáljuk. Mint már láttuk, a nyelvekkel való munka nehéz, így amennyiben lehetséges, jobban szeretjük a műveleteket a diszkrét eseményű rendszerek generátorain végezni. Nincs ez másként a szinkron szorzat esetén sem, így érdemes a műveletet az alrendszerek generátorain is leírni. 3.24. definíció. Adott két diszkrét eseményű rendszer, melynekek ismertek generátorai, G1 = (Q1 , Σ1 , ρ1 , q0,1 , Qm,1 ) és G2 = (Q2 , Σ2 , ρ2 , q0,2 , Qm,2 ). A közös működésüket leíró rendszer generátora G = G1 k G2 = (Q, Σ, ρ, q0 , Qm ), ahol • Q = Q1 × Q2 a két rendszer állapotterének Descartes-szorzata. A q = (q1 , q2 ) jelölés azt írja le, hogy a q ∈ Q állapot a G1 rendszer q1 ∈ Q1 és a G2 rendszer q2 ∈ Q2 állapotának együttese. • Σ = Σ1 ∪ Σ2  (ρ1 (q1 , σ), ρ2 (q2 , σ))    (ρ1 (q1 , σ), q2 ) • ρ(q, σ) = (q1 , ρ2 (q2 , σ))    nem definiált

σ ∈ Σ1 ∩ Σ2 és ∃ρ1 (q1 , σ), ∃ρ2 (q2 , σ) σ ∈ Q1 \ Q2 és ∃ρ1 (q1 , σ) σ ∈ Q2 \ Q1 és ∃ρ2 (q2 , σ) egyébként

• q0 = (q0,1 , q0,2 )

• Qm = Qm,1 × Qm,2 A szinkron szorzat állapotai tehát állapotpárok, amik a két alrendszer állapotainak minden lehetséges kombinációját lefedik, abc-je pedig a két alrendszer abc-jének uniója. A szinkron szorzat generátora a (q1 , q2 ) állapotból akkor vált állapotot egy σ esemény hatására, ha az az alrendszer, melynek abc-je tartalmazza σ-t, állapotot vált. Ha σ csak az egyik alrendszer eseménye, akkor G1 k G2 állapotának csak egyik komponense változik, pl. (ρ(q1 , σ), q2 )-re. Amennyiben σ közös esemény, akkor csak azokban az állapotokban következhet be, amelyek mindkét alrendszernek olyan állapotát írják le, ahol σ engedélyezett. A szinkron szorzat generátorának kezdeti állapota a két alrendszer kezdeti állapotainak párja, jelölt állapota pedig minden olyan állapot, amelynek legalább egyik komponense jelölt állapota a megfelelő alrendszernek.


W1 α

W2 α β2

|

µ1

D1

I2

|

β1 I1

λ2

|

|

λ1

µ2

D2

3.3. ábra. A két masina generátora A szinkron szorzat műveletének két speciális esetét is megkülönböztetjük. Ha a két alrendszer abc-je diszjunkt, azaz Σ1 ∩ Σ2 = ∅, akkor keverésről (shuffle), míg ha megegyezik, azaz Σ1 = Σ2 , akkor illesztésről (meet) beszélünk. Előbbi esetben a közös modellben a két rendszer továbbra is teljesen függetlenül működik egymástól, hiszen nincsen közös eseményük, míg utóbbi esetben minden esemény szinkronizációra kerül, azaz a két rendszer egyformán fog működni. 3.12. példa. Vegyünk ezúttal két masinát, amelyek indítási eseménye közös, többi eseménye azonban nem! Mi lesz a 3.3. ábrán látható G1 és G2 rendszerek szinkron szorzatának generátora? A szinkron szorzat állapottere az egyes alrendszerek állapotainak párjaiból áll, tehát esetünkben Q = {I1 I2 , I1 W2 , . . . , D1 D2 }. A könnyebb átláthatóság érdekében érdemes az állapotokat mátrix-elrendezésben felrajzolni, hasonlóan a 3.4. ábrán látható elrendezéshez, ahol a G1 illetve G2 állapotainak megfelelő komponensek egy soron illetve oszlopon belül azonosak. A szinkron szorzat generátorának kezdőállapota q0 = I1 I2 , jelölt állapotai pedig mindazon állapotok, melyeknek legalább egyik komponense jelölt állapot az adott alrendszerben. Mivel a G1 és G2 alrendszerekben rendre I1 és I2 a jelölt állapotok, ezért Qm = {I1 I2 , I1 W2 , I1 D2 , W1 I1 , D1 I2 }. A szinkron szorzat generátorának abc-je a két rész-abc uniója, tehát Σ = {α, β1 , β2 , λ1 , λ2 , µ1 , µ2 }. Az állapotátmeneti függvény definiálásakor tekintsük először az I1 I2 állapotot. Mivel G1 -ben az I1 átmenetből a W1 állapotba vezet átmenet α eseménnyel, és G2 -ben hasonlóan létezik az α eseményhez tartozó I2 -W2 él, ezért G1 k G2 -ben is kell definiálnunk egy α-hoz tartozó átmenetet, ami I1 I2 -ből W1 W2 -be vezet. Tekintsük most az I1 W2 állapotot. Ugyan G1 -ben az I1 állapotból indul ki az α átmenethez tartozó esemény, G2 generátorának W2 állapotából viszont nem, ellenben α ∈ Σ2 , így G1 k G2 I1 W2 állapotából nem indulhat ki α-hoz tartozó átmenet. Ugyanakkor, mivel G2 W2 állapotából indul ki β2 -höz tartozó él és β2 ∈ / Σ1 , ezért G1 k G2 -ben definiálnunk kell egy β2 -höz tartozó, I1 W2 -ből I1 I2 -be vezető élet. Hasonló okból definiáljuk a λ2 eseményhez tartozó, I1 W2 -ből I1 D2 -be vezető élt is.

3.5. ALAPVETŐ RENDSZERTULAJDONSÁGOK

25

µ2 |

β2 I1 I2

λ2

I 1 W2

I 1 D2

|

µ2

α

β1

|

β1

β1

µ2

|

β2 W1 I 2

W1 W2

λ1

W1 D 2

D1 W2

µ1

λ1

λ1

β2 D1 I 2

λ2

|

|

µ1

λ2

D1 D2

|

µ2 3.4. ábra. A G1 k G2 szinkron szorzat generátora A további éleket az előzőek alapján definiálva megkaphatjuk a G1 k G2 szinkron szorzat 3.4. ábrán látható generátorát.

3.5. Alapvető rendszertulajdonságok A következőkben néhány olyan alapvető tulajdonságot tekintünk át, ami szükséges a felügyeleti irányítások tervezési módszertanának megértéséhez. 3.25. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer q ∈ Q állapotát elérhetőnek nevezzük, ha ∃s ∈ Σ∗ : ρ(q0 , s) = q Amennyiben ∀q ∈ Q elérhető, akkor a G rendszert elérhetőnek nevezzük. Az elérhetőség szemléletesen azt fejezi ki, hogy a rendszer állapotgráfjában található-e út a kezdeti állapotból az adott állapotba. Vegyük észre, hogy a definíció nem tartalmaz megkötést a generált eseménysorozat tagjainak irányíthatóságára!

26 3. FEJEZET. DISZKRÉT ESEMÉNYŰ RENDSZEREK MODELLEZÉSE 3.26. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer q ∈ Q állapotát detektálhatónak nevezzük, ha ∃s ∈ Σ∗ : ρ(q, s) ∈ Qm Amennyiben ∀q ∈ Q detektálható, akkor a G rendszert detektálhatónak nevezzük. A detektálhatóság tehát valamennyire párja az elérhetőségnek, azt mondja meg, hogy az adott állapotból található-e olyan út, amely a jelölt állapotok egyikébe vezet. Mivel a jelölt állapotok kitüntetettek, ezért a detektálhatóság úgy is felfogható, hogy az adott állapot meglátogatásáról értesülhetünk-e a későbbiekben egy jelölt állapotba kerülés formájában. 3.27. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer takaros, ha elérhető és detektálható is. Különösen fontos tulajdonság a blokkolás, tehát az, hogy van-e a rendszerünknek olyan állapota, amelybe kerülve a továbbiakban nem működik megfelelően, azaz nem fejez be egy műveletsort. 3.28. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer blokkoló, ha Lm (G) ⊂ L(G) A fenti definíció szerint akkor nevezzük a rendszert blokkolónak, ha létezik L(G)-ben olyan s eseménysorozat, amely nincs benne Lm (G) prefix-zártjában, azaz nem találni olyan u eseménysorozatot, hogy su eseménysorozat mentén a kezdeti állapotból a jelölt állapotok valamelyikébe jussunk. Avagy, egyszerűbben szólva, létezik olyan eseménysorozat, amelynek mentén nem jutunk el a kezdeti állapotból egyetlen jelölt állapotba sem. Egyszerűen definiálhatjuk, hogy egy rendszer mikor nem blokkoló. 3.29. definíció. A G = {Q, Σ, ρ, q0 , Qm } diszkrét eseményű rendszer nem blokkoló, ha Lm (G) = L(G) A definíció azt mondja, hogy a rendszer akkor nem blokkoló, ha minden eseménysorozat folytatható úgy, hogy annak mentén jelölt állapotba jussunk. Könnyen belátható, hogy a detektálható rendszerek nem blokkolóak. A nemblokkolás azonban a detektálhatóságnál enyhébb feltétel, nem beszél például a nem elérhető állapotokról. Világos, hogy ha ezek közül van nem detektálható, akkor a rendszer sem lesz detektálható. Mivel azonban ezek az állapotok nem elérhetőek, így a rendszer működése közben nem jut el az adott állapotba, tehát ennek következtében a blokkolás kérdésére nem lesz hatásuk, a rendszer ettől függetlenül lehet nem blokkoló. A blokkolásnak két típusát különböztetjük meg aszerint, hogy a blokkolt állapotában lévő rendszer hogyan viselkedik.

3.5. ALAPVETŐ RENDSZERTULAJDONSÁGOK

q1

q3

q5

q2

q4

q6

27

q7

3.5. ábra. Példa a rendszertulajdonságok vizsgálatához 3.30. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer q állapota holtpont (deadlock), ha q elérhető és ∀σ ∈ Σ : ∄ρ(q, σ) A holtpont tehát, mint nevéből is kitűnik, azt jelenti, hogy a rendszer egy adott állapotba érve "megáll", további eseményeket nem generál. 3.31. definíció. A G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszer állapotai közül a Q′ ⊆ Q \ Qm halmazba tartozók livelock blokkolást valósítanak meg, ha ∀q ∈ Q′ : • q elérhető • ∃σ ∈ Σ : ∃ρ(q, σ) • ∀σ ∈ Σ: ha ∃ρ(q, σ), akkor ρ(q, σ) ∈ Q′ A livelock tehát azt jelenti, hogy a rendszer az állapotainak egy olyan, jelölt állapotot nem tartalmazó halmazába kerül, melyből többé nem kerül ki. Szemben a holtponttal, a rendszer generál(hat) eseményeket, de ennek ellenére sem kerül soha jelölt állapotba, hiszen a definíció harmadik pontja szerint bármilyen eseménysorozatot is generál, azok mindvégig a livelock-állapotok halmazában maradnak. 3.13. példa. Tekintsük a 3.5. ábrán látható diszkrét eseményű rendszert és vizsgáljuk meg a tulajdonságait! • Elérhetőség: mivel a q6 állapot nem elérhető, ezért a rendszer nem elérhető • Detektálhatóság: mivel a q2 , q4 és q7 állapotok nem detektálhatóak, ezért a rendszer nem detektálható • A rendszer takaros alrendszere a 3.6 ábrán látható


q1

q3

q5

3.6. ábra. A 3.5 ábrán látható rendszer takaros alrendszere • Deadlock : a rendszer q7 állapotba lépve deadlock-állapotba kerül. Vegyük észre, hogy a q6 állapot nem deadlock-állapot, hiszen nem elérhető! • Livelock: a q2 −q4 állapotok livelock-ot alkotnak, hiszen a rendszer közöttük mozoghat ugyan, de a két állapot által alkotott halmazból nem jut ki, így jelölt állapotba sem jut

4. fejezet

Felügyeleti irányítás Ebben a fejezetben a felügyeleti irányítás témakörét járjuk körül, azaz górcső alá vesszük, hogy miképpen tudunk egy diszkrét eseményű rendszerhez megfelelő szabályozót tervezni. Először próbáljuk meg megfogalmazni, mi is a felügyeleti irányítás célja, azaz mi az irányítási probléma! 4.1. definíció. A felügyeleti irányítás feladata az, hogy zárt körben biztosítsa a rendszer specifikációknak megfelelő működését. A következőkben ennek az egyelőre túlzottan általánosnak tűnő definíciónak a fogalmait tisztázzuk.

4.1. Az irányítási architektúra Mint már korábban is szó volt róla, a diszkrét eseményű rendszerek eseményeit két diszjunkt részhalmazra, az irányítható és nem irányítható események halmazára (előző jelölésünket megtartva Σc és Σu ) oszthatjuk. Ezek közül az előbbi az, amin keresztül a rendszer működését befolyásolni tudjuk. A felügyeleti irányítás képes arra, hogy az irányítható események bekövetkeztét meggátolja, illetve engedélyezze, azonban az események generálását továbbra is a rendszer maga végzi, amennyiben ezt a szabályozó lehetővé teszi. Az irányítási architektúrát az 4.1. ábra szemlélteti. A felügyeleti irányítás feladata az, hogy a rendszer működését, azaz a szakasz által generált eseményeket megfigyelve engedélyezze vagy letiltsa az irányítható események bekövetkeztét. A felügyeleti irányítás tehát ahhoz a forgalomirányító rendőrhöz hasonlít, aki egy kereszteződésben állva az egyes irányból érkező gépjárművek áthaladását kezének különféle mozdulataival engedélyezi vagy megtiltja. Egy-egy jármű áthaladásában a rendőr nem vesz részt (nem ő vezet, nem ő tolja át a kereszteződésen), csupán megengedi, hogy az adott jármű áthaladhasson. Az, hogy ez valóban megtörténik-e, és ha igen, mikor, az már a szakaszt alkotó autóvezetőktől, és nem a forgalmat irányító rendőrtől függ. 29

30

4. FEJEZET. FELÜGYELETI IRÁNYÍTÁS

Σu Szakasz Σc

Γ

Felügyeleti irányítás

4.1. ábra. Az irányítási architektúra Mint ahogyan a KRESZ is pontosan szabályozza, hogy a forgalomirányító rendőr milyen mozdulatokkal utasíthatja az autósokat, érdemes esetünkben is bevezetni az irányítási minta fogalmát. 4.2. definíció. A Σ = Σc ∪ Σu , Σc ∩ Σu = ∅ eseményhalmaz felett definiált γ irányítási minták Γ készlete az események olyan részhalmazait tartalmazza, melyek az összes nem irányítható eseményt magukban foglalják: Γ = {γ ∈ P wr(Σ)|Σu ⊆ γ} Az irányítási minták tehát az engedélyezett események lehetséges kombinációit (a 4.1. ábrán a kapcsolóállásokat) adják meg. Világos, hogy mivel a nem irányítható események bekövetkeztét a felügyeleti irányítás nem képes letiltani, így azok minden egyes irányítási mintában szerepelnek. Az irányítási minták segítségével már definiálhatjuk magát a felügyeleti irányítást is. 4.3. definíció. Egy G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszerhez tartozó felügyeleti irányítás egy V : L(G) → Γ leképezés. A felügyeleti irányítás tehát nem más, mint egy olyan leképezés, amely megadja, hogy a rendszer által generált különféle eseménysorozatok után mely irányítási mintákat kell alkalmazni, azaz mely események lesznek engedélyezettek, miután egy adott eseménysorozat bekövetkezett. Amennyiben a G diszkrét eseményű rendszerre alkalmazzuk a V felügyeleti irányítást, akkor a zárt rendszerre V /G-ként (V irányítás a G rendszer felett) hivatkozunk. Itt a szakasz már nem önmagában működik, hanem irányítható eseményeinek bekövetkeztét a felügyeleti irányítás befolyásolja az irányítási mintáknak megfelelően, így a rendszer működésének leírására a szakasz által a zárt körben generált illetve jelölt nyelv szolgál.

4.1. AZ IRÁNYÍTÁSI ARCHITEKTÚRA

31

4.4. definíció. A V felügyeleti irányítás alatt álló G diszkrét eseményű rendszer által generált nyelvet L(V /G)-vel jelöljük, és a következőképpen definiáljuk: • ǫ ∈ L(V /G) • Ha s ∈ L(V /G) és σ ∈ V (s), továbbá sσ ∈ L(G), akkor sσ ∈ L(V /G) • Semmilyen más szimbólumsorozat nem eleme L(V /G)-nek 4.5. definíció. A V felügyeleti irányítás alatt álló G diszkrét eseményű rendszer által jelölt Lm (V /G) nyelv a rendszer jelölt nyelvének és a zárt körben generált nyelvnek a metszete: Lm (V /G) = L(V /G) ∩ Lm (G) A definíció értelmében ha a rendszer zárt körben már generálta az s szimbólumsorozatot, akkor a következő szimbólum csak olyan lehet, amit irányítás nélkül is képes lenne generálni, és ezen felül benne kell lennie az L(s) irányítási mintában. Ebből következik, hogy L(V /G) ⊆ L(G). Néhány különleges esettől eltekintve elvárjuk a felügyeleti irányítástól, hogy ne vigye blokkoló állapotba a rendszert. A nem blokkoló felügyeleti irányítást a blokkolás és a felügyeleti irányítás definíciói alapján a következőképpen definitáljuk. 4.6. definíció. A G rendszer feletti V felügyeleti irányítás nem blokkoló, ha Lm (V /G) = L(V /G). 4.1. példa. Tekintsük ismét masinánkat (3.2. ábra), amelyhez a következő felügyeleti irányítás adott: • V (ǫ) = Σ • V (α) = {β, λ, µ} • V (αµ) = {β, λ, µ} • Az összes többi s szimbólumsorozatra V (s) = Σu Határozzuk meg a zárt kör által generált és jelölt nyelvet, valamint hogy blokkolóe a V felügyeleti irányítás! Ha a rendszer kezdeti állapotában van, azaz eddig az ǫ üres karaktersorozatot generálta, akkor a felügyeleti irányítás minden esemény bekövetkeztét engedi. Mivel azonban G kezdeti állapotában csak az α eseményt generálhatja, így az egyetlen esemény, ami bekövetkezhet, az α, azaz α ∈ L(V /G). Az α esemény után G-ben β és λ is bekövetkezhet, és mivel mindkettőt megengedi a felügyeleti irányítás, így {αβ, αλ} ⊂ L(V /G). Az αλ eseménysort G-ben µ generálása követi, amit V is engedélyez, így tehát αλµ ∈ L(V /G). Az αλµ és αβ eseménysorozatok után a szakasz csak α eseményt generálhatja, a felügyeleti irányításunk csupán β-t és λ-t engedélyezi (ezekez azonban minden esetben, hiszen nem irányítható események!), ezért L(V /G)-nek már semmilyen más szimbólumsorozat nem lehet eleme: L(V /G) = {α, αβ, αλ, αλµ} = α(β|λµ).

32


A zárt körben jelölt nyelv Lm (G) = (α(β|λµ))∗ és L(V /G) metszete, azaz Lm (V /G) = α(β|λµ). Rögtön látható, hogy Lm (V /G) = L(V /G), tehát a V felügyeleti irányítás nem blokkoló. Vegyük észre, hogy ezzel együtt a kezdeti állapotába viszzatérve a masina zárt körben már nem működik tovább, mivel azonban a kezdeti állapot egyúttal jelölt állapot is, így az irányítás a definíció szerint nem blokkoló.

4.2. Specifikációk megadása Az előzőekben már láthattuk, hogyan képes egy bizonyos működést biztosítani a felügyeleti irányítás. Azonban ahhoz, hogy megítéljük, vajon a zárt körű működés kielégítő-e, meg kell fogalmaznunk a rendszerrel szembeni elvárásokat, a specifikációkat. Folytonos szabályozási rendszerek esetén a specifikációk általában valamilyen, a zárt körrel kapcsolatos dinamikus jellemző (túllövés, beállási idő stb.) előírását, vagy pedig modell alapú szabályozótervezési módszerek alkalmazása esetén magának a zárt körnek a modelljét jelentik. Diszkrét eseményű rendszereknél is a zárt kör valamilyen elvárt tulajdonságát írjuk elő, egyéb megfogalmazás híján reguláris nyelv(ek) illetve generátoraik formájában. 4.7. definíció. A G = (Q, Σ, ρ, q0 , Qm ) rendszerhez tartozó specifikáció egy E nyelvvel vagy az azt generáló S = (QS , Σ, ρS , qS,0 , QS,m ) diszkrét eseményű rendszerrel adható meg. A specifikáció és a rendszer között csupán annyi kapcsolatot követelünk meg, hogy abc-jük megegyezzen – illetve a gyakorlatban csupán annyit, hogy ΣS ⊆ ΣG legyen. Ha vannak olyan események, amiket a specifikáció minden állapotában engedélyezünk, akkor minden állapothoz egy hurkot (az adott állapotból önmagába mutató átmenetet) kell definiálnunk, amelyhez az adott eseményeket rendeljük. Mint később látni fogjuk, a szabályozótervezés során használt algoritmus a specifikáció abc-jében nem szereplő σ ∈ ΣG \ ΣS eseményeket a specifikáció által mindig, minden állapotában megengedettnek tekinti, így az ilyen eseményeket nem kell szerepeltetnünk a specifikációban. Mivel a specifikáció maga is diszkrét eseményű rendszer, ezért az ismert tulajdonságok és műveletek értelmezhetőek rajta. Ezek közül is kiemelkedik a szinkron szorzat jelentősége, hiszen lehetővé teszi, hogy több rész-specifikációból alkossunk egy teljes specifikációt, ezáltal egyszerűsítve a megkívánt zárt körű működés megadását. Természetesen a leglényegesebb kérdés az, hogyan tervezzünk specifikációt. Mivel helyesen megtervezett felügyeleti irányítás esetén a rendszer azt a működést fogja követni, amit a specifikáció előír, így ez utóbbit hibásan definiálva a zárt körű működés is a rosszul megfogalmazott specifikációt követi majd, azaz a rendszer működése eltér az eredetileg elképzelttől. A specifikációk megadásának mikéntjére általánosságban nehéz választ adni, a következőkben mégis megpróbálunk bemutatni néhány alapvető specifikáció-típust, amikből építkezve előírásokat fogalmazhatunk meg a különféle rendszerek zárt körben történő

4.2. SPECIFIKÁCIÓK MEGADÁSA

33

működésére. Van azonban néhány általános igazság, amit csekély számú kivételtől eltekintve érdemes szem előtt tartanunk: • Soha ne próbáljuk meg teljes egészében leírni a megkívánt zárt körű működést! Inkább alkalmazzunk kis, néhány állapotú specifikációkat, így sokkal kisebb eséllyel tévedünk. • A specifikáció állapotai általában nem feleltethetők meg egyértelműen a rendszer állapotainak, így ne állapotokban, hanem eseményekben, eseménysorozatokban gondolkodjunk! • Ne bonyolítsuk túl a dolgokat! Tiltott állapotok Az első specifikáció-típus rögtön kivételt jelent a szabályok alól. Tételezzük fel, hogy adott egy G = (Q, Σ, ρ, q0 , Qm ) diszkrét eseményű rendszerünk, a célunk pedig meggátolni azt, hogy a rendszer a QI ⊆ Q állapotok valamelyikébe kerüljön. A specifikációt ekkor úgy állítjuk elő, hogy egyszerűen töröljük az eredeti rendszerből a tiltott állapotokat, azaz S = (Q′ , Σ, ρ′ , q0 , Q′m ), ahol Q′ = Q \ QI és Q′m = Qm \ QI . Természetesen a ρ′ : Q′ × Σ → Q′ állapotátmeneti függvényt is újra kell definiálnunk a következők szerint: ρ(q, σ) ∀q ∈ Q′ , σ ∈ Σ, ρ(q, σ) ∈ Q′ ′ ρ (q, σ) = nem definiált egyébként Az új állapotátmeneti függvény tehát nem értelmezett azon q ∈ Q′ , σ ∈ Σ párokra, amelyekre az eredeti ρ(q, σ) függvény QI -beli állapotot adott volna. A specifikáció kezdeti állapotának kijelölésekor feltételeztük, hogy q0 ∈ / QI , de ennek ellenkezője esetén a rendszer kiindulásakor már tiltott állapotban lenne, ami megoldhatatlan feladatot jelent. A fentiekben leírt módon kapott S rendszernek érdemes elérhető alrendszerét venni, hiszen elképzelhető, hogy léteztek olyan állapotok, amelyek csak a tiltott állapotokon keresztül voltak elérhetők, így S-ben nem elérhetők. Ez az egyszerű művelet csökkenti a specifikáció állapotainak számát, és ezáltal a szabályozótervezés során szükséges számítási időt. 4.2. példa. Tekintsük ismét a masinánkat és adjuk meg azt a specifikációt, mely szerint a masina nem kerülhet lerobbant (D) állapotba! A tiltott állapot QI = {D}, így a specifikációnk állapottere Q′ = {I, W }. Mivel a tiltott állapot nem jelölt állapot, így Q′m = Qm = {I}. Az állapotátmeneti függvényből a D állapot törlése miatt törölnünk kell a ρ(W, λ) = D és ρ(D, µ) = I átmeneteket, így az új állapotátmeneti függvényünk ρ′ : {I, W } × Σ → {I, W }, amit csak a következő esetekben és módon értelmezünk: ρ′ (I, α) = W és ρ′ (W, β) = I. A kiadódó specifikáció generátora az 4.2. ábrán látható.

34


W

|

α β I

4.2. ábra. A masina lerobbanását tiltó specifikáció generátora

Események váltakozása Az előírások alaptípusai közé tartozik az az eset, amikor a zárt körben egy rendszer két eseményének bekövetkeztét csak egymással váltakozva engedjük meg. Ilyen lehet például egy tartály feltöltése és ürítése, ahol a két művelet ebben a sorrendben kell, hogy kövesse egymást, hiszen sem az üres tartályból történő szivattyúzás, sem a tartály túlcsordulása nem megengedett. Természetesen ügyelni kell a kezdeti állapotra is, hiszen nem mindegy, hogy a rendszer ürítésekor a tartály üres vagy tele állapotban van. A 4.3. ábrán látható specifikáción az α − β váltakozást írjuk elő, ahol az α eseménynek mindenképpen meg kell előznie a β-t, azaz a tartály esetében az α esemény a feltöltést, míg a β esemény az ürítést jelképezi, a tartály pedig kezdetben üres. Vegyük észre, hogy a specifikációban szereplő egyik esemény sem irányítható, azaz csupán nem irányítható eseményeket használva írtuk elő a zárt körű működést, így nem élhetünk azzal az egyszerű megoldással, hogy az egyes állapotokban az α illetve β események bekövetkeztét letiltjuk. Hogy hogyan biztosítható mégis (ha egyáltalán biztosítható) az előírt zárt körű működés, az attól függ, hogy a rendszerben van-e olyan irányítható esemény, amelynek letiltásával valahogy mégis meg tudjuk akadályozni az α–β események nem megfelelő sorrendű váltakozását. Ennek részleteit a következő alfejezetben fogjuk áttekinteni.

Σ \ {α, β}

Σ \ {α, β} α

q0

q1 β

4.3. ábra. Események váltakozását leíró specifikáció

4.2. SPECIFIKÁCIÓK MEGADÁSA Σ \ {α, β}

35

Σ \ {α, β} α

q0

Σ \ {α, β} α

q1 β

q2 β

4.4. ábra. Kételemű buffert leíró specifikáció

Buffer Gyakori eset, hogy egy rendszer, például egy egymást követő gépekből álló gyártócella, valamilyen buffert használ, ahol a munkadarabok ideiglenes tárolása történik. Egyazon buffer egyes gépeknek bemeneti, míg másoknak kimeneti tárolója, így ilyenkor a gépek működését leíró specifikációban kell a buffer megfelelő kezelését előírnunk, magyarán azt, hogy ne csorduljon túl, illetve hogy ne próbáljunk az üres bufferből elemet kivenni. A 4.4. ábrán egy kételemű bufferhez tartozó specifikáció látható (az egyelemű buffer esete megegyezik a váltakozó eseményekével, ld. 4.3. ábra). A buffer kezdetben üres, a töltés eseményét α-val, míg az ürítést β-val írjuk le. Látható, hogy az ürítés csak akkor engedélyezett, ha legalább egy elem már van a bufferben, míg a betöltés eseménye nem engedélyezett, ha a buffer két elemet is tartalmaz. Nagyobb bufferekhez tartozó specifikációk hasonlóan írhatók le, az állapotok száma a buffer kapacitásánál egyel nagyobb (hiszen az üres, azaz 0 elemet tartalmazó állapotot is jelöljük), a szomszédos állapotok között pedig a betöltési és ürítési eseményekhez tartozó átmenetek vezetnek. A fenti specifikációra tekintve úgy tűnhet, mintha az egy vermet valósítana meg. Azonban sem az események, sem ezáltal az állapotok nem hordozzák azt az információt, hogy a munkadarabok milyen sorrendben követik egymást, azaz az elemek között nem teszünk különbséget. Valójában tehát a fenti specifikáció mind verem, mind FIFO, mind véletlen elérésű bufferhez tartozhat.

Hozzáférés közös erőforráshoz Amennyiben rendszerünk több alrendszerből áll, gyakran előfordul, hogy össze kell hangolnunk az alrendszerek hozzáférését egy erőforráshoz. Jelölje az erőforrás i.-ik alrendszer általi lefoglalását αi , míg elengedését βi . Ekkor az erőforráshoz való hozzáférést két alrendszer esetén a 4.5. ábrán látható specifikáció írja le, mely megtiltja annak lefoglalását, amíg az erőforrást korábban lefoglaló alrendszer el nem engedi azt. Amennyiben az alrendszerek modellje már tartalmazza az αi − βi események váltakozását, akkor a specifikáció a 4.6. ábrán láthatóra egyszerűsödik.

36

4. FEJEZET. FELÜGYELETI IRÁNYÍTÁS Σ \ {α1 , α2 , β1 , β2 } α1 α2 q0

q1

Σ \ {α1 , α2 , β2 }

β1

q2

Σ \ {α1 , α2 , β1 }

β2

4.5. ábra. Közös használatú erőforráshoz való hozzáférést leíró specifikáció Σ\

S

i

q0

βi

S

i

αi

Σ\

S

i

αi

q1

S

i

βi

4.6. ábra. Közös használatú erőforráshoz való hozzáférést leíró specifikáció, amennyiben a hozzáférés és elengedés váltakozását a rendszer önmagában rögzíti

Előírt eseménysor Egyes esetekben előfordulhat, hogy bizonyos eseményeket egymás után kell végrehajtanunk úgy, hogy közben más események bekövetkeztét megtiltjuk. Például egy keveréket kell elkészítenünk adott receptúra szerint, mégpedig úgy, hogy előbb az egyik, majd a másik komponenst töltjük a keverőüstbe, és csak ezután kapcsoljuk be a mixert. Ebben az esetben a 4.7. ábrán láthatóhoz hasonló specifikációt alkalmazhatunk. Példánkban az αβγ eseménysorozat az, amit pontosan ebben a sorrendben, megszakítás nélkül kell végrehajtanunk, ezért képezzük az előírt szimbólumsorozat prefixeihez tartozó ǫ, α és αβ címkéjű állapotokat. Mindegyik állapotból csak egyetlen átmenetet definiálunk, mégpedig az adott prefixet folytató szimbólumhoz (rendre α, β és γ) tartozót, melynek célállapota a következő prefix-állapot, illetve az utolsó prefix-állapot esetén a kezdőállapot. Fontos, hogy a kezdeti állapotban az összes, az αβγ sorozatban nem szereplő eseményt engedélyezzük! Amennyiben az előírt eseménysort más események is megszakíthatják, de az αβγ események generálását továbbra is kizárólag ebben a sorrendben engedjük meg, a 4.8. ábrán látható specifikációt alkalmazhatjuk. Az előző esethez képest a változást az jelenti, hogy a prefix-állapotokban az αβγ sorozathoz nem tartozó összes eseményt engedélyezzük, azonban azok nem okoznak állapotváltást, így az előírt eseménysorunk elemei továbbra is csak az előzőleg definiált módon követhetik egymást.

4.2. SPECIFIKÁCIÓK MEGADÁSA

37

Σ \ {α, β, γ} ǫ

α

α

β

αβ

γ 4.7. ábra. Előírt eseménysorra vonatkozó specifikáció

Σ \ {α, β, γ} ǫ

Σ \ {α, β, γ} α

α

Σ \ {α, β, γ} β

αβ

γ 4.8. ábra. Előírt eseménysorra vonatkozó specifikáció, amennyiben az eseménysor eseményei között más eseményeket is megengedünk

Tiltott eseménysor Az előző eset ellentettjének tekinthető az, amikor az αβγ eseménysor bekövetkeztét szeretnénk megtiltani. Ez azt jelenti, hogy például az αβ, αγ, αγαβ eseménysorok megengedettek, csak az αβγ hármas nem. A megfelelő specifikációt úgy képezhetjük, hogy a tiltott eseménysor mindegyik prefixének képzünk egy állapotot, ezekből az állapotokból pedig a tiltott eseménysorozat következő eseménye a következő prefix-állapotba, a szimbólumsorozat kezdőeleme az első prefix-állapotba, míg minden más esemény a kezdőállapotba vezet. Kivétel az utolsó prefix-állapot (példánkban az αβ prefixhez tartozó), ahonnan nem definiálunk az utolsó szimbólumhoz tartozó átmenetet, magyarán az utolsó szimbólum generálását nem engedjük meg, ha már csak az hiányzik a tiltott szimbólumsorozatból. Ezt mutatja a 4.9. ábra. Amennyiben nem csak közvetlenül egymás után nem engedjük meg a tiltott eseménysorozatot, hanem a benne szereplő események más eseményekkel elválasztva sem követhetik egymást (pl. tiltjuk az αµλβδγ eseménysorozatot is), akkor az előző specifikációt módosítanunk kell a 4.10. ábra által mutatott módon. Ebben az esetben a prefix-állapotokból csak olyan esemény hatására kerülünk vissza a kezdeti állapotba, amelyik benne van a tiltott eseménysorban, de nem közvetlenül az adott prefix után. Ezért láthatjuk az ábrán a második, α címkéjű állapotból a kezdeti állapotba vezető γ címkéjű élet: ha α után γ szimbólumot generál a rendszer, akkor megszakad a tiltott eseménysor.

38


Σ\α

α β

α ǫ

α

αβ α

Σ \ {α, β} Σ \ {α, γ}

4.9. ábra. Tiltott eseménysorra vonatkozó specifikáció

Σ\α

Σ \ {α, γ}

Σ \ {β, γ} β

α ǫ

α γ

αβ α

β 4.10. ábra. Tiltott eseménysorra vonatkozó specifikáció, amennyiben az események nem csak közvetlenül egymás után tiltottak

4.3. IRÁNYÍTHATÓSÁG

39

4.3. Irányíthatóság Az előzőekben körüljártuk, hogy hogy a felügyeleti irányítás hogyan képes valamilyen zárt körű működést megvalósítani, illetve azt, hogy mit értünk a zárt körrel támasztott elvárásokat leíró specifikáció alatt. Arról azonban eddig nem beszéltünk, vajon hogyan definiáljuk, hogy a zárt kör működése megfelel-e a specifikációnak. Kézenfekvő ötletként felmerülhet, hogy azt mondjuk, a zárt kör akkor felel meg az elvárásoknak, ha pontosan a specifikáció által megadott nyelvet generálja. Azonban lehetséges, sőt, általában igaz, hogy a specifikáció bizonyos részben tágabb teret enged a zárt kör működésének, mint amennyit a szakasz teljesíteni képes, így az irányíthatóságot nem érdemes a két nyelv egyenlőségre megszorítani. Arra azonban ügyelnünk kell, hogy zárt körben a rendszer semmi olyasmit ne tegyen, amit a specifikáció nem enged meg, tehát a zárt körű működés során megfelelő irányítással meg kell gátolnunk a specifikáció által nem megengedett eseménysorozatok generálását, amennyiben ez egyáltalán lehetséges. Arra a kérdésre, hogy találhatunk-e ilyen szabályozót, az irányíthatóság tulajdonsága ad választ, melyet a fentiek értelmében általánosságban nem, csak két konkrét nyelvre (a szakasz és a specifikáció nyelvére) definiálhatunk, mégpedig a következők szerint. 4.8. definíció. Egy K ⊆ L ⊆ Σ∗ nyelv irányítható L-re nézve, ha ∀s ∈ K, ∀σ ∈ Σu : sσ ∈ L ⇒ sσ ∈ K. avagy rövidebb formában: KΣu ∩ L ⊆ K. A fenti definíció értelmében a K nyelv akkor irányítható L-re nézve, ha minden prefixe után egy nem irányítható eseményt fűzve amennyiben az adott eseménysorozat benne van L-ben, akkor benne van K-ban is. Azaz K prefixei között nincs olyan, ami után L generálhatna olyan nem irányítható eseményt, amivel kilépnénk K-ból. A feltételben csak a nem irányítható σu események szerepelnek, az irányíthatóak nem. Ennek magyarázata az, hogy az irányítható eseményeket egy megfelelő felügyeleti irányítás alkalmazásával letilthatjuk. Azaz ha például s ∈ K, α ∈ Σc , sα ∈ L de sα ∈ / K, akkor egy olyan felügyeleti irányítást alkalmazva, amire α ∈ / V (s), az sα eseménysorozatot a zárt kör nem generálhatja, azaz a zárt kör nyelve már nem lép ki K-ból. Tehát az irányíthatóság feltétele akár úgy is megadható, hogy K akkor irányítható az L-re nézve, ha ∃V : L → Γ felügyeleti irányítás, hogy L(V /G) ∈ K. Vegyük észre, hogy a definíció azt nem követeli meg, hogy a rendszer minden K-ban lévő eseménysorozatot generáljon, csupán azt, hogy egyetlen olyat se generáljon, ami nincsen benne K-ban! Tehát a K-ra nézve irányítható L nyelvhez található olyan felügyeleti irányítás, ami biztosítja, hogy L(V /G) ⊆ K, az azonban egyáltalán nem biztos, hogy található olyan irányítás is, amivel L(V /G) = K.

40


β q0

| α

q1

γ |

q2

δ 4.11. ábra. A 4.3. példa generátora 4.3. példa. Tekintsük a 4.11. ábrán látható diszkrét eseményű rendszert, ahol Σc = {α, γ} és Σu = {β, δ}. Irányítható-e a rendszer által generált nyelvhez képest a K = (αβ, αγ) nyelv? A K nyelv prefix-zártja K = {ǫ, α, αβ, αγ}, míg a rendszer által generált nyelv L = L(G) = (αβ)∗ αγδ. Tekintsük sorra a K-ban lévő eseménysorozatokat: • ǫ: mivel nincs olyan σ nem irányítható esemény, amire ǫσ = σ ∈ L, ezért K eddig irányítható (ugyan ǫα = α ∈ L, de egyrészt α ∈ Σc , másrészt α ∈ K) • α : L-ben α után β és γ események következhetnek be, amik közül β nem irányítható, ugyanakkor αβ ∈ K, tehát K még mindig irányítható • αβ: ismét csak az α esemény következhet, ami irányítható esemény, így nem releváns az irányíthatóság szempontjából • αγ: mivel az αγ eseménysorozat után L a δ eseményt is generálhatja, ugyanakkor αγδ ∈ / K, ezért az irányíthatóság feltétele sérül Látható, hogy K-nak van olyan prefixe, ami után L-ben lehetséges eseményt fűzve kilépünk K-ból, így K nem irányítható. 4.4. példa. Az irányíthatóság fogalmát szemléletesebbé teszi, ha a rendszer és a specifikáció generátorát együtt tekintjük. Vegyük elő ismét a 4.2. példában létrehozott specifikáció-generátort (4.2. ábra) és a masinát (3.2. ábra), és döntsük el, irányítható-e a specifikáció! A specifikáció az (αβ)∗ nyelvet generálja, ami az előző példában leírtak alapján nem irányítható. Ugyanezt látni már a generátorokat összehasonlítva is. A 4.12. ábrán a szakasz és a rendszer generátorai láthatók egymra rajzolva, a specifikációt szürke színnel jelölve. Jól látható, hogy létezik olyan nem irányítható eseményhez tartozó átmenet (a λ eseményhez tartozó W → D átmenet), amely kivezet a specifikációból, így sérül az irányíthatóság 4.8. definíció szerinti feltétele.


41

W β

I

α |

|

λ D

µ

4.12. ábra. Az irányíthatóság szemléltetése A 4.3. példában használt nyelv tehát nem irányítható, azaz nem találhatunk olyan felügyeleti irányítást, ami a szakasz működését a specifikáció által megadottakra szorítaná. Látható azonban, hogy a specifikáció nyelvének egyik szimbólumsorozatát, αβ-t tartalmazó nyelv irányítható lenne L-hez képest, és világos, hogy ez a nyelv sem sérti a specifikáció előírásait. Kérdés, hogy általában hány ilyen nyelv létezik, és létezik ezek közül olyan, ami leginkább megfelel a specifikációknak. Mindenekelőtt definiáljuk, mit értünk egy nyelv résznyelve alatt. 4.9. definíció. A K ⊆ Σ∗ nyelv egy L ⊆ Σ∗ nyelv résznyelve, azaz K ⊆ L, ha s ∈ K ⇒ s ∈ L, ∀s ∈ K, azaz ha minden K-ba tartozó s szimbólumsorozat egyben L eleme is. Egy adott L nyelvből számos módon kiválaszthatunk résznyelveket, mivel azonban mi most az irányíthatóságot tartjuk szem előtt, válogassunk ezen tulajdonság szerint. 4.10. definíció. Legyen C(K) a K nyelv azon résznyelveinek száma, amik irányíthatóak L-re nézve: C(K) = {M ⊆ K|M Σu ∩ L ⊆ M } 4.1. tétel. A C(K) halmaz zárt az unió műveletére nézve és létezik egyetlen szupremális eleme, a legnagyobb irányítható résznyelv: [ K ↑C = sup C = M M ∈C(K)

A legnagyobb irányítható résznyelv fogalma kulcsfontosságú, így érdemes végiggondolnunk, mit is takar a fenti definíció. Jelöljük K −1 -el illetve M −1 -el azokat az eseménysorozatokat, amiknek bekövetkeztét K illetve M nem engedi meg:

42


K −1 = L \ K és M −1 = L \ M . A 4.10. definíció szerint M ⊆ K, ∀M ∈ C(K), így M −1 ⊇ K −1 , ∀M ∈ C(K), magyarán amit K tilt (avagy amit K nem enged meg), azt egyetlen S irányítható résznyelve sem engedi meg. Mivel a 4.1. tétel szerint K ↑C = M ∈C(K) , így K ↑C ⊇ M, ∀M ∈ C(K), amiből következik, hogy (K ↑C )−1 ⊆ M −1 , ∀M ∈ C(K). Tehát a legnagyobb irányítható résznyelv, K ↑C mindent tilt, amit K, ugyanakkor ezen kívül a lehető legkevesebbet, tehát legkevésbé korlátozza a szakasz mozgásterét úgy, hogy az megfeleljen a specifikációnak. A legnagyobb irányítható résznyelv (supremal controllable sublanguage) helyett ezért más, talán még szemléletesebb elnevezések is használatosak K ↑C -re: legmegengedőbb résznyelv (most permissive sublanguage), legkevésbé korlátozó résznyelv (least restrictive sublanguage). 4.5. példa. A 4.3. példában láttuk, hogy a K nyelv nem irányítható, hiszen nem tudjuk garantálni, hogy az αγ eseménysorozat után ne a szakasz ne generálja a δ eseményt. Ugyanakkor láttuk azt is, hogy K-nak léteznek irányítható résznyelvei: C(K) = {{ǫ}, {α}, {αβ}}, így 4.1. tétel értelmében K ↑ = {ǫ} ∪ {α} ∪ {αβ} = αβ. Látható, hogy αβ megakadályozza a δ esemény generálását, ugyanakkor azzal, hogy megengedi a kezdeti állapotban az α eseményt, a lehető legnagyobb mozgásteret biztosírja a rendszer számára. Irányítható résznyelv, de nem a legnagyobb az {ǫ} nyelv, mely csupán az üres szimbólumot tartalmazza. A {ǫ} nyelvet akkor generálja a zárt kör, ha a kezdeti állapotban nem engedjük meg az α esemény bekövetkeztét. Természetesen ekkor a rendszer nem mozdul ki a kezdeti állapotából, így bár semmi olyat nem tesz, amit a specifikáció tiltana, hasznos munkát sem végez. Mint az előbbi példából is látható, meg kell különböztetnünk az {ǫ} és ∅ nyelveket. Az előbbi az üres szimbólumot tartalmazza, tehát jelentése az, hogy a szakasz ugyan nem generál eseményeket, azonban ez megfelel a specifikáció előírásainak. A második, ∅ viszont az üres nyelv, amely egyetlen szimbólumot, így ǫ-t sem tartalmazza, azaz nincs olyan szimbólumsorozat, amelyet generálhatna a szakasz, magyarán kezdeti állapotából nem tudjuk megakadályozni a specifikációval ellentétes működést. A legnagyobb irányítható résznyelv megkeresése a fenti módszerrel nehézkes, különösen, ha mind a rendszer, mind pedig a specifikáció a generátorával adott. Márpedig a gyakorlatban az utóbbi leírásmód a használatos, azaz először meg kéne határozni a szakasz és a specifikáció által generált nyelvet, azok összes (akár végtelen sok) résznyelvét, és ezekre egyenként ellenőrizni kéne az irányíthatóságot. Kézenfekvő hát az igény egy olyan algoritmusra, ami képes a specifikáció legnagyobb irányítható résznyelvét megkeresni a generátorok felhasználásával, ráadásul optimálisan, lehetőleg az eddig használt műveletek segítségével. Ilyen a Kumar-féle algoritmus, amit a következőkben részletesen is ismertetünk. A Kumar-féle algoritmus Adott a szakasz P = (X, Σ, ρP , x0 , Xm ) és a specifikáció S = (Y, Σ, ρS , y0 , Ym ) generátora. L(S) legnagyobb irányítható résznyelvének generátorát a következő lépésekben kaphatjuk meg:


43

1. Készítsük el a P k S = {Z, Σ, ρ, z0 , Zm } generátort és vezessük be a következő jelöléseket: • z = (x, y) ∈ Z, x ∈ X, y ∈ Y a szinkron szorzatban a szakasz x és a specifikáció y együttes állapotát jelentő állapot • Σu (P )(x) = {σ ∈ Σu |∃ρP (x, σ)}, azaz Σu (P )(x) azon nem irányítható események halmaza, amikhez tartozó átmenet definiált x ∈ P -ből • Σu (P k S)(z) = {σ ∈ Σu |∃ρ(z, σ)} azon nem irányítható események halmaza, amikhez tartozó átmenet definiált z ∈ Z-ből 2. Képezzük a szinkron szorzat elemeinek Zb0 részhalmazát: Zb0 = {z = (x, y) ∈ Z|Σu (P )(x) * Σu (P k S)(z)} A Zb0 halmaz tehát a szinkron szorzat azon z = (x, y) állapotait tartalmazza, amelyekből nem definiált átmenet minden olyan nem irányítható eseményhez, amelyhez tartozó átmenet definiált P -ben a z állapothoz tartozó x ∈ P állapotból kiindulva. 3. Képezzük P k S állapotainak Zb∗ részhalmazát: Zb∗ = {z ∈ Z \ Zb0 |∃u ∈ Σ∗u : ρ(z, u) ∈ Zb0 }, azaz Z azon állapotainak halmazát, melyek nem elemei Zb0 -nak, viszont vezet belőlük Zb0 -ba csak nem irányítható eseményekhez tartozó átmenetekből álló élsorozat sorozat. 4. A legnagyobb irányítható résznyelv generátora ↑C E ↑C = (Z ↑C , Σ, ρ↑C , z0↑C , Zm ),

ahol • Z ↑C = Z \ (Zb0 ∪ Zb∗ ) ρ(z, σ) ∀z ∈ Z ↑C , σ ∈ Σ|ρ(z, σ) ∈ Z ↑C ↑C • ρ = nem definiált egyébként z0 ha z0 ∈ / Zb0 ∪ Zb∗ • z0↑C = ∅ egyébként ↑C • Zm = Zm \ (Zb0 ∪ Zb∗ )

Tekintsük át az algoritmus lépéseit! Először a P k S szinkron szorzat generátorát készítjük el, ami abc-jük azonossága miatt valójában nyelveik metszetét generálja, magyarán egy esemény csak akkor engedélyezett, ha egy adott állapotban mind a specifikációban mind a szakaszban engedélyezett. Emiatt P k S azt a működést írja le, amit mind a szakasz, mind a specifikáció megenged, azaz a szakasz specifikáció által megengedett működése. Ez lenne az ideális zárt körű működés, ha a felügyeleti irányítással a nem irányítható események bekövetkeztét is le tudnánk tiltani, amire azonban sajnos nem vagyunk képesek.

44


Az algoritmus második lépésében definiált Zb0 halmaz azon eseményeket tartalmazza, amelyekben egy adott nem irányítható eseményt nem engedünk meg P k S-ben, ugyanakkor a szakasz megfelelő állapotában generálhatja azt. Világos, hogy egy ilyen állapotba jutva a szakasz az adott eseményt generálva megsértené a specifikációt (szemléletesen elhagyná generátorát), és mivel nem irányítható eseményről van szó, annak bekövetkeztét nem tudjuk letiltani. Ha tehát szeretnénk, hogy a zárt kör megfeleljen a specifikációnak, akkor a Zb0 -ba tartozó "rossz" (bad, innen a b index) állapotokba nem engedhetjük eljutni a rendszert. A harmadik lépésben az állapotok Zb∗ halmazát definiáljuk, ami azon állapotok halmaza, melyekből csak és kizárólag nem irányítható események mentén eljuthatunk Zb0 egyik elemébe. Ez azt jelenti, hogy csak úgy tudjuk megakadályozni, hogy a rendszer egy "rossz" állapotba jusson, ha azt is megakadályozzuk, hogy Zb∗ -ba jusson. A legnagyobb irányítható résznyelvet akkor kapjuk, ha a szakaszt a specifikáción belülre szorítjuk, azon belül viszont a lehető legkevesebb megkötéssel élünk. Láttuk, hogy P k S tartalmazza a szakasz specifikációt betartó működésének generátorát, ugyanakkor láttuk azt is, hogy a Zb0 illetve Zb∗ halmazokba tartozó állapotokból nem tudjuk garantálni, hogy a rendszer csupán a specifikációnak megfelelő eseménysorozatokat fog generálni. Éppen ezért kézenfekvő, hogy a legnagyobb irányítható résznyelv generátorát úgy kapjuk meg, hogy P k S generátorából töröljük a Zb0 illetve Zb∗ halmazokba tartozó állapotokat. Világos, hogy ezen állapotokat törölve a hozzájuk tartozó (belőlük induló illetve feléjük mutató) átmeneteket is törölnünk kell, a legnagyobb irányítható résznyelv jelölt állapotai pedig a törlésnek áldozatul nem esett jelölt állapotok lesznek. A kezdeti állapot azonos P k S kezdeti állapotával, amennyiben z0 nem tartozik a törölt állapotok közé. Amennyiben z0 ∈ Zb0 ∪ Zb∗ , akkor az azt jelenti, hogy a rendszer kezdeti állapotából indulva is generálhat olyan, csak nem irányítható eseményeket tartalmazó eseménysorozatokat, melyek nem felelnek meg a specifikációnak. Ilyenkor Z ↑C a ∅ üres nyelvet generálja, azaz az adott specifikációra nézve a szakasz nem irányítható. A gyakorlatban érdemes az algoritmus eredményeképpen adódó Z ↑C automatának az elérhető részét venni, hiszen az ugyanazt a nyelvet generálja, mint Z ↑C , kevesebb állapota miatt azonban könnyebben kezelhető. Tovább egyszerűsítve szintén érdemes az L(Z ↑C ) nyelvet generáló és a Lm (Z ↑C ) nyelvet jelölő minimális generátort elkészíteni. 4.6. példa. Tekintsünk két masinát (4.13. ábra), amik egymástól függetlenül működnek, és a második masinát az első szolgálja ki munkadarabokkal. Az egyszerűség kedvéért feltételezzük, hogy az első masina soha nem romlik el, kettejük között pedig egy végtelen kapacitású, feltöltött buffer van. A rendszerrel szembeni elvárásunk az, hogy amennyiben a második masina elromlik, az első nem helyezhet munkadarabot a bufferbe. Az ennek megfelelő specifikáció a 4.14. ábrán látható. Első dolgunk a teljes rendszer, tehát a két masina szinkron szorzatának összeállítása, aminek generátora a szokásos jelölésekkel az 4.15. ábrán látható.


45

W1

W2 α2 λ2

|

α1

|

|

β1 β2 |

I1

I2

µ2

D2

4.13. ábra. A 4.6 példában használt két masina generátora

β1 λ2 0

µ2

1

|

4.14. ábra. A 4.6 példában használt specifikáció generátora

46


µ2 |

α2 | I1 I2

λ2

I 1 W2

I 1 D2

β2 α1 α2 | W1 I2

α1

β1

W1 W2

|

β1

|

|

α1

λ2

β1

W1 D 2

β2 |

µ2

4.15. ábra. A szakasz generátora

Ezután el kell készítenünk a szakasz és a specifikáció P k S szinkron szorzatát, ami a 4.16. ábrán látható. A szinkron szorzat generátorában két olyan "sziget" is szerepel, melyek állapotai nem elérhetők, így a Kumar-féle algoritmust implementálva érdemes ezeket a továbbiakban nem figyelembe venni. Ezek az állapotok ugyanis csak a detektálhatóság tulajdonságába szólnak bele, amit a gyakorlatban ritkán használunk, szemben a blokkolással. A szinkron szorzat definíciója szerint azon eseményhez tartozó átmenetek, amik nem szerepelnek a specifikációban, mindenképpen szerepelni fognak a P k S generátorának megfelelő helyein. Ez azt jelenti, hogy azon eseményeket, amiket a specifikáció minden állapotában megengedünk (azaz minden hurkon szerepelnek) akár el is hagyhatjuk a specifikáció generátorából! Vigyázzunk azonban, ha egy esemény akár egyszer is szerepel a specifikáció generátorában, az azt jelenti, hogy azon állapotokban, ahonnan nem indul ki hozzá tartozó átmenet (ilyen példánkban a β1 esemény a q1 állapotban) az adott esemény a specifikáció szerint nem generálható! Az algoritmus következő lépése a Zb0 halmaz összeállítása, ami azon állapotokat tartalmazza, amelyekhez tartozó szakasz-állapotból indul ki olyan nem irányítható esemény, ami szinkron szorzat adott állapotából nem. Mivel a specifikációban nem szerepel (azaz minden állapotában engedélyezett) a nem irányítható események közül β2 , így ezt nem kell vizsgálnunk. A szakasz és a szinkron szorzat állapotait összehasonlítva látható, hogy a β1 eseményhez tartozó átmenet nem definiált a szinkron szorzat W1 I2 1, W1 W2 1 és W1 D2 1 állapotaiból, miközben a szakasz W1 I2 , W1 W2 és W1 D2 állapotaiból mind definiált β1 -hez tartozó átmenet. Hasonlóan az I1 W2 1 és W1 W2 1 állapotokból nem indul ki λ2 -höz tar-


47

α2 | I1 I2 0

I1 W2 0

I 1 D2 0

β2 α1

β1

β1

µ2

|

|

α1

β1

|

|

α1

α2 | W1 I2 0

W1 W2 0

λ2

W 1 D2 0

β2 α2 | I1 I2 1

I1 W2 1

λ2

I 1 D2 1

β2 α1

W1 W2 1

W 1 D2 1

|

α1

|

|

α1

α2 | W1 I2 1 β2 µ2 |

4.16. ábra. A P k S szinkron szorzat generátora

48


α2 | I1 I2 0

I1 W2 0

I 1 D2 0

β2 α1

β1

β1

µ2

|

|

α1

β1

|

|

α1

α2 | W1 I2 0

W1 W2 0

λ2

W 1 D2 0

β2 α2 | I1 I2 1

I1 W2 1

λ2

I 1 D2 1

β2 α1

W1 W2 1

W 1 D2 1

|

α1

|

|

α1

α2 | W1 I2 1 β2 µ2 |

4.17. ábra. A Zb0 és Zb∗ halmazok tozó átmenet, míg a szakasz generátorainak I1 W2 és W1 W2 állapotaiból igen. A Zb0 halmaz állapotai ezek szerint: {I1 W2 1, W1 I2 1, W1 W2 1, W1 D2 1}, melyeket a 4.17. ábrán szürke színnel jelöltünk. Ezen állapotokban ugyanis a szakasz képes generálni a β1 illetve λ2 eseményeket, amiket viszont a specifikáció tilt. Mivel ezek az események nem irányíthatók, bekövetkeztükre nincs hatásunk, így generálásukat csak úgy előzhetjük meg, ha nem hagyjuk, hogy a szakasz a Zb0 állapotaiba jusson. Azon állapotokból, amelyekből nem tudjuk megakadályozni, hogy eljussunk Zb0 -ba, egy csak nem irányítható eseményeket tartalmazó út vezet Zb0 valamely elemébe. Ezért a Zb∗ halmaz elemeit úgy érdemes meghatározni, hogy megnézzük, Zb0 állapotai mely nem irányítható eseményhez tartozó átmenet végállapotai, és ezek kezdőállapotait hozzáadjuk Zb∗ -hoz. Majd a Zb∗ -ba vezető, nem irányítható eseményekhez tartozó átmenetek kezdőállapotait vesszük be Zb∗ -ba, és ezt így folytatjuk, amíg új állapotot tudunk hozzáadni. Példánkban Zb0 állapotai közül


49

α2 | I1 I2 0

I1 W2 0

I 1 D2 0

β2 α1

β1

β1

µ2

|

|

|

α1

W1 I2 0

I1 I2 1

λ2

W 1 D2 0

I 1 D2 1

4.18. ábra. A legnagyobb irányítható résznyelv Z ↑C generátora

az I1 W2 1 és W1 W2 1 állapotokba nem vezet nem irányítható él, W1 I2 1-be pedig ugyan igen, de az átmenet kezdőállapota, W1 W2 1 már eleme Zb0 -nak, így nem lehet eleme Zb∗ -nak. Ezzel szemben a W1 D2 1 állapotba vezet egy λ2 eseményhez tartozó átmenet W1 W2 0-ból, így az utóbbi állapotot hozzáadjuk Zb∗ -hoz. Ezután Zb∗ állapotait kell megvizsgálnunk az előzőekhez hasonlóan. Mivel W1 W2 0-ba egyetlen nem irányítható eseményhez tartozó átmenet sem vezet, ezért nem találtunk újabb elemet, azaz befejezhetjük a vizsgálatot: Zb∗ = {W1 W2 0}, amit a 4.17. ábrán átlós rácsozás jelöl. A legnagyobb irányítható résznyelv generátorát, Z ↑C -t úgy kapjuk, hogy P k S-ből kitöröljük a Zb0 -ba illetve Zb∗ -ba tartozó állapotokat, illetve a megfelelő átmeneteket. Az eredmény a 4.18. ábrán, míg E ↑C generátorának elérhető alrendszere a 4.19. ábrán látható. Vegyük észre, hogy a legnagyobb irányítható résznyelv csak akkor engedi meg az első masina elindítását, ha a második áll. Bár a specifikáció ezt közvetlenül nem mondta ki, mégis csak így teljesíthető. Megtiltottuk ugyanis azt, hogy a lerobbant masina bufferébe munkadarabot tegyünk, azonban a lerobbanás bármikor bekövetkezhet a második masina elindítása után. Ha tehát biztosak akarunk lenni abban, hogy nem teszünk munkadarabot a lerobbant masina bufferébe, akkor nem indíthatjuk el az első masinát, amíg a második dolgozik, és viszont. Tehát

50


µ2 |

β2 I1 I2 0

I1 W2 0 | α2

α1

λ2

I 1 D2 1

|

β1

W1 I2 0

4.19. ábra. Z ↑C elérhető alrendszere a megkívánt működést csak úgy tudjuk biztosítani, hogy a két masinát egymást váltva működtetjük, ami ugyan a hatékonyság tekintetében nem előnyös, ellenben biztosan teljesíti az előírt specifikációt.

4.4. A felügyeleti irányítás meghatározása Az előzőekben áttekintettük, hogyan működik a zárt kör, hogyan adjuk meg a vele szemben támasztott elvárásokat, illetve hogy a lehetséges zárt körű működések közül melyik az, amelyik a specifikációnak leginkább megfelel. Eszerint meg kell akadályoznunk az összes olyan eseménysorozat bekövetkeztét, amely nem szerepel a specifikációban, a specifikációban szereplők közül viszont a lehető legtöbbet meg kell engednünk a zárt körbeli működés során. Ez nem más, mint a specifikáció szakaszhoz képesti legnagyobb irányítható résznyelve, amiből kiindulva az alkalmazandó felügyeleti irányítást meghatározhatjuk. A felügyeleti irányítás meghatározásának feladata a következő. Legyen a szakaszunk generátora G, az általa generált nyelv pedig L(G), a specifikációnk nyelve E. A specifikáció szakaszhoz képesti legnagyobb résznyelvét jelölje E ↑C . Keressük azt a V felügyeleti irányítást, amelynek használatátával L(V /G) = E ↑C ! 4.11. definíció. Az L(G) ⊆ Σ∗ nyelvet generáló G rendszert az E ⊆ Σ′∗ ⊆ Σ∗ nyelvvel megadott specifikáció legnagyobb irányítható résznyelvére szorító fel-

4.4. A FELÜGYELETI IRÁNYÍTÁS MEGHATÁROZÁSA

51

ügyeleti irányítás az a V : L(G) → Γ, ahol az irányítási mintákat a következők szerint definiáljuk: V (s) = {Σu ∪ σ ∈ Σc : sσ ∈ E ↑C } Vegyük észre, hogy a fenti definícióban a teljes L(G)-hez rendeltük hozzá az irányítási mintákat. Azonban zárt körben csak az E ↑C eseménysorozatai következhetnek be, így egyszerűsíthetjük a felügyeleti irányítást, ha azt V : L(E ↑C ) → Γ-ra szorítjuk az irányítási mintákat a következők szerint definiálva: V (s) = {Σ′u ∪ σ ′ ∈ Σ′c : sσ ′ ∈ E ↑C } Látható, hogy így egyrészt kisebb halmazon, L(G) helyett E ↑C ⊆ L(G)-n kell definiálnunk az irányítási mintákat, másrészt azokban is csupán a legnagyobb irányítható résznyelv eseményei szerepelnek. Természetesen ez utóbbi megoldás nem nyújt semmiféle fogódzót arra ez esetre, amikor a zárt kör valamilyen nem modellezett jelenség, például műszaki hiba miatt a megfelelő irányítás mellett is kilép a legnagyobb irányítható résznyelv által megfogalmazott keretből. Ilyenkor a definícióban szereplő eredeti irányítás még képes tovább dolgozni, letiltani az összes irányítható esemény bekövetkeztét, hiszen azt a szakasz által fizikailag generálható összes eseménysorozatra, a teljes L(G) nyelvre definiáltuk.

52


5. fejezet

Felügyeleti irányítások megvalósítása Az előzőekben láttuk, hogyan állíthatjuk elő a zárt kör modelljét a legnagyobb irányítható résznyelv segítségével, illetve hogy hogyan definiálhatjuk ennek alapján a felügyeleti irányításhoz tartozó irányítási mintákat. Eddig a felügyeleti irányítások elmélete volt segítségünkre, annak eszközrendszerével dolgoztunk. Amikor azonban a konkrét szabályozó megvalósítására kerül sor, tipikusan valamilyen programozható irányítóberendezésen, az elmélet több fonákja is kiütközik. A legnyilvánvalóbb eltérés, hogy az elmélet szerint minden eseményt a szakasz generál, így azon irányítható eseményeket is, melyek a beavatkozó szervekhez tartoznak. A gyakorlatban viszont ezen események generálásáért a szabályozó felelős, például egy motor fordulatszám-alapjelét az irányítást végző PLC adja meg. Hasonló problémát jelenthet az irányítási mintáknak a szakasz vagy a zárt kör nyelvéhez rendelése is, lévén egy nyelv akár végtelen számú szimbólumsorozatot is tartalmazhaz. A következőkben ezen implementációs kérdések közül tekintünk át néhányat, kilépve a felügyeleti irányítások elméletének szigorú rendszeréből.

5.1. Determinisztikus irányítás A 3.1. fejezetben már szó esett a véges állapotú automaták determinisztikus tulajdonságáról, azaz arról, hogy determinisztikus automatákban egy adott állapotból kiindulva egy adott szimbólumhoz tartozó átmenet csak egyetlen más állapotba vezethet, azaz amennyiben ∃ρ(q, σ), akkor |ρ(q, σ)| = 1, ∀σ ∈ Σ. Amennyiben mind a szakasz, mind a specifikáció determinisztikus (ami valódi rendszerek és jól megtervezett specifikációk esetében teljesül), akkor a legnagyobb irányítható résznyelv generátora is determinisztikus lesz. Azonban irányítások tervezésekor az automaták determinizmusa nem elegendő. Az ugyanis megengedi, hogy egy állapotból több irányítható eseményhez 53

54

5. FEJEZET. FELÜGYELETI IRÁNYÍTÁSOK MEGVALÓSÍTÁSA

tartozó él is kiinduljon, ami problémát jelent a szabályozó implementálása során. Ekkor ugyanis konfliktushelyzet jelentkezik, egyszerre két beavatkozó jel kiadására utasítanánk a szabályozónkat, amiknek hatására ráadásul egészen más trajektóriát is követhet a rendszer. Világos, hogy ez a helyzet nem megfelelő, a szabályozóval egyszerre csupán egyetlen beavatkozó jelet adhatunk ki, így a megfelelő tervezéshez a zárt kör olyan modelljére van szükség, ahol egy adott állapotból csak egyetlen irányítható eseményhez tartozó átmenet indul ki. Az ilyen rendszereket nevezzük irányítás-determinisztikusnak. 5.1. definíció. A G = (Q, Σ, ρ, q0 , Qm ) véges állapotú automatával leírt diszkrét eseményű rendszer irányítás-determinisztikus, ha X |ρ(q, σ)| ≤ 1, ∀q ∈ Q σ∈Σc

A fenti kifejezésben az első Σ az összegzést, míg az alsó indexben lévő Σc az irányítható események halmazát jelöli. 5.1. példa. Az 5.1. ábrán látható automata-részlet által mutatott rendszer nem irányítás-determinisztikus, hiszen a q1 állapotból két irányítható eseményhez, αhoz és β-hoz tartozó átmenet is kiindul. Vegyük észre, hogy a q1 állapotból még kiindul egy harmadik átmenet is, de mivel az ehhez tartozó γ esemény nem irányítható, ezért ez az irányítás-determinizmus szempontjából nem releváns. Amennyiben a specifikációnk irányítás-determinisztikus, akkor nyilván annak legnagyobb irányítható résznyelve is az lesz. Azonban ha specifikációnkat több rész-specifikációból állítjuk össze, ezek diszjunkt eseményhalmazai miatt

q2 α µ

δ

q3

|

|

β

q1

q4 | β

γ

λ

| α

q5

δ

q6

q7 ν

5.1. ábra. Nem irányítás-determinisztikus rendszer generátorának részlete

5.2. AZ IRÁNYÍTHATÓ ESEMÉNYEK FORRÁSA

55

könnyen olyan specifikációhoz juthatunk, ami nem irányítás-determinisztikus. Ilyenkor ezt a tulajdonságot vagy a specifikációban, vagy pedig már a legnagyobb irányítható résznyelven kell érvényre juttatnunk. Sajnos erre automatikus eljárás nem létezik, hiszen számos oka lehet annak, ha egyszerre két irányítható esemény is megengedett, ráadásul egyenkét engedélyezve mindkettő helyes működéshez vezet. Ilyenkor a determinizmus biztosítása, annak eldöntése, hogy mikor melyik irányítható eseményt engedélyezzük, már az irányítástechnikus feladata, aki a teljes rendszerről alkotott ismeretei alapján oldja fel a nemdeterminisztikus helyzetet. Természetesen adódik egy egyszerű módszer az irányítás-determinizmus biztosítására. A legnagyobb irányítható résznyelv generátorának meghatározása után az eseményeket prioritással látjuk el, és azokban az állapotokban, amelyek ellentmondanak az irányítás-determinizmusnak, az engedélyezett események közül a legmagasabb prioritásút továbbra is engedélyezzük, a többit viszont letiltjuk. A prioritás megfelelő hozzárendelése azonban nem triviális feladat, hiszen lehetséges, hogy egyes esetekben más-más beavatkozást részesítenénk előnyben. Fontos azonban leszögeznünk, hogy a rendszer mindenképpen a specifikációknak megfelelően fog működni, hiszen az irányítás-determinizmust a legnagyobb irányítható résznyelv szűkítésével biztosítjuk! Másfelől a nem irányítás-determinisztikus rendszerekben a konfliktus leggyakrabban az 5.1. ábrán bemutatott módon jelentkezik, azaz a két trajektória csupán abban különbözik, hogy az irányítható események milyen sorrendben követik egymást, azaz a beavatkozásokat milyen sorrendben végezzük el. A prioritás alkalmazása azonban nem mindig jó megoldás, ugyanis felléphet az a probléma, hogy a magasabb prioritású esemény kiéhezteti az alacsonyabb prioritásút. Ez a helyzet a 4.6. példa esetében is, ahol például az 1. masina indítási eseményének magasabb prioritást adva az a helyzet áll elő, hogy a 2. masina soha nem fog elindulni. Ezekben az esetekben egy újabb, irányításdeterminizmust biztosító specifikáció előírásának eszközével élhetünk.

5.2. Az irányítható események forrása Mint ahogyan már többször is szóba került, a felügyeleti irányítások elmélete szerint minden eseményt a szakasz generál. Igaz ez a környezeti és a felhasználói eredetű eseményekre is, mint amilyen például egy gomb megnyomása. A szakaszra tehát nem önmagában érdemes gondolnunk, hanem a környezetének azon részével együtt, amelyik hatással lehet rá. Ebbe a körbe alkalomadtán a felhasználó is beletartozhat, ami első ránézésre furcsának tűnhet, de ebből a nézőpontból könnyebben átlátható, hogy az eseményeket valóban a szakasz maga generálja. Az irányítható események esetében az elmélet feltevése még távolabb áll az általános, gyakorlatban alkalmazott szemléletmódtól. Mint ahogyan a 4.1. ábrán is láttuk, a felügyeleti irányítás gyakorlatilag az irányítható események számára csupán engedélyező jeleket adhat, tehát például a szakasz egy motort folyamatosan "el akar indítani" illetve "le akar állítani", és a szabályozó csupán

56


ennek a két eseménynek a bekövetkeztét képes megakadályozni illetve engedélyezni. A gyakorlatban természetesen a szabályozó nem csak engedélyezi, hanem vezérli is a beavatkozó szerveket, illetve egyéb, irányítható eseményeken keresztül elérhető elemeket. Érdemes tehát az implementáció szempontjából az események halmazát újra felosztani, mégpedig a szabályozó szempontjából nézve bemeneti és kimeneti eseményekre. 5.2. definíció. Egy diszkrét eseményű rendszer eseményeinek Σ halmazát feloszthatjuk a bemeneti események Λ és a kimeneti események Ω halmazára, amennyiben teljesülnek a következők: • Λ∩Ω=∅ • Λ∪Ω=Σ A felosztás során tehát megköveteljük, hogy a be- és kimeneti események halmaza diszjunkt legyen, kettejük uniója pedig adja vissza a rendszer teljes Σ eseményhalmazát. Ennél több megkötést nem teszünk. Egyszerűbb esetekben bemeneti eseménynek a nem irányítható, míg kimeneti eseménynek az irányítható eseményeket tekintjük. Azonban ez általánosságban nem jó megoldás, hiszen például egy elosztott rendszerben egy irányítható esemény lehet az egyik szabályozó bemeneti eseménye, míg egy másiknak ugyanaz az esemény kimeneti eseménye.

5.3. A zárt kör modelljének transzformációja Mint láthattuk, a felügyeleti irányítást a zárt kör modellje alapján definiáljuk, és az irányítható eseményeket beavatkozásként kezeljük, amit tehát a szabályozónknak kell kiadnia. Amennyiben a zárt körben az irányítható eseményeket (vagy azok egy részhalmazát) a szabályozó kimeneteként, míg a nem irányítható eseményeket a szabályozó bemeneteként kezeljük, egy Mealy-automatát kapunk: 5.3. definíció. A szabályozót leírhatjuk a C = (Q, Λ, Ω, δ, φ, q0 ) Mealy-automatával, ahol • Q a szabályozó automatájának állapothalmaza • Λ a szabályozó bemeneti abc-je • Ω a szabályozó kimeneti abc-je • δ : Q × Λ → Q az állapotátmeneti függvény • φ : Q × Λ → Ω a kimeneti függvény • q0 a kezdeti állapot

5.3. A ZÁRT KÖR MODELLJÉNEK TRANSZFORMÁCIÓJA

57

Amennyiben a szabályozót a legnagyobb irányítható résznyelv alapján és az 5.2. definíció szerint meghatározott be- és kimeneti események alapján állítjuk össze, a szabályozó automatája a következők szerint viszonyul a legnagyobb irányítható résznyelv generátorához. 5.4. definíció. Tekintsük a G = (Q, Σ, ρ, q0 , QM ) véges állapotú automatát és annak eseményeinek a Λ bemeneti és Ω kimeneti eseményekre történő felosztását, ahol Λ ∩ Ω = ∅ és Λ ∪ Ω = Σ. A G által leírt működést zárt körben biztosító szabályozót leíró Mealy-automata C = (Q, Λ, Ω, δ, φ, q0 ), ahol az állapotok halmaza és a kezdeti állapot megfeleltehető a G automatáéval, a Λ és Ω halmazok a ki- és bemeneti felosztásnak, az állapotátmeneti és kimeneti függvényeket pedig a következők szerint definiáljuk: δ(q, λ) δ(q, ω) φ(q, ω)

= = =

ρ(q, λ), ∀q ∈ Q, λ ∈ Λ : ∃ρ(q, λ) ρ(q, ω), ∀q ∈ Q, ω ∈ Ω : ∃ρ(q, ω) ρ(q, ω), ∀q ∈ Q, ω ∈ Ω : ∃ρ(q, ω)

5.2. példa. Tekintsük az 5.2a. ábrán látható véges állapotú automatával megadott zárt kört és az események triviális felosztását ki- és bemeneti eseményekre, azaz legyen Λ = {α, δ, µ, ψ} és Ω = {β, γ}. A szabályozó Mealy-automatájának állapottere megfelel a zárt rendszer generátoráénak, kezdeti állapotuk is közös. Az állapotátmeneteket illetve a kimeneti eseményeket a 5.4. definíció szerint a következőképpen kapjuk meg. A generátor q0 állapotából egy bemeneti eseményhez, α-hoz tartozó átmenet vezet a q1 állapotba, így a Mealy-automatánk állapotátmeneti függvénye δ(q0 , α) = q1 , kimeneti függvénye pedig itt nem értelmezett. A generátor q1 állapotából q2 -be egy kimeneti eseményhez, β-hoz tartozó él vezet, így δ(q1 , ǫ) = q2 és φ(q1 , ǫ) = β. A további átmeneteket hasonló módon definiálva az 5.2b ábrán látható Mealy-automatát kapjuk. Az ábra átmenetein mind a bemeneti, mind a kimeneti események szerepelnek egy / jellel elválasztva. Természetesen kimeneti esemény csak akkor szerepel egy élen, ha az él kiinduló állapota és bemeneti eseménye által megadott párhoz definiált a kimeneti függvény. Amikor egy adott felügyeleti irányítást implementálunk, fontos, hogy azt a lehető legkevesebb állapottal és állapotátmenettel tegyük. A példán is látható, hogy az ǫ bemeneti szimbólumhoz tartozó átmenetek, illetve a kimeneti szimbólumhoz nem rendelt átmenetek megléte rejt magában egyszerűsítési potenciált. Rögtön adódik az ötlet, hogy amikor egy bemeneti eseményt egy kimeneti esemény követ, akkor a bemeneti eseményt követően azonnal generáljuk a kimeneti eseményt, és közvetlenül a kimeneti esemény célállapotába lépjünk, a köztes állapotot pedig töröljük a rendszerből. Példánkban ilyen a q1 állapot. Azonban vigyáznunk kell, ez csak akkor lehetséges, amikor a bemeneti eseményhez tartozó átmenet célállapotából (ami azonos a kimeneti eseményhez tartozó átmenet kiinduló állapotával) csak és kizárólag az adott kimeneti eseményhez tartozó átmenet indul ki! Amennyiben más (irányítás-determinisztikus rendszert feltételezve) bemeneti eseményhez tartozó átmenet is kiindul az adott állapotból

58


ψ

q0

α

q1

β |

µ

q2

q3

δ µ

|γ

q4

(a)

ψ

q0

α

q1

ǫ/β

µ

q2

q3

δ µ

q4

ǫ/γ

(b)

5.2. ábra. A zárt kört leíró véges állapotú automata (a) és a szabályozó Mealyautomatája (b)

5.3. A ZÁRT KÖR MODELLJÉNEK TRANSZFORMÁCIÓJA

59

(példánkban q4 ), akkor ezt nem tehetjük meg, ugyanis a beavatkozást mindig megelőzi a beérkező események kiindulása. Formálisan a következő algoritmussal élhetünk: 1. Tekintsük a rendszerünk C = (Q, Λ, Ω, δ, φ, q0 ) Mealy-automatáját. 2. Keressünk egy olyan q ∗ ∈ Q állapotot, amelyere (a) ∃δ(q ∗ , ǫ) (b) ∄δ(q ∗ , λ), ∀Λ \ ǫ (c) ∃λ ∈ Λ : ∃φ(q ∗ , λ) Amennyiben nem találtunk ilyen állapotot, akkor álljunk meg. 3. Hozzuk létre a C ′ Mealy-automatát a következő módon: • Q′ = Q \ q ∗ • Λ′ = Λ • Ω′ = Ω • δ ′ (q ′ , λ′ ) = ′

′

′

• φ (q , λ ) =

δ(q ∗ , ǫ) δ(q ′ , λ′ )

φ′ (q ∗ , λ) φ′ (q ′ , λ′ )

∀q ′ ∈ Q′ , λ′ ∈ Λ : δ(q ′ , λ′ ) = q ∗ egyébként ∀q ′ ∈ Q′ , λ′ ∈ Λ : δ(q ′ , λ′ ) = q ∗ egyébként

4. Legyen C = C ′ és ugrás a 2. pontra A fenti egyszerűsítéssel jócskán csökkenthetjük az implementálandó automata méretét, így erőforrásokat (mind processzoridőt, mind pedig memóriát) takaríthatunk meg. Szélsőséges esetben még az is előfordulhat, hogy egy kategóriával kisebb teljesítményű, így olcsóbb eszköz is elegendő a szabályozó implementálására. 5.3. példa. Tekintsük az 5.2. példában kiadódó Mealy-automatát, és próbáljuk meg egyszerűsíteni! Látható, hogy a q1 állapot megfelel a feltételeinknek, hiszen egyetlen, kimeneti eseményhez tartozó él vezet ki belőle. Így hát a q1 állapotot törölhetjük, az állapotátmeneti és kimeneti függvényekben pedig az alábbi módosításokat kell elvégeznünk: δ(q0 , α) δ(q3 , ψ) φ(q0 , α) φ(q3 , ψ)

= = = =

q2 q2 β β

További, a feltételeknek megfelelő állapotot nem találunk, mivel a q4 állapotból a γ kimeneti eseményen túl a µ bemeneti eseményhez tartozó átmenet is kiindul. Így további egyszerűsítéssel nem élhetünk, az eredményként adódó Mealyautomata az 5.3. ábrán látható.

60


ψ/β q0

α/β

µ

q2

q3

δ µ q4

ǫ/γ

5.3. ábra. Egyszerűsítés után adódó Mealy-automata

5.4. A felügyeleti irányítás implementálása A szabályozót az előzőekben ismertetett módon meghatározott és egyszerűsített C = (Q, Λ, Ω, δ, φ, q0 ) Mealy-automatára alapozva implementálhatjuk. A felügyeleti irányítás feladata az, hogy a rendszer működését a rendszer által generált bemeneti és a saját maga által kiadott kimeneti eseményeken keresztül kövesse, illetve hogy ez utóbbiakat a megfelelő állapotokban generálja. A szabályozó algoritmusa tehát valamilyen módon egy állapotgépet kell, hogy megvalósítson, amelynek állapotregisztere elegendően nagy méretű ahhoz, hogy a Q állapothalmaz minden állapotához egyedi értéket rendeljen. A szabályozó algoritmusa folyamatosan figyeli a bemeneti eseményeket, és a δ állapotátmeneti függvénynek megfelelően beállítja a φ kimeneti függvény által meghatározott beavatkozó jelet, majd pedig frissíti az állapotregisztert. Az algoritmus az alábbi pszeudo-kóddal írható le. q:=0; while() lambda:=check_input_events(); if lambda!=0 omega:=phi(q,lambda); if omega!=0 output(omega); end q:=delta(q,lambda); end end Az algoritmus pontos implementálása, az állapotgép megvalósításának módja nagyban függ a választott hardver lehetőségeitől. A szabályozót PLC-n megva-

5.4. A FELÜGYELETI IRÁNYÍTÁS IMPLEMENTÁLÁSA

61

lósítva például az algoritmus ciklikusan fut, minden egyes ciklusban ellenőrizve a bemeneti portokat, hogy vajon érkezett-e újabb esemény. Ekkor el kell döntenünk azt is, hogy ha két lekérdezés között egynél több esemény érkezett, akkor azokat milyen sorrendben vegyük figyelembe. Amennyiben az irányítást egy mikrokontrollerre bízzuk, akkor élhetünk a megszakítás nyújtotta lehetőségekkel, és az állapot valamint a kimenetek frissítéséért felelős rutint csak akkor hívjuk meg, ha érkezett bemeneti esemény. A felhasznált hardvereszköz szintén hatással van arra, hogy milyen programozási nyelven kell megvalósítanunk az algoritmust. Ez lehet valamilyen magas szintű nyelv (pl. C, Java), alacsony szintű nyelv (assembly, utasításlista), vagy valamilyen grafikus PLC-programozási nyelv (létradiagram, SFC, Grafcet), esetleg Simulink–Stateflow környezetben StateCharts. Természetesen minden nyelvnek megvannak a maga sajátosságai, azonban egy állapotgép megvalósítása mindegyikük esetében rutinfeladatnak számít.

Diszkrét eseményű rendszerek felügyeleti irányításának alapjai

Recommend Documents