Pattern Database Heuristics for Fully Observable Nondeterministic Planning

Authors

  • Robert Mattmüller University of Freiburg
  • Manuela Ortlieb University of Freiburg
  • Malte Helmert University of Freiburg
  • Pascal Bercher University of Ulm

DOI:

https://doi.org/10.1609/icaps.v20i1.13408

Keywords:

strong cyclic planning, PDB heuristics

Abstract

When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that our approach is competitive with symbolic regression search in terms of problem coverage, speed, and plan quality.

Downloads

Published

2021-05-25

How to Cite

Mattmüller, R., Ortlieb, M., Helmert, M., & Bercher, P. (2021). Pattern Database Heuristics for Fully Observable Nondeterministic Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 20(1), 105-112. https://doi.org/10.1609/icaps.v20i1.13408