České vysoké učení technické v Praze Fakulta jaderná a fyzikálně inženýrská

BAKALÁŘSKÁ PRÁCE

Kamil Ondrák

Praha – 2010

České vysoké učení technické v Praze Fakulta jaderná a fyzikálně inženýrská

Katedra matematiky

Decentralizované řízení dopravní signalizace: optimalizace zelené vlny

BAKALÁŘSKÁ PRÁCE

Vypracoval: Kamil Ondrák
Vedoucí práce: Ing. Václav Šmídl, Ph.D.
Konzultant: Dr. Ing. Jan Přikryl, Ph.D.
Rok: 2010

Zadání práce s podpisem děkana.

Prohlášení Prohlašuji, že jsem předloženou práci vypracoval samostatně a že jsem uvedl veškerou použitou literaturu.

Praha, 2. července 2010 Kamil Ondrák Poděkování (…) Děkuji Mgr. Markovi Hryciowovi za pozorné pročtení a podnětné připomínky. (…)

Kamil Ondrák Název práce: Decentralizované řízení dopravní signalizace: optimalizace zelené vlny

Autor:  Kamil Ondrák
Obor:  Inženýrská informatika
Druh práce:  Bakalářská práce

Vedoucí práce: Ing. Václav Šmídl, Ph.D.

ÚTIA AV ČR

Konzultant: Dr. Ing. Jan Přikryl, Ph.D.

ÚTIA AV ČR

Abstrakt: Popis práce

Klíčová slova:

Title: Decentralized control of traffic lights: green wave optimization

Author:  Kamil Ondrák

Abstract: Popis práce anglicky

Key words:

Obsah

Úvod 1

1 Popis situace 3 1.1 ”Křižovatka“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Oblast Zličína . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Simulátor Aimsun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Agentní systémy 7 2.1 Inteligentní agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Algoritmus řízení 10 3.1 Návrh algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Použité knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1 IT++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.2 BDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.3 Libconfig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 Struktura programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Obsah  VII

4 Výsledky simulací 17 Závěr 18 Seznam použitých zdrojů 19 Přílohy 20

Úvod

Na mnoha místech silničních komunikací dnes nastává problém s jejich ucpáváním příliš silným automobilovým provozem, přičemž nejčastějším úzkým hrdlem bývají křižovatky. Teoreticky nejjednodušší se jeví přestavba dotčených míst. To je však často také řešení nejnákladnější a v některých místech to ani není možné, například z důvodu nedostatku prostoru. Další možností je omezení počtu vozidel přijíždějících do předmětné oblasti. To sice zlepší průjezdnost v kritickém místě, ale provoz se tím přesouvá jinam, kde tak může vzniknout podobný problém. Jako zajímavá možnost se jeví co nejlepší řízení provozu pomocí světelných signalizačních zařízení.

V současné době je většina vytížených křižovatek řízena pomocí poměrně sofistikovaných signálních plánů, které se i dokáží přizpůsobovat aktuální dopravní situaci. Tyto plány bývají vypočítány různými dlouhodobě vyvíjenými programy na základě změřených dat o hustotě dopravy v daném místě. Pro izolované křižovatky se chovají velmi dobře, nevýhodou toho způsobu řízení však bývá právě izolovanost – každá křižovatka má informace jen o svém nejužším okolí a chybí jakákoli koordinace mezi sousedícími křižovatkami.

Na některých místech se používá jistá forma centralizovaného řízení. Ústředna sbírá údaje z určité oblasti a na základě těchto informací vysílá pokyny do řadičů příslušných křižovatek. Tento postup vede k velmi dobrým výsledkům, ale většímu rozšíření brání malá univerzálnost algoritmů používaných v ústřednách.

Relativně novým přístup je decentralizovaném řízení dopravní signalizace. Ta funguje na principu multiagentních systémů. Každá křižovatka se pak stává jedním agentem, který jedná s ostatními agenty za účelem vytvoření společné strategie řízení vedoucí ke zlepšení průjezdnosti.

Cílem této práce je seznámit se s tímto decentralizovaným způsobem řízení, navrh- \underline{Úvod 2}

nout komunikační strategii, která by pomocí nastavení tak zvaných offsetů mohla vézt ke zlepšení průjezdnosti oblastí, toto řešení implementovat na počítači a prozkoumat jeho důsledky v simulátoru dopravy Aimsun. Toto vše je prováděno na modelu skutečné oblasti, konkrétně Řevnické ulice v Praze – Zličíně. Jako referenční stav pak slouží řízení dopravní signalizace signálními plány expertně navrženými metodou Monte Carlo.

Na začátku práce je představen způsob řízení světelných křižovatek, používané detektory a popis signálních plánů. Následuje popis modelované oblasti a po té sekce o simulátoru Aimsun. Ta představuje některé možnosti, které Aimsun nabízí, ukazuje jaká vstupní data do simulace vstupují a jaké zní vystupují. Součástí je také popis rozhraní Getram Extensions, které se používá pro komunikaci mezi simulátorem a externími programy.

Následující kapitola pak představuje úvod to teorie multiagentních systému ... (atd, podle toho, co v kapitole bude)

Ve třetí kapitole je popsána nejprve teoreticky navrhovaná strategie komunikace mezi agenty a pak i představena konkrétní implementace. Ta spočívá v rozšíření stávajícího řešení pro simulace dopravy vyvíjené v Ústavu teorie informace a automatizace (ÚTIA) Akademie věd ČR.

V poslední kapitole se nacházejí výsledky simulací navrženého algoritmu a srovnání stavu v oblasti před a po jeho aplikaci.

Kapitola 1

Popis situace

1.1 ”Křižovatka“

Křižovatka řízená světelným signalizačním zařízením se skládá z několika prvků. Vedle samotných semaforů je v její blízkosti připojen řadič, který se stará o ovládání signalizačních prvků. K řadiči pak může být připojeno několik detektorů, poskytujících mu informace a aktuální dopravní situaci.

Detektory se dělí dělí do tří kategorií podle jejich umístění. (i) výzvové, (ii) prodlužovací a (iii) strategické. (i) jsou umístěné na stop čáře, (ii) cca 30 metrů před ní a (iii) na vzdálenějších místech, typicky alespoň 100 metrů před stop čárou. Ne vždy musí být na všech ramenech křižovatky instalovány všechny typy detektorů.

Technicky je nejčastějším řešením detektoru indukční smyčka umístěná ve vozovce. Ta pomocí změn magnetického pole ve své okolí zaznamenává projíždějící vozidla. V případě umístění dvou smyček blízko sebe lze získat i podrobnější informace o rychlosti, druhu vozidla a další informace. Další možností jsou infračervené detektory. Jejich hlavní součástí je kamera, snímající sledovaný prostor v infračervené oblasti. Ve výsledném obrazu pak poměrně snadno rozezná automobily i chodce jakožto zdroje tepelného záření.

Dále existují například video detektory založené na kamerách snímající v oblasti viditelného světla (videodetektory), mikrovlnné nebo ultrazvukové detektory. Tyto však nejsou v současné době v simulované oblasti instalovány.

Detektory umístěné na Zličíně poskytují dva údaje. Prvním je počet vozidel, které přes detektor projely a druhým čas, po který se v detekované oblasti vyskytovalo nějaké vozidlo. Bohužel, tato data nejsou naprosto přesná.

(!chyby detektorů!)

Řízení křižovatky probíhá pomocí signálních plánů uložených v řadiči nebo dle pokynů z ústředny. Signální plány mohou být pevné nebo rámcové. Signální plán se skládá z několika fází, které mají buď pevně nebo rámcově dány časy začátků a délku. Fáze jsou složené ze signálních skupin. Signální skupina pak značí skupinu světelných signalizačních zařízení, která rozsvěcuje současně zelenou. Signální plány mají pevnou a jednotnou délku jednoho cyklu. V předmětné oblasti je to konkrétně 80 sekund. Posledním důležitým pojmem je offset. Ten říká o kolik sekund je začátek jednoho cyklu signálního plánu posunut oproti jistému počátečnímu času t_{0}.

