\chapter{Algoritmus ��zen�}
\section{N�vrh algoritmu}
\label{sec:navrh}
�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�. 

Jedn�m z nosn�ch prvk� n�vrhu je funkce, kter� ohodnot� konkr�tn� nastaven� offsetu a umo�n� tak tedy porovnat r�zn� jeho hodnoty a vybrat tu mo�n� nejlep��. Za tuto m�ru kvality byl zvolen 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 vjezdech 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 dv�ma vypo��tan�m 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 ��daj�c�mu o odhady.

Po shrom�d�n� v�ech p�edpoklad� od soused� m��e agent p�istoupit k samotn�mu v�po�tu hodnocen�. 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}{\left|T_i\right|\cdot 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, $\left|T_i\right|$ 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�.

Z tohoto odhadu pak vych�z� v�po�et p�edpokl�dan� d�lky 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\{ 1, \ldots, k-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�nou d�lku 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 empiricky zji�t�n� 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}
	 	\geq -Q_i		&\text{pokud v intervalu } T_i \text{ pouze odj�d�j� vozidla}  \\
	 	\leq n_i 	&\text{pokud v intervalu } T_i \text{ p�ij�d�j� i odj�d�j� vozidla} 
	\end{cases}\,,
	\label{eq:uti-omez}
\end{equation}
kde $Q_i$ je d�lka fronty na za��tku intervalu $T_i$.

Tyto podm�nky zar�uj�, �e pokud z j�zdn�ho pruhu jen odj�d�j� vozidla, nem��e jich odjet v�ce ne� jich �ek� na za��tku ve front� a �e pokud vozidla z�rove� p�ij�d�j� a odj�d�j�, projede jich bez zastaven� maxim�ln� tolik, kolik doraz� od souseda.

Pokud vyjde $Q_K$ z�porn�, p�edstavuje (odhadovan�) po�et aut, kter� mohou k�i�ovatkou projet bez zastaven� a tato hodnota se tedy ode�te od hodnocen� dan� k�i�ovatky (a t�m se hodnocen� zv���). 

Vyvst�v� ot�zka jak zjistit aktu�ln� d�lky fronta na jednotliv�ch ramenech jen pomoc� �daj� z detektor�, kter� jsou k dispozici. Ukazuje se, �e toto nen� trivi�ln� probl�m a jeho �e�en� p�esahuje r�mec t�to pr�ce. Z toho d�vodu nejsou v programu d�lky front odhadov�ny tak, jak by to bylo nutn� v re�ln� situaci, ale pou��vaj� se hodnoty, kter� lze z�skat ze simul�toru Aimsun. Podrobn�j�� informace o modelov�n� d�lky fronty p�edstavuje nap��klad \cite{pecherkova}. 

P�i samotn�m vyjedn�v�n� pak maj� agenti dv� role, jeden z nich je ozna�en jako \emph{pasivn�}, zat�mco druh� je v pozici aktivn�ho. Pasivn� agent m� pevn� nastaven� offset a jen reaguje na pokyny aktivn�ho. Pokyny tvo�� bu� ��dost o o�ek�van� �asy p��jezd� nebo n�vrh na zm�nu offsetu. Na prvn� z nich agent v�dy odpov�d� zasl�n�m po�adovan�ch �daj�, u druh�ho 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. S p�ihl�dnut�m k t�mto o�ek�v�n�m pak aktivn� agenti spo��taj� \texttt{rating} sv�ho nastaven� offsetu a pokus� se zjistit, jestli by n�jak� zm�na vlastn�ho offsetu nevedla ke zlep�en� hodnocen�. 

Hled�n� nejlep��ho vlastn�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 nejl�pe hodnocen� ze t�� mo�nost� a pokra�uje se s n�m stejn�m zp�sobem, jen dal�� uva�ovan� zm�na je $\pm4$ sekundy. V posledn�m kroku je pak otestov�n posun o $\pm2$ sekundy.

Kdy� aktivn� agenti naleznou sv� nejlep�� offsety, roze�le se v�em ��astn�k�m zpr�va o nalezen� stabiln�ho stavu, kter� obsahuje nov� hodnoty o�ek�van�ch p��jezd� vozidel. Nyn� aktivn� agenti vyzkou��, jestli by k dal��mu zlep�en� nevedla zm�na offsetu u n�kter�ho z jejich 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�� hodnocen� nenulov� zm�na, za�le se sousedovi ��dost o tuto zm�nu spolu se zm�nou \texttt{ratingu}, kterou by p�inesla.

Ka�d� pasivn� agent pot� sesb�r� v�echny n�vrhy a otestuje, kter� z nich m� nejv�t�� sou�et zm�ny ratingu u n�j samotn�ho a zm�ny 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 tohoto d�vodu se vypo�ten� 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�izp�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 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 obsahuje tak� n�stroj pro ukl�d�n� pr�b�n�ch hodnoot z experimentu 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�. 

Pro zach�zen� s vektory jsou v~knihovn� mimo jin� 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}, �ili ��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� z nich 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 jedn�m z n�sleduj�c�ch p��kaz�.
\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, jako jsou:
\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 obdobn�ch pravidel.

