[1419] | 1 | \section{RMM - Rekurzivní modelové metody} |
---|
| 2 | |
---|
| 3 | |
---|
| 4 | Rekurzivní modelová metoda, která byla použita |
---|
| 5 | v článku \cite{4_rmm_formalization} k modelování chování |
---|
| 6 | agentů ovládajících ostatní dopravní uzly, slouží k odhadu chování ostatních a gentů. |
---|
| 7 | Akce každého agenta z pravidlo ovlivňuje do určité míry celý systém, tudíž |
---|
| 8 | výběr strategie každého agenta závisí na předpokládaném chování ostatních |
---|
| 9 | agentů. Tato metoda minimalizuje nutnost komunikace a vyjednávání o provedení jisté akce tím, |
---|
| 10 | že každý agent je schopen modelovat rozhodnutí ostatních a podle známých parametrů |
---|
| 11 | prostředí s určitou pravděpodobností stanovit jejich volbu. |
---|
| 12 | |
---|
| 13 | |
---|
| 14 | |
---|
| 15 | \subsection{Formální definice} |
---|
| 16 | |
---|
| 17 | Základním stavebním kamenem RMM je matice zisků agenta, Definovaná v souladu s teorií her v \cite{4_rmm_formalization} |
---|
| 18 | |
---|
| 19 | \begin{definition}[Matice zisků]\label{de:payoff_matrix} |
---|
| 20 | Matice zisků $P_{R_i}$ agenta $R_i$ je definována trojicí |
---|
| 21 | $$(R, A, U)$$ |
---|
| 22 | kde $R$ je množina všech agentů v systému, |
---|
| 23 | $A$ je množina množin $A_j = \{a_1^j, a_2^j, ...\}$ alternativních akcí agenta $R_j$. |
---|
| 24 | $A_j$ budeme nazývat rozhodovací prostor agenta $R_j$. |
---|
| 25 | U je funkce |
---|
| 26 | $$U : A_1 \times A_2 \times ... \times A_n \rightarrow \mathbb{R}$$ |
---|
| 27 | přiřazující hodnoty zisku všem kombinacím akcí všech agentů. |
---|
| 28 | \end{definition} |
---|
| 29 | Každý agent provádí danou akci z nějakého důvodu. Zisky agenta $R_i$ jsou spojeny s |
---|
| 30 | 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\} $ |
---|
| 31 | 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á |
---|
| 32 | se z prvků $u^{R_i}_{a_k^1 ... a_l^i ... a_m^n}$, reprezentující zisky v dané situaci. |
---|
| 33 | \\ |
---|
| 34 | K určení pravděpodobnosti provedení strategií ostatních agentů se definuje rekursivní modelová struktura. \cite{4_rmm_formalization} |
---|
| 35 | |
---|
| 36 | \begin{definition}[Rekursivní modelová struktura]\label{de:rms} |
---|
| 37 | Rekursivní modelová struktura $RMS_{R_i}$ agenta $R_i$ je definována jako dvojice |
---|
| 38 | $$ (P_{R_i}, RM_{R_i}) $$, |
---|
| 39 | kde $P_{R_i}$ je matice zisků definovaná v \ref{de:payoff_matrix} a $RM_{R_i}$ |
---|
| 40 | je rekurzivní model \ref{de:rm}, který je použit k modelování rozhodování ostatních agentů. |
---|
| 41 | \end{definition} |
---|
| 42 | |
---|
| 43 | Rekursivní model je definován v \cite{4_rmm_formalization} takto: |
---|
| 44 | |
---|
| 45 | \begin{definition}[Rekursivní model]\label{de:rm} |
---|
| 46 | Rekursivní model $MR_{R_i}$ agenta $R_i$ je definován jako $m$-tice dvojic \footnotemark |
---|
| 47 | $$ MR_{R_i} = ( (p^{R_i}_1, M^{(R_i, 1)}_{\{-R_i\}}), ... ,(p^{R_i}_m, M^{(R_i, m)}_{\{-R_i\}}) ) $$ |
---|
| 48 | kde |
---|
| 49 | $$ 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} )$$ |
---|
| 50 | 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. |
---|
| 51 | \end{definition} |
---|
| 52 | \footnotetext{$\{-R_i\}$ je zkrácený zápis množiny ostatních agentů $ \{R_1, ..., R_n\} / \{R_i\} $} |
---|
| 53 | |
---|
| 54 | $M^{(R_i, k )}_{R_j}$ je tedy jeden z možných modelů agenta $R_j$, který předpokládá agent $R_i$ |
---|
| 55 | s pravděpodobností $p^{R_i}_k$. Platí samozřejmě podmínka $\sum_{k=1}^m p^{R_i}_k = 1$. |
---|
| 56 | \\ |
---|
| 57 | Model $M^{(R_i, k )}_{R_j}$ se dá podle \cite{4_rmm_formalization} rozdělit do tří forem: |
---|
| 58 | |
---|
| 59 | \begin{itemize} |
---|
| 60 | \item $IM^{(R_i, k )}_{R_j}$ - Recionální model |
---|
| 61 | \item $NM^{(R_i, k )}_{R_j}$ - Neinformovaný model |
---|
| 62 | \item $SM^{(R_i, k )}_{R_j}$ - Neracionální model |
---|
| 63 | \end{itemize} |
---|
| 64 | |
---|
| 65 | Recionální model odpovídá tomu, že agent $R_i$ předpokládá o agentovi $R_j$, že se chová racionálně. |
---|
| 66 | V \cite{4_rmm_formalization} je definován jako |
---|
| 67 | |
---|
| 68 | $$IM^{(R_i, k )}_{R_j} = RMS_{R_j}^{(R_i, k)}$$, |
---|
| 69 | |
---|
| 70 | s parametry $p^{(R_i, k)}_{a^j_l}$ a $P_{R_j}^{(R_i, k)} $. |
---|
| 71 | $P_{R_j}^{(R_i, k)} $ je matice zisků, kterou podle agenta $R_i$ v modelu $k$ agent $R_j$ použije. |
---|
| 72 | což je Rekurzivní modelové struktura s $k$-tými daty, o kterých agent $R_i$ předpokládá, |
---|
| 73 | že je agent $R_j$ použije k rozhodování.\\ |
---|
| 74 | |
---|
| 75 | Neinformovaný model vychází z toho, že agent $R_i$ nemá o agentovi $R_j$ žádné informace, tudíž přiřadí každé |
---|
| 76 | 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$, |
---|
| 77 | což odpovídá rovnoměrnému rozdělení. |
---|
| 78 | $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$.\\ |
---|
| 79 | |
---|
| 80 | Neracionální model odpovídá tomu, že se agent $A_j$ chová iracionálně. Chování se v tompto případě modeluje |
---|
| 81 | podle situace pokaždé jinak.\\ |
---|
| 82 | |
---|
| 83 | Systém se tedy rekurzivně rozvijí, dokud jsou dostupné informace. Pokud nejsou, rekurze skončí neinformovaným modelem |
---|
| 84 | 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í |
---|
| 85 | v našem případě příliš časté. |
---|
| 86 | |
---|
| 87 | \subsection{Rozhodovací algoritmus} |
---|
| 88 | |
---|
| 89 | Po zkonstruování rekurzivní modelové struktury se prochází tento systém od konce rekurze, kde jsou pravděpodobnosti |
---|
| 90 | známi, z důvodu ukončení rekurzivního rozvijení neinformovaným modelem. K výběru nejpravděpodobnější situace se používá |
---|
| 91 | tzv. užitečnosti. \cite{4_rmm_formalization} |
---|
| 92 | |
---|
| 93 | \begin{definition}[Užitečnost]\label{de:utility} |
---|
| 94 | Užitečnost akce $a^i_m$ podle agenta $R_i$ je definována jako |
---|
| 95 | $$ |
---|
| 96 | u^{R_i}_{a^i_m} = |
---|
| 97 | \sum_{a^1_q \in A_1} ... |
---|
| 98 | \sum_{a^{i-1}_v \in A_{i-1}} |
---|
| 99 | \sum_{a^{i+1}_w \in A_{i+1}} ... |
---|
| 100 | \sum_{a^n_x \in A_n} |
---|
| 101 | ( 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 } ) |
---|
| 102 | $$, |
---|
| 103 | kde |
---|
| 104 | $$ u^{R_i}_{ a^1_q ... a^n_x } $$ |
---|
| 105 | je prvek matice zisků $P_{R_i}$ a pravděpodobnost $ p^{R_i}_{a_o^j} $ je definována jako |
---|
| 106 | $$ p^{R_i}_{a_k^j} = \sum_{o} p^{R_i}_o p^{(R_i, o)}_{a_k^j} $$. |
---|
| 107 | |
---|
| 108 | |
---|
| 109 | \end{definition} |
---|
| 110 | |
---|
| 111 | kde $p^{R_i}_o$ je pravděpodobnost modelu z definice \ref{de:rm} a |
---|
| 112 | $p^{(R_i, o)}_{a_k^j} $ značí pravďěpodobnost, že podle agenta $R_i$ |
---|
| 113 | 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, |
---|
| 114 | určí se tato hodnota rekurzivně, pokud je model neinformovaný, je rovna $\frac{1}{|A_j|}$. |
---|
| 115 | $ p^{R_i}_{a_k^j}$ je tedy součet pravděpodobností dané akce v modelu vyvážený pravděpodobností modelu |
---|
| 116 | 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 |
---|
| 117 | $R_i$, než je $a_k^j$, vyvažený touto pravděpodobností. |
---|
| 118 | |
---|