\chapter{Algoritmus řízení}
\section{Návrh algoritmu}
\label{sec:navrh}
Úkolem v~této práci bylo navrhnout algoritmus vyjednávání mezi jednotlivými křižovatkami tak, aby koordinovanou změnou svých offsetů vytvořili zelenou vlnu a~tedy aby projelo co nejvíce vozidel bez zbytečného zastavování. 

Jedním z nosných prvků návrhu je funkce, která ohodnotí konkrétní nastavení offsetu a umožní tak tedy porovnat různé jeho hodnoty a vybrat tu možná nejlepší. Za tuto míru kvality byl zvolen odhad počtu aut, která projedou křižovatkou bez zastavení.

Pro výpočet hodnocení (v programu nazývaném \texttt{rating}) je třeba pro každý jízdní pruh na vjezdech do křižovatky znát délku fronty a očekávané časy příjezdů vozidel od sousední křižovatky. Délka fronty se v současné době získává ze simulátoru, příjezdy pak přímo od souseda. Ten je počítá podle vztahu
\begin{equation}
	t_z = t_{zz} + \frac{d}{v_P} + \mathit{offset}
	\label{eq:tz}
\end{equation}
a
\begin{equation}
	t_k = t_z + t_{dz} \;,
	\label{eq:tk}
\end{equation}
kde $t_z$ je čas začátku příjezdu aut a $t_k$ čas konce. Dále pak $t_{zz}$ je čas začátku svícení zelené, $d$ vzdálenost ke křižovatce, která žádá o časy příjezdů, $v_P$ průměrná rychlost vozidel, $\mathit{offset}$ nastavený offset a $t_{dz}$ délka svícení zelné. K těmto dvěma vypočítaným hodnotám se ještě přidává předpokládaný počet aut. Jeho odhad je získán z hustoty provozu v minulém cyklu. Křižovatka zasílající odhady takovýchto trojic údajů předává několik -- podle toho, kolik fází rozsvěcí zelenou ve směru připouštějícím jízdu k sousedovi žádajícímu o odhady.

Po shromáždění všech předpokladů od sousedů může agent přistoupit k samotnému výpočtu hodnocení. Ten spočívá v tom, že agent spočítá příspěvky všech jízdních pruhů, u kterých má nějaké informace o časech příjezdů. Pro každý pruh se pak nejprve spočítá délka fronty v čase, kdy se na jeho odjezdu rozsvítí zelená. To znamená:
\begin{equation}
	Q_V = Q + \sum_{i=1}^{k}{\left|T_i\right|\cdot n_i}
	\label{eq:qv}
\end{equation}
kde $Q_V$ je délka tak zvané virtuální fronty, zde jde o délku fronty při rozsvícení zelené, $Q$ je odhadovaná délka fronty, $\left|T_i\right|$ je délka $i$-tého intervalu, ve kterém přijíždějí vozidla, $n_i$ je počet těchto vozidel a $k$ je počet intervalů s příjezdy před rozsvícením zelené.

Z tohoto odhadu pak vychází výpočet předpokládané délky fronty v okamžiku, kdy zelená přejde zpět na červenou. K tomu je třeba rozdělit interval od prvního očekávaného příjezdu nebo rozsvícení zelené (podle toho, co nastane dříve) po zhasnutí zelené (tento interval označíme $T$) na posloupnost intervalů $\left(T_i\right)^{k}_{i=1}$. $T_i$ jsou intervaly typu $\left<a_i;b_i\right>$, kde $b_i=a_{i+1}$ $\forall i \in \left\{ 1, \ldots, k-1\right\}$, $a_1$ a $b_k$ jsou krajní body intervalu $T$ a $a_i$ jsou chronologicky řazené všechny významné body, tedy body, ve kterých se mění signalizovaný znak nebo ve kterých začíná či končí příjezd vozidel od souseda.

S pomocí tohoto dělení pak můžeme počítat
\begin{equation}
	Q_K = Q_V + \sum_{i=1}^{k}{u(T_i)}\,,
	\label{eq:qk}
\end{equation}

kde $u(T_i)$ je funkce $u:\; \left<a;b\right> \rightarrow \mathbb{R}$
\begin{equation}
	u(T_i)=
	\begin{cases}
		n_i 								&\text{pokud v intervalu } T_i \text{ pouze přijíždějí vozidla}  \\
		-|T_i|\cdot c_o 		&\text{pokud v intervalu } T_i \text{ pouze odjíždějí vozidla}  \\
		n_i-|T_i|\cdot c_o 	&\text{pokud v intervalu } T_i \text{ přijíždějí i odjíždějí vozidla} 
	\end{cases}
	\;.
	\label{eq:uti}
\end{equation}

$Q_K$ značí konečnou délku fronty, $Q_V$ je virtuální fronta z rovnice (\ref{eq:qv}), $k$ je počet intervalů „s různými vjezdy a výjezdy“. $|T_i|$ je délka intervalu $T_i$, $n_i$ počet vozidel, která přijedou v intervalu $T_i$ a $c_o$ je empiricky zjištěná konstanta -- počet vozidel, která za sekundu opustí křižovatku.

