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

\def \obr {05_AlgorithmDescription/fig/}
\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numbersep=0pt, tabsize=4, breaklines, breakautoindent=false, captionpos=b}
\chapter{Popis implementace}



\section{Použité knihovny}

\subsection{IT++}
IT++ je knihovna jazyka C++ zahrnující třídy pro matematické výpočty a komunikaci.
Umožňuje práci s vektory a maticemi podobným způsobem jako v nástroji MATLAB.
Použity jsou třídy \texttt{vec} a \texttt{Array}.


\subsubsection{Třída vec}
Třída \texttt{vec} reprezentuje vektor hodnot číselného typu \texttt{double}.
Přetížením operátorů kulatých a hranatých závorek a operátoru \texttt{=} umožňuje jednoduchou inicializaci 
vektoru pomocí textového řetězce a zjednodušuje přístup k jednotlivým hodnotám.
Kód
\begin{lstlisting}
  vec a = "0.1 0.2 0.3";
  cout << a(0) << endl;
  cout << a[1] << endl;
\end{lstlisting}
inicializuje vektor o dimenzi 3 s hodnotami 0,1, 0,2 a 0,3 a poté
vypíše první a druhý prvek vektoru.

\subsubsection{Třída Array}
Tato šablonová třída umožňuje pracovat s polem o proměnných předem daného libovolného typu.
Rozměr pole se může v průběhu programu měnit.


\subsection{BDM}
Knihovna BDM (Bayesian Decision Making) je navržena pro programy používající
Bayesovu statistiku. Zde jsou použity hlavně třídy \texttt{Datalink}, \texttt{RV}, \texttt{UI} a \texttt{Setting}
sloužící pro komunikaci s mikrosimulátorem AIMSUN, načítání hodnot z konfiguračních souborů a komunikaci mezi agenty.
\\
\\
V knihovně BDM je také definována třída \texttt{Participant}, implementující metody pro komunikaci
, od které je odvozena třída našeho agenta.


\subsubsection{Třída RV}
Třída \texttt{RV} implementuje pole popisků k vektorům třídy IT++.
K přístupu k jednotlivým slouží přetížený operátor závorky \texttt{(int index)}.
K určení veličiny uložené ve vektoru se používají metody
\begin{description}
 \item [name] jméno veličiny uložené v příslušném vektoru
 \item [length] rozměr RV vektoru
 \item [size(i)] rozměr veličiny, kterou značí popisek na pozici \texttt{i}
\end{description}

\subsubsection{Třídy UI a Setting}
UI a Setting slouží mimo jiné k načtení vybraných dat z konfiguračních souborů.
Kód
\begin{lstlisting}
    UI::get(inputs,set,"inputs",UI::compulsory);
\end{lstlisting}
zapíše na adresu proměnné \texttt{inputs} hodnotu v objektu \texttt{set} třídy \texttt{Setting},
označenou jako \texttt{\"inputs\"}. Objekt \texttt{set} reprezentuje načtený konfigurační soubor.
\texttt{UI::compulsory} značí, že daná hodnota musí být zadána.



\subsubsection{Třída Datalink}
Tato třída definuje spojení mezi dvěma vektory, mezi kterými zprostředkovává spojení
pomocí metody \texttt{filldown}.
\\
\\
Následující kód popisuje vytvoření dvou vektorů \texttt{from} a \texttt{to},
popsaných \texttt{RV} vektory \texttt{rv\_from} a \texttt{rv\_to}, a zkopání odpovídajících
údajů z \texttt{from} do \texttt{to} pomocí třídy \texttt{Datalink}. Výsledkem je, že vektor
\texttt{to} bude obsahovat hodnoty 1 a 2.

\begin{lstlisting}
  RV a = RV ( "{ a }");
  RV b = RV ( "{ b }" );
  RV c = RV ( "{ c }" );

  RV rv_to = a;
  rv_to.add ( b );

  RV rv_from = rv_to;
  rv_from.to ( c );

  datalink dl ( rv_to, rv_from );
  vec from ( "1 2 3" );
  vec to = dl.pushdown ( total );
\end{lstlisting}





\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, jako je na příklad 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é zpracová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 nepř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. exponenciálního zapomínání. Metoda vychází z plovoucí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 kroku $i$, kam budeme ukládat posledních $n$ měření. Označme si velikost fronty naměřenou v $i$-tém kroku jako$q_i$.
V kroku $i+1$ je hodnota hodnota plovoucího průměru před přičtení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řírůstek 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 kroku 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 periodicky 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}


