\chapter{Algoritmus řízení}
\section{Návrh algoritmu}
Ú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í. 

Důležitým prvkem návrhu je funkce která, ohodnotí nastavení offsetu a umožní tak tedy porovnat různé jeho hodnoty a vybrat tu možná nejlepší. Jako míra kvality byl 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 vjezdu 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 dvoum 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, který o odhady žádal.

Po shromáždění všech předpokladů od sousedů může agent přistoupit k samotnému výpočtu. 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}{t_i 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, $t_i$ 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é.

Dále se pak spočítá délka virtuální 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\{ 2, \ldots, n-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čná délka 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 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}
	 	< Q_K & \text{někdy}\\
	 	> Neco 	& \text{jindy}
	\end{cases}
	\label{eq:uti-omez}
\end{equation}

(! výše uvedené je neúplné !)

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

Při samotném vyjednávání pak mají agenti dvě role, jeden z nich je označen jako \emph{pasivní}, zatímco druhý ne, hraje tedy roli aktivního. Pasivní agent má pevně nastavený offset a jen reaguje na pokyny aktivního. Pokyny jsou buď žádost o očekávané časy příjezdů nebo návrh na změnu offsetu. Na první z nich agent vždy reaguje zasláním požadovaných údajů, u druhé 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. Na základě těchto očekávaní pak aktivní agenti spočítají \texttt{rating} svého nastavení offsetu a pokusí se zjistit, jestli by nějaká změna jejich offsetu nevedla k zlepšení \texttt{ratingu}. Hledání nejlepší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 nejlepší ze tří možností a pokračuje se s ní stejným způsobem, jen uvažovaná změna je $\pm$ 4 sekundy. V posledním kroku je pak změna $\pm$ 2 sekundy.

Když všichni aktivní agenti naleznou své nejlepší offsety, rozešle se všem agentům zpráva o nalezení stabilního stavu, která obsahuje nové hodnoty očekávaných příjezdů vozidel. Nyní agenti vyzkouší, jestli by k dalšímu zlepšení nevedla změna offsetu u některého ze 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ší \texttt{rating} nenulová změna, zašle se sousedovi žádost o tuto změnu spolu se změnou \texttt{ratingu}, který by přinesla.

Soused poté sesbírá všechny návrhy a otestuje, který z návrhů má největší součet změny ratingu u něj samotného a 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 toho důvodu se nalezený 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řízpů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 se 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~\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é. 

V~knihovně jsou mj. 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}, tedy čí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í ze způsobů 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 následujími příkazy:
\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:
\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 stejných pravidel.

(Array)

\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í použity jen třídy \texttt{UI}, \texttt{RV}, \texttt{datalink} a~\texttt{loger}.

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}). Například podvektor \texttt{c} má tedy tvar [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 \texttt{datalinku} 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{Struktura programu}
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 spouští s~jedním parametrem, který představuje jméno konfiguračního souboru. Konfigurační soubor používá formát, který načítá knihovna \texttt{libconfig}. 

Program funguje tak, že na začátku načte konfigurační soubor. Pokud konfigurační soubor není zadán, program skončí s~chybou. Po načtení je spuštěn simulátor Aimsun s~parametry zapsanými ve skupině \texttt{system}. Jde především o~intenzitu provozu na vstupech do dopravní sítě a~délku simulace.

Následně je vytvořeno pole ukazatelů na agenty \texttt{Ags}. 


%\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numberstyle=\tiny, numbersep=5pt, tabsize=2}
%\begin{lstlisting}
%for ( int tK=0; tK < Ds->max_length(); tK++ ) {
%		Ds->log_write ( ); // write stuff to 
%		Ds->getdata(glob_dt);
%		for ( int i=0; i<Ags.length(); i++ ) {
%			Ags(i) -> adapt(glob_dt);
%		}
%
%		// NEGOTIATION CYCLE
%		// ends when Queue is empty or after defined number of cycles
%		int cycle=0;
%		do {
%			//DBG
%			MsgStore.writeFile("xxx");
%			// parse message queue
%			for ( int m=Queue.getLength()-1; m>=0; m-- ) { 
%			// go backwards - last mesages are discarded
%				for ( int i=0; i<Ags.length(); i++ ) {
%					Setting& msg=Queue[m];
%					string m_to=msg["to"];
%					if (m_to==Ags(i)->_name()) {
%						Ags(i)->receive(msg);
%						Queue.remove(m);
%						break;
%						// message delivered;
%					}
%				}
%			}
%			if (Queue.getLength()>0){
%				bdm_error("undelivered messages - 
%				probably unknown neighbours");
%			}
%
%			for ( int i=0; i<Ags.length(); i++ ) {
%				Ags(i) -> broadcast(Queue);
%			}
%
%			cycle++;
%		} 
%		while ((Queue.getLength()>0) && (cycle<max_cycles));
%		
%\end{lstlisting}