root/applications/doprava/texty/novotny_vyzk_LQ/03_RMM/RMM.tex @ 1434

\section{RMM - Rekurzivní modelové metody} 


Rekurzivní modelová metoda, která byla použita
v článku \cite{4_rmm_formalization} k modelování chování
agentů ovládajících ostatní dopravní uzly, slouží k odhadu chování ostatních a gentů.
Akce každého agenta z pravidla ovlivňuje do určité míry celý systém, tudíž
výběr strategie každého agenta závisí na předpokládaném chování ostatních. 
Tato metoda minimalizuje nutnost komunikace a vyjednávání o provedení jisté akce tím,
že každý agent je schopen modelovat rozhodnutí ostatních a podle známých parametrů
prostředí s určitou pravděpodobností stanovit jejich volbu.



\subsection{Formální definice}

Základním stavebním kamenem RMM je matice zisků agenta, Definovaná v souladu s teorií her v \cite{4_rmm_formalization}

\begin{definition}[Matice zisků]\label{de:payoff_matrix}
  Matice zisků $P_{R_i}$ agenta $R_i$ je definována trojicí
  $$(R, A, U)$$
  kde $R$ je množina všech agentů v systému, 
  $A$ je množina množin $A_j = \{a_1^j, a_2^j, ...\}$ alternativních akcí agenta $R_j$. 
  $A_j$ budeme nazývat rozhodovací prostor agenta $R_j$.
  $U$ je funkce 
  $$U : A_1 \times A_2 \times ... \times A_n \rightarrow \mathbb{R}$$
  přiřazující hodnoty zisku všem kombinacím akcí všech agentů.
\end{definition}
Každý agent provádí danou akci z nějakého důvodu. Zisky agenta $R_i$ jsou spojeny s
provedením jeho určité akce $a_m^i \in A_i$ za předpokladu, že ostatní agenti $R_j, j \in \{1 .. n \} / \{i\} $
provedou akci $a_k^j \in A_j$. Matice je tedy $n$-dimenzionální, kde $n$ je počet agentů v systému, a sestává
se z prvků $u^{R_i}_{a_k^1 ... a_l^i ... a_m^n}$, reprezentující zisky v dané situaci.
\\
K určení pravděpodobnosti provedení strategií ostatních agentů se v publikaci \cite{4_rmm_formalization}
definuje rekursivní modelová struktura. 

\begin{definition}[Rekursivní modelová struktura]\label{de:rms}
 Rekursivní modelová struktura $RMS_{R_i}$ agenta $R_i$ je definována jako dvojice
  $$ (P_{R_i}, RM_{R_i}) \;,$$
 kde $P_{R_i}$ je matice zisků definovaná v \ref{de:payoff_matrix} a $RM_{R_i}$
 je rekurzivní model \ref{de:rm}, který je použit k modelování rozhodování ostatních agentů. 
\end{definition}

Rekursivní model je definován v \cite{4_rmm_formalization} takto:

\begin{definition}[Rekursivní model]\label{de:rm}
  Rekursivní model $MR_{R_i}$ agenta $R_i$ je definován jako $m$-tice dvojic \footnotemark
  $$ MR_{R_i} = ( (p^{R_i}_1, M^{(R_i, 1)}_{\{-R_i\}}), ... ,(p^{R_i}_m, M^{(R_i, m)}_{\{-R_i\}}) ) \;, $$ 
  kde
  $$ M^{(R_i, k )}_{\{-R_i\}} = ( M^{(R_i, k )}_{R_1}, ... , M^{(R_i, k )}_{R_{i-1}}, M^{(R_i, k )}_{R_{i+1}}, ... ,M^{(R_i, k )}_{R_n} )$$
  představuje jednu z $m$ $(n-1)$-tic rozhodovacích modelů ostatních agentů a $p_i^k$ jeho subjektivní předpokládanou pravděpodobnost.  
\end{definition}
\footnotetext{$\{-R_i\}$ je zkrácený zápis množiny ostatních agentů $ \{R_1, ..., R_n\} / \{R_i\} $}

$M^{(R_i, k )}_{R_j}$ je tedy jeden z možných modelů agenta $R_j$, který předpokládá agent $R_i$
s pravděpodobností $p^{R_i}_k$. Platí samozřejmě podmínka $\sum_{k=1}^m p^{R_i}_k = 1$.
\\
Model $M^{(R_i, k )}_{R_j}$ se dá podle \cite{4_rmm_formalization} rozdělit do tří forem:

