[1419] | 1 | \chapter{Implementace} |
---|
| 2 | |
---|
| 3 | \section{Seznam proměnných} |
---|
| 4 | Všechny proměnné jsou zavedeny pro každého agenta reprezentujícího jednu křižovatku zvlášť |
---|
| 5 | a jsou označeny indexem $i$ signální skupiny. Tavždy ovládá jeden jízdní pruh. Pokud jsou bez indexu, |
---|
| 6 | jedná se o proměnnou agenta, případně oblasti simulace. |
---|
| 7 | |
---|
| 8 | \begin{tabular}{ccp{5cm}p{5cm}} |
---|
| 9 | \textbf{V textu} & \textbf{V programu} & \textbf{Název} & \textbf{Popis} \\ |
---|
| 10 | $T \in \mathbb{N}$ & \texttt{T} & Vzorkovací perioda & ...\\ |
---|
| 11 | $C \in \mathbb{N}$ & \texttt{Tc} & Délka cyklu & ... \\ |
---|
| 12 | $S = 0,5$ & \texttt{Tc} & Saturovaný tok & Maximální počet vozidel, která projedou křižovatkou za sekundu \\ |
---|
| 13 | $L \in \mathbb{R}^+$ & \texttt{L} & Ztrátový čas & Čas potřebný k vyklizení křižovatky mezi dvěma fázemi\\ |
---|
| 14 | $J = \{j_1, ..., j_n\}$ & & Množina signálních skupin & \\ |
---|
| 15 | $J_A \subset J$ & \texttt{} & Množina signálních skupin agenta $A$ & Skupiny náležící jednomu agentovi \\ |
---|
| 16 | $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$ \\ |
---|
| 17 | $g_j^N \in <0,1>$ & & Nominální poměr zelené & Defi novaný poměr fází \\ |
---|
| 18 | $g_j(t) \in <0,1>$ & & Efektivní poměr zelené & Část z délky cyklu, kdy je signální skupina průjezdná \\ |
---|
| 19 | $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 \\ |
---|
| 20 | $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 \\ |
---|
| 21 | $q_j(t) \in \mathbb{N}_0^+$ & \texttt{} & Fronta & Počet vozidel jedoucí menší rychlostí než $3,6 km/h$ \\ |
---|
| 22 | $\alpha_{j,k} \in <0,1>$ & \texttt{} & Odbočovací poměr z $j$ do $k$ & |
---|
| 23 | \end{tabular} |
---|
| 24 | |
---|
| 25 | \section{Použitá metoda} |
---|
| 26 | Účelem této práce je řídit provoz pomocí nastavení optimální délky cyklu za použití multiagentního systému, kde |
---|
| 27 | každý agent ovládá signální skupiny jedné křižovatky a jsou mu dostupné příslušné údaje. |
---|
| 28 | Jako vhodná metoda bylo zvoleno LQ řízení, které se snaží minimalizovat fronty a penalizovat délku cyklu. |
---|
| 29 | |
---|
| 30 | \subsection{Přechodové vztahy} |
---|
| 31 | 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 |
---|
| 32 | méně než 3,6 km/h. Pro danou frontu v čase $t+1$ platí zřejmě vztah |
---|
| 33 | \begin{equation}\label{eq:my_trans_01} |
---|
| 34 | q_j(t+1) = q_j(t) + T ( i_j(t) - o_j(t) ) |
---|
| 35 | \end{equation}, kde hustota vstupu $i_j(t)$ je součtem výstupů sousedů pronásobený odbočovacími poměry, |
---|
| 36 | případně vstupu do systému $i_{j,0}(t)$, pokud se jedná o koncové rameno řízené oblasti, tedy |
---|
| 37 | \begin{equation} |
---|
| 38 | i_j(t) = i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} o_k(t) |
---|
| 39 | \end{equation}. |
---|
| 40 | Křižovtkou z daného jízdního pruhu v průjezdné fázi projede $S$ vozidel za sekundu, kde |
---|
| 41 | délka průjezdné fáze závisí na nastaveném poměru a délce cyklu. Před přechodem do nové |
---|
| 42 | fáze signálího plánu je potřeba vklidit křižovatku, což vede ke ztrátovému času $L$, který |
---|
| 43 | se projeví vždy jednou za cyklus. Efektivní délka zelené je tedy |
---|
| 44 | \begin{equation} |
---|
| 45 | g_j(t) = (C(t) - L) g_j^N |
---|
| 46 | \end{equation} |
---|
| 47 | a pro hustotu výstupu platí |
---|
| 48 | \begin{equation} |
---|
| 49 | o_j(t) = \frac{S_j g_j(t)}{C(t)} = S_j g_j^N \left( 1 - LC(t)^{-1} \right) |
---|
| 50 | \end{equation}. Rovnice \ref{eq:my_trans_01} tedy přechází do tvaru |
---|
| 51 | \begin{equation}\label{eq:my_trans_02} |
---|
| 52 | 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) |
---|
| 53 | \end{equation}. |
---|
| 54 | Pokud budeme podobně jako v \cite{6_tuc_lq} předpokládat existenci nominální délky cyklu $C^N$, při níž se |
---|
| 55 | nemění délka fronty, platíc( |
---|
| 56 | \begin{equation}\label{eq:my_trans_nom} |
---|
| 57 | 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) |
---|
| 58 | \end{equation}. Odečtením rovnice \ref{eq:my_trans_nom} od \ref{eq:my_trans_02} dostaneme |
---|
| 59 | \begin{equation}\label{eq:my_trans_03} |
---|
| 60 | 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) |
---|
| 61 | \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 |
---|
| 62 | tedy rovnice pro fronty dají zapsat maticově ve tvaru |
---|
| 63 | \begin{equation}\label{eq:my_trans_mat} |
---|
| 64 | \vec{q}(t+1) = A \vec{q}(t) + B \Delta C^{-1}(t) |
---|
| 65 | \end{equation} |
---|
| 66 | |
---|
| 67 | Kostantni saturovany tok neni optimalni, pouzije aprox podle Pecherkove (viz bak.), |
---|
| 68 | prujezd odpovida bud sat. toku, pokud neodjede cela fronta, nebo je primo umerny |
---|
| 69 | fronte (+ prijezdum). prolozi se funkci a aprox se primkou podle hodnoty fronty v case t. |
---|
| 70 | Napocte se rizen pro horizont a podle vyvoje fronty se prepocte misto pro prolozeni pri |
---|
| 71 | |
---|
| 72 | |
---|
| 73 | \subsubsection{Model toku} |
---|
| 74 | V článku \cite{6_tuc_lq} se úbytek vozidel modeluje podle rovnice \ref{eq:tuc_u}, kde je uvažován |
---|
| 75 | tok vozidel křižovatkou za jednotku času jako konstanta $S$, což je saturovaný tok. Tento vztah |
---|
| 76 | platí pouze když je příslušný pruh naplněn vozidly do té míry, že křižovatkou projede maximální |
---|
| 77 | možný počet vozidel. To však neplatí, pokud není pruh dostatečně vytížen, například pokud se zmenší |
---|
| 78 | 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 |
---|
| 79 | fronty $q(t)/T$ a počtu vstupujících vozidel $i(t)$. Pro teoretickou hodnotu toku $S$ tedy dostáváme vztah |
---|
| 80 | \begin{equation}\label{eq:teor_tok} |
---|
| 81 | S_{teor}(q(t) + i(t)) = \left\{ |
---|
| 82 | \begin{array}{lr} |
---|
| 83 | \frac{q(t)}{T} + i(t) & \frac{q(t)}{T} + i(t) <= S_{max} \\ |
---|
| 84 | S_{max} & \frac{q(t)}{T} + i(t) > S_{max} |
---|
| 85 | \end{array} |
---|
| 86 | \right. |
---|
| 87 | \end{equation} |
---|
| 88 | . tento vztah vyjadřuje to, že pokud je fronta plus přírůstrek vozidel ve vzorkovací periodě |
---|
| 89 | $(q(t), i(t)T)$ menší než maximální počet vozidel, který je křižovatka za periodu $T$ schopna |
---|
| 90 | propustit $(T S_{max})$, projedou všechna vozidla. Abychom se vyhnuli podmínce podle $S_{max}$, |
---|
| 91 | aproximuje se tento vztah funkcí |
---|
| 92 | \begin{equation}\label{eq:exp_tok} |
---|
| 93 | S_{exp}(q(t), i(t)) = S_{max} \left(1 - e^{- \frac{1}{S_{max}} \left( \frac{q(t)}{T} + i(t) \right) } \right) |
---|
| 94 | \end{equation} |
---|
| 95 | , která splňuje podmínku |
---|
| 96 | \begin{equation} |
---|
| 97 | \frac{ dS_{exp} }{d(q/T+i)}(0,0) = 1 |
---|
| 98 | \end{equation} |
---|
| 99 | , tedy při malé frontě a hustotě provozu |
---|
| 100 | je přírůstek toku roven $q/T+i$, a podmínku |
---|
| 101 | \begin{equation} |
---|
| 102 | \lim_{q/T+i\to\infty} S_{exp} = S_{max} |
---|
| 103 | \end{equation} |
---|
| 104 | , tedy při velké frontě a hustotě provozu |
---|
| 105 | se tok blíží konstantě $S_{max}$. Pro malý časový interval můžeme tuto funkci dále zjednodušit na lineární vztah |
---|
| 106 | \begin{equation}\label{eq:lin_tok} |
---|
| 107 | S(q(t)) = \sigma(q(t)/T + i_0) |
---|
| 108 | \end{equation} |
---|
| 109 | , kde je $i_0 = i(0)$ a |
---|
| 110 | \begin{equation} |
---|
| 111 | \sigma = \frac{ dS_{exp} }{d(q/T+i)}(q(0),i(0)) |
---|
| 112 | \end{equation} |
---|
| 113 | \\ |
---|
| 114 | vlozit graf s ruznymi S |
---|
| 115 | \\ |
---|
| 116 | |
---|
| 117 | \subsubsection{Přechodové vztahy s proměnným tokem} |
---|
| 118 | Pro vyjádření přechodových vzthů použijeme lineární odel toku a rovnice \ref{eq:my_trans_02} |
---|
| 119 | přejde na tvar |
---|
| 120 | \begin{equation} |
---|
| 121 | 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) |
---|
| 122 | \end{equation} |
---|
| 123 | , a po dosazení \ref{eq:lin_tok} dostaneme |
---|
| 124 | \begin{equation} |
---|
| 125 | q_j(t+1) = q_j(t) + T \left( \begin{array}{c} |
---|
| 126 | i_{j,0}(t) + \\ |
---|
| 127 | + \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) - \\ |
---|
| 128 | - \delta_j(q_j(t) T^{-1} + i_{0,j}) g_j^N \left( 1 - LC(t)^{-1} \right) |
---|
| 129 | \end{array} |
---|
| 130 | \right) |
---|
| 131 | \end{equation} |
---|
| 132 | |
---|
| 133 | \begin{equation}\label{eq:my_trans_mod_tok_03} |
---|
| 134 | q_j(t+1) = q_j(t) + T \left( \begin{array}{c} |
---|
| 135 | i_{j,0}(t) + \\ |
---|
| 136 | + \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) + \\ |
---|
| 137 | + \sum_{k \in I_j} \alpha_{k,j} \delta_k i_{0,k} g_k^N - \delta_j i_{0,j} g_j^N - \\ |
---|
| 138 | - \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} - \\ |
---|
| 139 | - \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} |
---|
| 140 | \end{array} |
---|
| 141 | \right) |
---|
| 142 | \end{equation} |
---|
| 143 | |
---|
| 144 | . 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)$, |
---|
| 145 | dostaneme dosazením $\Delta C^{-1}(t) = C(t)^{-1} - C^{N -1} $ do \ref{eq:my_trans_mod_tok_03} rovnici |
---|
| 146 | |
---|
| 147 | \begin{equation}\label{eq:my_trans_mod_tok_04} |
---|
| 148 | \begin{array}{ccc} |
---|
| 149 | 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} +\\ |
---|
| 150 | & & + 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} |
---|
| 151 | \end{array} |
---|
| 152 | \end{equation} |
---|
| 153 | |
---|
| 154 | |
---|
| 155 | |
---|
| 156 | |
---|
| 157 | \subsection{Minimalizační kritérium} |
---|
| 158 | Podobně jako v předchozí kapitole, minimalizovat kvaratické kritérium $J$. |
---|
| 159 | Minimalizaci budeme provádět v proměnných $\Delta C(t)$ pro časový horizont $h$, |
---|
| 160 | tedy pro vektory $\Delta C(t_0), \Delta C(t_0 + 1), ..., \Delta C(t_0 + h)$. Pro zpřehlednění |
---|
| 161 | zápisu položíme bez újmy na obecnosti $t_0 = 0$. |
---|
| 162 | Kvadratické kritérium |
---|
| 163 | ve tvaru |
---|
| 164 | \begin{equation}\label{eq:J} |
---|
| 165 | J = \sum_{t=0}^h q(t)^T Q q(t) + \Delta C(t)^T R \Delta C(t) |
---|
| 166 | \end{equation}, |
---|
| 167 | kde $Q$ a $R$ jsou diagonální pozitivně definitní matice vah, |
---|
| 168 | rozepíšeme pomocí vztahu |
---|
| 169 | \begin{equation}\label{eq:prechod} |
---|
| 170 | q(t+1) = Aq(t) + Bq(t) |
---|
| 171 | \end{equation} a budeme minimalizovat pro jednotlivá $t$ podle $\Delta C(t)$. |
---|
| 172 | $\Delta C(h)$ se v kritériu vyskytuje pouze jako člen |
---|
| 173 | \begin{equation} |
---|
| 174 | \Delta C(h)^T R \Delta C(h) |
---|
| 175 | \end{equation} |
---|
| 176 | a tedy musí být $\Delta C(h) 0$. $\Delta C(h - 1)$ se vyskytuje ve členech |
---|
| 177 | \begin{equation} |
---|
| 178 | \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)) |
---|
| 179 | \end{equation} |
---|
| 180 | , což lze pomocí složených vektorů a matic přepsat do tvaru |
---|
| 181 | \begin{equation} \label{eq:J_sloz} |
---|
| 182 | (\Delta C(h-1)^T, q(h - 1)^T ) |
---|
| 183 | \left( \begin{array}{cc} |
---|
| 184 | B^T \sqrt{Q} & \sqrt{R} \\ |
---|
| 185 | A^T \sqrt{Q} & 0 |
---|
| 186 | \end{array} |
---|
| 187 | \right) |
---|
| 188 | \left( \begin{array}{cc} |
---|
| 189 | \sqrt{Q} B & \sqrt{Q} A \\ |
---|
| 190 | \sqrt{R} & 0 |
---|
| 191 | \end{array} |
---|
| 192 | \right) |
---|
| 193 | \left( \begin{array}{c} |
---|
| 194 | \Delta C(h-1) \\ |
---|
| 195 | q(h - 1) |
---|
| 196 | \end{array} |
---|
| 197 | \right) |
---|
| 198 | \end{equation}, kde $\sqrt{Q}$ je matice, pro níž platí $\sqrt{Q} \sqrt{Q} = Q$. |
---|
| 199 | Složenou matici |
---|
| 200 | \begin{equation} |
---|
| 201 | \left( \begin{array}{cc} |
---|
| 202 | B^T \sqrt{Q} & \sqrt{R} \\ |
---|
| 203 | A^T \sqrt{Q} & 0 |
---|
| 204 | \end{array} |
---|
| 205 | \right) |
---|
| 206 | \left( \begin{array}{cc} |
---|
| 207 | \sqrt{Q} B & \sqrt{Q} A \\ |
---|
| 208 | \sqrt{R} & 0 |
---|
| 209 | \end{array} |
---|
| 210 | \right) = |
---|
| 211 | \left( \begin{array}{cc} |
---|
| 212 | B^T Q B + R & B^T Q A \\ |
---|
| 213 | A^T Q B & A^T Q A |
---|
| 214 | \end{array} |
---|
| 215 | \right) |
---|
| 216 | \end{equation} |
---|
| 217 | můžeme pomocí Choleského dekompozici na součin dolní a horní trojúhelníkové matice. |
---|
| 218 | Člen \ref{eq:J_sloz} poté přejde na tvar |
---|
| 219 | \begin{equation} |
---|
| 220 | (\Delta C(h-1)^T, q(h - 1)^T ) |
---|
| 221 | \left( \begin{array}{cc} |
---|
| 222 | L_q^T & 0 \\ |
---|
| 223 | L^T & L_C^T |
---|
| 224 | \end{array} |
---|
| 225 | \right) |
---|
| 226 | \left( \begin{array}{cc} |
---|
| 227 | L_C & L \\ |
---|
| 228 | 0 & L_q |
---|
| 229 | \end{array} |
---|
| 230 | \right) |
---|
| 231 | \left( \begin{array}{c} |
---|
| 232 | \Delta C(h-1) \\ |
---|
| 233 | q(h - 1) |
---|
| 234 | \end{array} |
---|
| 235 | \right) |
---|
| 236 | \end{equation}, který můžeme dále upravit na |
---|
| 237 | \begin{equation} |
---|
| 238 | ( 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) |
---|
| 239 | \end{equation}. Pokud tento člen chceme minimalizovat v proměnné $q(h-1)$, musí nutně platit |
---|
| 240 | \begin{equation} |
---|
| 241 | \Delta C(h-1) = - L_C^{-1} L q(h-1) |
---|
| 242 | \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 |
---|
| 243 | \begin{equation} |
---|
| 244 | 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) ) |
---|
| 245 | \end{equation}, kde se vyskytuje $\Delta C(t)$ pouze pro $t = h-2$. Minimalizace přes |
---|
| 246 | $\Delta C(h-2)$ bude probíhat analogicky, pouze se matice $Q$ nahradí maticí |
---|
| 247 | \begin{equation} |
---|
| 248 | \widetilde{Q} = Q + L_q^T L_q |
---|
| 249 | \end{equation}, která zahrnuje zbytek po členu s $\Delta C(h-1)$. |
---|
| 250 | Pro další $\Delta C(t)$ se pouze upraví matice $\widetilde{Q}$ výše popsaným způsoen a minimalizace již probíhá stejně.\\ |
---|
| 251 | |
---|
| 252 | DOTAZY:\\ |
---|
| 253 | QR - obecne nerozklada na trojuhelnikove matice $L L^{-1}$, ale na jednu troj a na druhou ortogonal. |
---|
| 254 | Cholesky rozklada pouze pozitivně definitní matice - je pozitivně definitní? dokazovat? pouzit QR? |
---|
| 255 | Matice L se v tomto pripade meni v kazdem kroku. V poradku? |
---|
| 256 | |
---|
| 257 | |
---|
| 258 | |
---|
| 259 | |
---|
| 260 | |
---|
| 261 | |
---|
| 262 | |
---|
| 263 | |
---|
| 264 | |
---|
| 265 | |
---|
| 266 | |
---|
| 267 | \section{Simulace} |
---|
| 268 | |
---|
| 269 | \subsection{Simulátor AIMSUN} |
---|
| 270 | |
---|
| 271 | \subsection{Oblast simulace} |
---|