D�le se v knihovn� nach�z� t��da \texttt{Array}. D�ky n� je mo�n� vytv��et pole prvk� libovoln�ho typu (v�etn� v��e popsan�ch vektor�) a prov�d�t s nimi mnoh� operace. P��kladem u�it� pr�v� pro pole vektor� je nap��klad n�sleduj�c� k�d:
\begin{lstlisting}
Array<vec> pole_vektoru(2);
my_vec_array(0) = "2 4 5 0 3";;
my_vec_array(1) = "0.1 0.2 0.3 0.4 0.3 0.2 0.1";
\end{lstlisting}
U takto definovan�ho pole pak lze pak intuitivn� p�istupovat k jeho prvk�m pomoc� \lstinline!pole_vektoru(i)! a nav�c prov�d�t operace jako jsou posuny prvk�, v�b�r podmno�iny prvk� nebo t�eba prost�edn�ho prvku a mnoh� dal��.

\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� p��mo pou�ity jen n�kter� t��dy, jmenovit� \texttt{UI}, \texttt{RV}, \texttt{datalink} a~\texttt{logger}.

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}). V tomto p��pad� se tedy podvektor \texttt{c} rovn� vektoru [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 data\-linku 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{VGS API}
Velmi d�le�it�m �kolem p�i simulaci re�ln� oblasti v mikrosimul�toru Aimsun je vlo�en� re�ln�ch vstupn�ch intenzit dopravy do zkouman�ho modelu. B�n�m postupem je ru�n� s��t�n� vozidel v dan� oblasti, zpravidla v hodinov�m rastru. Takto z�skan� data je mo�n� vlo�it do simul�toru Aimsun jako hodinov� z�t�e, ov�em toto je t�eba prov�st tak� ru�n�.

%Jedn�m z nejd�le�it�j��ch �kol� p�i simulaci re�ln�ho zat�en� dopravn�� s�t� v mikrosimul�toru Aimsun je zat�en� cel� simulovan� dopravn� s�t� re�ln�mi vstupn�mi intenzitami dopravy, odpov�daj�c�mi m��en�m v simulovan� s�ti. P�i b�n�ch postupech se intenzity dopravy ur�uj� pomoc� ru�n�ho s��t�n� dopravy, zpravidla v hodinov�m rastru. Data, z�skan� t�mto postupem, je mo�no potom p��mo vlo�it op�t ru�n� do Aimsunu jako hodinov� dopravn� z�t�e.

P�esn�j�� mo�nost� je z�skat intenzity provozu z dat z�skan�ch p��mo z dopravn�ch detektor� instalovan�ch v p�edm�tn� oblasti. To v�ak znamen� ru�n� zad�n� stovek �daj� do simul�toru. Pr�v� z tohoto d�vodu vzniklo VGS API. To se star� o nastartov�n� Aimsunu a vpou�t�n� vozidel do oblasti. Vjezdy vozidel se p�i tom ��d� �daji v extern�m souboru, obsahuj�c�m intenzity na jednotliv�ch ramenech. U�ivatel pak jen zad� jm�no a um�st�n� tohoto souboru a v�e ostatn� se d�je automaticky. Nav�c lze volit mezi r�zn�mi rozd�len� pravd�podobnosti vjezd�, p�i�em� nej�ast�ji pou��van� je rovnom�rn� �i Poissonovo rozd�len�.

%Pokud se sna��me o p�esn�j�� simulaci, m��eme pro zati�en� dopravn� s�t� pou��t data z�skan� p��mo z dopravn�ch detektor� instalovan�ch v simulovan� oblasti. V takov�m p��pad� by bylo pot�eba ru�n� vkl�dat n�kolik set hodnot vstupn�ch intenzit pro ka�d� simulovan� den. VGS API vzniklo ve snaze tento handicap odstranit -- na za��tku simulace rozhran� pouze u�ivatewl p�ed� informace o tom, kde je um�st�n soubor s intenzitami vjezd� do jednotliv�ch ramen a o jak� vjezdov� ramena jde, VGS API se automaticky postar� o nastartov�n� Aimsunu a automaticky vpou�t� vozidla do syst�mu podle �daj�, obsa�en�ch v souboru s intenzitami vjezd�. U�ivatel m��e volit r�zn� druhy rozd�len� pravd�podobnosti vjezd�, nej�ast�ji se pou��v� rovnom�rn� nebo Poissonovo rozd�len�.

Vedle pr�ci se vstupn� daty pro simulaci se VGS API star� i o zpracov�n� dat v�stupn�ch. Aimsun sice zvl�d� export v�sledk� simulac� do textov�ch soubor� a obsahuje i n�stroje pro jejich vizualizaci, neumo��uje p��mo ale n�kter� d�le�it� v�ci jako je nap��klad porovn�n� v�sledk� ze dvou r�zn�ch sc�n���. VGS proto v pr�b�hu cel�ho experimentu ukl�d� �daje o sledovan� oblasti a to jak pro jednotliv� sekce, tak pro cel� syst�m. Ve v�sledku u�ivatel z�sk�v� informace o po�tu zastaven� vozidel, o jeho zpo�d�n�, pr�m�rn� rychlosti, dob� j�zdy a dob� st�n�, o doprav�m toku a hustot� dopravy na jednotliv�ch segmentech �i o d�lk�ch front vozidel. �daje o d�lk�ch front jsou specialitou VGS, Aimsun tento �daj pro jednotliv� j�zdn� pruhy p��mo neposkytuje a VGS m� proto implementov�n vlastn� algoritmus pro jejich s��t�n�.

%Druh�m d�le�it�m �kolem VGS API je zhroma��ovat data pot�ebn� pro vyhodnocen� experimentu. Aimsun sice disponuje jednoduch�m rozhran�m pro vizualizaci dat a jejich export do textov�ch soubor�, nen� ale mo�n� nap��klad porovn�vat jednotliv� sc�n��e simulac�. VGS API proto periodicky ukl�d� v�echny kl��ov� ukazatele jak pro jednotliv� segmenty dopravn� s�t�, tak i pro cel� simulovan� syst�m. U�ivatel m� po ukon�en� simulace k dispozici �daje o po�tu zastaven� vozidla, o jeho zpo�d�n�, pr�m�rn� rychlosti, dob� j�zdy a dob� st�n�, o doprav�m toku a hustot� dopravy na jednotliv�ch segmentech �i o d�lk�ch front vozidel. Vzhledem k tomu, �e Aimsun neposkytuje informace o d�lce fronty vozidel pro ka�d� na j�zdn� pruh zvl᚝ (k dispozici jsou pouze �daje o akumulovan� d�lce fronty vyj�d�en� po�etm vozuidel, kter� na segmentu dopravn� s�t� v dan� okam�ik stoj�), m� VGS API implementovan� vlastn� algoritmus v�po�tu d�lky fronty vozidel na ka�d�m j�zdn�m pruhu a poskytuje u�ivateli i takto z�skan� informace o d�lce fronty.

Implementac� VGS API je DLL knihovna napsan� v jazyce C pro 32 a 64 bitov� syst�my Windows XP a v��e. Nav�c je sou��st� VGStoolbox, sada skript� pro zpracov�n� v�stupn�ch dat v programu Matlab.

%Vlastn� VGS API je implementov�no v jazyce C jako DLL pro 32- a 64-bitov� syst�my po��naje Windows XP, rozhran� je dopln�no funkcemi pro obsluhu API a vyhodnocov�n� statistick�ch informac� v prost�ed� n�stroje Matlab 

\section{Struktura programu}

Fungov�n� simula�n�ho prost�ed� tak jak bylo navr�eno v �TIA je na obr�zku (\ref{fig:struktura}). Sklad� se ze t�� hlavn�ch blok�, mikrosimul�toru Aimsun, emul�tor� �adi�� ELS3 a z tzv. Aimsun agenta.

Aimsun agent p�edstavuje ��d�c� prvek cel�ho syst�mu. P�es \texttt{vgs_api} spou�t� Aimsun a stejn�m zp�sobem od n�j pr�b�n� p�ij�m� hodnoty sledovan�ch dopravn�ch veli�in. D�le prost�ednictv�m \texttt{eh_api} z�sk�v� �daje z �adi�� k�i�ovatek. Na z�klad� v�ech sesb�ran�ch �daj� pak sestavuje pokyny pro zm�ny v sign�ln�ch pl�nech a op�t pomoc� \texttt{eh_api} tyto pokyny zas�l� �adi��m. 

Na z�v�r komunikace mezi mikrosimul�torem a emul�tory �adi��, kter� obsahuje �daje z detektor� v jednom sm�ru a ze stav� sign�ln�ch skupin ve druh�m, prob�h� p�es \texttt{ea_api}.

\begin{figure}%
\centering
\includegraphics[width=\columnwidth]{aimsun-agents}%
\caption{Struktura cel� simulace}%
\label{fig:struktura}%
\end{figure}

\section{Program \texttt{main_loop.exe}}
\label{sec:main_loop}

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 d� rozd�lit na jednotliv� bloky jak je zobrazeno na obr�zku \ref{fig:mainloop}. Z tohoto n�kresu bude vych�zet n�sleduj�c� popis.

\begin{figure}[t]%
\centering
\includegraphics[width=8.5cm]{mainloop3}%
\caption{Strukuta fungov�n� programu \texttt{main_loop.exe}, podrobn�ji popsan� v podkapitole \ref{sec:main_loop}}%
\label{fig:mainloop}%
\end{figure}

B�hem \emph{inicializace} je na�ten konfigura�n� soubor, jeho� jm�no se p�ed�v� jako jedin� parametru p�i spou�t�n� \texttt{main_loop.exe}. Konfigura�n� soubor je ve form�tu stanoven�m knihovnou \texttt{libconfig}. Po na�ten� jsou parametry ze skupiny \texttt{system} p�ed�ny VGS API, kter� se postar� o spu�t�n� Aimsunu s t�mito parametry. Jde p�edev��m o~intenzitu provozu na vstupech do dopravn� s�t� a~d�lku simulace.

N�sledn� je dle konfigurace vytvo�eno pole ukazatel� na agenty \texttt{Ags}. P�i konstrukci jednotliv�ch agent� je vol�na jejich funkce \texttt{from_setting()} na��taj�c� konkr�tn� parametry ka�d�ho agenta.  

Pot� se vytv��� instance t��dy \texttt{logger} a jej� prov�z�n� s agenty. V tu chv�li se pou�t� i funkce \texttt{ds_register()} umo��uj�c� aktualizaci datalink� pro spojen� mezi agenty a simul�torem. Na z�v�r tohoto bloku programu je provedena inicializace fronty zpr�v a zaregistrov�n� vektor� kter� se budou v pr�b�hu simulace logovat.

D�le se pokra�uje �st�edn�m for cyklem. ��st \texttt{z�sk�n� dat} v sob� zahrnuje ulo�en� logovan�ch hodnot ze simul�toru a pak p�edev��m ulo�en� vektor $d_t$ do prom�nn� \texttt{glob_dt} a jeho odesl�n� agent�m ke zpracov�n� funkc� \texttt{adapt()}. Pot� p�ich�z� na �adu vyjedn�vac� cyklus.

Vyjedn�vac� cyklus se zab�v� obsluhou fronty zpr�v. Nejprve prob�hne \emph{doru�en� zpr�v}, kter� jsou aktu�ln� ve front�. V prvn�m kroku vyjedn�vac�ho cyklu je fronta zpr�v samoz�ejm� pr�zdn�, v n�sleduj�c�m se od konce proch�z� a adresovan�m agent�m jsou p�ed�ny p��slu�n� zpr�vy. To se d�je zavol�n�m funkce \texttt{recieve()} se zpr�vou jako parametrem. V p��pad�, �e adres�t nen� nalezen a zpr�vu tedy nelze doru�it je ozn�meno varov�n�, ale pokra�uje se d�l v �innosti. 
	
Po vypr�zdn�n� fronty nast�v� �as pro \emph{vys�l�n� zpr�v}. To spo��v� ve spu�t�n� funkce \texttt{broadcast()} u v�ech agent�. V n� maj� p��le�itost vlo�it do fronty zpr�v libovoln� po�et sd�len� pro ostatn� agenty, nemus� ov�em vys�lat ��dn�.

Dal�� postup z�vis� na stavu fronty zpr�v. Pokud je pr�zdn�, tedy ��dn� agent nevyslal ��dnou zpr�vu, kon�� vyjedn�vac� cyklus a pokra�uje se v b�hu programu. V p��pad�, �e fronta pr�zdn� nen�, cyklus se opakuje a prob�hne dal�� doru�ov�n� zpr�v z fronty. Vyjedn�v�n� m��e b�t ukon�eno je�t� v p��pad�, kdy prob�hne stanoven� maxim�ln� po�et vyjedn�vac�ch cykl�, nastaven� v prom�nn� \texttt{max_cycles}. Limit by v�ak m�l b�t nastaven tak, aby k jeho dosa�en� nedoch�zelo, pokud se tak stane, m�lo by to b�t sign�lem probl�mu v programu.

Posledn� ��st hlavn�ho cyklu je nazvan� \emph{krok simulace}. Spo��v� nejprve v zavol�n� funkce \texttt{act()} u ka�d�ho agenta. To je okam�ik, kdy mohou agenti ovlivnit ��zen� signalizace. Pr�v� zde prob�h� zkop�rov�n� vypo��tan�ch hodnot do vektoru \mbox{\texttt{glob_ut}}, tedy do prom�nn� p�edstavuj�c� vektor vstupn�ch hodnot $u_t$. Na z�v�r hlavn�ho cyklu je cel� simulace posunuta o jeden krok d�le vol�n�m funkc� \texttt{step()} u loggeru \texttt{L}, \texttt{Ds} a u v�ech agent�.

Tato smy�ka se opakuje dokud nen� dosa�en v konfigura�n�m souboru nastaven� �as simulace. \emph{Zakon�en�} spo��v� ji� jen v zaps�n� log souboru.

\section{Implementace navr�en�ho algoritmu}

Algoritmus popsan� v kapitole \ref{sec:navrh} je implementov�n ve t��d� \texttt{GreenWaveTrafficAgent}. Instance t�to t��dy p�edstavuj� agenty p�i�azen� k jednotliv�m k�i�ovatk�m (respektive jej�m �adi��m). 

T��da je odvozena od p�edka jm�nem \texttt{BaseTrafficAgent}. Ten slou�� jen jako prakticky pr�zdn� agent, po p�i�azen� k n�jak� k�i�ovatce nekon� ��dnou akci a umo��uje tak simulovat syst�m bez decentralizovan�ho ��zen�. P�edkem t�to t��dy je t��da \texttt{Participant} z knihovny BDM. \texttt{Participant}, tedy ��astn�k, p�edstavuje z�kladn� jednotku v rozhodovac�m procesu. Ka�d� ��astn�k m� sv� jm�no (\texttt{name}) a je schopen ukl�dat v�sledky. U� pr�v� t��da \texttt{Participant} deklaruje existenci funkc� \texttt{adapt()}, \texttt{broadcast()}, \texttt{recieve()}, \texttt{act()} a \texttt{step()}. Tyto jsou v n�m definov�ny jako virtu�ln� (\texttt{virtual}), tedy pokud je v potomkovi redefinujeme, je zaru�eno vol�n� t�chto nov�ch funkc�.

Prvn� po vytvo�en� instance agenta prob�hne zavol�n� funkce \texttt{from_setting()} vypsanou jako k�d \ref{lst:from}. V t� se nejprve vol� stejnojmenn� funkce p�edka, kter� na��t� z konfigurace z�kladn� parametry, jmenovit�:
\begin{description}
	\item[lanes] informace o j�zdn�ch pruz�ch,
	\item[neighbours] -- jm�na agent� u sousedn�ch k�i�ovatek,
	\item[green_names] -- jm�na jednotliv�ch sign�ln�ch skupin,
	\item[green_starts] -- �as, ve kter� p��slu�n� sign�ln� skupiny rozsv�c� zelenou,
	\item[green_times] -- d�lka trv�n� sv�cen� zelen� dan� sign�ln� skupiny, uv�d�na jako pom�r $\text{doba sv�cen�}/\text{d�lka cyklu}$, 
\end{description}
a n�kter� dal��, kter� pro tuto pr�ci nejsou d�le�it�.

D�le se v t�to funkci nastavuj� hodnoty konstant a v�choz� hodnoty n�kter�ch prom�nn�ch. Konkr�tn� jde o
\begin{description}
	\item[car_leaving] -- �as v sekund�ch, ze kter� jedno auto opust� frontu
	\item[VP] -- pr�mern� rychlost j�zdy automobilu mezi k�i�ovatkami na voln� silnici
	\item[actual_time] -- uchov�v� aktu�ln� �as simulace (v sekund�ch)
	\item[negot_cycle] -- po�et ji� prob�hl�ch vyjedn�vac�ch cykl� od posledn�ho (! zformulovat !)
	\item[cycle_count] -- hranice, po kter� nast�v� pr�m�rov�n� kone�n�ho offsetu
	\item[total_offset] -- hodnota sou�tu dosud vyjednan�ch offset� od posledn�ho pr�m�rov�n�
	\item[negot_offset] -- krok, kter�m se za��n� p�i hled�n� ide�ln�ho offsetu u souseda
	\item[negot_limit] -- krok, kter�m se kon�� p�i hled�n� ide�ln�ho offsetu u souseda
	\item[passive] --	indikuje zda agent zast�v� pasivn� nebo aktivn� roli
\end{description}

V z�v�ru jsou je pak z konfigurace na�ten v�choz� offset, role agenta a p�ipraven vektor v�stupn�ch hodnost \texttt{outputs} spolu s jeho popisem \texttt{rv_outputs}. Na �pln�m konci je je�t� zapnuto logov�n� hodnot offset� pro pozd�j�� vyhodnocen�.

\lstset{language=[Visual]C++,showstringspaces=false,numbers=left, numberstyle=\tiny, numbersep=0pt, tabsize=2, breaklines, breakautoindent=false, captionpos=b}
\begin{lstlisting}[caption=Funkce from_setting(), label=lst:from, firstnumber=587]
	void from_setting(const Setting &set) {
		BaseTrafficAgent::from_setting(set);

		RV rv_exp;

		car_leaving=2;
		VP=45;
		actual_time=0;
		
		negot_cycle=1;
		cycle_count=5;
		total_offset=0;

		negot_offset=4;
		negot_limit=1;

		passive=0;
		
		UI::get(last_offset, set, "offset", UI::compulsory);
		UI::get(passive, set, "passive", UI::optional);

		for (int i=0;i<lanes.length();i++) {
			for (int j=0;j<lanes(i).outputs.length();j++) {
				if (lanes(i).outputs(j)!="DUMMY_DET") {
					rv_exp=RV(lanes(i).outputs(j)+"-"+name+"_"+to_string(i),3);
					rv_outputs.add(rv_exp);
				}
			}
		}
		outputs.set_size(rv_outputs._dsize());	

		log_level[logoffset]=true;
	}
\end{lstlisting}

Dal�� volanou funkc� v agentech je \texttt{adapt()}. Podobn� jako \texttt{from_setting()} nejprve spou�t� stejnomenou funkci u sv�ho p�edka. V t� prob�h� vypln�n� vektor� \texttt{inputs} a \texttt{queues} daty z Aimsunu, ulo�en�mi ve vektoru \texttt{glob_dt}. �daje z \texttt{queues} se p�edaj� p��slu�n�m \texttt{LaneHandler}�m. D�le je nastaven \texttt{planned_offset} na hodnotu z�skanou v minul�m cyklu a stavov� prom�nn� jsou nastaveny do sv�ch v�choz�ch hodnot.

\begin{lstlisting}[caption=Funkce adapt(), label=lst:adapt, firstnumber=415]
	void adapt(const vec &glob_dt) {
		BaseTrafficAgent::adapt(glob_dt);
			
		for (int i=0;i<lanehs.length();i++) {
			lanehs(i)->queue=queues(lanehs(i)->queue_index);		
		}

		planned_offset=last_offset;
		
		//set state variables to default values
		final_state=false;
		new_stable_state=false;
		send_requests=false;
		need_exps=true;
		negot_offset=4;
	}
\end{lstlisting}

Funkce \texttt{recieve} zpracov�v� p�ijat� zpr�vy od ostatn�ch agent�. Na za��tku je p�ijat� zpr�va rozd�lena do jednotliv�ch prom�nn�ch.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}, inicializace}, label=lst:recieveInit, firstnumber=491]
	void receive(const Setting &msg){
		string what;
		string to;
		string from;
		vec value;
		RV *rv;
		
		UI::get(what, msg, "what", UI::compulsory);
		UI::get(to, msg, "to", UI::compulsory);
		UI::get(from, msg, "from");
		UI::get(rv, msg, "rv");
		UI::get(value, msg, "value");
\end{lstlisting}

D�le se �innost li�� podle �p�edm�tu� zpr�vy, tedy podle �et�zce ulo�en�ho v ��sti \texttt{what}. V p��pad� p�ijet� ��dosti o o�ek�van� �asy p��jezd� je jen ulo�eno jm�no odes�latele do seznamu �adatel� \texttt{requesters}.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveExpReq, firstnumber=last]
		if (what=="expected_times_request"){ 
			requesters.push_back(from);
		} 
				
