New Flaw Search Strategies in CEGAR for Cartesian Abstractions in Optimal Classical Planning

Abstract

Background: Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost-optimal planning. The core idea is to start from the trivial abstraction—an abstract state representing all concrete states—and iteratively refine it in a loop by splitting one abstract state into two. Each iteration of the loop searches an optimal abstract plan and replicates it into the concrete state space until finding a flaw—and splitting such abstract state—or returning a plan for the task if no flaw is found. Previous work finds only a single flaw in progression, by executing the abstract plan from the initial state and stopping when execution cannot be continued.

Objectives: A theoretical framework for identifying different flaws of abstract plans, analysing their properties and using them to refine abstractions in different ways leading to higher-quality heuristics.

Methods: We show that alternative types of flaw can be defined. Specifically, we search flaws in regression from the goals—resulting in higher heuristic values—and identify sequence flaws along the whole abstract plan by searching them in a Cartesian relaxation of the task after the first flaw, which greatly increases the flexibility of refinements in CEGAR.

Results: Our experiments show that across existing benchmarks numerous sequence flaws exist in most abstract plans. We observe that the selected flaw has a high impact on the heuristic, and we propose several strategies that generate more informed abstractions. Overall, this greatly improves the performance of the baseline that only used the first progression flaw.

Conclusions: Guiding the CEGAR process by analysing multiple flaws of an abstract plan trace and selecting the best refinement can improve its performance as a tool to generate admissible heuristics in planning. Thus, using our new types of flaw and flaw selection strategies, we get stronger heuristics than the state-of-the-art planners based on Cartesian abstractions.