(možná obrázek sem)

V případě pevných signálních plánů se přepínání fází řídí předem danou tabulkou, která určuje kdy která fáze začíná a jak dlouho má trvat. Navíc může být u fází uložena možnost je prodloužit v případě, že údaje z detektorů oznamují další přijíždějící vozidla v daném směru.

Rámcové signální plány dovolují řadiči větší volnost při zařazování fází. Na základě aktuálních naměřených údajů může řadič volit nejvhodnější fázi z několika momentálně přípustných, může nastat i situace, že některá fáze nebude v rámci cyklu zařazena vůbec.

1.2 Oblast Zličína

Ověření možnosti decentralizovaného řízení dopravní signalizace je v této práci ověřeno na modelu skutečné oblasti: ulice Řevnická v Praze – Zličíně. V ulici se nachází pět světelných křižovatek situovaných v jedné linii. Pro zjednodušení jsou simulovány jen dvě severní křižovatky: 5.495 a 5.601. První jmenovaná je trojramenná křižovatka ulic Řevnická a Na Radosti, druhá je potom čtyřramenná a je tvořena napojením autobusového terminálu na jedné a obchodního centra Metropole Zličín na druhé straně na Řevnickou.

1.3 Simulátor Aimsun

K simulaci dopravní situace se používá softwarový balík GETRAM/AIMSUN od společnosti TSS (Transport Simulation Systems) ve verzi 4.2.16. Jádrem celého nástroje je program Aimsun, který slouží k samotné simulaci.

Aimsun (Advanced Interactive Microscopic Simulator for Urban and Non-Urban Networks, [6]) je mikrosimulátorem dopravy^{1}. To znamená, že modeluje polohu jednotlivých vozidel spojitě během celé doby simulace. Každé vozidlo se řídí určitým modelem chování. Lze nastavit různé styly předjíždění, prudkost brzdění a rozjezdů, ale třeba i ochotu čekat. Je možné simulovat různé druhy vozidel, od osobních přes nákladní auta až po autobusy a hromadnou dopravu vůbec. Vedle vozidel Aimsun samozřejmě nabízí simulaci většiny objektů, které se vyskytují v dopravních sítích: světelných signalizační zařízení, detektorů, atd.

Vstup pro simulátor se skládá ze scénáře a parametrů simulace. Scénář obsahuje popis dopravní sítě, údaje o dopravní poptávce, ”traffic control plans“ a plány veřejné dopravy. Popis dopravní sítě představuje geometrickou reprezentaci zkoumané oblasti, tedy rozměry a tvar jednotlivých silničních pruhů a křižovatek, umístění dopravní signalizace, detektorů, zastávek hromadné dopravy a podobně. Dopravní poptávka může být zadaná ve dvou formách. Buď ve formě intenzity dopravy na vstupech, poměrů odbočení na křižovatkách a počátečního stavu sítě, nebo pomocí takzvané O-D matice, která zachycuje počet uskutečněných cest mezi dvojicemi vstupních a výstupních bodů. ”Traffic control plans“ zahrnují popisy fází a jejich trvání pro řízené křižovatky, přednosti v jízdě pro křižovatky neřízené. Konečně plány veřejné dopravy se skládají z popisů tras, zastávek a jízdních řádů linek hromadné dopravy v simulované oblasti. Parametry simulace představují pevné hodnoty popisující experiment (jako doba simulace) a proměnné hodnoty určené pro kalibraci modelu.

Výstup za simulace jsou textové soubory s číselnými údaji, které se zpracovávají například v MATLABu pomocí toolboxVGS.

Aimsun má aplikační rozhraní (API) jménem Getram Extensions, které umožňuje komunikaci s ostatními programy. Aimsun pomocí tohoto rozhraní poskytuje v re-

1Současná verze Aimsun 6 dovoluje již mikro, meso i makrosimulaci

1.3. Simulátor Aimsun  6

álném čase data ze simulace a naopak přijímá data pro její ovlivňování. (... popis rozhraní přijde sem... )

Agentní systémy

2.1 Inteligentní agent

Pokud mluvíme o agentních systémech, je nutné předem si vyjasnit základní pojem agent. Bohužel neexistuje přesná obecně přijímaná definice. Pro účely této práce můžeme použít například definici, kterou používá Michael Wooldrige v [7, kap. 1]: ”Agent je počítačový program, který je umístěn v nějakém prostředí a který je schopen autonomního jednání v tomto prostředí za účelem dosažení určených cílů.“ Autonomií se zde myslí schopnost samostatného jednání bez zásahu člověka nebo jiných programů. Tato definice se zatím vyhýbá pojmu inteligentní, tomu se budeme věnovat později.

Agent z definice má tedy určitý druh čidel, kterými může získat některé údaje o svém okolí, omezený seznam akcí, které může provádět a jistý algoritmus, který určuje jakou z akcí (pokud vůbec nějakou) v aktuálním čase provést.

Komplexnost rozhodovacího procesu závisí mimo jiné i na prostředí. To můžeme klasifikovat z mnoha pohledů. Zda lze či nelze získat úplné informace o jeho současném stavu, jestli jde o deterministické nebo nedeterministické prostředí, tedy jestli stejná akce povede vždy ke stejnému konečnému stavu. Dále je možné rozlišit mezi statickým a dynamickým prostředí. Ve statickém prostředí jsou veškeré změny stavu dílem pouze agenta, zatímco dynamické okolí se mění ať agent jedná nebo ne. Podobných rozdělení existuje mnoho, ale toto pro představu postačí. Nejlépe řiditelné je samozřejmě prostředí, které je plně popsatelné, deterministické a statické, bohužel řízení dopravy je případem přesně opačným.

Naprosto typickým příkladem jednoduchého agenta umístěného v prostředí je termostat ovládající topení za účelem udržení stále teploty v místnosti. Tento agent má jedno čidlo, kterým určuje jestli je teplota nižší než nastavená požadovaná, a dvě možné akce: zapnutí a vypnutí vytápění. Rozhodovací proces se pak skládá ze dvou pravidel:

nízká teplota⟶ zapnout vytápění
správná teplota⟶ vypnout vytápění

Takto postavený program se dá považovat za agenta, ale pravděpodobně jen málokdo by ho označil za agenta inteligentního. Problém je už samotná definice inteligence. Proto se omezíme na to, že inteligentní agent je takový, který dokáže flexibilně reagovat. Flexibilita jsou myšleny tři body:

reaktivita – inteligentní agent vnímá své okolí a dle takto získaných údajů reaguje na jeho změny tak, aby splnil své nastavené cíle;

proaktivita – inteligentní agent je schopný předvídat chování systému a na základě těchto předpovědí aktivně jednat tak, aby splnil své nastavené cíle;

sociální schopnosti – inteligentní agenti na sebe mohou vzájemně působit tak, aby splnili své nastavené cíle.

Požadavky na reaktivitu a proaktivitu jdou proti sobě. Je třeba najít vyvážený poměr mezi oběma. Extrémně reaktivní agent totiž na základě neustále přijímaných podmětů stále koná nějakou akci. Ovšem tímto způsobem se může dostat do stavu, kdy podměty způsobují zaměření agenta na různé cíle jdoucí proti sobě a tím pádem ani jeden z cílů nemůže být nikdy uskutečněn. Na druhou stranu příliš proaktivní agent se zaměří na jeden cíl a kvůli ignoruje, že počáteční podmínky, které ho k plnění cíle dovedly už nejsou platné. Najít proto tu správnou míru je obtížná úloha.

Mezi sociální schopnosti nepatří jen rutinní výměna informací, kterou dnešní počítače provádějí prakticky neustále, ale především schopnost vyjednávat a spolupracovat při plnění společných nebo individuálních cílů. Mezi běžné akce tak patří navrhování změn spolu s přínosem, které by tato změna přinesla, jejich zvažování a následné přijetí, odmítnutí či protinávrh vedoucí ke kompromisu.

(...pokračování...)

Algoritmus řízení

