root/applications/doprava/texty/Zelena_vlna/vnitrek-kapitola3.tex @ 1118

\chapter{Algoritmus ��
\section{N�h algoritmu}
�olem v~t� pr� bylo navrhnout algoritmus vyjedn�n�ezi jednotliv�i�ovatkami tak, aby koordinovanou zm�u sv�fset�vo�zelenou vlnu a~tedy aby projelo co nejv� vozidel bez zbyte�ho zastavov�. 

D�t�kem n�hu je funkce kter�ohodnot�astaven�ffsetu a umo�n�ak tedy porovnat r�jeho hodnoty a vybrat tu mo�n�ejlep��Jako m� kvality byl odhad po� aut, kter�rojedou k�atkou bez zastaven�

Pro v� hodnocen�v programu naz� \texttt{rating}) je t�pro ka�d�n�ruh na vjezdu do k�atky zn�d�u fronty a o��n�asy p�d�idel od sousedn��atky. D�a fronty se v sou�n�ob��� ze simul�ru, p�dy pak p�od souseda. Ten je po��odle 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 � za�ku p�du aut a $t_k$ � konce. D� pak $t_{zz}$ je � za�ku sv�n�elen�$d$ vzd�nost ke k�atce, kter�� o �y p�d�_P$ pr��ychlost vozidel, $\mathit{offset}$ nastaven�et a $t_{dz}$ d�a sv�n�eln�K t�o dvoum hodnot�se je�t����kl�n�t aut. Jeho odhad je z��z hustoty provozu v minul�cyklu. K�atka zas�j� odhady takov�trojic � p���lik -- podle toho, kolik f� rozsv� zelenou ve sm� p��t�c�j�u k sousedovi, kter�hady ��l.

