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

Výzkumný úkol

Teorie a aplikace multiagentního řízení dopravy

Vypracoval: Jakub Novotný
Vedoucí práce: Dr. Ing. Jan Přikryl, Ph.D.
Konzultant: Ing. Václav Šmídl, Ph.D.

Praha, 2012

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

Praha, 8. července 2010 Jakub Novotný

Rád bych poděkoval vedoucímu práce Ing. Janu Přikrylovi, Ph.D. a odbornému konzultantovi Ing. Václavu Šmídlovi, Ph.D. za odborné vedení a úsilí vynaložené při tvorbě této práce.

Název práce: Teorie a aplikace multiagentního řízení dopravy

Autor:  Jakub Novotný
Obor:  Inženýrská informatika
Zaměření:  Tvorba softwaru
Druh práce:  Výzkumný ůkol
Vedoucí práce: Dr. Ing. Jan Přikryl, Ph.D.

Abstrakt: V této práci je ...

Klíčová slova: multiagentní systémy, decentralizované řízení, řízení dopravy

Title: Theory of multiagent traffic control

Author:  Jakub Novotný

Abstract: This work represents ...

Key words: multiagent systems, decentralized control, control of traffic lights Zadání práce s podpisem děkana Vypracujte přehled literatury zabývající se použitím multi-agentních systémů v řízení

dopravy. Zvláštní pozornost věnujte řízení v městském provozu s množstvím křižovatek. Z použitých přístupů sestavte přehled používaných metod autonomního řízení a komunikovaných informací mezi agenty. Z dostupných metod zvolte takovou, která je v vhodná pro použití v oblasti Zličína a implementujte ji v prostředí řízení mikrosimulátoru AIMSUN. Výsledné řízení zvolenou metodou srovnejte se současným řídícím algoritmem navrženým dopravními experty.

Obsah

1 Úvod  1
2 Matematické metody rozhodování  3
2.1 Multiagentní systémy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.3 Druhy prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.4 Stavy prostředí a preference agentů . . . . . . . . . . . . . . . . . 4
2.2 Výběr strategie podle teorie her . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Zpětnovazebné učení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 Markovův rozhodvací proces . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 Dynamické programování . . . . . . . . . . . . . . . . . . . . . . 7
2.3.3 Zpětnovazebné učení (Reinforcement learning) . . . . . . . . . . . 9
2.3.3.1 Q-učení (Q-learning) . . . . . . . . . . . . . . . . . . . . 9
2.3.3.2 Učení na základě modelu (Model-based learning) …. 9
2.4 RMM - Rekurzivní modelové metody . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Formální definice . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.2 Rozhodovací algoritmus . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.3 Bayesovské učení . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.3.1 Věrohodnostní funkce . . . . . . . . . . . . . . . . . . . 13
2.5 LQ řízení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Použití rozhodovacích metod v řízení dopravy  16
3.1 Použití zpětnovazebného učení . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Použití RMM a Bayesova učení v decentralizovaném řízení dopravy … 17
3.3 Zhodnocení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.1 Použití zpětnovazebného učení . . . . . . . . . . . . . . . . . . . . 19

3.3.2 Použití RMM a Bayesova učení . . . . . . . . . . . . . . . . . . . 20
3.3.3 Použití LQ řízení ve strategii TUC . . . . . . . . . . . . . . . . . 20
3.3.3.1 Kvadratické kritérium . . . . . . . . . . . . . . . . . . . 21
4 Implementace  23
4.1 Použitá metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.1 Přechodové vztahy . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2 Minimalizace kritéria . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.2.1 Implementace minimalizace . . . . . . . . . . . . . . . . 28
4.2 Simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.0.2 VGS API . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.1 Řadiče . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.2 Oblast simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Popis algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Možné vylepšení do budoucna . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.0.1 Model toku . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.1 Odhdad odbočovacích poměrů . . . . . . . . . . . . . . . . . . . . 33
5 Výsledky  35
5.1 Scénář 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Scénář 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Závěr  39
Literatura  41
A Příloha 1  I

Kapitola 1

Úvod

Účelem této práce je prozkoumat možné způsoby decentralizovaného řízení dopravy, či metody s ústředním řídícim prvkem a jejich možnost decentralizace, vybrat jednu vhodnou metodu pro řízení dvou křižovate v oplasti Praha - Zličín, tuto metodu naimplementovat a otrestovat na simulátoru AIMSUN.

K decentralizovanému řízení bude použit tzv. multiagentní systém. Multiagentní systémy jsou dnes rychle se rozvijející formou decentralizované umělé inteligence a s úspěchem se aplikují na celou řadu problémů, kde není možné použít centrální řízení a je zapotřebí komunikace, koordinace a spolupráce.

V této práci si nejdříve definujeme základní pojmy, a poté se hlouběji podíváme na problém interakce agentů. Popíšeme zde různé způsoby výběru vhodných strategií. Prozkoumáme některé způsoby učení agentů, které pomáhají zlepšovat jejich reakce na neustále se měníci prostředí a na chování ostatních.

Po výběru nejvhodnější metody ji modifikujeme do vhodné formy pro naše účely, kde agent představuje řídící jednotku jedné signální skupiny a ovládá nastavení délky cyklu, tedy periodu, za kterou se vystřídají všechny fáze nastavení senaforů. Implementace bude provedena v jazyce C++ a s pomocí knihoven BDM, VGS API a IT++.

Metoda bude testována pomocí mikrosimulátoru dopravy AIMSUN a porovnávána se dvěma konstantními scénáři a se záznamem skutečné dopravní situace modelované oblasti. Výsledky simulace, tedy výstupní data ze simulátoru, budou zpracovány v prostředí MATLAB a pomocí jeho nadstavby VGS Toolbox, kde porovnáme několik zkoumaných KAPITOLA 1. ÚVOD 2 dopravních parametrů, jako je doba průjezdu sítí, průměrná rychlost, počet zastavení a jiné.

Matematické metody rozhodování

2.1 Multiagentní systémy

Multiagentní systém je druh distribuované umělé inteligence, jehož základem je agent - výpočetní prvek schopný autonomní reakce, komunikace a koordinace. Každý agent je schopen vyhodnotit optimální chování v dané situaci, které závisí i na akoci ostatních agentů. Ke sploupráci jednotlivých agentů slouží různe metody vejednávání a predikce chování.

2.1.1 Historie

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

2.1.2 Agent

Obecně uznávaná definice agenta neexistuje. Jedna z možných je uvedena například v publikaci [15]:

Definice 2.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. ▶

2.1.3 Druhy prostředí

Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle [15] se prostředí dají klasifikovat následovně:

• Deterministické vs. nedeterministické

• Dostupné vs. nedostupné

• Statické vs. dynamické

Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu. Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí.

2.1.4 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 2.2 (Uspořádání na množině všech stavů): Mějme 2 stavy prostředí ω_{1}, ω_{2}. Řekněme, ž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} ω

Tranzitivitu:

∀ω_{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.

2.2 Výběr strategie podle teorie her

Nyní, jak je rozebíráno v [15], 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žina

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

znázorňuje množinu 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 → Ω.

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 2.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 2.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 2.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 agenty, i a j

Definice 2.6 (Nashova rovnost): 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 agenta i nejvýhodnější strategií a_{1}. ▶

2.3 Zpětnovazebné učení

2.3.1 Markovův rozhodvací proces

Markovův rozhodvací proces je alternativní metoda sloužící k volbě strategií odhadem zisků z nich plynoucích do budoucna. Modeluje prostředí jako množinu stavů a akcí, které je možné provést a mění stav prostředí s určitou pravděpodobností. Čas je zde vnímán v diskrétní formě kroků a prostředí jako částečně známé, částečně ovlivnitelné a do jisté míry měnící se náhodně.

Účelem tohoto procesu je najít funkci π(s) : S → A která každému stavu prostředí jednoznačně přiřadí akci maximalizující zisky do určitého bodu v budoucnosti, teoreticky do nekonečna. V [14] je Markovův rozhodovací proces definován takto:

Definice 2.7 (Markovův rozhodovací proces): Markovův rozhodovací proces je definován jako uspořádaná čtveřice

(S, A, P, R)

kde jsou

• S - množina stavů prostředí

• A - množina možných akcí

• P (i, a, j) := p(s_{t+1} = j|s_{t} = i ∧ a = a_{t}) - pravděpodobnost, že při aplikování akce a za stavu i přejde systém do stavu j

• R(i, a, j) - okamžitý užitek přechodu systému ze stavu i do stavu j při akci a ▶

2.3.2 Dynamické programování

Dynamické programování je proces sloužící k nalezení optimální strategie dané π(s). K tomu slouží funkce očekávaných kumulativních diskontních zisků V^{π}(i) :→ ℝ reprezentující předpokládané dlouhodobé zisky při určité π(s). Agent se tedy snaží zvolit strategii tak, aby funkci V^{π} při daném počátečním stavu s_{0} = i maximalizoval. V [14] je tato funkce definována násedovně:

Definice 2.8 (V-funkce):

V^{π}(i) = ∑_{k=0}^{∞} E(γ^{k}R(s_{k}, π(s_{k}), s_{k+1}))

při s_{0} = i kde jsou

• γ ∈< 0, 1 > diskontní faktor určující snižování významnosti odhadu s narůstajícím časem

• E operator odhadu ▶

Tento zápis je spíše formální, proto se tato funkce v [14] definuje pomocí pomocí Q-funkce Q^{π}(i, a), funkce odhadující zisk při aplikování akce a při stavu a.

Definice 2.9 (Q-function):

Q(i, a)^{π} = ∑_{j∈S} P (i, a, j)(R(i, a, j) + γV^{π}(j))

kde jsou

V^{π}(i) = max_{a} Q^{π}(i, a)

,

π(i) = arg max_{a} Q^{π}(i, a)

Postupným iterativním přepočítáváním V, Q a π dostaneme Bellmanovu rovnici optimality definovanou v [3] jako:

Definice 2.10 (Bellmanova rovnice optimality):

Q(i, a)^{∗} = ∑_{j∈S} P (i, a, j)(R(i, a, j) + γV^{∗}(j))

kde funkce Q a V nezávisí na strategii π. Bellmanova rovnice optimality říká, že pokud jsou Q a V optimální, nemění se s dalšími kroky iterace. V praxi se stanoví nějaká dostatečně malá konstanta ϵ, a pokud se v dalším kroku Q a V nezmění o vícejak ϵ, považujeme je za optimální. Navíc bylo dokázáno, že vždy existuje právě jedna dvojice dvojice těchto funkcí, která je optimální a vždy ji lze tedy iterací určit.

Algoritmus pro určení funkce π tedy iterativně přes všechny stavy, akce a časové kroky upravuje funkce V, Q a π podle rovnic 2.9, a v [14] je v krocích popsán takto:

1. Inicializace počátečních hodnot funkcí V a Q

2. Opakovat kroky 3-5 do dosažení podmínek optimality

3. Upravit hodnotu Q-funkce podle rovnice

Q(i, a) = ∑_{j∈S} P (i, a, j)(R(i, a, j) + γV (j))

4. dopočítat hodnotu funkce V jako

V (i) = max_{a} Q(i, a)

5. nastavit hodnotu funkce pi na akci maximálního zisku jako

π(i) = arg max_{a} Q(i, a)

2.3.3 Zpětnovazebné učení (Reinforcement learning)

V praxi jsou z počátku hodnoty funkcí P a R popsané v 2.7 neznámé a je potřeba je určit pozorováním. Prakticky se tedy agent musí naučit jak prostředí reaguje na provedení každé akce v určitém stavu. Podle [14] se tedy na začátku procesu nastaví všechny hodnoty na nulu a po každé provedené akci se pozoruje jak prostředí reaguje, tedy hodnota funkce P (i, a, j), a jaký okamžitý zisk z toho plyne, tedy R(i, a, j). K určení těchto hodnot se používají různé algoritmy.

2.3.3.1 Q-učení (Q-learning)

Q-učení je bezmodelová metoda popsaná v [13] a [9]. K určení požadovaných hodnot, jak název napovídá, používá úpravu funkce Q definované v 2.9 v každém časovém kroce t podle rovnice:

Q_{t}(i, a) = \{ \begin{matrix}(1 − α_{t})Q_{t−1}(i, a) + α_{t}(r_{t} + γV_{t−1}(i)) & : i = i_{t} ∧ a = a_{t} \\ Q_{t−1}(i, a) & : jinak \end{matrix}

kde α_{t} ∈< 0, 1 > je učící faktor v časovém kroce t a r_{t} je okamžitý zisk akce a. Funkce P a R popisující prostředí se zde tedy nevyskytují a Q-funkce se zde upravuje přímo z naměřených hodnot za použití snižujícího se učícího koeficientu α.

2.3.3.2 Učení na základě modelu (Model-based learning)

V této metodě, popsané v [14], se modeluje prostředí funkcemi P (i, a, j) a R(i, a, j), které jsou definované v 2.7. Ty jsou z počátku neznámé a jejich hodnoty se určují metodou maximální věrohodnosti podle četnosti naměřených údajů. Agent popsaný v [14] používal následující veličiny:

• C_{i}(a) - počet, kolikrát agent zvolil akci a ve stavu i

• C_{i,j}(a) - počet, kolikrát prostředí přešlo ze stavu i do stavu j při aplikace akce a

• R_{i,j}(a) - součet okamžitých zisků při použití akce a ve stavu i a následném přechodu do stavu j

Model maximální věrohodnosti (MLM) je v [14] definován jako:

Definice 2.11 (MLM):

P̂(i, a, j) = \frac{C_{i,j}(a)}{C_{i}(a)}

R̂(i, a, j) = \frac{R_{i,j}(a)}{C_{i,j}(a)}

V každém časovém kroce je po aplikaci akce a model přepočítán. Poté je znovu použito dynamické programování popsané v sekci 2.3.2.

2.4 RMM - Rekurzivní modelové metody

Rekurzivní modelová metoda, která byla použita v článku [5] k modelování chování agentů ovládajících ostatní dopravní uzly, slouží k odhadu chování ostatních a gentů. Akce každého agenta z pravidlo ovlivňuje do určité míry celý systém, tudíž výběr strategie každého agenta závisí na předpokládaném chování ostatních agentů. Tato metoda minimalizuje nutnost komunikace a vyjednávání o provedení jisté akce tím, že každý agent je schopen modelovat rozhodnutí ostatních a podle známých parametrů prostředí s určitou pravděpodobností stanovit jejich volbu.

2.4.1 Formální definice

Základním stavebním kamenem RMM je matice zisků agenta, Definovaná v souladu s teorií her v [5]

Definice 2.12 (Matice zisků): Matice zisků P_{R_{i}} agenta R_{i} je definována trojicí

(R, A, U)

kde R je množina všech agentů v systému, A je množina množin A_{j} = {a_{1}^{j}, a_{2}^{j}, ...} alternativních akcí agenta R_{j}. A_{j} budeme nazývat rozhodovací prostor agenta R_{j}. U je funkce

U : A_{1} × A_{2} × ... × A_{n} → ℝ

přiřazující hodnoty zisku všem kombinacím akcí všech agentů. ▶

Každý agent provádí danou akci z nějakého důvodu. Zisky agenta R_{i} jsou spojeny s provedením jeho určité akce a_{m}^{i} ∈ A_{i} za předpokladu, že ostatní agenti R_{j}, j ∈ {1..n}/{i} provedou akci a_{k}^{j} ∈ A_{j}. Matice je tedy n-dimenzionální, kde n je počet agentů v systému, a sestává se z prvků u_{a_{k}^{1}...a_{l}^{i}...a_{m}^{n}}^{R_{i}}, reprezentující zisky v dané situaci. K určení pravděpodobnosti provedení strategií ostatních agentů se definuje rekursivní modelová struktura. [5] Definice 2.13 (Rekursivní modelová struktura): Rekursivní modelová struktura RMS_{R_{i}} agenta R_{i} je definována jako dvojice

(P_{R_{i}}, RM_{R_{i}})

, kde P_{R_{i}} je matice zisků definovaná v 2.12 a RM_{R_{i}} je rekurzivní model 2.14, který je použit k modelování rozhodování ostatních agentů. ▶

Rekursivní model je definován v [5] takto:

Definice 2.14 (Rekursivní model): Rekursivní model MR_{R_{i}} agenta R_{i} je definován jako m-tice dvojic ^{1}

MR_{R_{i}} = ((p_{1}^{R_{i}}, M_{{−R_{i}}}^{(R_{i},1)}), ..., (p_{m}^{R_{i}}, M_{{−R_{i}}}^{(R_{i},m)}))

kde

M_{{−R_{i}}}^{(R_{i},k)} = (M_{R_{1}}^{(R_{i},k)}, ..., M_{R_{i−1}}^{(R_{i},k)}, M_{R_{i+1}}^{(R_{i},k)}, ..., M_{R_{n}}^{(R_{i},k)})

představuje jednu z m (n − 1)-tic rozhodovacích modelů ostatních agentů a p_{i}^{k} jeho subjektivní předpokládanou pravděpodobnost. ▶

M_{R_{j}}^{(R_{i},k)} je tedy jeden z možných modelů agenta R_{j}, který předpokládá agent R_{i} s pravděpodobností p_{k}^{R_{i}}. Platí samozřejmě podmínka ∑_{k=1}^{m} p_{k}^{R_{i}} = 1. Model M_{R_{j}}^{(R_{i},k)} se dá podle [5] rozdělit do tří forem:

• IM_{R_{j}}^{(R_{i},k)} - Recionální model

• NM_{R_{j}}^{(R_{i},k)} - Neinformovaný model

• SM_{R_{j}}^{(R_{i},k)} - Neracionální model

Recionální model odpovídá tomu, že agent R_{i} předpokládá o agentovi R_{j}, že se chová racionálně. V [5] je definován jako

IM_{R_{j}}^{(R_{i},k)} = RMS_{R_{j}}^{(R_{i},k)} ,

s parametry p_{a_{l}^{j}}^{(R_{i},k)} a P_{R_{j}}^{(R_{i},k)}. P_{R_{j}}^{(R_{i},k)} je matice zisků, kterou podle agenta R_{i} v modelu k agent R_{j} použije. což je Rekurzivní modelové struktura s k-tými daty, o kterých agent R_{i} předpokládá, že je agent R_{j} použije k rozhodování.

1{−R_{i}} je zkrácený zápis množiny ostatních agentů {R_{1}, ..., R_{n}}/{R_{i}}

Neinformovaný model vychází z toho, že agent R_{i} nemá o agentovi R_{j} žádné informace, tudíž přiřadí každé akci a_{l}^{R_{j}} pravděpodobnost p_{a_{l}^{j}}^{(R_{i},k)} = \frac{1}{|A_{j}|} , kde |A_{j}| je počet možných akcí agenta R_{j}, což odpovídá rovnoměrnému rozdělení. p_{a_{l}^{j}}^{(R_{i},k)} značí pravd’ěpodobnost, že podle agenta R_{i} nastane v k-tém modelu agenta R_{j} akce a_{l}^{j}.

Neracionální model odpovídá tomu, že se agent A_{j} chová iracionálně. Chování se v tompto případě modeluje podle situace pokaždé jinak.

Systém se tedy rekurzivně rozvijí, dokud jsou dostupné informace. Pokud nejsou, rekurze skončí neinformovaným modelem s rovnoměrným rozdělením pravděpodobnosti všech akcí. Rekurze také může skončit iracionálním modelem, což ovšem není v našem případě příliš časté.

2.4.2 Rozhodovací algoritmus

Po zkonstruování rekurzivní modelové struktury se prochází tento systém od konce rekurze, kde jsou pravděpodobnosti známi, z důvodu ukončení rekurzivního rozvijení neinformovaným modelem. K výběru nejpravděpodobnější situace se používá tzv. užitečnosti. [5] Definice 2.15 (Užitečnost): Užitečnost akce a_{m}^{i} podle agenta R_{i} je definována jako

u_{a_{m}^{i}}^{R_{i}} = ∑_{a_{q}^{1}∈A_{1}} ... ∑_{a_{v}^{i−1}∈A_{i−1}} ∑_{a_{w}^{i+1}∈A_{i+1}} ... ∑_{a_{x}^{n}∈A_{n}}(p_{a_{q}^{1}}^{R_{i}}...p_{a_{v}^{i−1}}^{R_{i}}p_{a_{w}^{i−1}}^{R_{i}}...p_{a_{x}^{n}}^{R_{i}}u_{a_{q}^{1}...a_{m}^{i}...a_{x}^{n}}^{R_{i}}) ,

kde

u_{a_{q}^{1}...a_{x}^{n}}^{R_{i}}

je prvek matice zisků P_{R_{i}} a pravděpodobnost p_{a_{o}^{j}}^{R_{i}} je definována jako

p_{a_{k}^{j}}^{R_{i}} = ∑_{o} p_{o}^{R_{i}}p_{a_{k}^{j}}^{(R_{i},o)}

.

kde p_{o}^{R_{i}} je pravděpodobnost modelu z definice 2.14 a p_{a_{k}^{j}}^{(R_{i},o)} značí pravd’ěpodobnost, že podle agenta R_{i} nastane v o-tém modelu agenta R_{j} akce a_{k}^{j}. V případě, že je algoritmus v bodě racionálního modelu, určí se tato hodnota rekurzivně, pokud je model neinformovaný, je rovna \frac{1}{|A_{j}|} . p_{a_{k}^{j}}^{R_{i}} je tedy součet pravděpodobností dané akce v modelu vyvážený pravděpodobností modelu a u_{a_{m}^{i}}^{R_{i}} se definuje jako součet všech prvků matice zisků, kromě těch, které zahrnují jiné akce agenta R_{i}, než je a_{k}^{j}, vyvažený touto pravděpodobností.

2.5 Bayesovské učení

V této kapitole je naznačena metoda bayesovského učení , což je bodový odhadu parametru rozdělení náhodné veličiny založený na Bayesovuě větě. Tato metoda byla použita v článku [5] ke zlepšení odhadu pravděpodobnosti uskutečnění se modelového chování ostatních agentů. Jeho výhodou je využití experimentální i expertní znalosti. V praxi se této metody hojně využívá tam, kde jsou data získávána postupně a zpočátku je nutné parametr odhadnout na základě zkušenosti a nadále ho podle výsledků měření zpřesňovat.

Definice 2.16 (Podmíněná pravděpodobnost): Necht’ A a B jsou náhodné jevy. Podmíněná pravděpodobnost jevu A na jevu B, tedy pravděpodobnost že nastane jev A pokud nastane jev B, je definována jako

P (A|B) = \frac{P (A ∩ B)}{P (B)}

Věta 2.1 (Bayesova věta): Necht’ A a B jsou náhodné jevy a platí P (B) > 0. Potom

P (A|B) = \frac{P (B|A)P (A)}{P (B)}

V souladu s [6] zavedeme následující značení:

• y(t) = [y_{1}, ..., y_{T}] - vetor T ∈ ℕ naměřených hodnot, kde y_{t} ∈ {0, 1} a y_{t} = 1 značí, že výsledek experimentu v čase t ∈ {1, ..., T } dopadlu v souladu s naší hypotézou

• Θ - parametr rozdělení

• Θ̂_{T} - odhad parametru při T naměřených hodnotách

• f(y_{t}|Θ) - hustota pravděpodobnosti náhodné veličiny v čase t při parametru Θ

2.5.0.1 Věrohodnostní funkce

K odhadu parametru se v této metodě využívá věrohodnostní funkce, která vyjadřuje pravděpodobnost, že při daném parametru se bude vektor naměřených výsledků bude rovnat teoretické hodnotě. V [6] se tato funkce definuje jako: ^{2} Definice 2.17 (Věrohodnostní funkce):

2Tato definice je poněkud zjednodušena a předpokládá, že výsledek t-tého pokusu nezávisí na předchozích pokusech, ani na počátečních podmínkách před t-tým pokusem.

f(y(T)|Θ) = ∏_{t=1}^{T} f(y_{t}|Θ)

Při použití těchtu veličin nabývá Bayesova věta podle [6] tvaru

f(Θ|y(T)) = \frac{f(y(T)|Θ)f(Θ)}{f(y(T))}

kde jsou

• f(Θ|y(T)) aposteriorní hustota pravděpodobnosti

• f(y(T)|Θ) Věrohodnostní funkce

• f(Θ) = f(Θ|y(0)) je tzv. apriorní hustota pravděpodobnosti

• f(y(T)) normalizační konstanta (f(Θ|y(T)) se bere jako funkce Θ a parametrů y(t))

Apriorní hustota pravděpodobnosti zde vyjadřuje odhad parametru při nenaměřených datech. Jedná se tedy o expertní odhad, předpokládané chování náhodné veličiny založené na známých faktech a zkušenosti. Aposteriorní hustota pravděpodobnosti představuje pravděpodobnost parametru Θ závislou na naměřených hodnotách náhodné veličiny a její střední hodnota je odhadem tohoto parametru. Tedy platí:

Θ̂_{T} = ∫_{ℝ} f(Θ|y(T))dΘ

2.6 LQ řízení

LQ je zkratka slovního spojení linaer-quadratic, tedy lineárně kvadratický. Jedná se obecně o metodu, kdy je systém v diskrétním časovém kroku t popsán vektorem proměnných x(t) = (x_{1}(t), ..., x_{n}(t)) a my můžeme nastavovat vektor parametrů y(t) = (y_{1}(t), ..., y_{n}(t)). Metoda je popsána a použita v článku [11] pro nastavování časů zelených na křižovatce. Princip přechodu z času t do t + 1 je popsán lineárním vztahem

x(t + 1) = Ax(t) + By(t) ,  (2.1)

kde matice A a B jsou matice stavů a vstupů vyjadřující odezvu systému vzhledem k x(t) a y(t). Účelem LQ řízení je najít optimální hodnoty y(t) v závislosti na x(t) dané zpětnovazebnou maticí L vztahem

y(t) = −Lx(t) .  (2.2)

Optimalita je definována pomocí kvadratického kritéria

J = ∑_{t=1}^{∞} x(t)^{T} Qx(t) + y(t)^{T} Ry(t) ,  (2.3)

kde Q a R jsou diagonální pozitivně semidefinitní matice vah určující významnost jednotlivých členů kritéria. Zpětnovazebná matice L se podle [11] dostane minimalizací kritéria J jako

L = (R + B^{T} P B)^{−1}B^{T} P A ,  (2.4)

kde P je jednoznačné řešení Riccatiho rovnice pro diskrétní časový krok

P = Q + A^{T} (P − P B(R + B^{T} P B)B^{T} P)A .  (2.5)

Rovnici a její řešení popisuje například [2].

Použití rozhodovacích metod v

řízení dopravy

3.1 Použití zpětnovazebného učení

V [14] je popsána simulace používající zpětnovazebné učení na základě modelu popsané v 2.3.3.2. Na rozdíl od ezperimentu popsaného v předchozí kapitole zde autoři zvolili variantu, kde existují 2 druhy agentů: agent-vozidlo a agent-křižovatka. Agent-vozidlo má v každý časový krok následující parametry definující jeho stav, které se ukládají v průběhu celé simulace:

• node - dopravní uzel, kde se právě nachází

• dir - směr vůči tomuto uzlu

• place - pozice ve frontě vozidel

• des - místo, kam chce v systému dojet

Algoritmus se snaží minimalizovat celkový čas od vyjetí až po dosažení cíle. Každý agent má ve vyjednávání právo hlasovat o nastavení dopravního uzlu, tedy jestli bude v průjezdném nebo uzavřeném stavu. Pro každý uzel node a směr dir je to tedy akce g - na uzlu node, kde se vozidlo nachází ve směru dir, svítí červená - uzel je v tomto směru neprůjezdný, a akce g - uzel je v tomto směru průjezdný. Funkce definované v 2.3.2 se tedy zapisují ve tvarech

Q([node, dir, place, des], a)
V ([node, dir, place, des])

kde a ∈ {r, g}. Optimální akce se v [14] volí podle maxima sumy z

Q([node, dir, place, des], r) − Q([node, dir, place, des], g)

přes všechny vozidla ovlivněná frontou u daného uzlu. Komunikace je zde tedy omezena pouze na výměnu hodnot Q.

3.2 Použití RMM a Bayesova učení v

decentralizovaném řízení dopravy

V následujícím textu se budeme zabývat konkrétním využitím rekursivních modelovacích metod v kombinaci s bayesovským učením v decentralizovaném řízení dopravy pomocí multiagentních systémů. Tento koncept byl testován a výsledky zveřejněny v článku [7].

Testy byly prováděny na modelu dvou křižovatek klasického typu, kde každý agent R_{1}, R_{2} ovládal jednu z nich. K modelování chování druhého agenta bylo použito třísyupňové RMM zakončené neinformovaným modelem. Obrázek 3.1 z článku [7] znázorňuje RMM agenta R_{1}, kde se na každé úrovni agent rozhoduje mezi dvěma modely, informovaným a neinformovaným. Z počátku simulace jsou těmto modelům přiřazeny pravděpodobnosti po řadě 0,8 a 0,2. Tyto pravděpodobnosti jsou upravovány metodou bayesovskeho učení podle akcí provedených druhým agentem. Pro řešení tohoto modelu je použit algoritmus z [5] popsaný v předchozí kapitole.

Určujícím faktorem pro sestavení matice zisků je délka fronty čekajících aut. Tento údaj byl také použit jako klíčový pro srovnání s ostatními metodami při testování. Metoda byla testována za použití simulace psané v jazyce VC++ a porovnávána s dvěma dalšími, a to pevně dané sekvence stanovené dopravními experty a stochastická metoda ”Hillclimbing process”. Z tohoto srovnání vychází metoda využívající RMM a bayesovského učenís podle výsledků prezentovaných v [7] nejlépe, jak můžeme vidět na obrázku 3.2.

KAPITOLA 3. POUŽITÍ ROZHODOVACÍCH METOD V ŘÍZENÍ DOPRAVY 18

Obrázek 3.1: Tříúrovňová rekurzivní modelová struktura agenta R_{1} Obrázek 3.2: Výsledky měření. M1 - RMM, M2 - pevné cykly, M3 - ”Hill-

climbing”

3.3 Zhodnocení

3.3.1 Použití zpětnovazebného učení

Metode popsaná v článku [14] používá ohodnocovací funkci založenou na parametrech jednotlivých vozidel. Výhodou oproti pojetí, kdy agent představuje pouze signální skupinu, jsou například v tom, že není potřeba odhadovat délku fronty a úloha se celá zjednoduší. Například v publikaci [10] se musí používat k odhadu funkcí V a Q neuronová sít’. Navíc tento systém umožňuje i výběr optimální cesty vozidla pro průjezd dopravní sítí. Nevýhodou tohoto pojetí je ovšem značná neuniverzálnost. Už pro počítačové testování tato metode znesnadnuje či úplně znemožňuje použít celou řadu dopravních simulátorů, které jsou pro simulaci po dlouhou dobu optimalizovány a jejichž nasazení značně zjednodušuje práci a urychluje vývoj. Navíc pokud je použit řadič, který obstarává logiku přepínání průjezdnosti a lze nastavovat pouze vnější parametry jako jsou délka cyklu a offset, je metoda, která potřebuje okamžitou změnu signalizace naprosto nevhodná, proto je toto řešení pro reálné nasazení v dnešní době obtížně použitelné. Zapojení některých myšlenek z článku [14] nebo použití zpětnovazevného učení k řešení dílčích problémů by však mohlo přinést zlepšení i do způsobu žešení popsaných v dalších kapitolách.

3.3.2 Použití RMM a Bayesova učení

V článku [5] nenjsou podrobně popsány akce agentů ani způsob, jak hodnotit jejich užitečnost. Proto je tato metoda jen obtížně reprodukovatelná, modifikovatelná či dále rozvinutelná. V naší situaci popsanné v dalších kapitolách také není nutné modelovat chování agentů, nebot’ je možné ho vykomunikovat pomocí posílaných zpráv. V případě reálného nasazení by však bylo možné vylepšení zapojení RMM pro odhad chování agenta pokud by nastal výpadek spojení nebo podobná situace.

3.3.3 Použití LQ řízení ve strategii TUC

LQ řízení bylo použito v [11] k nalezení optimální délky zelených v systému 13-ti signálních skupin. Proměnné x_{i}(t) zde představují obsazenost ramene i spojující křižovatky M a N. Účelem strategie je nalezení optimální délky zelených g, g_{N,i} značí délku zelené na signální skupiny křižovatky N zprůjezdňující směr do ramene i. Předpokládaný vztah pro přechod systému z času t do času t + 1 je

x_{i}(t + 1) = x_{i}(t) + T [q_{i}(t) + s_{i}(t) + d_{i}(t) + u_{i}(t)] ,  (3.1)

kde proměnné značí:

• T - časový krok

• q_{i}(t) - přírůstek vozidel z křižovatek

• u_{i}(t) - úbytek vozidel do ostatních křižovatek

• s_{i}(t) - přírůstek vozidel z okolí sítě

• d_{i}(t) - úbytek vozidel mimo sít’

Přírůstek vozidel z křižovatek je dán vztahem

q_{i}(t) = ∑_{k∈I_{m}} t_{k,i}u_{k}(t) ,  (3.2)

je to tedy součet úbytků vozidel z ramen ústících do křižovatky N vynásobených koeficinety t_{k,i}, což jsou odbočovací poměry z ramene k do ramene i. V podovném tvaru se předpokládá s_{i}(t)

s_{i}(t) = t_{i,0}q_{i}(t) ,  (3.3)

kde t_{i,0} je odbočovací koeficient ramene i mimo sledovanou sít’. Při délce cyklu C, saturovaném toku S_{i} a délce zelených g_{N,i}(t) ramene i platí

u_{i}(t) = \frac{S_{i} ∑ g_{N,i}(t)}{C} .  (3.4)

Rovnice 3.1 tedy přechází do tvaru

x_{i}(t + 1) = x_{i}(t) + T [(1 − t_{i,0}) ∑_{k∈I_{m}} t_{k,i} \frac{S_{k} ∑ g_{M,k}(t)}{C} − \frac{S_{i} ∑ g_{N,i}(t)}{C} + d_{i}(t)] . (3.5)

Uvažujeme-li nominální hodnoty d^{n} a g^{n} vedoucí vždy na stav x^{n}, platí podle rovnice 3.5

0 = T [(1 − t_{i,0}) ∑_{k∈I_{m}} t_{k,i} \frac{S_{k} ∑ g_{M,k}^{n}}{C} − \frac{S_{i} ∑ g_{N,i}^{n}}{C} + d_{i}^{n}] .  (3.6)

Označíme-li

Δg(t) = g(t) − g^{n} ,  (3.7)

můžeme psát rovnici 3.5 jako

x_{i}(t + 1) = x_{i}(t) + T [(1 − t_{i,0}) ∑_{k∈I_{m}} t_{k,i} \frac{S_{k} ∑ Δg_{M,k}(t)}{C} − \frac{S_{i} ∑ Δg_{N,i}(t)}{C} ] ,  (3.8)

což dovoluje tuto rovnici zapsat pomocí matic v požadovaném tvaru

x(t + 1) = Ax(t) + BΔg(t) ,  (3.9)

kde A je jednotková matice.

3.3.3.1 Kvadratické kritérium

Účelem lagoritmu je minimalizovat obsazenost ramen, tedy vektor x(t) a penalizovat změnu délky trvání zelené oproti nominálním hodnotám. Kvadratické kritérium optimálního řízení 2.3 jetedy v [11] definováno vztahem

J = ∑_{t=0}^{∞} x(t)^{T} Qx(t) + Δg(t)^{T} RΔg(t) .  (3.10)

Diagonální matice Q je zde zodpovědná za vyvažování počtu vozidel jednotlivých úseků. V [11] je každý diagonální prvek Q_{i,i} matice Q položen převrácené hodnotě maximálního povoleného počtu vozidel daného úseku i. R = rI penalizuje změnu časů zelených. Parametr r ovlivňuje míru reakce systému a ja volen metodou pokus-oprava. Minimalizací tohoto kritéria pomcí 2.4 získáme zpětnovazebnou matici L, která určuje g(t). Z rovnic 2.2 a 3.7 dostaneme výsledný vztah

g(t) = g^{n} − Lx(t) .  (3.11)

Toto řešení předpokládá, že známe hodnotu g^{n}, při které systém zůstává ve stavu x^{n}. Tak tomu ale většinou není. Při absenci znalosti g^{n} podle [11] odečteme g(t) − g(t − 1) a rovnice 3.11 nabývá tvaru

g(t) = g(t − 1) − L(x(t) − x(t − 1)) .  (3.12)

23

Kapitola 4

Implementace

V textu  V programu Název  Popis
T ∈ ℕ  T  Vzorkovací perioda
C ∈ ℕ  Tc  Délka cyklu

S = 0, 5 ss Saturovaný tok Maximální počet vozidel, která projedou křižovatkou za sekundu

L ∈ ℝ^{+} L Ztrátový čas Čas potřebný k vyklizení křižovatky mezi dvěma fázemi

J = {j_{1}, ..., j_{n}}  Množina signálních skupin

J_{A} ⊂ J Množina signálních skupin agenta A Skupiny náležící jednomu agentovi

I_{j} ⊂ J Množina vstupů signální skupiny Signální skupiny ostatních agentů ústících do příslušné skupiny g

g_{j}^{N} ∈< 0, 1 > Nominální poměr zelené Defi novaný poměr fází

g_{j}(t) ∈< 0, 1 > Efektivní poměr zelené Část z délky cyklu, kdy je signální skupina průjezdná

i_{j}(t) ∈ ℝ^{+} i g Hustota vstupů Počet přijíždějících vozidel do pruhu signální skupiny za jednotku času

o_{j}(t) ∈ ℝ^{+} Hustota výstupů Počet vyjíždějících vozidel z pruhu signální skupiny za jednotku času

q_{j}(t) ∈ ℕ_{0}^{+} Fronta Počet vozidel jedoucí menší rychlostí než 3, 6km/h

α_{j,k} ∈< 0, 1 >  Odbočovací poměr z j do k

4.1 Použitá metoda

Účelem této práce je řídit provoz pomocí nastavení optimální délky cyklu za použití multiagentního systému, kde každý agent ovládá signální skupiny jedné křižovatky a jsou mu dostupné příslušné údaje. Jako vhodná metoda bylo zvoleno LQ řízení, které se snaží minimalizovat fronty a penalizovat délku cyklu.

4.1.1 Přechodové vztahy

Jako údaj popisující stav systému byla zvolena délka fronty q_{j}(t), což je počet aut v jízdním pruhu jedoucích méně než 3,6 km/h. Pro danou frontu v čase t + 1 platí zřejmě vztah

q_{j}(t + 1) = q_{j}(t) + T (i_{j}(t) − o_{j}(t)),  (4.1)

kde hustota vstupu i_{j}(t) je součtem výstupů sousedů pronásobený odbočovacími poměry, případně vstupu do systému i_{j,0}(t), pokud se jedná o koncové rameno řízené oblasti, tedy

i_{j}(t) = i_{j,0}(t) + ∑_{k∈I_{j}} α_{k,j}o_{k}(t).  (4.2)

Křižovtkou z daného jízdního pruhu v průjezdné fázi projede S vozidel za sekundu, kde délka průjezdné fáze závisí na nastaveném poměru a délce cyklu. Před přechodem do nové fáze signálího plánu je potřeba vklidit křižovatku, což vede ke ztrátovému času L, který se projeví vždy jednou za cyklus. Efektivní délka zelené je tedy

g_{j}(t) = (C(t) − L)g_{j}^{N}  (4.3)

a pro hustotu výstupu platí

o_{j}(t) = \frac{S_{j}g_{j}(t)}{C(t)} = S_{j}g_{j}^{N} (1 − LC(t)^{−1}) .  (4.4)

Rovnice 4.1 tedy přechází do tvaru

q_{j}(t + 1) = q_{j}(t) + T (i_{j,0}(t) + ∑_{k∈I_{j}} α_{k,j}S_{k}g_{k}^{N} (1 − LC(t)^{−1}) − S_{j}g_{j}^{N} (1 − LC(t)^{−1})) .

(4.5)

Za řídící proměnnou tedy vezmeme

y(t) = 1 − LC(t)^{−1} .  (4.6)

takže můžeme rovnici 4.5 přepsat do maticové formy

q(t + 1) = A_{0}q(t) + B_{0}y(t) + I_{0}(t) ,  (4.7)

kde A je jednotková matice, B je diagonální matice s prvky

b_{jj} = T (∑_{k∈I_{j}} α_{k,j}S_{k}g_{k}^{N} − S_{j}g_{j}^{N} ) ,  (4.8)

a I je vektor s prvky I_{0_{j}} = T i_{j,0}(t).

4.1.2 Minimalizace kritéria

Podobně jako v předchozí kapitole budeme minimalizovat kvaratické kritérium J. Minimalizaci budeme provádět v proměnných u(t) pro časový horizont h, tedy pro vektory ΔC(t_{0}), ΔC(t_{0} +1), ..., u(t_{0} +h). Pro zpřehlednění zápisu položíme bez újmy na obecnosti t_{0} = 0. Matici I_{0}(t), která vyjadřuje příjezd vozidel z okolí do sledované sítě, budeme v rámci minimalizačního horizontu považovat za konstantu značenou I_{0} a vztah 4.7 se dá tedy přepsat do tvaru

( \begin{matrix}q(t + 1) \\ 1 \end{matrix} ) = ( \begin{matrix}A_{0} & I_{0} \\ 0 & 1 \end{matrix} ) ( \begin{matrix}q(t) \\ 1 \end{matrix} ) + ( \begin{matrix}B_{0} \\ 0 \end{matrix} ) u(t) .  (4.9)

Po provedení substituce

x(t) = ( \begin{matrix}q(t) \\ 1 \end{matrix} ) , A = ( \begin{matrix}A_{0} & I_{0} \\ 0 & 1 \end{matrix} ) , B = ( \begin{matrix}B_{0} \\ 0 \end{matrix} ) ,  (4.10)

se rovnice 4.9 zjednoduší na

x(t + 1) = Ax(t) + Bu(t) ,  (4.11)

kde chybí konstantní člen.

Kvadratické kritérium ve tvaru

J = ∑_{t=0}^{h} x(t)^{T} Qx(t) + u(t)^{T} Ru(t) ,  (4.12)

kde Q a R jsou diagonální pozitivně definitní matice vah, rozepíšeme pomocí vztahu 4.11 a budeme minimalizovat pro jednotlivá t podle u(t). Proměnná u(h) se v kritériu vyskytuje pouze ve členu

u(h)^{T} Ru(h)  (4.13)

a tedy musí být u(h) = 0. u(h − 1) se vyskytuje ve členech

u(h−1)^{T} Ru(h−1)+(x(h−1)^{T} A^{T} +u(h−1)^{T} B^{T})Q(Ax(h−1)+Bu(h−1)+I_{0}) , (4.14)

což lze pomocí složených vektorů a matic přepsat do tvaru

(u(h − 1)^{T} , x(h − 1)^{T}) ( \begin{matrix}B^{T} \sqrt{Q}^{T} & \sqrt{R}^{T} \\ A^{T} \sqrt{Q}^{T} & 0 \end{matrix} ) ( \begin{matrix}\sqrt{Q}B & \sqrt{Q}A \\ \sqrt{R} & 0 \end{matrix} ) ( \begin{matrix}u(h − 1) \\ x(h − 1) \end{matrix} ) , (4.15)

kde symbolem \sqrt{Q} myslíme matici, pro níž platí \sqrt{Q}^{T} \sqrt{Q} = Q. Matice Q a R jsou pozitivně definitní diagonální matice, takže \sqrt{Q} bude také pozitivně definitní diagonální a její diagonální prvky budou rovny odmocnině příslušných prvků původní matice Q. Složenou matici

M_{0} = ( \begin{matrix}\sqrt{Q}B & \sqrt{Q}A \\ \sqrt{R} & 0 \end{matrix} )  (4.16)

můžeme pomocí QR dekompozice rozložit na součin

M_{0} = M_{R}M_{Q},  (4.17)

kde M_{Q} je horní trojůhelníková matice a M_{R} je matice ortonormální. Pro ortonormální matici M_{R} platí

M_{R}^{T}M_{R} = I ,  (4.18)

nebot’ její zloupce jsou vzájemně ortogonální a normované na jednotku. Z toho plyne, že součin matic M_{0}^{T} M_{0} vyskytující se v členu 4.15 můžeme pomocí QR rozlkladu převést na tvar

M_{0}^{T} M_{0} = (M_{R}M_{Q})^{T} M_{R}M_{Q} = M_{Q}^{T}M_{R}^{T}M_{R}M_{Q} = M_{Q}^{T}M_{Q} ,  (4.19)

kde

M_{Q} = ( \begin{matrix}L_{u} & L \\ 0 & L_{q} \end{matrix} ) ,  (4.20)

je horní trojůhelníková matice. Člen 4.15 poté přejde na tvar

(ΔC(h − 1)^{T} , x(h − 1)^{T}) ( \begin{matrix}L_{q}^{T} & 0 \\ L^{T} & L_{u}^{T} \end{matrix} ) ( \begin{matrix}L_{u} & L \\ 0 & L_{q} \end{matrix} ) ( \begin{matrix}u(h − 1) \\ x(h − 1) \end{matrix} ) ,  (4.21)

který můžeme dále upravit na

(L_{u}u(h − 1) + L_{q}x(h − 1))^{T} (L_{u}u(h − 1) + L_{q}x(h − 1)) + x(h − 1)^{T} L_{q}^{T} L_{q}x(h − 1) (4.22)

. Pokud tento člen chceme minimalizovat v proměnné x(h − 1), musí nutně platit

u(h − 1) = −L_{u}^{−1}Lx(h − 1)  (4.23)

. Zbývající nenulová část x(h − 1)^{T} L_{q}^{T} L_{q}x(h − 1) lze přepsat pomocí rovnice ?? do tvaru

x(h−1)^{T} L_{q}^{T} L_{q}x(h−1) = (Ax(h−2)+Bu(h−2))^{T} L_{q}^{T} L_{q}(Ax(h−2)+Bu(h−2)) , (4.24)

kde se vyskytuje u(t) pouze pro t = h − 2. Při minimalizaci podle u(h − 2) musíme zahrnout i tuto část, člen ve složeném maticovém zápisu tudíž nabyde tvaru

(u(h − 2)^{T} , x(h − 2)^{T}) ( \begin{matrix}B^{T} \sqrt{Q}^{T} & \sqrt{R}^{T} & L_{x}A \\ A^{T} \sqrt{Q}^{T} & 0 & L_{x}B \end{matrix} ) ( \begin{matrix}\sqrt{Q}B & \sqrt{Q}A \\ \sqrt{R} & 0 \\ L_{x}A & L_{x}B \end{matrix} ) ( \begin{matrix}u(h − 2) \\ x(h − 2) \end{matrix} ) .

(4.25)

Matici

M = ( \begin{matrix}\sqrt{Q}B & \sqrt{Q}A \\ \sqrt{R} & 0 \\ L_{x}A & L_{x}B \end{matrix} ) = ( \begin{matrix}M_{0} \\ L_{x}A L_{x}B \end{matrix} )  (4.26)

opět převedeme QR dekompozicí do horního trojůhelníkového tvaru a dostaneme vztah pro u(h − 2). Tento postup se analogicky aplikuje na každé u(t). Matice M_{0} je stále stjná, L_{x} použijeme z předchozího kroku minimalizace.

4.1.2.1 Implementace minimalizace

Minimaizace kvadratického kritéria je v simulaci prováděna metoduo mat L( const int horizont ) ve třídě QuadraticMinimalizator , které se jako parametry konstruktoru předávají matice A, B, L a Q. Pro numerické výpočty je použite knihovna IT++, která umožňuje jednoduché operace s maticemi a vektory syntakticky podobně jako v jazyku MATLAB. Jsou zde také implementovány jednoduché algoritmy, jako například pro naše účely potřebný QR rozklad. Níže je vložen zdrojový kód metody pro minimalizaci kritéria a získání hodnot řídících parametrů. Proměnné jsou v kódu značeny stejně jako v textu výše. Ty, které jsou v kódu použity navíc, jsou popsány v komentářích.

mat L( const i n t horizont ) {
i n t xdim = A. c o l s ( ) ; // Dimenze vektoru x
i n t udim = B. c o l s ( ) ; // Dimenze vektoru u
mat sqQ = s q r t (Q) ;  // Odmocninove matice
mat sqR = s q r t (R) ;

mat M0, M;
mat qrQ ;
mat L , Ls , Lx , Lu ;
// s e s t a v e n i matice M0
M0 = c o n c a t v e r t i c a l (
c o n c a t h o r i z o n t a l ( sqQ ∗ B,  sqQ ∗ A ) ,
c o n c a t h o r i z o n t a l ( sqR ,  z e r o s ( udim , xdim ) )

) ;

M = M0;
// hlavni cyklus
f o r ( i n t h = horizont ; h >= 0 ; h −−) {
qr (M, L ) ; // QR rozklad matice M
// rozklad matice L na do s l o z e k
Lu = L(0 , udim−1, 0 , udim −1);
Lx = L( udim , udim+xdim−1, udim , udim+xdim −1);
Ls = L(0 , udim−1, udim , udim+xdim −1);
// kompozice matice M
M = c o n c a t v e r t i c a l (
M0,
c o n c a t h o r i z o n t a l (Lx ∗ B, Lx ∗ A )

) ;

}

// navratova hodnota − vysledna matice L : u( t +1) = Lx( t )
return − inv (Lu) ∗ Ls ;
}

4.2 Simulace

Pro simulaci byl použit mikorsimulátor dopravy AIMSUN (Advanced Interactive Microscopic Simulator for Urban and Non-Urban Networks). 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ů. V této kapitole je popsána základní charakteristika mikrosimulátoru AIMSUN. Podrobnější informace lze nalézt například v [1].

AIMSUN potřebuje pro svůj běh simulační scénář skládající se z popisu dopravní sítě, plánů řízení dopravy, požadovaných dopravních data, a plánů hromadné dopravy a množinu simulačních parametrů definujících experiment. Popis dopravní sítě obsahuje geometrii sítě, popis křižovatek a rozmístění detektorů, Dopravní data se dají zadat dvěma způsoby: Pomocí matice opbsahující informace kolik jízd se uskuteční z uzlu i do uzlu j. Každému vozidlu je tedy přiřazena trasa. V fruhém případě se pro určitá místa zadají hustoty provozu a vozidla se rozmístí stochasticky podle požadovaných počtů a poměrů odbočení do dopravní sítě.

4.2.0.2 VGS API

VGS API je rozhraní napsané v jazyce C++, které rozšiřuje funkčnost mikrosimulátoru AIMSUN. Zjednodušuje simulaci reálné situace, kdy podle tabulek naměřených ručně nebo zaznamenaných údajů z dopravních detektorů generuje vozidla v průběhu simulace.

Druhým důležitým úkolem VGS API je shromažd’ovat data potřebná pro běh experimentu a jeho. 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. Zprostředkovává tak důležitá data o počtu zastavení vozidla, o jeho zpoždění, průměrné rychlosti, době jízdy atd. Tato data jsou dostupná v průběhu simulace i po skončení k následujícímu zpracování.

Důležitý údaj, které nám VGS API poskytuje, je délka fronty pro daný jízdní pruh. Fronta se podle dat z detektorů odhaduje velice obtížně, nebot’ ty vykazují zančnou chybovost, která u sledování průjezdů neni až tak zásadní, ale při použití na výpočet front by docházelo ke kumulaci této chyby a výsledky by byly prakticky nepoužitelné. Hlavní chyby detektorů spočívají v nerozpoznání mezery mezi vozidly a zpočtení dvou vozidel jako jedno, nebo zaznamenání jednoho vozidla dvěma detektory ve dvou jízdních pruzích zároveň.

4.2.1 Řadiče

Kvůli věrnějšímu napodobení skutečnosti, jsou použity k ovládání signálních skupin použity emulátory řadičů ELS3 firmy ELTODO. Ty to řadiče, strejně jako v reálné situaci kvůli bezpečnosti, mají pevně dané fáze a v nich definované průjezdnosti daných pruhů. Ovladatelné jsou pouze vnějí parametry, jako je délka cyklu, poměry časů fází a offset. V našenm případně budeme nastavovat pouze délku cyklu, po jakou se vystřídají všechny fáze. Offset a ani poměr fází, tedy i poměr doby zelených, se nemění.

4.2.2 Oblast simulace

Pro simulaci bylo použito schéma dvou křižovatek na ulici Řevnické. Následující schémata znázorňují křižovatky s označením 495 - Na Radosti a 601 - terminál BUS, jejich pruhy (VA, VB, VC, VD, VE, VF a VA, VAa, VB, VBa, VC, VD, VE, Se) a detektory, znázorněné zelenými obdélníky.

Obrázek 4.1: Křižovatka 601

Obrázek 4.2: Křižovatka 495

4.3 Popis algoritmu

Základ hlavní smyčky programu je postaven na knihovně BDM (Bayesian Decision Making), vyvýjena na ústavu teorie informace a automatizace. Knihovna obsahuje třídu Participant, od které je odvozena základní třída agenta BaseTrafficAgent. Ta má předdefinované metody, které jsou volány v každém cyklu simulace. Jsou to metody Adapt, sloužící k získání dat, Broadcast, ve které se posílají data sousedním agentům, Receive, kde se zprávy příjímají a zpracovávají a Act, metoda určená pro nastavení řídících parametrů, v našem případě délky cyklu.

Finální agent určený pro LQ řízení je odvozen od této t’rídy. V každém cyklu posílá ůdaje o délce front, zatížení detektorů a odbočovacích poměrec. Z těchto dat si poté podle rovnic 4.5 a 4.7 sestaví matici B. Matice A je jednotková a penalizační matice kvadratického kritéria Q a R jsou konstantně nastaveny podle významnosti dopravních pruhů. Tím jsou sestaveny vstupní parametry pro minimalizátor, který vypočte řídící matici L potřebnou k získání optimální hodnoty délky cyklu.

4.4 Možné vylepšení do budoucna

4.4.0.1 Model toku

V článku [11] se úbytek vozidel modeluje podle rovnice 3.4, kde je uvažován tok vozidel křižovatkou za jednotku času jako konstanta S, což je saturovaný tok. Tento vztah platí pouze když je příslušný pruh naplněn vozidly do té míry, že křižovatkou projede maximální možný počet vozidel. To však neplatí, pokud není pruh dostatečně vytížen, například pokud se zmenší délka fronty v nějaký časový okamžik na nulu. Pokud je vytížení menší je tok lineárně závislý na součtu fronty q(t)/T a počtu vstupujících vozidel i(t). Pro teoretickou hodnotu toku S tedy dostáváme vztah

S_{teor}(q(t) + i(t)) = \{ \begin{matrix}\frac{q(t)}{T} + i(t) & \frac{q(t)}{T} + i(t) <= S_{max} \\ S_{max} & \frac{q(t)}{T} + i(t) > S_{max} \end{matrix}  (4.27)

. tento vztah vyjadřuje to, že pokud je fronta plus přírůstrek vozidel ve vzorkovací periodě (q(t), i(t)T) menší než maximální počet vozidel, který je křižovatka za periodu T schopna propustit (T S_{max}), projedou všechna vozidla. Abychom se vyhnuli podmínce podle S_{max}, aproximuje se tento vztah funkcí

S_{exp}(q(t), i(t)) = S_{max} (1 − e^{− \frac{1}{Smax} (\frac{q(t)}{T} +i(t))})  (4.28)

, která splňuje podmínku

\frac{dS_{exp}}{d(q/T + i)} (0, 0) = 1  (4.29)

, tedy při malé frontě a hustotě provozu je přírůstek toku roven q/T + i, a podmínku

lim_{q/T +i→∞} S_{exp} = S_{max}  (4.30)

, tedy při velké frontě a hustotě provozu se tok blíží konstantě S_{max}. Pro malý časový interval můžeme tuto funkci dále zjednodušit na lineární vztah

S(q(t)) = σ(q(t)/T + i_{0})  (4.31)

, kde je i_{0} = i(0) a

σ = \frac{dS_{exp}}{d(q/T + i)} (q(0), i(0))  (4.32)

4.4.1 Odhdad odbočovacích poměrů

V ninější verzi se pracuje s konstantními odbočovacími poměry, které byly naměřeny v reálné siutaci a zadávají se pomocí konfiguračního souboru. Pro standartní simulace je tento způsob dostačující, do budoucna by však mohlo přinést zlepšení tyto koeficienty odhadovat v průběhu simulace.

Vhodnou metodou k odhadu odbočovacích poměrů by mohl být například Kalmanův filtr, nebo jiná metoda používající bayesovské učení popsané v kapitole 2.4.3 , kde by se nyní používaná konstantní hodnota zavedla jako apriorní pravděpodobnost.

Výsledky

Použitá metoda byla testována na mikrosimulátoru dopravy AIMSUN v oblasti Praha - Zličín na dvou scénářích s konstantní hustotou provozu a jednom scénáři reálným. Referenční výsledky byly získány testováním těchto scénářů na konstantní délce cyklu o hodnotě 80s, která je v modelové oblasti skutečně používána.

5.1 Scénář 1

První testovaný konstantní scénář má menší intenzitu provozu a při měření s různými konstantními délkami cyklu se ukazuje, že referenční hodnota 80s je více méně optimální. Jak ukazuje následující graf, algoritmus osciluje okolo těchto hodnot až na moment kolem padesáté minuty, kdy reaguje na prudké zvýšení front, jak ukazuje další graf.

KAPITOLA 5. VÝSLEDKY 36

Obrázek 5.1: Průběh délky cyklu Obrázek 5.2: Průběh součtu délek front

Tento nárůst front kolem padesáté minuty se projevil negativně na vývoji dopravy, jak ukazují následující dva grafy porovnávající počty zastavení a průměrnou dobu jízdy s referenční délkou cyklu 80s.

Obrázek 5.3: Počet zastavení

Obrázek 5.4: Průměrná doba jízdy

KAPITOLA 5. VÝSLEDKY 38

5.2 Scénář 2

Kapitola 6 Závěr

39

Literatura

[1] AIMSUN Getram v4.2 getting started - User’s manual. 2003.

[2] Anderson, M. J., B.D.O.: Optimal Control - Linear Quadratic Methods. Prentice Hall, Englewood Cliffs, NJ, 1990.

[3] Bellman, R.: Dynamic programming. Princeton University Press, 1957.

[4] Ferreira, E.; Subrahmanian, E.; Manstetten, D.: Intelligent agents in decentralized traffic control. Intelligent Transportation Systems, 2001.

[5] Gmytrasiewicz, P. J.; Durfee, E. H.: A rigorous, operational formalization of recursive modeling. First International Conference on Multiagent Systems, 1995.

[6] Nagy, I.; Nedoma, P.; Ettler, P.; aj.: O bayesovském učení. Automa, 2002.

[7] Ou, H.; Zhang, W.; Xu, X.: Urban traffic multi-agent system based on RMM and Bayesian learning. American Control Conference, 2002.

[8] P., P.; J., D.; Flídr: Modelling and Simultaneous Estimation of State and Parameters of Traffic System. Robotics, Automation and Control, 2008.

[9] Sutton, R. S.: Learning to predict by the methods of temporal didffrences. Machine Learning, 1988.

[10] Thorpe, T.: Vehicle traffic light controlusing sarsa. Master’s thesis, Department of Computer Science, Colorado State University, 1997.

[11] Vaya Dinopoulou, M. P., Christina Diakaki: Applications of the urban traffic control strategy TUC. European Journal of Operational Research, 2005.

[12] Watkins, C. J. C. H.: Leraning from Delayed Rewards. PhD thesis, King’s College, Cambridge, England, 1989.

LITERATURA 41 [13] Watkins, C. J. C. H.; Dayan, P.: Q-leraning. Machine Learning, 1992.

[14] Wiering, M.; Van Veenen, J.; Vreeken, J.; aj.: Intelligent traffic light control. European Research Consortium for Informatics and Mathematics, 2003.

[15] Wooldridge, M.: Multi Agent Systems. MIT Press, Březen 2005.

Příloha A Příloha 1

I