V reálném případě je potřeba vypočítat délku fronty podle záznamů z detektorů.
Prostý výpočet délky fronty například jako rozdíl počtu vozidel, která odjela a která přijela však není možný.
V důsledku problémů popsaných v \ref{sss:zpracovani_dat}. Výpočet délky fronty není předmětem zkoumání této práce.
Podrobnější pojednání o tomto problému lze najít například v \cite{pecherkova}.
\\
\\
Protože časté přenastavování délky cyklu působí řadičům problémy, přenastavuje se tento parametr jednou za časový
úsek, ktrý je několikanásobně delší než 90 sekund. Je tedy nutné modelovat časový průběh fronty. Při rozšiřování testovacího
prostředí tento model ovlivní i údaj o počtu vozidel, které přijedou ze sousední křižovatky. Tento údaj závisí na délce cyklu
a není agentovy dostupný přímo. Bude tedy nutné rozšířit komunikaci agentů, popsanou v \ref{ss:komunikace}, o tento údaj.


\subsection{Odhad čekací doby}\label{ss:odhad_cekaci_doby}
Jednou z nejdůležitějších částí logiky, implementovaná v třídě \texttt{LaneHandler} je
odhad čekací doby vozidel stojících v, nebo přijíždějících do příslušného jízdního pruhu.
Tento odhad se používá při výběru a ohodnocení délky cyklu.
\\
\\
Odahad se provádí zjednodušenou mikrosimulací po čas \texttt{T}.
Do proměnné \texttt{q} se uloží aktuální hodnota fronty. 
Simulace začíná v čase \texttt{t = 0}. V každém kroku simulace
se zvětší fronta o hustotu provozu (počt aut za sekundu), odhadovanou z údajů z detektorů, a pokud se čas nachází
ve průjezdné fázi, zmenší se o konstantu, nazývanou saturovaný tok, která udává maximální počet aut, které projedou
křižovatkou. K čekací době vozidel, uložené v proměnné \texttt{wt}, se potom přičte délka zbývající fronty a čas 
\texttt{t} se zvětší o jednu sekundu.
\\
\\
Odhad probíhá ve dvou fázích, realizovaných cykly typu \texttt{for}. V první běží čas do největší části \texttt{T},
soudělné s \texttt{tc}, v druhé po zbytek \texttt{T}. níže uvádím popis všech proměnných.
\begin{description}
 \item[tc] délka cyklu, pro kterou je odhad prováděn (parametr funkce)
 \item[T] doba odhadu
 \item[ro] hustota provozu odhadovaná z dat z detektorů 
 \item[cars\_in\_avg] filtrovaná data z detektorů (atribut třídy)
 \item[queue\_avg] filtrovaná naměřená délka fronty (atribut třídy)
 \item[q] délka fronty v průběhu odhadu
 \item[wt] součet čekacích časů
 \item[green\_time\_ratio] poměr délky zelené k délce cyklu (atribut třídy)
 \item[gt] doba, kdy je křižovatka pro pruh průjezdná
 \item[tc\_rest] čas v daném cyklu
 \item[tc\_last] zbytek odhadovací periody
 \item[gt\_last] délka zelené ve zbytku odhadovací periody
 \item[delta] korekční parametr vyjadřuje zkrácení doby průjezdnosti vlivem pomalých rozjezdů a podpbně
\end{description}
Odhad je implementován v metodě \texttt{getWT}:

\begin{lstlisting}
        double getWT ( int tc ) {
                const int T = 450; // 5 scyklů
                double ro = cars_in_avg/90;
                double q = queue_avg;
                double wt = 0;
                double gt = tc*green_time_ratio - delta;
                int t_rest;
                int tc_last = T % tc;
                double gt_last = tc_last*green_time_ratio;
                for ( int t = 0; t < (T-tc_last); t++ ) {
                        t_rest = t%tc;
                        // zelena
                        if ((tc-gt)/2<=t_rest&&t_rest<(tc+gt)/2)
                                q -= saturated_stream;
                        if ( q < 0)
                                q = 0;
                        wt += q;                        
                        q += ro;                                
                }               
                // zbytek
                for ( int t = 0; t < tc_last; t++ ) {
                        // zelena
                        if ((tc_last-gt_last)/2<=t&&t<(tc_last+gt_last)/2 )
                                q -= saturated_stream;
                        if ( q < 0)
                                q = 0;
                        wt += q;                        
                        q += ro;
                }
                return wt;
        }