Definice funkce $u(T_i)$ jak je zapsána vztahem (\ref{eq:uti}) není úplná. Ještě je nutné doplnit omezení
\begin{equation}
	u(T_i)
	\begin{cases}
	 	\geq -Q_i		&\text{pokud v intervalu } T_i \text{ pouze odjíždějí vozidla}  \\
	 	\leq n_i 	&\text{pokud v intervalu } T_i \text{ přijíždějí i odjíždějí vozidla} 
	\end{cases}\,,
	\label{eq:uti-omez}
\end{equation}
kde $Q_i$ je délka fronty na začátku intervalu $T_i$.

Tyto podmínky zarčují, že pokud z jízdního pruhu jen odjíždějí vozidla, nemůže jich odjet více než jich čeká na začátku ve frontě a že pokud vozidla zároveň přijíždějí a odjíždějí, projede jich bez zastavení maximálně tolik, kolik dorazí od souseda.

Pokud vyjde $Q_K$ záporné, představuje (odhadovaný) počet aut, která mohou křižovatkou projet bez zastavení a tato hodnota se tedy odečte od hodnocení dané křižovatky (a tím se hodnocení zvýší). 

Vyvstává otázka jak zjistit aktuální délky fronta na jednotlivých ramenech jen pomocí údajů z detektorů, které jsou k dispozici. Ukazuje se, že toto není triviální problém a jeho řešení přesahuje rámec této práce. Z toho důvodu nejsou v programu délky front odhadovány tak, jak by to bylo nutné v reálné situaci, ale používají se hodnoty, které lze získat ze simulátoru Aimsun. Podrobnější informace o modelování délky fronty představuje například \cite{pecherkova}. 

Při samotném vyjednávání pak mají agenti dvě role, jeden z nich je označen jako \emph{pasivní}, zatímco druhý je v pozici aktivního. Pasivní agent má pevně nastavený offset a jen reaguje na pokyny aktivního. Pokyny tvoří buď žádost o očekávané časy příjezdů nebo návrh na změnu offsetu. Na první z nich agent vždy odpovídá zasláním požadovaných údajů, u druhého pak zvažuje, jestli by změna v celkovém součtu přinesla zlepšení \texttt{ratingu}. Z tohoto popisu už pak vyplývá role aktivního agenta. Ten stejně pracuje se žádostmi o časy příjezdů, navíc ale aktivně mění svůj offset a pokouší se vyjednat změnu u sousedů.

Vyjednávací cyklus pak probíhá v několika krocích. Nejprve si všichni agenti vyžádají očekávané příjezdy vozidel na základě offsetů nastavených v minulém cyklu. S přihlédnutím k těmto očekáváním pak aktivní agenti spočítají \texttt{rating} svého nastavení offsetu a pokusí se zjistit, jestli by nějaká změna vlastního offsetu nevedla ke zlepšení hodnocení. 

Hledání nejlepšího vlastního offsetu probíhá ve třech krocích. Nejprve se porovná aktuální offset, offset zvýšený o 8 sekund a offset snížený o 8 sekund. Vybere se nejlépe hodnocený ze tří možností a pokračuje se s ním stejným způsobem, jen další uvažovaná změna je $\pm4$ sekundy. V posledním kroku je pak otestován posun o $\pm2$ sekundy.

Když aktivní agenti naleznou své nejlepší offsety, rozešle se všem účastníkům zpráva o nalezení stabilního stavu, která obsahuje nové hodnoty očekávaných příjezdů vozidel. Nyní aktivní agenti vyzkouší, jestli by k dalšímu zlepšení nevedla změna offsetu u některého z jejich sousedů. Stejným způsobem jako při hledání vlastního nejlepšího offsetu zkusí odhadnout změnu \texttt{ratingu} při posunu sousedova offsetu o $\pm$ 4, 2 a 1 sekundu. Pokud má nejlepší hodnocení nenulová změna, zašle se sousedovi žádost o tuto změnu spolu se změnou \texttt{ratingu}, kterou by přinesla.

Každý pasivní agent poté sesbírá všechny návrhy a otestuje, který z nich má největší součet změny ratingu u něj samotného a změny u navrhovatele a ten potom přijme za vlastní. Pokud by všechny návrhy přinesly zápornou změnu, jsou zamítnuty a žádná změna nenastává. V každém případě jsou pak rozeslány informace o novém stabilním stavu a s nimi opět očekávané příjezdy. 

Tímto každá křižovatka nalezne svůj konečný offset. Problém nastává při zaslání tohoto offsetu do řadiče křižovatky. Od toho není garantována okamžitá akce, způsob jakým žádaného offsetu dosáhne je jen v jeho režii a než se tak stane může trvat i několik cyklů. Z tohoto důvodu se vypočtený offset neposílá hned po nalezení, ale agent vždy v pěti cyklech napočítá optimální offset, z těchto pěti hodnot spočítá průměr a až ten se následně předá řadiči pro zpracování. Tím je také snížena reaktivnost agenta a zamezí se případným přehnaným reakcím na chvilkové změny poptávky, kterým stejně není možné se přizpůsobit.

\section{Použité knihovny}
Pro usnadnění práce a také z důvodu lepšího začlenění do současného řešení se v~programu používají tři volně dostupné knihovny: \texttt{IT++}, zjednodušující práci s~vektory, maticemi a~poli, \texttt{BDM} (Bayesian Decision Making), která obsahuje užitečné nástroje pro práci s~popisy k~vektorům a obsahuje také nástroj pro ukládání průběžných hodnoot z experimentu a~\texttt{libconfig}, sloužící především pro práci s~konfiguračními soubory. První dvě knihovny jsou distribuovány pod GPL licencí, třetí pak pod licencí LGPL.

