# Sparse Graphical Memory for Robust Planning

arXiv: https://arxiv.org/abs/2003.06417 · HTML: https://mlsanity.com/paper/2003.06417/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2020.

## Built on by (most cited first, 30 of 31)

- [No RL, No Simulation: Learning to Navigate without Navigating](https://mlsanity.com/paper/2110.09470/) (2021)
- [Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2110.13625/) (2021)
- [Hierarchical Few-Shot Imitation with Skill Transition Models](https://mlsanity.com/paper/2107.08981/) (2021)
- [LEAGUE: Guided Skill Learning and Abstraction for Long-Horizon Manipulation](https://mlsanity.com/paper/2210.12631/) (2022)
- [Differentiable Spatial Planning using Transformers](https://mlsanity.com/paper/2112.01010/) (2021)
- [Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2111.09858/) (2021)
- [Topological Experience Replay](https://mlsanity.com/paper/2203.15845/) (2022)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Offline Imitation Learning Through Graph Search and Retrieval](https://mlsanity.com/paper/2407.15403/) (2024)
- [Learning Robotic Navigation from Experience: Principles, Methods, and Recent Results](https://mlsanity.com/paper/2212.06759/) (2022)
- [Imitating Graph-Based Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/2303.11166/) (2023)
- [Goal-Space Planning with Subgoal Models](https://mlsanity.com/paper/2206.02902/) (2022)
- [Value Memory Graph: A Graph-Structured World Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.04384/) (2022)
- [Test-Time Graph Search for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2510.07257/) (2025)
- [DisTop: Discovering a Topological representation to learn diverse and rewarding skills](https://mlsanity.com/paper/2106.03853/) (2021)
- [Lifelong Topological Visual Navigation](https://mlsanity.com/paper/2110.08488/) (2021)
- [One-4-All: Neural Potential Fields for Embodied Navigation](https://mlsanity.com/paper/2303.04011/) (2023)
- [E-MAPP: Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance](https://mlsanity.com/paper/2212.02064/) (2022)
- [Neural Constraint Satisfaction: Hierarchical Abstraction for Combinatorial Generalization in Object Rearrangement](https://mlsanity.com/paper/2303.11373/) (2023)
- [PALMER: Perception-Action Loop with Memory for Long-Horizon Planning](https://mlsanity.com/paper/2212.04581/) (2022)
- [Enabling Visual Action Planning for Object Manipulation through Latent Space Roadmap](https://mlsanity.com/paper/2103.02554/) (2021)
- [Graph Convolutional Memory using Topological Priors](https://mlsanity.com/paper/2106.14117/) (2021)
- [Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks](https://mlsanity.com/paper/2107.06405/) (2021)
- [L-SA: Learning Under-Explored Targets in Multi-Target Reinforcement Learning](https://mlsanity.com/paper/2305.13741/) (2023)
- [Guided Cooperation in Hierarchical Reinforcement Learning via Model-based Rollout](https://mlsanity.com/paper/2309.13508/) (2023)
- [Balancing Exploration and Exploitation in Hierarchical Reinforcement Learning via Latent Landmark Graphs](https://mlsanity.com/paper/2307.12063/) (2023)
- [The Imperfect Learner: Incorporating Developmental Trajectories in Memory-based Student Simulation](https://mlsanity.com/paper/2511.05903/) (2025)
- [A New View on Planning in Online Reinforcement Learning](https://mlsanity.com/paper/2406.01562/) (2024)
- [What to Do Next? Memorizing skills from Egocentric Instructional Video](https://mlsanity.com/paper/2507.02997/) (2025)
- [Metro-WM: Long-Horizon Latent Planning with Realisable Sub-Goals](https://mlsanity.com/paper/2609.31868/) (2026)

## Abstract (arXiv)

To operate effectively in the real world, agents should be able to act from high-dimensional raw sensory input such as images and achieve diverse goals across long time-horizons. Current deep reinforcement and imitation learning methods can learn directly from high-dimensional inputs but do not scale well to long-horizon tasks. In contrast, classical graphical methods like A* search are able to solve long-horizon tasks, but assume that the state space is abstracted away from raw sensory input. Recent works have attempted to combine the strengths of deep learning and classical planning; however, dominant methods in this domain are still quite brittle and scale poorly with the size of the environment. We introduce Sparse Graphical Memory (SGM), a new data structure that stores states and feasible transitions in a sparse memory. SGM aggregates states according to a novel two-way consistency objective, adapting classic state aggregation criteria to goal-conditioned RL: two states are redundant when they are interchangeable both as goals and as starting states. Theoretically, we prove that merging nodes according to two-way consistency leads to an increase in shortest path lengths that scales only linearly with the merging threshold. Experimentally, we show that SGM significantly outperforms current state of the art methods on long horizon, sparse-reward visual navigation tasks. Project video and code are available at https://mishalaskin.github.io/sgm/