\end{lstlisting}

Pokud jsou naopak obsahem p�ijat� zpr�vy o�ek�van� �asy p��jezd� automobil� od souseda, aktivn� agent najde nov� optim�ln� offset pro sv�j sign�ln� pl�n a spo��t� \texttt{rating}, pasivn� provede jen tento v�po�et. Na konci je stavov� prom�nn� nastavena \texttt{new_stable_state} na \texttt{true}, co� ur�uje dal�� �innost agent ve f�zi vys�l�n� zpr�v.

\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveNewExp, firstnumber=last]
		else if (what=="new_expected_cars") {
			rv_recieved_exps=*rv;
			recieved_exps=value;
			
			if (!passive) {
				planned_offset=find_best_offset(planned_offset,8);
				planned_offset=normalize_offset(planned_offset);
			}

			planned_rating=count_rating(planned_offset, recieved_exps, rv_recieved_exps);
			
			// we have new stable state to broadcast
			new_stable_state=true;
		}
\end{lstlisting}
Obdr�en� zpr�vy s hlavi�kou �\texttt{stable_state}� znamen�, �e n�kter� ze soused� zm�nil sv� nastaven� offsetu a zas�l� tedy nov� hodnoty o�ek�van�ch p��jezd�. Pokud je aktu�ln� hodnota \texttt{negot_offset} v�t�� nebo rovna \texttt{negot_limit}, zkou�� aktivn�, kter� z hodnot $0$, $+\mathtt{negot\_offset}$ nebo $-\mathtt{negot\_offset}$ by po p�i�ten� k sousedov� offsetu znamenala nejlep�� rating. Hodnota \texttt{negot_offset} je sn�ena na polovinu a je p�ipraveno odesl�n� ��dosti pro souseda. Pokud Pokud byla prom�nn� \texttt{negot_offset} ji� ni��� ne� ne� \texttt{negot_limit}, p�ep�n� se agent do kone�n�ho stavu, neb ji� nem� dal�� prostor k vyjedn�v�n� se sousedy. 
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveStable, firstnumber=last]
		else if (what=="stable_state") {
			rv_recieved_exps=*rv;
			recieved_exps=value;

			planned_rating=count_rating(planned_offset, recieved_exps, rv_recieved_exps);

			if (!passive) {
				for (int i=0;i<neighbours.length();i++) {
					rv_change_request.add(RV(neighbours(i)+"_change",2));
					change_request.set_size(rv_change_request._dsize()); 
					ivec ind=RV(neighbours(i)+"_change",2).dataind(rv_change_request);
					
					// offset change
					change_request(ind(0))=find_best_exps(negot_offset,neighbours(i),rating_change);
					// rating change
					change_request(ind(1))=rating_change;
				}

				if (negot_offset>=negot_limit) { 
					negot_offset/=2;
					send_requests=true;
				}
				else {
					final_state=true;
				}
			}
			else {
				final_state=true;
			}
		}
