root/applications/doprava/texty/novotny_vyzk_LQ/Implementation.tex @ 1446

\chapter{Implementace}

\section{Seznam proměnných}
% Všechny proměnné jsou zavedeny pro každého agenta reprezentujícího jednu křižovatku zvlášť
% a jsou označeny indexem $i$ signální skupiny. Tavždy ovládá jeden jízdní pruh. Pokud jsou bez indexu,
% jedná se o proměnnou agenta, případně oblasti simulace.

\begin{tabular}{ccp{5cm}p{5cm}}
  \textbf{V textu} & \textbf{V programu} & \textbf{Název} & \textbf{Popis} \\
  $T \in \mathbb{N}$ & \texttt{T} & Vzorkovací perioda & ...\\
  $C \in \mathbb{N}$ & \texttt{Tc} & Délka cyklu & ... \\
  $S = 0,5$ & \texttt{Tc} & Saturovaný tok & Maximální počet vozidel, která projedou křižovatkou za sekundu \\
  $L \in \mathbb{R}^+$ &  \texttt{L} & Ztrátový čas & Čas potřebný k vyklizení křižovatky mezi dvěma fázemi\\ 
  $J = \{j_1, ..., j_n\}$ &  & Množina signálních skupin &  \\
  $J_A \subset J$ & \texttt{} & Množina signálních skupin agenta $A$ & Skupiny náležící jednomu agentovi \\
  $I_j \subset J$ & \texttt{} & Množina vstupů signální skupiny & Signální skupiny ostatních agentů ústících do příslušné skupiny $g$ \\
  $g_j^N \in <0,1>$ & & Nominální poměr zelené & Defi novaný poměr fází \\
  $g_j(t) \in <0,1>$ & & Efektivní poměr zelené & Část z délky cyklu, kdy je signální skupina  průjezdná \\
  $i_j(t) \in \mathbb{R}^+$ & \texttt{i\_g} & Hustota vstupů & Počet přijíždějících vozidel do pruhu signální skupiny za jednotku času \\
  $o_j(t) \in \mathbb{R}^+$ & \texttt{} & Hustota výstupů & Počet vyjíždějících vozidel z pruhu signální skupiny za jednotku času \\
  $q_j(t) \in \mathbb{N}_0^+$ & \texttt{} & Fronta & Počet vozidel jedoucí menší rychlostí než $3,6 km/h$ \\
  $\alpha_{j,k}  \in <0,1>$ & \texttt{} & Odbočovací poměr z $j$ do $k$ &  
\end{tabular}

\section{Použitá metoda}
Účelem této práce je řídit provoz pomocí nastavení optimální délky cyklu za použití multiagentního systému, kde
každý agent ovládá signální skupiny jedné křižovatky a jsou mu dostupné příslušné údaje.
Jako vhodná metoda bylo zvoleno LQ řízení, které se snaží minimalizovat fronty a penalizovat délku cyklu.

\subsection{Přechodové vztahy}
Jako údaj popisující stav systému byla zvolena délka fronty $q_j(t)$, což je počet aut v jízdním pruhu jedoucích 
méně než 3,6 km/h. Pro danou frontu v čase $t+1$ platí zřejmě vztah
\begin{equation}\label{eq:my_trans_01}
 q_j(t+1) = q_j(t) + T ( i_j(t) - o_j(t) )
\end{equation}, kde hustota vstupu $i_j(t)$ je součtem výstupů sousedů pronásobený odbočovacími poměry,
případně vstupu do systému $i_{j,0}(t)$, pokud se jedná o koncové rameno řízené oblasti, tedy
\begin{equation}
  i_j(t) = i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} o_k(t)
\end{equation}.
Křižovtkou z daného jízdního pruhu v průjezdné fázi projede $S$ vozidel za sekundu, kde 
délka průjezdné fáze závisí na nastaveném poměru a délce cyklu. Před přechodem do nové
fáze signálího plánu je potřeba vklidit křižovatku, což vede ke ztrátovému času $L$, který
se projeví vždy jednou za cyklus. Efektivní délka zelené je tedy
\begin{equation}
 g_j(t) = (C(t) - L) g_j^N
\end{equation}
a pro hustotu výstupu platí
\begin{equation}
 o_j(t) = \frac{S_j g_j(t)}{C(t)} = S_j g_j^N \left( 1 - LC(t)^{-1} \right)
