Monte Carlo Tree Search for Multi-Robot Task Allocation

Authors

  • Bilal Kartal University of Minnesota
  • Ernesto Nunes University of Minnesota
  • Julio Godoy University of Minnesota
  • Maria Gini University of Minnesota

DOI:

https://doi.org/10.1609/aaai.v30i1.9945

Keywords:

Monte Carlo Tree Search, Optimization, Search

Abstract

Multi-robot teams are useful in a variety of task allocation domains such as warehouse automation and surveillance. Robots in such domains perform tasks at given locations and specific times, and are allocated tasks to optimize given team objectives. We propose an efficient, satisficing and centralized Monte Carlo TreeSearch based algorithm exploiting branch and bound paradigm to solve the multi-robot task allocation problem with spatial, temporal and other side constraints. Unlike previous heuristics proposed for this problem, our approach offers theoretical guarantees and finds optimal solutions for some non-trivial data sets.

Downloads

Published

2016-03-05

How to Cite

Kartal, B., Nunes, E., Godoy, J., & Gini, M. (2016). Monte Carlo Tree Search for Multi-Robot Task Allocation. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.9945