3.1 Návrh algoritmu

Úkolem v této práci bylo navrhnout algoritmus vyjednávání mezi jednotlivými křižovatkami tak, aby koordinovanou změnou svých offsetů vytvořili zelenou vlnu a tedy aby projelo co nejvíce vozidel bez zbytečného zastavování.

Důležitým prvkem návrhu je funkce která, ohodnotí nastavení offsetu a umožní tak tedy porovnat různé jeho hodnoty a vybrat tu možná nejlepší. Jako míra kvality byl odhad počtu aut, která projedou křižovatkou bez zastavení.

Pro výpočet hodnocení (v programu nazývaném rating) je třeba pro každý jízdní pruh na vjezdu do křižovatky znát délku fronty a očekávané časy příjezdů vozidel od sousední křižovatky. Délka fronty se v současné době získává ze simulátoru, příjezdy pak přímo od souseda. Ten je počítá podle vztahu

t_{z} = t_{zz} + \frac{d}{v_{P}} + offset  (3.1)

a

t_{k} = t_{z} + t_{dz} ,  (3.2)

kde t_{z} je čas začátku příjezdu aut a t_{k} čas konce. Dále pak t_{zz} je čas začátku svícení zelené, d vzdálenost ke křižovatce, která žádá o časy příjezdů, v_{P} průměrná rychlost vozidel, offset nastavený offset a t_{dz} délka svícení zelné. K těmto dvoum hodnotám se ještě přidává předpokládaný počet aut. Jeho odhad je získán z hustoty provozu v minulém cyklu. Křižovatka zasílající odhady takovýchto trojic údajů předává několik – podle toho, kolik fází rozsvěcí zelenou ve směru připouštějícím jízdu k sousedovi, který o odhady žádal.

Po shromáždění všech předpokladů od sousedů může agent přistoupit k samotnému výpočtu. Ten spočívá v tom, že agent spočítá příspěvky všech jízdních pruhů, u kterých má nějaké informace o časech příjezdů. Pro každý pruh se pak nejprve spočítá délka fronty v čase, kdy se na jeho odjezdu rozsvítí zelená. To znamená:

Q_{V} = Q + ∑_{i=1}^{k} t_{i}n_{i}  (3.3)

kde Q_{V} je délka tak zvané virtuální fronty, zde jde o délku fronty při rozsvícení zelené, Q je odhadovaná délka fronty, t_{i} je délka i-tého intervalu, ve kterém přijíždějí vozidla, n_{i} je počet těchto vozidel a k je počet intervalů s příjezdy před rozsvícením zelené.

Dále se pak spočítá délka virtuální fronty v okamžiku, kdy zelená přejde zpět na červenou. K tomu je třeba rozdělit interval od prvního očekávaného příjezdu nebo rozsvícení zelené (podle toho, co nastane dříve) po zhasnutí zelené (tento interval označíme T) na posloupnost intervalů (T_{i})_{i=1}^{k}. T_{i} jsou intervaly typu ⟨a_{i}; b_{i}⟩, kde b_{i} = a_{i+1} ∀i ∈ {2, …, n − 1}, a_{1} a b_{k} jsou krajní body intervalu T a a_{i} jsou chronologicky řazené všechny významné body, tedy body, ve kterých se mění signalizovaný znak nebo ve kterých začíná či končí příjezd vozidel od souseda.

S pomocí tohoto dělení pak můžeme počítat

Q_{K} = Q_{V} + ∑_{i=1}^{k} u(T_{i}) ,  (3.4)

kde u(T_{i}) je funkce u : ⟨a; b⟩ → ℝ

u(T_{i}) = \begin{cases}n_{i} & pokud v intervaluT_{i} pouze přijíždějí vozidla \\ −|T_{i}| · c_{o} & pokud v intervaluT_{i} pouze odjíždějí vozidla \\ n_{i} − |T_{i}| · c_{o} & pokud v intervaluT_{i} přijíždějí i odjíždějí vozidla \end{cases} . (3.5)

