Map Induction: Compositional spatial submap learning for efficient exploration in novel environments
Authors: Sugandha Sharma
Aidan Curtis
Marta Kryven
Joshua B. Tenenbaum
Ila R Fiete
Venue: ICLR 2022 Poster (2022)
Keywords: Cognitive Science
Bayesian Framework
Program Induction
Spatial Navigation
Planning
Map Learning

Abstract: Humans are expert explorers and foragers. Understanding the computational cognitive mechanisms that support this capability can advance the study of the human mind and enable more efficient exploration algorithms. We hypothesize that humans explore new environments by inferring the structure of unobserved spaces through re-use of spatial information collected from previously explored spaces. Taking inspiration from the neuroscience of repeating map fragments and ideas about program induction, we present a novel ``Map Induction'' framework, which involves the generation of novel map proposals for unseen environments based on compositions of already-seen spaces in a Hierarchical Bayesian framework. The model thus explicitly reasons about unseen spaces through a distribution of strong spatial priors. We introduce a new behavioral Map Induction Task (MIT) that involves foraging for rewards to compare human performance with state-of-the-art existing models and Map Induction. We show that Map Induction better predicts human behavior than the non-inductive baselines. We also show that Map Induction, when used to augment state-of-the-art approximate planning algorithms, improves their performance.


Published as a conference paper at ICLR 2022
MAP INDUCTION: COMPOSITIONAL SPATIAL SUBMAP LEARNING FOR EFFICIENT EXPLORATION IN NOVEL ENVIRONMENTS
Sugandha Sharma, Aidan Curtis, Marta Kryven, Josh Tenenbaum, Ila R. Fiete Massachusetts Institute of Technology (susharma, curtisa, pertiss,,mkyve... jot, fiete) edu
ABSTRACT
Humans are expert explorers and foragers. Understanding the computational cog- nitive mechanisms that support this capability can advance the study of the human mind and enable more efficient exploration algorithms. We hypothesize that hu- explore new environments by inferring the structure of unobserved spaces through re-use of spatial information collected from previously explored spaces. Taking inspiration from the neuroseience of repeating map fragments and ideas about program induction, we present a novel "Map Induction" framework, which involves the generation of novel map proposals for unseen environments based on compositions of already-seen spaces in Hierarchical Bayesian framework. The model thus explicitly reasons about unseen spaces through distribution of strong spatial priors. We introduce new behavioral Map Induction Task (MIT) that in- volves foraging for rewards to compare human performance with state-of-the-an existing models and Map Induction. We show that Map Induction better predicts human behavior than the non-inductive baselines. We also show that Map In- duction, when used to augment state-of-the-arr approximate planning algorithms, improves their performance.
INTRODUCTION
Humans efficiently spatial reasoning explore and forage in new environments. We easily find our way around new buildings and infer promising foraging locations. For instance, after some experience of foraging on cluster of hills and finding berries the south-facing slopes, could anticipate that nearby hills may have a similar distribution of berries (see Figure I
Which neurally-informed computational cognitive mechanisms make this possible, and could they be leveraged for better exploration in AI? We empirically study human exploration in novel spaces, and propose formal computational model, which call Map Induction, that predicts human be- haviour by leveraging Bayesian inference about the structure of unobserved space. We also show that map induction can improve the performance of a Partially Observable Markov Decision Pro- cess (POMDP) planner during foraging. We begin by reviewing the literature on human spatial cognition involved exploration and parallel developments of exploration algorithms, followed by introducing computational modeling and experimental results.
Distributed non-metric representations. Human exploration relies on constructing approximate spatial representations [Wang& & Brockmole| 2003 Warren et al. 2017 Wiener & Mallot 2003) that support near-optimal planning in daily life (Bongiorno et al., (2021) while sacrificing global metric accuracy (Vuong et al. 20019 Newcombe et al. 1999 Zhu & Levinson 2015). These representations
are acquired by combining redundant observations of local landmarks. such as views from multiple
perspectives (Gillner & Mallot 1998 Foo et al. 2005). The use of distributed spatial representations

---

Published as a conference paper at ICLR 2022
???
map induction
using the inferred map to plan
Map induction: We propose how humans might infer the structure of unobserved spaces based priors constructed from observations of other environments or different parts of the same spacee. Map induction can minimize exploration cost by filling in incomplete or missing observa- tions from experience.
Figure 1:
for cost-effective navigation also has a long history in AL. Examples include computational theory of wayfinding based on multiple locally unique but globally similar landmarks (Prescott 1996),
which prioritized error recovery over accuracy. The Spatial Semantic Hierarchy model (Kuipers
& Leviti 1988) used distributed spatial graphs as maps for navigation (Kuipers) 2000: Kuipers
al. 2004). Simultancous Localization and Mapping (SLAM) algorithms based segmenting the
explored space circumvent scale limitations by dividing the world into manageable locally metric
submaps with topological relationships between submaps (Bosse et al. [003 Fairfield et al. 2010).
By contrast, recent recurrent neural network models of navigation have focused more closely on the
metric structure of explored spaces and global map formation (Burak & Fiete 2009), showing how
networks trained on path integration can take shortcuts (Banino et al. 20188)
Hierarchical organization. Humans minimize planning costs by representing spaces hierarchically based on visible spatial boundaries (Kosslyn et al.] 1974), geography (Stevens & Coupe 1978).
or otherwise interpreting spaces as composed of sub-regions (Hirtle & Jonides 1985). Hicrarchical
spatial organisation is evident in a tendency to plan paths between regions, before planning sub- paths within each region (Bailenson al., 2000 Newcombe al. 1999 Wiener Mallot 2003
Wang & Brockmole 2003 [Balaguer et al., 2016). and in increased reaction times when switching between hierarchy levels during plan execution (Balaguer et al. 2016; Kryven al., 202T). Hi-
erarchical state-spaces in non-spatial planning domains include drawing (Tian et al., 2020) inverse inference (Shu et al. 2020), and reasoning about topology (Tomov et 2020).
Hierarchical representations in Al and specifically in Reinforcement Learning can be expressed as options- - a hierarchical grouping of actions frequently performed together (Sutton et al., 1999). Assuming novel Markov Decision Processes (MDP) is sampled from family of similar MDPs, its rewards can be learned as derived from a parent distribution shared by the MDP family (Wilson et al. 2012). (Sinhh et al. (2012) proposed computational framework for learning efficient state- space representations by recognizing which sequences of actions lead to identical observations - for example, grouping together paths that lead to observing the same landmark. A principle of grouping game-board states based on rotation and reflection symmetries has been used to optimize state-space representations in the game of Go (Silver al. 2017).
Shared reference frames. From young children to hunter-gatherers, humans spontaneously orga- nize sensory precepts into patterns (Pitl al. 202 }), and use them to generalize between tasks Tian et al.) 2020 Lake & Piantadosi] 2020; Schulz et al. 2018). Generalization and transfer learning neural scene representations (Dilks al. 201 l), and
in spatial domains include mirror-invariin
reusing of reference frames across similar environments (Marchette et al.) 2014). Shared reference frames may occur in other mammals as well, as suggested by evidence rodents reusing grid-cell maps between similar parts of an environments (Derdikman et al.) 2009 Carpenter et al. 20155). A recent computational framework for clustering space by fragmenting neural representations at loca- tions of high surprisal during online exploration shows how such submaps might form (Klukas et al.) 2021]. However, these studies have not considered how submaps may be recombined and reused to efficiently forage in novel spaces.
Map Induction. We propose a Map Induction hypothesis - that humans optimize exploration of new spaces by representing maps composed of reusable reference frames which can inferred
2

---

