@inproceedings{659fa137fe3e443d8752862b93a2882b,
title = "Solving non-deterministic planning problems with pattern database heuristics",
abstract = "Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using A* 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.",
keywords = "Heuristic search, Non-deterministic planning, PDB heuristics",
author = "Pascal Bercher and Robert Mattm{\"u}ller",
year = "2009",
doi = "10.1007/978-3-642-04617-9\_8",
language = "English",
isbn = "978-3-642-04616-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer Berlin",
pages = "57--64",
booktitle = "KI 2009: Advances in Artificial Intelligence",
address = "Germany",
note = "32nd Annual German Conference on Artificial Intelligence, KI 2009 ; Conference date: 15-09-2009 Through 18-09-2009",
}