Motivace a inspirace

Přestože pravidla soutěže jsou na první pohled poměrně hodně jednoduchá, odrážejí několik zajímavých prvků a pojmů, které jsou poměrně aktuální (a které mohou udělat i z hry s jednoduchými pravidly pěkně komplikovanou záležitost). Zde popíšeme některé z těchto pojmů. Obeznámenost s níže uvedenými pojmy není nijak nezbytná pro účast na soutěži, ale alespoň zevrubné seznámení s nimi může být výhodou a zajímavou inspirací.

Úkol, který vás v soutěži čeká spočívá v podstatě v návrhu "decentralizovaného systému spolupracujících autonomních agentů". Reálné příklady (i tyto "reálné" systémy jsou zatím většinou ve fázi návrhu) takových systémů jsou například:

• autonomní navigace systémů pro objevování vesmíru (jedna z technologií testovaných u Deep Space 1, ve fázi návrhu jsou týmy autonomních robotů),
• internetoví agenti pro vyhledávání informací,
• roboti pro záchrané akce při katastrofách,
• týmy robotů hrající fotbal.

Nyní stručně okomentujeme některé základní pojmy, které se této oblasti týkají.

Autonomní agenti

An agent is a computer system that is capable of independent (autonomous) action on behalf of its user or owner (figuring out what needs to be done to satisfy design objectives, rather than constantly being told). (Michael Wooldridge)

Autonomní agent může být jak fyzický (zvíře, stroj) tak virtuální (bot, virus). Autonomní agent se pohybuje v určitém prostředí (les, oceán, Mars, váš žaludek, Internet) a na základě podnětů z tohoto prostředí se samostatně rozhoduje, co bude dělat dál.

Příklad architektury autonomního agenta (který by mohl být inspirací pro soutěž):

• planning module - na základě cílů agenta sestavuje plán, jak těchto cílů dosáhnout
• communication and coordination module - získává a zpracovává informace a podněty z okolí a od ostatních agentů
• scheduling module - rozhoduje konkrétní realizaci jednotlivých kroků plánu
• execution monitor - má na starosti spouštění a kontrolu korektní realizace akcí agenta
• exception-handling - vypořádává se s akcemi, které selhaly

Multiagent system

A multiagent system is one that consists of a number of agents, which interact with one-another. In the most general case, agents will be acting on behalf of users with different goals and motivations. To successfully interact, they will require the ability to cooperate, coordinate, and negotiate with each other, much as people do. (Michael Wooldridge)

The characteristics of MASs are that (1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint; (2) there is no system global control; (3) data are decentralized; and (4) computation is asynchronous. (Katia Sycara)

V takovémto systému, jak už název napovídá, máme (autonomních) agentů více. Agenti spolu nějakým způsobem spolupracují - může se jednat o fyzickou spolupráci nebo "jen" předávání informací. Spolupráce a interakce je většinou lokální - pouze mezi dvěma agenty či mezi malým počtem agentů.

Takovýto systém může být organizován různými způsoby (většina systémů je nějakým hybridem mezi těmito přístupy):

• Centralizovaně: Existuje jasná hierarchie (vůdce), v rámci které proudí pokyny "od shora". Příklady: většina strojů, vojsko, autokracie, centrálně plánovaný trh.
• Decentralizovaně: neexistuje hierarchie, všichni agenti jsou si "rovni", řízení a chování obecně je založeno na lokálních interakcích mezi jednotlivými agenty, dochází k sebe-organizaci "od spodu". Příklady: mraveniště, hejno, slumy, Internet, volný trh.

Decentralizované systémy vykazují oproti centralizovaným systémům podstatě vyšší robustnost (jsou odolnější proti narušení) a menší (potenciální) efektivitu.

Další související pojmy

• Decentralized artificial intelligence - úzce souvisí s "multiagent systems".
• Algoritmy pro volbu vůdce (leader election algorithms) - algoritmy sloužící k tomu, aby se z množiny (přibližně) identických agentů vybral jeden vůdce.
• Protokoly vzájemného vyloučení (mutual exclusion protocols) - protokoly, jejichž cílem je zaručit, že ke sdílenému zdroji bude vždy přistupovat pouze jeden process.
• Komprese zpráv (message packing) - způsoby jak přenášet co nejvíce informací pomocí omezeného kanálu.
• Obfuskace (obfuscation) - úprava zprávy/dokumentu, tak aby byl hůře pochopitelný.

Odkazy

• Multiagent Systems. Katia Sycara, AI magazine 19(2), 1998. Přehledový článek.
• Teambots.org: zaměřeno zejména na "týmové roboty", obsahuje mimo jiné simulovaný fotbal.
• NetLogo: systém pro programování s mnoha agenty. Obsahuje velmi pěkné příklady, které ilustrují uvedené pojmy (zejména decentralizované řízení).
• Multiagent systems: rozcestník o "multiagent systems".
• AgentLink: rozcestník o "agent technology".
• IV109 Modelování a simulace: předmět, který se částečně zabývá i decentralizovanými systémy a modelováním s využitím agentů.
• Termites, turtles, and traffic jams. Mitchel Resnick. The MIT Press, 1997 (dostupné v knihovně FI). Útlá kniha o decentralizovaném myšlení. Většina knihy spočívá v diskuzi různých příkladů (mravenci, termiti, zácpy). Psáno čtivě, pedagogicky, zajímavě.
• Introduction to MultiAgent Systems, Michael Wooldridge. John Wiley & Sons, 2002. Na webové stránce knihy je možno najít doprovodný materiál (např. slidy).
• RoboCup - turnaje robotů ve fotbale.
• Autonomous agent, multiagent system - stránky na wikipedii.