Domain-Abstraction Heuristics for Simple Numeric Planning

Abstract

Abstraction heuristics are among the most effective approaches in optimal classical planning. For numeric planning, however, existing abstraction heuristics suffer from the infiniteness of the abstract state spaces, which is an immediate consequence of numeric state variables. This has recently been analyzed for numeric Pattern Database (PDB) heuristics, which fall short of their classical-planning counterpart due to fundamental limitations in the handling of unbounded variable domains. In this work, we argue that domain abstractions offer a framework that lends itself much better to simple numeric planning, with abstract state spaces that are computed incrementally using counterexample-guided abstraction refinement (CEGAR), avoiding the exhaustive exploration of PDBs. We extend the established framework from classical planning such that the typically infinite concrete state space is fully represented in the abstraction, and adapt the CEGAR mechanism to support refining numeric abstractions. To obtain a strong search guidance, we combine multiple domain abstractions admissibly using the canonical heuristic. Our empirical evaluation exemplifies the potential of domain abstractions for numeric planning.