Pattern Database Heuristics for Fully Observable Nondeterministic Planning

Pattern Database Heuristics for Fully Observable Nondeterministic Planning. Mattmüller, R., Ortlieb, M., Helmert, M., & Bercher, P. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pages 105–112, 2010. AAAI Press.

Paper doi abstract bibtex

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 and 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 in selected domains our approach is competitive with symbolic regression search in terms of problem coverage and speed, and that plan sizes are often significantly smaller than with symbolic regression search.

@InProceedings{Mattmueller2010NondeterministicPlanning,
  author    = {Robert Mattm{\"u}ller and Manuela Ortlieb and Malte Helmert and Pascal Bercher},
  title     = {Pattern Database Heuristics for Fully Observable Nondeterministic Planning},
  booktitle = {Proceedings of the 20th International Conference on Automated Planning and Scheduling ({ICAPS} 2010)},
  year      = {2010},
  pages     = {105--112},
  publisher = {{AAAI} Press},
  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 and 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 in selected domains our approach is competitive with symbolic regression search in terms of problem coverage and speed, and that plan sizes are often significantly smaller than with symbolic regression search.},
  doi       = {10.1609/icaps.v20i1.13408},
  url_Paper = {https://bercher.net/publications/2010/Mattmueller2010NondeterministicPlanning.pdf},
  keywords  = {conference}
}

Downloads: 0