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

BAKALÁŘSKÁ PRÁCE

Decentralizované řízení dopravní signalizace, nastavení délky cyklu

Praha, 2010 Autor: Jakub Novotný

Seznamte se se současným stavem řízení dopravní signalizace v Praze v oblasti Zličína, zvláště pak s rozvržením křižovatek, sensorů a signálními plány jednotlivých řadičů. Mikrosimulátor dopravy AIMSUN se běžně používá k srovnávání různých variant dopravního řešení. Seznamte se s tímto nástrojem a se způsobem předávání dat mezi ním a externími aplikacemi pomocí toolboxu vgsapi. Decentralizace řízení dopravy spočívá v zavedení komunikace mezi řadiči sousedících křižovatek, posílání zpráv o současném stavu a vyjednávání o společném postupu pro změny řídícího plánu. Teoretický přístup je též znám jako agentní přístup (multi-agent system). Navrhněte vhodnou komunikační strategii pro alespoň dvě křižovatky jejímž cílem je změna délky cyklů signalizačních plánů jednotlivých křižovatek za účelem zvýšení průjezdnosti oblastí. Tuto strategii implementujte jako rozšíření stávajícího řešení v C. Navrhněte vhodný komunikační protokol a pokud to bude výhodné použijte napojení na knihovnu rozhodovacích algoritmů BDM. Chování navrženého řízení srovnejte s expertně navrženým lokálním řešením pomocí Monte Carlo simulace a mikrosimulátoru AIMSUN. ii

Obsah

Seznam obrázků  v
Seznam tabulek  vii
1 Úvod  1
2 AIMSUN  3
2.1 Vstupní data pro AIMSUN . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Scénář . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Výstupní data AIMSUNu . . . . . . . . . . . . . . . . . . . . . . 4
2.1.3 VGS API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3.1 Reálná simulace . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3.2 Zpracování dat . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.4 Řadiče . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Multiagentní systémy  7
3.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2 Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.1 Dostupné vs. nedostupné . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.2 Deterministické vs. Nedetrministické . . . . . . . . . . . . . . . . 8
3.2.3 Statické vs. dynamické . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.4 Diskrétní vs. spojité . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Interakce agentů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3.1 Stavy prostředí a preference agentů . . . . . . . . . . . . . . . . . 8
3.3.2 Akce agentů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.4.1 Použití pro výběr délky cyklu . . . . . . . . . . . . . . . . . . . . 10
3.4.2 Globálně nějlepší řešení . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Popis implementace  13
4.1 Třída Lane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Třída LaneHandler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.1 Fronta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.2 Odhad fronty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2.3 Odhad čekací doby . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.4 Odhad parametru δ . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Třída agenta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Hlavní smyčka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4.1 Krok simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Literatura  21

Seznam obrázků

2.1 Grafický výstup ze simulátoru AIMSUN . . . . . . . . . . . . . . . . . . 4
2.2 Grafický výstup ze simulátoru AIMSUN - detail . . . . . . . . . . . . . . 5
4.1 Porovnání okamžité a filtrované délky frontydélka cyklu 80 s . . . . . . . 15
4.2 Porovnání okamžité a filtrované délky frontydélka cyklu 40-120 s . . . . . 15

vi

Seznam tabulek

vii viii

Kapitola 1

Úvod

Stav dopravní situace ve městě bezesporu ovlivňuje život každého z nás a pro jeho zlepšení, at’ už máme na mnysli výstavbu a zlepšování dopravních komunikací, nebo teoretický výzkum, jsou v dnešní době investovány nemalé finanční prostředky. Optimalizované řízení provozu je jedním z možností, jak odlehčit dopravě bez nutnosti zasahování do fyzického stavu silnic. V součané době se spoléhá hlavně na ruční nastavení parametrů křižovatky z centrály na základě dat z detektorů. Účelem této práce je prozkoumat možnosti řízení novým způsobem, a to decentralizovaným řízením multiagentím systémem. Pomocí programu v C++, kde jsou agenti ovládající křižovatky reprezentováni objektem, a komunikací přes knihovny AimsunDs s mikrosimulátorem dopravy Aimsun, budeme testovat možnosti výměny údajů, nalezení optimální strategie a změny dopravní situace na křižovatkách. Nejprve popíšeme mmikrosimulátor Aimsun, použité knihovny a používané parametry. Poté si přiblížíme některé důležité prvky z teorie multiagentních systémů. V druhé části práce popíšeme běh cel0ho programu, způsob implementace třídy agenta, zpracování údajů a volbu nejbhodnější strategie. Na závěr vyhodnotíme získané výsledky.