\end{equation}. Rovnice \ref{eq:my_trans_01} tedy přechází do tvaru
\begin{equation}\label{eq:my_trans_02}
 q_j(t+1) = q_j(t) + T \left( i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} S_k g_k^N \left( 1 - LC(t)^{-1} \right)  - S_j g_j^N \left( 1 - LC(t)^{-1} \right) \right)
\end{equation}.
Pokud budeme podobně jako v \cite{6_tuc_lq} předpokládat existenci nominální délky cyklu $C^N$, při níž se
nemění délka fronty, platíc(
\begin{equation}\label{eq:my_trans_nom}
 0 = T \left( i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} S_k g_k^N \left( 1 - LC^{N -1} \right)  - S_j g_j^N \left( 1 - LC^{N -1} \right) \right)
\end{equation}. Odečtením rovnice \ref{eq:my_trans_nom} od \ref{eq:my_trans_02} dostaneme
\begin{equation}\label{eq:my_trans_03}
 q_j(t+1) = q_j(t) + T \left( - \sum_{k \in I_j} \alpha_{k,j} S_k g_k^N  + S_j g_j^N  \right) L \Delta C^{-1}(t)
\end{equation}, kde $ \Delta C^{-1}(t) = C(t)^{-1} - C^{N -1}$. Pro ramena $j \in J_A$ náležící agentovi $A$ se
tedy rovnice pro fronty dají zapsat maticově ve tvaru
\begin{equation}\label{eq:my_trans_mat}
 \vec{q}(t+1) = A \vec{q}(t) + B \Delta C^{-1}(t) 
\end{equation}

Kostantni saturovany tok neni optimalni, pouzije aprox podle Pecherkove (viz bak.), 
prujezd odpovida bud sat. toku, pokud neodjede cela fronta, nebo je primo umerny
fronte (+ prijezdum). prolozi se funkci a aprox se primkou podle hodnoty fronty v case t.
Napocte se rizen pro horizont a podle vyvoje fronty se prepocte misto pro prolozeni pri


\subsubsection{Model toku}
V článku \cite{6_tuc_lq} se úbytek vozidel modeluje podle rovnice \ref{eq:tuc_u}, kde je uvažován
tok vozidel křižovatkou za jednotku času jako konstanta $S$, což je saturovaný tok. Tento vztah
platí pouze když je příslušný pruh naplněn vozidly do té míry, že křižovatkou projede maximální
možný počet vozidel. To však neplatí, pokud není pruh dostatečně vytížen, například pokud se zmenší
délka fronty v nějaký časový okamžik na nulu. Pokud je vytížení menší je tok lineárně závislý na součtu
fronty $q(t)/T$ a počtu vstupujících vozidel $i(t)$. Pro teoretickou hodnotu toku $S$ tedy dostáváme vztah
\begin{equation}\label{eq:teor_tok}
 S_{teor}(q(t) + i(t)) = \left\{
                        \begin{array}{lr}
                          \frac{q(t)}{T} + i(t) & \frac{q(t)}{T} + i(t) <= S_{max} \\
                          S_{max} &  \frac{q(t)}{T} + i(t) > S_{max}
                        \end{array}
                  \right.
\end{equation}
. tento vztah vyjadřuje to, že pokud je fronta plus přírůstrek vozidel ve vzorkovací periodě
$(q(t), i(t)T)$ menší než maximální počet vozidel, který je křižovatka za periodu $T$ schopna
propustit $(T S_{max})$, projedou všechna vozidla. Abychom se vyhnuli podmínce podle $S_{max}$,
aproximuje se tento vztah funkcí
\begin{equation}\label{eq:exp_tok}
 S_{exp}(q(t), i(t)) = S_{max} \left(1 - e^{- \frac{1}{S_{max}} \left( \frac{q(t)}{T} + i(t) \right) } \right)
\end{equation}
, která splňuje podmínku 
\begin{equation} 
\frac{ dS_{exp} }{d(q/T+i)}(0,0) = 1  
\end{equation}
, tedy při malé frontě a hustotě provozu
je přírůstek toku roven $q/T+i$, a podmínku 
\begin{equation}
\lim_{q/T+i\to\infty} S_{exp} = S_{max}  
\end{equation}
, tedy při velké frontě a hustotě provozu
se tok blíží konstantě $S_{max}$. Pro malý časový interval můžeme tuto funkci dále zjednodušit na lineární vztah
\begin{equation}\label{eq:lin_tok}
 S(q(t)) = \sigma(q(t)/T + i_0)
\end{equation}
, kde je $i_0 = i(0)$ a
\begin{equation}
 \sigma = \frac{ dS_{exp} }{d(q/T+i)}(q(0),i(0))
\end{equation}
\\
vlozit graf s ruznymi S
\\

\subsubsection{Přechodové vztahy s proměnným tokem}
Pro vyjádření přechodových vzthů použijeme lineární odel toku a rovnice \ref{eq:my_trans_02}
přejde na tvar
\begin{equation}
 q_j(t+1) = q_j(t) + T \left( i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} S_k(q_k(t)) g_k^N \left( 1 - LC(t)^{-1} \right)  - S_j(q_j(t)) g_j^N \left( 1 - LC(t)^{-1} \right) \right)