\begin{itemize}
 \item $IM^{(R_i, k )}_{R_j}$ - Recionální model
 \item $NM^{(R_i, k )}_{R_j}$ - Neinformovaný model
 \item $SM^{(R_i, k )}_{R_j}$ - Neracionální model
\end{itemize}

Recionální model odpovídá tomu, že agent $R_i$ předpokládá o agentovi $R_j$, že se chová racionálně.
V \cite{4_rmm_formalization} je definován jako

$$
  IM^{(R_i, k )}_{R_j} = RMS_{R_j}^{(R_i, k)} \;, 
$$

s parametry $p^{(R_i, k)}_{a^j_l}$ a $P_{R_j}^{(R_i, k)} $.
$P_{R_j}^{(R_i, k)} $ je matice zisků, kterou podle agenta $R_i$ v modelu $k$ agent $R_j$ použije,
což je rekurzivní modelové struktura s $k$-tými daty, o kterých agent $R_i$ předpokládá,
že je agent $R_j$ použije k rozhodování.\\

Neinformovaný model vychází z toho, že agent $R_i$ nemá o agentovi $R_j$ žádné informace, tudíž přiřadí každé
akci $a^{R_j}_l$ pravděpodobnost $p^{(R_i, k)}_{a^j_l} = \frac{1}{|A_j|}$, kde $|A_j|$ je počet možných akcí agenta $R_j$, 
což odpovídá rovnoměrnému rozdělení.
$p^{(R_i, k)}_{a^j_l}$ značí pravďěpodobnost, že podle agenta $R_i$ nastane v $k$-tém modelu agenta $R_j$ akce $a^j_l$.\\

Neracionální model odpovídá tomu, že se agent $A_j$ chová iracionálně. Chování se v tomto případě modeluje 
podle situace pokaždé jinak.\\

Systém se tedy rekurzivně rozvijí, dokud jsou dostupné informace. Pokud nejsou, rekurze skončí neinformovaným modelem
s rovnoměrným rozdělením pravděpodobnosti všech akcí. Rekurze také může skončit iracionálním modelem, což ovšem není 
v našem případě příliš časté.

\subsection{Rozhodovací algoritmus}

Po zkonstruování rekurzivní modelové struktury se prochází tento systém od konce rekurze, kde jsou pravděpodobnosti
známi, z důvodu ukončení rekurzivního rozvijení neinformovaným modelem. K výběru nejpravděpodobnější situace se používá
tzv. užitečnosti. \cite{4_rmm_formalization}

\begin{definition}[Užitečnost]\label{de:utility}
  Užitečnost akce $a^i_m$ podle agenta $R_i$ je definována jako
  $$ 
  u^{R_i}_{a^i_m}  = 
  \sum_{a^1_q \in A_1} ...
  \sum_{a^{i-1}_v \in A_{i-1}}
  \sum_{a^{i+1}_w \in A_{i+1}} ...
  \sum_{a^n_x \in A_n} 
  ( p^{R_i}_{a^1_q} ... p^{R_i}_{a^{i-1}_v} p^{R_i}_{a^{i-1}_w} ...  p^{R_i}_{a^n_x}  u^{R_i}_{ a^1_q ... a^i_m ... a^n_x } ) \;,
  $$
  kde 
  $$ u^{R_i}_{ a^1_q ... a^n_x } $$ 
  je prvek matice zisků $P_{R_i}$ a pravděpodobnost $ p^{R_i}_{a_o^j} $ je definována jako
  $$ p^{R_i}_{a_k^j} = \sum_{o} p^{R_i}_o p^{(R_i, o)}_{a_k^j} \;,$$
\end{definition}
kde $p^{R_i}_o$ je pravděpodobnost modelu z definice \ref{de:rm} a 
$p^{(R_i, o)}_{a_k^j} $ značí pravďěpodobnost, že podle agenta $R_i$ 
nastane v $o$-tém modelu agenta $R_j$ akce $a^j_k$. V případě, že je algoritmus v bodě racionálního modelu,
určí se tato hodnota rekurzivně, pokud je model neinformovaný, je rovna $\frac{1}{|A_j|}$.
$ p^{R_i}_{a_k^j}$ je tedy součet pravděpodobností dané akce v modelu vyvážený jeho pravděpodobností
a $ u^{R_i}_{a^i_m} $ se definuje jako součet všech prvků matice zisků, kromě těch, které zahrnují jiné akce agenta 
$R_i$, než je $a_k^j$, vyvažený touto pravděpodobností.