2 KAPITOLA 1. ÚVOD

AIMSUN

AIMSUN (Advanced Interactive Microscopic Simulator for Urban and Non-Urban Networks), je mikrosimulátor dopravy. Podstatou mikroskopické simulace (mikrosimulace) je modelování jízdy jednotlivých vozidel po dané komunikační síti, přičemž se zohledňují všechny parametry infrastruktury i dopravních prostředků, a to včetně chování řidiče.

2.1 Vstupní data pro AIMSUN

AIMSUN potřebuje pro svůj běh simulační scénář a množinu simulačních parametrů, které definují experiment. Scénář se skládá ze čtyř druhů dat: popis dopravní sítě, plány řízení dopravy, požadovaná dopravní data, a plány hromadné dopravy.

2.1.1 Scénář

Popis dopravní sítě zahrnuje geometrii sítě, popis křižovatek a rozmístění detektorů, které jsou rozmístěny podál dopravní sítě.

Plány řízení doprahy obsahují fáze a jejich délky pro křižovatky, které jsou řízeny dopravními světly. V každé fázi je definováno která signální skupina je průjezdná.

dopravní data se dají zadat dvěma způsoby:

• Pomocí objemů dopravy v určitých místech dopravní sítě, poměrů odbočení a počátečního stavu

• Pomocí matice, kde prvek na i-tém řádku a v j-sloupci udává kolik jízd se uskuteční z místa i do místa j

V prvním případě se vozidla rozmístí stochasticky podle pořžadovaných počtů a poměrů odbočení do dopravní sítě, v případě druhém je každému vozidlu přiřazena trasa z místa i do místa j.

Plány hromadné dopravy obsahují linky autobusů, jejich zastávky a jízdní řády.

2.1.2 Výstupní data AIMSUNu

AIMSUN poskytuje jak statistické výstupy v podobě hodnot doby průjezdu vozidla sítí, počtu zastavení, zpoždění a průměrné rychlosti, tak výstupy z detektorů - počet vozidel, rychlost a doba stání na detektoru, tak i plynule modelovaný grafický výstup.

Obrázek 2.1: Grafický výstup ze simulátoru AIMSUN

Obrázek 2.2: Grafický výstup ze simulátoru AIMSUN - detail

2.1.3 VGS API

VGS API je rozhraní napsané v jazyce, které rozšiřuje funkčnost mikrosimulátoru AIM-SUN. Jeho dva nejdůležitější úkoly jsou zjednodušení reálné simulace a statistické zpracování výstupních dat.

2.1.3.1 Reálná simulace

Aimsun umožňuje simulaci reálné dopravní sítě, kdy hodnoty hustoty dopravy odpovídají skutečně naměřeným hodnotám v reálném prostření simulované sítě. Běžně se používají ručně sečtené hodoty v intervalech jedné hodiny. Údaje se potom vkládají opět ručně do simulátoru.

Pro přesnější simulaci se používají data z detektorů v simulované oblasti. Objem dat je ale pro ruční vkládání neúnosně velký. Proto bylo vyvinuto VGS API, které umožňuje generování vozidel v průběhu simulace. VGS API se předá soubor s uloženými údaji z detektorů, to automaticky rozběhne AIMSUN, do kterého generuje v průběhu simulace vozidla podle reálných dat.

2.1.3.2 Zpracování dat

