[1147] | 1 | \def \obr {05_AlgorithmDescription/fig/} |
---|
| 2 | |
---|
| 3 | \chapter{Popis implementace} |
---|
| 4 | |
---|
| 5 | |
---|
| 6 | \section{Třída Lane} |
---|
| 7 | Každá instance třídy Lane reprezentuje jeden dopravní pruh. |
---|
| 8 | Po inicializaci se do příslušných proměnných uloží textové |
---|
| 9 | řetězce, podle kterých se přiřazují k pruhu data z detektorů |
---|
| 10 | a AIMSUNu, jak je, pro naše účely důležitá, maximální délka |
---|
| 11 | fronty na dopravním pruhu za jednu simulační periodu. |
---|
| 12 | |
---|
| 13 | |
---|
| 14 | \section{Třída LaneHandler} |
---|
| 15 | Tato třída zprostředkovává přístup agentovi k ůdajům z jednotlivých pruhů. |
---|
| 16 | Stará se o zaznamenávání a statistické spracování dat z AIMSUNu. |
---|
| 17 | Také je zde implementován odhad čekací doby automobilu do průjezdu křižovatkou, |
---|
| 18 | což je údaj používaný v hodnotící délky cyklu funkci agenta. |
---|
| 19 | |
---|
| 20 | \subsection{Fronta} |
---|
| 21 | Agent předává třídě LaneHandler údaj o maximální délce fronty za vzorkovací periodu. |
---|
| 22 | Jedná se o největší počet automobilů v příslušném jízdním pruhu, jejichž rychlost reřesahuje |
---|
| 23 | určitou hodnotu. V našem konkrétním případě je tato mezní rychlost nastavena na 3,6 km/h. |
---|
| 24 | 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 |
---|
| 25 | se vzorkovací periodou. Uvažujme jízdní pruh s poměrem délky zelené 0,5. |
---|
| 26 | 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, |
---|
| 27 | kdy na příslušném semaforu naskočí zelená, bude v první vzorkovací periodě pruh průjezdný po dobu 45 sekund, ale |
---|
| 28 | v další nebude průjezdný vůbec a fronta se za stejné hustoty provozu zvětší. |
---|
| 29 | |
---|
| 30 | \subsection{Odhad fronty}\label{ss:odhad_fronty} |
---|
| 31 | K odhadu fronty je použito metody tzv. exponencionálního zapomínání. Metoda vychází z povoucího průměru |
---|
| 32 | Který je vhodný pro odhad nekonstantní hodnoty. Označíme si veličinu $\overline{q_i}$ jako plovoucí průměr |
---|
| 33 | 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 jako$q_i$. |
---|
| 34 | V kroce $i+1$ je hodnota hodnota plovoucího průměru přepřičytením poslední naměřené hodnoty rovna |
---|
| 35 | $$ |
---|
| 36 | \overline{q_i} = \frac{1}{n} \sum_{j=0}^{n-1} q_{i-j} . |
---|
| 37 | $$ |
---|
| 38 | |
---|
| 39 | Obsahuje tedy všech posledních $n$ naměřených hodnot. $\overline{q_{i+1}}$ se tedy rovná |
---|
| 40 | $$ |
---|
| 41 | \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}. |
---|
| 42 | $$ |
---|
| 43 | 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 |
---|
| 44 | jeho hodnotu podělenou délkou průměrovacího okna $n$. Výpočet přejde na tvar |
---|
| 45 | $$ |
---|
| 46 | \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}). |
---|
| 47 | $$ |
---|
| 48 | $\frac{1}{n} (q_{i+1} - \overline{q_i}$ je vlastně přírustek v kroku $i+1$, označme si ho jako $\Delta q_{i+1}$, |
---|
| 49 | a faktor $1/n$ můžeme chápat jako jeho váhu $w$. Po dosazení dostáváme jednoduchý tvar |
---|
| 50 | $$ |
---|
| 51 | \overline{q_{i+1}} = \overline{q_i} + w \Delta q_{i+1}. |
---|
| 52 | $$ |
---|
| 53 | 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, |
---|
| 54 | má však zanedbatelnou váhu $\left(\frac{n-1}{n}\right)^i$. Jedná se o jaksi zjednodušenou verzi Kalmanova filtru. |
---|
| 55 | Grafy \ref{fig:q1} a \ref{fig:q2} znázorňují rozdíl mezi okamžitou a filtrovanou délkou fronty při váze $w = 0.2$. |
---|
| 56 | Graf \ref{fig:q1} pro konstantní délku cyklu 80 sekund, graf \ref{fig:q2} pro délku cyklu peridicky se měnící od 40 |
---|
| 57 | do 120 sekund. |
---|
| 58 | |
---|
| 59 | \begin{figure}[H] |
---|
| 60 | \begin{center} |
---|
| 61 | {\includegraphics[width=10cm]{\obr q_scen_01_1h_tc80.eps}} |
---|
| 62 | \caption{Porovnání okamžité a filtrované délky fronty \newline délka cyklu 80 s}\label{fig:q1} |
---|
| 63 | \end{center} |
---|
| 64 | \end{figure} |
---|
| 65 | |
---|
| 66 | \begin{figure}[H] |
---|
| 67 | \begin{center} |
---|
| 68 | {\includegraphics[width=10cm]{\obr q_scen_01_1h_tc40-120.eps}} |
---|
| 69 | \caption{Porovnání okamžité a filtrované délky fronty \newline délka cyklu 40-120 s}\label{fig:q2} |
---|
| 70 | \end{center} |
---|
| 71 | \end{figure} |
---|
| 72 | |
---|
| 73 | |
---|
| 74 | \subsection{Odhad čekací doby}\label{ss:odhad_cekaci_doby} |
---|
| 75 | Představme si, že ke přižovatce přijíždí auto $a_n$ a mezi tímto autem a křižovatkou je |
---|
| 76 | $n$ dalšíchch aut. Budeme chtít odhadnout střední hodnotu času do průjezdu auta $a_n$ |
---|
| 77 | 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 |
---|
| 78 | v době, kdy je signální skupina ve stavu zelená, projede okamžitě. Pokud ne, čeká do konce fáze. |
---|
| 79 | 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$. |
---|
| 80 | Předpopkládejme rovnoměrné rozdělení, hustota pravděpodobnosti příjezdu auta v čase $t$ je tedy |
---|
| 81 | $$ |
---|
| 82 | \omega(t) = |
---|
| 83 | \left\{ |
---|
| 84 | \begin{array}{r@{\quad}c} |
---|
| 85 | \frac{1}{T_c} , & 0 < t < T_c \\ |
---|
| 86 | 0 , & jinak \\ |
---|
| 87 | \end{array} |
---|
| 88 | \right.. |
---|
| 89 | $$ |
---|
| 90 | Střední hodnotu $t_{w0}$ tedy spočteme jako |
---|
| 91 | $$ |
---|
| 92 | <t_{w0}> = \int_{0}^{T_c} \omega(t) t_{w0}(t) dt = |
---|
| 93 | \int_{0}^{T_c(1-r_g)} \frac{1}{T_c} t dt + \int_{T_c(1-r_g)}^{T_c} \frac{1}{T_c} 0 dt = |
---|
| 94 | \frac{1}{T_c} \int_{0}^{T_c(1-r_g)} t dt = \frac{1}{2}T_c(1-r_g)^2 |
---|
| 95 | $$ |
---|
| 96 | Výraz $r_g T_c$ představuje jakousi délku časového okna, kdy auto projede bez čekání. |
---|
| 97 | Pokud chceme zjistit střední hodnotu času průjezdu libovolného auta $<t_{wn}>$, musíme |
---|
| 98 | 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 |
---|
| 99 | je schopen propustit maximální počet aut za sekundu. Tento ůdaj se nazývá saturovaný tok, |
---|
| 100 | budeme ho značit $s_s$, a bere se jako konstanta rovnající se $0.5 auto/s$. Pro $n$-té |
---|
| 101 | auto se tedy okno nulového čekání zkrátí na $r_g T_c - \frac{n}{s_s}$ a střední hodnota doby |
---|
| 102 | průjezdu křižovatkou se změní na |
---|
| 103 | $$ |
---|
| 104 | <t_{wn}> = \frac{1}{T_c} \int_{0}^{T_c(1-r_g) + \frac{n}{s_s}} t dt = \frac{1}{2T_c} \left(T_c(1-r_g) + \frac{n}{s_s} \right)^2 . |
---|
| 105 | $$ |
---|
| 106 | To však platí pouze když stihnou všechna auta křižovatkou projet, tedy pokud |
---|
| 107 | $$ |
---|
| 108 | r_g T_c < \frac{n}{s_s}. |
---|
| 109 | $$ |
---|
| 110 | 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ž |
---|
| 111 | 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á |
---|
| 112 | dolní celé části z podílu čekajících aut a počtu aut, které projedou na zelenou za jeden cyklus, tedy |
---|
| 113 | $$ |
---|
| 114 | \left\lfloor \frac{n}{r_g T_c s_s} \right\rfloor, |
---|
| 115 | $$ |
---|
| 116 | a do horní meze intrgrálu potom přispěje pouze počet aut, který zbyl po odečtení těch, které zcela pokryla |
---|
| 117 | fáze se zeleným světlem. |
---|
| 118 | Po zahrnutí tohoto předpokladu se výraz pro $<t_{wn}>$ změní na |
---|
| 119 | $$ |
---|
| 120 | <t_{wn}> = \left\lfloor \frac{n}{r_g T_c s_s} \right\rfloor T_c + \frac{1}{2T_c} \left(T_c(1-r_g) + \frac{n - \left\lfloor \frac{n}{r_g T_c s_s} \right\rfloor r_g T_c s_s}{s_s} \right)^2 . |
---|
| 121 | $$ |
---|
| 122 | |
---|
| 123 | 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 |
---|
| 124 | 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 |
---|
| 125 | si zavedeme malý kladný parametr $\delta$, o který snížíme dobu trvání průjezdnosti křižovatky. |
---|
| 126 | Výraz pro dobu průjezdnosti se potom změní na |
---|
| 127 | $$ |
---|
| 128 | (r_g T_c - \delta) |
---|
| 129 | $$ |
---|
| 130 | a povzorec počet cyklů, po jejichž celý čas stráví vozidlo čekáním je roven |
---|
| 131 | $$ |
---|
| 132 | \left\lfloor \frac{n}{(r_g T_c - \delta) s_s} \right\rfloor. |
---|
| 133 | $$ |
---|
| 134 | Konečná podoba výrazu pro střední hodnotu $t_{wn}$ je tedy |
---|
| 135 | $$ |
---|
| 136 | <t_{wn}> = \left\lfloor \frac{n}{(r_g T_c - \delta) s_s} \right\rfloor T_c + \frac{1}{2T_c} \left( T_c(1-r_g) + \frac{n - \left\lfloor \frac{n}{(r_g T_c - \delta) s_s} \right\rfloor r_g T_c s_s}{s_s} \right)^2 . |
---|
| 137 | $$ |
---|
| 138 | |
---|
| 139 | Tento výpočet je implementován jako metoda \texttt{getEcarWT}, pijímající dva paramentry. Délku cyklu $tc$ a pořadí auta $n$. |
---|
| 140 | \lstset{language=C++,basicstyle=\footnotesize} |
---|
| 141 | \begin{lstlisting} |
---|
| 142 | |
---|
| 143 | double getEcarWT ( const double tc, const int n ) { |
---|
| 144 | //gr - pomer casu zelene - atribut tridy |
---|
| 145 | //ss - saturovany tok - konstanta |
---|
| 146 | // pocet aut, ktera projedou za zeleneou |
---|
| 147 | double cpg = tc * gr * ss; |
---|
| 148 | // number of waiting cycles |
---|
| 149 | double wc = floor( n / cpg ); |
---|
| 150 | double ET_last_cycle = ( 1/ (2*tc) ) |
---|
| 151 | * ( tc*(1-gr) + (n-wc*cpg)/ss ) |
---|
| 152 | * ( tc*(1-gr) + (n-wc*cpg)/ss ); |
---|
| 153 | double ET = wc*tc + ET_last_cycle; |
---|
| 154 | return ET; |
---|
| 155 | } |
---|
| 156 | \end{lstlisting} |
---|
| 157 | |
---|
| 158 | Pro hodnocení výhodnosti se používá funkce $getWT$, která sčítá všechny čekací časy pro auta ve frontě |
---|
| 159 | \begin{lstlisting} |
---|
| 160 | double getWT ( const double tc ) { |
---|
| 161 | double sumEWT = 0; |
---|
| 162 | int n = getAverageQueueLength(); |
---|
| 163 | for ( int i = 0; i <= n; i ++ ) { |
---|
| 164 | sumEWT += getEcarWT( tc, i ); |
---|
| 165 | } |
---|
| 166 | return sumEWT; |
---|
| 167 | } |
---|
| 168 | |
---|
| 169 | \end{lstlisting} |
---|
| 170 | |
---|
| 171 | \subsection{Odhad parametru $\delta$} |
---|
| 172 | Delta vyjadřuje korekční parametr doby průjezdnosti křižovatky. |
---|
| 173 | Jak jsme již ukázali v kapitole \ref{ss:odhad_cekaci_doby}, počet vozidel, které projedou křižovatkou |
---|
| 174 | za jeden cyklus řadiče je |
---|
| 175 | $$ |
---|
| 176 | (r_g T_c - \delta) s_s. |
---|
| 177 | $$ |
---|
| 178 | To znamená že pokud je fronta větší, než $(r_g T_c - \delta) s_s$, mměla by se její velikost za dobu $T_c$ |
---|
| 179 | změnit o |
---|
| 180 | $$ |
---|
| 181 | \Delta q_{T_c} = n_{Tc} - (r_g T_c - \delta) s_s, |
---|
| 182 | $$ |
---|
| 183 | |
---|
| 184 | kde $n_{Tc}$ je počet vozidel, přijíždějících na křižovatku za dobu $T_c$. |
---|
| 185 | Tento údaj je vlastně výstup z detektorů, který je nám však dostupný pouze |
---|
| 186 | jednou za simulační cyklus, trvající 90 sekund. Protože pracujeme s filtrovanými hodnotami front, |
---|
| 187 | nedojde k velké chybě, pokud výraz přepočítáme na 90 sekund do podoby |
---|
| 188 | $$ |
---|
| 189 | \Delta q_{90} = n_{90} - \frac{90}{T_c}(r_g T_c - \delta) s_s = n_{90} - 90 r_g s_s - \frac{90 s_s}{T_c} \delta, |
---|
| 190 | $$ |
---|
| 191 | z čehož si parametr $\delta$ vyjádříme jako |
---|
| 192 | $$ |
---|
| 193 | \delta = \frac{T_c}{90 s_s} \left( n_{90} - \Delta q_{90} \right) - r_g. |
---|
| 194 | $$ |
---|
| 195 | Jak údaje o projíždejících vozidlech za simulační cyklus $n_{90}$, tak parametry $\delta$, jsou filtrovány |
---|
| 196 | způsobem, použitým na odhad délky fronty a popsaným v kapitole \ref{ss:odhad_fronty}. |
---|
| 197 | \section{Třída agenta} |
---|
| 198 | |
---|
| 199 | |
---|
| 200 | \section{Hlavní smyčka} |
---|
| 201 | Hlavní smyčka programu se stará o synchronizaci všech potřebných parametrů a provádění iterací. |
---|
| 202 | Před započetím opakování kroku simulace nastaví podle konfiguračního souboru počáteční parametry mikrosimulátoru dopravy AIMSUN, |
---|
| 203 | jako jsou délka cyklu a fází řadičů, inicializuje jednotlivé agenty a zavolá jejich metody fromSettings a Validate. |
---|
| 204 | Také inicializuje instanci třídy Logger pro logování a AIMSUNDs potřebnou pro výměnu dat s AIMSUNem. |
---|
| 205 | |
---|
| 206 | \subsection{Krok simulace} |
---|
| 207 | Délka kroku simulace je pevně nastavena na 90 sekund shodně s periodou sběru dat z AIMSUNu. |
---|
| 208 | V jednom kroku se nejprve načtou data z AIMSUNu do vektoru glob\_dt, který se následně předá |
---|
| 209 | každému z agentů jako paramentr jejich metody adapt. Následně zprostředkuje komunikaci mezi |
---|
| 210 | agenty tak, že naplní frontu zpráv voláním metod broadcast jednotlivých agentů. Z této fronty |
---|
| 211 | postupně poté odebírá zprávy, které předává agentům parametrem jejich metody receive, dokud není |
---|
| 212 | fronta prázdná. Tento cyklus se opakuje, dokud agenti komunikují, nebo dokud se nedosáhne předem stanoveného |
---|
| 213 | počtu opakování. Po ukončení komunikace naplní vektor výstupů glob\_ut voláním metod act hodotami parametrů |
---|
| 214 | pro AIMSUN, vše zaloguje a vyčká do dalšího kroku. |
---|
| 215 | |
---|