Trial-Based Heuristic Tree-Search for Distributed Multi-Agent Planning

Authors

  • Tim Schulte University of Freiburg
  • Bernhard Nebel University of Freiburg

DOI:

https://doi.org/10.1609/socs.v10i1.18506

Abstract

We present a novel search scheme for privacy-preserving multi-agent planning. Inspired by UCT search, the scheme is based on growing an asynchronous search tree by running repeated trials through the tree. We describe key differences to classical multi-agent forward search, discuss theoretical properties of the presented approach, and evaluate it based on benchmarks from the CoDMAP competition. As a secondary contribution, we describe a technique that extends the regular search approach by small explorative trials which are performed subsequent to each node expansion. We show that this technique significantly increases the number of problems solved for all algorithms considered, including MAFS.

Downloads

Published

2021-09-01