Memory Bounded Planning and Representation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2495 papers655 conceptsfrozen 2026-10-04

In the quest for autonomous agents that can navigate complex environments, researchers have long faced a physical limit: the "Memory Wall." While computational speed has increased dramatically, the memory required to store optimal strategies, state-space graphs, and high-quality heuristics often grows exponentially with the complexity of the task.

This research direction focuses on bridging the gap between theoretical optimality and the physical constraints of hardware. By developing techniques to compress state representations, abstract away irrelevant details, and bound the memory used during search, researchers aim to build "bounded-optimal" systems that can solve massive problems without exhausting available RAM.

The Tension Between Thinking and Reflexes

A fundamental trade-off in AI is whether an agent should compute its next move on the fly or rely on a pre-computed "reflex" table. As Eric Horvitz, John S. Breese, and David Heckerman noted in The Compilation of Decision Models, reactive systems that attempt to store every possible input-output combination suffer from exponential memory growth. This scaling issue creates a physical limit on the environments a simple lookup-table approach can handle.

To move beyond these limits, systems must become more selective about what they remember. This has led to the development of "lightweight" methods, such as the Statistical Model Checking approach proposed by Axel Legay and Sean Sedwards in Lightweight Verification of Markov Decision Processes with Rewards, which samples schedulers in constant memory rather than building massive numerical tables.

Abstraction and Partial Grounding

One of the most effective ways to save memory is to avoid representing the entire problem at its highest resolution. Traditional planning often "grounds" every possible action and variable before starting a search, which can crash a system before it even begins to "think."

To combat this, Daniel Gnad and Álvaro Torralba introduced partial grounding, using machine learning to predict and instantiate only the most relevant parts of a task. Similarly, Jendrik Seipp and Malte Helmert developed Counterexample-Guided Cartesian Abstraction Refinement, which iteratively refines the state space. Instead of incorporating entire variables at once—which causes exponential memory spikes—they use fine-grained abstractions to keep the model size manageable.

In the realm of Task and Motion Planning (TAMP), Nicholas Roy and William Vega-Brown demonstrated in Admissible Abstractions for Near-optimal Task and Motion Planning that using "angelic semantics" to bound plan costs allows for searching in massive state spaces (up to $10^{13}$ states) by focusing on memory capacity as the primary constraint rather than just CPU time.

Compact Symbolic Representations

When an explicit list of states is too large to store, researchers turn to symbolic representations that group similar states together. Ugur Kuter and Dana S. Nau showed in Controlled Search over Compact State Representations how Binary Decision Diagrams (BDDs) can represent sets of states compactly, allowing planners to perform operations on entire groups of states simultaneously.

This symbolic approach is also vital in complex "leader-follower" scenarios. In Faster Stackelberg Planning via Symbolic Search and Information Sharing, Álvaro Torralba and colleagues used symbolic representations to solve grueling planning tasks that would otherwise exceed standard memory limits.

Memory-Efficient Heuristics and Caching

Heuristics are the "compass" of a search algorithm, but high-quality compasses often require massive lookup tables. Rong Zhou and Eric A. Hansen addressed this in Space-Efficient Memory-Based Heuristics, exploring ways to use less memory without sacrificing search guidance.

A breakthrough in this area is the True Distance Heuristic (TDH) by Nathan R. Sturtevant and Ariel Felner. Instead of storing every possible distance, TDHs store distances between select "pivot" states, using less than 1% of the memory of a full table while providing highly accurate estimates.

When even these compressed tables are too large, systems can move from exhaustive memoization to bounded caching. As shown in Using Caching to Solve Larger Probabilistic Planning Problems, replacing full memory storage with "Smart" difficulty-based heuristics or Least Recently Used (LRU) caches allows solvers to explore much deeper horizons without crashing.

Bounded Rationality as a Strategy

Finally, some researchers argue that memory limits aren't just a hurdle to overcome, but a lens through which to understand efficient intelligence. In Bounded Rationality in Las Vegas, Joseph Halpern and Xinming Liu modeled decision-makers as Probabilistic Finite Automata (PFAs). They found that simple, memory-light strategies—like focusing only on the most recent outcomes—can perform near-optimally. This suggests that for agents with finite memory, "biases" toward simplicity are actually mathematically sound adaptations to the physical reality of the Memory Wall.

Papers in this version

Showing 60 of 495 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 517 papers
  2. Version 1 · 2026-10-04 · 495 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_memory_constrained_search_e0dab7a9,
  title = {memory-constrained search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-search/rdr_e0dab7a9de9f4e51b81dab96ea3f95ef},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_memory_bounded_planning_and_representati_e0dab7a9_v1,
  title = {Memory Bounded Planning and Representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-bounded-planning-and-representation/rdr_e0dab7a9de9f4e51b81dab96ea3f95ef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}