root/applications/doprava/texty/delka_cyklu/05_AlgorithmDescription/AlgorithmDescription.tex.old @ 1147

\def \obr {05_AlgorithmDescription/fig/}

\chapter{Popis implementace}


\section{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.


\section{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.

\subsection{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ší.

\subsection{Odhad fronty}\label{ss: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 jako$q_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} \sum_{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 $\Delta 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 \Delta 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 $\left(\frac{n-1}{n}\right)^i$. Jedná se o jaksi zjednodušenou verzi Kalmanova filtru.
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$.
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
do 120 sekund.

\begin{figure}[H]
\begin{center}
    {\includegraphics[width=10cm]{\obr q_scen_01_1h_tc80.eps}}
    \caption{Porovnání okamžité a filtrované délky fronty \newline délka cyklu 80 s}\label{fig:q1}
\end{center}
\end{figure}

\begin{figure}[H]
\begin{center}
    {\includegraphics[width=10cm]{\obr q_scen_01_1h_tc40-120.eps}}
    \caption{Porovnání okamžité a filtrované délky fronty \newline délka cyklu 40-120 s}\label{fig:q2}
\end{center}
\end{figure}


\subsection{Odhad čekací doby}\label{ss:odhad_cekaci_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
$$ 
\omega(t) = 
\left\{  
\begin{array}{r@{\quad}c}
 \frac{1}{T_c} , & 0 < t < T_c   \\
 0 , & jinak \\
\end{array}
\right..
$$
Střední hodnotu $t_{w0}$ tedy spočteme jako
$$
<t_{w0}> = \int_{0}^{T_c} \omega(t) t_{w0}(t) dt = 
\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 = 
\frac{1}{T_c} \int_{0}^{T_c(1-r_g)} t dt = \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.5 auto/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} \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 .
$$
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
$$
\left\lfloor \frac{n}{r_g T_c s_s} \right\rfloor,
$$
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}> = \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 .
$$

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 $\delta$, 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 - \delta)
$$
a povzorec počet cyklů, po jejichž celý čas stráví vozidlo čekáním je roven
$$
\left\lfloor \frac{n}{(r_g T_c - \delta) s_s} \right\rfloor.
$$
Konečná podoba výrazu pro střední hodnotu $t_{wn}$ je tedy 
$$
<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 .
$$

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$.
\lstset{language=C++,basicstyle=\footnotesize}
\begin{lstlisting}
 
double getEcarWT ( const double tc, const int n ) {
        //gr - pomer casu zelene - atribut tridy
        //ss - saturovany tok - konstanta 
        // pocet aut, ktera projedou za zeleneou
        double cpg = tc * gr * ss;
        // number of waiting cycles             
        double wc = floor( n / cpg ); 
        double ET_last_cycle = ( 1/ (2*tc) ) 
                * ( tc*(1-gr) + (n-wc*cpg)/ss )
                * ( tc*(1-gr) + (n-wc*cpg)/ss );
        double ET = wc*tc + ET_last_cycle;
        return ET;
}
\end{lstlisting}

Pro hodnocení výhodnosti se používá funkce $getWT$, která sčítá všechny čekací časy pro auta ve frontě
\begin{lstlisting}
double getWT ( const double tc ) {
        double sumEWT = 0;
        int n = getAverageQueueLength();
        for ( int i = 0; i <= n; i ++ ) {
                sumEWT += getEcarWT( tc, i );
        }
        return sumEWT;
}

\end{lstlisting}

\subsection{Odhad parametru $\delta$}
Delta vyjadřuje korekční parametr doby průjezdnosti křižovatky.
Jak jsme již ukázali v kapitole \ref{ss:odhad_cekaci_doby}, počet vozidel, které projedou křižovatkou
za jeden cyklus řadiče je
$$
(r_g T_c - \delta) s_s.
$$
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$
změnit o 
$$
\Delta q_{T_c} = n_{Tc} - (r_g T_c - \delta) s_s,
$$

kde $n_{Tc}$ 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
$$
\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,
$$
z čehož si parametr $\delta$ vyjádříme jako
$$
\delta = \frac{T_c}{90 s_s} \left( n_{90} - \Delta q_{90} \right) - r_g.
$$
Jak údaje o projíždejících vozidlech za simulační cyklus $n_{90}$, tak parametry $\delta$, jsou filtrovány
způsobem, použitým na odhad délky fronty a popsaným v kapitole \ref{ss:odhad_fronty}.
\section{Třída agenta}


\section{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.

\subsection{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.