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

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