Published as a conference paper at ICLR 2022
Deut
08.00
Dismonds:
0
02:15
Diamonds:
Figure 2: An example of MIT task. A. A 2-dimensional grid discretization showing the map used for modeling exploration trajectory. The black cells indicate walls, and the red cells indicate reward locations. B. The 3-dimensional world, in which subjects search for rewards (shown blue diamonds on a red platform), seen from an overhead perspective in the Unity Design system. C. First-person views of the task, seen by subjects different times during the experiment.
by program induction represent unseen space composed of previously encountered regions. Program induction generally refers to inferring a program that likely produced given sequence of observations (Stuhlmuller al.) 2010 Lake et al. 2015). For example, given sequence of numbers, the inferred program may be an arithmetic progression; given a natural texture the program may be reaction-diffusion equation (Camazine et al. (2020). Although Bayesian models of concept-learning by program induction have been developed for many domains (Stuhlmuller et al., 2010 Lake et al., 2015 Tian al., 2020), its use understand spatial structures and environments unexplored. In this work map induction refers to inferring program(s) that could generate the current environment, given past observations. Given such program, an agent can anticipate the structure of an unseen environment and use this estimated structure to optimize exploration.
In this work we adopt scientific and an engineering goal: (1) to empirically study how humans learn spatial representations, and (2) describe computational model that formalizes human-like map induction that can potentially optimize exploration AL. We show that Partially Observed Markov Decision Process (POMDP) planner augmented with Hicrarchical Bayesian map induc- tion predicts human exploration better than a naive, non-inductive, POMDP (Experiment 1). We also show that human exploration relies probabilistic distributions over likely map-generating programs, as opposed to using only the most likely map (Experiment 2). the next section, we introduce the Map Induction Task. We then give a detailed description of computational models in Section 3 In Section 4 we describe two human experiments, and compare behavioral metrics with our models' predictions.
2 MAP INDUCTION TASK
The Map Induction Task (MIT) is designed to present subjects with novel environments and provide a context for learning novel spatial representations. We are especially interested environments in be predicted from incomplete observations. For example,
which certain parts of the environment upon entering a unit an apartment building human will likely categorize it as a new region, but after exploring several units, should be able to anticipate the remaining floor-plan,

---

Published as a conference paper at ICLR 2022
consider several possibilities consistent with prior observations such as, that the right and the left wing of the building could mirror each other. In nature, predictable structures occur in patterns of hills and valleys, branching riverbeds, and plants favoring certain features of the environment (see Figure D. which in theory can be probabilistic, rather than exactly structured repetitions.
The subjects' task is to forage for rewards in novel partially observable 3-dimensional environments, which contain multiple rewards. To keep each experiment duration under 45 minutes, the current experiments each environment consisted of repeated unity structural blocks repeated throughout the environment (see Figure B). However, in theory the environment structure could be a proba- bilistic mixture of different parts.
The subjects have no advance knowledge of the specific environment structure and are instructed to collect all diamonds (see Cig Subjects use a keyboard and mouse (or trackpad) to navigate, which are standard navigation controls in first-person games. The distribution of rewards is initially unknown the subjects, but is predictable from the layout of the environment for example, the rewards may be placed in the same part of unit each time the unit occurs. While the MIT task can completed without map induction, or even without an explicit map representation (e.g. by following wall) such naive strategy would take longer than selectively exploring only the parts likely to contain diamonds. Each trial continues either until all diamonds are collected or until timeout is reached, whichever comes first.
Map Induction
Region Extractor
Map Generator
Map Inference
Planner
Observation Reward
Action
Environment
D
E
H.. HEE..
Planner
Uniform Model
Maximum A Posteriori Model
Distributional Model
Figure 3: Model architecture. A. Four steps required solve the MIT task and the corresponding computational modules in our framework. B. Extracting the candidate regions (submaps) from the known map, and generating possible map completions by composing these regions and their simple transformations (c.g., mirror reflections) as defined in the generative grammar of the Map Generator. C. Uniform Model assumes uniform distribution for the unobserved part of the map. Maximum A Posteriori Model uses the most likely map completion for planning. E. Distributional Model uses the entire distribution of map completions for planning.
COMPUTATIONAL MODELS
We now formalize the map induction hypothesis to quantitatively and computationally test its pre- dictions. Optimizing performance in the MIT task requires the following computational steps: (1) inferring that the euvironment is composed of repeating units (2) inferring the most likely struc- ture(s) of the environment (3) inferring the distribution of rewards within the environment, and (4)

---

Published as a conference paper at ICLR 2022
planning the shortest route that collects all rewards. Here (1) and (2) refer to map induction, and (3) may involve further program induction over the distribution of rewards (e.g. the rewards could be placed in the top left corner of every unit, in every odd unit, etc.). Because of uncertainty in the environment, this computational pipeline is executed in the context of a replanning loop. Finally, step (4) involves solving a Partially Observed Markov Decision Process (POMDP) that
dis- tribution of hypothetical environments to plan. While it is possible to do (4) without performing the first three steps, this would entail assuming uninformed prior that any unobserved cell could equally likely be wall, an empty space, or a reward which would result in exploring exhaustively.
Formally. we can model this process by a Bayesian generative framework consisting of four com- putational modules (see Figure 3/A) corresponding to the four steps described above. Each module can be independent of the others and can express different modeling assumptions. the remainder of this section, we discuss the function of each module in detail and define three specific combi- nations of module implementations, to express three distinct computational hypotheses formalizing the principle of map induction in different ways.
3.1 MAP INDUCTION THROUGH OBSERVED SPATIAL STRUCTURES
Steps (1) and (2) entail approximate inference of a posterior distribution pl (D) over possible maps. Here we formalize the computations that estimate this distribution (see Figure 3A).
Region Extraction: The region extractor extracts candidate regions (or submaps) Mp from known parts of the map (see Figure 3 for simple example). The second stage of the hierarchy in Figure 3 shows examples regions extracted from the observed map, shown above. Note that the term hypothetical building block of the environment considered by the model, and is dif- ferent from the term unit used in the previous section to describe repeating elements in environment design. In theory multiple regions can represent unit, or a region may comprise several units.
region refers
Map Generation: To develop a space of possible map completions, we use a probabilistic gener- ative grammar that combines region primitives into set of completed maps. If the current map has dimensions Sas Sy. and dy dy are the dimensions of the extracted regions, then the generative grammar for that map is described shown in Table T
The third level of the hierarchy in Figure
Production Rule
Probability
Mplde, dy) Mp(de,dy) Mp(de, dgy
FLIPH(M, dy))
(.PV(M,(d,) dy))
ROTATE M, (dy, dr))
Mp(dz, + dzzs dyy) Mpldei, dy dyz) M
UCAT((M, dny 3,MMpp Mp(dee doy)) VCAT(M, dr Mp (dxz ,
Mp(82,8y)
Table 1: Probabilistic context-free grammar used to generate a distribution of map hypotheses.
BB shows examples of map completions generated this way. The probabilities assigned to the rules in the generative grammar encode priors on coverage and consistency of the generated maps.
Map Inference: We use this probabilistic generative grammar along with the following likelihood over generated maps to form the posterior p)M
3
7
I(M; D) x
X
X
8z X
where 7/5² Sy is the fraction of the map not predicted by given map completion and 8/sz Sy the fraction of mismatched reward locations relative to the history of observations. At high level, this likelihood function encodes two simple assumptions: (1) map completions that maximally
5

---

Published as a conference paper at ICLR 2022
descriptive of unseen portions of the environment are more likely; (2) map hypotheses that min- imally contradictory with previous observations are more likely. The posterior distribution p(M) D) is computed using the above likelihood function, and an initial prior on the map hypotheses p(M) derived from the probabilities assigned to the production rules in the generative grammar listed in Table 1 1 For simplicity, here we assume uniform prior over the map hypotheses generated by the Map Generator since the space of possible hypotheses is small.
p(M = 1(M; -
(ttp:))))M))=(((((((((( P(DIM)p(M)
3.1.1 PLANNER
We model the exploration problem as a Partially Observable Markov Decision Process (POMDP). In a POMDP, the state not directly observable by the agent and can only be inferred through sequences of observations in the environment. A POMDP can be described as a tuple the of possible states the world, A is a finite set of actions, T: P:SxA- (S) is a stochastic transition function which maps a state action pair to a distribution over possible next states, R: S x A - a reward function that maps state action pairs to scalar reward, Ω is set of observations that an agent can experience in the world, O : S A + [T)) is an observation function which maps state and action pair to distribution of possible observations after taking the action, and y is discount factor such that 0 < Y < 1. An optimal agent in this formulation acts to maximize the expected discounted reward from the environment.
(S. A. R, 0, ? where
π (s)) arg max a
E k R(s.a)))
k
For our task, the state space is defined as = H x [0. 7 x S₂ where H is the set of possible map hypotheses from p(M) D). [0. 1||l| is the probability associated with each hypothesis, and S₂ is a 3 3-tuple (az, ay: a,,) with dimensions (sg, Sy. 4) indicating the index into the grid world state where the agent is positioned and the current direction the agent is facing. The action space is discrete with size 3 for bidirectional rotation and forward movement. We use reward function R defined by an indicator function over the state space 1 (S [4g, ay = reward). The transition function T 28, a) stochastic function that maps the given action and the previous state to new state. There is no closed-form expression for T,, but it can be expressed using a generative probabilistic sampler that takes s, samples a grid from the hypothesis distribution in s, deterministically simulates action a in the sampled grid, and returns a new position, orientation of the agent and an updated hypothesis distribution consistent with the new observations. The observation space [2ss o; D) defined by surjective line-of-sight (LOS) observation function O that maps from state and action to a deterministic observation. This function casts rays within a 90-degree field of view in the direction of the agent's orientation. Lastly, we define finding an exact solution is intractable due to the size of the problem (Kaelbling et al., 19988, we search through belief space using an approximate online Partially Observable Monte Carlo Planner (POMCP) (Silver & Veness 2010).
0.90 for all of our experiments. Since
3.2 COMPUTATIONAL HYPOTHESES
We compare human performance to three hypotheses (variants of POMCP) to evaluate whether and how human exploration implements the computational steps described in Figure 3A:
1. Uniform Model (Uniform-POMCH) The Uniform model doesn't use map induction, i.e., it doesn't learn any inductive priors about spatial structures during exploration outlined in steps (1)-(3). Instead, assumes uniform distribution over possible settings for each grid cell (reward, empty, etc.) and uses that for planning as shown in Figure BC.
2. Maximum A Posteriori Model (MAP-POMCP): The MAP model uses the most likely map from the distribution of induced maps (MM)) to plan (see Figure 3D).
'Given the relatively small environments, we are able to compute the posterior exactly. However, larger and more complex environments (where enumerating all possible map completions is not feasible) would likely require approximate Bayesian inference methods such as Markov Chain Monte Carlo.

---

Published as a conference paper at ICLR 2022
3. Full Distributional Model (D-POMPC): The Distributional model uses the entire set of induced maps in the distribution p(M D) to plan (see Figure 3
Both second and third hypotheses are consistent with the previous studies discussed in Section D They both use the map induction framework based on compositionality of space. i.c., combining local regions to form the global map instead learning global metric representation. On the other hand, the first hypothesis is inconsistent with this literature, since makes prior assumptions about the organization of space (neither hierarchical organization, nor the use of shared reference frames). Furthermore, it assumes uniform distribution the unseen map space which is akin to learning global map.
4 BEHAVIORAL EXPERIMENTS
map induction, implemented by the experiments. Experiment tests whether humans perform and D-POMCP models, in contrast naive exploration implemented by Uniform-POMCP. The results show that humans indeed rely on map induction and rule the use of the Uniform model. Experiment 2 tests whether human exploration best explained by MAP-POMCP or D-POMCP models, and shows that humans plan according distribution of hypothetical maps, explicitly gathering information disambiguate those hy- potheses. The number of subjects recruited for both experiments was determined through prior pilot experiments, our goal was to recruit sufficient number of responses differentiate between the Uniform-POMen MAP-POMCP and D-POMCP.
Below we describe two human behavioral
4.1 EXPERIMENT 1: USING MAP INDUCTION TO OPTIMIZE EXPLORATION
End
Start
B
Mod
Lowt
Env1
Env5
Env3
C
ooserved
1:5
MAR POWCP
D-POWCP
POMIC
Env3
Erv5
Env6
MAP-POMPP Unioom-POOWP
D-POWOP
1.5 15 12- 125-1 4.5 46--6
2-25 12-
2-12 15-12 43-02-
Haman
UnIfom-POMCP
Figure 4: Experiment results. A. Exploration trajectories of a representative subject. Visitation heatmaps of three example environments aggregated across subjects and pairs of reflected environ- ments. The visited area was computed in a 2D grid projection, using circular radius of five grid cells around the agent. C. Fractions of environments observed by the models and humans. Error bars show 95% confidence intervals. D. Log-likelihon
that the model takes the same actions as the human (details in Appendix section A.3) Each marker is subject-environmest pair, with each color showing a single environment: Env Env66 (blue-yellow). Error bars show standard error along each axis.
Method: The experiment was conducted web browser. using 3D virtual environments built-in Unity WebGL. Each environment was composed of corridor connecting five instances of a specific unit. The rewards (diamonds) were placed at identical locations within each unit. An example environment is shown in Figure 2 Each subject performed four practice trials, followed by an instruction quiz and 12 test trials in order randomized between subjects. Subjects who failed the instruction quiz repeated the instructions and practice until they answered the quiz correctly. The

---

Published as a conference paper at ICLR 2022
timer for the trial and the number of diamonds collected were shown the upper right comner of the screen (see Figure (C). See Supplementary Materials for full experimental instructions and screenshots.
Stimuli: The 12 test trials comprised six pairs of unique environments and their reflections. The reflected environments increase the number of trials and control for possible left or right biases.
Subjects: We recruited 30 subjects via Amazon Mechanical Turk. Subjects were paid for 45 minutes of work and received a monetary bonus for each collected diamond.
Results: Out of the 30 subjects, 4 subjects explored exhaustively, 2 did not complete the experiment, and 24 subjects correctly inferred reward placement, indicative of map induction. Most subjects haustively explored the first two units in a new environment, followed by partial exploration through the remainder of the trial. Throughout the experiment, the extent to which non-rewarding areas were visited decreased, indicating that people were increasingly confident about the repeating layout.
Figure 4A shows examples of exploration trajectories of one subject. Subjects generally used iden- tical trajectories to search the reflected pairs of environments, and so we aggregated results for each of the six pairs. Figure 4B illustrates the extent which three example environments were vis- ited, aggregated across subjects, and across reflected pairs of environments. See the Appendix for complete plot of all exploration trajectories and heatmaps. Figure H shows the fractions of each en- vironment observed by humans and models. The areas observed by MAP-POMCP and D-POMCP were similar to humans', while the area observed by Uniform-POMCE was significantly larger. Figure 4D shows the fit of the three models to human behavior, indicating that the MAP-POMCP and D- D-POMCP models, which implement map induction, explain human behavior better than the Pefform-POMCP model, which makes no predictions about map structure.
4.2 EXPERIMENT 2: DISTRIBUTIONAL SUB-MAP REPRESENTATIONS
Experiment 2 differentiates between MAP-POMCP and D-POMCP models using color cues to in- dicate the location of rewards within each unit. This was done by including a 'cue room' within each unit a small room containing information about the location of the reward. The environments were designed so that A planner guided by the
would take longer exploration path compared to D-POMCP. model ignores the rooms and heads toward the part of a unit most likely to contain a diamond based on previous experience. In contrast, the D-POMCP model visits the cue room gather information about the location of the diamonds.
Method: Experiment 2 followed a procedure similar to Experiment 1, with a different set of environ- ments. Each subject performed five practice trials, followed by an instruction quiz. 12 test trials in order randomized between subjects, and a test of skills using navigation controls. The controls skill test ensured that subjects could navigate in WebUnity without undue difficulty since Experiment used larger environments. Subjects who failed the controls skill test were paid but excluded from the analysis. The instructions were modified to prompt subjects to consider colors as cues to the placement of the reward - see the Appendix for full details.
Stimuli: The 12 test environments comprised six unique environments and their reflections. The color cues were randomized within each environment so that the reflected pairs of environments were colored in different ways and contained rewards different locations.
Subjects: We recruited 51 subjects via Amazon Mechanical Turk. Each was paid for 45 minutes of work and received a monetary bonus for each collected diamond.
Results: Out of 51 subjects, 35 completed the controls skill test. Of the 35 subjects, all but nine were able to successfully use color cues, as predicted by the D-POMCP model, indicating that the majority took into account the entire distribution of possible maps in contrast to just the most likely map. Example exploration trajectories of one subject and visitation heatmaps are shown in Figure A and B. See the Appendix for more results. Comparing the fractions of environments observed by humans and models indicates that only the D-POMCP model was comparable to humans (see Figure 5C). D-POMCP model was also best explaining human behavioral data, as shown in Figure 5D.
8

---

Published as a conference paper at ICLR 2022
A
Start
stted
Env1
Env6
Env2
D
%6 Env olverveeeed
Po
405
Ra
MARPONEP
D-POWO
-15
8d
Envl
Env2
Emx3
Emd
Erv5
33 -1-25 -3 -1
-15 3.35 2--5 -144
MAP-POMCP
D-POMEP
Uniform POMEP
Human
Figure 5: Experiment 2 results. A. Exploration trajectories of representative subject. Visitation heatmaps of three example environments aggregated across subjects. The visited area was computed in 2D grid projection, using a circular radius five grid cells around agent. C. Fractions of environments observed by the models and humans. Error bars show 95% confidence intervals. D. Log- Log-likelihood that the model takes the same actions as the human (details in Appendix section
A.3
Each marker is eebeemttnnvirommentt pair, with each color showing single environment:
Env -Env6 (blue-yellow). Error bars show standard error along each axis.
5
DISCUSSION
In this work we proposed novel Map Induction hypothesis that humans use program induction to infer maps of novel environments from partial observations and the inferred map distribution to optimize exploration for rewards. We formalize this hypothesis computationally. by combining Bayesian map induction model and approximate belief-space planner. We present the results of two behavioral experiments that support the map induction hypothesis by demonstrating that our computational model predicts human exploration, and show that the performance of a Partially Observable Monte Carlo Planner can be improved by adding map induction.
While explored map induction in simple environments, it is likely apply more widely hu- mans not only forage selectively but also tend to consider only plausible theories. This may indicate that humans anticipate the structure of abstract search spaces by noticing repetitions and symmetries to simplify hard computing problems in various domains. Using map induction for exploration may be unique to humans the evidence of rodents reusing grid-cell maps similar parts of environ- ments suggests that grid-cell remapping may be neural signature of map induction (Derdikman ctt al. 2009; Carpenter et al. 2015). Hippocampal reuse of place-cell maps in composite environ- ments PPaz- Villagáán al. 2004), which invariant rotation and scaling (Muller & Kubie, 1987 suggests that animals use landmark cues to guide map induction as well.
In future work intend study map induction in larger, more naturalistic environments, where more comprehensive generative models may be needed for map induction in order to optimally induce the generative programs used to generate these environments. Map induction may also have potential applications for fast and generalizable map learning SLAM and in model-based RI. tasks.
ACKNOWLEDGMENTS
We would like to thank Kevin Ellis for helpful discussions, and Kevin M. Zayas for assistance with the development of web-hosting our tasks. This work is supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF-1231216. We acknowledge support from the K. Lisa Yang Integrative Computational Neuroscience Center (ICoN) and the Friends Mc- Govern Fellowship the MIT McGovem Institute of Brain Research to Sugandha Sharma; from

---

Published as a conference paper at ICLR 2022
the NSF Graduate Research Fellowship Program to Aidan Curtis; from the ONR, the Simons Foun- dation, and HHMI through the Faculty Scholars Foundation to lla Ficte.
REPRODUCIBILITY STATEMENT
The source code for the models and the behavioral datasets used for this project are made available the following GitHub repository, along with instructions how them.
https://gg http::///httuutt thub. com/ S 72 MMaue//aap- Inductioon
The compiled Unity WebGL build packages for both experiments presented in this paper are also provided at the above repository. The builds can be hosted using any web hosting service (e.g.. simmer.io) in order re-run the experiments and reproduce experimental results. The Unity source code used to generate these builds is available on request.
To ensure reprodueibility, the behavioral experiments are also explained in detail in the Appendix.
Our institutional IRB approved all experiments.
REFERENCES
Jeremy N Bailenson, Michael S Shum, and David H Uttal. The initial segment strategy: A heuristic for route selection. Memory & Cognition, 28(2):306-318 2000.
Jan Balaguer, Hugo Spiers, Demis Hassabis, and Christopher Summerfield. Neural mechanisms of hierarchical planning in virtual subway network. Neuron, 90(4))893-903, 2016.
Andrea Banino, Caswell Barry, Benigno Uria, Charles Blundell, Timothy Lillicrap. Piotr Mirowski,
Alexander Pritzel, Martin Chadwick, Thomas Degris, Joseph Modayil, al. Vector-basee navigation using grid-like representations in artificial agents. Nature, 557(7705):429 433, 2018.
Christian Bongiorno, Yulun Zhou, Marta Kryven, David Theurel, Alessandro Rizzo, Paolo Santi, Joshua Tenenbaum, and Carlo Ratti. Vector-based pedestrian navigation cities, 2021.
Michael Bosse, Paul Newman, John Leonard, Martin Soika, Wendelin Feiten, and Seth Teller. An atlas framework for scalable mapping- In 2003 IEEE International Conference on Robotics and mapping Automation (Cat. No. 03CH37422), volume 2, pp. 1899-19009 IEEE, 2003.
Yoram Burak and Ila R Fiete. Accurate path integration in continuous attractor network models of grid cells. PLoS Comput Biol, 5(2): 1000291, Feb 2009, doi: 10.1371/joumal.ppp 1000291.
Scott Camazine, LeansLouis Deneubourg, Nigel R Franks, James Sneyd, Guy Theraula, and Eric Bonabeau. Self-organizationn in biological systems. Princeton university press, 2020.
Francis Carpenter, Daniel Manson, Kate Jeffery, Neil Burgess, and Caswell Barry. Grid cells form global representation of connected environments. Current Biology, 15(9):1166-1133 2015.
Dori Derdikman, Jonathan R Whitlock, Albert Tsao, Marianne Fyhn, Torkel Hafting, May-Britt Moser, and Edvard I Moser. Fragmentation of grid cell maps in multicompartment environment. Nature neuroscience, 12(10):1325-1332, 2009.
Daniel D Dilks, Joshua B Julian, Jonas Kubilius, Elizabeth S Spelke, and Nancy Kanwisher. Mirror- image sensitivity and invariance object and scene processing pathways. Journal of Neuro- science, 31()3): 1305-113133 2011.
Nathaniel Fairfield, David Wettergreen, and George Kantor. Segmented slam in three-dimensional environments. Journal of Field Robotics, 27(1):85-133 2010.
Patrick Foo, William H Warren, Andrew Duchon, and Michael Tarr. Do humans integrate routes into cognitive map? map-versus landmark-based navigation of novel shortcuts. Journal of Experimental Psychology: Learning, Memory, and Cognition, (1(2):195, 2005.
Sabine Gillner and Hanspeter A Mallot. Navigation and acquisition of spatial knowledge in a virtual maze. Journal of cognitive neuroscience, 10(4):445-485 1998.
10

---

Published as a conference paper at ICLR 2022
Stephen C Hirtle and John Jonides. Evidence of hierarchies in cognitive maps. Memory & cognition, 13(3):208-25 217, 1985.
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-134 1998.
Mirko Klukas, Sugandha Sharma, YiLun Du, Tomas Lozano-Perez, Leslie P.Leslie Kaelbling, and lla Fiete. Fragmented spatial maps: State abstraction and efficient planning from surprisal.
bioRxiv, 2021.
Stephen M Kosslyn, Herbert L Pick Jr, and Griffin R Fariello. Cognitive maps in children and men. Child development, pp. 707-716, 1974.
Marta Kryven, Suhyoun Yu, Max Kleiman-Weiner, and Joshua Tenenbaum. Adventures of human planners maze search task. PsyArXiv, 2021.
Benjamin Kuipers. The spatial semantic hierarchy. Artificial intelligence, 119(1-2):191 2000.
Benjamin Kuipers, Joseph Modayil, Patrick Beeson, Matt MacMahon, and Francesco Savelli. Local metrical and global topological maps in the hybrid spatial semantic hierarchy. In IEEE Interna- tional Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, volume 5, pp. 4845 4851. IEEE, 2004.
Benjamin J Kuipers and Todd Levitt. Navigation and mapping in large scale space. Al magazine, 9(2:255-25, 1988.
Brenden M Lake and Steven T Piantadosi. People infer recursive visual concepts from just a few examples. Computational Brain & Behavior, 3(1):54-65, 2020.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 23506626):133221111 2015.
Steven A Marchette, Lindsay K Vass, Jack Ryan, and Russell A Epstein. Anchoring the neural com- pass: coding of local spatial reference frames in human medial parietal lobe. Nature neuroscience, 17(11):1598, 2014.
Robert U Muller and John L Kubie. The effects of changes in the environment on the spatial firing of hippocampal complex-spike cells. Journal of Neuroscience, 777): 1987.
Nora Newcombe, Janellen Huttenlocher, Elisabeth Sandberg, Eunhui Lie, and Sarah Johnson. What do misestimations and asymmetries in spatial judgement indicate about spatial representation? Journal of Experimental Psychology: Learning. Memory, and Cognition, 25(4):986, 1999.
V Paz- Villagrá, E Save, and Bruno Poucet. Independent coding of connected environments by place cells. European Journal of Neuroscience, 1379):137, 2004.
Benjamin Pitt, Stephen Ferrigno, Jessica Cantlon, Daniel Casasanto, Edward Gibson, and Steven T Piantadosi. PsyArXiv, 2021.
Tony Prescott. Spatial representation for navigation animats, Adaptive Behavior, 4(2):85-123, 1996.
Eric Schulz, Nicholas Franklin, and Samuel Gershman. Finding structure in multi- armed ban- dits. bioRxiv. 2018. doi: 10. 101/432334 URLhttts:://wwe http://wwwwwxwwoo/o/oooooo//oo crmcteeent///tt//////// ear Barl1//0188/2////43355
Tianmin Shu, Marta Kryven, Tomer D Ullman, and Joshua B Tenenbaum. Adventures in flatland: Perceiving social interactions under physical dynamics. In 42d Proceedings of the Annual Meeting of the Cognitive Science Society, 2020.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. Advances in Neural Information Processing Systems, 2010. Neural Information Processing Systems, 2010.

---

Published as a conference paper at ICLR 2022
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354- 359, 2017.
Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv: 2012.
Albert Stevens and Patty Coupe. Distortions in judged spatial relations. Cognitive psychology, 10 (4):422 -437422-437, 1978.
Andreas Stuhlmuller, Joshua B Tenenbaum, and Noah D Goodman. Learning structured generative concepts. In 32d Proceedings of the Anmual Meeting of the Cognitive Science Society. Cognitive Science Society, 2010.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Lucas Tian, Kevin Ellis, Marta Kryven, and Josh Tenenbaum. Learning abstract structure for draw- ing by efficient motor program induction. Advances in Neural Information Processing Systems, 33, 2020.
Momchil S Tomov, Samyukta Yagati, Agni Kumar, Wanqian Yang, and Samuel J Gershman. Dis- covery of hierarchical representations for efficient planning. PLoS computational biology, 16(4): e1007594, 2020.
Jenny Vuong, Andrew W Fitzgibbon, and Andrew Glennerster. No single, stable 3d representation can explain pointing biases in spatial updating task. Scientific reports, 911):1-13, 2019.
Ranxiao Frances Wang and James R Brockmole. Human navigation in nested environments. Journal of Experimental Psychology: Learning. Memory, and Cognition. 29(3):398. 2003.
William H Warren, Daniel B Rothman, Benjamin H Schnapp, and Jonathan D Ericson. Wormholes in virtual space: From cognitive maps to cognitive graphs. Cognition, 166: 166:152-163, 2017.
Jan M Wiener and Hanspeter A Mallot. 'fine-to-coarse route planning and navigation in regionalized environments. Spatial cognition and computation, 3(4):331-358, 2003.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. Transfer learning in sequential decision prob- lems: A hierarchical bayesian approach. In Proceedings of ICML Workshop on Unsupervised and Transfer Learning, pp. 217-227. JMLR Workshop and Conference Proceedings. 2012.
Shanjiang Zhu and David Levinson. Do people use the shortest path? an empirical test of wardrop's first principle. PloS one, 10(8), 2015.
A APPENDIX
A.1 EXPERIMENT 1
Figure 6 shows the stimuli used in the experiment, with practice stimuli in panel A and test stimuli in panel B. Each of the test stimuli is composed of a corridor connecting five instances of a specific unit. The rewards (diamonds) are placed at identical locations within each unit. The task was to navigate the environments and collect all the diamonds in the least amount of time, At the beginning of each trial, the subject is spawned at fixed starting location (marked by a red floor-mat) in all en- vironments. The subjects can then use the keyboard and mouse controls to explore the environment and find the diamonds. Note that there are six base test stimuli with the other six as their reflected versions. We use reflected versions to counter-balance the left and right turns required across en- vironments during the experiment and to increase the number of experimental trials while saving effort on environment design. This experimental design can also be used to study how map induc- tion generalizes to transformations of environments (these results out of the scope of this paper and are therefore not presented). For instance, we noticed that subjects were able to use program induction across environments when they shared similar spatial structures.
12

---

Published as a conference paper at ICLR 2022
Figure 7 shows the scenes displayed during the progression of the experiment. Figure 7 is the welcome scene that subjects see at the beginning of the experiment. Here, we confirm that the subjects consent to participating in the experiment voluntarily, and collect their age and gender information. Figure 7 is the next scene that provides instructions to the subjects about the task and the keyboard/mouse controls that they can to navigate during the task. Figure 7C shows the first practice trial and is followed by three additional practice trials in the order shown in Figure [6A. At the end of each trial, a "Level Complete" (Figure 7D) or "Out of Time" (Figure 9)) pop-up window is displayed depending on whether the subject collected all the diamonds in the environment or ran out of time before doing so. Both these pop-ups also specify the ratio of the number of diamonds collected to the total diamonds embedded in the environment. This provides feedback to the subjects about their performance the trial before they continue to the next trial. At the end of the practice trials, subjects are presented with an instruction quiz as shown in Figure 7 to ensure that they understand the task. If they answer the instruction quiz incorrectly, they are requested to re-read the instructions and re-do the practice trials, and are sent back to the instructions scene in Figure 7B.
If the subjects answer the instruction quiz correctly, they are presented with the twelve test trials (see Figure (B) in succession. An example test trial is shown in Figure 77.. The test stimuli are grouped into three blocks containing four stimuli each, according to their difficulty level. For each subject, the order of stimulus presentation within blocks is randomized, while the blocks themselves are presented in a fixed order e.g., block1 (simple environments Envl, Eny Env1R, IR, Env2R, Env2R) is presented first, followed by block2 (moderate complexity Env3, Env3R, Env4, Env4R), followed by block3 (high complexity- Env5, Env5R, Env6, EnvóR). After the test stimuli, a final scene in Figure 7 is shown to thank the subjects for their participation, get their comments about the strategies they used to solve the task, and their general feedback about the experiment.
Figure shows the results from the experiment. Panel shows the trajectories of a representative subject on six base test trials (Env6), shown in the order presented to the subject (top bot- tom). Panel shows the visitation heat-maps indicating the least to most visited regions in each environment, averaged across subjects. The heat-maps are aggregated across the base environments (EnvI-Env3) and their reflected versions (EnvIR-Env66) RR-Enó))) shown in Figure 6B. Separate heat-maps for the base environments and their reflected versions are also shown in Figure 13 for comparison between the first and the second presentation (mirrored with respect to the first presentation).
A.2 EXPERIMENT 2
Figure 9 shows the stimuli used in this experiment, with practice stimuli in panel A and test stimuli in panel B. The practice stimuli have color cues at the entrance indicating the location of diamonds. Each of the test stimuli is composed of a corridor connecting five instances of a specific unit. Unlike Experiment 1, the diamonds are placed at different locations within each unit determined by the color cue in the cue room of the unit. Relative to the base test environments (Env (Env),,, the reflected versions (Env Env6R) have a reflected geometry, however unlike Experiment 1, they have a different reward distribution. The task was to navigate the environments and collect all the diamonds in the least amount of time. At the beginning of each trial, the subject is spawned at a fixed starting location (marked by red floor-mat) in all environments. The subjects can then the keyboard controls to explore the environment and find the diamonds.
Figure 10 shows the scenes displayed during the progression of the experiment. Figure 10AA is the welcome scene same as in Experimentl. Figure [OB is the next scene that provides instructions to the subjects about the task. The next scene is the instruction quiz shown in Figure 10C that ensures that subjects have read the instructions. If they get the quiz wrong, they are sent back to the instructions page, and requested to re-read them. This is followed by five practice trials in the order shown in Figure PA. As an example. the second practice trial is shown in Figure TOP. At the end of each trial, a "Great Job" (Figure TO]:) or "Out of Time" (Figure TOF) pop-up window is displayed depending on whether the subject collected all the diamonds in the environment or ran out of time before doing so. Both these pop-ups also specify the ratio of the number of diamonds collected to the total diamonds embedded in the environment. This provides feedback to the subjects about their performance in the trial before they continue to the next trial. At the end of the practice trials, subjects presented with another instruction quiz as shown in Figure G to ensure that they understand the task. If they answer the instruction quiz incorrectly, they are requested to re-read the instructions and re-do the practice trials, and are sent back to the instructions scene in Figure 7B.
13

---

Published as a conference paper at ICLR 2022
(
(i0)
(iv)
Env1
Env1R
Env3
Env3R
Env5
Env5R
Env2
Env2R
Env4
Env4R
Envō
EnvōR
Figure 6: Top-down views of the stimuli used in Experimentl. A. Practice stimuli. B. Test stimuli. 'R' indicates reflected. The red square is floor mat indicating the starting location. The red diamonds are the rewards.
the subjects answer the instruction quiz correctly, they are shown additional instructions (Figure
10H) and another instruction quiz (Figure 10) before moving onto the test trials. Next, the twelve test trials (see Figure 9 are presented in succession. An example test trial shown in Figure [O]. The test stimuli are grouped into two blocks containing six stimuli each, according to their difficulty level. For each subject, the order stimulus presentation within blocks is randomized, while the blocks themselves presented in fixed order e.g., block1 (relatively simple environments: Env1,
14

---

Published as a conference paper at ICLR 2022
B
Fee Thaika aat--ppling)
you will dameraa
You shalk all clanardd quility
wifice atvete of seca Your lacus
diiinn Haghar insiae contant
Vii lingo aucalio ridirs
Complcte!
Cen,, you thher the ench
trak tor
Out tital
Whik rouh poeaie gianiiine
York aet Summer
Oare
09.05
Camendee
Thank
fee hoe ttan cry trodllckk obout the ooparient
Lnciliedd Froe the envinomment hast)
Commanc
Figure 7: Screenshots from Experimentl. A. Welcome scene. B. Instructions. C. First practice trial. D. Pop-up window displayed at the end of a successful trial. E. Pop-up window displayed when the subject out of time before collecting all diamonds. F. Instruction Quiz. G. Sample first test trial. H. Concluding scene at the end.
EnvIR, Env3, Env3R, Env5, Env5R) presented first, followed by block2 (high complexity Env2, Env2R, Env4, Env4R, Env6, Env6R).
After the test stimuli, subjects are subjected to a controls skill test unbeknownst to them, to test their skills using navigation controls. This test is introduced ensure that subjects are able navigate in WebUnity without undue difficulty, given the larger environments, and a relatively higher cognitive load in this experiment. The test is introduced at the end rather than at the beginning account for the deterioration of control skills due to fatigue. Subjects are shown the scene Figure ITA that tells them that they are about enter environment with ten diamonds, in every room. They
15

---

Published as a conference paper at ICLR 2022
A
B
Env2
Env1
Most visited
Env3
Least visited
Start
Env4
Env5
Env6
Figure 8: Trajectories and heat-maps from Experiment 1. A. Exploration trajectories of a represen- tative subject. Stimuli are shown in the order presented to the subject (top bottom). B. Visitation heat-map maps aggregated across subjects. Each subject's 's visited area was computed in 2D represen- tation of the environment, using a circular radius of five grid cells centered at the cells traversed by the subject.
are instructed to visit every room to collect all the diamonds. Figure I1B shows the controls skill test trial with the tow-down view of the stimulus shown in Figure [TC. To pass the test, subjects must collect all the diamonds in this trial. The test helps disqualify two types subjects: i) subjects who do not complete the experiment i.e., wait the entrance without exploring the spatial environments, in the hope of getting the base payment from the study; ii) subjects who have difficulty navigating in WebUnity due inexperience/fatigue or difficulty with controls since they may not have the appropriately functioning control devices (mouse/keyboarce test were paid, but excluded from the analysis. Figure TTD shows the trajectory of representative subject who failed the test. After the controls skill test trial, a final scene is shown to thank the subjects for their participation, and get their comments/feedhack.
Subjects who failed the controls skill
Figure 12 shows the results from the experiment on the six base test stimuli (Env 1-Ev6.. Panel A shows the trajectories of a representative subject. The stimuli are shown the order presented to the subject (top- bottom). Panel B shows the heat-maps indicating the least most visited regions each of the base test environments, averaged across subjects. Separate heat-maps for when the base environments shown during the first and the second presentation (mirrored with respect to the first presentation) are shown in Figure 14
A.3 MODEL. LIKELIHOOD COMPARISONS
Our model likelihood analysis aims to compare the similarity of human decisions model deci- sions. Specifically, we wanted to determine which models made the most human-like decisions. Because action-level similarity was too granular, we decided to compare room visitation similarity. We accomplished this by manually breaking each map into set of convex rooms as shown in Fig- ure 15 Using this map decomposition, we obtained an ordering of visited rooms for each human each map. For each point on the human trajectory, human initial state and history of human observations. We queried the model to find an optimal plan from this state. The result of such query is policy tree that branches observations and actions.
provided each model with the current
16

---

Published as a conference paper at ICLR 2022
(
(i0
(ii1)
(iv)
Env1
Env1R
Env6
Env6R
Env2
Env2R
Env5
EnvSR
Env3
Env3R
Env4
Env4R
Figure 9: Top-down views of the stimuli used in Experiment A. Practice stimuli. B. Test stimuli. 'R' indicates reflected. The red square is floor mat indicating the starting location. The red diamonds are the rewards.
The most significant statistic of POMDP policy tree is visitation frequency of nodes on the tree. To convert policy tree to room visitation probabilities, we first flattened all the trajectories in the policy that led to different room. We then summed and normalized their state visitation frequency in the policy tree. This process results in distribution of rooms that the model is likely to visit given the human's experience. The model likelihood for a particular human is defined as the arithmetic mean of the log probabilities of the human's next room in the model's room visitation distribution.
17

---

Published as a conference paper at ICLR 2022
B
Pleat din
Thaika aat--ppling)
iight cas to shetr clamonds are locand buler wrady?
poon
Your
You duttre league danas boar ans dee sedia
wifice atvete of seca Your lacus
ror ean se unforiace di amart sepiiing the des tinae
diiing Hagher iniiae contant
Musin tusu
enttrshisk seseti le sutarattinn de saken Enallstio
ollle memoeee mis experaett
C
Thems mooee beoungg gii rerthut
Wal ond aedic culld si Ball sheel gran.
sudlo the
Ailuve
Gresd You made the achanologate prout!
of tinet
Butee Back must Wi
Yerfhed
of Domanddr
Prose
Phose
Grass Nock motee the prectes
Myssul sual
Cosll you haur for shed pratioe, and naw contree the
fook de lan
anchanclogtt cade teet pant the searrc small room
Fnrsiis su of
Durendoo
coond test
Cala ere dediec at lagest secal.
dove serdare shav
Figure 10: Screenshots from Experiment 2. A. Welcome scene. B. Instructions. C. Instruction Quiz
1. D. Second practice trial. E. Pop-up window displayed at the end of a successful trial. F. Pop-up window displayed when the subject runs out of time before collecting all diamonds. G. Instruction Quiz 2. H. Instructions for test trials. I. Instruction quiz 3. J. Sample first test trial.
18

---

Published as a conference paper at ICLR 2022
A
Fotal Weduimonth
Great almost done.
aichookogists have just discovered this wealthy temple diamond every roo
Cra LeIS Sampa
HITTHA
Figure 11: Controls skill test Experiment A. Instructions about the Controls skill trial. B. Controls skill trial. C. Top-down view of the stimulus used for the test. D. Exploration trajectory of a subject who failed the test.
B
Env1
End
Most visited
Env6
Least visited
Start
Env3
Env4
Env5
Env2
Qualify
Figure 12: Trajectories and heat-maps from Experiment 2. A. Exploration trajectories of a single representative subject. Stimuli are shown in the order presented to the subject (top bottom). B. Visitation heat-maps aggregated across subjects. Each subject's visited area was computed in 2D representation of the environment, using circular radius of five grid cells centered the cells traversed by the subject.
19

---

Published as a conference paper at ICLR 2022
First Presentation
B
Second Presentation
Env2
Env3
visited
visited
Env4
Env5
Env6
Experiment 1 visitation heat-maps aggregated across subjects. A. Heat-maps for the first presentation of environments. B. Heat-maps for the second presentation of environments. The stimuli in the second presentation were reflected versions of the ones in the first presentation as shown in Figure
Figure 13:
First Presentation
Second Presentation
Env1
visited
Env6
visited
Env3
Env4
Env5
Env2
Figure 14: Experiment 2 visitation heat-maps aggregated across subjects. A. Heat-map maps for when base environments are shown during the first presentation. B. Heat-maps when base environments are shown during the second presentation. The stimuli in the second presentation were reflected versions of the ones in the first presentation as shown in Figure
20

---

Published as a conference paper at ICLR 2022
A
B
Figure 15:
Illustration showing how the maps qualitatively broken into convex rooms (discrete areas) A. Envl stimulus from Experiment 1. B. Set convex rooms defined for Enyl. Each color indicates separate convex room.
B
Env1
Env2
Most
visited
visited
Human
Uniform-POMCP
MAP-POMCP
D-POMCP
Figure 16: Model visitation heatmaps from two sample environments in Experiment 1. A. Env1. B. Env2. Top to bottom: top-down view of environment layouts; human visitation heatmaps aggregated across subjects and pairs of reflected environments; visitation heatmap from the Uniform-POne model; visitation heatmap from the MAP-POMCP model; visitation heatmap from the D-POMCP model. The visited area was computed 2D grid projection, using eircular radius of five grid cells around the agent.
21

---

Published as a conference paper at ICLR 2022
B
Env1
Env5
Most visited
Least
Human
Uniform-POMCP
MAP-POMCP
D-POMCP
Figure 17: Model visitation heatmaps from two sample environments in Experiment 2. A. Envl. B. Env5. Top to bottom: top-down view of environment layouts; human visitation heatmaps ag- gregated across subjects; visitation heatmap from the Uniform-POMCE model: visitation heatmap from the MAP-POMCP model; visitation heatmap from the D-POMCP model. The visited area was computed in 2D grid projection, using circular radius of five grid cells around the agent.
22


Reviews:
[{"review_id": "ynbjbrd2W8A", "reviewer": "Reviewer_8xU7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The article is well written and clear, providing a good motivation for the work and an good review of the related literature. I have on the other hand some concerns about the suitability of this paper for this conference and the methodology. \n\nAlthough the author claim the dual goal of: \"(1) to empirically study how humans learn spatial representations using a novel experimental Map Induction Task, and (2) describe a computational model of map induction that can be leveraged to optimize exploration in AI\", point (2) is not really elaborated in the paper, nor does the paper provide experimental evidence to this claim.\n\nTherefore, my first concern with this paper, is that this is effectively a Psychology article. There is nothing wrong with that of course, but the hypothesis, its relation to prior literature and methodology ought to be reviewed by an expert in the field.\nFor example, it is difficult for me to judge how well the results obtained on the proposed task would apply more broadly to human cognition in the real world. Although the literature review is generally good, a better discussion of how the paper's hypothesis fits with existing theories and previous experimental results would be useful. \n\nThe second concern is methodoligical. Although several hypotheses are mentioned in the text of the article, it is not clear how those hypotheses are supported from either the literature or experiments. For example: \n- \"We hypothesize that humans represent survey knowledge as composed of regions\" [p. 3]\n- \"We hypothesize that while navigating novel environments, humans approximately infer a posterior distribution p(M|D) over its possible maps...\" [p.5]\n- \"humans prefer map completions that are maximally descriptive of unseen portions of the environment\" [p.6]\n- \"humans prefer map hypotheses that are minimally contradictory with previous observations.\" [p.6]\nHow confident are the authors that those assumptions hold, and what would be the consequence for their experimental results if they did not? \n\nMoreover, the experimental results do not seem to clearly provide the evidence to support or discard the hypothesis. No hypothesis testing is provided. Concerning the number of participants in each experiment: Why using such a small number of participants if using Amazon mechanical Turk? Are the authors confident that this number is sufficient to prove/disprove the hypothesis? ", "summary_of_the_paper": "This paper investigates the concept of map induction for exploration in novel environments. This is an important problem for robotics applications, relevant for scaling up navigation of autonomous systems to large environments and for exploring unknown environments. \n\nThe article's main contribution is a new task and a set of experiments to evaluate the central hypothesis: \"that humans use program induction to infer possible maps of unseen spaces, as made up of submaps encountered in the observed areas\".\n\nThis is evaluated by proposing a novel map induction task that is the main contribution of the paper, as well as a set of probabilistic models that implement the different hypotheses considered in the paper. ", "summary_of_the_review": "In summary, the paper is generally well written and tackling and interesting question. The proposed task is interesting, but I am concerned that the paper does not provide a clear argument that the proposed methodology and analysis actually prove the hypothesis. \n- This paper is mainly a Psychology study (as the computational model for AI part of the claims is not really demonstrated), and ought to be reviewed by an expert in experimental psychology. \n- The analysis of the result does not provide clear evidence that the hypothesis is true\n- The hypothesis should be framed more clearly with the existing literature, existing hypotheses of human spatial cognition and prior experimental evidence using established tasks. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "nqDa6SBMdE", "reviewer": "Reviewer_M48j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n- The experiments are tailored to the main hypothesis of the paper and manage to highlight the argued points well. It is evident that exploration is more efficient under the assumed computational model when solving the reward collection task, which indicates that the map induction is indeed informing the planner.\n- The conducted real-life study also seems well-constructed. The results in fig. 4, d) and fig. 5, d) support the idea that a fully-probabilistic map induction model comes closer to human behavior than an uninformed / a point-estimated (MAP) one.\n- The presented figures are legible and convey the message of the paper well.\n\n## Weaknesses\n\n- The considered environments are very simplified and exhibit very regular structures (repeating patterns). This is understandable, they are tailored to the proposed hypothesis and highlight the arguments made in the paper, they are also useful for comparing human behavior to the computational model. However, I cannot judge how well the presented arguments would extrapolate to more realistic (natural) environments, where e.g. repetition patterns & regularities are much less obvious.\n- I find the claim in the abstract that the proposed approach outperforms state-of-the-art planning algorithms to be overstated (largely because of the previous point).\n- Since everything is discrete and because of the combinatorial nature of map induction, the cardinality of the space over possible maps will quickly explode. This is acknowledged in the conclusion, but I am not sure if a discretized approach like program induction will scale well, even if shorter programs are considered (it can hurt planning performance). Have you considered some form of continuous relaxations?\n- I think the section on the assumed computational model can be improved, right now it lacks a rigorous specification of the assumed joint distribution / probabilistic model of all variables in question (e.g. how the factorization looks, initial prior on the map, etc.).\n- In section 3.1.4, the POMDP is introduced with a state-space that captures both agent states & map hypotheses. In that context, I find the verbal description of the assumed transition model confusing: it implies normalizing the map hypothesis distribution after a movement action is executed. Can you clarify why this is necessary? I think the clarity of this section would be better if the assumed transition model is explicitly specified (in terms of a conditional distribution).\n- Is the likelihood in section 3.1.3. a well-defined distribution? It needs to integrate to 1 over the space of possible observations D (which should be discrete), but based on the description it seems like there can be many observations for which it evaluates to 1 (e.g. if $\\beta$ and $\\gamma$ are 0).\n- Ideally, I would like to see visitation heatmaps from the computational model next to the ones in fig. 4 and fig. 5 from the real-life study, to judge whether the visitation patterns are similar / where they differ. The aggregated results in fig 4. c) d) and fig 5. c) d) somewhat obfuscate the comparison.\n", "summary_of_the_paper": "This work is motivated by the hypothesis that humans maintain a hierarchical spatial representation when exploring new environments, such that shared patterns (due to the hierarchy) between spatial regions can be used to predict how still unvisited places would look. A simple discrete 2D computational model based on probabilistic program induction is proposed for predicting the map at yet unseen places. The model assumes a discrete set of possible transformations (flips, rotations, concatenations, etc.) of small extracted regions (submaps of previous observations), based on which a distribution over possible completions of empty map regions can be formulated.\n\nA control task is then considered, in which an agent needs to explore a completely new environment and collect rewards (tokens) in the process. Under strong structural assumptions for the test environments (e.g. it is ensured that patterns actually repeat in a very uniform way, rooms look the same, rewards are placed consistently, etc.), it is shown that model-based planning under the map-induction model results in more efficient exploration & reward-collection behavior. Furthermore, a study with actual human subjects is conducted where they need to solve the same task. Results suggest that real-life exploration behavior is consistent with the most expressive version of the proposed computational model, where a full distribution over possible map completions is maintained (as opposed to a MAP estimate or an uninformed model).\n", "summary_of_the_review": "I find the idea of the paper interesting, and I think the selected suite of experiments highlights the points the paper makes rather well. However, I cannot tell if the insights about map induction would extrapolate to more realistic cases, as the considered environments are very regular & specific in their repeating patterns, applicability might be limited. I also think the clarity of the model specification & the assumed probabilistic assumptions can be improved, I listed my main concerns in the main review.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nGlyCzHSKui", "reviewer": "Reviewer_toMF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n\n- While there are multiple heuristic / learnt models for exploration of novel spaces, modeling how humans explore novel environments is an interesting area of research. In this paper, the authors present an interesting take on this problem by treating it as program induction — inferring the program that will lead to a correct map of the environment based on past observations.\n- The experimental setup and inferences made through the experiments were easy to grasp and made sense to me. The experiments were designed to test the two main hypothesis (1. Does humans rely on some sort of map induction for exploration as opposed to uniformly visiting all the map regions? 2) Do humans seek information about the task to score different possible map completion hypotheses?)\n\n**Weaknesses:**\n\n- A major concern for this paper is that the task was designed keeping the hypothesis is mind. For instance, the maps and 3D environments are synthetically constructed such that they have repeated blocks. Given that the environments were created to have repeatability, humans performing the task will obviously pickup on that signal. It would have been better if the experiment was conducted using publicly available layouts (3D scans like Gibson, Matterport etc).\n- On a related note, the environments are composed of simple units and are almost grid-world like. For such environments, production rules (Table 1) used to generate map hypotheses are simple. Can the authors comment on how this will generalize to generic environments which might have fairly arbitrary layouts?\n\n**Updates after Rebuttal**\nThank you authors for your responses and clarifications to my concerns. I think the hypotheses presented in the paper are interesting and are tested appropriately. Even though the paper lacks experiments on more complicated environments such as Gibson, Matterport, I think the ideas presented in the paper are good first steps and might be useful to the broader community (including myself). Thus, I am happy to update my scores. ", "summary_of_the_paper": "In this paper, the authors try to model how humans explore novel environments. The main hypothesis tested in the paper is that humans think of maps of unseen places as compositions of submaps in observed areas. Towards this, the authors propose a new \"Map Induction Task\" (MIT) to study how humans explore novel maps. Additionally, they try to model the exploration behavior exhibited by humans as a hierarchical bayesian generative framework which generates a distribution over possible maps given past observations, and use this distribution to plan. They present results on their  task (MIT) which validate the aforementioned hypothesis", "summary_of_the_review": "The authors present an interesting hypothesis regarding modeling human exploration behavior. However, I am not convinced that the experimental setup captures general human exploration. The experimental setup were synthetically created to have repeatability and doesn't capture the general layouts (of indoor spaces or otherwise). Thus, I am not convinced that these hypotheses will hold true when tested on realistic environments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EjrDrnvuyQG", "reviewer": "Reviewer_vNyW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although it is a work focused on how humans plan and predict unseen space, it provides good inspiration for artificial intelligence. The work is novel, as program induction has not been applied to map prediction and spatial planning before. I believe it will also inspire much more in-depth experimental works.\nOne minor concern I have is about the experimental design and analysis: when participants visit mirrored environments, they may recognize it is an mirror image of a previously learned environment, and thus the predicted distribution of map may be different from when they first see that environment. It was not clear to me whether mirroring of a previously learned environment is part of the program induction, as I suppose most of the modeling is performed within game instead of across game. Please clarify this. \nFurther, due to the above reason, it seems less justified to combine the result of first visit of an environment and the visit of its mirror environment. It would be good to plot heatmaps for them separately in the appendix.\n\nAn illustration of how the authors manually breaking each map into a set of convex rooms is necessary for understanding the model fitting. Is the model likelihood geometric or arithmetic average of the predicted probability of humans' next room visitation across all convex rooms (last sentence of A.3)?\n\n\nIt was not super intuitive for me why D-POMCP would predict better than MAP-POMCP in experiment 2. Is it mainly because the reward locations themselves cannot be deterministically predicted as in Experiment 1? \nIs there any component of softmax in the model's policy for choosing routes? If not, where does stochasticity come from in the predicted distribution of visitation by the models? If yes, will D-POMCP still win when the softmax temperature or epsilon-greedy are free parameters?\n\nAre there any free parameters being tuned to fit data? If yes, what are they?", "summary_of_the_paper": "This paper tests a hypothesis of how humans choose the path to explore and maximize reward in unvisited space based on their past experience. The central hypothesis is that human uses program induction to generate prediction of possible spatial map. Based on human behavior in two experiments, the paper further compared different models of map prediction, and demonstrated that humans actually consider the distribution of possible maps instead of only consider the most likely map.\n\n", "summary_of_the_review": "The paper appears to be generally interesting and novel. Perhaps because of the page limit, not enough details that would be expected for a human behavioral modeling are provided, and I hope they can be added during revision. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a hierarchical Bayesian approach to exploration in grid worlds.  The paper considers the hypothesis that humans maintain a hierarchical representation when exploring a space, where the distribution over unknown space can be modeled with a structured probabilistic program.  The paper compares the behavior of people during exploration tasks to the behavior of a Bayesian model under different distributional approximations.  The results indicate that people can behave similarly to a sophisticated Bayesian model on small grid world domains.

The reviews highlighted several concerns about the paper.  One initial concern was that the experimental domain is too simple and small compared to real world environments encountered by robots or humans.  However, this work is similar in scope to other exploration work in reinforcement learning and psychology studies, where tiny grid worlds are still commonly used to gather insight.  Thus, this concern does not reduce the potential contribution of the paper.  The reviewers raised several other concerns about the work that were largely addressed by the author response.  The remaining reviewer concerns centered on the limited strength of the evidence in the experiments, but the reviewers expect the paper will still be of interest to the broader research community.

Four reviewers indicate to accept this paper for its contribution of a study into the use of probabilistic program induction to infer possible completions of maps in small environments.  The paper is therefore accepted.
Decision: Accept (Poster)