Research map / Learning theory and algorithms / Combinatorial and search optimization
When CEGAR Meets Regression: A Love Story in Optimal Classical Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes backward (regression-based) flaw detection for CEGAR-generated Cartesian abstraction heuristics in optimal classical planning, plus bidirectional forward/backward refinement strategies, improving Scorpion coverage.
Problem
Cost-optimal classical planning relies on CEGAR-generated Cartesian abstraction heuristics, but all existing flaw detection executes abstract plans forward from the initial state, leaving the refinement guidance under-explored.
Approach
Find flaws by regressing the abstract plan backward from the goal rather than progressing it from the initial state, yielding regression flaws that identify invalid plan suffixes; the resulting abstractions are less focused on the initial state but more informative on average, and can be combined with forward refinements in bidirectional strategies.
Key results
- Scorpion with backward refinements (Sb) solves 743 tasks vs 727 for forward-only Sf in the Scorpion configuration, and Sb-f is among the best bidirectional strategies.
- In single abstractions, backward Cb is significantly worse than forward Cf within CEGAR (Cf solves 34 more tasks in CEGAR) but yields far better heuristics when used with search (Cb solves 30 fewer tasks with Cf in CEGAR-only; overall search coverage 427 vs 397 for Cf).
- Backward refinements find regression flaws closer to the goal in about 99% of cases for single abstractions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace forward refinements with backward regression refinements | Scorpion single-abstraction CEGAR · Autoscale 21.11 | coverage with A* search: 397 -> 427 | Helped |
| Replace forward refinements with backward regression refinements | Scorpion single-abstraction CEGAR · Autoscale 21.11 | coverage within CEGAR: 112 -> 78 | Hurt |
| Use backward refinements instead of forward refinements | Scorpion additive abstractions · Autoscale 21.11 | coverage: 480 -> 490 | Helped |
| Interleave backward and forward refinements | Scorpion additive abstractions · Autoscale 21.11 | coverage: 480 -> 493 | Helped |
| Use backward refinements instead of forward refinements | Scorpion configuration · Autoscale 21.11 | coverage: 727 -> 743 | Helped |
| Use backward refinements, then forward refinements | Scorpion configuration · Autoscale 21.11 | coverage: 727 -> 740 | Helped |
| Use backward refinements instead of forward refinements | Single abstractions · Logistics p04 | average heuristic value: 9.9 -> 11.7 | Helped |
| Use backward refinements instead of forward refinements | Single abstractions · Transport p02 | average heuristic value: 133 -> 221 | Helped |
| Use backward refinements instead of forward refinements | Single abstractions · DataNetwork p08 | average heuristic value: 5.8 -> 2.2 | Hurt |
| Use backward refinements instead of forward refinements | Scorpion single-abstraction CEGAR · Autoscale 21.11 | initial heuristic value | Hurt |
| Combine backward and forward refinements | Scorpion single-abstraction CEGAR · Autoscale 21.11 | coverage with A* search: Cb: 427; Cb-f: 426; Cf-b: 411; Cbd: 414 | Mixed |
| Disable the pre-loop goal refinement optimization for backward and bidirectional methods | Scorpion CEGAR · Autoscale 21.11 | performance | Helped |
Surprising findings
- Backward refinements yield abstractions with lower initial-state heuristic values h0 in single abstractions yet produce more informative heuristics overall, leading to fewer expansions.
- CEGAR with backward flaws solves fewer tasks within the CEGAR loop itself than forward flaws, while the resulting heuristics solve more tasks when combined with search.
Limitations
- Backward abstractions converge more slowly toward the optimal plan and yield lower h0 in single abstractions.
- Regression flaws are not guaranteed to occur close to the goal, and abstract plans without regression flaws may be non-mappable.
Experimental setup
Datasets: Autoscale 21.11 benchmark set
Benchmarks: Autoscale 21.11 (42 domains, 1260 tasks)
Metrics: coverage expansions until last f-layer initial state heuristic value h0 average heuristic value
Baselines: Cf (forward CEGAR refinement) Sbatch (batch refinement Scorpion) Scorpion 2018 Complementary2
Builds on: CEGAR for Cartesian abstractions (Seipp and Helmert) Scorpion planner saturated cost partitioning batch refinement (Speck and Seipp 2022)
Closest papers by meaning
- Not Everything Is Permitted: Constrained Cartesian Abstractions for Optimal Classical Planning (AAAI 2026 · similarity 0.88)
- An Effective Polynomial Technique for Compiling Conditional Effects Away (AAAI 2024 · similarity 0.86)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.84)
- Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans (AAAI 2025 · similarity 0.84)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.83)
- An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.