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

(!tady je�t� ��st chyb�!)

P�i 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.

(!Jeden odstavec na p�eps�n� ve je zdroj�ku!)

%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 optim�ln� offset. Probl�m nast�v� p�i zasl�n� nalezen�ho 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 intiutivn�, 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}
