Domain-independent construction of pattern database heuristics for cost-optimal planning

Abstract

Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing ad-missible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on abstractions of the search space, are currently one of the most promising approaches to developing better ad-missible heuristics. The informedness of PDB heuristics de-pends crucially on the selection of appropriate abstractions (patterns). Although PDBs have been applied to many search problems, including planning, there are not many insights into how to select good patterns, even manually. What con-stitutes a good pattern depends on the problem domain, mak-ing the task even more difcult for domain-independent plan-ning, where the process needs to be completely automatic and general. We present a novel way of constructing good pat-terns automatically from the specication of planning prob-lem instances. We demonstrate that this allows a domain-independent planner to solve planning problems optimally in some very challenging domains, including a STRIPS formu-lation of the Sokoban puzzle.