Reusing Search Trees for Iterative and Dynamic Planning

55 concepts44 papers1 proposal

When an artificial intelligence plans a route, schedules a factory, or proves a theorem, it explores a space of possibilities by building a search tree. Traditionally, this process operates under a "blank slate" paradigm: if the environment changes, the time budget increases, or a new task arrives, the system discards its current tree and restarts from scratch.

This blank-slate approach introduces massive computational redundancy. In a rolling schedule, starting from scratch for every new batch of tasks prevents the system from narrowing its search space effectively, as noted by Lise Getoor et al. in Effective Redundant Constraints for Online Scheduling. Similarly, Maxim Likhachev et al. demonstrate in ARA*: Anytime A* with Provable Bounds on Sub-Optimality that iterative refinement algorithms waste significant effort when they discard previous search results to start a new search under tighter constraints.

The core insight of incremental search tree reuse is to treat the search state not as a transient calculation, but as a persistent, evolving data structure. By maintaining and repairing this structure across iterations, algorithms can compute only the difference (or delta) required by new information, reducing node expansions by orders of magnitude.


The Intuition: Search as a Continuous Process

To understand why tree reuse works, consider a robot navigating an unknown environment. As it moves, it discovers an obstacle blocking its planned path. A naive planner throws away its entire search tree and recalculates a path from its new position to the goal.

However, the obstacle only invalidates a small fraction of the search space. The rest of the tree—representing paths through open terrain—remains perfectly valid. By preserving the valid subtrees and repairing only the affected nodes, the system treats environmental changes as a continuation of its previous search.

This philosophy dates back to early logic programming. Murray Shanahan proposed in An Incremental Theorem Prover that storing a search tree as a persistent data structure allows a reasoning system to map how specific conclusions are derived. When the knowledge base updates, the system modifies only the affected branches rather than recalculating the entire space.


Mechanics of Reuse: Subtrees, Frontiers, and Rewinding

Depending on the problem domain, researchers have developed different granularities of state reuse:

1. Root Shifting and Subtree Retention

In receding horizon frameworks like Monte Carlo Tree Search (MCTS) or Partially Observable Markov Decision Processes (POMDPs), an agent plans several steps ahead, executes a single action, receives an observation, and plans again.

Instead of discarding the tree after the action, the system shifts the root of the search tree to the chosen next state. As shown by John Lathrop et al. in Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search, retaining the entire subtree rooted at the selected state preserves critical information about both promising paths and low-reward regions, drastically reducing the number of simulations needed for subsequent steps. Stéphane Ross et al. utilize a similar root-shifting strategy in AEMS: An Anytime Online Search Algorithm for Approximate Policy Refinement in Large POMDPs to accumulate search depth over time without redundant computations.

2. Frontier Preservation and Compilation

When a search algorithm terminates or pauses, the "frontier" (the open list of unexpanded nodes) represents the exact boundary of its progress. Retaining this frontier allows a search to be paused and resumed seamlessly.

In Frontier Search and Plan Reconstruction in Oversubscription Planning, Daniel Muller demonstrates how compiling a search frontier into a set of entry points for a new planning task allows the algorithm to incorporate new heuristic data or landmarks without restarting from the initial state. Similarly, Jasmeet Kaur et al. show in Efficient Budgeted Graph Search that carrying the frontier and explored node lists forward across budget adjustments allows iterative algorithms to match the efficiency of single-pass searches.

3. Coarse-Grained Rewinding

Sometimes, tracking fine-grained dependencies between nodes introduces too much bookkeeping overhead. A powerful alternative is to "rewind" the search to a known valid historical state.

Xiaoxun Sun et al. introduce this in The Fringe-Saving A* Search Algorithm - A Feasibility Study. When a map change occurs, the algorithm restores a valid prefix of the previous search history and resumes exploration from that point, bypassing complex graph-dependency tracking.


Managing Changes: Inconsistency and Repairs

When the underlying problem changes—such as when a multi-agent collision boundary expands or a new object is discovered—the existing tree must be updated to maintain correctness.

A foundational approach to this is found in D*Lite by Sven Koenig et al., which identifies "locally inconsistent" states—nodes whose cost estimates do not align with their neighbors due to environmental changes. By placing only these inconsistent nodes onto the priority queue, the algorithm surgically repairs the affected portions of the tree.

This repair mechanism has been adapted across diverse domains:


How Traversal Topology Enables Incremental Updates

The efficiency of tree reuse is deeply tied to how the tree is traversed. In a standard best-first search, the algorithm frequently jumps between distant nodes on the frontier, making it expensive to maintain a single, globally synchronized state.

As detailed in Iterative-Deepening Conflict-Based Search, a depth-first traversal topology unlocks massive efficiency gains for incremental data structures. Because state changes only occur between adjacent parent and child nodes, the algorithm only needs to calculate the immediate difference between states during forward steps and backtracking. This avoids the overhead of rebuilding complex representations from scratch at every node.

A similar structural advantage is exploited by Anej Svete et al. in Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs. By treating failure transitions as a forest of trees and traversing them via depth-first search, they incrementally update a single data structure to share computations across states, eliminating redundant calculations.


Conclusion

Incremental search tree reuse shifts the paradigm of AI planning from episodic computation to continuous state refinement. Whether an algorithm is tightening an approximation bound, adapting to a moving obstacle, or scaling up a hyperparameter search budget, the underlying principle remains the same: information gained from prior exploration is an asset to be preserved and repaired, not a sunk cost to be discarded. By mastering the bookkeeping of frontiers, subtrees, and local inconsistencies, these systems achieve real-time responsiveness in complex, shifting worlds.

Key Foundational Work

Best-First Minimax Search: Othello Results (1994) — contributed 1 concept elements to this direction.
An Incremental Theorem Prover (1987) — 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_incremental_search_tree_reuse_6fabaeaf,
  title = {incremental search tree reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-search-tree-reuse/rdr_6fabaeafb61641628d01b959841238cf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_incremental_search_tree_reuse_6fabaeaf_v1,
  title = {incremental search tree reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-search-tree-reuse/rdr_6fabaeafb61641628d01b959841238cf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake