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

\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ě, 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{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.

\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ž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{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 agenty, $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 agenta 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 agenty ve skupině zahrnující křižovatky do zelené vlny 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 kolaps systému při nastavení různých délek cyklu.
To však znamená, že žádná strategie není silně 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ě nejlepší ř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). 
$$ 
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á
největší součet zisků od všech agentů nad časem, u kterého předpokládá největší zisk pro sebe.

\subsection{Rozšíření}

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
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
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
do výběru strategie.