A planner that keeps a library of past solutions faces a basic problem: which stored plan should it modify to solve a new problem? Most case-based systems answer by surface resemblance, such as shared goals or overlapping start conditions. Resemblance is a poor guide to how much work the modification will take. The better answer is to rank stored plans by their adaptation cost, meaning the effort needed to turn the old plan into a valid plan for the new task. Existing estimators of that cost either learn it from past adaptation traces, which adds lookup overhead and gives no guarantees, or compute it by actually running a planner, which is expensive. Both still depend on a cheap surface filter up front, and that filter can silently discard the plan that would have been easiest to adapt.
This note proposes computing a provable lower bound on adaptation cost from precomputed lookup tables of abstract distances. These are pattern databases: tables of exact solution costs in a simplified version of the problem, which never overestimate true costs. With such a bound, a planner can search its whole library and skip only cases that provably cannot beat the current best. It can also certify which problems each case can handle within a fixed adaptation budget. The core claim is that admissible bounds turn two currently heuristic steps of case-based planning into exact, pruned searches over the library: choosing which case to retrieve, and choosing which cases to keep. This removes both the false negatives of surface filtering and the planner-in-the-loop cost of library maintenance.
Core Claim
Fix a concrete adaptation model, which we call plan splicing. A stored case is a plan $\pi = (s_0, \dots, s_n)$, a sequence of states. A target task asks to go from start $s'$ to goal $g'$. Adapting $\pi$ means three steps: plan a bridge from $s'$ into some state $s_i$ on the stored plan, follow the plan to some later state $s_j$, then plan a bridge from $s_j$ to $g'$. The adaptation cost is the total length of the two bridges. Let $d(a,b)$ be the true shortest distance from $a$ to $b$, and let $h(a,b) \le d(a,b)$ be any admissible state-to-state estimate. Then the cost of adapting $\pi$ satisfies
$$c(\pi \to (s', g')) \;\ge\; \min_{i} h(s', s_i) \;+\; \min_{j} h(s_j, g'),$$
where the inequality comes from dropping the ordering constraint $i \le j$.
The state-to-state estimate comes from differential heuristics. These store distances between every state and a few "pivot" states $p$ and combine them through the triangle inequality. The Compressed Differential Heuristic and Anchor Search both build such pivot tables, the latter from pattern databases. Both rely on the symmetric form $|d(a,p) - d(b,p)|$, and Anchor Search names directed spaces as open. Adaptation is inherently directed: bridging into a plan is not the reverse of bridging out of it. We therefore store both distance-to-pivot and distance-from-pivot tables and use the one-sided bound
$$h(a,b) = \max_p \max\big(d(a,p) - d(b,p),\; d(p,b) - d(p,a)\big),$$
which stays admissible whether or not $d(a,b) = d(b,a)$. Here $d$ is either the true distance or an abstract pattern-database distance, which is itself a lower bound. The one-sided bound is elementary. The contribution is not the bound itself but its use as the scoring function for case libraries.
Relation to Prior Work
The motivating evidence comes from adaptation-cost similarity. Case-Based Similarity Assessment: Estimating Adaptability from Experience predicts adaptation effort by reasoning over stored adaptation traces. It cut actual adaptation effort to 36 primitive memory operations, against 65 for semantic similarity. However, it still pre-filters candidates by semantic distance, and its estimates carry no guarantee. Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures learns "censors" from failed replays: rules explaining why a case failed, used to block it in future. Its replay with learning took about 32 seconds on 4-goal Logistics, against 916 seconds for plain case-based planning and 2967 seconds from scratch. Censors are binary and indexed by goal subsets; they do not produce a numerical distance.
The maintenance side comes from A Case‐Addition Policy for Case‐Base Maintenance. It defines a case's functional neighborhood as the set of problems it can solve within adaptation budget $L$, and proves that greedy addition achieves at least $1-1/e$ of optimal coverage. On Towers of Hanoi it reached full competence with 58 cases, where 200 random cases did not. That paper computed neighborhoods with an unguided forward-chaining planner. Our bounds replace most of those planner calls with table lookups. Adaptation-Guided Case Base Maintenance reaches the same theme from regression, showing that preserving adaptation knowledge matters more than preserving solutions. We do not reuse its method.
The technique comes from the search literature. Pattern databases (Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases, Compressing Pattern Databases) supply cheap admissible lookups, and differential heuristics supply the state-to-state form. These works use the bounds to guide search within a single task, never to rank or curate a library of stored plans.
Two papers constrain the design. Compliant Conditions for Polynomial Time Approximation of Operator Counts notes that its fast closed-form estimate is inadmissible, so it cannot serve where certified pruning is the point. Conversely, New Admissible Heuristics for Domain-Independent Planning shows that abstractions which keep mutual-exclusion constraints are much stronger than single-fact relaxations. That is why we build pivot tables from constrained pattern abstractions rather than from single-fact potentials.
Research Program
We will build three components.
The first is a retrieval engine. It computes the lower bound above for every case in the library, using precomputed per-case minima where possible. It visits cases in order of increasing bound. It actually adapts a case by running the two bridging searches with A*, guided by the same tables, which also yields an upper bound. It stops once the next case's lower bound exceeds the best realized cost. This is branch-and-bound over the library, and it returns the provably cheapest case under the splicing model.
The second is a maintenance procedure that runs the greedy Yang–Zhu policy with interval neighborhoods. Problems whose lower bound already exceeds $L$ are certified as outside a case's neighborhood without any planning. Problems whose cheap upper bound, obtained from quick heuristic-guided bridges, falls within $L$ are certified as inside. Only the band where the lower bound is at most $L$ but the upper bound exceeds $L$ is sent to an exact planner.
The third is a directedness study. In domains with irreversible actions, we measure how often the symmetric bound overestimates true adaptation cost and therefore wrongly prunes, compared with the one-sided bound.
Pivot placement is the main design choice. We will compare placing pivots far apart, which is standard for differential heuristics, with placing them at states that many stored plans pass through. Our hypothesis is that the second option tightens the per-case minima over $s_i$ and $s_j$.
Baselines
The naive reference point is from-scratch optimal search with modern pattern databases, ignoring the library entirely. We will run it with the complementary pattern-database planner of On Creating Complementary Pattern Databases, which reports 1,055 of 1,667 Fast Downward IPC tasks solved, against 857 for iPDB. It gets the same per-task time and memory as our full pipeline. Its offline table construction is charged to it, just as ours is charged to us. Beating it means lower total time per solved task across a stream of related tasks drawn from a fixed domain distribution, at matched memory. We do not expect to beat it on isolated tasks.
The strongest case-based competitor is learned adaptation-cost estimation in the style of RCR. Its reported result is 36 versus 65 primitive operations in DIAL. That number comes from a different domain and is not directly comparable to ours. We will reimplement it on our domains: it stores realized bridge costs and scales them by role-filler distance, and it receives the same library and the same coarse semantic pre-filter it was designed with. The censor-based replay of Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures will be run on Logistics as a second case-based reference. Beating these systems means lower retrieval regret at equal or lower retrieval time. Retrieval regret is the realized adaptation cost of the chosen case minus the best adaptation cost in the library. Our method is guaranteed zero regret under the splicing model, so the real comparison is whether it reaches that at competitive time.
The surface baseline is goal-overlap similarity, measured by the share of goals in common, with start-state difference used to break ties.
For maintenance, the reference is the Yang–Zhu greedy policy with unguided planner neighborhoods: 58 cases for full competence on Towers of Hanoi. We should match their case count, since our certified intervals change only cost and not the greedy choices. A win means a large reduction in planner calls and wall time for building neighborhoods.
Two ablations isolate the key ingredient. The first replaces the admissible bound with an equally cheap inadmissible estimate: the closed-form operator-count approximation, or an abstract distance scaled upward. This tests whether the guarantee, rather than the ranking quality alone, drives the result. The second uses the symmetric differential bound in directed domains.
Why not just…?
Why not just solve every task from scratch with a strong pattern-database planner? This is a real threat in domains where from-scratch search is fast. The Logistics gap reported for derivational replay, 32 versus 2967 seconds, predates modern heuristics and may have narrowed substantially. Our experiments report, per domain, the break-even point at which library reuse beats from-scratch search in amortized time. If that point never arrives on IPC domains, we will say so and confine the claim to repeated-query regimes such as grid maps and large Towers of Hanoi instances.
Why not just retrieve by goal overlap and adapt the top few? If adaptation is cheap and libraries are small, adapting the top-$k$ surface matches may find the best case anyway. We test this directly. We sweep library size from tens to tens of thousands of cases, and we plot, against $k$, the probability that the true best case lies outside the top-$k$ goal-overlap matches. The method earns its keep only if that miss rate stays significant at sizes where adapting all candidates is too slow.
Why not just use the heuristic between case endpoints, $h(s', s_0) + h(s_n, g')$? This ignores entry and exit points in the middle of the plan, so it is not a valid lower bound under splicing. It can therefore prune the true best case. We include it as a baseline and report its false-pruning rate alongside its speed. If that rate turns out to be negligible in practice, the per-case minima over intermediate states are unnecessary, and we will drop them.
Proposed Experiments
We use the benchmarks in the file that support both case libraries and pattern-database lookups. The first is 4-peg Towers of Hanoi from 12 to 24 disks, following the settings of the Yang–Zhu and Anchor Search evaluations. The second is MovingAI grid maps, where The Compressed Differential Heuristic reports results at memory budgets of $1|V|$ to $8|V|$, with $|V|$ the number of states. The third is IPC Logistics, with libraries generated from solved training tasks. The fourth is Sokoban as the directed domain, which needs abstract rather than exact pivot tables. Planning infrastructure will build on IBM/kstar for PDDL parsing. Its multi-plan generation also lets us seed libraries with diverse plans.
Metrics are retrieval regret, retrieval time against library size, the false-negative rate of each filter, amortized time per task over a task stream, and, for maintenance, cases needed for full competence along with planner calls spent building neighborhoods.
The decisive checks are three. First, our filter must show zero false negatives under splicing while the semantic pre-filter and the endpoint heuristic do not. Second, retrieval time must grow sublinearly in library size because of bound-based pruning; linear growth would mean the bounds are too loose to help. Third, in Sokoban the symmetric bound must produce measurable false pruning that the one-sided bound eliminates. Without that, the directed construction adds nothing. If the bounds prune well but regret against goal-overlap top-$k$ retrieval is negligible at every library size, the proposal fails on its own terms.
References
- The Compressed Differential Heuristic
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
- Case-Based Similarity Assessment: Estimating Adaptability from Experience
- Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures
- A Case‐Addition Policy for Case‐Base Maintenance
- Adaptation-Guided Case Base Maintenance
- Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases
- Compressing Pattern Databases
- Compliant Conditions for Polynomial Time Approximation of Operator Counts
- New Admissible Heuristics for Domain-Independent Planning
- On Creating Complementary Pattern Databases