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) failures. |
| Seznam odborné literatury |
| Y. Shoham, K. Leyton-Brown: Multiagent systems: Algorithmic,
game-theoretic, and logical foundations. Cambridge University Press. 2008 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ý |