root/applications/doprava/texty/novotny_vyzk_LQ/02_Agents/Agents.tex @ 1421

\chapter{Multiagentní systémy}

\section{Úvod}

Multiagentní systém je druh distribuované umělé inteligence. Tento systém se skládá z
jednotlivých výpočetních prvků, tzv. agentů, které musí mít dvě základní schopnosti.
Zaprvé musí být schopni autonomní akce rozhodnutí - zjistit jak nejlépe dosáhnout
požadovaných cílů - a zadruhé je to schopnost interakce s ostatními agenty. V druhém případě nejde
jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí.

\subsection{Historie}

Multiagentní systémy jsou na poli počítačové vědy relativní novinkou. Studium tohoto 
tématu probíhá od začátku osmdesátých let dvacátého století. Větší pozornosti
se jim dostalo v polovině let devadesátých s rozvojem internetu. 

\subsection{Agent}

Neexistuje obecně uznávaná definice agenta. Přikloníme se k definici použité v publikaci 
\cite{wooldridge}.

\begin{definition}[Agent]\label{de:agent01}
Agent je počítačový systém umístěný do nějakého prostředí, který je schopen autonomní akce
k přiblížení se navrženým cílům.
\end{definition}


Agent v naprosté většině případů nemá celkovou kontrolu nad prostředím. Prostředí může ovlivňovat
jen částečně. Obecně je prostředí nedeterministické. Stejná akce provedená dvakrát za sebou 
nemusí vést ke stejnému výsledku.

\section{Druhy prostředí}

Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se
prostředí dají klasifikovat následovně:

\begin{itemize}
 \item Deterministické vs. nedeterministické
 \item Dostupné vs. nedostupné
 \item Statické vs. dynamické
\end{itemize}
Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt.
Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu.
Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty.
V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí.
% \\
% \\
% V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru),
% nedostupné (hodnoty se měří pouze jednou za 90 sekund, a ještě jsou zkreslené) a dynamické 
% (intenzita dopravy se mění nezávisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi
% znesnadňuje rozhodování a kontrolu vyvolaného výsledku.


\section{Interakce agentů}

\subsection{Stavy prostředí a preference agentů}

Mějme pro jednoduchost 2 agenty. Označme si je $i$ a $j$.
Předpokládejme, že máme množinu $$\Omega = \{\omega_1, \omega_2, ...\}$$ obsahující všechny možné stavy
prostředí, v kterém agenti operují. Aby byl agent schopen efektivně ovlivňovat prostření, musí být schopen
ohodnotit, jak je pro něj daný stav příznivý. Hodnocení daného stavu agenta $i$ a $j$ formálně definujeme jako funkce
$$u_i : \Omega \rightarrow \mathbb{R}, $$
$$u_j : \Omega \rightarrow \mathbb{R}. $$
Čím je stav $\omega$ příznivější pro agenta $i$, tím je větší hodnota funkce $u_i$.

\begin{definition}[Uspořádání na množině všech stavů]
 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$,
pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme
$$ \omega_1 \succeq_i \omega_2. $$
Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$,
pokud platí $u_i(\omega_1) > u_i(\omega_2)$. Značíme
$$ \omega_1 \succ_i \omega_2 $$
\end{definition}

Relace $ \succeq_i $ je zřejmě uspořádání, protože má všechny potřebné vlastnosti.
\newline
Reflexivitu:
$$  \forall \omega \in \Omega : \omega \succeq_i \omega $$
Tranzitivitu:
$$  \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$$
Porovnatelnost:
$$  \forall \omega_1, \omega_2 \in \Omega : \omega_1 \succeq_i \omega_2 \vee \omega_2 \succeq_i \omega_1 $$

Relace $\succ_i$ zjevně nesplňuje podmínky reflexivity.

\chapter{Výběr strategie genta}
Nyní popíšeme, jak mají agenti možnost ovlivňovat prostředí.
Opět předpokládejme existenci dvou agentů $i$ a $j$. Obecně mají
různí agenti různou oblast působnosti. Množina
$$ A = \{ a_1, a_2, ... \} $$
znázorňuje množinu všech akcí, které jsou agenti schopni provézt.
Na tyto akce reaguje prostředí přechodem do nějakého stavu $\omega \in \Omega$.
Formálně můžeme tento přechod zapsat jako funkci
$$ \tau : A \times A \rightarrow \Omega. $$




\section{Výběr strategie podle teorie her}

Popišme zde způsob, jak se agent rozhodne pro realizaci určité akce.
Agent je nyní schopen ohodnotit, který stav prostředí je pro něj příznivější než jiný,
neví však jak budou reagovat ostatní agenti, není schopen určit tudíž, i za předpokladu,
že by systém byl deterministický, do jakého stavu systém přejde. K výběru optimální akce
se používají prvky z teorie her. Zadefinujme nejprve v souladu s touto teorií základní pojmy.

\begin{definition}[Dominance množiny]
 Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $. 
Řekneme, že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí
$$
\forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'.
$$
Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí
$$
\forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'.
$$
\end{definition}

Abychom používali terminologii teorie her, budeme nyní akce $a_i \in A$ jednotlivých agentů
nazývat strategiemi.

\begin{definition}[Množina výsledků]
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$,
množinou možných výsledků. Označme ji
$$
a_i^* \subset \Omega.
$$
\end{definition}

\begin{definition}[Dominance strategie]
 Řekneme, že strategie $a_i$ je dominantní nad strategií $a_j$,
pokud je množina $a_i^*$ dominantní nad množinou $a_j^*$.
Strategie $a_i$ je silně dominantní nad strategií $a_j$,
pokud je množina $a_i^*$ silně dominantní nad množinou $a_j^*$.
\end{definition}

Racionálně uvažující agent tedy vyloučí všechny strategie $a_i$, jestliže existuje
strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zúžení výběru zbývajících
strategií slouží Nashova rovnost. Pro zjednodušení uvažujme 2 agenty, $i$ a $j$
\begin{definition}[Nashova rovnost]\label{de:nash_equlibrium}
 Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent 
  $i$ zvolí strategii $a_1$, je nejvýhodnější strategií pro agenta $j$ je strategie $a_2$ a zároveň
  pokud agent $j$ zvolí strategii $a_2$, je pro agenta i nejvýhodnější strategií $a_1$.
\end{definition}