\subsection{IT++}
\texttt{IT++} je knihovna pro C++, která obsahuje třídy a~funkce pro provádění některých matematických operací, zpracování signálů a~další. Pro účely této práce jsou zajímavé právě funkce matematické. 

Pro zacházení s vektory jsou v~knihovně mimo jiné zavedeny typy \texttt{vec} a~\texttt{ivec}. První jmenovaný je vektor obsahující prvky typu \texttt{double}, tedy čísla s~desetinou čárkou, druhý je pak složen z~prvků \texttt{int}, čili čísel celých. Práce s~vektory je velmi intuitivní, navíc lze často používat syntaxi podobnou jako v~programu MATLAB.

Vektor můžeme nadefinovat jedním z~těchto způsobů
\lstset{language=C++, showstringspaces=false}
\begin{lstlisting}
vec my_vector;
vec my_vector(10);
\end{lstlisting}
přičemž první z nich pro vektor nealokuje paměť. To je pak nutné udělat funkcí \lstinline{setsize()}. Následně je pak možné uložit do vektoru jednotlivé prvky a~to například jedním z následujících příkazů.
\begin{lstlisting}
vec  a = "0 0.7 5 9.3";        // tedy a = [0 0.7 5 9.3]
ivec b = "0:5";                // tedy b = [0 1 2 3 4 5]
vec  c = "3:2.5:13";           // tedy c = [3 5.5 8 10.5 13]
ivec d = "1:3:5,0:2:4";        // tedy d = [1 3 5 0 2 4]
vec e("1.2,3.4,5.6");          // tedy e = [1.2 3.4 5.6]
\end{lstlisting}
Navíc lze i-tému prvku vektoru \texttt{a} přistupovat pomocí \lstinline!a(i)! nebo \lstinline[]!a[i]!. 

Díky přetížení operátorů lze s~vektory přímo provádět běžné matematické operace, jako jsou:
\begin{lstlisting}
a+b	// součet vektorů
a+5	// přičtení čísla 5 ke všem prvkům vektoru
a*b	// skalární součin vektorů
a*9	// vynásobení všech prvků vektoru číslem 9
\end{lstlisting}
a~tak podobně.

Práce s maticemi pak funguje podle obdobných pravidel.

Dále se v knihovně nachází třída \texttt{Array}. Díky ní je možné vytvářet pole prvků libovolného typu (včetně výše popsaných vektorů) a provádět s nimi mnohé operace. Příkladem užití právě pro pole vektorů je například následující kód:
\begin{lstlisting}
Array<vec> pole_vektoru(2);
my_vec_array(0) = "2 4 5 0 3";;
my_vec_array(1) = "0.1 0.2 0.3 0.4 0.3 0.2 0.1";
\end{lstlisting}
U takto definovaného pole pak lze pak intuitivně přistupovat k jeho prvkům pomocí \lstinline!pole_vektoru(i)! a navíc provádět operace jako jsou posuny prvků, výběr podmnožiny prvků nebo třeba prostředního prvku a mnohé další.

\subsection{BDM}
Knihovna \texttt{BDM} (Bayesian Decision Making) se zabývá, jak název napovídá, bayesovským rozhodováním. Ovšem v~této práci jsou z~ní přímo použity jen některé třídy, jmenovitě \texttt{UI}, \texttt{RV}, \texttt{datalink} a~\texttt{logger}.

Třída \texttt{UI} (User Info) slouží pro ukládání a~čtení libovolných uživatelských dat. Zde se používá pro načtení konfigurace pro simulátor a~pro jednotlivé agenty a~dále jako formát pro ukládání a~posílání zpráv mezi agenty.

Účelem třídy \texttt{RV} je poskytovat popisné informace k~datovému vektoru. Proměnná typu \texttt{RV} se skládá z~jedné nebo několika položek. Každá taková položka má svoje jméno (\texttt{name}) a~délku -- počet prvků, které tomuto jménu odpovídají. Součet délek všech takovýchto položek se potom musí rovnat délce vektoru, který je danou proměnnou typu \texttt{RV} popisován. Fungování je ilustrováno na obrázku \ref{fig:rv}.

\begin{figure}%
	\centering
	\includegraphics[width=7cm]{rv}%
	\caption{Vektor typu \texttt{RV} (vlevo) fungující jako popis k vektoru typu \texttt{vec}~(vpravo). Každá položka z \texttt{rv\_vector} má v levém sloupci své jméno (\texttt{name}) a v pravém velikost (\texttt{size}). V tomto případě se tedy podvektor \texttt{c} rovná vektoru [5~4]}%
	\label{fig:rv}%
\end{figure}

Pro kopírování dat mezi vektory existuje třída \texttt{datalink}. Vytváří spojení mezi dvěma datovými vektory na základně shodně pojmenovaných prvků v k nim příslušných popisných vektorech. Po propojení vektoru s podvektorem pak funkce data\-linku umožňují snadné kopírování dat oběma směry.