Q_{K} značí konečnou délku fronty, Q_{V} je virtuální fronta z rovnice (3.3), k je počet intervalů ”s různými vjezdy a výjezdy“. |T_{i}| je délka intervalu T_{i}, n_{i} počet vozidel, která přijedou v intervalu T_{i} a c_{o} je empiricky zjištěná konstanta – počet vozidel, která za sekundu opustí křižovatku.

Definice funkce u(T_{i}) jak je zapsána vztahem (3.5) není úplná. Ještě je nutné doplnit omezení

|u(T_{i})| \begin{cases}≤ Q_{i} & pokud v intervaluT_{i} pouze odjíždějí vozidla \\ ≥ n_{i} & pokud v intervaluT_{i} přijíždějí i odjíždějí vozidla \end{cases} ,  (3.6)

kde Q_{i} je délka fronty na začátku intervalu T_{i}.

Tyto podmínky zarčují, že pokud z jízdního pruhu jen odjíždějí vozidla, nemůže jich odjet více než jich čeká na začátku ve frontě a že pokud vozidla zároveň přijíždějí a odjíždějí, projede jich bez zastavení maximálně tolik, kolik dorazí od souseda.

Pokud vyjde Q_{K} záporné, představuje (odhadovaný) počet aut, která mohou křižovatkou projet bez zastavení a tato hodnota se tedy odečte od hodnocení dané křižovatky (a tím se tedy hodnocení zvýší).

Při samotném vyjednávání pak mají agenti dvě role, jeden z nich je označen jako pasivní, zatímco druhý je v pozici aktivního. Pasivní agent má pevně nastavený offset a jen reaguje na pokyny aktivního. Pokyny jsou buď žádost o očekávané časy příjezdů nebo návrh na změnu offsetu. Na první z nich agent vždy odpovídá zasláním požadovaných údajů, u druhého pak zvažuje, jestli by změna v celkovém součtu přinesla zlepšení ratingu. Z tohoto popisu už pak vyplývá role aktivního agenta. Ten stejně pracuje se žádostmi o časy příjezdů, navíc ale aktivně mění svůj offset a pokouší se vyjednat změnu u sousedů.

Vyjednávací cyklus pak probíhá v několika krocích. Nejprve si všichni agenti vyžádají očekávané příjezdy vozidel na základě offsetů nastavených v minulém cyklu. S přihlédnutím k těmto očekáváním pak aktivní agenti spočítají rating svého nastavení offsetu a pokusí se zjistit, jestli by nějaká změna jejich offsetu nevedla k zlepšení hodnocení. Hledání nejlepšího offsetu probíhá ve třech krocích. Nejprve se porovná aktuální offset, offset zvýšený o 8 sekund a offset snížený o 8 sekund. Vybere se nejlepší ze tří možností a pokračuje se s ním stejným způsobem, jen uvažovaná změna je ± 4 sekundy. V posledním kroku je pak otestován posun o ± 2 sekundy.

Když aktivní agenti naleznou své nejlepší offsety, rozešle se všem agentům zpráva o nalezení stabilního stavu, která obsahuje nové hodnoty očekávaných příjezdů vozidel.

Nyní aktivní agenti vyzkouší, jestli by k dalšímu zlepšení nevedla změna offsetu u některého z jejich sousedů. Stejným způsobem jako při hledání vlastního nejlepšího offsetu zkusí odhadnout změnu ratingu při posunu sousedova offsetu o ± 4, 2 a 1 sekundu. Pokud má nejlepší hodnocení nenulová změna, zašle se sousedovi žádost o tuto změnu spolu se změnou ratingu, kterou by přinesla.

Každý pasivní agent poté sesbírá všechny návrhy a otestuje, který z nich má největší součet změny ratingu u něj samotného a změny u navrhovatele a ten potom přijme za vlastní. Pokud by všechny návrhy přinesly zápornou změnu, jsou zamítnuty a žádná změna nenastává. V každém případě jsou pak rozeslány informace o novém stabilním stavu a s nimi opět očekávané příjezdy.