\end{lstlisting}



\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áze řadičů, inicializuje jednotlivé agenty a zavolá jejich metody \texttt{fromSettings} a \texttt{Validate}.

\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 \texttt{glob\_dt}, který se následně předá 
každému z agentů jako parametr jejich metody \texttt{adapt}. Následně se zprostředkuje komunikace mezi
agenty tak, že se naplní fronta zpráv voláním metody \texttt{broadcast} jednotlivých agentů. Z této fronty
se postupně odebírají zprávy, které se předávají agentům parametrem jejich metody \texttt{receive}
Po ukončení komunikace naplní vektor výstupů \texttt{glob\_ut} voláním metod \texttt{act} hodotami parametrů
pro AIMSUN, předá se mu a vyčká se do dalšího kroku.

\section{Třída agenta}
Třída \texttt{TrafficAgentCycleTime} je odvozena od obecného návrhu agenta \texttt{BaseTrafficAgent}.
Jsou v ní implementovány metody pro načtení dat, komunikaci a nastavení délky cyklu za účelem řízení
jedné konkrétní křižovatky.

\subsection{Stručný popis algoritmu}
Cíl algoritmu je zlepšit dopravní situaci nastavením délky cyklu řadiče na takovou
hodnotu, při níž bude celková čekací doba všech vozidel minimální.
Nejprve agent odhadne délku cyklu, která je ideální pro něj, poté vyšle zprávu, zda je tato hodnota
vyšší nebo nižší než aktuální. Pokud je nadpoloviční většina agentů pro změnu stejným směrem,
pokouší se najít hodnotu ideální pro všechny.

\subsection{Výpočetní metody}

\subsubsection{Metoda getWT}

Tato metoda vrací součet čekacích dob, sečtený přes všechny dopravní pruhy pro danou délku cyklu předanou parametrem \texttt{tc}.
V cyklu projde instance tříd \texttt{LAneHandler}, na které má uloženy ukazatele v proměnné \texttt{lanehs} typu
\texttt{Array<LaneHandler*>}. Pole se inicializuje v metodě \texttt{validate} předka \texttt{BaseTrafficAgent}.

\subsubsection{Metoda findIdealTc}\label{sss:ideal_tc}
Pro určení, zda vznést návrh na zvýšení či snížení délky cyklu, slouží metoda \texttt{findIdealTc}.
Ta zjišťuje čekací doby pro všechny možnosti rozsahu od minimální do maximální hodnoty, určené atributy
\texttt{minTc} a \texttt{maxTc}. Vrátí takovou délku cyklu, pro kterou je čekací doba nejmenší.
\\
\\
Princip použití součtu čekacích dob automaticky upřednostňuje dopravní pruhy s větší
vytížeností, což je žádoucí. Ostatní pruhy však zcela nepotlačuje. Tímto způsobem by se mělo
dosáhnout optimální hodnoty pro celou křižovatku.

\subsection{Přepsané metody předka}
Hlavní smyčka programu automaticky volá v každém cyklu metody určené
k načtení dat, komunikaci a nastavení dalšího řízení.



\subsubsection{Metoda validate}
K předání požadovaných hodnot parametrů v průběhu simulace slouží vektor \texttt{actions}.
Významy těchto hodnot vysvětluje \texttt{rv\_actions} třídy \texttt{RV}. V metodě \texttt{validate},
která se volá na začátku simulace, přidáme do \texttt{rv\_actions} hodnotu \texttt{Tc}. Tím
vlastně sdělíme AIMSUNu, že budeme přenastavovat délku cyklu. Protože délka jednotlivých fází se nepřenastavuje automaticky,
přidáme do \texttt{rv\_actions} také označení těchto fází. V praxi je tento postup realizován kódem
\begin{lstlisting}
  rv_action = RV("Tc",1);
  rv_action.add( RV(stage_names, ones_i(stage_names.length())));
\end{lstlisting}
kde je v proměnné \texttt{stage\_names} uložen seznam fází.
\\
\\
Následující metody se volají v každém cyklu simulace.



\subsubsection{Metoda adapt}
Na začátku každého simulačního cyklu se jako první volá u všech agentů metoda \texttt{adapt}.
V parametru se jí předá adresa vektoru výstupních údajů simulace \texttt{glob\_dt}, k jejichž zpracování je metoda určena.
Zde se předávají údaje z detektorů a délky front instancím třídy \texttt{LaneHandler} a poté se volá jejich metoda
\texttt{countAvgs}, která počítá filtrované hodnoty způsobem popsaným v sekci \ref{ss:odhad_fronty}.


\subsubsection{Metoda receive a broadcast} \label{ss:komunikace}
Po načtení a zpracování dat začíná komunikace. Ta je realizována metodami
\texttt{broadcas} a \texttt{receive}, které se volají střídavě. Přesněji řečeno,
hlavni smyčka nejprve volá metody \texttt{receive} každého agenta tak dlouho, dokud nevyprázdní frontu zpráv.
Ta je reprezentována polem proměnných typu \texttt{Setting}, které mají nastaveny čtyři parametry:

\begin{description}
 \item [from] určuje od koho zpráva přichází
 \item [to] má hodnotu jména agenta, pro kterého je zpráva určena
 \item [what] obsahuje co posíláme
 \item [value] obsahuje hodnotu spojenou s tím co posíláme
\end{description}

Každý agent má v atributu \texttt{name} uloženo jméno křižovatky, kterou ovládá.
Toto jméno je uloženo v konfiguračním souboru a odpovídá označením ze sekce \ref{ss:oblast_simulace}.
Pokud je jméno agenta stejné jako parametr zprávy \texttt{to}, vyjme se zpráva z fronty a předá se 
metodě \texttt{receive}.V momentě, kdy je fronta prázdná, zavolají se metody \texttt{broadcast} všech agentů.
Metoda \texttt{broadcast} opět plní frontu zprávami, které chce agent vyslat. Po jejím ukončení se opět volá \texttt{receive}.
Střídavé volání těchto dvou metod probíhá, dokud \texttt{broadcast} produkuje nějaké zprávy.
\\
\\
V našem případě probíhá odesílání ve dvou krocích. V obou se posílají zprávy všem ostatním agentům.
Nejprve agent sdělí, jestli chce délku cyklu zvýšit, snížit, nebo ponechat stejnou.
Pokud je pro zvýšení více než polovina agentů, začíná druhá fáze.
V té každý agent pošle všechny délky cyklu v předem daném rozsahu a k nim očekávané zisky.
Rozsah je od minimální do stávající při odhlasování snížení a od stávající do maximální při zvýšení.
Zisk se počítá jako rozdíl čekací doby při navrhované a stávající délce cyklu pomocí metody popsané v \ref{ss:odhad_cekaci_doby}.
Odeslání těchto zpráv je realizováno kódem
\begin{lstlisting}
  int broadcast_width = (max_tc - min_tc) + 1;

  for ( int i = 0; i < broadcast_width; i++ ) {
    int time_cycle = min_tc + i*stepTc;
    double profit = getProfit(time_cycle);
    
    // send tc
    stringstream time_cycle_stream;
    time_cycle_stream << "tc_" << (i);
    send2allNeighbours( set, time_cycle_stream.str(), time_cycle);

    // send profit
    stringstream profit_stream;
    profit_stream << "profit_" << (i);
    send2allNeighbours( set, profit_stream.str(), profit );
  }
\end{lstlisting}

Agent tedy vygeneruje pro každou hodnotu délky cyklu index, podle kterého se k ní dá přiřadit hodnota zisku.
V metodě \texttt{receive} se podle tohoto indexu sčítají zisky do pole \texttt{received\_profit\_sum}.



\subsubsection{Metoda act}\label{sss:metoda_act}
Pokud se agenti dohodly na změně délky cyklu, probíhá její přenastavení v metodě \texttt{act}.
Nejprve se projde pole \texttt{received\_profit\_sum} a vybere se z něj maximum.
Poté se podle indexu maximálního zisku určí ideální délka fronty.
\\
\\
Měření ukázala, že časté změny cyklu působí emulátorům řadičů problémy.
Proto se ideální hodnota průměruje plovoucím průměrem a nastavuje se jednou za 5 cyklů.