Na závěr \texttt{Logger} je třída určená pro ukládání dat z~programu. Tvoří abstraktní vrstvu mezi programem a~samotným zápisem dat. Při použití se jen na začátku nastaví v~jaké formě chceme získat výsledné údaje (např. uložit do paměti, do souboru, do databáze, atd.) a~dále třídu používáme bez ohledu na tuto volbu. Je tím zajištěna flexibilita pro případ, že se změní požadavky na výstupy z~programu.

\subsection{Libconfig}
Konfigurační parametry pro simulaci se ukládají do souboru ve formátu, který zavádí knihovna \texttt{libconfig}. Jde o~textový formát, který je stručnější a~pro člověka lépe čitelný, než XML. 

(...rozvést nebo zrušit...)

\section{VGS API}
Velmi důležitým úkolem při simulaci reálné oblasti v mikrosimulátoru Aimsun je vložení reálných vstupních intenzit dopravy do zkoumaného modelu. Běžným postupem je ruční sčítání vozidel v dané oblasti, zpravidla v hodinovém rastru. Takto získaná data je možné vložit do simulátoru Aimsun jako hodinové zátěže, ovšem toto je třeba provést také ručně.

%Jedním z nejdůležitějších úkolů při simulaci reálného zatížení dopravnéí sítě v mikrosimulátoru Aimsun je zatížení celé simulované dopravní sítě reálnými vstupními intenzitami dopravy, odpovídajícími měřením v simulované síti. Při běžných postupech se intenzity dopravy určují pomocí ručního sčítání dopravy, zpravidla v hodinovém rastru. Data, získaná tímto postupem, je možno potom přímo vložit opět ručně do Aimsunu jako hodinové dopravní zátěže.

Přesnější možností je získat intenzity provozu z dat získaných přímo z dopravních detektorů instalovaných v předmětné oblasti. To však znamená ruční zadání stovek údajů do simulátoru. Právě z tohoto důvodu vzniklo VGS API. To se stará o nastartování Aimsunu a vpouštění vozidel do oblasti. Vjezdy vozidel se při tom řídí údaji v externím souboru, obsahujícím intenzity na jednotlivých ramenech. Uživatel pak jen zadá jméno a umístění tohoto souboru a vše ostatní se děje automaticky. Navíc lze volit mezi různými rozdělení pravděpodobnosti vjezdů, přičemž nejčastěji používané je rovnoměrné či Poissonovo rozdělení.

%Pokud se snažíme o přesnější simulaci, můžeme pro zatižení dopravní sítě použít data získaná přímo z dopravních detektorů instalovaných v simulované oblasti. V takovém případě by bylo potřeba ručně vkládat několik set hodnot vstupních intenzit pro každý simulovaný den. VGS API vzniklo ve snaze tento handicap odstranit -- na začátku simulace rozhraní pouze uživatewl předá informace o tom, kde je umístěn soubor s intenzitami vjezdů do jednotlivých ramen a o jaká vjezdová ramena jde, VGS API se automaticky postará o nastartování Aimsunu a automaticky vpouští vozidla do systému podle údajů, obsažených v souboru s intenzitami vjezdů. Uživatel může volit různé druhy rozdělení pravděpodobnosti vjezdů, nejčastěji se používá rovnoměrné nebo Poissonovo rozdělení.

Vedle práci se vstupní daty pro simulaci se VGS API stará i o zpracování dat výstupních. Aimsun sice zvládá export výsledků simulací do textových souborů a obsahuje i nástroje pro jejich vizualizaci, neumožňuje přímo ale některé důležité věci jako je například porovnání výsledků ze dvou různých scénářů. VGS proto v průběhu celého experimentu ukládá údaje o sledované oblasti a to jak pro jednotlivé sekce, tak pro celý systém. Ve výsledku uživatel získává informace o počtu zastavení vozidel, o jeho zpoždění, průměrné rychlosti, době jízdy a době stání, o dopravím toku a hustotě dopravy na jednotlivých segmentech či o délkách front vozidel. Údaje o délkách front jsou specialitou VGS, Aimsun tento údaj pro jednotlivé jízdní pruhy přímo neposkytuje a VGS má proto implementován vlastní algoritmus pro jejich sčítání.

%Druhým důležitám úkolem VGS API je zhromažďovat data potřebná pro vyhodnocení experimentu. 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. Uživatel má po ukončení simulace k dispozici údaje o počtu zastavení vozidla, o jeho zpoždění, průměrné rychlosti, době jízdy a době stání, o dopravím toku a hustotě dopravy na jednotlivých segmentech či o délkách front vozidel. Vzhledem k tomu, že Aimsun neposkytuje informace o délce fronty vozidel pro každý na jízdní pruh zvlášť (k dispozici jsou pouze údaje o akumulované délce fronty vyjádřené početm vozuidel, která na segmentu dopravní sítě v daný okamžik stojí), má VGS API implementovaný vlastní algoritmus výpočtu délky fronty vozidel na každém jízdním pruhu a poskytuje uživateli i takto získané informace o délce fronty.

Implementací VGS API je DLL knihovna napsaná v jazyce C pro 32 a 64 bitové systémy Windows XP a výše. Navíc je součástí VGStoolbox, sada skriptů pro zpracování výstupních dat v programu Matlab.