\end{lstlisting}
P�i p�ijet� se zpr�vy s ��dost� o zm�nu offsetu agent zkoum�, zda je sou�et zm�ny hodnocen� po aplikaci navr�en�ho offsetu a zlep�en� hodnocen� u souseda, kter� od zm�ny offsetu o�ek�v�, v�t�� ne� nula. Takov�to zm�na se p�ij�m� a podle n� se upravuje \texttt{planned_offset}. V ka�d�m p��pad� se agent p�iprav� na zasl�n� aktu�ln�ch hodnot o�ek�van�ch p��jezd�.
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveOffChange, firstnumber=last]
		else if (what=="offset_change_request") {
			double final_rating_diff;

			rv_recieved_changes=*rv;
			recieved_changes=value;

			for (int i=0;i<rv_recieved_changes.length();i++) {

				ivec ind=RV(rv_recieved_changes.name(i),2).dataind(rv_recieved_changes);

				final_rating_diff=-planned_rating+count_rating(planned_offset+(int)recieved_changes(ind(0)), recieved_exps, rv_recieved_exps)+recieved_changes(ind(1));
				if (final_rating_diff>=0) {
					planned_offset+=(int)recieved_changes(ind(0));
					planned_offset=normalize_offset(planned_offset);
					planned_rating+=final_rating_diff;
				}
			}

			new_stable_state=true;
		}
