Galvan, Edgar and Li, Ruohua and Patsakis, Constantinos and Clarke, Siobhan and Cahill, Vinny (2014) Heuristic-Based Multi-Agent Monte Carlo Tree Search. IISA 2014, The 5th International Conference on Information, Intelligence, Systems and Applications. pp. 177-182.

Preview

Download (291kB) | Preview

Abstract

Monte Carlo Tree Search (MCTS) is a relatively new sampling best-first method to search for optimal decisions. The MCTS' popularity is based on its extraordinary results in the challenging two-player based game Go, a game considered much harder than Chess and that until very recently was considered unfeasible for Artificial Intelligence methods. Different MCTS variants have been proposed, mainly to enhance its capabilities. Perhaps, one of the main limitations of this approach is its applicability in scenarios where multiple agents (more than two) are required. Some works have made an attempt to overcome this limitation by using a vector of reward values for each agent and allowing the algorithm to find an optimal equilibrium strategy. Inspired by these approaches, in this work we make an effort to explore a new proposal for handling multiple agents in MCTS by using a vector of values of what the agents need to do (defined tasks) instead of a vector of rewards for each agent. To achieve this we use a rather simple, but powerful heuristic that estimates the desired values of this vector. That is, a set of values that could lead to the optimal completion of the task. We tested this idea in a real-world scenario rather than using it in games as traditionally done. The results achieved by our proposed approach, named Heuristic-Based Multi-Agent Monte Carlo Tree Search, indicate the feasibility of using heuristics in the MCTS algorithm in situations where more than two agents are required.

Item Type:	Article
Keywords:	Monte Carlo Tree Search; Heuristics; Demand Side Management Systems;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	15360
Identification Number:	https://doi.org/10.1109/IISA.2014.6878747
Depositing User:	Edgar Galvan
Date Deposited:	31 Jan 2022 14:05
Journal or Publication Title:	IISA 2014, The 5th International Conference on Information, Intelligence, Systems and Applications
Publisher:	IEEE
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads