root/applications/doprava/texty/delka_cyklu/03_Agents/Agents.tex.backup @ 1148

\chapter{Multiagentní systémy}

\section{Úvod}

Multiagentí 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 ostaní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}

Multiagentí systémy jsou na poli počítačové vědy poměrně nnovinkou. Studium tohoto 
tématu probíhá od začátku osmdesátých let devatenácté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 
Wooldridge a Jennings(1995).

\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ě, stejně jako v našem případě, je prostředí nedeterministické. Stejná akce
provedená dvakrát za sebou nemusí vést ke stejnému výsledku.

\section{Prostředí}

Russel a Norvig navrhli klasifikaci prostředí podle jednotlivých parametrů následovně.

\subsection{Dostupné vs. nedostupné}

Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu.

\subsection{Deterministické vs. Nedetrministické}

Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt.

\subsection{Statické vs. dynamické}

Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty.

\subsection{Diskrétní vs. spojité}

V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí.

\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ěmě, že stav $\omega_1$ je preferován agentem $i$ nad stavem $\omega_2$,
pokud platí $u_i(\omega_1) \>= 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 $$
Transitivitu:
$$  \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.

\subsection{Akce agentů}
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žiny
$$ A = \{ a_1, a_2, ... \} $$
znázorňují množiny 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. $$

\begin{definition}[Dominance]
 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}


\section{Strategie}

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 agnenty, $i$ a $j$.
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 agnta i nejvýhodnější strategií $a_1$.

\subsection{Použití pro výběr délky cyklu}

Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupině společný.
Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií
$A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$
v dané situaci. Mějme funkci $u_{i_{Tc}} : A \rightarrow \mathbb{R} $, jejíž funkční hodnota v bodě $Tc_j$
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ě
(pro jednoduchost předpokládejme existenci dvou agentů $i$ a $j$)
$$
 u_i(\tau(Tc_k, Tc_l) = 
\left\{  
\begin{array}{r@{\quad}c}
 u_{i_{Tc}}(Tc_k) , & k = l \\
 - \infty , & k \neq l \\
\end{array}
\right.,
$$
kde hodnota $-\infty$ vyjadřuje jakýsi kolabs systému při nastavení různých délek cyklu.
To však znamená, že žádná strategie není sinlně dominantní nad jinou. Zároveň za předpokladu,
že agent $i$ zvolí strategii $Tc_l$, agent $j$ nemůže udělat lépe, než že zvolí stejnou strategii.
To znamená že pro všechny strategie $Tc_l \in A$ platí, že jsou v Nashově rovnosti samy se sebou.
Takto definovaná funkce nám v souladu s teorií zaručí, že agenti nenastaví různé délky cyklu, potřebujeme
ale dodatečné kritérium kterou délku cyklu vybrat.

\subsection{Globálně nějlepší řešení}
Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu.
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á.
Určíme tedy přirozená čísla $n$ a $dTc$. Množina možných strategií $A$ bude
$$
A = \{ Tc_{-n}, Tc_{-n+1}, ..., Tc_{n-1}, Tc_{n} \},
$$
$$
Tc_i = Tc + i \cdot dTc,
$$
kde $Tc$ je délka cyklu v minulém kroku simulace. Každý agent je pak schopen sestavit množinu součtů zisků
$$
U = \{ u_{Tc_{-n}}, u_{Tc_{-n+1}}, ..., u_{Tc_{n-1}, u_{Tc_{n}}} \},
$$
kde
$$ 
u_{Tc_i} = \sum_k u_{k_{Tc}}(Tc_i).
$$
Agent poté zvolí takovou délku cyklu $Tc_i$, pro kterou platí
$$
u_{Tc_i} = \max(U). 
$$