Imagine you are a chef trying to bake a new type of cake, but you are missing a key ingredient: sugar. To find a workaround, you look through your old recipes for something "similar." A standard search engine might point you to a classic sponge cake because it shares 95% of the same ingredients. However, because a sponge cake relies fundamentally on the chemical structure of sugar to rise, adapting it without sugar is nearly impossible. Meanwhile, a flourless keto cake might look completely different on paper, but substituting its alternative sweetener is trivial.
This scenario illustrates the fundamental flaw of traditional Case-Based Reasoning (CBR) and Case-Based Planning (CBP) systems. Historically, these systems retrieved past experiences from memory by matching surface-level features. But as early AI planning systems like CHEF (Hammond) demonstrated, focusing purely on surface similarities or the number of shared goals frequently causes systems to overlook underlying constraints and goal interactions. This creates a similarity-adaptability misalignment: a system retrieves a past case that looks identical on the surface, only to find that adapting its solution to the new problem is computationally prohibitive or outright impossible.
To resolve this misalignment, a cohesive body of research emerged around a powerful idea: redefining similarity as a function of adaptation cost. Instead of asking how much two problems look alike, the system evaluates how much effort is required to transform a past solution into a new one.
From Feature Distance to Functional Neighborhoods
In traditional CBR, a case's relevance is determined by its geometric distance from a query within a static feature space. The adaptation-cost paradigm completely reimagines this geometry.
Under this framework, a case is no longer surrounded by an abstract bubble of feature similarity. Instead, it is defined by its functional neighborhood—the set of all target problems that can be successfully solved by retrieving and modifying that specific case within a strict limit on adaptation effort (Remembering to Add: Competence-preserving). By linking the conceptual reach of an experience directly to the practical effort required to reuse it, the system ensures that any retrieved case is fundamentally viable.
Traditional CBR:
[Query] <--- Feature Distance ---> [Stored Case] (May be unadaptable)
Adaptation-Driven CBR:
[Query] <--- Estimated Adaptation Effort ---> [Stored Case] (Guaranteed viable)
Learning the Cost of Adaptation Through Failure
How can a system know how difficult a case will be to adapt before it actually performs the adaptation? The first core mechanism relies on introspective reasoning and learning from execution failures.
When a system suffers a "mis-retrieval"—selecting a case that appears relevant but fails during adaptation—it analyzes its own mistake. For example, the ROBBIE system developed by Fox et al. uses introspective reasoning to explain why a retrieved plan was suboptimal. By diagnosing the root cause of the adaptation failure, the system automatically learns new indexing features, dynamically updating its memory to prevent similar mis-retrievals.
A parallel approach applies Explanation-Based Learning (EBL) to partial-order planning. As shown by Ihrig et al., when a retrieved plan cannot be extended to accommodate new goals, the system diagnoses these "replay failures." It generates "censors" that block bad retrievals in the future, refining its similarity judgments to account for hidden goal interactions that surface-level metrics miss (Ihrig et al.).
Predicting Adaptability from Past Edits
Beyond simply blocking bad cases, a system can proactively predict adaptation costs by treating the adaptation process itself as an experience to be remembered.
In the RCR (Re-application Costs and Relevance) framework introduced in Case-Based Similarity Assessment: Estimating Adaptability from Experience, the authors bypassed static feature matching entirely. Instead, the system records the historical computational effort expended during past solution modifications. When a new problem arrives, the system uses case-based reasoning on its own history of adaptations to estimate how much effort the current modification will require.
This creates a virtuous cycle of optimization, as detailed in Learning to Integrate Multiple Knowledge Sources for Case-Based Reasoning. As the system solves more problems, its store of adaptation knowledge grows. By continuously linking its similarity assessments to this evolving body of historical adaptation data, the retrieval mechanism naturally shifts toward prioritizing cases that are predicted to be the easiest to adapt.
Optimizing Memory via Adaptation Boundaries
Grounding similarity in adaptation costs does more than accelerate retrieval; it provides a mathematical foundation for maintaining case libraries.
A persistent challenge in CBR is case-base maintenance: if a library contains too many cases, retrieval becomes sluggish, but if it contains too few, the system cannot solve diverse problems. Traditional approaches attempted to prune bloated libraries by deleting cases that seemed redundant based on surface features.
By framing case coverage through the lens of low-cost adaptation neighborhoods, researchers inverted this problem. Zhu et al. proposed a greedy "case-addition" policy. Instead of filtering a massive library, they construct a compact case base from the ground up by selecting cases that maximize the total union of their functional neighborhoods. Because these neighborhoods represent true problem-solving competence rather than superficial feature overlap, this strategy provides a strict theoretical guarantee: the resulting case base will preserve at least 63% of the absolute optimal problem-solving competence achievable (Zhu).
Ultimately, this research direction demonstrates that memory retrieval in intelligent agents should not be a passive lookup of similar-looking files. By treating similarity as a dynamic reflection of adaptation effort, AI systems can bridge the gap between what they remember and what they can actually achieve.
Key Foundational Work
Using Introspective Reasoning to Refine Indexing (1995) — contributed 1 concept elements to this direction.
CHEF: A Model of Case-Based Planning (1986) — contributed 1 concept elements to this direction.