[1147] | 1 | \chapter{Multiagentní systémy} |
---|
| 2 | |
---|
| 3 | \section{Úvod} |
---|
| 4 | |
---|
[1150] | 5 | Multiagentní systém je druh distribuované umělé inteligence. Tento systém se skládá z |
---|
[1147] | 6 | jednotlivých výpočetních prvků, tzv. agentů, které musí mít dvě základní schopnosti. |
---|
| 7 | Zaprvé musí být schopni autonomní akce rozhodnutí - zjistit jak nejlépe dosáhnout |
---|
[1151] | 8 | požadovaných cílů - a zadruhé je to schopnost interakce s ostatními agenty. V druhém případě nejde |
---|
[1147] | 9 | jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí. |
---|
| 10 | |
---|
| 11 | \subsection{Historie} |
---|
| 12 | |
---|
[1151] | 13 | Multiagentní systémy jsou na poli počítačové vědy relativní novinkou. Studium tohoto |
---|
| 14 | tématu probíhá od začátku osmdesátých let dvacátého století. Větší pozornosti |
---|
[1147] | 15 | se jim dostalo v polovině let devadesátých s rozvojem internetu. |
---|
| 16 | |
---|
| 17 | \subsection{Agent} |
---|
| 18 | |
---|
| 19 | Neexistuje obecně uznávaná definice agenta. Přikloníme se k definici použité v publikaci |
---|
[1150] | 20 | \cite{wooldridge}. |
---|
[1147] | 21 | |
---|
| 22 | \begin{definition}[Agent]\label{de:agent01} |
---|
| 23 | Agent je počítačový systém umístěný do nějakého prostředí, který je schopen autonomní akce |
---|
| 24 | k přiblížení se navrženým cílům. |
---|
| 25 | \end{definition} |
---|
| 26 | |
---|
| 27 | |
---|
| 28 | Agent v naprosté většině případů nemá celkovou kontrolu nad prostředím. Prostředí může ovlivňovat |
---|
| 29 | jen částečně. Obecně, stejně jako v našem případě, je prostředí nedeterministické. Stejná akce |
---|
| 30 | provedená dvakrát za sebou nemusí vést ke stejnému výsledku. |
---|
| 31 | |
---|
| 32 | \section{Druhy prostředí} |
---|
| 33 | |
---|
[1150] | 34 | Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se |
---|
| 35 | prostředí dají klasifikovat následovně: |
---|
[1147] | 36 | |
---|
| 37 | \begin{itemize} |
---|
[1150] | 38 | \item Deterministické vs. nedeterministické |
---|
[1147] | 39 | \item Dostupné vs. nedostupné |
---|
| 40 | \item Statické vs. dynamické |
---|
| 41 | \end{itemize} |
---|
| 42 | Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. |
---|
[1150] | 43 | Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu. |
---|
[1147] | 44 | Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. |
---|
| 45 | V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. |
---|
| 46 | \\ |
---|
| 47 | \\ |
---|
| 48 | V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru), |
---|
[1150] | 49 | nedostupné (hodnoty se měří pouze jednou za 90 sekund, a ještě jsou zkreslené) a dynamické |
---|
| 50 | (intenzita dopravy se mění nezávisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi |
---|
[1147] | 51 | znesnadňuje rozhodování a kontrolu vyvolaného výsledku. |
---|
| 52 | |
---|
| 53 | |
---|
| 54 | \section{Interakce agentů} |
---|
| 55 | |
---|
| 56 | \subsection{Stavy prostředí a preference agentů} |
---|
| 57 | |
---|
| 58 | Mějme pro jednoduchost 2 agenty. Označme si je $i$ a $j$. |
---|
| 59 | Předpokládejme, že máme množinu $$\Omega = \{\omega_1, \omega_2, ...\}$$ obsahující všechny možné stavy |
---|
| 60 | prostředí, v kterém agenti operují. Aby byl agent schopen efektivně ovlivňovat prostření, musí být schopen |
---|
| 61 | ohodnotit, jak je pro něj daný stav příznivý. Hodnocení daného stavu agenta $i$ a $j$ formálně definujeme jako funkce |
---|
| 62 | $$u_i : \Omega \rightarrow \mathbb{R}, $$ |
---|
| 63 | $$u_j : \Omega \rightarrow \mathbb{R}. $$ |
---|
| 64 | Čím je stav $\omega$ příznivější pro agenta $i$, tím je větší hodnota funkce $u_i$. |
---|
| 65 | |
---|
| 66 | \begin{definition}[Uspořádání na množině všech stavů] |
---|
[1150] | 67 | Mějme 2 stavy prostředí $\omega_1$, $\omega_2$. Řekněme, že stav $\omega_1$ je preferován agentem $i$ nad stavem $\omega_2$, |
---|
[1147] | 68 | pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme |
---|
| 69 | $$ \omega_1 \succeq_i \omega_2. $$ |
---|
| 70 | Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$, |
---|
| 71 | pokud platí $u_i(\omega_1) > u_i(\omega_2)$. Značíme |
---|
| 72 | $$ \omega_1 \succ_i \omega_2 $$ |
---|
| 73 | \end{definition} |
---|
| 74 | |
---|
| 75 | Relace $ \succeq_i $ je zřejmě uspořádání, protože má všechny potřebné vlastnosti. |
---|
| 76 | \newline |
---|
| 77 | Reflexivitu: |
---|
| 78 | $$ \forall \omega \in \Omega : \omega \succeq_i \omega $$ |
---|
[1150] | 79 | Tranzitivitu: |
---|
[1147] | 80 | $$ \forall \omega_1, \omega_2, \omega_3 \in \Omega : \omega_1 \succeq_i \omega_2 \wedge \omega_2 \succeq_i \omega_3 \Rightarrow \omega_1 \succeq_i \omega_3$$ |
---|
| 81 | Porovnatelnost: |
---|
| 82 | $$ \forall \omega_1, \omega_2 \in \Omega : \omega_1 \succeq_i \omega_2 \vee \omega_2 \succeq_i \omega_1 $$ |
---|
| 83 | |
---|
| 84 | Relace $\succ_i$ zjevně nesplňuje podmínky reflexivity. |
---|
| 85 | |
---|
| 86 | \subsection{Akce agentů} |
---|
| 87 | Nyní popíšeme, jak mají agenti možnost ovlivňovat prostředí. |
---|
| 88 | Opět předpokládejme existenci dvou agentů $i$ a $j$. Obecně mají |
---|
[1151] | 89 | různí agenti různou oblast působnosti. Množina |
---|
[1147] | 90 | $$ A = \{ a_1, a_2, ... \} $$ |
---|
[1151] | 91 | znázorňuje množinu všech akcí, které jsou agenti schopni provézt. |
---|
[1147] | 92 | Na tyto akce reaguje prostředí přechodem do nějakého stavu $\omega \in \Omega$. |
---|
| 93 | Formálně můžeme tento přechod zapsat jako funkci |
---|
| 94 | $$ \tau : A \times A \rightarrow \Omega. $$ |
---|
| 95 | |
---|
| 96 | |
---|
| 97 | |
---|
| 98 | |
---|
| 99 | \section{Strategie} |
---|
| 100 | |
---|
| 101 | Popišme zde způsob, jak se agent rozhodne pro realizaci určité akce. |
---|
| 102 | Agent je nyní schopen ohodnotit, který stav prostředí je pro něj příznivější než jiný, |
---|
| 103 | neví však jak budou reagovat ostatní agenti, není schopen určit tudíž, i za předpokladu, |
---|
| 104 | že by systém byl deterministický, do jakého stavu systém přejde. K výběru optimální akce |
---|
| 105 | se používají prvky z teorie her. Zadefinujme nejprve v souladu s touto teorií základní pojmy. |
---|
| 106 | |
---|
| 107 | \begin{definition}[Dominance množiny] |
---|
| 108 | Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $. |
---|
| 109 | Řekneme, že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 110 | $$ |
---|
| 111 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'. |
---|
| 112 | $$ |
---|
| 113 | Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 114 | $$ |
---|
| 115 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'. |
---|
| 116 | $$ |
---|
| 117 | \end{definition} |
---|
| 118 | |
---|
| 119 | Abychom používali terminologii teorie her, budeme nyní akce $a_i \in A$ jednotlivých agentů |
---|
| 120 | nazývat strategiemi. |
---|
| 121 | |
---|
| 122 | \begin{definition}[Množina výsledků] |
---|
| 123 | Nazvěme množinu všech stavů, do kterých může prostředí přejít při hraní strategie $a_i \in A$, |
---|
| 124 | množinou možných výsledků. Označme ji |
---|
| 125 | $$ |
---|
| 126 | a_i^* \subset \Omega. |
---|
| 127 | $$ |
---|
| 128 | \end{definition} |
---|
| 129 | |
---|
| 130 | \begin{definition}[Dominance strategie] |
---|
| 131 | Řekneme, že strategie $a_i$ je dominantní nad strategií $a_j$, |
---|
| 132 | pokud je množina $a_i^*$ dominantní nad množinou $a_j^*$. |
---|
| 133 | Strategie $a_i$ je silně dominantní nad strategií $a_j$, |
---|
| 134 | pokud je množina $a_i^*$ silně dominantní nad množinou $a_j^*$. |
---|
| 135 | \end{definition} |
---|
| 136 | |
---|
| 137 | Racionálně uvažující agent tedy vyloučí všechny strategie $a_i$, jestliže existuje |
---|
[1150] | 138 | strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zúžení výběru zbývajících |
---|
[1151] | 139 | strategií slouží Nashova rovnost. Pro zjednodušení uvažujme 2 agenty, $i$ a $j$. |
---|
[1147] | 140 | Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent |
---|
| 141 | $i$ zvolí strategii $a_1$, je nejvýhodnější strategií pro agenta $j$ je strategie $a_2$ a zároveň |
---|
[1150] | 142 | pokud agent $j$ zvolí strategii $a_2$, je pro agenta i nejvýhodnější strategií $a_1$. |
---|
[1147] | 143 | |
---|
| 144 | \subsection{Použití pro výběr délky cyklu} |
---|
| 145 | |
---|
[1150] | 146 | Délka cyklu řadiče křižovatky je parametr, který je pro všechny agenty ve skupině zahrnující křižovatky do zelené vlny společný. |
---|
[1147] | 147 | Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií |
---|
| 148 | $A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ |
---|
| 149 | v dané situaci. Mějme funkci $u_{i_{Tc}} : A \rightarrow \mathbb{R} $, jejíž funkční hodnota v bodě $Tc_j$ |
---|
| 150 | udává předpokládaný zisk pro agenta $i$ při délce cyklu $Tc_j$. Funkci $u_i(\omega) = u_i(\tau(Tc_k, Tc_l))$ můžeme zadefinovat následovně |
---|
| 151 | (pro jednoduchost předpokládejme existenci dvou agentů $i$ a $j$) |
---|
| 152 | $$ |
---|
| 153 | u_i(\tau(Tc_k, Tc_l) = |
---|
| 154 | \left\{ |
---|
| 155 | \begin{array}{r@{\quad}c} |
---|
| 156 | u_{i_{Tc}}(Tc_k) , & k = l \\ |
---|
| 157 | - \infty , & k \neq l \\ |
---|
| 158 | \end{array} |
---|
| 159 | \right., |
---|
| 160 | $$ |
---|
[1150] | 161 | kde hodnota $-\infty$ vyjadřuje jakýsi kolaps systému při nastavení různých délek cyklu. |
---|
| 162 | To však znamená, že žádná strategie není silně dominantní nad jinou. Zároveň za předpokladu, |
---|
[1147] | 163 | že agent $i$ zvolí strategii $Tc_l$, agent $j$ nemůže udělat lépe, než že zvolí stejnou strategii. |
---|
| 164 | To znamená že pro všechny strategie $Tc_l \in A$ platí, že jsou v Nashově rovnosti samy se sebou. |
---|
| 165 | Takto definovaná funkce nám v souladu s teorií zaručí, že agenti nenastaví různé délky cyklu, potřebujeme |
---|
| 166 | ale dodatečné kritérium kterou délku cyklu vybrat. |
---|
| 167 | |
---|
[1150] | 168 | \subsection{Globálně nejlepší řešení} |
---|
[1147] | 169 | Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu. |
---|
| 170 | Nejprve musíme určit množinu možných délek cyklu tak, aby v každém kroku simulace byla pro všechny agenty společná. |
---|
| 171 | Určíme tedy přirozená čísla $n$ a $dTc$. Množina možných strategií $A$ bude |
---|
| 172 | $$ |
---|
| 173 | A = \{ Tc_{-n}, Tc_{-n+1}, ..., Tc_{n-1}, Tc_{n} \}, |
---|
| 174 | $$ |
---|
| 175 | $$ |
---|
| 176 | Tc_i = Tc + i \cdot dTc, |
---|
| 177 | $$ |
---|
| 178 | kde $Tc$ je délka cyklu v minulém kroku simulace. Každý agent je pak schopen sestavit množinu součtů zisků |
---|
| 179 | $$ |
---|
| 180 | U = \{ u_{Tc_{-n}}, u_{Tc_{-n+1}}, ..., u_{Tc_{n-1}, u_{Tc_{n}}} \}, |
---|
| 181 | $$ |
---|
| 182 | kde |
---|
| 183 | $$ |
---|
| 184 | u_{Tc_i} = \sum_k u_{k_{Tc}}(Tc_i). |
---|
| 185 | $$ |
---|
| 186 | Agent poté zvolí takovou délku cyklu $Tc_i$, pro kterou platí |
---|
| 187 | $$ |
---|
| 188 | u_{Tc_i} = \max(U). |
---|
| 189 | $$ |
---|
| 190 | Toto je výběr globálně nejlepšího řešení, kde agent upřednostní takový čas délky cyklu, u kterého se předpokládá |
---|
[1150] | 191 | největší součet zisků od všech agentů nad časem, u kterého předpokládá největší zisk pro sebe. |
---|
| 192 | |
---|
| 193 | \subsection{Rozšíření} |
---|
| 194 | |
---|
| 195 | V našem případě se zabýváme pouze dvěma křižovatkami. V případě většího počtu křižovatek patřících do různých skupin zelené vlny |
---|
| 196 | se bude optimalizace provádět pro každou skupinu zvlášť. Jak dále popíšeme v \ref{ss:odhad_fronty}, pro danou skupinu je důležitý i údaj |
---|
| 197 | o délce cyklu okolních agentů, neboť ovlivňuje předpoklad o hustotě provozu. Komunikace se rozšíří o tento údaj a každá skupina ho zahrne |
---|
| 198 | do výběru strategie. |
---|