Online Refinement of Cartesian Abstraction Heuristics

Abstract

In classical planning as heuristic search, the guiding heuristic function is typically treated as a black box. While many heuristics support refinement operations, they are typically only used for its initialization before search, but further refinement during search could make use of additional information not available in the initial state. We explore online refinement for additive Cartesian abstraction heuristics. These abstractions are computed through counter-example guided abstraction refinement, which can be applied online as well to further improve the abstractions. We introduce three operations, refinement, merging, and reordering, which are combined to a converging online-refinement algorithm. We describe how online refinement can effectively be used in A* and evaluate our approach on the IPC benchmarks, where it outperforms offline-generated abstractions in many domains.