Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 354)
Detail práce
   Přihlásit přes CAS
Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
Název práce v češtině: Distribuovaný MCTS pro hry s týmem kooperujících agendů
Název v anglickém jazyce: Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
Klíčová slova: Multi-agentní systémy, Monte-Carlo tree search, distribuované algoritmy
Klíčová slova anglicky: Multi-agent systems, Monte-Carlo tree search, distributed algorithms
Akademický rok vypsání: 2012/2013
Typ práce: diplomová práce
Jazyk práce: angličtina
Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Vedoucí / školitel: Mgr. Viliam Lisý
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 16.11.2012
Datum zadání: 27.11.2012
Datum potvrzení stud. oddělením: 14.12.2012
Datum a čas obhajoby: 10.09.2013 00:00
Datum odevzdání elektronické podoby:29.07.2013
Datum odevzdání tištěné podoby:31.07.2013
Datum proběhlé obhajoby: 10.09.2013
Oponenti: Mgr. Vladan Majerech, Dr.
Zásady pro vypracování
Monte-Carlo tree search (MCTS) has been recently used to create strong
artificial players for wide variety of games. Thanks to its fast
convergence and anytime property, it has been also suggested as a
suitable algorithm for canonical multi-robot application, such as
Pursuit-evasion games. The naive approach for using MCTS in a team
environment is to produce the solution centrally in the joint
configuration space of the robots. On the other hand, this approach
does not scale well with increasing number of agents and in real-world
multi-robot applications, it fails due to unreliable communication and
hardware failures. Distributed, loosely-coupled algorithms could offer
a solution to both these problems.

In this work, the student will design, implement, and evaluate
distributed algorithms for planning actions of a team of autonomous
agents in a game environment. He will review the related research on
Monte-Carlo tree search and distributed coordination algorithms for
autonomous agents. He will design a set of algorithms with different
scalability trade-offs and communication requirements. He will
implement the algorithms in an existing simulation of a multi-agent
game with a team of players, such as a pursuit-evasion game. He will
experimentally evaluate and compare the developed algorithms in terms
of quality of the game play, computational time, the amount of
communication and the robustness of the approach to (communication)

Seznam odborné literatury
Y. Shoham, K. Leyton-Brown: Multiagent systems: Algorithmic,
game-theoretic, and logical foundations. Cambridge University Press.

G. Chaslot, M. H. M. Winands , H. Herik, J. Uiterwijk, B. Bouzy:
Progressive strategies for monte-carlo tree search. New Mathematics
and Natural Computation, 4(3), 343-358. 2008

G. Chaslot, M. H. M. Winands , H. Herik: Parallel monte-carlo tree
search. Computers and Games. 60-71. 2008

R. Zivan, R. Glinton, K. Sycara: Distributed constraint optimization for
large teams of mobile sensing agents. IEEE/WIC/ACM International Joint
Conferences on Web Intelligence and Intelligent Agent Technologies,
347-354, 2009

K. Q. Nguyen, R. Thawonmas: Applying Monte-Carlo Tree Search to
collaboratively controlling of a Ghost Team in Ms Pac-Man. IEEE
International Games Innovation Conference (IGIC), 8-11, 2011
Předběžná náplň práce
Externí vedoucí: V. Lisý
Univerzita Karlova | Informační systém UK