\end{lstlisting}
Pokud p�ijde zpr�va s p�edm�tem, kter� \texttt{GreenWaveTrafficAgent} neum� zpracovat, p�ed�v� ji p�edkovi. Kdyby se stalo, �e ani ten si se zpr�vou neporad�, po�le se zpr�va jeho p�edkovai (tedy t��d� \texttt{bdm::Participant}), kter� v takov�m p��pad� vyvol� varov�n� o nezpracovateln� zpr�v�.
\begin{lstlisting}[caption={Fragment funkce \texttt{recieve()}}, label=lst:recieveBase, firstnumber=last]
		else {
			BaseTrafficAgent::receive(msg);
		}
	}
\end{lstlisting}

Funkce \texttt{broadcast()} vys�l� zpr�vy do fronty zpr�v a to v z�vislosti na hodnot�ch agentov�ch stavov�ch prom�nn�ch. Pokud nen� pr�zdn� seznam \texttt{requests}, sestav� odpov�� pro ka�d�ho z agent� uveden�ho v seznamu a ten n�sledn� vypr�zdn�. D�le pak za ka�dou ze stavov�ch prom�nn�ch, kter� maj� hodnotu \texttt{true} sestav� p��slu�nou zpr�vu a hodnotu zm�n� na \texttt{false}. 

