[1428] | 1 | \chapter{Matematické metody rozhodování} |
---|
| 2 | |
---|
| 3 | \section{Multiagentní systémy} |
---|
| 4 | |
---|
| 5 | Multiagentní systém je druh distribuované umělé inteligence, jehož základem je |
---|
| 6 | agent - výpočetní prvek schopný autonomní reakce, komunikace a koordinace. |
---|
| 7 | Každý agent je schopen vyhodnotit optimální chování v dané situaci, |
---|
| 8 | které závisí i na akoci ostatních agentů. Ke sploupráci jednotlivých |
---|
| 9 | agentů slouží různe metody vejednávání a predikce chování. |
---|
| 10 | |
---|
| 11 | \subsection{Historie} |
---|
| 12 | |
---|
| 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 |
---|
| 15 | se jim dostalo v polovině let devadesátých s rozvojem internetu. |
---|
| 16 | |
---|
| 17 | \subsection{Agent} |
---|
| 18 | |
---|
| 19 | Obecně uznávaná definice agenta neexistuje. Jedna z možných je uvedena například v publikaci |
---|
| 20 | \cite{wooldridge}: |
---|
| 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 | \subsection{Druhy prostředí} |
---|
| 29 | |
---|
| 30 | Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se |
---|
| 31 | prostředí dají klasifikovat následovně: |
---|
| 32 | |
---|
| 33 | \begin{itemize} |
---|
| 34 | \item Deterministické vs. nedeterministické |
---|
| 35 | \item Dostupné vs. nedostupné |
---|
| 36 | \item Statické vs. dynamické |
---|
| 37 | \end{itemize} |
---|
| 38 | Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. |
---|
| 39 | Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu. |
---|
| 40 | Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. |
---|
| 41 | V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. |
---|
| 42 | % \\ |
---|
| 43 | % \\ |
---|
| 44 | % V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru), |
---|
| 45 | % nedostupné (hodnoty se měří pouze jednou za 90 sekund, a ještě jsou zkreslené) a dynamické |
---|
| 46 | % (intenzita dopravy se mění nezávisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi |
---|
| 47 | % znesnadňuje rozhodování a kontrolu vyvolaného výsledku. |
---|
| 48 | |
---|
| 49 | |
---|
| 50 | |
---|
| 51 | |
---|
| 52 | \subsection{Stavy prostředí a preference agentů} |
---|
| 53 | |
---|
| 54 | Mějme pro jednoduchost 2 agenty. Označme si je $i$ a $j$. |
---|
| 55 | Předpokládejme, že máme množinu $$\Omega = \{\omega_1, \omega_2, ...\}$$ obsahující všechny možné stavy |
---|
| 56 | prostředí, v kterém agenti operují. Aby byl agent schopen efektivně ovlivňovat prostření, musí být schopen |
---|
| 57 | ohodnotit, jak je pro něj daný stav příznivý. Hodnocení daného stavu agenta $i$ a $j$ formálně definujeme jako funkce |
---|
| 58 | $$u_i : \Omega \rightarrow \mathbb{R}, $$ |
---|
| 59 | $$u_j : \Omega \rightarrow \mathbb{R}. $$ |
---|
| 60 | Čím je stav $\omega$ příznivější pro agenta $i$, tím je větší hodnota funkce $u_i$. |
---|
| 61 | |
---|
| 62 | \begin{definition}[Uspořádání na množině všech stavů] |
---|
| 63 | 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$, |
---|
| 64 | pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme |
---|
| 65 | $$ \omega_1 \succeq_i \omega_2. $$ |
---|
| 66 | Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$, |
---|
| 67 | pokud platí $u_i(\omega_1) > u_i(\omega_2)$. Značíme |
---|
| 68 | $$ \omega_1 \succ_i \omega_2 $$ |
---|
| 69 | \end{definition} |
---|
| 70 | |
---|
| 71 | Relace $ \succeq_i $ je zřejmě uspořádání, protože má všechny potřebné vlastnosti. |
---|
| 72 | \newline |
---|
| 73 | Reflexivitu: |
---|
| 74 | $$ \forall \omega \in \Omega : \omega \succeq_i \omega $$ |
---|
| 75 | Tranzitivitu: |
---|
| 76 | $$ \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$$ |
---|
| 77 | Porovnatelnost: |
---|
| 78 | $$ \forall \omega_1, \omega_2 \in \Omega : \omega_1 \succeq_i \omega_2 \vee \omega_2 \succeq_i \omega_1 $$ |
---|
| 79 | |
---|
| 80 | Relace $\succ_i$ zjevně nesplňuje podmínky reflexivity. |
---|
| 81 | |
---|
| 82 | |
---|
| 83 | \section{Výběr strategie podle teorie her} |
---|
| 84 | |
---|
| 85 | Nyní, jak je rozebíráno v \cite{wooldridge}, 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žina |
---|
| 88 | $$ A = \{ a_1, a_2, ... \} $$ |
---|
| 89 | znázorňuje množinu 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 | Popišme zde způsob, jak se agent rozhodne pro realizaci určité akce. |
---|
| 95 | Agent je nyní schopen ohodnotit, který stav prostředí je pro něj příznivější než jiný, |
---|
| 96 | neví však jak budou reagovat ostatní agenti, není schopen určit tudíž, i za předpokladu, |
---|
| 97 | že by systém byl deterministický, do jakého stavu systém přejde. K výběru optimální akce |
---|
| 98 | se používají prvky z teorie her. Zadefinujme nejprve v souladu s touto teorií základní pojmy. |
---|
| 99 | |
---|
| 100 | \begin{definition}[Dominance množiny] |
---|
| 101 | Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $. |
---|
| 102 | Řekneme, že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 103 | $$ |
---|
| 104 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'. |
---|
| 105 | $$ |
---|
| 106 | Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí |
---|
| 107 | $$ |
---|
| 108 | \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'. |
---|
| 109 | $$ |
---|
| 110 | \end{definition} |
---|
| 111 | |
---|
| 112 | Abychom používali terminologii teorie her, budeme nyní akce $a_i \in A$ jednotlivých agentů |
---|
| 113 | nazývat strategiemi. |
---|
| 114 | |
---|
| 115 | \begin{definition}[Množina výsledků] |
---|
| 116 | 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$, |
---|
| 117 | množinou možných výsledků. Označme ji |
---|
| 118 | $$ |
---|
| 119 | a_i^* \subset \Omega. |
---|
| 120 | $$ |
---|
| 121 | \end{definition} |
---|
| 122 | |
---|
| 123 | \begin{definition}[Dominance strategie] |
---|
| 124 | Řekneme, že strategie $a_i$ je dominantní nad strategií $a_j$, |
---|
| 125 | pokud je množina $a_i^*$ dominantní nad množinou $a_j^*$. |
---|
| 126 | Strategie $a_i$ je silně dominantní nad strategií $a_j$, |
---|
| 127 | pokud je množina $a_i^*$ silně dominantní nad množinou $a_j^*$. |
---|
| 128 | \end{definition} |
---|
| 129 | |
---|
| 130 | Racionálně uvažující agent tedy vyloučí všechny strategie $a_i$, jestliže existuje |
---|
| 131 | strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zúžení výběru zbývajících |
---|
| 132 | strategií slouží Nashova rovnost. Pro zjednodušení uvažujme 2 agenty, $i$ a $j$ |
---|
| 133 | \begin{definition}[Nashova rovnost]\label{de:nash_equlibrium} |
---|
| 134 | Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent |
---|
| 135 | $i$ zvolí strategii $a_1$, je nejvýhodnější strategií pro agenta $j$ je strategie $a_2$ a zároveň |
---|
| 136 | pokud agent $j$ zvolí strategii $a_2$, je pro agenta i nejvýhodnější strategií $a_1$. |
---|
| 137 | \end{definition} |
---|
| 138 | |
---|
| 139 | |
---|
| 140 | |
---|
| 141 | |
---|