Retrieving Plans by the Size of the Patch They Need

When a planner faces a new problem, it can either search from scratch or retrieve an old solved problem and repair its plan. Repair is often far cheaper, but only when the right old plan is retrieved. Retrieval systems usually judge "right" by surface resemblance, such as shared goals or matching objects. The planning-theory literature gives a sharp reason why this fails: how cheap a repair is depends on which state variables and actions the repair must touch, not on how many steps it adds. This note proposes a retrieval index built directly on that quantity. For every stored plan and new problem, it computes the set of variables and actions the patch must involve. It ranks all stored plans by the size of the search space that set implies. It then confines the repair search to that scope, and falls back to from-scratch planning when even the best patch looks too expensive.

The payoff matters for any planner that currently discards its past work. That includes the classical planners whose "amnesia" motivates Action Schema Networks: Generalised Policies With Deep Learning. The file's evidence shows that reuse can beat first-principles search by large margins. On 4-goal Logistics problems, from-scratch generative planning took about 2,967 seconds, reuse with goal-overlap retrieval 916 seconds, and failure-censored reuse about 32 seconds (Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures). The same numbers show that the gains depend on retrieval quality. The question is whether retrieval can be made adaptation-aware before any failure occurs, and cheaply enough to scan the whole library.

Core Claim

Case-based planning retrieves a stored plan and adapts it to a new problem. Parameterized Complexity Results for Plan Reuse studies the core adaptation problem, which it calls CASEMOD: find a "glue" sequence of actions that turns an old plan into a valid one for a new problem. It proves two things. Bounding the number of added steps leaves the problem W[2]-complete, meaning intractable in the worst case. The problem becomes fixed-parameter tractable (solvable efficiently when certain quantities are small) when one bounds either the set of modification actions or the number and domain sizes of the variables involved.

Our claim is that these parameters can be estimated cheaply from state-annotated cases, before any search. Once estimated, they serve two roles. They give a retrieval score that predicts adaptation effort better than surface similarity or step counts. They also define a restricted repair search that is itself cheaper. Concretely, a stored case $c$ carries its plan and the states along it. For a query $q$, let $S(c,q)$ be the patch scope. It contains the variables whose values disagree between $q$ and the case's annotated start or goal states, closed backward through the actions that can change them up to a small depth $k$. Let $A(c,q)$ be the actions over that scope. Any glue search confined to the scope explores at most the product of the scope variables' domain sizes, so we score cases by

$$ h(c,q) \;=\; \sum_{v \in S(c,q)} \log |D_v| \;+\; \lambda \log |A(c,q)|, $$

where $D_v$ is the value set of variable $v$. The weight $\lambda$ is fit on past adaptations. Its role is to capture branching, which the domain-product term misses. The logarithmic form follows directly from the bound: the first term is the log-size of the projected state space the restricted search can visit.

What is new relative to the file is threefold. The index uses tractability parameters rather than step counts or semantic overlap. It is cheap enough to score every case, which removes the coarse first-stage filter. And the same scope that ranks a case also restricts its repair.

Relation to Prior Work

Three adaptation-aware retrieval methods motivate the gap and differ from the proposal in distinct ways.

Case-Based Similarity Assessment: Estimating Adaptability from Experience (the RCR model) estimates adaptation cost from stored records of past adaptation effort. In the DIAL disaster domain it cut effort from 65 to 36 primitive memory operations. However, it first filters candidates by semantic similarity, so an easy-to-adapt but surface-dissimilar case never reaches the cost estimator. Our index scores the full library with bit-level variable comparisons, so no semantic filter is needed.

Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures (DERSNLP+EBL) learns "censors." These are explanations of past replay failures, derived by explanation-based learning, that block bad cases in future retrievals. The mechanism is reactive and binary. Ours is predictive and graded, and it could absorb censors as a hard filter.

Using Introspective Reasoning to Refine Indexing similarly refines indices only after failure.

Two further works constrain the design. The parameterized complexity paper supplies the method's theoretical basis. It also shows that reuse without state annotations is W[P]-complete. That result tells us cases must store intermediate states, a storage cost we accept. The CHEF system (CHEF: A Model of Case-Based Planning) first documented that surface matching misses goal interactions. Our scope closure is an attempt to detect such interactions syntactically.

On the experience-driven planning side, A Validation-Structure-Based Theory of Plan Modification and Reuse (PRIAR) repairs plans locally by tracking which actions support which preconditions. We reuse the idea of local repair, but PRIAR does not address which case to retrieve.

Generalized planning offers a competing way to reuse experience. Satisficing and Optimal Generalised Planning via Goal Regression (MOOSE) lifts rules from solved instances and reports near-100% coverage across its domains. It explicitly fails when goals are entangled. Case reuse with scope-aware retrieval should be most useful in exactly that regime, and our evaluation targets it.

A Case‐Addition Policy for Case‐Base Maintenance gives a greedy case-addition policy with a 63%-of-optimal coverage guarantee over "functional neighborhoods." These neighborhoods are the sets of problems a case can solve within an adaptation budget. We reuse the policy, redefining a neighborhood as the problems with $h(c,q)$ below a threshold.

Research Program

We would build the system on a finite-domain (SAS+-style) representation, where each state is an assignment to multi-valued variables, so that domain sizes and a causal graph are well defined. Each case stores its initial state, goal, plan, and per-step states.

Retrieval compares the query's initial state and goals against every case's annotated states using precomputed bit vectors. From the mismatched variables it computes the backward scope closure with depth $k$ from 1 to 3, then evaluates $h$. Adaptation runs a glue search, planning into and out of a chosen splice point of the old plan, with the search projected onto $S(c,q)$. Candidate patches are validated on the full state. If validation fails, the scope is widened by one closure step, up to a budget.

A reuse-or-replan rule compares the best $h$ against a threshold. The threshold is calibrated on held-out queries so that reuse is attempted only when its predicted effort is below the from-scratch planner's median effort on similar-size problems.

The fitting step is kept minimal: one scalar $\lambda$, the depth $k$, and the threshold. This keeps the method transparent and makes clear that any gain comes from the choice of features, not from learning capacity.

A second phase applies the Yang and Zhu greedy addition policy with $h$-defined neighborhoods. It tests whether compact case bases retain competence in Towers of Hanoi, where that paper reached full competence with 58 cases versus 200 random ones, and in Logistics.

Baselines

The naive reference point is experience-agnostic planning. We use a modern heuristic planner run from scratch on every query, Fast Downward with the LAMA configuration, under the same per-query time and memory limits and on the same machine. Retrieval and adaptation time are charged to our system. No reported result was found on Lacuna for Fast Downward on these query sets, so this baseline is measured fresh. Beating it means higher coverage within the time limit, or lower median wall-clock time at equal coverage, on the misaligned-query sets described below.

The retrieval baselines all feed the identical glue-search repair engine, with unrestricted scope, the same library, and the same budget, so that only the ranking differs.

The first is goal-overlap retrieval, the standard case-based planning criterion. It took 916 seconds versus 32 for failure-censored reuse on 4-goal Logistics in Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures. Those figures come from an old partial-order planner, so we treat them as motivation, not as numbers to reproduce.

The second is a reimplementation of RCR-style estimation: semantic prefiltering to the top 10% of cases, then ranking by the recorded past adaptation effort of similar adaptations. It is the strongest existing adaptation-aware retriever. Its published figure is 36 versus 65 primitive memory operations in DIAL (Case-Based Similarity Assessment: Estimating Adaptability from Experience). Beating it means lower mean and tail adaptation effort, and specifically recovering cases that its prefilter discards.

The third is a censor filter in the style of DERSNLP+EBL, layered on goal overlap and given the same training queries to learn from.

