Case-based planners solve a new problem by retrieving an old solved problem (a "case") and editing its plan to fit. Their weak point is retrieval. A case can look nearly identical to the new problem and still be very hard to adapt, because a step the old plan relies on conflicts with something the new problem requires. Existing remedies learn this after the fact. One family explains each failed adaptation and stores a rule that blocks that case in the future. Another remembers how costly past edits were. Both need failures or edit histories before they help, and both pay the full price of a failed adaptation to learn anything.
Classical planning already has a cheap, polynomial-time tool for spotting facts that can never hold together. That tool is mutual-exclusion ("mutex") propagation: pairs of facts or actions are marked incompatible when no reachable state contains both. We propose to run mutex propagation on the new problem together with the commitments the retrieved plan imposes. The result is a score for how hard adaptation will be, available before any adaptation is attempted. When a commitment and a required goal are mutex at the fixpoint, the score becomes a sound rejection. The same analysis also yields a pruned set of actions and variables for the edit search. That pruning is exactly the restriction that the parameterized-complexity theory of plan reuse says is needed for adaptation to be tractable.
Core Claim
Adaptation cost depends on the adaptation operator, and for adaptation that extends an old plan without retracting it, cost depends on the plan's commitments, not just on its end state. Concretely, take a retrieved partial plan and its causal links. A causal link is a recorded promise that step $s$ produces fact $p$ for later step $s'$, so nothing in between may delete $p$. We compile this plan into a constrained planning task. Tracking fluents force the case's steps to occur in order and keep each protected fact true over its interval. On that task we build a planning graph and propagate pairwise mutexes, as in Fast Planning Through Planning Graph Analysis. The planning graph is a layered structure alternating reachable facts and applicable actions, built in polynomial time.
The analysis gives three outputs. The first is a graded retrieval score: the set-level and adjusted-sum estimates of Extracting Effective and Admissible State Space Heuristics from the Planning Graph, computed for the target goals together with the case's protected facts. The second is a sound a priori censor: if a protected fact and a target goal remain mutex at the graph's fixpoint, no extension of the case satisfies both. The case can then be rejected with no false rejections, relative to extend-only adaptation. The third is a pruned patch alphabet: the actions and variables that survive mutex pruning, which we then hand to the edit search.
The claim is that this commitment-aware score ranks cases by true adaptation cost markedly better than surface similarity or end-state relaxed distance, with zero adaptation experience. We also claim it recovers most of the benefit of failure-learned censors.
Relation to Prior Work
The closest work is Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures (DERSNLP+EBL). It replays stored derivations inside a partial-order planner. When replay fails, it explains the exhausted search tree to extract the conflicting goal subset as a censor. It reports about 32 seconds on 4-goal Logistics against 916 for plain case-based planning and 2967 from scratch. That paper motivates ours, since it shows hidden goal interactions dominate reuse cost. It also sets the target to beat. We differ in computing conflicts before replay, in polynomial time, rather than after an exhaustive failure.
Case-Based Similarity Assessment: Estimating Adaptability from Experience (RCR) estimates adaptability from stored adaptation cases. It reports 36 versus 65 primitive memory operations against semantic similarity. However, it falls back to semantic similarity when no relevant edits exist and uses semantic similarity as a prefilter. Our score needs no edit history, so it addresses exactly that cold start. The introspective indexing of Using Introspective Reasoning to Refine Indexing is likewise failure-driven.
On the mutex side, three papers supply our methods: Graphplan's propagation rules, the set-level and adjusted-sum heuristics of Nguyen and Kambhampati, and the lifted mutex groups and pruned grounding of Lifted Fact-Alternating Mutex Groups and Pruned Grounding of Classical Planning Problems. The lifted inference typically takes under a second and removes roughly twice as many operators as Fast Downward's baseline. All of these work only in generative, from-scratch search. They measure distance from a state to goals, never the cost of extending a committed plan.
Using Backwards Generated Goals for Heuristic Planning checks mutex "legality" of regressed goals. It is the nearest use of mutexes to validate reused structure, but the reuse happens within one search episode, not across a case library.
Parameterized Complexity Results for Plan Reuse constrains the design. Bounding patch length alone leaves plan modification W[2]-complete, and tractability requires bounding the action set or the affected variables and values. Our pruned alphabet is a concrete, instance-level way to shrink those parameters. That paper gives no algorithm for doing so.
Finally, Model-Lite Case-Based Planning deliberately avoids model-based invariants because it assumes a broken domain model. Our approach assumes a correct model and is not a substitute there.
Research Program
We will build a replay engine for grounded STRIPS tasks, implemented on top of Fast Downward's translator so that lifted mutex groups are available. The engine extends a retrieved case's partial plan by inserting steps and resolving threats, without retracting case steps. A second mode allows retraction, which we use to test the claim that commitments matter only for extend-only adaptation.
The compiler turns (target problem, case) into a constrained task. On that task we compute reachability mutexes ($h^2$-style) and lifted fact-alternating mutex groups. From these we read off three things: the fixpoint censor, the set-level and adjusted-sum scores over target goals plus protected facts, and the surviving actions and variables used to restrict patch search.
The analysis will characterize when the a priori censor misses conflicts that EBL catches. The expected source is higher-order (three-or-more-fact) interactions, which pairwise mutexes cannot see; the file lists these among the open problems of mutex methods. We will then test a hybrid in which EBL is invoked only for failures the mutex censor did not predict. If those residual failures are rare, the expensive explanation step becomes the exception.
A secondary study uses the cheap score to estimate the functional neighborhoods needed by the greedy case-addition policy of A Case‐Addition Policy for Case‐Base Maintenance. A functional neighborhood is the set of problems a case can be adapted to within a cost budget. That policy reports full competence with 58 cases in Towers of Hanoi, but it relies on expensive sample solving to estimate the neighborhoods.
Baselines
The naive reference is surface-similarity retrieval: count shared goals and initial facts, then replay the top case. This is the setting in which DERSNLP+EBL reports 916 seconds on 4-goal Logistics. Generating from scratch is the second reference point. We use Fast Downward with LM-Cut and with the mutex-strengthened potential heuristic of Strengthening Potential Heuristics with Mutexes and Disambiguations. That paper reports 1001 solved tasks across 65 IPC domains versus 911 for LM-Cut. Planners like these are what make case-based planning look unnecessary, so a reuse system must beat them on time-to-solution under tight budgets to matter.
The strongest reuse competitor is failure-driven censors in the DERSNLP+EBL style, reimplemented inside our replay engine so search code, grounding, and hardware are identical. On 4-goal Logistics the reported figure is about 32 seconds with a 100% success rate (Ihrig and Kambhampati). Censors will be learned online over the same problem stream our method sees. The comparison is therefore matched on experience, and it explicitly includes the early, cold part of the stream.
We will also run an RCR-style learned cost estimator, trained on adaptation records our engine logs. The only RCR number in the file is DIAL's 36 versus 65 operations. DIAL is not something we can rerun, and no reported RCR result was found on Lacuna for IPC domains.
The ablation that isolates our key ingredient replaces the commitment-aware task with the case's end state. It scores retrieval by $h^2$-mutex set-level and by $h_{FF}$ distance from that end state to the target goals, using the same planning graph code. A second ablation drops the pruned alphabet and keeps only the retrieval score, to separate the retrieval gain from the search-space gain.
We count it as beating the baselines if three things hold. On interaction-heavy domains, our method needs to match censor-based retrieval in steady state and clearly beat it over the first stretch of the stream, before censors accumulate. It also needs to beat the end-state ablation in rank correlation with realized adaptation cost.
Why not just…?
Why not just score cases by relaxed-plan distance from the case's end state? This is the real threat. If adaptation is allowed to retract steps freely, the end state may be nearly all that matters, and the commitment compilation adds nothing. The evidence against relaxed distance in general is that heuristics ignoring negative interactions fail badly on Grid and Mystery (Extracting Effective and Admissible State Space Heuristics from the Planning Graph). That argues for mutexes, but not yet for commitment awareness. The end-state ablation, run under both extend-only and retracting adaptation, settles the question. We predict a gap only in extend-only mode. If the gap does not appear, the contribution narrows to "mutex-aware end-state scoring plus alphabet pruning," and we will report it as such.
Why not just plan from scratch with a modern planner? On many IPC tasks this will win, and we expect to show that. The claim is restricted to stream settings with recurring structure and tight deadlines. There, from-scratch planning on 4-goal Logistics was reported at 2967 seconds against 32 for indexed reuse, and real-time domains such as WARGUS cannot afford generative search (On-Line Case-Based Plan Adaptation for Real-Time Strategy Games.). The comparison runs on matched budgets of 1 to 300 seconds, so the crossover point is measured rather than assumed.
Why not just learn from failures, as EBL censors or RCR do? Learning from failure works once failures have accumulated, and in steady state it may match or exceed us, because it captures higher-order conflicts that pairwise mutexes miss. Its costs are the cold start and the price of exhausting each failed search tree. The learning-curve experiment exposes both. The hybrid tests whether the two approaches are complementary rather than competing.
Why not just retrieve the top few cases and time-slice replay across them? A portfolio of top-k cases hedges against mis-retrieval cheaply. We include it with k from 1 to 5 at an equal total budget. If surface similarity rarely places an adaptable case in its top five, the portfolio fails, and the planner wastes time on doomed cases. Our censor can filter the portfolio as well, so the two approaches compose.
Proposed Experiments
Case libraries will be generated by solving random instances of Logistics, Grid, Mystery, Depots, Blocks, Towers of Hanoi, and Matching-BW, drawn from the IPC suites the file lists. Targets will be perturbations of stored cases: added, removed, or swapped goals and changed initial facts, with interaction strength controlled by how many perturbed goals touch facts the case protects.
The first decisive check measures retrieval quality. We compute Kendall rank correlation between each method's predicted cost and the realized replay node count over all case-target pairs, along with the fraction of doomed retrievals avoided. We will also verify empirically that the fixpoint censor never rejects a case that extend-only replay could adapt; any violation would indicate a compilation bug, since the rejection is sound by construction.
The second check is end-to-end. We measure time to solution and coverage on problem streams of increasing length, against both from-scratch planners and censor learning, with special attention to the first 50 problems. The third measures how much the pruned alphabet shrinks the action set and touched variables, and whether patch-search nodes fall accordingly. This tests whether the parameters de Haan identifies are actually small in practice.
The final check reports the residual failures the mutex censor misses, broken down by conflict arity. That shows directly where pairwise propagation stops being enough, and whether the hybrid closes the gap.
References
- Fast Planning Through Planning Graph Analysis
- Extracting Effective and Admissible State Space Heuristics from the Planning Graph
- Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures
- Case-Based Similarity Assessment: Estimating Adaptability from Experience
- Using Introspective Reasoning to Refine Indexing
- Lifted Fact-Alternating Mutex Groups and Pruned Grounding of Classical Planning Problems
- Using Backwards Generated Goals for Heuristic Planning
- Parameterized Complexity Results for Plan Reuse
- Model-Lite Case-Based Planning
- A Case‐Addition Policy for Case‐Base Maintenance
- Strengthening Potential Heuristics with Mutexes and Disambiguations
- On-Line Case-Based Plan Adaptation for Real-Time Strategy Games.