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

Revision 1120, 13.2 kB (checked in by ondrak, 15 years ago)

bugfix in count_rating

v textech rozpracován popis výpočtu hodnocení

Line 
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
5D�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
7Pro 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}
12a
13\begin{equation}
14        t_k = t_z + t_{dz} \;,
15        \label{eq:tk}
16\end{equation}
17kde $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
19Po 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}
24kde $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
26D� 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
28S 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
34kde $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� d�a 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 konstanta -- po� vozidel, kter�a sekundu opust��atku.
47
48Definice 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                < Q_K & \text{n�y}\\
52                > Neco  & \text{jindy}
53        \end{cases}
54        \label{eq:uti-omez}
55\end{equation}
56
57(! v�eden�e ne� !)
58
59Pokud vyjde $Q_K$ z�rn�zna�(odhadovan�et aut, kter�ohou k�atkou projet bez zastaven� toto �lo se tedy ode� od hodnocen�an��atky (a t�tedy toto hodnocen�v�
60
61P�motn�vyjedn�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�
62Vyjedn�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.
63
64Kdy� 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.
65
66Soused 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.
67
68T�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 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.
69
70\section{Pou�it�nihovny}
71Pro 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.
72
73\subsection{IT++}
74\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�
75
76V~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.
77
78Vektor m� nadefinovat jedn�z~t�to zp�:
79\lstset{language=C++, showstringspaces=false}
80\begin{lstlisting}
81vec my_vector;
82vec my_vector(10);
83\end{lstlisting}
84p�� 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:
85\begin{lstlisting}
86vec  a = "0 0.7 5 9.3";        // tedy a = [0 0.7 5 9.3]
87ivec b = "0:5";                // tedy b = [0 1 2 3 4 5]
88vec  c = "3:2.5:13";           // tedy c = [3 5.5 8 10.5 13]
89ivec d = "1:3:5,0:2:4";        // tedy d = [1 3 5 0 2 4]
90vec e("1.2,3.4,5.6");          // tedy e = [1.2 3.4 5.6]
91\end{lstlisting}
92Nav�lze i-t� prvku vektoru \texttt{a} p�povat pomoc�lstinline!a(i)! nebo \lstinline[]!a[i]!. �
93
94D� p�en�per�r� s~vektory p�prov�t b��atematick�perace:
95\begin{lstlisting}
96a+b     // sou� vektor�5        // p�n��a 5 ke v�em prvk�ktoru
97a*b     // skal��ou� vektor�9   // vyn�ben��ech prvk�toru �lem 9
98\end{lstlisting}
99a~tak podobn�
100
101Pr� s maticemi pak funguje podle stejn�avidel.
102
103(Array)
104
105\subsection{BDM}
106Knihovna \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}.
107
108T�\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
119Pro 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
121Na 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}
124Konfigura� 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}
129Simulace 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
131Program 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
133N�edn�e vytvo�pole ukazatel�agenty \texttt{Ags}.
134
135
136%\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numberstyle=\tiny, numbersep=5pt, tabsize=2}
137%\begin{lstlisting}
138%for ( int tK=0; tK < Ds->max_length(); tK++ ) {
139%               Ds->log_write ( ); // write stuff to
140%               Ds->getdata(glob_dt);
141%               for ( int i=0; i<Ags.length(); i++ ) {
142%                       Ags(i) -> adapt(glob_dt);
143%               }
144%
145%               // NEGOTIATION CYCLE
146%               // ends when Queue is empty or after defined number of cycles
147%               int cycle=0;
148%               do {
149%                       //DBG
150%                       MsgStore.writeFile("xxx");
151%                       // parse message queue
152%                       for ( int m=Queue.getLength()-1; m>=0; m-- ) {
153%                       // go backwards - last mesages are discarded
154%                               for ( int i=0; i<Ags.length(); i++ ) {
155%                                       Setting& msg=Queue[m];
156%                                       string m_to=msg["to"];
157%                                       if (m_to==Ags(i)->_name()) {
158%                                               Ags(i)->receive(msg);
159%                                               Queue.remove(m);
160%                                               break;
161%                                               // message delivered;
162%                                       }
163%                               }
164%                       }
165%                       if (Queue.getLength()>0){
166%                               bdm_error("undelivered messages -
167%                               probably unknown neighbours");
168%                       }
169%
170%                       for ( int i=0; i<Ags.length(); i++ ) {
171%                               Ags(i) -> broadcast(Queue);
172%                       }
173%
174%                       cycle++;
175%               }
176%               while ((Queue.getLength()>0) && (cycle<max_cycles));
177%               
178%\end{lstlisting}
Note: See TracBrowser for help on using the browser.