[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} |
---|
[1424] | 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, |
---|
[1419] | 36 | případně vstupu do systému $i_{j,0}(t)$, pokud se jedná o koncové rameno řízené oblasti, tedy |
---|
| 37 | \begin{equation} |
---|
[1424] | 38 | i_j(t) = i_{j,0}(t) + \sum_{k \in I_j} \alpha_{k,j} o_k(t) . |
---|
| 39 | \end{equation} |
---|
[1419] | 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} |
---|
[1424] | 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 |
---|
[1419] | 51 | \begin{equation}\label{eq:my_trans_02} |
---|
[1424] | 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 | |
---|
| 55 | % Nebudeme delat trik s nominální hodnotou, ale pouzijeme u(t) = 1 - LC(t)^{-1} |
---|
| 56 | % Pokud budeme podobně jako v \cite{6_tuc_lq} předpokládat existenci nominální délky cyklu $C^N$, při níž se |
---|
| 57 | % nemění délka fronty, platíc( |
---|
| 58 | % \begin{equation}\label{eq:my_trans_nom} |
---|
| 59 | % 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) |
---|
| 60 | % \end{equation}. Odečtením rovnice \ref{eq:my_trans_nom} od \ref{eq:my_trans_02} dostaneme |
---|
| 61 | % \begin{equation}\label{eq:my_trans_03} |
---|
| 62 | % 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) |
---|
| 63 | % \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 |
---|
| 64 | % tedy rovnice pro fronty dají zapsat maticově ve tvaru |
---|
| 65 | % \begin{equation}\label{eq:my_trans_mat} |
---|
| 66 | % \vec{q}(t+1) = A \vec{q}(t) + B \Delta C^{-1}(t) |
---|
| 67 | % \end{equation} |
---|
| 68 | |
---|
| 69 | Za řídící proměnnou tedy vezmeme |
---|
| 70 | \begin{equation} |
---|
| 71 | u(t) = 1 - LC(t)^{-1} . |
---|
| 72 | \end{equation} |
---|
| 73 | takže můžeme rovnici \ref{eq:my_trans_02} přepsat do maticové formy |
---|
[1419] | 74 | \begin{equation}\label{eq:my_trans_mat} |
---|
[1424] | 75 | q(t+1) = A q(t) + B u(t) + I_0(t) , |
---|
[1419] | 76 | \end{equation} |
---|
[1424] | 77 | kde $A$ je jednotková matice, $B$ je diagonální matice s prvky |
---|
| 78 | \begin{equation} |
---|
| 79 | b_{jj} = T \left( \sum_{k \in I_j} \alpha_{k,j} S_k g_k^N - S_j g_j^N \right) |
---|
| 80 | \end{equation} |
---|
[1419] | 81 | |
---|
[1424] | 82 | |
---|
| 83 | |
---|
[1419] | 84 | Kostantni saturovany tok neni optimalni, pouzije aprox podle Pecherkove (viz bak.), |
---|
| 85 | prujezd odpovida bud sat. toku, pokud neodjede cela fronta, nebo je primo umerny |
---|
| 86 | fronte (+ prijezdum). prolozi se funkci a aprox se primkou podle hodnoty fronty v case t. |
---|
| 87 | Napocte se rizen pro horizont a podle vyvoje fronty se prepocte misto pro prolozeni pri |
---|
| 88 | |
---|
| 89 | |
---|
| 90 | \subsubsection{Model toku} |
---|
| 91 | V článku \cite{6_tuc_lq} se úbytek vozidel modeluje podle rovnice \ref{eq:tuc_u}, kde je uvažován |
---|
| 92 | tok vozidel křižovatkou za jednotku času jako konstanta $S$, což je saturovaný tok. Tento vztah |
---|
| 93 | platí pouze když je příslušný pruh naplněn vozidly do té míry, že křižovatkou projede maximální |
---|
| 94 | možný počet vozidel. To však neplatí, pokud není pruh dostatečně vytížen, například pokud se zmenší |
---|
| 95 | 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 |
---|
| 96 | fronty $q(t)/T$ a počtu vstupujících vozidel $i(t)$. Pro teoretickou hodnotu toku $S$ tedy dostáváme vztah |
---|
| 97 | \begin{equation}\label{eq:teor_tok} |
---|
| 98 | S_{teor}(q(t) + i(t)) = \left\{ |
---|
| 99 | \begin{array}{lr} |
---|
| 100 | \frac{q(t)}{T} + i(t) & \frac{q(t)}{T} + i(t) <= S_{max} \\ |
---|
| 101 | S_{max} & \frac{q(t)}{T} + i(t) > S_{max} |
---|
| 102 | \end{array} |
---|
| 103 | \right. |
---|
| 104 | \end{equation} |
---|
| 105 | . tento vztah vyjadřuje to, že pokud je fronta plus přírůstrek vozidel ve vzorkovací periodě |
---|
| 106 | $(q(t), i(t)T)$ menší než maximální počet vozidel, který je křižovatka za periodu $T$ schopna |
---|
| 107 | propustit $(T S_{max})$, projedou všechna vozidla. Abychom se vyhnuli podmínce podle $S_{max}$, |
---|
| 108 | aproximuje se tento vztah funkcí |
---|
| 109 | \begin{equation}\label{eq:exp_tok} |
---|
| 110 | S_{exp}(q(t), i(t)) = S_{max} \left(1 - e^{- \frac{1}{S_{max}} \left( \frac{q(t)}{T} + i(t) \right) } \right) |
---|
| 111 | \end{equation} |
---|
| 112 | , která splňuje podmínku |
---|
| 113 | \begin{equation} |
---|
| 114 | \frac{ dS_{exp} }{d(q/T+i)}(0,0) = 1 |
---|
| 115 | \end{equation} |
---|
| 116 | , tedy při malé frontě a hustotě provozu |
---|
| 117 | je přírůstek toku roven $q/T+i$, a podmínku |
---|
| 118 | \begin{equation} |
---|
| 119 | \lim_{q/T+i\to\infty} S_{exp} = S_{max} |
---|
| 120 | \end{equation} |
---|
| 121 | , tedy při velké frontě a hustotě provozu |
---|
| 122 | se tok blíží konstantě $S_{max}$. Pro malý časový interval můžeme tuto funkci dále zjednodušit na lineární vztah |
---|
| 123 | \begin{equation}\label{eq:lin_tok} |
---|
| 124 | S(q(t)) = \sigma(q(t)/T + i_0) |
---|
| 125 | \end{equation} |
---|
| 126 | , kde je $i_0 = i(0)$ a |
---|
| 127 | \begin{equation} |
---|
| 128 | \sigma = \frac{ dS_{exp} }{d(q/T+i)}(q(0),i(0)) |
---|
| 129 | \end{equation} |
---|
| 130 | \\ |
---|
| 131 | vlozit graf s ruznymi S |
---|
| 132 | \\ |
---|
| 133 | |
---|
| 134 | \subsubsection{Přechodové vztahy s proměnným tokem} |
---|
| 135 | Pro vyjádření přechodových vzthů použijeme lineární odel toku a rovnice \ref{eq:my_trans_02} |
---|
| 136 | přejde na tvar |
---|
| 137 | \begin{equation} |
---|
| 138 | 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) |
---|
| 139 | \end{equation} |
---|
| 140 | , a po dosazení \ref{eq:lin_tok} dostaneme |
---|
| 141 | \begin{equation} |
---|
| 142 | q_j(t+1) = q_j(t) + T \left( \begin{array}{c} |
---|
| 143 | i_{j,0}(t) + \\ |
---|
| 144 | + \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) - \\ |
---|
| 145 | - \delta_j(q_j(t) T^{-1} + i_{0,j}) g_j^N \left( 1 - LC(t)^{-1} \right) |
---|
| 146 | \end{array} |
---|
| 147 | \right) |
---|
| 148 | \end{equation} |
---|
| 149 | |
---|
| 150 | \begin{equation}\label{eq:my_trans_mod_tok_03} |
---|
| 151 | q_j(t+1) = q_j(t) + T \left( \begin{array}{c} |
---|
| 152 | i_{j,0}(t) + \\ |
---|
| 153 | + \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) + \\ |
---|
| 154 | + \sum_{k \in I_j} \alpha_{k,j} \delta_k i_{0,k} g_k^N - \delta_j i_{0,j} g_j^N - \\ |
---|
| 155 | - \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} - \\ |
---|
| 156 | - \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} |
---|
| 157 | \end{array} |
---|
| 158 | \right) |
---|
| 159 | \end{equation} |
---|
| 160 | |
---|
[1424] | 161 | % . 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)$, |
---|
| 162 | % dostaneme dosazením $\Delta C^{-1}(t) = C(t)^{-1} - C^{N -1} $ do \ref{eq:my_trans_mod_tok_03} rovnici |
---|
| 163 | % |
---|
| 164 | % \begin{equation}\label{eq:my_trans_mod_tok_04} |
---|
| 165 | % \begin{array}{ccc} |
---|
| 166 | % 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} +\\ |
---|
| 167 | % & & + 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} |
---|
| 168 | % \end{array} |
---|
| 169 | % \end{equation} |
---|
[1419] | 170 | |
---|
| 171 | |
---|
| 172 | |
---|
| 173 | |
---|
| 174 | \subsection{Minimalizační kritérium} |
---|
| 175 | Podobně jako v předchozí kapitole, minimalizovat kvaratické kritérium $J$. |
---|
[1424] | 176 | Minimalizaci budeme provádět v proměnných $u(t)$ pro časový horizont $h$, |
---|
| 177 | tedy pro vektory $\Delta C(t_0), \Delta C(t_0 + 1), ...,u(t_0 + h)$. Pro zpřehlednění |
---|
[1419] | 178 | zápisu položíme bez újmy na obecnosti $t_0 = 0$. |
---|
| 179 | Kvadratické kritérium |
---|
| 180 | ve tvaru |
---|
| 181 | \begin{equation}\label{eq:J} |
---|
[1424] | 182 | J = \sum_{t=0}^h q(t)^T Q q(t) + u(t)^T R u(t) , |
---|
| 183 | \end{equation} |
---|
[1419] | 184 | kde $Q$ a $R$ jsou diagonální pozitivně definitní matice vah, |
---|
| 185 | rozepíšeme pomocí vztahu |
---|
[1424] | 186 | \begin{equation}\label{eq:prechod} |
---|
| 187 | q(t+1) = Aq(t) + Bu(t) + I_0(t) |
---|
| 188 | \end{equation} |
---|
| 189 | a budeme minimalizovat pro jednotlivá $t$ podle $u(t)$. |
---|
| 190 | Matici $I_0(t)$, která vyjadřuje příjezd vozidel z okolí do sledované sítě, |
---|
| 191 | budeme v rámci minimalizačního horizontu považovat za konstantu značenou $I_0$. |
---|
| 192 | $u(h)$ se v kritériu vyskytuje pouze jako člen |
---|
[1419] | 193 | \begin{equation} |
---|
[1424] | 194 | u(h)^T Ru(h) |
---|
[1419] | 195 | \end{equation} |
---|
[1424] | 196 | a tedy musí být $u(h) = 0$. $u(h - 1)$ se vyskytuje ve členech |
---|
[1419] | 197 | \begin{equation} |
---|
[1424] | 198 | u(h - 1)^T Ru(h - 1) + (q(h - 1)^T A^T +u(h - 1)^T B^T ) Q ( A q(h - 1) + B u(h - 1) + I_0) |
---|
[1419] | 199 | \end{equation} |
---|
| 200 | , což lze pomocí složených vektorů a matic přepsat do tvaru |
---|
| 201 | \begin{equation} \label{eq:J_sloz} |
---|
[1424] | 202 | (u(h-1)^T, q(h - 1)^T ) |
---|
[1419] | 203 | \left( \begin{array}{cc} |
---|
[1424] | 204 | B^T \sqrt{Q}^T & \sqrt{R}^T \\ |
---|
| 205 | A^T \sqrt{Q}^T & 0 |
---|
[1419] | 206 | \end{array} |
---|
| 207 | \right) |
---|
| 208 | \left( \begin{array}{cc} |
---|
| 209 | \sqrt{Q} B & \sqrt{Q} A \\ |
---|
| 210 | \sqrt{R} & 0 |
---|
| 211 | \end{array} |
---|
| 212 | \right) |
---|
| 213 | \left( \begin{array}{c} |
---|
[1424] | 214 | u(h-1) \\ |
---|
[1419] | 215 | q(h - 1) |
---|
| 216 | \end{array} |
---|
| 217 | \right) |
---|
[1424] | 218 | \end{equation}, kde symbolem $\sqrt{Q}$ myslíme matici, pro níž platí $\sqrt{Q}^T \sqrt{Q} = Q$. |
---|
| 219 | Matice $Q$ a $R$ jsou pozitivně definitní diagonální matice, takže $\sqrt{Q}$ bude také |
---|
| 220 | pozitivně definitní diagonální a její diagonální prvky budou rovny odmocnině |
---|
| 221 | příslušných prvků původní matice $Q$. |
---|
[1419] | 222 | Složenou matici |
---|
[1424] | 223 | \begin{equation} |
---|
| 224 | M_0 = \left( \begin{array}{cc} |
---|
[1419] | 225 | B^T \sqrt{Q} & \sqrt{R} \\ |
---|
| 226 | A^T \sqrt{Q} & 0 |
---|
| 227 | \end{array} |
---|
[1424] | 228 | \right) |
---|
| 229 | \end{equation} |
---|
| 230 | můžeme pomocí QR dekompozice na součin |
---|
| 231 | |
---|
| 232 | \begin{equation} |
---|
| 233 | M_0 = M_R M_Q , |
---|
| 234 | \end{equation} |
---|
| 235 | kde $M_Q$ je horní trojůhelníková matice a $M_R$ je matice ortonormální. |
---|
| 236 | Pro ortonormální matici $M_R$ platí |
---|
| 237 | \begin{equation} |
---|
| 238 | M_R^T M_R = I , |
---|
| 239 | \end{equation} |
---|
| 240 | neboť její zloupce jsou vzájemně ortogonální a normované na jednotku. |
---|
| 241 | Z toho plyne, že součin matic $M_0^T M_0$, vyskytující se ve vztahu |
---|
| 242 | |
---|
| 243 | Člen \ref{eq:J_sloz} poté přejde na tvar |
---|
| 244 | \begin{equation} |
---|
| 245 | (\Delta C(h-1)^T, q(h - 1)^T ) |
---|
[1419] | 246 | \left( \begin{array}{cc} |
---|
[1424] | 247 | L_q^T & 0 \\ |
---|
| 248 | L^T & L_u^T |
---|
[1419] | 249 | \end{array} |
---|
[1424] | 250 | \right) |
---|
[1419] | 251 | \left( \begin{array}{cc} |
---|
[1424] | 252 | L_u & L \\ |
---|
| 253 | 0 & L_q |
---|
[1419] | 254 | \end{array} |
---|
| 255 | \right) |
---|
[1424] | 256 | \left( \begin{array}{c} |
---|
| 257 | u(h-1) \\ |
---|
| 258 | q(h - 1) |
---|
| 259 | \end{array} |
---|
| 260 | \right) |
---|
| 261 | \end{equation}, který můžeme dále upravit na |
---|
| 262 | \begin{equation} |
---|
| 263 | ( L_u u(h-1) + L_q q(h-1) )^T ( L_uu(h-1) + L_q q(h-1) ) + q(h-1)^T L_q^T L_q q(h-1) |
---|
| 264 | \end{equation}. Pokud tento člen chceme minimalizovat v proměnné $q(h-1)$, musí nutně platit |
---|
| 265 | \begin{equation} |
---|
| 266 | u(h-1) = - L_u^{-1} L q(h-1) |
---|
| 267 | \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 |
---|
| 268 | \begin{equation} |
---|
| 269 | q(h-1)^T L_q^T L_q q(h-1) = ( A q(h-2) + B u(h-2) )^T L_q^T L_q ( A q(h-2) + B u(h-2) ) |
---|
| 270 | \end{equation}, kde se vyskytuje $u(t)$ pouze pro $t = h-2$. Minimalizace přes |
---|
| 271 | $u(h-2)$ bude probíhat analogicky, pouze se matice $Q$ nahradí maticí |
---|
| 272 | \begin{equation} |
---|
| 273 | \widetilde{Q} = Q + L_q^T L_q |
---|
| 274 | \end{equation}, která zahrnuje zbytek po členu s $u(h-1)$. |
---|
| 275 | Pro další $u(t)$ se pouze upraví matice $\widetilde{Q}$ výše popsaným způsoen a minimalizace již probíhá stejně.\\ |
---|
[1419] | 276 | |
---|
| 277 | |
---|
| 278 | |
---|
| 279 | |
---|
| 280 | |
---|
| 281 | |
---|
| 282 | |
---|
| 283 | \section{Simulace} |
---|
| 284 | |
---|
| 285 | \subsection{Simulátor AIMSUN} |
---|
| 286 | |
---|
| 287 | \subsection{Oblast simulace} |
---|