\begin{lstlisting}[caption=Funkce broadcast(), label=lst:broadcast, firstnumber=429]
	void broadcast(Setting& set){

		//ask neighbours for exptected arrive times
		if (need_exps) {
			for (int i=0; i<neighbours.length(); i++){
				Setting &msg =set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save (name,msg,"from");
				UI::save ( (string)"expected_times_request", msg, "what");
			}
			need_exps=false;
		}

		// broadcast expected cars
		if (!requesters.empty()) {
			double a;
			expected_cars();
			do {
				Setting &msg =set.add(Setting::TypeGroup);
				UI::save ( requesters.back(), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"new_expected_cars", msg, "what");
				UI::save ( &(rv_outputs), msg, "rv");
				UI::save ( outputs, msg, "value");
				requesters.pop_back();
				a=outputs (10);
			} while (!requesters.empty());			
		}

		// broadcast new stable state (new stable expectations)
		if (new_stable_state) {
			expected_cars();
			for (int i=0;i<neighbours.length();i++) {
				Setting &msg = set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"stable_state", msg, "what");
				UI::save ( &(rv_outputs), msg, "rv");
				UI::save ( outputs, msg, "value");
			}
			new_stable_state=false;
		}

		// broadcast requests to change offset(s)
		if (send_requests) {
			for (int i=0;i<neighbours.length();i++) {
				Setting &msg = set.add(Setting::TypeGroup);
				UI::save ( neighbours(i), msg, "to");
				UI::save ( name, msg, "from");
				UI::save ( (string)"offset_change_request", msg, "what");
				UI::save ( &(rv_change_request), msg, "rv");
				UI::save ( change_request, msg, "value");
			}
			send_requests=false;
		}
	
		// reached final offset.
		if (final_state) {
			final_state=false;
		}
	}

