Vzorový konečný automat
Vytvořme automat, který bude ovládat semafory na následující křižovatce.
Schéma křižovatky
Tvorbu rozdělíme do několika fází, během kterých budeme automat zdokonalovat (a zesložiťovat):
- zjistíme, co je to "stav křižovatky",
- navrhneme "ruční pomůcku", která umožní světla semaforů pohodlně přepínat,
- doplníme časovač, který bude světla přepínat automaticky,
- semafory doplníme tlačítky pro chodce.
Stav křižovatky
Nejpřirozenějším chápáním stavu světelné křižovatky je popis, která světla svítí. Ze schématu vidíme, že křižovatka obsahuje osm tříbarevných semaforů (pro auta) a osm dvoubarevných semaforů (pro chodce). Celkem tak křižovatka obsahuje 8 × 3 + 8 × 2 = 40 světel, z nichž každé může být zapnuté nebo vypnuté; světla na křižovatce se tak mohou nacházet v jednom ze 240 stavů, tedy v jednom z více než bilionu stavů.
Celkem pochopitelně jsou některé stavy teoreticky možné, ale prakticky vyloučené; nemá například smysl, aby všechna světla svítila současně. Smysl budou mít zřejmě zejména tzv. "bezkonfliktní stavy", kdy auta a chodci mohou křižovatkou procházet, aniž by si vadili. Standardní křižovatka obsahuje čtyři takové bezkonfliktní stavy.
Bezkonfliktní stavy křižovatky S1, S2, S3, S4. Pro přehlednost jsou vyznačeny trasy, kudy se mohou pohybovat auta a chodci
Při přechodu mezi stavy musíme samozřejmě chvíli počkat - nelze do křižovatky pouštět auta, dokud jsou v konfliktních pruzích jiná auta. To zařídíme mezistavy, během nichž rozsvítíme na některých semaforech oranžovou - tehdy už do křižovatky nesmí vjíždět nová auta, a oranžovou necháme svítit tak dlouho, dokud se křižovatka nevyprázdní. Všimněme si, že například mezi stavy S1 a S2 se barva na některých semaforech změní z červené na zelenou či naopak, zatímco na jiných semeforech stále svítí stejná barva. Tam, kde se barva mění, rozsvítíme oranžovou, kde se barva nemění, necháme světla být. Nové stavy si nazveme S12, S23, S34, S41 a vložíme je mezi stávající. Křižovatka by pak měla přecházet postupně v cyklu S1, S12, S2, S23, S3, S34, S4, S41, S1, ...
Průběh křižovatky všemi stavy i s "oranžovými" mezistavy. Pro přehlednost je stav S1 na konci zopakován
Kromě standardní činnosti semaforů bychom měli uvažovat i činnost nestandardní - jsou-li semafory vypnuty (například když nejde elektřina), nachází se křižovatka rovněž v definovaném stavu, nazvěme jej SV. Chceme-li (například ráno) křižovatku "oživit", těžko můžeme přímo vstupit do některého ze stavů S1 až S8 - není rozumné najednou na některém ze semaforů pro auta rozsvítit červenou. Rozumnější bude na chvíli všem autům rozsvítít oranžovou (indikace "pozor, změna!") a všem chodcům červenou, aby na přechody nikdo nevcházel. Tento stav nazveme S0. Kromě toho víme, že při v noci je vhodné řidičům dát najevo, že semafory nejsou rozbité, ale křižovatka se nachází v neřízeném režimu. To se obvykle indikuje blikající oranžovou barvou, semafory pro chodce jsou vypnuté. Během blikání se tedy střídají stavy SV a stav podobný stavu S0; oproti němu má semafory pro chodce vypnuté. Označme si tento stav SV'.
Pomocné stavy SV (vypnuto), SV' (pro blikající oranžovou) a S0 (přechod mezi nefunkční a funkční signalizací)
"Řídicí panel" k ovládání křižovatky
Nyní můžeme snadno přistoupit ke konstrukci "řídicího panelu" ovládaného dopravním policistou. Bude mít k dispozici tlačítka odpovídající názvům stavů a po stisku tlačítka se rozsvítí ta světla, která stavu se stejným jménem odpovídají. Označme si napřed semafory:
Označení semaforů
Tlačítka pak budou reagovat samozřejmě následovně:
Vyznačení, která světla jsou rozsvícená po stisku tlačítka Sxx
Dopravní policista pak bude jen sledovat dopravu a podle potřeby mačkat taková tlačítka, která odpovídají zamýšlenému stavu semaforů. Pravda, blikání oranžové barvy je zařízeno poněkud hloupě (musel by opakovaně mačkat tlačítka SV a SV'), ale to vyřešíme později.
Poloautomatické řízení křižovatky
Musíme připustit, že i dopravní policista se může zmýlit. Ačkoliv jsme plánovali, že po stavu S1 má následovat stav S12, může policista omylem stisknut jiné tlačítko. Proto bude ideální, když tlačítko bude jen jedno (nazveme jej T) a jeho stiskem se křižovatka přepne do následujícího správného stavu. Nezapomeneme označit, v jakém stavu se má řízení nacházet po uvedení do činnosti!
Základní podoba řízení. Po stisku tlačítka T se světla přepnou do následující konfigurace
Budeme-li uvažovat i situace, kdy se má celá křižovatka zapínat či vypínat, budeme chtě nechtě muset přidat i tlačítko pro zapnutí, resp. vypnutí křižovatky (nazveme jej Z). Pracovně teď budeme předpokládat, že vypnutá křižovatka má všechna světla vypnutá a že při vypínání křižovatky všechna světla naráz zhasnou; blikání oranžového světla při "vypnuté křižovatce" zatím ponechme stranou.
Řízení se základní implementací zapnutí a vypnutí křižovatky. Z je tlačítko pro zapnutí/vypnutí světelné signalizace, tlačítkem T se v režimu řízení provozu křižovatka přesouvá mezi stavy S1 až S41
Automatické řízení křižovatky
Na jednu stranu je příjemné, když někdo (či něco) sleduje dopravu a stavy semaforů přepíná podle potřeby. Na druhou stranu je takové řízení drahé. Zkusme proto vymyslet zařízení, které bude simulovat mačkání tlačítka T, čili bude řídit přesun mezi stavy cyklu.
V nejjednodušším případě bychom vzali "černou krabičku", která jednou za čas (např. za 30 vteřin) vygeneruje puls a ten jako signál T odešle druhé "černé krabičce", která řídí světla semaforů. Zatímco o první krabičce zatím nic nevíme, o vnitřním uspořádání krabičky druhé jakési povědomí máme - celou dobu uvažujeme o její struktuře. Soustava, která nám vznikne, vypadá schematicky takto:
Propojení časovače s řízením světel
Pochopitelně je poměrně nešikovné, aby stav s oranžovou (přechodový) svítil stejně dlouho jako stav, kdy mají auta křižovatkou projíždět. Bylo by proto vhodné, kdyby časovač dokázal s vygenerováním pulsu počkat zadanou dobu; dobu čekání by mu mohla diktovat krabička řídící světla, protože ta ví, v jakém stavu se nachází. Pokud by krabička řídící světla měla navíc výstup "s přechodem do dalšího stavu počkej X vteřin", mohla by situace vypadat takto:
Propojení nastavitelného časovače s řízením světel
Samotný výběr doby čekání implementujeme snadno: v okamžiku, kdy automat řídící světla přechází do nějakého stavu, vygeneruje informaci, která nastaví dobu setrvání v tomto stavu. Nyní si snadno uvědomíme, že automat může generovat jak výstupy impulsní (v okamžiku přechodu mezi stavy), tak výstupy hladinové (po celou dobu, kdy je automat v nějakém stavu). Automatu s impulsními výstupy říkáme Mealyho, automatu s hladinovými výstupy říkáme Mooreův. Náš automat je tedy kombinací Moorova i Mealyho typu - ve stavech generuje hladinové výstupy řídící jednotlivá světla, v přechodu mezi stavy impulsní výstup nastavující časovač.
Automat s generováním nastavení časovače. Označení na hranách je dvojice vstup / výstup, čili např. "T / 3" znamená "jakmile přijde vstup T, přejdi do následujícího stavu a vygeneruj výstup '3' pro nastavení časovače"
Nyní můžeme jednoduchou úpravou zařídit i blikání oranžové při vypnutém řízení křižovatky. Pro přehlednost do schématu nebudeme kreslit reakci na tlačítko Z do všech stavů - definujme, že tlačítko Z stisknuté ve stavech S0 až S41 uvede automat do stavu SV'. Všimněme si, že reakce na vstup časovače T je definována všude. Tím máme u každého stavu jasně řečeno, co se má stát při příchodu jak vstupu T, tak vstupu Z. Nezapomeňme, že korektně definovaný konečný automat musí přechodovou funkci (tj. reakci na vstup) definovat všude.
Automat s indikací vypnutého řízení křižovatky blikající oranžovou
Implelemntace časovače
Podívejme se nyní na černou skříňku, která má generovat vstup T pro řízení světel. K její realizaci budeme nutně potřebovat zařízení, které periodicky generuje impulsy. Standardně se mu říká hodiny (clock), jeho výstup se často označuje zkratkou CLK. Do implementace hodin už se pouštět nebudeme; předpokládejme zkrátka, že máme další černou krabičku, která například jednou za vteřinu vygeneruje výstup označený CLK.
Síť automatů tedy bude vypadat následovně: do hodin samotných nevidíme, řízení světel máme zpracované poměrně detailně, zbývá jen vyřešit implementaci časovače.
Soustava řízená hodinami a tlačítkem Z pro zapnutí / vypnutí světelného řízení křižovatky
Automat pro řízení světel vyžaduje buď čekání třívteřinové, nebo třicetivteřinové. Časovač reagující na vstupy 3 a 30 může vypadat třeba následujícím způsobem, jeho rozšíření na automat reagující na vstupy 1, 2, ..., 29, 30 by bylo snadné.
Možná implementace časovače s nastavením délky čekání
Všimněme si, že automat generuje výstup výhradně při přechodu ze stavu 1 do stavu 0; číslo stavu tedy označuje, kolik musí automat dostat od hodin impulsů CLK, aby vygeneroval výstup T. Ve stavu 0 pak automat čeká tak dlouho, dokud nepřijde vstup 3, 30, případně jiný. Definujme, že reakci na nastavení časovače (tj. vstupy 3, 30 atd.) bude automat akceptovat jen ve stavu 0; v jiných stavech tento vstup se stavem automatu nic neudělá. Konečně si uvědomme, že musíme pečlivě zvolit startovací stav; ten určuje, jak dlouho po zapnutí systému vydrží řízení světel ve stavu SV (vše vypnuto).
Podotkněme, že uvedená struktura automatu je vhodná jen pro malý rozsah nastavení časovače (u nás maximálně 30 vteřin). Pokud bychom chtěli automat reagující na mnohem širší rozsah vstupů, asi bychom jej měli pojmout jinak; čtenář se o to může pokusit samostatně.
Reakce na tlačítka pro chodce
Současná podoba automatu pro řízení světel postrádá jakékoliv přizpůsobení momentální dopravní situaci. Zkusme například navrhnout reakci na tlačítko umístěné na semaforech pro chodce.
Pro začátek si stačí uvědomit, že zelená svítí chodcům pouze ve dvou stavech: S1 a S3.
Stavy, kdy mohou chodci přecházet
Je-li proto stisknuto tlačítko na chodeckém semaforu 9, 10, 11 nebo 12, je zřejmé, že chodec potřebuje křižovatku dostat do stavu S1. Je-li stisknuto tlačítko na chodeckém semaforu 13, 14, 15 nebo 16, touží po stavu S3. Všech osm tlačítek na semaforech proto můžeme popsat jen dvěma typy: tlačítko typu A slouží pro co nejrychlejší posun do stavu S1, tlačítko typu B pro co nejrychlejší posun do stavu S3.
Označení semaforů
K řešení reakce na tlačíto můžeme přistoupit nejméně dvěma způsoby. První způsob je příjemný pro chodce: křižovatka se okamžitě přepne do stavu s oranžovou pro auta a následně do žádaného stavu S1 nebo S3. Má to ovšem háček: chodec se smyslem pro akční humor by mohl opakovaným mačkáním jednoho tlačítka udržet semafor víceméně v jediném stavu a způsobit dopravní kolaps. Proto se musí nějak ošetřit, aby se průběžně objevovaly všechny stavy S1, S2, S3, S4, kdy auta mohou jezdit.
Druhý způsob řešení je snadný, "neprůstřelný", leč k chodcům ne tak vstřícný. Tlačítko na semaforu nezpůsobí okamžitý přechod do žádaného stavu; pouze způsobí rychlejší výměnu stavů a semafory se do požadovaného stavu dostanou rychleji. Po dosažení požadovaného stavu se vrátí normální rychlost cyklu.
U přizpůsobování doby čekání můžeme samozřejmě upravovat jen 30vteřinové setrvávání ve stavech S1, S2, S3 a S4; mezistavy s oranžovou barvou trvají tak dlouho, aby auta stačila odjet z křižovatky, což samozřejmě nezávisí na trpělivosti čekajícího chodce. Pozměněný automat může vypadat například takto: kromě základního cyklu se standardními dobami čekání bude obsahovat i dva "rychlejší" - jeden co nejrychleji dorazí do stavu S1 druhý do stavu S3. Na obrázku jsou vyznačeny purpurově (posun do S1) a azurově (posun do S3).
Kompletní řízení světel včetně reakce na chodecká tlačítka A a B
Všimněme si několika zajímavých detailů.
Z původních stavů S1 až S41 (černě) se tlačítkem A dostáváme do purpurového zrychleného cyklu; jakmile v něm dojdeme do kýženého stavu S1, vrátí se automat zpět do cyklu s normální rychlostí. To je zařízeno mimo jiné tím, že přechod ze stavu S41' do stavu S1 generuje výstup 30, čili ve stavu S1 se má automat zdržet standardních 30 vteřin. Obdobně funguje i přechod tlačítkem B do cyklu azurového, který co nejrychleji spěje ke stavu S3.
Pokud je na křižovatce více chodců, může se například stát, že ve zrychleném purpurovém (A) cyklu někdo stiskne tlačítko B. To znamená, že se potřebuje co nejrychleji dostat do stavu S3. Nachází-li se automat ve stavech S12', S2' nebo S23', nemusí se vlastně dělat nic - i purpurový cyklus do stavu S3 (resp. S3') dospěje, a to stejně rychle, jako by tam dospěl cyklus azurový. Pokud se ale automat nachází ve stavech S34', S4' nebo S41', něco udělat musíme, jinak by automat po skoku do stavu S1 opět běžel v základní rychlosti. Proto se automat přepne do stavů S34'', S4'' nebo S41''. Smysl purpurového zrychleného cyklu se tím nijak nenarušil - i azurový cyklus co nejrychleji dojde do stavu S1 (resp. S1''), ale poté rychle pokračuje do stavu S3, což jsme potřebovali zařídit.
Podotkněme, že ve schématu nejsou zakresleny všechny reakce na tlačítka, například ve stavu S1 chybí reakce na tlačítko A (vynucený rychlý přechod do S1). Definujme, že u nezakreslených reakcí nemá vstup na stav automatu vliv, tj. ve stavu S1 by měla být zakreslena šipka, která na stisk A převede automat opět do stavu S1. Připomeňme si, že již dříve jsme definovali, že ovládacím tlačítkem Z (zapni/vypni světelné řízení křižovatky) přecházíme do stavu SV', není-li ve schématu řečeno jinak.
A jak na implementaci konečného automatu? Podívejte se na vzorový program v druhém cvičení, jak implementovat standardní konečný automat. Pro inspiraci se dále podívejte na ukázkovou implementaci sítě konečných automatů, kde se několik automatů propojí mezi sebou.