Research map / Learning theory and algorithms / Combinatorial and search optimization
Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans
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 a method that repairs flawed lifted PDDL domains using both positive plans (should be feasible) and negative counter-example plans (should be infeasible), returning a cardinality-minimum repair set via conflict-based hitting set search.
Problem
Automated planning domain models often contain modeling errors; existing repair methods only use positive plans (infeasible in the flawed domain but feasible in the true domain), ignoring negative plans that are valid in the flawed domain but infeasible in reality.
Approach
Extends diagnosis-style conflict-based domain repair (Lin, Grastien, and Bercher 2023) to handle negative plans by computing conflicts that enumerate repairs making the first inapplicable action occur at the specified position, and finds a cardinality-minimum repair set satisfying both positive and negative plans.
Key results
- On randomized-error FD domains, the approach achieves higher precision than the positive-only baseline in more than half of benchmarks and higher recall in almost every domain (e.g., FREECELL recall 0.55 vs 0.35).
- On bespoke benchmarks, the approach reaches 1.00 precision and 1.00 recall on all three, while the positive-only baseline finds no repairs for two of them (clear and free).
- Most domain repair instances finish within 100 seconds, with many under 10 seconds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use positive and negative plans instead of positive plans only | Domain repair approach · BlocksWorld benchmark with clear precondition errors | recall: 0.00 -> 1.00 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · Gripper benchmark with free predicate errors | precision: 0.00 -> 1.00 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · TETRIS | recall: 0.10 -> 0.40 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · FREECELL | recall: 0.35 -> 0.55 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · WOODWORKING11 | precision: 0.30 -> 0.53 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · LOGISTICS00 | precision: 0.80 -> 0.50 | Hurt |
| Use positive and negative plans instead of positive plans only | Domain repair approach · LOGISTICS98 | recall: 0.35 -> 0.45 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · BLOCKSWorld with handempty errors | recall: 0.30 -> 1.00 | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · Randomized-error IPC domains | recall | Helped |
| Use positive and negative plans instead of positive plans only | Domain repair approach · Randomized-error IPC domains | precision | Mixed |
| Use positive and negative plans instead of positive plans only | Domain repair approach · Randomized-error IPC domains | runtime | Hurt |
Surprising findings
- The positive-only baseline finds no repairs at all for the BlocksWorld (clear) and Gripper (free) bespoke flaws, since those flaws only over-relax the domain and so no positive plan fails.
Limitations
- Assumes the inapplicable action in each negative plan is given explicitly
- Runtime is higher than the positive-only baseline due to larger search space
- Cannot change action parameter lists; hitting-set solver randomness causes precision variance
Experimental setup
Datasets: IPC/Fast Downward benchmark domains BlocksWorld (handcrafted flaws) Gripper (handcrafted flaws)
Benchmarks: 15 flawed FD domains with randomized errors 3 handcrafted BlocksWorld/Gripper domains with bespoke errors
Metrics: precision recall runtime
Baselines: Lin, Grastien, and Bercher (2023) positive-plan repair
Builds on: Lin, Grastien, and Bercher 2023 (positive-plan domain repair) Reiter diagnosis Struss and Dressler complex conflicts
Closest papers by meaning
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.87)
- An Effective Polynomial Technique for Compiling Conditional Effects Away (AAAI 2024 · similarity 0.84)
- When CEGAR Meets Regression: A Love Story in Optimal Classical Planning (AAAI 2024 · similarity 0.84)
- Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models (NeurIPS 2024 · similarity 0.83)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.83)
- Property-Guided LLM Program Synthesis for Planning (NeurIPS 2026 · similarity 0.82)
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.