(!tady je�t�� chyb�

P�jedn�n�ak maj�genti dv�ole, jeden z nich je ozna� jako \emph{pasivn� zat�o druh�hraje tedy roli aktivn�. Pasivn�gent m�evn�astaven�et a jen reaguje na pokyny aktivn�. Pokyny jsou bu��st o o��n�asy p�d�o n�h na zm� offsetu. Na prvn� nich agent v�dy reaguje zasl�m po�adovan�aj�druh�ak zva�uje, jestli by zm� v celkov�sou� p�la zlep�en�texttt{ratingu}. Z tohoto popisu u� pak vypl�le aktivn� agenta. Ten stejn�racuje se ��stmi o �y p�d�v�ale aktivn�� sv�fset a pokou��e vyjednat zm� u soused�
Vyjedn�c�yklus pak prob� v n�lika kroc�. Nejprve si v�ichni agenti vy��j���n��dy vozidel na z�ad�ffset�taven�minul�cyklu. Na z�ad��to o��n�ak aktivn�genti spo�aj�texttt{rating} sv� nastaven�ffsetu a pokus�e zjistit, jestli by n�k�m� jejich offsetu nevedla k zlep�en�texttt{ratingu}. Hled� nejlep�� offsetu prob� ve t�kroc�. Nejprve se porovn�ktu��ffset, offset zv�o 8 sekund a offset sn�n�sekund. Vybere se nejlep��e t��nost� pokra�e se s n�tejn�sobem, jen uva�ovan�m� je $\pm$ 4 sekundy. V posledn�kroku je pak zm� $\pm$ 2 sekundy.

(!Jeden odstavec na p�n�e je zdroj�!)

%Kdy� v�ichni aktivn�genti naleznou sv�ejlep��ffsety, roze�le se v�em agent�r� o nalezen�tabiln� stavu, kter�bsahuje nov�odnoty o��n��zd�idel. Nyn�genti vyzkou��jestli by k dal�� zlep�en�evedla zm� offsetu u n�er� ze soused�ejn�sobem jako p�ed� vlastn� nejlep�� offsetu zkus�dhadnout zm� \texttt{ratingu} p�sunu sousedova offsetu o $\pm$ 4, 2 a 1 sekundu. Pokud m�ejlep��texttt{rating} nenulov�m�, za�le se sousedovi ��st o tuto zm� spolu se zm�u \texttt{ratingu}, kter��la.

Soused pot�esb� v�echny n�hy a otestuje, kter�vrh�nejv��ou� zm� ratingu u n�samotn� a u navrhovatele a ten potom p� za vlastn�Pokud by v�echny n�hy p�ly z�rnou zm�, jsou zam�uty a ���m� nenast�. V ka�d�p��sou pak rozesl� informace o nov�stabiln�stavu a s nimi op�o��n��dy. 

T�o ka�d��atka nalezne sv�tim��ffset. Probl�nast� p�sl� nalezen� offsetu do �e k�atky. Od toho nen�arantov� okam�it�kce, zp�jak�an� offsetu dos�e je jen v jeho re�ii a ne� se tak stane m�rvat i n�lik cykl�toho d� se nalezen�et nepos� hned po nalezen�ale agent v�dy v p� cyklech napo��ptim��ffset, z t�to p� hodnot spo��r�a a� ten se n�edn���i pro zpracov�. T�je tak�n�na reaktivnost agenta a zamez�e p�n�hnan�kc�na chvilkov�m� popt�y, kter�jn�en�o�n�e p�sobit.

\section{Pou�it�nihovny}
Pro usnadn� pr� a tak� d� lep�� za�n� do sou�n� ��e v~programu se pou��j��ln�ostupn�nihovny: \texttt{IT++}, zjednodu�uj� pr� s~vektory, maticemi a~poli, \texttt{BDM} (Bayesian Decision Making), kter�bsahuje u�ite� n�roje pro pr� s~popisy k~vektor�\texttt{libconfig}, slou�� p���pro pr� s~konfigura�mi soubory. Prvn�v�nihovny jsou distribuov� pod GPL licenc�t�pak pod licenc�GPL.

\subsection{IT++}
\texttt{IT++} je knihovna pro C++, kter�bsahuje t�a~funkce pro prov�n��er�tematick�erac�zpracov� sign� a~dal��Pro � t� pr� jsou zaj�v�r� funkce matematick�

V~knihovn�sou mj. zavedeny typy \texttt{vec} a~\texttt{ivec}. Prvn�menovan�ektor obsahuj� prvky typu \texttt{double}, tedy �la s~desetinou �kou, druh�ak slo�en z~prvk�ttt{int}, tedy �el cel�r� s~vektory je velmi intiutivn�nav�lze �to pou��t syntaxi podobnou jako v~programu MATLAB.

Vektor m� nadefinovat jedn�z~t�to zp�:
\lstset{language=C++, showstringspaces=false}
\begin{lstlisting}
vec my_vector;
vec my_vector(10);
\end{lstlisting}
p�� prvn�e zp� pro vektor nealokuje pam� To je pak nutn�d�t funkc�lstinline{setsize()}. N�edn�e pak mo�n�lo�it do vektoru jednotliv�rvky a~to nap�d n�eduj� p�y:
\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�lze i-t� prvku vektoru \texttt{a} p�povat pomoc�lstinline!a(i)! nebo \lstinline[]!a[i]!. �

D� p�en�per�r� s~vektory p�prov�t b��atematick�perace:
\begin{lstlisting}
a+b     // sou� vektor�5        // p�n��a 5 ke v�em prvk�ktoru
a*b     // skal��ou� vektor�9   // vyn�ben��ech prvk�toru �lem 9
\end{lstlisting}
a~tak podobn�

Pr� s maticemi pak funguje podle stejn�avidel.

(Array)

\subsection{BDM}
Knihovna \texttt{BDM} (Bayesian Decision Making) se zab�ak n�v napov�, bayesovsk�hodov�m. Ov�em v~t� pr� jsou z~n�ou�ity jen t�\texttt{UI}, \texttt{RV}, \texttt{datalink} a~\texttt{loger}.

T�\texttt{UI} (User Info) slou��ro ukl�n�~�n�ibovoln�ivatelsk�t. Zde se pou�� pro na�n�onfigurace pro simul�r a~pro jednotliv�genty a~d� jako form�pro ukl�n�~pos�n�pr�mezi agenty.

�elem t�\texttt{RV} je poskytovat popisn�nformace k~datov� vektoru. Prom��ypu \texttt{RV} se skl� z~jedn�ebo n�lika polo�ek. Ka�d�akov�olo�ka m�voje jm� (\texttt{name}) a~d�u -- po� prvk�er�omuto jm� odpov�j�Sou� d�k v�ech takov�polo�ek se potom mus�ovnat d�e vektoru, kter�anou prom�ou typu \texttt{RV} popisov� Fungov� je ilustrov� na obr�u \ref{fig:rv}.

\begin{figure}%
        \centering
        \includegraphics[width=7cm]{rv}%
        \caption{Vektor typu \texttt{RV} (vlevo) funguj� jako popis k vektoru typu \texttt{vec}~(vpravo). Ka�d�olo�ka z \texttt{rv\_vector} m� lev�sloupci sv�m� (\texttt{name}) a v prav�velikost (\texttt{size}). Nap�d podvektor \texttt{c} m�edy tvar [5 4]}%
        \label{fig:rv}%
\end{figure}

Pro kop�v� dat mezi vektory existuje t�\texttt{datalink}. Vytv� spojen�ezi dv� datov�ktory na z�adn�hodn�ojmenovan�vk� nim p��n�pisn�ktorech. Po propojen�ektoru s podvektorem pak funkce \texttt{datalinku} umo�� snadn�op�v� dat ob� sm�.

Na z�r \texttt{Logger} je t�ur��ro ukl�n�at z~programu. Tvo�straktn�rstvu mezi programem a~samotn�isem dat. P�u�it�e jen na za�ku nastav�~jak�orm�hceme z�at v��daje (nap�o�it do pam�, do souboru, do datab�, atd.) a~d� t�pou��me bez ohledu na tuto volbu. Je t�zaji�t� flexibilita pro p�, �e se zm� po�adavky na v� z~programu.

\subsection{Libconfig}
Konfigura� parametry pro simulaci se ukl�j�o souboru ve form�, kter�d�nihovna \texttt{libconfig}. Jde o~textov�� kter�tru�j��~pro �v� l� �eln� XML. 

(...rozv� nebo zru�it...)

\section{Struktura programu}
Simulace je obsluhov� z~programu \emph{main\_loop.exe}. Ten se star�~na�n�onfigurace, spu�t� simul�ru Aimsun a~zaji��uje komunika�ho prost�ka mezi jednotliv�enty. Program se spou�t�~jedn�parametrem, kter�stavuje jm� konfigura�ho souboru. Konfigura� soubor pou�� form� kter�t�nihovna \texttt{libconfig}. 

Program funguje tak, �e na za�ku na� konfigura� soubor. Pokud konfigura� soubor nen�ad� program skon�s~chybou. Po na�n�e spu�t�simul�r Aimsun s~parametry zapsan� skupin�texttt{system}. Jde p���o~intenzitu provozu na vstupech do dopravn�� a~d�u simulace.

N�edn�e vytvo�pole ukazatel�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}