%Vlastní VGS API je implementováno v jazyce C jako DLL pro 32- a 64-bitové systémy počínaje Windows XP, rozhraní je doplněno funkcemi pro obsluhu API a vyhodnocování statistických informací v prostředí nástroje Matlab 

\section{Struktura programu}

Fungování simulačního prostředí tak jak bylo navrženo v ÚTIA je na obrázku (\ref{fig:struktura}). Skladá se ze tří hlavních bloků, mikrosimulátoru Aimsun, emulátorů řadičů ELS3 a z tzv. Aimsun agenta.

Aimsun agent představuje řídící prvek celého systému. Přes \texttt{vgs_api} spouští Aimsun a stejným způsobem od něj průběžně přijímá hodnoty sledovaných dopravních veličin. Dále prostřednictvím \texttt{eh_api} získává údaje z řadičů křižovatek. Na základě všech sesbíraných údajů pak sestavuje pokyny pro změny v signálních plánech a opět pomocí \texttt{eh_api} tyto pokyny zasílá řadičům. 

Na závěr komunikace mezi mikrosimulátorem a emulátory řadičů, které obsahuje údaje z detektorů v jednom směru a ze stavů signálních skupin ve druhém, probíhá přes \texttt{ea_api}.

\begin{figure}%
\centering
\includegraphics[width=\columnwidth]{aimsun-agents}%
\caption{Struktura celé simulace}%
\label{fig:struktura}%
\end{figure}

\section{Program \texttt{main_loop.exe}}
\label{sec:main_loop}

Simulace je obsluhována z~programu \emph{main\_loop.exe}. Ten se stará o~načtení konfigurace, spuštění simulátoru Aimsun a~zajišťuje komunikačního prostředníka mezi jednotlivými agenty. Program se dá rozdělit na jednotlivé bloky jak je zobrazeno na obrázku \ref{fig:mainloop}. Z tohoto nákresu bude vycházet následující popis.

\begin{figure}[t]%
\centering
\includegraphics[width=8.5cm]{mainloop3}%
\caption{Strukuta fungování programu \texttt{main_loop.exe}, podrobněji popsaná v podkapitole \ref{sec:main_loop}}%
\label{fig:mainloop}%
\end{figure}

Během \emph{inicializace} je načten konfigurační soubor, jehož jméno se předává jako jediný parametru při spouštění \texttt{main_loop.exe}. Konfigurační soubor je ve formátu stanoveném knihovnou \texttt{libconfig}. Po načtení jsou parametry ze skupiny \texttt{system} předány VGS API, které se postará o spuštění Aimsunu s těmito parametry. Jde především o~intenzitu provozu na vstupech do dopravní sítě a~délku simulace.

Následně je dle konfigurace vytvořeno pole ukazatelů na agenty \texttt{Ags}. Při konstrukci jednotlivých agentů je volána jejich funkce \texttt{from_setting()} načítající konkrétní parametry každého agenta.  

Poté se vytváří instance třídy \texttt{logger} a její provázání s agenty. V tu chvíli se pouští i funkce \texttt{ds_register()} umožňující aktualizaci datalinků pro spojení mezi agenty a simulátorem. Na závěr tohoto bloku programu je provedena inicializace fronty zpráv a zaregistrování vektorů které se budou v průběhu simulace logovat.

Díle se pokračuje ústředním for cyklem. Část \texttt{získání dat} v sobě zahrnuje uložení logovaných hodnot ze simulátoru a pak především uložení vektor $d_t$ do proměnné \texttt{glob_dt} a jeho odeslání agentům ke zpracování funkcí \texttt{adapt()}. Poté přichází na řadu vyjednávací cyklus.

Vyjednávací cyklus se zabývá obsluhou fronty zpráv. Nejprve proběhne \emph{doručení zpráv}, které jsou aktuálně ve frontě. V prvním kroku vyjednávacího cyklu je fronta zpráv samozřejmě prázdná, v následujícím se od konce prochází a adresovaným agentům jsou předány příslušné zprávy. To se děje zavoláním funkce \texttt{recieve()} se zprávou jako parametrem. V případě, že adresát není nalezen a zprávu tedy nelze doručit je oznámeno varování, ale pokračuje se dál v činnosti. 
	
Po vyprázdnění fronty nastává čas pro \emph{vysílání zpráv}. To spočívá ve spuštění funkce \texttt{broadcast()} u všech agentů. V ní mají příležitost vložit do fronty zpráv libovolný počet sdělení pro ostatní agenty, nemusí ovšem vysílat žádné.

Další postup závisí na stavu fronty zpráv. Pokud je prázdná, tedy žádný agent nevyslal žádnou zprávu, končí vyjednávací cyklus a pokračuje se v běhu programu. V případě, že fronta prázdná není, cyklus se opakuje a proběhne další doručování zpráv z fronty. Vyjednávání může být ukončeno ještě v případě, kdy proběhne stanovený maximální počet vyjednávacích cyklů, nastavený v proměnné \texttt{max_cycles}. Limit by však měl být nastaven tak, aby k jeho dosažení nedocházelo, pokud se tak stane, mělo by to být signálem problému v programu.