Tímto každá křižovatka nalezne svůj konečný offset. Problém nastává při zaslání tohoto offsetu do řadiče křižovatky. Od toho není garantována okamžitá akce, způsob jakým žádaného offsetu dosáhne je jen v jeho režii a než se tak stane může trvat i několik cyklů. Z toho důvodu se vypočtený offset neposílá hned po nalezení, ale agent vždy v pěti cyklech napočítá optimální offset, z těchto pěti hodnot spočítá průměr a až ten se následně předá řadiči pro zpracování. Tím je také snížena reaktivnost agenta a zamezí se případným přehnaným reakcím na chvilkové změny poptávky, kterým stejně není možné se přizpůsobit.

3.2 Použité knihovny

Pro usnadnění práce a také z důvodu lepšího začlenění do současného řešení se v programu se používají tři volně dostupné knihovny: IT++, zjednodušující práci s vektory, maticemi a poli, BDM (Bayesian Decision Making), která obsahuje užitečné nástroje pro práci s popisy k vektorům a libconfig, sloužící především pro práci s konfiguračními soubory. První dvě knihovny jsou distribuovány pod GPL licencí, třetí pak pod licencí LGPL.

3.2.1 IT++

IT++ je knihovna pro C++, která obsahuje třídy a funkce pro provádění některých matematických operací, zpracování signálů a další. Pro účely této práce jsou zajímavé právě funkce matematické.

V knihovně jsou mj. zavedeny typy vec a ivec. První jmenovaný je vektor obsahující prvky typu double, tedy čísla s desetinou čárkou, druhý je pak složen z prvků int, tedy čísel celých. Práce s vektory je velmi intuitivní, navíc lze často používat syntaxi podobnou jako v programu MATLAB.

Vektor můžeme nadefinovat jedním z těchto způsobů:

vec my vector;
vec my vector( 1 0 ) ;

přičemž první ze způsobů pro vektor nealokuje paměť. To je pak nutné udělat funkcí setsize(). Následně je pak možné uložit do vektoru jednotlivé prvky a to například jedním z následujících příkazů.

vec a = ”0 0.7 5 9.3”;  // tedy a = [0 0.7 5 9 . 3 ]
i v e c b = ”0:5”;  // tedy b = [0 1 2 3 4 5]
vec c = ”3 : 2 . 5 : 1 3”;  // tedy c = [3 5.5 8 10.5 13]
i v e c d = ” 1 : 3 : 5 , 0 : 2 : 4”;  // tedy d = [1 3 5 0 2 4]
vec e(”1 . 2 , 3 . 4 , 5 . 6” ) ;  // tedy e = [ 1 . 2 3.4 5 . 6 ]

Navíc lze i-tému prvku vektoru a přistupovat pomocí a(i) nebo a[i].

Díky přetížení operátorů lze s vektory přímo provádět běžné matematické operace, jako jsou:

a+b  // součet vektorů
a+5  // p ř i č t e n í č í s l a 5 ke všem prvkům vektoru
a∗b  // s k a l á r n í součin vektorů
a∗9  // vynásobení všech prvků vektoru číslem 9

a tak podobně.

Práce s maticemi pak funguje podle obdobných pravidel.

(Array)

Obrázek 3.1: Vektor typu RV (vlevo) fungující jako popis k vektoru typu vec (vpravo). Každá položka z rv˙ vector má v levém sloupci své jméno (name) a v pravém velikost (size). Například podvektor c má tedy tvar [5 4]

3.2.2 BDM

Knihovna BDM (Bayesian Decision Making) se zabývá, jak název napovídá, bayesovským rozhodováním. Ovšem v této práci jsou z ní použity jen třídy UI, RV, datalink a logger.

Třída UI (User Info) slouží pro ukládání a čtení libovolných uživatelských dat. Zde se používá pro načtení konfigurace pro simulátor a pro jednotlivé agenty a dále jako formát pro ukládání a posílání zpráv mezi agenty.

Účelem třídy RV je poskytovat popisné informace k datovému vektoru. Proměnná typu RV se skládá z jedné nebo několika položek. Každá taková položka má svoje jméno (name) a délku – počet prvků, které tomuto jménu odpovídají. Součet délek všech takovýchto položek se potom musí rovnat délce vektoru, který je danou proměnnou typu RV popisován. Fungování je ilustrováno na obrázku 3.1.