\end{equation}
, a po dosazení \ref{eq:lin_tok} dostaneme
\begin{equation}
 q_j(t+1) = q_j(t) + T \left( \begin{array}{c}
                                i_{j,0}(t) + \\
                                + \sum_{k \in I_j} \alpha_{k,j} \delta_k(q_k(t) T^{-1} + i_{0,k}) g_k^N \left( 1 - LC(t)^{-1} \right) - \\
                                - \delta_j(q_j(t) T^{-1} + i_{0,j}) g_j^N \left( 1 - LC(t)^{-1} \right)
                              \end{array}
  \right)
\end{equation}

\begin{equation}\label{eq:my_trans_mod_tok_03}
 q_j(t+1) = q_j(t) + T \left( \begin{array}{c}
                                i_{j,0}(t) + \\
                                + \sum_{k \in I_j} \alpha_{k,j} \delta_k g_k^N T^{-1} q_k(t)  - \delta_j g_j^N T^{-1} q_j(t) + \\
                                + \sum_{k \in I_j} \alpha_{k,j} \delta_k i_{0,k} g_k^N - \delta_j i_{0,j} g_j^N - \\
                                - \sum_{k \in I_j} \alpha_{k,j} \delta_k g_k^N L T^{-1} q_k(t) C(t)^{-1} + \delta_j  g_j^N L T^{-1} q_j(t) C(t)^{-1} - \\                               
                                - \sum_{k \in I_j} \alpha_{k,j} \delta_k i_{0,k} g_k^N L C(t)^{-1} + \delta_j i_{0,j} g_j^N L C(t)^{-1}                                 
                              \end{array}
  \right)
\end{equation}

. Pokud budeme podobně jako v rovnici \ref{eq:my_trans_nom} uvažovat nominální $C^N$, pro které se $q(t+1)$ rovná $q(t)$,
dostaneme dosazením $\Delta C^{-1}(t) = C(t)^{-1} - C^{N -1} $ do \ref{eq:my_trans_mod_tok_03} rovnici

\begin{equation}\label{eq:my_trans_mod_tok_04}
\begin{array}{ccc}
 q_j(t+1) &= q_j(t) +& L \left( \delta_j  g_j^N q_j(t)   - \sum_{k \in I_j} \alpha_{k,j} \delta_k g_k^N q_k(t) \right) C(t)^{-1} +\\
  & & + L T \left( \delta_j i_{0,j} g_j^N - \sum_{k \in I_j} \alpha_{k,j} \delta_k i_{0,k} g_k^N  \right) C(t)^{-1} 
\end{array} 
\end{equation}




\subsection{Minimalizační kritérium}
Podobně jako v předchozí kapitole, minimalizovat kvaratické kritérium $J$.
Minimalizaci budeme provádět v proměnných $\Delta C(t)$ pro časový horizont $h$,
tedy pro vektory $\Delta C(t_0), \Delta C(t_0 + 1), ..., \Delta C(t_0 + h)$. Pro zpřehlednění
zápisu položíme bez újmy na obecnosti $t_0 = 0$.
Kvadratické kritérium
ve tvaru
\begin{equation}\label{eq:J}
 J = \sum_{t=0}^h q(t)^T Q q(t) + \Delta C(t)^T R \Delta C(t)
\end{equation}, 
kde $Q$ a $R$ jsou diagonální pozitivně definitní matice vah,
rozepíšeme pomocí vztahu
\begin{equation}\label{eq:prechod}
 q(t+1) = Aq(t) + Bq(t)
