Map Induction: Compositional spatial submap learning for efficient
  exploration in novel environments
  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.
