Show
Ignore:
Timestamp:
07/27/10 06:50:13 (14 years ago)
Author:
jabu
Message:
 
Location:
applications/doprava/texty/delka_cyklu/03_Agents
Files:
2 modified

Legend:

Unmodified
Added
Removed
  • applications/doprava/texty/delka_cyklu/03_Agents/Agents.tex

    r1147 r1150  
    33\section{Úvod} 
    44 
    5 Multiagentí systém je druh distribuované umělé inteligence. Tento systém se skládá z 
     5Multiagentní systém je druh distribuované umělé inteligence. Tento systém se skládá z 
    66jednotlivých výpočetních prvků, tzv. agentů, které musí mít dvě základní schopnosti. 
    77Zaprvé 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 ostaními agenty. V druhém případě nejde 
     8požadovaných cílů a zadruhé je to schopnost interakce s ostatními agenty. V druhém případě nejde 
    99jen o pouhou výměnu dat, ale o typ kolektivní aktivity - návrh, potvrzení, odmítnutí. 
    1010 
    1111\subsection{Historie} 
    1212 
    13 Multiagentí systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto  
     13Multiagentní systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto  
    1414tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti 
    1515se jim dostalo v polovině let devadesátých s rozvojem internetu.  
     
    1818 
    1919Neexistuje obecně uznávaná definice agenta. Přikloníme se k definici použité v publikaci  
    20 Wooldridge a Jennings(1995). 
     20\cite{wooldridge}. 
    2121 
    2222\begin{definition}[Agent]\label{de:agent01} 
     
    3232\section{Druhy prostředí} 
    3333 
    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í. 
     34Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se 
     35prostředí dají klasifikovat následovně: 
    3636 
    3737\begin{itemize} 
    38  \item Deterministické vs. Nedetrministické 
     38 \item Deterministické vs. nedeterministické 
    3939 \item Dostupné vs. nedostupné 
    4040 \item Statické vs. dynamické 
    4141\end{itemize} 
    4242Deterministické 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. 
     43Prostředí je dostupné, pokud agent může zjistit jeho úplný stav v kteroukoliv dobu. 
    4444Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. 
    4545V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. 
     
    4747\\ 
    4848V 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 
     49nedostupné (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 
    5151znesnadňuje rozhodování a kontrolu vyvolaného výsledku. 
    5252 
     
    6565 
    6666\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$, 
    6868pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme 
    6969$$ \omega_1 \succeq_i \omega_2. $$ 
     
    7777Reflexivitu: 
    7878$$  \forall \omega \in \Omega : \omega \succeq_i \omega $$ 
    79 Transitivitu: 
     79Tranzitivitu: 
    8080$$  \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$$ 
    8181Porovnatelnost: 
     
    136136 
    137137Racioná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ích 
    139 strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 agnenty, $i$ a $j$. 
     138strategie $a_j$, která nad strategií $a_i$ silně dominuje. K zúžení výběru zbývajících 
     139strategií slouží Nashova Rovnost. Pro zjednodušení uvažujme 2 agenty, $i$ a $j$. 
    140140Dvě strategie, $a_1$ a $a_2$ jsou v Nashově rovnosti, pokud za předpokladu že agent  
    141141$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 agnta i nejvýhodnější strategií $a_1$. 
     142pokud agent $j$ zvolí strategii $a_2$, je pro agenta i nejvýhodnější strategií $a_1$. 
    143143 
    144144\subsection{Použití pro výběr délky cyklu} 
    145145 
    146 Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupině společný. 
     146Dé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ý. 
    147147Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií 
    148148$A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ 
     
    159159\right., 
    160160$$ 
    161 kde hodnota $-\infty$ vyjadřuje jakýsi kolabs systému při nastavení různých délek cyklu. 
    162 To však znamená, že žádná strategie není sinlně dominantní nad jinou. Zároveň za předpokladu, 
     161kde hodnota $-\infty$ vyjadřuje jakýsi kolaps systému při nastavení různých délek cyklu. 
     162To však znamená, že žádná strategie není silně dominantní nad jinou. Zároveň za předpokladu, 
    163163že agent $i$ zvolí strategii $Tc_l$, agent $j$ nemůže udělat lépe, než že zvolí stejnou strategii. 
    164164To znamená že pro všechny strategie $Tc_l \in A$ platí, že jsou v Nashově rovnosti samy se sebou. 
     
    166166ale dodatečné kritérium kterou délku cyklu vybrat. 
    167167 
    168 \subsection{Globálně nějlepší řešení} 
     168\subsection{Globálně nejlepší řešení} 
    169169Komunikace agentům dovoluje vzájemně si předat předpokládané zisky pro určitou délku cyklu. 
    170170Nejprve 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á. 
     
    190190Toto 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á 
    191191nejvě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 
     195V 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 
     196se 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 
     197o 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 
     198do výběru strategie. 
  • applications/doprava/texty/delka_cyklu/03_Agents/Agents.tex.backup

    r1147 r1150  
    1111\subsection{Historie} 
    1212 
    13 Multiagentí systémy jsou na poli počítačové vědy poměrně nnovinkou. Studium tohoto  
     13Multiagentí systémy jsou na poli počítačové vědy poměrně novinkou. Studium tohoto  
    1414tématu probíhá od začátku osmdesátých let devatenáctého století. Větší pozornosti 
    1515se jim dostalo v polovině let devadesátých s rozvojem internetu.  
     
    3030provedená dvakrát za sebou nemusí vést ke stejnému výsledku. 
    3131 
    32 \section{Prostředí} 
     32\section{Druhy prostředí} 
    3333 
    34 Russel a Norvig navrhli klasifikaci prostředí podle jednotlivých parametrů následovně. 
     34Způsob práce agentů se liší podle druhu prostředí, ve kterém pracují. Podle \cite{wooldridge} se 
     35prostředí dají klasifikovat následovně: 
    3536 
    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} 
     42Deterministické prostředí je takové, ve kterém má každá jednotlivá akce předem daný efekt. 
     43Prostředí je dostupné, pokud agent múže zjistit jeho úplný stav v kteroukoliv dobu. 
     44Statické prostředí se na rozdíl od dynamického mění pouze vlivem akcí vyvolanými agenty. 
     45V diskrétním prostředí existuje pevné konečné číslo možných vjemů a akcí. 
     46\\ 
     47\\ 
     48V našem případě je prostředí nedeterministické (agent pouze odhaduje vliv přenastavení parametru), 
     49nedostupné (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 
     51znesnadňuje rozhodování a kontrolu vyvolaného výsledku. 
    3752 
    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í. 
    5153 
    5254\section{Interakce agentů} 
     
    6466\begin{definition}[Uspořádání na množině všech stavů] 
    6567 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číme 
     68pokud platí $u_i(\omega_1) \geqq u_i(\omega_2)$. Značíme 
    6769$$ \omega_1 \succeq_i \omega_2. $$ 
    6870Stav $\omega_1$ je silně preferován agentem $i$ nad stavem $\omega_2$, 
    69 pokud platí $u_i(\omega_1) \> u_i(\omega_2)$. Značíme 
     71pokud platí $u_i(\omega_1) > u_i(\omega_2)$. Značíme 
    7072$$ \omega_1 \succ_i \omega_2 $$ 
    7173\end{definition} 
     
    9294$$ \tau : A \times A \rightarrow \Omega. $$ 
    9395 
    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 $$ 
    10496 
    105 \end{definition} 
    10697 
    10798 
     
    153144\subsection{Použití pro výběr délky cyklu} 
    154145 
    155 Délka cyklu řadiče křižovatky je parametr, který je pro všechny křižovatky ve skupině společný. 
     146Dé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ý. 
    156147Nesmí tedy dojít k situaci, kdy by každý agent nastavil jinou délku cyklu. Množina strategií 
    157148$A = \{ a_1, a_2, ... \}$ je tedy v našem případě množinou všech nastavitelných délek cyklu $Tc_k$ 
     
    197188u_{Tc_i} = \max(U).  
    198189$$  
     190Toto 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á 
     191nejvě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í} 
     194V 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 
     195S bude optimalizace provádět pro každou skupinu zvlášť. jak dále popíšeme v \ref{ss:odhad_fronty}