\end{equation} a budeme minimalizovat pro jednotlivá $t$ podle  $\Delta C(t)$.
$\Delta C(h)$ se v kritériu vyskytuje pouze jako člen
\begin{equation}
\Delta C(h)^T R \Delta C(h)
\end{equation}
a tedy musí být $\Delta C(h) 0$. $\Delta C(h - 1)$ se vyskytuje ve členech
\begin{equation}
  \Delta C(h - 1)^T R \Delta C(h - 1) + (q(h - 1)^T A^T + \Delta C(h - 1)^T B^T ) Q ( A q(h - 1) + B \Delta C(h - 1))
\end{equation}
, což lze pomocí složených vektorů a matic přepsat do tvaru
\begin{equation} \label{eq:J_sloz}
 (\Delta C(h-1)^T, q(h - 1)^T ) 
  \left( \begin{array}{cc}
          B^T \sqrt{Q} & \sqrt{R} \\
          A^T \sqrt{Q} & 0
          \end{array}
  \right)  
  \left( \begin{array}{cc}
           \sqrt{Q} B & \sqrt{Q} A \\
          \sqrt{R} & 0
          \end{array}
  \right)
  \left( \begin{array}{c}
            \Delta C(h-1) \\
            q(h - 1)
          \end{array}
  \right)
\end{equation}, kde $\sqrt{Q}$ je matice, pro níž platí $\sqrt{Q} \sqrt{Q} = Q$.
Složenou matici
\begin{equation}
  \left( \begin{array}{cc}
          B^T \sqrt{Q} & \sqrt{R} \\
          A^T \sqrt{Q} & 0
          \end{array}
  \right)  
  \left( \begin{array}{cc}
           \sqrt{Q} B & \sqrt{Q} A \\
          \sqrt{R} & 0
          \end{array}
  \right) = 
  \left( \begin{array}{cc}
          B^T Q B + R & B^T Q A \\
          A^T Q B & A^T Q A
          \end{array}
  \right)
\end{equation}
můžeme pomocí Choleského dekompozici na součin dolní a horní trojúhelníkové matice.
Člen \ref{eq:J_sloz} poté přejde na tvar
\begin{equation}
 (\Delta C(h-1)^T, q(h - 1)^T ) 
  \left( \begin{array}{cc}
          L_q^T & 0 \\
          L^T & L_C^T
          \end{array}
  \right)  
  \left( \begin{array}{cc}
          L_C & L \\
          0 & L_q
          \end{array}
  \right)
  \left( \begin{array}{c}
            \Delta C(h-1) \\
            q(h - 1)
          \end{array}
  \right)
\end{equation}, který můžeme dále upravit na
\begin{equation}
 ( L_C \Delta C(h-1) +  L_q q(h-1) )^T ( L_C \Delta C(h-1) +  L_q q(h-1) ) + q(h-1)^T L_q^T L_q q(h-1) 
\end{equation}. Pokud tento člen chceme minimalizovat v proměnné $q(h-1)$, musí nutně platit
\begin{equation}
 \Delta C(h-1) = - L_C^{-1} L q(h-1)
\end{equation}. Zbývající nenulová část $q(h-1)^T L_q^T L_q q(h-1) $ lze přepsat pomocí rovnice \ref{eq:prechod} do tvaru 
\begin{equation}
 q(h-1)^T L_q^T L_q q(h-1) = ( A q(h-2) + B \Delta C(h-2) )^T L_q^T L_q ( A q(h-2) + B \Delta C(h-2) )
\end{equation}, kde se vyskytuje $\Delta C(t)$ pouze pro $t = h-2$. Minimalizace přes
$\Delta C(h-2)$ bude probíhat analogicky, pouze se matice $Q$ nahradí maticí 
\begin{equation}
\widetilde{Q} = Q + L_q^T L_q
\end{equation}, která zahrnuje zbytek po členu s $\Delta C(h-1)$.
Pro další $\Delta C(t)$ se pouze upraví matice $\widetilde{Q}$ výše popsaným způsoen a minimalizace již probíhá stejně.\\

DOTAZY:\\
QR - obecne nerozklada na trojuhelnikove matice $L L^{-1}$, ale na jednu troj a na druhou ortogonal.
Cholesky rozklada pouze pozitivně definitní matice - je pozitivně definitní? dokazovat? pouzit QR?
Matice L se v tomto pripade meni v kazdem kroku. V poradku?











\section{Simulace}

\subsection{Simulátor AIMSUN}

\subsection{Oblast simulace}