Multiagent Monte Carlo Tree Search with Difference Evaluations and Evolved Rollout Policy

Loading...
Thumbnail Image

Authors

Zerbel, Nicholas A.

Issue Date

2018

Type

Thesis

Language

Keywords

Autonomous Control Systems , Monte Carlo Tree Search , Multiagent Path Planning , Multiagent Systems , Reinforcement Learning , Transfer Learning

Research Projects

Organizational Units

Journal Issue

Alternative Title

Abstract

Monte Carlo Tree Search (MCTS) is a best-first search algorithm that has produced many breakthroughs in AI research. MCTS has been applied to a wide variety of domains including turn-based board games, real-time strategy games, multiagent systems, and optimization problems. In addition to its ability to function in a wide variety of domains, MCTS is also a suitable candidate for performance improving modifications such as the improvement of its default rollout policy. In this work, we propose an enhancement to MCTS called Multiagent Monte Carlo Tree Search (MAMCTS) which incorporates multiagent credit evaluations in the form of Difference Evaluations. We show that MAMCTS can be successfully applied to a cooperative system called Multiagent Gridworld. We then show that the use of Difference Evaluations in MAMCTS offers superior control over agent decision making compared with other forms of multiagent credit evaluations, namely Global Evaluations. Furthermore, we show that the default rollout policy can be improved using a Genetic Algorithm, with (μ + λ) selection, resulting in a 37.6% increase in overall system performance within the training domain. Finally, we show that the trained rollout policy can be transferred to more complex multiagent systems resulting in as high as a 14.6% increase in system performance compared to the default rollout policy.

Description

Citation

Publisher

License

Creative Commons Attribution 4.0 United States

Journal

Volume

Issue

PubMed ID

DOI

ISSN

EISSN