Pro kopírování dat mezi vektory existuje třída datalink. Vytváří spojení mezi dvěma datovými vektory na základně shodně pojmenovaných prvků v k nim příslušných popisných vektorech. Po propojení vektoru s podvektorem pak funkce datalinku umožňují snadné kopírování dat oběma směry.

Na závěr Logger je třída určená pro ukládání dat z programu. Tvoří abstraktní vrstvu mezi programem a samotným zápisem dat. Při použití se jen na začátku nastaví v jaké formě chceme získat výsledné údaje (např. uložit do paměti, do souboru, do databáze, atd.) a dále třídu používáme bez ohledu na tuto volbu. Je tím zajištěna flexibilita pro případ, že se změní požadavky na výstupy z programu.

3.2.3 Libconfig

Konfigurační parametry pro simulaci se ukládají do souboru ve formátu, který zavádí knihovna libconfig. Jde o textový formát, který je stručnější a pro člověka lépe čitelný, než XML.

(...rozvést nebo zrušit...)

3.3 Struktura programu

Simulace je obsluhována z programu main loop.exe. Ten se stará o načtení konfigurace, spuštění simulátoru Aimsun a zajišťuje komunikačního prostředníka mezi jednotlivými agenty. Program se spouští s jedním parametrem, který představuje jméno konfiguračního souboru. Konfigurační soubor používá formát, který načítá knihovna libconfig.

Program funguje tak, že na začátku načte konfigurační soubor. Pokud konfigurační soubor není zadán, program skončí s chybou. Po načtení je spuštěn simulátor Aimsun s parametry zapsanými ve skupině system. Jde především o intenzitu provozu na vstupech do dopravní sítě a délku simulace.

Následně je dle konfigurace vytvořeno pole ukazatelů na agenty Ags. Při konstrukci jednotlivých agentů je volána jejich funkce from˙ setting() načítající konkrétní parametry každého agenta.

Poté se vytváří instance třídy logger a její provázání s agenty. V tu chvíli se pouští i funkce ds˙ register() umožňující aktualizaci datalinků.

(...)

Pak již následuje ústřední for cyklus. Na jeho začátku se zapíší údaje do logu. Poté jsou přečtena aktuální data ze simulátoru a předána agentům ke zpracování funkcí adapt(). Pokračuje se vyjednávacím cyklem.

Vyjednávací cyklus se zabývá obsluhou fronty zpráv. Nejprve frontu prohledá frontu zpráv a příslušným agentů předá jim určené zprávy zavoláním funkce recieve(). V případě, že nemožnosti doručit oznámí varování, ale pokračuje dál v práci. Nakonec všichni agenti mají možnost nějaké zprávy do fronty přidat – k tomuto účelu existuje funkce broadcast().

Kapitola 4 Výsledky simulací Závěr

19

Seznam použitých zdrojů

[1] Bazzan, A. L. C.: Opportunities for multiagent systems and multiagent reinforcement learning in traffic control. Auton Agent Multi-Agent Syst, 2009: s. 342–375.

[2] Pecherková, P.; Duník, J.; Flídr, M.: Robotics, Automation and Control, kapitola Modelling and Simultaneous Estimation of State and Parameters of Traffic System. InTech, Croatia, 2008, ISBN 978-953-7619-18-3, s. 319–336.

[3] Roozemond, D. A.: Using intelligent agents for pro-active, real-time urban intersection control. European Journal o Operational Research, 2001: s. 293–301.

[4] TSS: Getram v4.2 getting started - User’s manual. Říjen 2003.

[5] TSS: GETRAM Extensions VERSION 4.2 - User’s manual. Květen 2004.

[6] TSS: Getram v4.2 - User manual. Únor 2004.

[7] Weiss, G. (editor): Multiagent systems: a modern approach to distribuated artificial intelligence. MIT Press, 1999, ISBN 0-262-23203-0.

Přílohy

21