Solving Non-deterministic Planning Problems with Pattern Database Heuristics

Solving Non-deterministic Planning Problems with Pattern Database Heuristics. Bercher, P. & Mattmüller, R. In Advances in Artificial Intelligence, Proceedings of the 32nd German Conference on Artificial Intelligence (KI 2009), pages 57–64, 2009. Springer.

Paper

Slides doi abstract bibtex 2 downloads

Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.

@InProceedings{Bercher2009FONDWithPDBHeuristics,
  author     = {Pascal Bercher and Robert Mattm{\"u}ller},
  title      = {Solving Non-deterministic Planning Problems with Pattern Database Heuristics},
  booktitle  = {Advances in Artificial Intelligence, Proceedings of the 32nd German Conference on Artificial Intelligence ({KI} 2009)},
  year       = {2009},
  pages      = {57--64},
  publisher  = {Springer},
  doi        = {10.1007/978-3-642-04617-9_8},
  abstract   = {Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.},
  url_Paper  = {https://bercher.net/publications/2009/Bercher2009FONDWithPDBHeuristics.pdf},
  url_Slides = {https://bercher.net/publications/2009/Bercher2009FONDWithPDBHeuristicsSlides.pdf},
  keywords   = {conference}
}

Downloads: 2