Druhým důležitám úkolem VGS API je zhromažd’ovat data potřebná pro vyhodnocení experimentu. Aimsun sice disponuje jednoduchým rozhraním pro vizualizaci dat a jejich export do textových souborů, není ale možné například porovnávat jednotlivé scénáře simulací. VGS API proto periodicky ukládá všechny klíčové ukazatele jak pro jednotlivé segmenty dopravní sítě, tak i pro celý simulovaný systém. Uživatel má po ukončení simulace k dispozici údaje o počtu zastavení vozidla, o jeho zpoždění, průměrné rychlosti, době jízdy a době stání, o dopravím toku a hustotě dopravy na jednotlivých segmentech.

Jedním z nejpodstatnějších údajů, které nám VGS API poskytuje, je délka fronty pro daný jízdní pruh. Tento údaj je prakticky nemožný určovat podle dat z detektorů, podstatně zkreslených chybami dvojího typu. Jednak vzniká chyba při přejezdu vozidla z pruhu do pruhu v oblasti detektorů, kdy jedno vozidlo zaznamenají oba detektory. Vozidlo by se potom přičetlo do obou front. K druhému případu chyby dochází, pokud je mezi dvěma vozidly tak malý rozestup, že je detektor považuje za jedno. V tomto případě naopak dochází k samovolnému vytrácení vozidel. Pokud bychom chtěli počítat délku fronty jako rozdíl počtů vozidel, která do křižovatky přijela a která ji opustila, docházelo by ke kumulaci této chyby v průběhu simulace. Hodnota délky fronty se ve VGS API získá vysčítáním vozidel s menší rychlostí než 3,6 km/h po segmentech jízdního pruhu.

2.1.4 Řadiče

K řízení signálních skupin křižovatky se používá tzv. řadič.

Multiagentní systémy

3.1 Úvod

Multiagentí systém je druh distribuované umělé inteligence. Tento systém se skládá z jednotlivých výpočetních prvků, tzv. agentů, které musí mít dvě základní schopnosti. Zaprvé musí být schopni autonomní akce rozhodnutí - zjistit jak nejlépe dosáhnout požadovaných cílů a zadruhé je to schopnost interakce s ostaními agenty. V druhém případě nejde jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí.

3.1.1 Historie

Multiagentí systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti se jim dostalo v polovině let devadesátých s rozvojem internetu.

3.1.2 Agent

Neexistuje obecně uznávaná definice agenta. Přikloníme se k definici použité v publikaci Wooldridge a Jennings(1995).

Definice 3.1 (Agent): Agent je počítačový systém umístěný do nějakého prostředí, který je schopen autonomní akce k přiblížení se navrženým cílům. ▶

Agent v naprosté většině případů nemá celkovou kontrolu nad prostředím. Prostředí může ovlivňovat jen částečně. Obecně, stejně jako v našem případě, je prostředí nedeterministické. Stejná akce provedená dvakrát za sebou nemusí vést ke stejnému výsledku.

3.2 Prostředí

Russel a Norvig navrhli klasifikaci prostředí podle jednotlivých parametrů následovně.

3.2.1 Dostupné vs. nedostupné

Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu.

3.2.2 Deterministické vs. Nedetrministické

Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt.

3.2.3 Statické vs. dynamické

Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty.

3.2.4 Diskrétní vs. spojité

V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí.

3.3 Interakce agentů

3.3.1 Stavy prostředí a preference agentů

Mějme pro jednoduchost 2 agenty. Označme si je i a j. Předpokládejme, že máme množinu

Ω = {ω_{1}, ω_{2}, ...}

obsahující všechny možné stavy prostředí, v kterém agenti operují. Aby byl agent schopen efektivně ovlivňovat prostření, musí být schopen ohodnotit, jak je pro něj daný stav příznivý. Hodnocení daného stavu agenta i a j formálně definujeme jako funkce

u_{i} : Ω → ℝ,

u_{j} : Ω → ℝ.

Čím je stav ω příznivější pro agenta i, tím je větší hodnota funkce u_{i}.

Definice 3.2 (Uspořádání na množině všech stavů): Mějme 2 stavy prostředí ω_{1}, ω_{2}. Řekněmě, že stav ω_{1} je preferován agentem i nad stavem ω_{2}, pokud platí u_{i}(ω_{1}) = u_{i}(ω_{2}). Značíme

ω_{1} ⪰_{i} ω_{2}.

Stav ω_{1} je silně preferován agentem i nad stavem ω_{2}, pokud platí u_{i}(ω_{1}) u_{i}(ω_{2}). Značíme

ω_{1} ≻_{i} ω_{2}

Relace ⪰_{i} je zřejmě uspořádání, protože má všechny potřebné vlastnosti. Reflexivitu:

∀ω ∈ Ω : ω ⪰_{i} ω

Transitivitu:

∀ω_{1}, ω_{2}, ω_{3} ∈ Ω : ω_{1} ⪰_{i} ω_{2} ∧ ω_{2} ⪰_{i} ω_{3} ⇒ ω_{1} ⪰_{i} ω_{3}

Porovnatelnost:

∀ω_{1}, ω_{2} ∈ Ω : ω_{1} ⪰_{i} ω_{2} ∨ ω_{2} ⪰_{i} ω_{1}

Relace ≻_{i} zjevně nesplňuje podmínky reflexivity.

3.3.2 Akce agentů

Nyní popíšeme, jak mají agenti možnost ovlivňovat prostředí. Opět předpokládejme existenci dvou agentů i a j. Obecně mají různí agenti různou oblast působnosti. Množiny

A = {a_{1}, a_{2}, ...}

znázorňují množiny všech akcí, které jsou agenti schopni provézt. Na tyto akce reaguje prostředí přechodem do nějakého stavu ω ∈ Ω. Formálně můžeme tento přechod zapsat jako funkci

τ : A × A → Ω.

3.4 Strategie

Popišme zde způsob, jak se agent rozhodne pro realizaci určité akce. Agent je nyní schopen ohodnotit, který stav prostředí je pro něj příznivější než jiný, neví však jak budou reagovat ostatní agenti, není schopen určit tudíž, i za předpokladu, že by systém byl deterministický, do jakého stavu systém přejde. K výběru optimální akce se používají prvky z teorie her. Zadefinujme nejprve v souladu s touto teorií základní pojmy.

Definice 3.3 (Dominance množiny): Mějme 2 podmnožiny Ω_{1}, Ω_{2} ⊂ Ω. Řekneme, že Ω_{1} je pro agenta i dominantní nad množinou Ω_{2}, pokud platí

∀ω ∈ Ω_{1}, ∀ω′ ∈ Ω_{2} : ω ⪰_{i} ω′.

Řekneme že Ω_{1} je pro agenta i silně dominantní nad množinou Ω_{2}, pokud platí

∀ω ∈ Ω_{1}, ∀ω′ ∈ Ω_{2} : ω ≻_{i} ω′.

Abychom používali terminologii teorie her, budeme nyní akce a_{i} ∈ A jednotlivých agentů nazývat strategiemi.

Definice 3.4 (Množina výsledků): Nazvěme množinu všech stavů, do kterých může prostředí přejít při hraní strategie a_{i} ∈ A, množinou možných výsledků. Označme ji

a_{i}^{∗} ⊂ Ω.

Definice 3.5 (Dominance strategie): Řekneme, že strategie a_{i} je dominantní nad strategií a_{j}, pokud je množina a_{i}^{∗} dominantní nad množinou a_{j}^{∗}. Strategie a_{i} je silně dominantní nad strategií a_{j}, pokud je množina a_{i}^{∗} silně dominantní nad množinou a_{j}^{∗}. ▶

Racionálně uvažující agent tedy vyloučí všechny strategie a_{i}, jestliže existuje strategie a_{j}, která nad strategií a_{i} silně dominuje. K zůžení výběru zbývajících strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 agnenty, i a j. Dvě strategie, a_{1} a a_{2} jsou v Nashově rovnosti, pokud za předpokladu že agent i zvolí strategii a_{1}, je nejvýhodnější strategií pro agenta j je strategie a_{2} a zároveň pokud agent j zvolí strategii a_{2}, je pro agnta i nejvýhodnější strategií a_{1}.

