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 | |
---|