\end{lstlisting}

Ve funkci \texttt{act()} se spo��tan� hodnota \texttt{planned_offset} p�i��t� k hodnot� prom�nn� \texttt{total_offset} a to a� do chv�le, ne� je v n�m tolik hodnot, kolik stanovuje limit \texttt{cycle_count}. Kdy� se tohoto limitu dos�hne, vyd�l� se \texttt{total_offset} t�mto limitem, ��m� se z�sk� pr�m�rn� hodnotn� offsetu z posledn�ch cykl�. Pr�m�r se pak znormalizuje, aby byl z intervalu $\left<0;T_c\right>$ a ulo�� se do vektoru $u_t$, p�edstavovan�m prom�nou \texttt{global_ut}. T�m se tato hodnota dostane k �adi�i k�i�ovatky.
\begin{lstlisting}[caption=Funkce act(), label=lst:act, firstnumber=615]
	void act(vec &glob_ut){
		if (negot_cycle==cycle_count) {
			vec action;
			action.set_size(rv_action._dsize());
		
			ivec index = RV(name+"_offset",1).dataind(rv_action);

			action(index(0))=normalize_offset(total_offset/cycle_count, false);
			action2ds.filldown(action,glob_ut);

			total_offset=0;
			negot_cycle=1;
		}
		else {
			total_offset+=planned_offset;
			negot_cycle++;
		}
		last_offset=planned_offset;
	}
\end{lstlisting}

O z�pis aktu�ln�ch hodnot do logovac�ho souboru se star� \texttt{log_write()}. Ukl�d� se dvouslo�kov� vektor. Prvn� prvek obsahuje vypo��tan� offset \texttt{planned_offset}, druh� jeho hodnocen� \texttt{planned_rating}.

\begin{lstlisting}[caption=Funkce log_write(), label=lst:logwrite, firstnumber=644]
	void log_write() const {
		if (log_level[logoffset]){
			vec offset_vec(2);
			offset_vec(0)=planned_offset;
			offset_vec(1)=planned_rating;
			log_level.store(logoffset, offset_vec);			
		}
	} 
\end{lstlisting}
Posledn� volan� ve�ejn� funkce agenta je \texttt{step()}, kter� jen posouv� intern� ukazatel �asu v agentovi o d�lku kroku simulace.
\begin{lstlisting}[caption=Funkce step(), label=lst:step, firstnumber=635]
	void step() {
		actual_time+=step_length;
	}
\end{lstlisting}

