[1147] | 1 | \chapter{Multiagentní systémy} |
---|
| 2 | |
---|
| 3 | \section{Úvod} |
---|
| 4 | |
---|
| 5 | Multiagentí systém je druh distribuované umělé inteligence. Tento systém se skládá z |
---|
| 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 |
---|
| 8 | požadovaných cílů a zadruhé je to schopnost interakce s ostaními agenty. V druhém případě nejde |
---|
| 9 | jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí. |
---|
| 10 | |
---|
| 11 | \subsection{Historie} |
---|
| 12 | |
---|
| 13 | Multiagentí systémy jsou na poli počítačové vědy poměrně nnovinkou. Studium tohoto |
---|
| 14 | tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti |
---|
| 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 |
---|
| 20 | Wooldridge a Jennings(1995). |
---|
| 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{Prostředí} |
---|
| 33 | |
---|
| 34 | Russel a Norvig navrhli klasifikaci prostředí podle jednotlivých parametrů následovně. |
---|
| 35 | |
---|
| 36 | \subsection{Dostupné vs. nedostupné} |
---|
| 37 | |
---|
| 38 | Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu. |
---|
| 39 | |
---|
| 40 | \subsection{Deterministické vs. Nedetrministické} |
---|
| 41 | |
---|
| 42 | Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. |
---|
| 43 | |
---|
| 44 | \subsection{Statické vs. dynamické} |
---|
| 45 | |
---|
| 46 | Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. |
---|
| 47 | |
---|
| 48 | \subsection{Diskrétní vs. spojité} |
---|
| 49 | |
---|
| 50 | V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. |
---|
| 51 | |
---|
| 52 | \section{Interakce agentů} |
---|
| 53 | |
---|
| 54 | \subsection{Stavy prostředí a preference agentů} |
---|
| 55 | |
---|
| 56 | Mějme pro jednoduchost 2 agenty. Označme si je $i$ a $j$. |
---|
| 57 | Předpokládejme, že máme množinu $$\Omega = \{\omega_1, \omega_2, ...\}$$ obsahující všechny možné stavy |
---|
| 58 | prostředí, v kterém agenti operují. Aby byl agent schopen efektivně ovlivňovat prostření, musí být schopen |
---|
| 59 | ohodnotit, jak je pro něj daný stav příznivý. Hodnocení daného stavu agenta $i$ a $j$ formálně definujeme jako funkce |
---|
| 60 | $$u_i : \Omega \rightarrow \mathbb{R}, $$ |
---|
| 61 | $$u_j : \Omega \rightarrow \mathbb{R}. $$ |
---|
| 62 | Čím je stav $\omega$ příznivější pro agenta $i$, tím je větší hodnota funkce $u_i$. |
---|
| 63 | |
---|
| 64 | \begin{definition}[Uspořádání na množině všech stavů] |
---|
| 65 | Mějme 2 stavy prostředí $\omega_1$, $\omega_2$. Řekněmě, že stav $\omega_1$ je preferován agentem $i$ nad stavem $\omega_2$, |
---|
| 66 | pokud platí $u_i(\omega_1) \>= u_i(\omega_2)$. Značíme |
---|
| 67 | $$ \omega_1 \succeq_i \omega_2. $$ |
---|
| 68 | Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$, |
---|
| 69 | pokud platí $u_i(\omega_1) \> u_i(\omega_2)$. Značíme |
---|
| 70 | $$ \omega_1 \succ_i \omega_2 $$ |
---|
| 71 | \end{definition} |
---|
| 72 | |
---|
| 73 | Relace $ \succeq_i $ je zřejmě uspořádání, protože má všechny potřebné vlastnosti. |
---|
| 74 | \newline |
---|
| 75 | Reflexivitu: |
---|
| 76 | $$ \forall \omega \in \Omega : \omega \succeq_i \omega $$ |
---|
| 77 | Transitivitu: |
---|
| 78 | $$ \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$$ |
---|
| 79 | Porovnatelnost: |
---|
| 80 | $$ \forall \omega_1, \omega_2 \in \Omega : \omega_1 \succeq_i \omega_2 \vee \omega_2 \succeq_i \omega_1 $$ |
---|
| 81 | |
---|
| 82 | Relace $\succ_i$ zjevně nesplňuje podmínky reflexivity. |
---|
| 83 | |
---|
| 84 | \subsection{Akce agentů} |
---|
| 85 | Nyní popíšeme, jak mají agenti možnost ovlivňovat prostředí. |
---|
| 86 | Opět předpokládejme existenci dvou agentů $i$ a $j$. Obecně mají |
---|
| 87 | různí agenti různou oblast působnosti. Množiny |
---|
| 88 | $$ A = \{ a_1, a_2, ... \} $$ |
---|
| 89 | znázorňují množiny všech akcí, které jsou agenti schopni provézt. |
---|
| 90 | Na tyto akce reaguje prostředí přechodem do nějakého stavu $\omega \in \Omega$. |
---|
| 91 | Formálně můžeme tento přechod zapsat jako funkci |
---|
| 92 | $$ \tau : A \times A \rightarrow \Omega. $$ |
---|
| 93 | |
---|
| 94 | \begin{definition}[Dominance] |
---|
| 95 | Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $. |
---|
| 96 | Řekneme že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 97 | $$ |
---|
| 98 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'. |
---|
| 99 | $$ |
---|
| 100 | Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 101 | $$ |
---|
| 102 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'. |
---|
| 103 | $$ |
---|
| 104 | |
---|
| 105 | \end{definition} |
---|
| 106 | |
---|
| 107 | |
---|
| 108 | \section{Strategie} |
---|
| 109 | |
---|
| 110 | Popišme zde způsob, jak se agent rozhodne pro realizaci určité akce. |
---|
| 111 | Agent je nyní schopen ohodnotit, který stav prostředí je pro něj příznivější než jiný, |
---|
| 112 | neví však jak budou reagovat ostatní agenti, není schopen určit tudíž, i za předpokladu, |
---|
| 113 | že by systém byl deterministický, do jakého stavu systém přejde. K výběru optimální akce |
---|
| 114 | se používají prvky z teorie her. Zadefinujme nejprve v souladu s touto teorií základní pojmy. |
---|
| 115 | |
---|
| 116 | \begin{definition}[Dominance množiny] |
---|
| 117 | Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $. |
---|
| 118 | Řekneme, že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 119 | $$ |
---|
| 120 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'. |
---|
| 121 | $$ |
---|
| 122 | Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 123 | $$ |
---|
| 124 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'. |
---|
| 125 | $$ |
---|
| 126 | \end{definition} |
---|
| 127 | |
---|
| 128 | Abychom používali terminologii teorie her, budeme nyní akce $a_i \in A$ jednotlivých agentů |
---|
| 129 | nazývat strategiemi. |
---|
| 130 | |
---|
| 131 | \begin{definition}[Množina výsledků] |
---|
| 132 | 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$, |
---|
| 133 | množinou možných výsledků. Označme ji |
---|
| 134 | $$ |
---|
| 135 | a_i^* \subset \Omega. |
---|
| 136 | $$ |
---|
| 137 | \end{definition} |
---|
| 138 | |
---|
| 139 | \begin{definition}[Dominance strategie] |
---|
| 140 | Řekneme, že strategie $a_i$ je dominantní nad strategií $a_j$, |
---|
| 141 | pokud je množina $a_i^*$ dominantní nad množinou $a_j^*$. |
---|
| 142 | Strategie $a_i$ je silně dominantní nad strategií $a_j$, |
---|
| 143 | pokud je množina $a_i^*$ silně dominantní nad množinou $a_j^*$. |
---|
| 144 | \end{definition} |
---|
| 145 | |
---|
| 146 | Racionálně uvažující agent tedy vyloučí všechny strategie $a_i$, jestliže existuje |
---|
| 147 | strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zůžení výběru zbývajících |
---|
| 148 | strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 agnenty, $i$ a $j$. |
---|
| 149 | Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent |
---|
| 150 | $i$ zvolí strategii $a_1$, je nejvýhodnější strategií pro agenta $j$ je strategie $a_2$ a zároveň |
---|
| 151 | pokud agent $j$ zvolí strategii $a_2$, je pro agnta i nejvýhodnější strategií $a_1$. |
---|
| 152 | |
---|
| 153 | \subsection{Použití pro výběr délky cyklu} |
---|
| 154 | |
---|
| 155 | Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupině společný. |
---|
| 156 | Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií |
---|
| 157 | $A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ |
---|
| 158 | v dané situaci. Mějme funkci $u_{i_{Tc}} : A \rightarrow \mathbb{R} $, jejíž funkční hodnota v bodě $Tc_j$ |
---|
| 159 | 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ě |
---|
| 160 | (pro jednoduchost předpokládejme existenci dvou agentů $i$ a $j$) |
---|
| 161 | $$ |
---|
| 162 | u_i(\tau(Tc_k, Tc_l) = |
---|
| 163 | \left\{ |
---|
| 164 | \begin{array}{r@{\quad}c} |
---|
| 165 | u_{i_{Tc}}(Tc_k) , & k = l \\ |
---|
| 166 | - \infty , & k \neq l \\ |
---|
| 167 | \end{array} |
---|
| 168 | \right., |
---|
| 169 | $$ |
---|
| 170 | kde hodnota $-\infty$ vyjadřuje jakýsi kolabs systému při nastavení různých délek cyklu. |
---|
| 171 | To však znamená, že žádná strategie není sinlně dominantní nad jinou. Zároveň za předpokladu, |
---|
| 172 | že agent $i$ zvolí strategii $Tc_l$, agent $j$ nemůže udělat lépe, než že zvolí stejnou strategii. |
---|
| 173 | To znamená že pro všechny strategie $Tc_l \in A$ platí, že jsou v Nashově rovnosti samy se sebou. |
---|
| 174 | Takto definovaná funkce nám v souladu s teorií zaručí, že agenti nenastaví různé délky cyklu, potřebujeme |
---|
| 175 | ale dodatečné kritérium kterou délku cyklu vybrat. |
---|
| 176 | |
---|
| 177 | \subsection{Globálně nějlepší řešení} |
---|
| 178 | Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu. |
---|
| 179 | 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á. |
---|
| 180 | Určíme tedy přirozená čísla $n$ a $dTc$. Množina možných strategií $A$ bude |
---|
| 181 | $$ |
---|
| 182 | A = \{ Tc_{-n}, Tc_{-n+1}, ..., Tc_{n-1}, Tc_{n} \}, |
---|
| 183 | $$ |
---|
| 184 | $$ |
---|
| 185 | Tc_i = Tc + i \cdot dTc, |
---|
| 186 | $$ |
---|
| 187 | kde $Tc$ je délka cyklu v minulém kroku simulace. Každý agent je pak schopen sestavit množinu součtů zisků |
---|
| 188 | $$ |
---|
| 189 | U = \{ u_{Tc_{-n}}, u_{Tc_{-n+1}}, ..., u_{Tc_{n-1}, u_{Tc_{n}}} \}, |
---|
| 190 | $$ |
---|
| 191 | kde |
---|
| 192 | $$ |
---|
| 193 | u_{Tc_i} = \sum_k u_{k_{Tc}}(Tc_i). |
---|
| 194 | $$ |
---|
| 195 | Agent poté zvolí takovou délku cyklu $Tc_i$, pro kterou platí |
---|
| 196 | $$ |
---|
| 197 | u_{Tc_i} = \max(U). |
---|
| 198 | $$ |
---|