Changeset 1150 for applications/doprava/texty/delka_cyklu/03_Agents
- Timestamp:
- 07/27/10 06:50:13 (14 years ago)
- Location:
- applications/doprava/texty/delka_cyklu/03_Agents
- Files:
-
- 2 modified
-
Agents.tex (modified) (10 diffs)
-
Agents.tex.backup (modified) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
-
applications/doprava/texty/delka_cyklu/03_Agents/Agents.tex
r1147 r1150 3 3 \section{Úvod} 4 4 5 Multiagent í systém je druh distribuované umělé inteligence. Tento systém se skládá z5 Multiagentní systém je druh distribuované umělé inteligence. Tento systém se skládá z 6 6 jednotlivých výpočetních prvků, tzv. agentů, které musí mít dvě základní schopnosti. 7 7 Zaprvé musí být schopni autonomní akce rozhodnutí - zjistit jak nejlépe dosáhnout 8 požadovaných cílů a zadruhé je to schopnost interakce s osta ními agenty. V druhém případě nejde8 požadovaných cílů a zadruhé je to schopnost interakce s ostatními agenty. V druhém případě nejde 9 9 jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí. 10 10 11 11 \subsection{Historie} 12 12 13 Multiagent í systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto13 Multiagentní systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto 14 14 tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti 15 15 se jim dostalo v polovině let devadesátých s rozvojem internetu. … … 18 18 19 19 Neexistuje obecně uznávaná definice agenta. Přikloníme se k definici použité v publikaci 20 Wooldridge a Jennings(1995).20 \cite{wooldridge}. 21 21 22 22 \begin{definition}[Agent]\label{de:agent01} … … 32 32 \section{Druhy prostředí} 33 33 34 Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. 35 Prostředí se dají klasifikovat podle tří vlastností. 34 Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se 35 prostředí dají klasifikovat následovně: 36 36 37 37 \begin{itemize} 38 \item Deterministické vs. Nedetrministické38 \item Deterministické vs. nedeterministické 39 39 \item Dostupné vs. nedostupné 40 40 \item Statické vs. dynamické 41 41 \end{itemize} 42 42 Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. 43 Prostředí je dostupné, pokud agent m úže zjistit jeho úplný stav v kteroukoliv dobu.43 Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu. 44 44 Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. 45 45 V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. … … 47 47 \\ 48 48 V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru), 49 nedostupné (hodnoty se měří pouze jednou za 90 sekund, a ještě jsou zkreslené) a dynamické50 (intenzita dopravy se mění nez évisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi49 nedostupné (hodnoty se měří pouze jednou za 90 sekund, a ještě jsou zkreslené) a dynamické 50 (intenzita dopravy se mění nezávisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi 51 51 znesnadňuje rozhodování a kontrolu vyvolaného výsledku. 52 52 … … 65 65 66 66 \begin{definition}[Uspořádání na množině všech stavů] 67 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$,67 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$, 68 68 pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme 69 69 $$ \omega_1 \succeq_i \omega_2. $$ … … 77 77 Reflexivitu: 78 78 $$ \forall \omega \in \Omega : \omega \succeq_i \omega $$ 79 Tran sitivitu:79 Tranzitivitu: 80 80 $$ \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$$ 81 81 Porovnatelnost: … … 136 136 137 137 Racionálně uvažující agent tedy vyloučí všechny strategie $a_i$, jestliže existuje 138 strategie $a_j$, která nad strategií $a_i$ silně dominuje. K z ůžení výběru zbývajících139 strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 ag nenty, $i$ a $j$.138 strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zúžení výběru zbývajících 139 strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 agenty, $i$ a $j$. 140 140 Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent 141 141 $i$ zvolí strategii $a_1$, je nejvýhodnější strategií pro agenta $j$ je strategie $a_2$ a zároveň 142 pokud agent $j$ zvolí strategii $a_2$, je pro ag nta i nejvýhodnější strategií $a_1$.142 pokud agent $j$ zvolí strategii $a_2$, je pro agenta i nejvýhodnější strategií $a_1$. 143 143 144 144 \subsection{Použití pro výběr délky cyklu} 145 145 146 Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupiněspolečný.146 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ý. 147 147 Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií 148 148 $A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ … … 159 159 \right., 160 160 $$ 161 kde hodnota $-\infty$ vyjadřuje jakýsi kola bs systému při nastavení různých délek cyklu.162 To však znamená, že žádná strategie není si nlně dominantní nad jinou. Zároveň za předpokladu,161 kde hodnota $-\infty$ vyjadřuje jakýsi kolaps systému při nastavení různých délek cyklu. 162 To však znamená, že žádná strategie není silně dominantní nad jinou. Zároveň za předpokladu, 163 163 že agent $i$ zvolí strategii $Tc_l$, agent $j$ nemůže udělat lépe, než že zvolí stejnou strategii. 164 164 To znamená že pro všechny strategie $Tc_l \in A$ platí, že jsou v Nashově rovnosti samy se sebou. … … 166 166 ale dodatečné kritérium kterou délku cyklu vybrat. 167 167 168 \subsection{Globálně n ějlepší řešení}168 \subsection{Globálně nejlepší řešení} 169 169 Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu. 170 170 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á. … … 190 190 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á 191 191 největší součet zisků od všech agentů nad časem, u kterého předpokládá největší zisk pro sebe. 192 193 \subsection{Rozšíření} 194 195 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 196 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 197 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 198 do výběru strategie. -
applications/doprava/texty/delka_cyklu/03_Agents/Agents.tex.backup
r1147 r1150 11 11 \subsection{Historie} 12 12 13 Multiagentí systémy jsou na poli počítačové vědy poměrně n novinkou. Studium tohoto13 Multiagentí systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto 14 14 tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti 15 15 se jim dostalo v polovině let devadesátých s rozvojem internetu. … … 30 30 provedená dvakrát za sebou nemusí vést ke stejnému výsledku. 31 31 32 \section{ Prostředí}32 \section{Druhy prostředí} 33 33 34 Russel a Norvig navrhli klasifikaci prostředí podle jednotlivých parametrů následovně. 34 Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se 35 prostředí dají klasifikovat následovně: 35 36 36 \subsection{Dostupné vs. nedostupné} 37 \begin{itemize} 38 \item Deterministické vs. Nedetrministické 39 \item Dostupné vs. nedostupné 40 \item Statické vs. dynamické 41 \end{itemize} 42 Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. 43 Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu. 44 Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. 45 V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. 46 \\ 47 \\ 48 V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru), 49 nedostupné (hodnoty se měří pouze jednou za 90 sekund, aještě jsou zkreslené) a dynamické 50 (intenzita dopravy se mění nezévisle na akcích agenta). Je zřejmé, že prostředí s těmito vlastnostmi 51 znesnadňuje rozhodování a kontrolu vyvolaného výsledku. 37 52 38 Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu.39 40 \subsection{Deterministické vs. Nedetrministické}41 42 Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt.43 44 \subsection{Statické vs. dynamické}45 46 Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty.47 48 \subsection{Diskrétní vs. spojité}49 50 V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí.51 53 52 54 \section{Interakce agentů} … … 64 66 \begin{definition}[Uspořádání na množině všech stavů] 65 67 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$, 66 pokud platí $u_i(\omega_1) \ >=u_i(\omega_2)$. Značíme68 pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme 67 69 $$ \omega_1 \succeq_i \omega_2. $$ 68 70 Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$, 69 pokud platí $u_i(\omega_1) \> u_i(\omega_2)$. Značíme71 pokud platí $u_i(\omega_1) > u_i(\omega_2)$. Značíme 70 72 $$ \omega_1 \succ_i \omega_2 $$ 71 73 \end{definition} … … 92 94 $$ \tau : A \times A \rightarrow \Omega. $$ 93 95 94 \begin{definition}[Dominance]95 Mějme 2 podmnožiny $ \Omega_1, \Omega_2 \subset \Omega $.96 Řekneme že $\Omega_1$ je pro agenta $i$ dominantní nad množinou $\Omega_2$, pokud platí97 $$98 \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succeq_i \omega'.99 $$100 Řekneme že $\Omega_1$ je pro agenta $i$ silně dominantní nad množinou $\Omega_2$, pokud platí101 $$102 \forall \omega \in \Omega_1, \forall \omega' \in \Omega_2 : \omega \succ_i \omega'.103 $$104 96 105 \end{definition}106 97 107 98 … … 153 144 \subsection{Použití pro výběr délky cyklu} 154 145 155 Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupiněspolečný.146 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ý. 156 147 Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií 157 148 $A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ … … 197 188 u_{Tc_i} = \max(U). 198 189 $$ 190 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á 191 největší součet zisků od všech agentů nad časem, u kterého předpokládá největší zisk pro sebe. 192 193 \subsection{Rozšíření} 194 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 195 S bude optimalizace provádět pro každou skupinu zvlášť. jak dále popíšeme v \ref{ss:odhad_fronty}
