Conformant planning asks for a single sequence of actions that reaches the goal no matter which of many possible starting states the world is actually in. The set of states the agent cannot rule out is called its belief state, and the number of possible belief states grows as $2^{2^n}$ in the number $n$ of true/false facts. The fastest current planners avoid searching over belief states at all. They guess a plan and ask a satisfiability (SAT) solver for one starting state where the plan fails, called a counterexample or witness. They then call an ordinary single-state planner to patch the plan for that state, and repeat. Which counterexample gets patched next is left to the solver's internal heuristics, or it is chosen for how many unresolved sub-conditions it exposes. Neither rule considers how hard the patch will be. Yet the patch is where almost all the time goes.
We propose to choose the next counterexample by expected coverage per unit of repair effort. Before committing, the planner asks the SAT solver for several distinct failing states. It estimates how expensive each would be to patch, using the case-based reasoning idea that similarity should be measured by adaptation effort, and patches the one that retires the most remaining failures per unit cost. It also records the realized cost of every patch and uses that record to improve its estimates as refinement proceeds. The claim is that repair difficulty varies widely across the counterexamples available at a given iteration, and that exploiting this variance cuts both classical-planner time and plan bloat relative to arbitrary or coverage-only selection.
Where this sits
The belief-explosion side supplies the architecture we modify. Generate-and-Complete turns conformant planning into repeated repair of a seed plan with the LAMA classical planner, reaching 93% coverage (727/777). It tests states in a fixed order and cannot recover from a seed that commits to an unrepairable path. iGC replaces sequential testing with SAT verification over the whole belief state and prunes redundant loops. It solves 989 of 1,179 instances across 50 domains, but its counterexamples are whatever the SAT solver happens to return. SUPERB is the closest prior work. Inside the sampling-based planner CPCES, it asks the solver for counterexamples that satisfy the most unaddressed "tags" (logical conditions naming contingencies), which cuts BOMB iterations from 61 to 3. SUPERB optimizes information per iteration. It never asks what a given counterexample costs the sub-planner. Our selection rule adds that denominator, and the experiments test whether it matters.
The case-based reasoning side supplies the method. CHEF and DERSNLP+EBL showed that problems that look alike can need very different repairs; in 4-goal Logistics, retrieval by learned failure indices took 32 s against 916 s for surface-feature retrieval. That misalignment motivates us: a counterexample that looks "rich" by tag count may be the hardest to patch. RCR predicts adaptation cost from stored records of past adaptations, discounted by how dissimilar the current context is, and needed 36 memory operations per adaptation against 65 for semantic similarity. We reuse its estimator almost directly, with "adaptation cases" being prior patches within the same refinement run. Yang and Zhu's case-addition policy defines a case's "functional neighborhood" as the problems it can solve within bounded adaptation cost, and greedily maximizes covered neighborhoods, with a 63% approximation guarantee. Our selection rule is the cost-weighted analogue of that greedy step, applied to witnesses rather than stored cases.
These sources constrain us in two ways. RCR reports that estimator overhead was offset by savings only in preliminary tests, and Fang et al. note that front-end translation time can already exceed solve time. So any per-iteration overhead must be measured, not assumed away.
Core Claim
At refinement step $t$, let $W_t$ be a set of $k$ distinct failing states returned by the SAT solver. Diversity is enforced with blocking clauses, which forbid the solver from returning a state it has already given. For each witness $w \in W_t$ we pick
$$ w_t^\ast = \arg\max_{w \in W_t} \frac{\hat g(w)}{\hat c(w) + \lambda}. $$
Here $\hat g(w)$ is the estimated number of currently failing states, or unaddressed tags, that a patch for $w$ would also fix. $\hat c(w)$ is the estimated repair effort, measured in node expansions by the classical planner. $\lambda > 0$ is a fixed per-iteration overhead that keeps very cheap patches from dominating.
$\hat g$ comes from the regression condition of $w$'s failure point: states that fail on the same precondition at the same plan step are counted as jointly repairable. $\hat c$ is RCR-style. It is the realized cost of the most similar previously patched witness, scaled by a dissimilarity penalty. Before any history exists, it falls back to a delete-relaxation heuristic evaluated from $w$'s state at the failure point.
After patching we log the actual cost, so the estimator improves within the run. When a patch exceeds its budget, the witness is deferred rather than treated as fatal. This gives a principled way around some of the dead ends that make Generate-and-Complete incomplete. It does not restore completeness in general.
Research Program
The program has three stages. First, a measurement study to decide whether the idea is worth building. On the iGC benchmark suite, at every refinement iteration we enumerate $k=8$ counterexamples, patch every one of them offline with LAMA, and record expansions, wall time, and how many other failing states each patch retires. The quantity of interest is the within-iteration spread of repair cost, together with how weakly cost correlates with tag count. If repair costs at an iteration are nearly uniform, the idea is dead and we stop.
Second, we implement the selection rule inside iGC, reusing its SAT verifier, pruning, and LAMA calls unchanged, so that only witness choice differs. The same rule is implemented inside SUPERB's CEGAR loop, which tests transfer across architectures.
Third, we analyze where cost-aware selection helps. We break results down by the width categories reported for CPCES (width at most 1: DISPOSE, BOMB, COINS, UTS; width above 1: BLOCKSWORLD, RAO'S KEYS, ONE-DISPOSE, LOOK-GRAB) and by MAWALLGRID. We also check whether gains concentrate where SUPERB-style multi-tag counterexamples provoke negative goal interactions. A cross-problem extension, which would keep the patch-cost memory across instances of one domain, is deferred until within-run gains are established.
Baselines
The naive reference is iGC exactly as published: one arbitrary SAT counterexample per iteration. It is also the strongest existing method on this suite, solving 989 of 1,179 instances across 50 domains (Fang et al.), with coins-21 ($10^{16}$ initial states) solved in 23.82 s using 84 witnesses. We rerun it on our hardware rather than copying numbers, so time limits, memory, and LAMA configuration are identical. Beating it means solving strictly more instances under the same limits and lowering median time on commonly solved instances. Plan length must not be worse than iGC's already-pruned plans.
The second baseline is SUPERB-style selection transplanted into iGC: among the same $k$ candidates, choose the one covering the most unaddressed tags. This is coverage-only selection, $\hat c \equiv$ constant. It is the strongest competitor on the precise question of whether cost matters beyond information. On its native CEGAR architecture we also run SUPERB itself, whose reported gain is 61 to 3 iterations on BOMB (Zhang et al.). Iterations there are cheap by construction, so our target is total time and solved count rather than iteration count.
Three further runs isolate ingredients:
- Random-of-$k$. Pays the same enumeration overhead but picks at random, isolating the value of selection from the value of enumeration.
- Cost-only. Sets $\hat g \equiv 1$.
- Cheap-proxy selection. Replaces the RCR estimator with failure depth in the plan or number of violated preconditions.
An offline oracle that patches all $k$ candidates and picks the best realized ratio bounds what any selection rule could gain.
All variants share the same $k$, time and memory limits, and SAT and LAMA settings. Tunable constants ($\lambda$, the dissimilarity penalty) are set on a held-out third of the domains and frozen for the rest.
Why not just…?
Why not just keep iGC's arbitrary counterexamples, since it already solves 989 instances? Fang et al. themselves identify LAMA as the bottleneck. Arbitrary witnesses offer no control over how much work each LAMA call receives. The measurement study answers this directly. If the oracle over $k$ candidates gains little over the arbitrary choice, iGC's approach is adequate, and we will report that.
Why not just maximize tag coverage as SUPERB does? This is the real threat, because SUPERB's iteration reductions are large. Our hypothesis, drawn from the goal-interaction evidence in DERSNLP+EBL, is that high-coverage counterexamples are disproportionately the expensive ones to patch. Coverage-only and cost-weighted selection run on identical candidate sets. If tag count and repair cost turn out to be uncorrelated or positively aligned, the cost term adds nothing, and the proposal reduces to SUPERB-inside-iGC.
Why not just use a cheap proxy such as failure depth instead of an RCR-style estimator? It may well work as well, and the design deliberately allows this. The core claim concerns the cost-weighted selection objective, not the particular estimator. The cheap-proxy ablation decides the question. If it matches RCR-style estimation, we adopt the proxy and drop the memory, which reduces overhead.
Why not just compile uncertainty away as bounded-width methods do? Palacios and Geffner's compilation avoids belief tracking only when width is bounded. Compilation-style planners reached only 46–58% coverage on the 777-instance suite, against 93% for Generate-and-Complete (Nguyen et al.). Our target is the regime where repair-based planners already win.
Proposed Experiments
The benchmarks are the 50-domain, 1,179-instance suite from Fang et al., the IPC domains used for CPCES and SUPERB, and MAWALLGRID. The metrics are:
- instances solved within the shared limit;
- total and per-component time, split into SAT enumeration, estimation, and LAMA;
- refinement iterations;
- LAMA expansions;
- final plan length relative to iGC.
We have not found on Lacuna the exact time limit used in Fang et al.'s evaluation. We will fix a limit, report it, and rerun iGC under it.
The first decisive check is the measurement study's within-iteration coefficient of variation in patch cost, and its rank correlation with tag count. High variance with weak correlation licenses the project; low variance ends it.
The second decisive check is the gap between cost-weighted and coverage-only selection, and between the RCR estimator and the cheap proxy, on held-out domains. It asks whether solved count and LAMA expansions move once enumeration overhead is charged.
The third examines coins-21 and similarly astronomical instances. The question is whether cost-aware selection reduces the number of witnesses (84 for iGC) or only their per-patch cost. Only the former would suggest the approach scales with uncertainty rather than simply trimming constant factors.
References
- On Computing Conformant Plans Using Classical Planners: A Generate-And-Complete Approach
- Improvements to the Generate-and-Complete Approach to Conformant Planning
- Computing Superior Counter-Examples for Conformant Planning
- Intelligent Belief State Sampling for Conformant Planning
- CHEF: A Model of Case-Based Planning
- Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures
- Case-Based Similarity Assessment: Estimating Adaptability from Experience
- A Case‐Addition Policy for Case‐Base Maintenance
- Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width