Poslední část hlavního cyklu je nazvaná \emph{krok simulace}. Spočívá nejprve v zavolání funkce \texttt{act()} u každého agenta. To je okamžik, kdy mohou agenti ovlivnit řízení signalizace. Právě zde probíhá zkopírování vypočítaných hodnot do vektoru \mbox{\texttt{glob_ut}}, tedy do proměnné představující vektor vstupních hodnot $u_t$. Na závěr hlavního cyklu je celá simulace posunuta o jeden krok dále voláním funkcí \texttt{step()} u loggeru \texttt{L}, \texttt{Ds} a u všech agentů.

Tato smyčka se opakuje dokud není dosažen v konfiguračním souboru nastavený čas simulace. \emph{Zakončení} spočívá již jen v zapsání log souboru.

\section{Implementace navrženého algoritmu}

Algoritmus popsaný v kapitole \ref{sec:navrh} je implementován ve třídě \texttt{GreenWaveTrafficAgent}. Instance této třídy představují agenty přiřazené k jednotlivým křižovatkám (respektive jejím řadičům). 

Třída je odvozena od předka jménem \texttt{BaseTrafficAgent}. Ten slouží jen jako prakticky prázdný agent, po přiřazení k nějaké křižovatce nekoná žádnou akci a umožňuje tak simulovat systém bez decentralizovaného řízení. Předkem této třídy je třída \texttt{Participant} z knihovny BDM. \texttt{Participant}, tedy účastník, představuje základní jednotku v rozhodovacím procesu. Každý účastník má své jméno (\texttt{name}) a je schopen ukládat výsledky. Už právě třída \texttt{Participant} deklaruje existenci funkcí \texttt{adapt()}, \texttt{broadcast()}, \texttt{recieve()}, \texttt{act()} a \texttt{step()}. Tyto jsou v něm definovány jako virtuální (\texttt{virtual}), tedy pokud je v potomkovi redefinujeme, je zaručeno volání těchto nových funkcí.

První po vytvoření instance agenta proběhne zavolání funkce \texttt{from_setting()} vypsanou jako kód \ref{lst:from}. V té se nejprve volá stejnojmenná funkce předka, která načítá z konfigurace základní parametry, jmenovitě:
\begin{description}
	\item[lanes] informace o jízdních pruzích,
	\item[neighbours] -- jména agentů u sousedních křižovatek,
	\item[green_names] -- jména jednotlivých signálních skupin,
	\item[green_starts] -- čas, ve který příslušné signální skupiny rozsvěcí zelenou,
	\item[green_times] -- délka trvání svícení zelené dané signální skupiny, uváděna jako poměr $\text{doba svícení}/\text{délka cyklu}$, 
\end{description}
a některé další, které pro tuto práci nejsou důležité.

Dále se v této funkci nastavují hodnoty konstant a výchozí hodnoty některých proměnných. Konkrétně jde o
\begin{description}
	\item[car_leaving] -- čas v sekundách, ze který jedno auto opustí frontu
	\item[VP] -- průmerná rychlost jízdy automobilu mezi křižovatkami na volné silnici
	\item[actual_time] -- uchovává aktuální čas simulace (v sekundách)
	\item[negot_cycle] -- počet již proběhlých vyjednávacích cyklů od posledního (! zformulovat !)
	\item[cycle_count] -- hranice, po které nastává průměrování konečného offsetu
	\item[total_offset] -- hodnota součtu dosud vyjednaných offsetů od posledního průměrování
	\item[negot_offset] -- krok, kterým se začíná při hledání ideálního offsetu u souseda
	\item[negot_limit] -- krok, kterým se končí při hledání ideálního offsetu u souseda
	\item[passive] --	indikuje zda agent zastává pasivní nebo aktivní roli
\end{description}

V závěru jsou je pak z konfigurace načten výchozí offset, role agenta a připraven vektor výstupních hodnost \texttt{outputs} spolu s jeho popisem \texttt{rv_outputs}. Na úplném konci je ještě zapnuto logování hodnot offsetů pro pozdější vyhodnocení.

\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numberstyle=\tiny, numbersep=0pt, tabsize=2, breaklines, breakautoindent=false, captionpos=b}
\begin{lstlisting}[caption=Funkce from_setting(), label=lst:from, firstnumber=587]
	void from_setting(const Setting &set) {
		BaseTrafficAgent::from_setting(set);

		RV rv_exp;

		car_leaving=2;
		VP=45;
		actual_time=0;
		
		negot_cycle=1;
		cycle_count=5;
		total_offset=0;

		negot_offset=4;
		negot_limit=1;

		passive=0;
		
		UI::get(last_offset, set, "offset", UI::compulsory);
		UI::get(passive, set, "passive", UI::optional);

		for (int i=0;i<lanes.length();i++) {
			for (int j=0;j<lanes(i).outputs.length();j++) {
				if (lanes(i).outputs(j)!="DUMMY_DET") {
					rv_exp=RV(lanes(i).outputs(j)+"-"+name+"_"+to_string(i),3);
					rv_outputs.add(rv_exp);
				}
			}
		}
		outputs.set_size(rv_outputs._dsize());	

		log_level[logoffset]=true;
	}
\end{lstlisting}

Další volanou funkcí v agentech je \texttt{adapt()}. Podobně jako \texttt{from_setting()} nejprve spouští stejnomenou funkci u svého předka. V té probíhá vyplnění vektorů \texttt{inputs} a \texttt{queues} daty z Aimsunu, uloženými ve vektoru \texttt{glob_dt}. Údaje z \texttt{queues} se předají příslušným \texttt{LaneHandler}ům. Dále je nastaven \texttt{planned_offset} na hodnotu získanou v minulém cyklu a stavové proměnné jsou nastaveny do svých výchozích hodnot.

