Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
| Thesis title in Czech: | Distribuovaný MCTS pro hry s týmem kooperujících agendů |
|---|---|
| Thesis title in English: | Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents |
| Key words: | Multi-agentní systémy, Monte-Carlo tree search, distribuované algoritmy |
| English key words: | Multi-agent systems, Monte-Carlo tree search, distributed algorithms |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | Mgr. Viliam Lisý |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 16.11.2012 |
| Date of assignment: | 27.11.2012 |
| Confirmed by Study dept. on: | 14.12.2012 |
| Date and time of defence: | 10.09.2013 00:00 |
| Date of electronic submission: | 29.07.2013 |
| Date of submission of printed version: | 31.07.2013 |
| Date of proceeded defence: | 10.09.2013 |
| Opponents: | Mgr. Vladan Majerech, Dr. |
| Guidelines |
| 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. |
| References |
| 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 |
| Preliminary scope of work |
| Externí vedoucí: V. Lisý |