As the strongest competitor for experience reuse overall, we run MOOSE (Satisficing and Optimal Generalised Planning via Goal Regression) trained on the same solved instances. It reports near-100% coverage in its tested domains, so we expect it to win on goal-independent domains. Our system beats it only if it achieves higher coverage on entangled domains. We also run OAKPlan, the case-based planner that Model-Lite Case-Based Planning compares against.

Two ablations isolate the key ingredient. The first uses $h$ for ranking but repairs with unrestricted scope, testing whether scope restriction matters beyond ranking. The second ranks by the number of mismatched facts, a Hamming-style step proxy, while keeping restricted repair. This tests whether domain sizes and action sets, the specific quantities the complexity result names, add anything over counting differences.

Why not just…?

Why not just plan from scratch with a modern planner? Modern planners are far faster than the SNLP planner behind the 2,967-second figure, and on easy IPC instances they may well dominate reuse. We take this as a real threat. The proposal only claims an advantage on larger instances whose solutions are near neighbors of library cases, and the reuse-or-replan rule exists to avoid losing elsewhere. The comparison is run per problem-size bucket. If from-scratch planning matches our system at every size, the claim fails.

Why not just count how many facts differ, and retrieve the closest case? This is the cheapest adaptation-aware metric, and it may correlate with effort in practice even though the complexity theory says step-like counts guarantee nothing. The Hamming ablation settles it directly. We expect the gap to appear on constructed queries where one differing fact has a large scope. An example is a package goal in a new city that forces plane, truck, and airport variables into the patch, while many differing facts elsewhere have trivial scopes. If Hamming ranking matches $h$ on those queries, the complexity-grounded features are not earning their place and the method should be simplified.

Why not just train a neural regressor on problem pairs to predict adaptation cost? A graph network over the two problems could in principle learn the same signal. However, it must be evaluated pairwise against every case, which reintroduces the prefilter dilemma that RCR suffers from. Graph networks in planning also struggle with long dependency chains, a limitation Action Schema Networks: Generalised Policies With Deep Learning reports for its fixed receptive field. We include a small graph-network regressor over the difference graph, given the same training adaptations, as an extra ranking baseline. If it clearly wins, the scope features remain useful as its input and for restricting repair.

Why not just use generalized planning instead of a case library? MOOSE's rules generalize beyond any single case and should win wherever goals decompose. The proposal therefore concentrates its claim on the entangled domains MOOSE's authors flag as failures, and reports results on decomposable domains so that the boundary is visible.

Proposed Experiments

Libraries are built from solved instances in the IPC domains the file names: Logistics, Blocksworld, Driverlog, and Depots from the case-based planning papers. We add entangled domains from the MOOSE evaluation where goal regression fails, and Towers of Hanoi for maintenance.

Queries come in two sets. The natural set consists of fresh random instances. The misalignment set consists of perturbations of library problems, generated in controlled pairs. In each pair the surface-most-similar case needs a wide-scope patch while a less similar case needs a narrow one. Pairs are verified by running exhaustive adaptation against every case to find the oracle cheapest one.

The measurements are as follows. We report rank correlation between each score and actual adaptation effort, counted as node expansions in the glue search. We report retrieval regret, defined as effort of the retrieved case divided by effort of the oracle case. We report end-to-end coverage, time including retrieval, and plan length. Finally, we count cases the RCR prefilter discards that turn out to be oracle-best.

The first decisive check is whether $h$ beats both Hamming distance and RCR-style retrieval on regret in the misalignment set while not losing on the natural set. The second is whether restricting repair to the scope reduces expansions beyond the ranking gain; this is the first ablation. The third is whether the full system raises coverage over MOOSE on entangled domains and over Fast Downward on the largest size bucket. The fourth, for the maintenance phase, is whether greedy addition with $h$-neighborhoods matches the reported full competence in Towers of Hanoi with a similarly small case base, and transfers that compactness to Logistics.

Any of these failing would be informative. A win for Hamming distance would mean the complexity parameters matter in theory but not in these benchmarks. A win for from-scratch planning would mean retrieval quality is no longer the bottleneck for modern planners.