\begin{lstlisting}[caption=Funkce adapt(), label=lst:adapt, firstnumber=415]
	void adapt(const vec &glob_dt) {
		BaseTrafficAgent::adapt(glob_dt);
			
		for (int i=0;i<lanehs.length();i++) {
			lanehs(i)->queue=queues(lanehs(i)->queue_index);		
		}

		planned_offset=last_offset;
		
		//set state variables to default values
		final_state=false;
		new_stable_state=false;
		send_requests=false;
		need_exps=true;
		negot_offset=4;
	}
\end{lstlisting}

Funkce \texttt{recieve} zpracovává přijaté zprávy od ostatních agentů. Na začátku je přijatá zpráva rozdělena do jednotlivých proměnných.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}, inicializace}, label=lst:recieveInit, firstnumber=491]
	void receive(const Setting &msg){
		string what;
		string to;
		string from;
		vec value;
		RV *rv;
		
		UI::get(what, msg, "what", UI::compulsory);
		UI::get(to, msg, "to", UI::compulsory);
		UI::get(from, msg, "from");
		UI::get(rv, msg, "rv");
		UI::get(value, msg, "value");
\end{lstlisting}

Dále se činnost liší podle „předmětu“ zprávy, tedy podle řetězce uloženého v části \texttt{what}. V případě přijetí žádosti o očekávané časy příjezdů je jen uloženo jméno odesílatele do seznamu žadatelů \texttt{requesters}.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveExpReq, firstnumber=last]
		if (what=="expected_times_request"){ 
			requesters.push_back(from);
		} 
				
\end{lstlisting}

Pokud jsou naopak obsahem přijaté zprávy očekávané časy příjezdů automobilů od souseda, aktivní agent najde nový optimální offset pro svůj signální plán a spočítá \texttt{rating}, pasivní provede jen tento výpočet. Na konci je stavová proměnná nastavena \texttt{new_stable_state} na \texttt{true}, což určuje další činnost agent ve fázi vysílání zpráv.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveNewExp, firstnumber=last]
		else if (what=="new_expected_cars") {
			rv_recieved_exps=*rv;
			recieved_exps=value;
			
			if (!passive) {
				planned_offset=find_best_offset(planned_offset,8);
				planned_offset=normalize_offset(planned_offset);
			}

			planned_rating=count_rating(planned_offset, recieved_exps, rv_recieved_exps);
			
			// we have new stable state to broadcast
			new_stable_state=true;
		}
\end{lstlisting}
Obdržení zprávy s hlavičkou „\texttt{stable_state}“ znamená, že některý ze sousedů změnil své nastavení offsetu a zasílá tedy nové hodnoty očekávaných příjezdů. Pokud je aktuální hodnota \texttt{negot_offset} větší nebo rovna \texttt{negot_limit}, zkouší aktivní, která z hodnot $0$, $+\mathtt{negot\_offset}$ nebo $-\mathtt{negot\_offset}$ by po přičtení k sousedově offsetu znamenala nejlepší rating. Hodnota \texttt{negot_offset} je snížena na polovinu a je připraveno odeslání žádosti pro souseda. Pokud Pokud byla proměnná \texttt{negot_offset} již nižší než než \texttt{negot_limit}, přepíná se agent do konečného stavu, neb již nemá další prostor k vyjednávání se sousedy. 
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveStable, firstnumber=last]
		else if (what=="stable_state") {
			rv_recieved_exps=*rv;
			recieved_exps=value;

			planned_rating=count_rating(planned_offset, recieved_exps, rv_recieved_exps);

			if (!passive) {
				for (int i=0;i<neighbours.length();i++) {
					rv_change_request.add(RV(neighbours(i)+"_change",2));
					change_request.set_size(rv_change_request._dsize()); 
					ivec ind=RV(neighbours(i)+"_change",2).dataind(rv_change_request);
					
					// offset change
					change_request(ind(0))=find_best_exps(negot_offset,neighbours(i),rating_change);
					// rating change
					change_request(ind(1))=rating_change;
				}

				if (negot_offset>=negot_limit) { 
					negot_offset/=2;
					send_requests=true;
				}
				else {
					final_state=true;
				}
			}
			else {
				final_state=true;
			}
		}
\end{lstlisting}
Při přijetí se zprávy s žádostí o změnu offsetu agent zkoumá, zda je součet změny hodnocení po aplikaci navrženého offsetu a zlepšení hodnocení u souseda, které od změny offsetu očekává, větší než nula. Takováto změna se přijímá a podle ní se upravuje \texttt{planned_offset}. V každém případě se agent připraví na zaslání aktuálních hodnot očekávaných příjezdů.
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveOffChange, firstnumber=last]
		else if (what=="offset_change_request") {
			double final_rating_diff;

			rv_recieved_changes=*rv;
			recieved_changes=value;

			for (int i=0;i<rv_recieved_changes.length();i++) {

				ivec ind=RV(rv_recieved_changes.name(i),2).dataind(rv_recieved_changes);

				final_rating_diff=-planned_rating+count_rating(planned_offset+(int)recieved_changes(ind(0)), recieved_exps, rv_recieved_exps)+recieved_changes(ind(1));
				if (final_rating_diff>=0) {
					planned_offset+=(int)recieved_changes(ind(0));
					planned_offset=normalize_offset(planned_offset);
					planned_rating+=final_rating_diff;
				}
			}

			new_stable_state=true;
		}
