| 1 | \chapter{Algoritmus �� |
|---|
| 2 | \section{N�h algoritmu} |
|---|
| 3 | �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�. |
|---|
| 4 | |
|---|
| 5 | 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� |
|---|
| 6 | |
|---|
| 7 | 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 |
|---|
| 8 | \begin{equation} |
|---|
| 9 | t_z = t_{zz} + \frac{d}{v_P} + \mathit{offset} |
|---|
| 10 | \label{eq:tz} |
|---|
| 11 | \end{equation} |
|---|
| 12 | a |
|---|
| 13 | \begin{equation} |
|---|
| 14 | t_k = t_z + t_{dz} \;, |
|---|
| 15 | \label{eq:tk} |
|---|
| 16 | \end{equation} |
|---|
| 17 | 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. |
|---|
| 18 | |
|---|
| 19 | Po shrom�� v�ech p�klad�soused�e agent p�upit k samotn� v�. Ten spo�� tom, �e agent spo���vky v�ech j�n� pruh�kter� n�k�nformace o �ech p�d�o ka�d� se pak nejprve spo���a fronty v �e, kdy se na jeho odjezdu rozsv� zelen�To znamen� |
|---|
| 20 | \begin{equation} |
|---|
| 21 | Q_V = Q + \sum_{i=1}^{k}{t_i n_i} |
|---|
| 22 | \label{eq:qv} |
|---|
| 23 | \end{equation} |
|---|
| 24 | kde $Q_V$ je d�a tak zvan�irtu��ronty, zde jde o d�u fronty p�zsv�n�elen�$Q$ je odhadovan��a fronty, $t_i$ je d�a $i$-t� intervalu, ve kter�p�d� vozidla, $n_i$ je po� t�to vozidel a $k$ je po� interval��dy p�ozsv�n�zelen� |
|---|
| 25 | |
|---|
| 26 | D� se pak spo���a virtu��ronty v okam�iku, kdy zelen�� zp�na �venou. K tomu je t�rozd�t interval od prvn� o��n� p�du nebo rozsv�n�elen�podle toho, co nastane d� po zhasnut�elen�tento interval ozna�e $T$) na posloupnost interval�eft(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�ody intervalu $T$ a $a_i$ jsou chronologicky ���echny v��ody, tedy body, ve kter� m� signalizovan� nebo ve kter���i kon�p�d vozidel od souseda. |
|---|
| 27 | |
|---|
| 28 | S pomoc�ohoto d�n�ak m� po�at |
|---|
| 29 | \begin{equation} |
|---|
| 30 | Q_K = Q_V + \sum_{i=1}^{k}{u(T_i)}\,, |
|---|
| 31 | \label{eq:qk} |
|---|
| 32 | \end{equation} |
|---|
| 33 | |
|---|
| 34 | kde $u(T_i)$ je funkce $u:\; \left<a;b\right> \rightarrow \mathbb{R}$ |
|---|
| 35 | \begin{equation} |
|---|
| 36 | u(T_i)= |
|---|
| 37 | \begin{cases} |
|---|
| 38 | n_i &\text{pokud v intervalu } T_i \text{ pouze p�d� vozidla} \\ |
|---|
| 39 | -|T_i|\cdot c_o &\text{pokud v intervalu } T_i \text{ pouze odj�� vozidla} \\ |
|---|
| 40 | n_i-|T_i|\cdot c_o &\text{pokud v intervalu } T_i \text{ p�d� i odj�� vozidla} |
|---|
| 41 | \end{cases} |
|---|
| 42 | \;. |
|---|
| 43 | \label{eq:uti} |
|---|
| 44 | \end{equation} |
|---|
| 45 | |
|---|
| 46 | $Q_K$ zna�kone�u d�u fronty, $Q_V$ je virtu��ronta z rovnice (\ref{eq:qv}), $k$ je po� interval�r�i vjezdy a v��. $|T_i|$ je d�a intervalu $T_i$, $n_i$ po� vozidel, kter��ou v intervalu $T_i$ a $c_o$ je empiricky zji�t� konstanta -- po� vozidel, kter�a sekundu opust��atku. |
|---|
| 47 | |
|---|
| 48 | Definice funkce $u(T_i)$ jak je zaps� vztahem (\ref{eq:uti}) nen�pln�Je�t�e nutn�oplnit omezen�\begin{equation} |
|---|
| 49 | |u(T_i)| |
|---|
| 50 | \begin{cases} |
|---|
| 51 | \leq Q_i &\text{pokud v intervalu } T_i \text{ pouze odj�� vozidla} \\ |
|---|
| 52 | \geq n_i &\text{pokud v intervalu } T_i \text{ p�d� i odj�� vozidla} |
|---|
| 53 | \end{cases}\,, |
|---|
| 54 | \label{eq:uti-omez} |
|---|
| 55 | \end{equation} |
|---|
| 56 | kde $Q_i$ je d�a fronty na za�ku intervalu $T_i$. |
|---|
| 57 | |
|---|
| 58 | Tyto podm�y zar���e pokud z j�n� pruhu jen odj�� vozidla, nem�ich odjet v� ne� jich ��a za�ku ve front� �e pokud vozidla z�ve�ij�� a odj��, projede jich bez zastaven�axim��olik, kolik doraz�d souseda. |
|---|
| 59 | |
|---|
| 60 | Pokud vyjde $Q_K$ z�rn�p�avuje (odhadovan�et aut, kter�ohou k�atkou projet bez zastaven� tato hodnota se tedy ode� od hodnocen�an��atky (a t�se tedy hodnocen�v� |
|---|
| 61 | |
|---|
| 62 | P�motn�vyjedn�n�ak maj�genti dv�ole, jeden z nich je ozna� jako \emph{pasivn� zat�o druh� pozici 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 odpov� zasl�m po�adovan�aj�druh� pak 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� |
|---|
| 63 | 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. S p�dnut�k t�o o��n�pak aktivn�genti spo�aj�texttt{rating} sv� nastaven�ffsetu a pokus�e zjistit, jestli by n�k�m� jejich offsetu nevedla k zlep�en�odnocen�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�stejn�sobem, jen uva�ovan�m� je $\pm$ 4 sekundy. V posledn�kroku je pak otestov�posun o $\pm$ 2 sekundy. |
|---|
| 64 | |
|---|
| 65 | Kdy� 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�ktivn�genti vyzkou��jestli by k dal�� zlep�en�evedla zm� offsetu u n�er� z jejich 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��odnocen�enulov�m�, za�le se sousedovi ��st o tuto zm� spolu se zm�u \texttt{ratingu}, kterou by p�la. |
|---|
| 66 | |
|---|
| 67 | Ka�d�vn�gent pot�esb� v�echny n�hy a otestuje, kter�ch m�ejv��ou� zm� ratingu u n�samotn� a zm� 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. |
|---|
| 68 | |
|---|
| 69 | T�o ka�d��atka nalezne sv�ne� offset. Probl�nast� p�sl� tohoto 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 vypo�n�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. |
|---|
| 70 | |
|---|
| 71 | \section{Pou�it�nihovny} |
|---|
| 72 | 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. |
|---|
| 73 | |
|---|
| 74 | \subsection{IT++} |
|---|
| 75 | \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� |
|---|
| 76 | |
|---|
| 77 | 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�xttt{int}, tedy �el cel�r� s~vektory je velmi intuitivn�nav�lze �to pou��t syntaxi podobnou jako v~programu MATLAB. |
|---|
| 78 | |
|---|
| 79 | Vektor m� nadefinovat jedn�z~t�to zp�: |
|---|
| 80 | \lstset{language=C++, showstringspaces=false} |
|---|
| 81 | \begin{lstlisting} |
|---|
| 82 | vec my_vector; |
|---|
| 83 | vec my_vector(10); |
|---|
| 84 | \end{lstlisting} |
|---|
| 85 | 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 jedn�z n�eduj�ch p��begin{lstlisting} |
|---|
| 86 | vec a = "0 0.7 5 9.3"; // tedy a = [0 0.7 5 9.3] |
|---|
| 87 | ivec b = "0:5"; // tedy b = [0 1 2 3 4 5] |
|---|
| 88 | vec c = "3:2.5:13"; // tedy c = [3 5.5 8 10.5 13] |
|---|
| 89 | ivec d = "1:3:5,0:2:4"; // tedy d = [1 3 5 0 2 4] |
|---|
| 90 | vec e("1.2,3.4,5.6"); // tedy e = [1.2 3.4 5.6] |
|---|
| 91 | \end{lstlisting} |
|---|
| 92 | Nav�lze i-t� prvku vektoru \texttt{a} p�povat pomoc�lstinline!a(i)! nebo \lstinline[]!a[i]!. |
|---|
| 93 | |
|---|
| 94 | D� p�en�per�r� s~vektory p�prov�t b��atematick�perace, jako jsou: |
|---|
| 95 | \begin{lstlisting} |
|---|
| 96 | a+b // sou� vektor�5 // p�n��a 5 ke v�em prvk�ktoru |
|---|
| 97 | a*b // skal��ou� vektor�9 // vyn�ben��ech prvk�toru �lem 9 |
|---|
| 98 | \end{lstlisting} |
|---|
| 99 | a~tak podobn� |
|---|
| 100 | |
|---|
| 101 | Pr� s maticemi pak funguje podle obdobn�avidel. |
|---|
| 102 | |
|---|
| 103 | (Array) |
|---|
| 104 | |
|---|
| 105 | \subsection{BDM} |
|---|
| 106 | 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{logger}. |
|---|
| 107 | |
|---|
| 108 | 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. |
|---|
| 109 | |
|---|
| 110 | �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}. |
|---|
| 111 | |
|---|
| 112 | \begin{figure}% |
|---|
| 113 | \centering |
|---|
| 114 | \includegraphics[width=7cm]{rv}% |
|---|
| 115 | \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]}% |
|---|
| 116 | \label{fig:rv}% |
|---|
| 117 | \end{figure} |
|---|
| 118 | |
|---|
| 119 | 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�. |
|---|
| 120 | |
|---|
| 121 | 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. |
|---|
| 122 | |
|---|
| 123 | \subsection{Libconfig} |
|---|
| 124 | 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. |
|---|
| 125 | |
|---|
| 126 | (...rozv� nebo zru�it...) |
|---|
| 127 | |
|---|
| 128 | \section{Struktura programu} |
|---|
| 129 | 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}. |
|---|
| 130 | |
|---|
| 131 | 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. |
|---|
| 132 | |
|---|
| 133 | N�edn�e dle konfigurace vytvo�pole ukazatel�agenty \texttt{Ags}. P�nstrukci jednotliv�ent�vol� jejich funkce \texttt{from_setting()} na�aj� konkr��arametry ka�d� agenta. |
|---|
| 134 | |
|---|
| 135 | Pot�e vytv� instance t�\texttt{logger} a jej�rov�n� agenty. V tu chv� se pou�t� funkce \texttt{ds_register()} umo��c�ktualizaci datalink� |
|---|
| 136 | (...) |
|---|
| 137 | |
|---|
| 138 | Pak ji� n�eduje �dn�or cyklus. Na jeho za�ku se zap� � do logu. Pot�sou p�na aktu��ata ze simul�ru a p�a agent� zpracov� funkc�texttt{adapt()}. Pokra�e se vyjedn�c�cyklem. |
|---|
| 139 | |
|---|
| 140 | Vyjedn�c�yklus se zab�sluhou fronty zpr� Nejprve frontu prohled�rontu zpr�a p��n�nt�d�im ur��pr� zavol�m funkce \texttt{recieve()}. V p���e nemo�nosti doru� ozn� varov�, ale pokra�e d�v pr�. Nakonec v�ichni agenti maj�o�nost n�k�pr� do fronty p� -- k tomuto � existuje funkce \texttt{broadcast()}. |
|---|
| 141 | |
|---|
| 142 | %\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numberstyle=\tiny, numbersep=5pt, tabsize=2} |
|---|
| 143 | %\begin{lstlisting} |
|---|
| 144 | %for ( int tK=0; tK < Ds->max_length(); tK++ ) { |
|---|
| 145 | % Ds->log_write ( ); // write stuff to |
|---|
| 146 | % Ds->getdata(glob_dt); |
|---|
| 147 | % for ( int i=0; i<Ags.length(); i++ ) { |
|---|
| 148 | % Ags(i) -> adapt(glob_dt); |
|---|
| 149 | % } |
|---|
| 150 | % |
|---|
| 151 | % // NEGOTIATION CYCLE |
|---|
| 152 | % // ends when Queue is empty or after defined number of cycles |
|---|
| 153 | % int cycle=0; |
|---|
| 154 | % do { |
|---|
| 155 | % //DBG |
|---|
| 156 | % MsgStore.writeFile("xxx"); |
|---|
| 157 | % // parse message queue |
|---|
| 158 | % for ( int m=Queue.getLength()-1; m>=0; m-- ) { |
|---|
| 159 | % // go backwards - last mesages are discarded |
|---|
| 160 | % for ( int i=0; i<Ags.length(); i++ ) { |
|---|
| 161 | % Setting& msg=Queue[m]; |
|---|
| 162 | % string m_to=msg["to"]; |
|---|
| 163 | % if (m_to==Ags(i)->_name()) { |
|---|
| 164 | % Ags(i)->receive(msg); |
|---|
| 165 | % Queue.remove(m); |
|---|
| 166 | % break; |
|---|
| 167 | % // message delivered; |
|---|
| 168 | % } |
|---|
| 169 | % } |
|---|
| 170 | % } |
|---|
| 171 | % if (Queue.getLength()>0){ |
|---|
| 172 | % bdm_error("undelivered messages - |
|---|
| 173 | % probably unknown neighbours"); |
|---|
| 174 | % } |
|---|
| 175 | % |
|---|
| 176 | % for ( int i=0; i<Ags.length(); i++ ) { |
|---|
| 177 | % Ags(i) -> broadcast(Queue); |
|---|
| 178 | % } |
|---|
| 179 | % |
|---|
| 180 | % cycle++; |
|---|
| 181 | % } |
|---|
| 182 | % while ((Queue.getLength()>0) && (cycle<max_cycles)); |
|---|
| 183 | % |
|---|
| 184 | %\end{lstlisting} |
|---|