3.4.1 Použití pro výběr délky cyklu

Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupině společný. Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií A = {a_{1}, a_{2}, ...} je tedy v našem případě množinou všech nastavitelných délek cyklu T c_{k} v dané situaci. Mějme funkci u_{i_{T c}} : A → ℝ, jejíž funkční hodnota v bodě T c_{j} udává předpokládaný zisk pro agenta i při délce cyklu T c_{j}. Funkci u_{i}(ω) = u_{i}(τ(T c_{k}, T c_{l})) můžeme zadefinovat následovně (pro jednoduchost předpokládejme existenci dvou agentů i a j)

u_{i}(τ(T c_{k}, T c_{l}) = \{ \begin{matrix}u_{i_{T c}}(T c_{k}), & k = l \\ −∞, & k ≠ l \end{matrix} ,

kde hodnota −∞ vyjadřuje jakýsi kolabs systému při nastavení různých délek cyklu. To však znamená, že žádná strategie není sinlně dominantní nad jinou. Zároveň za předpokladu, že agent i zvolí strategii T c_{l}, agent j nemůže udělat lépe, než že zvolí stejnou strategii. To znamená že pro všechny strategie T c_{l} ∈ A platí, že jsou v Nashově rovnosti samy se sebou. Takto definovaná funkce nám v souladu s teorií zaručí, že agenti nenastaví různé délky cyklu, potřebujeme ale dodatečné kritérium kterou délku cyklu vybrat.

3.4.2 Globálně nějlepší řešení

Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu. Nejprve musíme určit množinu možných délek cyklu tak, aby v každém kroku simulace byla pro všechny agenty společná. Určíme tedy přirozená čísla n a dT c. Množina možných strategií A bude

A = {T c_{−n}, T c_{−n+1}, ..., T c_{n−1}, T c_{n}},
T c_{i} = T c + i · dT c,

kde T c je délka cyklu v minulém kroku simulace. Každý agent je pak schopen sestavit množinu součtů zisků

U = {u_{T c_{−n}}, u_{T c_{−n+1}}, ..., u_{T c_{n−1},u_{T cn}}},

kde

u_{T c_{i}} = ∑_{k} u_{k_{T c}}(T c_{i}).

Agent poté zvolí takovou délku cyklu T c_{i}, pro kterou platí

u_{T c_{i}} = max(U).

Toto je výběr globálně nejlepšího řešení, kde agent upřednostní takový čas délky cyklu, u kterého se předpokládá největší součet zisků od všech agentů nad časem, u kterého předpokládá největší zisk pro sebe.

12 KAPITOLA 3. MULTIAGENTNÍ SYSTÉMY

Popis implementace

4.1 Třída Lane

Každá instance třídy Lane reprezentuje jeden dopravní pruh. Po inicializaci se do příslušných proměnných uloží textové řetězce, podle kterých se přiřazují k pruhu data z detektorů a Aimsunu, jak je, pro naše účely důležitá, maximální délka fronty na dopravním pruhu za jednu simulační periodu.

4.2 Třída LaneHandler

Tato třída zprostředkovává přístup agentovi k ůdajům z jednotlivých pruhů. Stará se o zaznamenávání a statistické spracování dat z AIMSUNu. Také je zde implementován odhad čekací doby automobilu do průjezdu křižovatkou, což je údaj používaný v hodnotící délky cyklu funkci agenta.

4.2.1 Fronta

Agent předává třídě LaneHandler údaj o maximální délce fronty za vzorkovací periodu. Jedná se o největší počet automobilů v příslušném jízdním pruhu, jejichž rychlost reřesahuje určitou hodnotu. V našem konkrétním případě je tato mezní rychlost nastavena na 3,6 km/h. Tento ůdaj je však pro naše potřeby zkreslený, a to hlavně tím, že ve většině případů se délka cyklu neshoduje se vzorkovací periodou. Uvažujme jízdní pruh s poměrem délky zelené 0,5. Pokud bude například délka cyklu 180 sekund, a budeme li předpokládat, že začátek jedné periody se bude shodovat s časem, kdy na příslušném semaforu naskočí zelená, bude v první vzorkovací periodě pruh průjezdný po dobu 45 sekund, ale v další nebude průjezdný vůbec a fronta se za stejné hustoty provozu zvětší.

4.2.2 Odhad fronty

K odhadu fronty je použito metody tzv. exponencionálního zapomínání. Metoda vychází z povoucího průměru Který je vhodný pro odhad nekonstantní hodnoty. Označíme si veličinu \overline{q_{i}} jako plovoucí průměr fronty v kroce i, kam budeme ukládat posledních n měření. Označme si velikost fronty naměřenou v i-tém kroce jakoq_{i}. V kroce i + 1 je hodnota hodnota plovoucího průměru přepřičytením poslední naměřené hodnoty rovna

\overline{q_{i}} = \frac{1}{n} ∑_{j=0}^{n−1} q_{i−j}.

Obsahuje tedy všech posledních n naměřených hodnot. \overline{q_{i+1}} se tedy rovná

\overline{q_{i+1}} = \frac{1}{n} (n\overline{q_{i}} − q_{i−n+1} + q_{i+1}) = \overline{q_{i}} − \frac{1}{n} q_{i−n+1} + \frac{1}{n} q_{i+1}.

Abychom nemuseli ukládat posledních n měření. Zjednodušíme algoritmus tím, že místo kroku i − n + 1 odečteme od průměru jeho hodnotu podělenou délkou průměrovacího okna n. Výpočet přejde na tvar

\overline{q_{i+1}} = \frac{1}{n} (n\overline{q_{i}} − \overline{q_{i}} + q_{i+1}) = \overline{q_{i}} + \frac{1}{n} (q_{i+1} − \overline{q_{i}}).

\frac{1}{n} (q_{i+1} − \overline{q_{i}} je vlastně přírustek v kroku i + 1, označme si ho jako Δq_{i+1}, a faktor 1/n můžeme chápat jako jeho váhu w. Po dosazení dostáváme jednoduchý tvar

\overline{q_{i+1}} = \overline{q_{i}} + wΔq_{i+1}.

Průměr s exponenciálním zapomínáním se nazývá proto, že je v něm v i-tém kroce uložena i první hodnota, má však zanedbatelnou váhu (\frac{n−1}{n} )^{i}. Jedná se o jaksi zjednodušenou verzi Kalmanova filtru. Grafy 4.1 a 4.2 znázorňují rozdíl mezi okamžitou a filtrovanou délkou fronty při váze w = 0.2. Graf 4.1 pro konstantní délku cyklu 80 sekund, graf 4.2 pro délku cyklu peridicky se měnící od 40 do 120 sekund.

4.2. TŘÍDA LANEHANDLER 15

Obrázek 4.1: Porovnání okamžité a filtrované délky fronty délka cyklu 80 s

Obrázek 4.2: Porovnání okamžité a filtrované délky fronty délka cyklu 40-120 s

4.2.3 Odhad čekací doby

Představme si, že ke přižovatce přijíždí auto a_{n} a mezi tímto autem a křižovatkou je n dalšíchch aut. Budeme chtít odhadnout střední hodnotu času do průjezdu auta a_{n} křižovatkou < t_{wn} >. Nejprve odhadněmě < t_{wn} > v řípadě, že počet aut před ním je roven 0. Pokud přijede v době, kdy je signální skupina ve stavu zelená, projede okamžitě. Pokud ne, čeká do konce fáze. Označme si délku cyklu křižovatky T_{c} a poměr doby, kdy pro příslušný pruh svítí zelená jako r_{g}. Předpopkládejme rovnoměrné rozdělení, hustota pravděpodobnosti příjezdu auta v čase t je tedy

ω(t) = \{ \begin{matrix}\frac{1}{T_{c}} , & 0 < t < T_{c} \\ 0, & jinak \end{matrix} .

Střední hodnotu t_{w0} tedy spočteme jako

< t_{w0} >= ∫_{0}^{T_{c}} ω(t)t_{w0}(t)dt = ∫_{0}^{T_{c}(1−r_{g})} \frac{1}{T_{c}} tdt+∫_{T_{c}(1−r_{g})}^{T_{c}} \frac{1}{T_{c}} 0dt = \frac{1}{T_{c}} ∫_{0}^{T_{c}(1−r_{g})} tdt = \frac{1}{2} T_{c}(1−r_{g})^{2}

Výraz r_{g}T_{c} představuje jakousi délku časového okna, kdy auto projede bez čekání. Pokud chceme zjistit střední hodnotu času průjezdu libovolného auta < t_{wn} >, musíme toto okno zmenšit o dobu, kterou trvá průjezd křižovatkou autům před ním. Každý pruh křižovatky je schopen propustit maximální počet aut za sekundu. Tento ůdaj se nazývá saturovaný tok, budeme ho značit s_{s}, a bere se jako konstanta rovnající se 0.5auto/s. Pro n-té auto se tedy okno nulového čekání zkrátí na r_{g}T_{c} − \frac{n}{s_{s}} a střední hodnota doby průjezdu křižovatkou se změní na

< t_{wn} >= \frac{1}{T_{c}} ∫_{0}^{T_{c}(1−r_{g})+ \frac{n}{ss}} tdt = \frac{1}{2T_{c}} (T_{c}(1 − r_{g}) + \frac{n}{s_{s}} )^{2} .

To však platí pouze když stihnou všechna auta křižovatkou projet, tedy pokud

r_{g}T_{c} < \frac{n}{s_{s}} .

jestliže tato nerovnost není splněna, vozidlo nestihne projet na první zelenou a dobu čekání si prodlouží o další cyklus, přičemž počet aut stojících před ním se sníží o (r_{g}T_{c})s_{s}. Počet cyklů, které musíme připočítat k čekací době se rovná dolní celé části z podílu čekajících aut a počtu aut, které projedou na zelenou za jeden cyklus, tedy

⌊\frac{n}{r_{g}T_{c}s_{s}} ⌋ ,

a do horní meze intrgrálu potom přispěje pouze počet aut, který zbyl po odečtení těch, které zcela pokryla fáze se zeleným světlem. Po zahrnutí tohoto předpokladu se výraz pro < t_{wn} > změní na

< t_{wn} >= ⌊\frac{n}{r_{g}T_{c}s_{s}} ⌋ T_{c} + \frac{1}{2T_{c}} (T_{c}(1 − r_{g}) + \frac{n − ⌊\frac{n}{r_{g}T_{c}s_{s}} ⌋ r_{g}T_{c}s_{s}}{s_{s}} )^{2} .

Počet vozidel, která projedou na zelenou, však není přesně přímo úměrný délce zelené. Musíme počítat, že jich projede o něco méně vlivem pomalých reakcí řidiče, časových ztrát při rozjezsu kolony a podobně. Tyto vlivy započteme tak, že si zavedeme malý kladný parametr δ, o který snížíme dobu trvání průjezdnosti křižovatky. Výraz pro dobu průjezdnosti se potom změní na

(r_{g}T_{c} − δ)

a povzorec počet cyklů, po jejichž celý čas stráví vozidlo čekáním je roven

⌊\frac{n}{(r_{g}T_{c} − δ)s_{s}} ⌋ .

Konečná podoba výrazu pro střední hodnotu t_{wn} je tedy

< t_{wn} >= ⌊\frac{n}{(r_{g}T_{c} − δ)s_{s}} ⌋ T_{c} + \frac{1}{2T_{c}} (T_{c}(1 − r_{g}) + \frac{n − ⌊\frac{n}{(r_{g}T_{c}−δ)s_{s}} ⌋ r_{g}T_{c}s_{s}}{s_{s}} )^{2} .

Tento výpočet je implementován jako metoda getEcarW T, pijímající dva paramentry. Délku cyklu tc a pořadí auta n.

// ss − saturovany tok − konstanta
double cpg = tc ∗ gr ∗ s s ;
// number of w a i t i n g c y c l e s
double wc = f l o o r ( n / cpg ) ;
double E T l a s t c y c l e = ( 1/ (2∗ tc ) )
double ET = wc∗ tc + E T l a s t c y c l e ;
return ET;

}

double getEcarWT ( const double tc , const int n ) {

// gr − pomer casu z e l e n e − a t r i b u t t r i d y // pocet aut , k t e r a projedou za zeleneou

∗ ( tc ∗(1− gr ) + (n−wc∗cpg )/ s s )

∗ ( tc ∗(1− gr ) + (n−wc∗cpg )/ s s ) ;

Pro hodnocení výhodnosti se používá funkce getW T, která sčítá všechny čekací časy pro auta ve frontě

double getWT ( const double tc ) {
double sumEWT = 0 ;
int n = getAverageQueueLength ( ) ;
for ( int i = 0 ; i <= n ; i ++ ) {
sumEWT += getEcarWT ( tc , i ) ;
}
return sumEWT;

}

4.2.4 Odhad parametru δ

Delta vyjadřuje korekční parametr doby průjezdnosti křižovatky. Jak jsme již ukázali v kapitole 4.2.3, počet vozidel, které projedou křižovatkou za jeden cyklus řadiče je

(r_{g}T_{c} − δ)s_{s}.

To znamená že pokud je fronta větší, než (r_{g}T_{c} − δ)s_{s}, mměla by se její velikost za dobu T_{c} změnit o

Δq_{T_{c}} = n_{T c} − (r_{g}T_{c} − δ)s_{s},

kde n_{T c} je počet vozidel, přijíždějících na křižovatku za dobu T_{c}. Tento údaj je vlastně výstup z detektorů, který je nám však dostupný pouze jednou za simulační cyklus, trvající 90 sekund. Protože pracujeme s filtrovanými hodnotami front, nedojde k velké chybě, pokud výraz přepočítáme na 90 sekund do podoby

Δq_{90} = n_{90} − \frac{90}{T_{c}} (r_{g}T_{c} − δ)s_{s} = n_{90} − 90r_{g}s_{s} − \frac{90s_{s}}{T_{c}} δ,

z čehož si parametr δ vyjádříme jako

δ = \frac{T_{c}}{90s_{s}} (n_{90} − Δq_{90}) − r_{g}.

Jak údaje o projíždejících vozidlech za simulační cyklus n_{90}, tak parametry δ, jsou filtrovány způsobem, použitým na odhad délky fronty a popsaným v kapitole 4.2.2.

4.3 Třída agenta

4.4 Hlavní smyčka

Hlavní smyčka programu se stará o synchronizaci všech potřebných parametrů a provádění iterací. Před započetím opakování kroku simulace nastaví podle konfiguračního souboru počáteční parametry mikrosimulátoru dopravy Aimsun, jako jsou délka cyklu a fází řadičů, inicializuje jednotlivé agenty a zavolá jejich metody fromSettings a Validate. Také inicializuje instanci třídy Logger pro logování a AimsunDs potřebnou pro výměnu dat s Aimsunem.

4.4.1 Krok simulace

Délka kroku simulace je pevně nastavena na 90 sekund shodně s periodou sběru dat z Aimsunu. V jednom kroku se nejprve načtou data z Aimsunu do vektoru glob dt, který se následně předá každému z agentů jako paramentr jejich metody adapt. Následně zprostředkuje komunikaci mezi agenty tak, že naplní frontu zpráv voláním metod broadcast jednotlivých agentů. Z této fronty postupně poté odebírá zprávy, které předává agentům parametrem jejich metody receive, dokud není fronta prázdná. Tento cyklus se opakuje, dokud agenti komunikují, nebo dokud se nedosáhne předem stanoveného počtu opakování. Po ukončení komunikace naplní vektor výstupů glob ut voláním metod act hodotami parametrů pro Aimsun, vše zaloguje a vyčká do dalšího kroku.

20 KAPITOLA 4. POPIS IMPLEMENTACE

Literatura

21 22 LITERATURA