Admissible Landmark Heuristic for Multi-Agent Planning

Authors

  • Michal Štolba Czech Technical University in Prague
  • Daniel Fišer Czech Technical University in Prague
  • Antonín Komenda Czech Technical University in Prague

DOI:

https://doi.org/10.1609/icaps.v25i1.13719

Keywords:

multiagent planning, distributed planning, distributed heuristic, admissible heuristic, landmarks

Abstract

Heuristics are a crucial component in modern planning systems. In optimal multiagent planning the state of the art is to compute the heuristic locally using only information available to a single agent. This approach has a major deficiency as the local shortest path can arbitrarily underestimate the true shortest path cost in the global problem. As a solution, we propose a distributed version of a state-of-the-art LM-Cut heuristic. We show that our distributed algorithm provides estimates provably equal to estimates of the centralized version computed on the global problem. We also evaluate the algorithm experimentally and show that on a number of domains, the distributed algorithm can significantly improve performance of a multiagent planner.

Downloads

Published

2015-04-08

How to Cite

Štolba, M., Fišer, D., & Komenda, A. (2015). Admissible Landmark Heuristic for Multi-Agent Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 211-219. https://doi.org/10.1609/icaps.v25i1.13719