\end{lstlisting}
Pokud přijde zpráva s předmětem, který \texttt{GreenWaveTrafficAgent} neumí zpracovat, předává ji předkovi. Kdyby se stalo, že ani ten si se zprávou neporadí, pošle se zpráva jeho předkovai (tedy třídě \texttt{bdm::Participant}), který v takovém případě vyvolá varování o nezpracovatelné zprávě.
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveBase, firstnumber=last]
		else {
			BaseTrafficAgent::receive(msg);
		}
	}
\end{lstlisting}

Funkce \texttt{broadcast()} vysílá zprávy do fronty zpráv a to v závislosti na hodnotách agentových stavových proměnných. Pokud není prázdný seznam \texttt{requests}, sestaví odpověď pro každého z agentů uvedeného v seznamu a ten následně vyprázdní. Dále pak za každou ze stavových proměnných, která mají hodnotu \texttt{true} sestaví příslušnou zprávu a hodnotu změní na \texttt{false}. 

\begin{lstlisting}[caption=Funkce broadcast(), label=lst:broadcast, firstnumber=429]
	void broadcast(Setting& set){

		//ask neighbours for exptected arrive times
		if (need_exps) {
			for (int i=0; i<neighbours.length(); i++){
				Setting &msg =set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save (name,msg,"from");
				UI::save ( (string)"expected_times_request", msg, "what");
			}
			need_exps=false;
		}

		// broadcast expected cars
		if (!requesters.empty()) {
			double a;
			expected_cars();
			do {
				Setting &msg =set.add(Setting::TypeGroup);
				UI::save ( requesters.back(), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"new_expected_cars", msg, "what");
				UI::save ( &(rv_outputs), msg, "rv");
				UI::save ( outputs, msg, "value");
				requesters.pop_back();
				a=outputs (10);
			} while (!requesters.empty());			
		}

		// broadcast new stable state (new stable expectations)
		if (new_stable_state) {
			expected_cars();
			for (int i=0;i<neighbours.length();i++) {
				Setting &msg = set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"stable_state", msg, "what");
				UI::save ( &(rv_outputs), msg, "rv");
				UI::save ( outputs, msg, "value");
			}
			new_stable_state=false;
		}

		// broadcast requests to change offset(s)
		if (send_requests) {
			for (int i=0;i<neighbours.length();i++) {
				Setting &msg = set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"offset_change_request", msg, "what");
				UI::save ( &(rv_change_request), msg, "rv");
				UI::save ( change_request, msg, "value");
			}
			send_requests=false;
		}
	
		// reached final offset.
		if (final_state) {
			final_state=false;
		}
	}

\end{lstlisting}

Ve funkci \texttt{act()} se spočítaná hodnota \texttt{planned_offset} přičítá k hodnotě proměnné \texttt{total_offset} a to až do chvíle, než je v něm tolik hodnot, kolik stanovuje limit \texttt{cycle_count}. Když se tohoto limitu dosáhne, vydělí se \texttt{total_offset} tímto limitem, čímž se získá průměrná hodnotná offsetu z posledních cyklů. Průměr se pak znormalizuje, aby byl z intervalu $\left<0;T_c\right>$ a uloží se do vektoru $u_t$, představovaným proměnou \texttt{global_ut}. Tím se tato hodnota dostane k řadiči křižovatky.
\begin{lstlisting}[caption=Funkce act(), label=lst:act, firstnumber=615]
	void act(vec &glob_ut){
		if (negot_cycle==cycle_count) {
			vec action;
			action.set_size(rv_action._dsize());
		
			ivec index = RV(name+"_offset",1).dataind(rv_action);

			action(index(0))=normalize_offset(total_offset/cycle_count, false);
			action2ds.filldown(action,glob_ut);

			total_offset=0;
			negot_cycle=1;
		}
		else {
			total_offset+=planned_offset;
			negot_cycle++;
		}
		last_offset=planned_offset;
	}
\end{lstlisting}

O zápis aktuálních hodnot do logovacího souboru se stará \texttt{log_write()}. Ukládá se dvousložkový vektor. První prvek obsahuje vypočítaný offset \texttt{planned_offset}, druhý jeho hodnocení \texttt{planned_rating}.

\begin{lstlisting}[caption=Funkce log_write(), label=lst:logwrite, firstnumber=644]
	void log_write() const {
		if (log_level[logoffset]){
			vec offset_vec(2);
			offset_vec(0)=planned_offset;
			offset_vec(1)=planned_rating;
			log_level.store(logoffset, offset_vec);			
		}
	} 
\end{lstlisting}
Poslední volaná veřejná funkce agenta je \texttt{step()}, která jen posouvá interní ukazatel času v agentovi o délku kroku simulace.
\begin{lstlisting}[caption=Funkce step(), label=lst:step, firstnumber=635]
	void step() {
		actual_time+=step_length;
	}
\end{lstlisting}