Reusing and Generalizing Plans from Past Experience

25 concepts27 papers1 proposal

When an automated agent faces a new task, its default strategy is often to act as if it has amnesia. Whether it is a classical planner navigating a grid, a robot arm calculating joint angles, or an online decision-making system tracking beliefs, traditional algorithms solve every new problem instance from scratch. This is known as first-principles search.

As Jaime G. Carbonell noted in early work on analogical problem solving, this approach ignores the human-like ability to adapt past experiences to novel situations, resulting in massive, redundant computational overhead (Experiential Learning in Analogical Problem Solving). This "from-scratch" bottleneck spans across domains: continuous motion planners re-evaluate the entire configuration space for every single query (Experience-Based Heuristic Search: Robust Motion Planning with Deep Q-Learning), online POMDP solvers frequently recalculate plans even when returning to previously encountered belief states (Online Planning Algorithms for POMDPs), and state-of-the-art heuristic planners solve every instance independently, failing to accumulate domain knowledge (Action Schema Networks: Generalised Policies With Deep Learning).

The core insight of experience-driven planning is that problems are rarely entirely novel. Instead of treating every task as an isolated island, we can treat planning history as a library of templates to be retrieved, repaired, or generalized.

Surgical Repair and Case-Based Adaptation

How do we reuse an old plan when the new problem is slightly different? The intuitive solution is plan modification. If you have a plan to build a three-story house, and a client asks for a four-story house, you don't redesign the foundation from scratch; you modify the top.

Subbarao Kambhampati formalized this intuition via the PRIAR system, introducing the concept of a "validation structure" (A Theory of Plan Modification). A validation structure maps out the internal dependencies of a plan—specifically, which actions satisfy which preconditions for subsequent actions. When a new goal or initial state is introduced, the system does not throw away the existing plan. Instead, it uses the validation structure to surgically identify and repair only the broken parts. This localized repair mechanism yields up to a 50x computational speedup compared to generative planning from scratch.

[Old Plan] ---> (Validation Structure: Tracks Dependencies)
                       |
                       v
[New Goal] ---> [Surgical Repair of Broken Parts Only] ---> [New Plan]

This paradigm forms the backbone of Case-Based Reasoning (CBR) in planning. For instance, the CHEF system developed by Kristian J. Hammond generates new recipes by retrieving past culinary experiences and modifying them, specifically learning from past failures to avoid repeating mistakes (CHEF: A Model of Case-Based Planning). Similarly, in complex medical diagnosis, Phyllis Koton demonstrated that the CASEY system could achieve a 100x speedup by retrieving a similar past patient's causal explanation and adapting it to fit new clinical evidence, bypassing massive state-space searches (Reasoning about Evidence in Causal Explanations).

Learning Continuous Biases and Constraints

In high-dimensional geometric spaces, like robotic manipulation or path planning, exact plan matching is impossible because no two environments are perfectly identical. The trick here is to use past experience to predict constraints or biases that narrow down where the planner should look, rather than predicting the exact path.

Beomjoon Kim et al. implemented this via the BOX (Blackbox Optimization with eXperience) algorithm (Learning to guide task and motion planning using score-space representation). Instead of full paths, the system uses a "score-space representation" to evaluate how a new problem matches a library of past solutions, using this relationship to predict solution constraints. This allows the robot to transfer experience across highly diverse environments, accelerating planning by orders of magnitude.

Modern deep learning allows these biases to be learned implicitly from data. Binghong Chen et al. proposed Neural Exploration-Exploitation Trees (NEXT), which combine attention-based neural networks with tree search (Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees). NEXT extracts structural regularities from previous successful navigation tasks to guide the search tree, preventing the redundant exploration that plagues traditional sampling-based planners like RRT*.

Other approaches focus on optimizing specific bottlenecks within the planning loop:

Compiling Experience into Generalized Policies

Instead of retrieving individual cases or biasing local searches, can we synthesize a single, overarching rule or policy that solves an entire family of problems regardless of scale? This is the domain of Generalized Planning.

Consider a logistics domain: the underlying logic of delivering packages remains identical whether you have 5 packages or 5,000. Yet traditional planners treat a change in object count as an entirely new problem. León Illanes et al. solved this by abstracting away the specific identities of objects (Generalized Planning via Abstraction: Arbitrary Numbers of Objects). Their LOOM system treats choices between identical objects as non-deterministic, generating compact, loopy programs that can instantly solve massive problem instances.

Neural architectures achieve similar domain-wide generalization. Sam Toyer et al. introduced Action Schema Networks (ASNets), which use a relational neural architecture to learn generalized policies that scale seamlessly across different problem sizes within the same domain (Action Schema Networks: Generalised Policies With Deep Learning).

[Instance 1: 5 Objects]   ---\
[Instance 2: 50 Objects]  ----> [Goal Regression / Abstraction] ----> [Single Generalized Policy]
[Instance 3: 500 Objects] ---/

More recently, Dillon Z. Chen et al. developed MOOSE, a framework that performs goal regression on optimal plans for individual goal atoms to synthesize first-order "Condition $\rightarrow$ Action" rules (Satisficing and Optimal Generalised Planning via Goal Regression). These rules act as a standalone policy or prune search spaces drastically, turning one-off solvers into generalized engines.

Expanding to Reasoning and Coordination

The imperative to avoid from-scratch planning extends beyond physical robots and classical blocks-worlds into modern language models and multi-agent coordination.

Large Language Models (LLMs) often suffer from high costs and repetitive generation when solving complex tasks. To mitigate this, Lakshmi Nair et al. introduced the Flow-of-Options (FoO) framework, which models task steps as a graph of options, allowing autonomous agents to retrieve and adapt existing successful reasoning frameworks rather than re-developing them entirely from scratch (Flow-of-Options: Diversified and Improved LLM Reasoning by Thinking Through Options). Similarly, in goal-oriented information seeking, Harshita Chopra et al. demonstrated that agents equipped with feedback-aware tree search can reuse successful questioning strategies across different sessions, slashing expensive LLM calls by 10x (Feedback-Aware MCTS for Goal-Oriented Information Seeking).

Even in multi-agent systems where coordination is dynamic, planning from scratch creates severe efficiency gaps. Nicholas R. Jennings et al. argued that instead of using first-principles reasoning to form agent groups and collaborative plans for every new task, systems must incorporate historical coordination patterns to bypass the immense computational cost of redundant group formation (Using Joint Responsibility to Coordinate Collaborative Problem Solving in Dynamic Environments).

Key Foundational Work

Experiential Learning in Analogical Problem Solving (1982) — contributed 1 concept elements to this direction.
A Computational Model of Analogical Problem Solving (1981) — contributed 1 concept elements to this direction.
A Computational Model of Analogical Problem Solving (1981) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_experience_agnostic_planning_f421c9b0,
  title = {experience-agnostic planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/experience-agnostic-planning/rdr_f421c9b084e8428dafc101baded84dbc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_experience_agnostic_planning_f421c9b0_v1,
  title = {experience-agnostic planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/experience-agnostic-planning/rdr_f421c9b084e8428dafc101baded84dbc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake