# Map Induction: Compositional spatial submap learning for efficient exploration in novel environments

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 45 references that are in the map.
- First posted on arXiv 23 Oct 2021.

## Builds on (most cited first, 3 of 3)

- [People infer recursive visual concepts from just a few examples](https://mlsanity.com/paper/1904.08034/) (2019)
- [Learning abstract structure for drawing by efficient motor program induction](https://mlsanity.com/paper/2008.03519/) (2020)
- [Vector-based Pedestrian Navigation in Cities](https://mlsanity.com/paper/2103.07104/) (2021)

## Built on by (most cited first, 9 of 9)

- [PoE-World: Compositional World Modeling with Products of Programmatic Experts](https://mlsanity.com/paper/2505.10819/) (2025)
- [Graph schemas as abstractions for transfer learning, inference, and planning](https://mlsanity.com/paper/2302.07350/) (2023)
- [Toward Human-AI Alignment in Large-Scale Multi-Player Games](https://mlsanity.com/paper/2402.03575/) (2024)
- [Cognitive maps are generative programs](https://mlsanity.com/paper/2504.20628/) (2025)
- [Path-dependent program induction under resource constraints explains human sequence learning](https://mlsanity.com/paper/2606.20623/) (2026)
- [Fast exploration and learning of latent graphs with aliased observations](https://mlsanity.com/paper/2303.07397/) (2023)
- [When Remembering and Planning are Worth it: Navigating under Change](https://mlsanity.com/paper/2602.15274/) (2026)
- [Prospective Compression in Human Abstraction Learning](https://mlsanity.com/paper/2605.09985/) (2026)
- [Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2608.02993/) (2026)

## Abstract (arXiv)

Humans are expert explorers. Understanding the computational cognitive mechanisms that support this efficiency can advance the study of the human mind and enable more efficient exploration algorithms. We hypothesize that humans explore new environments efficiently by inferring the structure of unobserved spaces using spatial information collected from previously explored spaces. This cognitive process can be modeled computationally using program induction in a Hierarchical Bayesian framework that explicitly reasons about uncertainty with strong spatial priors. Using a new behavioral Map Induction Task, we demonstrate that this computational framework explains human exploration behavior better than non-inductive models and outperforms state-of-the-art planning algorithms when applied to a realistic spatial navigation domain.