Cartesian Abstraction Refinement for Simple Numeric Planning

Abstract

Cartesian abstractions are a successful approach for obtaining admissible heuristics in optimal classical planning. In this paper, we generalize the counterexample-guided abstraction refinement (CEGAR) algorithm to compute Cartesian abstractions for simple numeric planning. Specifically, our CEGAR algorithm operates on a special form of Cartesian states consisting of a single interval per numeric variable. We prove that, in the absence of zero-cost actions, this algorithm is semi-complete and optimal. Our experimental evaluation shows that our approach performs similarly to other abstraction heuristics and provides better heuristic estimates in multiple domains.