Emergence of Maps in the Memories of Blind Navigation Agents
Authors: Erik Wijmans
Manolis Savva
Irfan Essa
Stefan Lee
Ari S. Morcos
Dhruv Batra
Venue: ICLR 2023 notable top 25% (2023)
Keywords: embodied AI
navigation
characterizing representations

Abstract: Animal navigation research posits that organisms build and maintain internal spa- tial representations, or maps, of their environment. We ask if machines – specifically, artificial intelligence (AI) navigation agents – also build implicit (or ‘mental’) maps. A positive answer to this question would (a) explain the surprising phenomenon in recent literature of ostensibly map-free neural-networks achieving strong performance, and (b) strengthen the evidence of mapping as a fundamental mechanism for navigation by intelligent embodied agents, whether they be biological or artificial. Unlike animal navigation, we can judiciously design the agent’s perceptual system and control the learning paradigm to nullify alternative navigation mechanisms. Specifically, we train ‘blind’ agents – with sensing limited to only egomotion and no other sensing of any kind – to perform PointGoal navigation (‘go to $\Delta$x, $\Delta$y’) via reinforcement learning. Our agents are composed of navigation-agnostic components (fully-connected and recurrent neural networks), and our experimental setup provides no inductive bias towards mapping. Despite these harsh conditions, we find that blind agents are (1) surprisingly effective navigators in new environments (∼95% success); (2) they utilize memory over long horizons (remembering ∼1,000 steps of past experience in an episode); (3) this memory enables them to exhibit intelligent behavior (following walls, detecting collisions, taking shortcuts); (4) there is emergence of maps and collision detection neurons in the representations of the environment built by a blind agent as it navigates; and (5) the emergent maps are selective and task dependent (e.g. the agent ‘forgets’ exploratory detours). Overall, this paper presents no new techniques for the AI audience, but a surprising finding, an insight, and an explanation.

Published as a conference paper at ICLR 2023
EMERGENCE OF MAPS IN THE MEMORIES
OF BLIND NAVIGATION AGENTS
Erik Wijmans 2-
-22 Manolis Savva Irfan Essa 1.4 Stefan Lee Ari S. Morcos Dhruv B Georgia Institute of Technology ?FAIR, Meta AI Simon Fraser University Google Research Atlanta "Oregon State University
ABSTRACT
Animal navigation research posits that organisms build and maintain internal spa- tial representations, maps, of their environment. We ask if machines sppccifi- cally, artificial intelligence (AI) navigation agents - also build implicit (or 'men- tal') maps. A positive answer to this question would (a) explain the surprising phenomenon in recent literature of ostensibly map-free neural-networks achieving strong performance, and (b) strengthen the evidence of mapping fundamental mechanism for navigation by intelligent embodied agents, whether they be biolog- ical or artificial. Unlike animal navigation, perceptual system and control the learning paradigm to nullify alternative naviga- tion mechanisms. Specifically, we train 'blind' agents with sensing limited only egomotion and no other sensing of any kind to perform PointGoal navi- gation ('go Ax, Ay') via reinforcement learning. Our agents are composed of eevigation-agnssie components colly-conneeted and recurrent neural networks), and our experimental setup provides no inductive bias towards mapping. Despite these harsh conditions, we find that blind agents are (1) surprisingly effective nav- igators in new environments (~-95% success); (2) they utilize memory over long horizons (remembering ~ 11,000 steps of past experience in episode); (3) this memory enables them to exhibit intelligent behavior (following walls, detecting collisions, taking shortcuts); (4) there is emergence maps and collision detection neurons in the representations of the environment built by a blind agent as it nav- igates; and (5) the emergent maps are selective and task dependent (e.g. the agent 'forgets' exploratory detours). Overall, this paper presents no new techniques for the AI audience, but surprising finding, an insight, and an explanation.
can judiciously design the agent's
INTRODUCTION
Decades of research into intelligent animal navigation posits that organisms build and maintain inter- nal spatial representations (or maps)' of their environment, that enables the organism to determine and follow aas--appropriate paths (Tolman, 1948; O'keefe & Nadel, 1978; Epstein al., 2017). Hamsters, wolves, chimpanzees, and bats leverage prior exploration to determine and follow short- cuts they may never have taken before (Chapuis & Scardigli, 1993; Peters, 1976; Menzel, 1973;
Toledo et al., 2020; Harten et al., 2020). Even blind mole rats and animals rendered situationally- blind in dark environments demonstrate shortcut behaviors (Avni et al., 2008; Kimchi et al., 2004; Maaswinkel & Whishaw, 1999). Ants forage for food along meandering paths but take near-optimal return trips (Müller & Wehner, 1988), though there is some controversy about whether insects like ants and bees capable of forming maps (Cruse & Wehner, 201 I; Cheung al., 2014).
Analogously, mapping and localization techniques have long played a central role in enabling non- biological navigation agents (or robots) to exhibit intelligent behavior (Thrun et al., 2005; Institute,
*Correspondence etw@gatech. edu.
'Throughout this work, we use 'maps' to refer to a spatial representation of the environment that enables intelligent navigation hehavior like taking shortcuts. We provide detailed discussion and contrast w.r.t. cognitivv map' defined by O' O'keefe & Nadel (1978) in Apx. B.1.

---

Published as a conference paper at ICLR 2023
1972: Ayache & Faugeras, 1988; Smith et al., 1990). More recently, the machine learning commu- nity has produced a surprising phenomenon - neural-network models for navigation that curiously do not contain any explicit mapping modules but still achieve remarkably high performance (Savva et al., 2019; Wijmans et al., 2020; Kadian et al., 2020; Chattopadhyay et al., 2021; Khandelwal et al., 2022; Partsey et al., 2022; Reed et al., 2022). For instance, Wijmans et al. (2020) showed that a simple 'pixels-to-actioe
architecture (using a CNN and RNN) can navigate to given point in a novel environment with near-perfect accuracy; Partsey et al. (2022) further generalized this result to more realistic sensors and actuators. Reed et al. (2022) showed a similar general purpose archi- tecture (a transformer) can perform a wide variety of embodied tasks, including navigation. The mechanisms explaining this ability remain unknown. Understanding them is both of scientific and practical importance due to safety considerations involved with deploying such systems.
In this work, we investigate the following question - is mapping an emergent phenomenon? Specif- ically, do artificial intelligence (Al) agents learn to build internal spatial representations (or 'mental' natural consequence of learning to navigate?
maps) of their environment
The specific task we study is PointGoal navigation (Anderson et al., 2018), where an Al agent is introduced into new (unexplored) environment and tasked with navigating to relative location "go 5m north. 2m west relative to start". This is analogous to the direction and distance of foraging locations communicated by the waggle dance of honey bees (Von Frisch, 1967).
Unlike animal navigation studies, experiments with AI agents allow us to precisely isolate map- ping from alternative mechanisms proposed for animal navigation the use of visual land- marks (Von Frisch, 1967), orientation by the arrangement of stars (Lockley, 1967), gradients of olfaction other senses (Ioalè et al., 1990). We achieve this isolation by judiciously designing the agent's perceptual system and the learning paradigm such that these alternative mechanisms are rendered implausible. Our agents are effectively 'blind'; they possess a minimal perceptual system capable of sensing only egomotion, i.e. change in the agent's 's location and orientation as the it moves no vision, no audio, no olfactory, no haptic, no magnetic, or any other sensing of any kind. This perceptual system is deliberately impoverished to isolate the contribution of memory, and is inspired by blind mole rats, who perform localization via path integration and use the Earth's magnetic field as a compass (Kimchi et al., 2004). Further still, agents are composed of anvigation-agnostic generic, and ubiquitous architectural components (fully-connectter layers and LSTM-based recur- rent neural networks), and our experimental setup provides inductive bias towards mapping no map-like or spatial structural components in the agent, no mapping supervision, no auxiliary tasks, nothing other than reward for making progress towards a goal.
Surprisingly, even under these deliberately harsh conditions, we find the emergence of map-like spatial representations in the agent's non-spatial unstructured memory, enabling it to not only suc- cessfully navigate to the goal but also exhibit intelligent behavior (like taking shortcuts, following walls, detecting collisions) similar aforementioned animal studies, and predict free-space in the environment. Essentially, we demonstrate an 'existence proof" or an ontogenetic developmental ac- count for the emergence of mapping without any previous predisposition. Our results also explain the aforementioned surprising finding in recent literature that ostensibly map-free neural-netwer achieve strong autonomous navigation performance - by demonstrating that these 'map-free' sys- tems in fact learn to construct and maintain map-like representations of their environment.
Concretely, we ask and answer following questions:
1) Is it possible to effectively navigate with just egomotion sensing? Yes. We find that our 'blind' agents are highly effective in navigating new environments - reaching the goal with 95. 1 1..3..3 success rate. And they traverse moderately efficient (though far from optimal) paths, reaching 62.9%.1.6% of optimal path efficiency. We stress that these are novel testing environments, the agent has not memorized paths within training environment but has learned efficient navigation strategies that generalize to novel environments, such as emergent wall-following behavior.
2) What mechanism explains this strong performance by 'blind' agents? Memory. We find that memoryless agents completely fail at this task, achieving nearly 0% success. More importantly, we find that agents with memory utilize information stored over long temporal and spatial hori- zon and that collision-detection neurons emerge within this memory. Navigation performance as function of the number of past actions/observations encoded in the agent's 's memory does not
Thee description in English is purely for explanatory purposes; the agent receives relative goal coordinates.
2

---

Published as a conference paper at ICLR 2023
saturate till one thousand steps (corresponding to the agent traversing 89.1 2066 meters), suggest- ing that the agent 'remembers' a long history of the episode.
3) What information does the memory encode about the environment? Implicit maps. We perform an Al rendition of Menzel (1973y's experiments, where a chimpanzee is carried by a human and shown the location of food hidden in the environment. When the animal is set free to collect the food, it does not retrace the demonstrator's s steps but takes shortcuts to collect the food faster. Analogously, we train a blind agent to navigate from a source location (S) to a target location (T). After it has finished navigating, we transplant its constructed episodic memory into a second probe'-agen (which is also blind). We find that this implanted-memon drumaticully better in navigating from S to T (and T to S) than it would without the memory transplant. Similar to the chimpanzee, the probe agent takes shortcuts, typically cutting out backtracks or excursions that the memory-creator had undertaken as it tried to work its way around the obstacles. These experiments provide compelling evidence that blind agents learn to build and use implicit map-like representations of their environment solely through learning to navigate. Intriguingly further still, we find that surprisingly detailed metric occupancy maps of the environment (indicating free-space)
probe-agent performs
be explicitly decoded from the agent's 's memory.
4) Are maps cask-dependent? Yes. We find that the emergent maps are function of the navigation goal. Agents 'forget' excursions and detours, i.e. their episodic memory only preserves the features of the environment relevant to navigating to their goal. This, in part, explains why transplanting episodic memory from one agent to another leads take shortcuts because the excursion and detours are simply forgotten.
Overall, our experiments and analyses demonstrate that 'blind' agents solve PointGoalNav by combining information over long time horizons to build detailed maps of their environment, solely through the learning signals imposed by goal-driven navigation. In biological systems, convergent evolution of analogous structures that cannot be attributed to a common ancestor (e.g. eyes in vertebrates and jellyfish (Kozmik et al., 2008) is often an indicator that the structure a natural response to the ecological niche and selection pressures. Analogously, our results suggest that mapping may be a natural solution to the problem of navigation by intelligent embodied agents, whether they be biological or artificial. We now describe our findings for each question in detail.
2 BLIND AGENTS ARE EFFECTIVE NAVIGATORS
We train navigation agents for PointGoalNav in virtualized 3D replicas of real houses utilizing the AI Habitat simulator (Savva et al.. 2019; Szot et al., 2021) and Gibson (Xia et al., 2018) and Matterport3D (Chang et al., 2017) datasets. The agent is physically embodied as an cylinder with a diameter 0.2m and height 1.5m. each episode, the agent is randomly initialized in the environ- ment, which establishes an episodic agent-centric coordinate system. The goal location is specified in cartesian coordinates (Z My: 2g) in this system. The agent has four actions - morw_forward (0.25 meters), turn_ (10"), turn_right (10"), and stop (to signal reaching the goal), and allowed maximum of 2,000 steps to reach the specified goal. is equipped with an egomotion sensor provid- ing it relative position (Ar, Ay, A2) and relative 'heading' (or yaw angle) AØ between successive steps, which is integrated to track the agent's 's pose relative to start [x,, yt. 24, Oz). This is sometimes referred to as a 'GPS+Compass' sensor in this literature (Savva et al., 2019; Wijmans et al., 2020).
We use two task-performance dependent metrics: i) Success, defined as whether the agent predicted stop within 0.2 meters of the target, and ii) Success weighted by inverse Path Length (SPL) (Ander- son et al., 2018), defined as success weighted by the efficiency of agent's 's path compared to the oracle path (the shortest path). Given the high success rates we observe, SPL can be roughly interpreted as efficiency of the path taken compared to the oracle path e.g. 95% SPL means the agent took path 95% as efficient as the oracle path while 50% SPL means the agent was 50% as efficient. Perfor- mance is evaluated in previously wnseen environments to test generalization, not just memorization.
The agent's policy is instantiated as a long short-term memory (LSTM) (Hochreiter Schmidhuber, 1997) recurrent neural network formally, given current observations o = [xgg Vg. Tt, (h, c.) = LSTM(o., (h,-1, 1)). We refer to this (hr. c,) as the agent's s internal memory repre- sentation. Note that only contains information gathered during the current navigation episode. We train our agents for this task using a reinforcement learning (Sutton & Barto, 1992) algorithm called DD-PPO (Wijmans et al., 2020). The reward has a term for making progress towards the goal and for successfully reaching it. Neither the training procedure nor agent architecture contain explicit inductive biases towards mapping or planning relative to map. Apx. A. describes training details.
Tt, Ut. 21 0t),
3

---

Published as a conference paper at ICLR 2023
(4)
CAM
Forward No
GRS-Compess
Dug Anep Lat
Foward Colicad
Tar Calation
Figure 1: (A) PointGoal navigation. An agent is initialized in a novel environment (blue square) and task with navigation to a point specified relative to the start location (red square). We study 'blind' agents, equipped with just an egomotion sensor (called GPS+Compass in this literature). (B) 'Blind' agent vs. bug. Our learned 'blind' agent compared to 2 variants and an oracle equipped variant of the Bug algorithm (Lumelsky & Stepanov, 1987). The Bug algorithm initially orients itself towards the goal and then proceeds towards the goal. Upon hitting a wall, it follows along the wall until it reaches the other side. The oracle version is told whether woll-following left or right is optimal, providing an upper-bound on Bug algorithm performance. (C) t-SNE of the agent's internal representation for collisions. We find 4 overall clusters corresponding to the previous action taken and whether or not that action led to a collision.
Surprisingly, we find that agents with this impover- ished sensing regime are able to navigate with near-
Agent
Success
SPL
Blind
95.1 1...
62.9114
perfect efficacy - reaching the goal with 95. +1.% success rate (Table 1), even when the agent must take hundreds of actions and traverse over 25m. This per- formance is similar in success rate (95.1 vs 94.0)² to a sighted agent (equipped with a depth camera) trained on larger dataset (HM3D) (Ramakrishnan et al., 2021). The paths taken by the blind agent are moderately efficient but (as one might expect) far less so than a sighted agent (62.9 vs 83.0 SPL).
Clairvoyant Bug
100.00
46.0
3 Sighted (Depth)
94.0
83.0
(Ramakrishnan et al., 2021)
Table 1: PointGoalNav performance agents on PointGoalNav. We find that blind agents are surprisingly effective (success) though not efficient (SPL) navigators. They have similar success as an agent equipped with Depth camera and higher SPI. than a clair- voyant version of the 'Bug' algorithm.
At this point, it might be tempting to believe that this is an easy navigation problem, but we urge the reader to fight hindsight bias. We contend that the SPL of this blind agent is surprisingly high given the impoverished sensor suite. To put this SPL in context, we compare it with 'Bug algorithms' (Lumelsky & Stepanov, 1987), which are motion planning al- gorithms inspired by insect navigation, involving In these algorithms, the agent first orients itself towards the goal and then travels directly towards until it encounters wall, in which case it follows along the wall along one of two directions of travel. The primary challenge for Bug algorithms is determining whether to go left or right upon reaching wall. To provide upper bound on performance, we implement a 'clairvoyant' Bug algorithm agent with an oracle that tells it whether left or right is optimal. Even with the additional privileged information, the 'clairvoyant' Bug agent achieves SPL of 46% which is considerably less effi- cient than the 'blind' agent. Fig. 1b shows an example of the path our blind agent takes compared to 3 variants of the Bug algorithm. This shows that blind navigation agents trained with reinforcement learning are highly efficient at navigating in previously unseen environments given their sensor suite.
agent equipped with only a localization sensor.
2.1 EMERGENCE OF WALL-FOLLOWING BEHAVIOR AND COLLISION DETECTION NEURONS
Fig. 1b shows the blind agent exhibiting woll-following behavior (also blue paths in Fig. A6 and videos in supplement). This behavior is remarkably consistent; the agent spends the majority of an episode near a wall. This is surprising because it is trained to navigate as quickly as possible. thus, would be rewarded for traveling in straighter paths (that avoid walls). We hypothesize that this strat- egy emerges due two factors. 1) The agent blind, it has no way to determine where obstacles are besides 'bumping' into them. 2) The environment is unknown to the agent. While this is clearly true for testing environments is also functionally true for training environments because the coordinate
It may seem like the blind agent outperforms the sighted agent, hut performance is within our bars.
4

---

Published as a conference paper at ICLR 2023
system is episodic, every episode uses agent was spawned; and the since the agent is blind, it cannot perform visual localization.
coordinate system based on how the
We test both hypotheses. To test (2), we provide experiment in Apx. C.I showing that when the agent is trained in a single environment with a consistent global coordinate system, it learns to memorize the shortest paths in this environment and wall-following does not emerge. Consequently, this agent is unable to navigate in new environment, achieving 100% success on train and 0% on test.
To test (1), analyze whether the agent is capable of detecting collisions. Note that the agent is not equipped with a collision sensor. In principle, the agent can infer whether it collided - if tries move forward and the resulting egomotion is atypical, then it is likely that collision happened. This leads us to ask does the agent's 's memory contain information about collisions? We train linear classifier that uses the (frozen) internal representation (h++1. ct+1) to predict if action ar resulted in collision (details in Apx. A.5). The classifier achieves 98% accuracy on held-out data. As comparison, random guessing on this 2-class problem would achieve 50%. This shows the agent's s memory not only predicts its collisions, but also that collision-vs-not are linearly separable in reteesalrppresentationn space, which strongly suggests that the agent has learned a collision sensor.
Next, we examine how collisions are structured in the agent's ss internal representation by identifying the subspace that used for collisions. Specifically, we re-train the linear classifier with an 41- weight penalty to encourage sparsity. We then select the top 10 neurons (from 3072) with the largest weight magnitude; this reduces dimensionality by 99.7% while still achieving 96% collision-vs-no accuracy. We t-SNE (Van der Maaten & Hinton, 2008) create 2-dimension visualization. We find 4 distinct semantically waaatiically-mmaingfuuu clusters (Fig. Ic). One cluster always fires for collisions, one for forward actions that did not result in a collision, and the other two correspond to turning actions. Notice that these exceedingly small number of dimensions and neurons essentially predict all collisions and movement of the agent. We include videos in the supplementary materials.
MEMORY IS USED OVER LONG HORIZONS
Next, we examine how memory is utilized by asking if the agent uses memory solely to remember short-term informa- tion (e.g. did it collide in the last step?) or whether it also in- cludes long-ran
Performance (Higher is better)
SPL
information (e.g. did it collide hundreds of
80
Succoss
steps ago?). To answer this question, we restrict the memory
60
capacity of our agent. Specifically, let k denote the memory budget. At each time t, we take the previous observations, De-k+1....;; 0r). and construct the internal representation (h,, C.) via the recurrence (h,, c,) = LSTM(O;; (h;-1,c;-1)) fort k
4.0
20
k < i
t where (hı-k; kz-k) = 0).
10"
10'
10"
1o²
Memory Length (log-scale)
the agent is only leveraging its memory for short-term stor- age would expect performance to saturate at a small value of kt Instead, Fig. 2 shows that the agent leverages its memory for significantly long term storage. When memoryless (k- 1), the agent completely fail at the task, achieving nearly 0% suc- cess. Navigation performance as function of the memory budget (k) does not saturate till one thousand steps. Recall that the agent can move forward 0.25 meters or turn 10 at each step. The average distance traveled in 1000 steps is 89. 19066 meters, indicating that remembers information over long temporal and spatial horizons. In Apx. C.6 we train agents to operate at specific memory budget. We find that a budget of k = 256, the largest we are able to train, is not sufficient to achieve the performance of unbounded.
Figure 2:
Navigation perfor- mance vs. memory length. Agent performance does not saturate until memory can contain information from hundreds of steps. A mem- ory of 103 steps is half the maxi- mum episode length.
MEMORY ENABLES SHORTCUTS
To investigate what information is encoded the memory of our blind agents, we develop an exper- imental paradigm based on 'probe' agents. A probe is secondary navigation agent" that is struc- turally identical to the original (sensing, architecture, etc.), but parametrically augmented with the primary agent's 's constructed episodic memory representation (hy, cr). The probe has no influence
"o avoid confusion, we refer this probe agent as 'prohe' and the primary agent as 'agent' from this point.
5

---

Published as a conference paper at ICLR 2023
(A)
(8)
(S
SecomdNaatTT-
S
Type
Success
SPL
Success
Zerooeorryy
22.0
Tradneskgontteeeery
96.2 (9:0
$3.01
96.0..16
Newoo
Probe Network
LOT1 LCTM
LSM
LOTM
Figure 3: (A) Probe experiment. First, an agent navigates (blue path, blue LSTM) from start (green sphere) to target (red sphere). After the agent navigates, we task a probe (purple LSTM) with performing the same navigation episode with the additional information encapsulated in the agent's s internal representation (or memory). h The probe is able to navigate more efficiently by taking shortcuts (purple path). As denoted by the dashed line between the probe and agent networks, the probe does not influence what the agent stores in its internal representation. (B) Agent memory increases probe efficiency (SPL). Results of our trained probe agent under three configurations initialized with an empty representation (AllZeroMemory), a representation of a random agent and the final representation of the 95% confidence interval reported over 5 agent-probe pairs.
walked along the trained agent's 's path trained agent TrriieddAeetteeean
on the agent, i.e. no gradients (or rewards) follow from probe agent (please see training details in Apx. A.2). We use this paradigm to examine whether the agent's final internal representation contains sufficient information for taking shortcuts in the environment.
As illustrated in Fig. 3A, the agent first navigates from source (S) to target (T). After the agent reaches T, a probe is initialized at S, its memory initialized with the agent's final memory repre- sentation, i.e. (ho, C probe (hr, Cr) ) and tasked with navigating to T. We refer to this probe task as SecondNav(S TT). All evaluations are conducted in environments not used for training the agent nor the probe. Thus, any environmental information in the agent's memory must have been gathered during its trajectory (and not during any past exposure during learning), Similarly, all initial knowledge the probe has of the environment must come from the agent's 's memory (hy, er) )agent
Our hypothesis is that the agent's 's memory contains a spatial representation of the environment, which the probe can leverage. If the hypothesis is true, we would expect the probe to navigate Sec- ondNav(S->>) T) more efficiently than the agent (e.g. by taking shortcuts and cutting out exploratory excursions taken by the agent). If not, would expect the probe perform on-par with the agent since the probe is being trained on essentially the same task as the agent In our experiments, we find that the probe is significuntly more efficient than the agent SPL of 62.9%+1.64 (agent) vs. 85.0% 10.16% (probe). It is worth stressing how remarkable the performance of the probe is in a new environment, a blind probe navigating without a map traverses path that is within 15% of the shortest path on the map. The best known sighted agents (equipped with an RGB camera, Depth sensor, and egomotion sensor) achieve an SPL of 84% on this task (Ramakrishnan et al., 2021). Essentially, the memories of blind agent are as valuable as having vision!
Fig. 3A shows the difference in paths between the agent and probe (and videos showing more exam- ples are available in the supplement). While the agent exhibits wall-following behavior, the probe instead takes more direct paths and rarely performs wall following. Recall that the only difference in the agent and probe is the contents of the initial hidden state reward is identical (and available only during training), training environments are identical (although the episodes are different), and eval- uation episodes are identical meaning that the environmental representation in the agent's 's episodic memory is what enables the probe to navigate more efficiently.
We further compare this result (which we denote TrainedAgentMemoryy with two control groups: 1) AllZer An empty (all zeros) episodic memory to test for any systematic biases in the
'The prohe's heading at S 'We note that an argument can be made that if the agent's memory is useless to the probe, then the probe is being trained on harder task since it must learn navigate and ignore the agent's 's memory. But this argument would predict the prohe's 's performance to he lower not higher than the agent.
the agent's final heading upon reaching T.
6

---

Published as a conference paper at ICLR 2023
12.4%
32.4%
UntrainndkgeniMeemryy TrainedkgentHemory
Ground Truth
Prediction
Ground Truth
Prediction
Notronpalic
Negale
0.0
0.2 0.4
0.6
0.8
Map Prediction Accuracy (loU)
Figure 4: Learning navigation improves map prediction. (Left) Accuracy (Intersection over Union) distributions (kernel density estimation) and means (dashed lines); TrainedAgentMemory has a higher mean than EntrrainedAgentMemrr with p-value < 10-6 (via Wilcoxon (1992) signed- rank test). (Right) Example ground truth and predicted occupancy maps for TrainedkgentHemory (corresponding to (A) and (B) loU points). Light grey is non-navigable and dark grey is navigable. The agent (light blue path) navigates from start (green) target (red). Notice that when the agent travels close to a wall, the decoder predicts another parallel to it, indicating a corridor.
probe tasks. This probe contains identical information at the start of an episode as the agent (i.e. no information). 2) UntrainedkgentMemmry Episodic memory generated by an untrained agent (i.e. with random parameters) as it is walked along the trajectory of the trained agent. This disentangles the agent's 's structure from its parameters; and tests whether simply being encoded by an LSTM (even one with random parameters) provides inductive bias towards building good environmental rep- resentations (Wieting & Kicla, 2019). We find no evidence for this bias inttrinnddAgenteemee performs better than AllZeryMemory (Fig. 3B, row 1 vs. 2). Furthermore, TrainedAgentMemon significantly outperforms both controls by +13 points SPL and +4 points Success (Fig. 3B, row 1 and 2). Taken together, these two results indicate that the ability to construct useful spatial representations of the environment from a trajectory is decidedly a learned behavior.
Next, we examine if there is any directional preference in the episodic memory constructed by the agent. Our claim is that even though the agent navigates from to T, if its memory indeed contains map-like spatial representations, should also support probes for the reverse task Second- Nav(T-S). Indeed, we find that TrainedAgentMemory probe performs the same (within margin of error) on both SecondNav(S->> the memory is equally useful in both directions. In Apx. C.2 we demonstrate that the probe removes excursions from the agent's 's path and takes shortcuts through previously unseen parts of the envi- ronment. Overall, these results provide compelling evidence that blind agents learn to build and use implicit map-like representations that enable shortcuts and reasoning about previously untraversed locations in the environment, solely through learning to navigate between two points.
and SecondNav(T-5S)) (Fig. 3B right column) indicating that
LEARNING NAVIGATION IMPROVES METRIC MAP DECODING
Next, we tackle the question 'Does the agent build episodic representations capable of decod- ing metric maps (occupancy grids) of the environment?" Formally, given the final representation (hr,, Cr ) we train a separate decoding network to predict an allocentric top-down occupancy grid (free-space vs not) of the environment. As with the probes, no gradients are propagated from the decoder to the agent's internal representation. We constrain the network to make predictions for location only if the agent reached within 2.5 meters of (refer Apx. A.3 for details). Note that since the agents are 'blind' predictions about any unvisited location require reasoning about unseen space. As before, we compare the internal representation produced by TrainedAgentMemory to internal representation produced by agent with random parameters, UntrainedAgentMMemory
Fig. 4 shows the distribution map-prediction accuracy, measured as interaction-over-ume with the true occupancy grid. We find that TrainedAgentMemory enables uniformly more accurate predictions than UntrainedAgentNemery show that the predictor is commonly able to make accurate predictions about unvisited locations, e,g. when the agent travels close to one wall, the decoder predicts another parallel to it, indicating a cor- ridor. These results show that the internal representation contains necessary information to decode accurate occupancy maps, even for unseen locations. We note that the environment structural priors also necessary prediction unseen locations. Thus agent memory is necessary but not sufficient.
(IoU)
32.5% vs 12.5% average IOU. The qualitative examples
7

---

Published as a conference paper at ICLR 2023
(A)
Excursion non-Excursion
(B)
Predicted
Visited Chance
0.4
0.3
Mon-Bounsion
25
Raladve
Excursion
0.2
0.1
40
60
Steps in the Past
Figure 5: (A) Excursion prediction example. Qualitative example of the previously loca- tion decoder making systematic errors. Blue represents the confidence of the decoder that the agent was previously at a given location; we can see that it is lower in the path interval marked in red (excursion) than the rest. (B) Remembrance of excursions. Performance broken down into three categories. -occexxursion' is all predictions where the current location of the agent and the predic- tion time step are not part of an excursions. 'Excursion' is when the prediction time step is part of an excursion. "Fxir' is when the prediction time step is part of the last 10% of the excursion. X-axis is the distance into the past and Y-axis is the relative error between the true and predicted locations.
In Apx. C.4, we conduct this analysis 'sighted' navigation agents (equipped with Depth camera and egomotion sensor). Perhaps counter-intuitively we do not find conclusive evidence that metric maps be decoded from the memory of sighted agents (despite their sensing suite being strict superset of blind agents). Our conjecture is that for higher-level strategies like map-building to emerge, the learning problem must not admit 'trivial' solutions such as the ones deep reinforcement learning is know to latch onto (Baker et al., 2020; Lehman et al., 2020; Kadian et al., 2020), We believe that the minimal perception system used in our work served create challenging learning problem, which in turn limited the possible 'trivial" solutions, thus inducing map- han-buildiing.
6 MAPPING Is AASK-DEPENDENT: AGENT FORGETS EXCURSIONS
Given that the agent is memory- memory-limited. it stands to reason that it might need to choose what informa- tion to preserve and what to 'forget'. To examine this, we attempt to decode the agent's s past positions from its memory. Formally, given internal state at time t, (h,, c,), the agent's 's location steps in to the past, Le. & k = f& (h,, Ct) + 8t, & E [1, 256). Given ground truth location 8t-k, evaluate the decoder via relative 1.2 error || lt=x|/||| /////|ss==>>>/// 8t (see Apx. A.4 for details). Qualitative analysis shows that the agent forgets excursions' i.e. excursions harder to decode (see Fig. 5a). To quantify this, we manually labelled excursions in 216 randomly sampled episodes in evaluation environments. Fig. 5b shows that excursions are harder to decode than non-excursions, indicating that the agent does indeed forget excursions. Interestingly. we find that the exit of the excursion is considerably easier to decode, indicating that the end of the excursion performs similar function to landmarks in animal and human navigation (Chan et al., 2012).
train network fiz(-) predict
In the appendix, we study several additional questions that could not be accommodated in the main paper. Apx. C.2 we further examine the probe's 's performance. In Apx. C.3 we examine predicting future agent locations. In Apx. C.5 we use agent's 's hidden state world model.
RELATED WORK
Spatial representations. Prior work has shown that LSTMs build grid-cell (O'keefe & Nadel, 1978) representations of an environment when trained for path integration within that environment (Banino al., 2018; Cueva & Wei, 2018: Sorscher al., 2020). In contrast, our work provides direct supervision for path integration, localization, or mapping. Banino et al. (2018) demonstrated that these maps aid in navigation by training navigation agent that utilizes this cognitive map. In contrast, we show that LSTMs trained for navigation learn to build spatial representations in novel environments. Whether or not I.STMs trained under this setting also utilize grid-cells is a question for future work. Bruce et al. (2018) demonstrated that LSTMs learn localization when trained for navigation in single environment. We show that they learn mapping when given location and trained in many environments. Dwivedi et al. (2022) examined what navigation agents learn about
We define excursion sub-path that approximately forms loop.
8

---

Published as a conference paper at ICLR 2023
their environments. We provided detailed account of emergent mapping in larger environments, over longer time horizons, and show the emergence of intelligent behavior and mapping in blind agents, which is not the focus of prior work.
Graves ct al. (2016) proposed a differentiable neural computer and showed that spatial representa- tions emerge from graph tasks and block puzzles. Huynh et al. (2020) proposed spatial memory architecture and show that a map-like representation emerges when trained for localization. We show that spatial representations emerge task-agnostic neural networks trained for navigation.
'Map-free' navigation agents. Learned agents that navigate without an explicit mapping module (called 'map-free'
variety of tasks (Savva et al., 2019; Wijmans et al., 2020; Kadian et al.. 2020; Chattopadhyay et al., 2021; Khandelwal et al., 2022: Partsey et al., 2022; Reed al., 2022). In this work, we do not provide any novel techniques nor make any experimental advancement in the efficacy of such (sighted) agents. However, we make two key findings. First, that blind agents are highly effective navigators for PointGoalNav, exhibit- ing similar efficacy as sighted agents. Second, we begin to explain how 'map-free" navigation agents perform their task: they build implicit maps in their memory, although the story is bit nuanced due to the results in Apx. C.4; we suspect this understanding might be extended in future work.
pixels-to-actions: have shown strong performance
8 OUTLOOK: LIMITATIONS, REPRODUCIBILITY
In this work, we have shown that 'blind' Al navigation agents agents with similar perception as blind mole rats are capable of performing goal-driven navigation to high degree of performance. We then showed that these Al navigation agents learn to build map-like representations (supporting the ability to take shortcuts, follow walls, and predict free-space and collisions) of their environ- ment solely through learning goal-driven navigation. Our agents and training regime have no added inductive bias towards map-building, be it explicit or implicit, implying that cognitive maps may be a natural solution to the inductive biases imposed by navigation by intelligent embodied agents, whether they be biological or artificial. In similar manner, convergent evolution (Kozmik et al., 2008), where two unrelated intelligent systems independently arrive at similar mechanisms, suggests that the mechanism is a natural response of having to adapt to the environment and the task.
Our results also provide an explanation of the surprising success of map-free neural network nav- igation agents by showing that these agents in fact learn to build map-like internal representations with no learning signal other than goal driven navigation. This result establish a link between how 'map-free' systems navigate with analytic mapping-and aantin---nd---nninnn techniques (Thrun et al., 2005; Institute, 1972; Ayache & Faugeras, 1988; Smith et al., 1990).
Our results and analyses also point towards future directions in Al navigation research. Specifically, imbuing AI navigation agents with explicit (e.g. architectural design) or implicit (e.g. training regime or auxiliary objectives) priors that bias agents towards learning an internal representation with the features found here may improve their performance. Further, it may better equip them to learn more challenging tasks such as rearrangement of an environment by moving objects (Batra et al., 2020).
We see several limitations and areas for future work. First, we examined ground-based navigation agents operating in digitizations of real houses. This limits the agent to a 2D manifold and induces strong structural priors on environment layout. As such, it is unclear how to a drone flying through a large forest. Second, we examined agents with a minimal perceptual system. In the supplementary text, we attempted to decode occupancy grids (metric maps) from Depth sensor equipped agents and did not find convincing evidence. Our conjecture is that for higher-level strategies like map-building to emerge, the learning problem must not admit 'trivial' solutions. We believe that the minimal perception system used in our work also served to create such a challenging learning problem. Third, our experiments do not study the effects of actuation noise, which is an important consideration in both robot navigation systems and path integration in biological systems. Fourth, we examine an implicit map-building mechanism (an LSTM), a similar set of experiments could be performed for agents with differentiable read/write map but no direct mapping supervision. Fifth, our agents only explore their environment for a short period of time (an episode) before their memory is reset. Animals and robots at deployment experience their environment for significantly longer periods of time. Finally, we do not provide a complete mechanistic account for how the agent learns build its map what else stores in its memory.
results generalize
9

---

Published as a conference paper at ICLR 2023
Reproducibility Statement: Implementation details of analyses provided in the appendix. Our work builds on datasets and code that are already open-sourced. Our analysis code will be open-sourced.
Acknowledgements:: We thank Abhishek Kadian for his help in implementing the first version of the SecondNav(T-SSS probe experiment. We thank Jitendra Malik for his feedback the draft and guidance. EW was supported in part by an ARCS fellowship. The Georgia Tech effort was supported in part by NSF, ONR YIP, and ARO PECASE. The Oregon State effort was supported in part by the DARPA Machine Common Sense program. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the U.S. Government, or any sponsor.
REFERENCES
Peter Anderson, Angel X. Chang. Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, and Amir Roshan Zamir. On evaluation of embodied navigation agents. CoRR, foss/1807.666 2018. URL http:::/aaxxv.org//aaee http//1887.00775.0 06757.
Reut Avni, Yael Tzvaigrach, and David Eilam. Exploration and navigation in the blind mole rat (spalax chrenbergi): global calibration as a primer of spatial representation. Journal of Experi- mental Biology, 211(17)2817-2826 2008.
Nicholas Ayache and Olivier D Faugeras. Building, registrating, and fusing noisy visual maps. The International Journal of Robotics Research, 7(6))45-65, 1988.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Andrea Banino, Caswell Barry, Benigno Uria, Charles Blundell, Timothy Lillicrap. Piotr Mirowski, Alexander Pritzel, Martin J. Chadwick, Thomas Degris, Joseph Modayil, Greg Wayne, Hubert Soyer, Fabio Viola, Brian Zhang, Ross Goroshin, Neil Rabinowitz, Razvan Pascanu, Charlie Beat- tic, Stig Petersen, Amir Sadik, Stephen Gaffney, Helen King, Koray Kavukeuoglu, Demis Hass- abis, Raia Hadsell, and Dharshan Kumaran. fector-based navigation using grid-like representa- tions in artificial agents. Nature, 557(7705):429 2018. doi: 10. 1010038/441186-0888-102222 URL https: org/10. 1038/s441 586-586660 018-0102-6.
Dhruv Batra, Angel Chang. Sonia Chernova, Andrew Davison, Jia Deng, Vladlen Koltun, Sergey Levine, Jitendra Malik, Igor Mordatch, Roozbeh Mottaghi, Manolis Savva, and Hao Su. Rear- rangement: challenge for embodied ai. In arXiv preprint arXiv:201 1.01975. 2020.
Jake Bruce, Niko Sünderhauf, Piotr Mirowski, Raia Hadsell, and Michael Milford. Learning deploy- able navigation policies at kilometer scale from a single traversal. Conference on Robot Learning (CoRL), 2018.
Edgar Chan, Oliver Baumann, Mark A Bellgrove, and Jason B Mattingley. From objects to land- marks: the function of visual location information in spatial navigation. Frontiers in psychology, 3:304, 2012.
Angel Chang, Angela Dai. Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. Matterport3d: Learning from rgb-d data in indoor environments. In International Conference on 31) Vision (3DV), 2017. License: http://kaldir. vc.in. tum. www.ddd/mttteeeeee ttee///atteeprrr//...... pf
Nicole Chapuis and Patricia Scardigli. Shortcut ability in hamsters (mesocricetus auratus): The role of environmental and kinesthetic information. Animal Learning & Behavior, 2153)255- 1993.
Prithvijit Chattopadhyay, Judy Hoffman, Roozbeh Mottaghi, and Ani Kembhavi. Robustnav: To- wards benchmarking robustness in embodied navigation. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
10

---

Published as a conference paper at ICLR 2023
Allen Cheung, Matthew Collett, Thomas S. Collett, Alex Dewar, Fred Dyer, Paul Graham, Michael Mangan, Ajay Narendra, Andrew Philippides, Wolfgang Stürzl, Barbara Webb, Antoine Wys- trach, and Jochen Zeil. Still no convincing evidence for cognitive map by honeybees. Pro- ceedings of the National Academy of Sciences, 11 F1144)):443966 2014. ISSN 0027-8424.
doi: 10.1073/paas. 1413581111. URL https: //w::///wwwww..w pww..pppsaaaa httmmaa.rrrgooeenn/////////////
Holk Cruse and Rüdiger Wehner. No need for cognitive map: Decentralized memory for in- sect navigation. PLOS Computational Biology, 7(3):1110, 03 2011. doi: 10. 10.1371/jouraal.po 1002009, URL http:://ooooooo/..///// 1371 journal pcbi. 1002009.
Christopher Cueva and Xue-Xin Wei. Emergence of grid-like representations by training recur- rent neural networks perform spatial localization. In Proceedings of the International Confer- ence on Learning Representations (ICLR), 2018. URL https: ttttp:://operreeee iew.. net/forum?id= B17JT0e0-.
Kshitij Dwivedi, Gemma Roig, Aniruddha Kembhavi, and Roozbeh Mottaghi. What do navigation agents learn about their environment? In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10276-10285, 2022.
Russell Epstein, E Z Patai, Joshua Julian, and Hugo Spiers. The cognitive map in humans: Spatial navigation and beyond. Nature Neuroscience, 10:1504-1513, 10 2017. doi: n..103//nn.6660
Charles R. Gallistel. Learning, development, and conceptual change. organization of learning.
The MIT Press, 1990.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training ima- genet in hour. CoRR, 01211706606677, 2017. URL http:://rxii...../ org/ aas/a/ss//// /176 02677.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using neural network with dynamic external memory. Nature, 538 (7626):471-76,, 2016.
Lee Harten, Amitay Katz, Aya Goldshtein, Michal Handel, and Yossi Yovel. The ontogeny of mammalian cognitive map in the real world. Science, 36966500):994-97, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
Peter Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, pp. 73-101. JSTOR, 1964.
Tri Huynh, Michael Maire, and Matthew R. Walter. Multigrid neural memory. In Proceedings of the International Conference on Machine Learning (ICML), pp. 4561-4571, PMLR, 2020.
Stanford Research Institute. Shakey: An experiment in robot planning and learning.. 1972.
loalè, M Nozzolini, and F Papi. Homing pigeons do extract directional information from olfactory stimuli. Behavioral Ecology and Sociobiology, 26(5):301-305, 1990.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the International Conference on Machine Learning (ICML), 2015.
Lucia Jacobs. The evolution the cognitive map. Brain, behavior and evolution, 62(2):128-11 2003.
11

---

Published as a conference paper at ICLR 2023
Abhishek Kadian, Joanne Truong, Aaron Gokaslan, Alexander Clegg, Erik Wijmans, Stefan Lee, Manolis Savva, Sonia Chernova, and Dhruv Batra. Are we making real progress simulated environments? measuring the sim2real gap in embodied visual navigation. In IEEE Robotics and Automation Letters (RA-L.), 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Apoorv Khandelwal, Luca Weihs, Roozbeh Mottaghi, and Aniruddha Kembhavi. Simple but effec- tive: Clip embeddings for embodied ai. In Proceedings of IEEE Conference on Computer Vision and Pultern Recognition (CVPR), pp. 14829-14838, 2022.
Tali Kimchi, Ariane S Etienne, and Joseph Terkel. A subterranean mammal uses the magnetic compass for path integration. Proceedings of the National Academy of Sciences, 101(4):1105- 1109, 2004.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
Dmitry Kobak and Philipp Berens. The art of using t-sne for single-cell transcriptomics. Nature communications, 10(1):1-14, 2019.
Zbynek Kozmik, Jana Ruzickova, Kristyna Jonasova, Yoshifumi Matsumoto, Pavel Vopalensky, Iryna Kozmikova, Hynek Stmad, Shoji Kawamura, Joram Piatigorsky, Vaclav Paces, et al. As- sembly the cnidarian camera-type eye from vertebrate-like components. Proceedings of the National Academy of Sciences, 105(26):8989-89)) 8993, 2008.
Joel Lehman, Jeff Clune, Dusan Misevic, Christoph Adami, Lee Altenberg, Julie Beaulieu, Peter J Bentley, Samuel Bernard, Guillaume Beslon, David M Bryson, et al. The surprising creativity of digital evolution: A collection of aneedotes from the evolutionary computation and artificial life research communities. Artificial Life, 26(2):774-366, 2020.
Tsung-Yi Yin Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. Proceedings of IEEE International Conference on Computer Vision (ICCV), pp. 2988, 2017.
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordconv solution. In Advances in Neural Information Processing Systems (NeurIPS), pp. 9605-9616, 2018.
Ronald Mathias Lockley. Animal navigation. Pan Books, 1967.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of the International Conference Learning Representations (ICLR), 2019.
Vladimir J Lumelsky and Alexander A Stepanov. Path-planning strategies for point mobile au- tomaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, 2(1-4):403-430, 1987.
Hans Maaswinkel and Ian Q Whishaw. Homing with locale, taxon, and dead reckoning strategies by foraging rats: sensory hierarchy in spatial navigation. Behavioural brain research, 99(2): 143-152, 1999.
Emil W Menzel. Chimpanzee spatial memory organization. Science, 182(4115):943 945, 1973.
Martin Müller and Rüdiger Wehner. Path integration in desert ants, cataglyphis fortis. Proceedings of the National Academy of Sciences, 85(14):5287-5290 1988.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the International Conference on Machine Learning (ICML), 2010.
John O' O'keefe and Lynn Nadel. The hippocampus as a cognitive map. Oxford: Clarendon Press, 1978.
12

---

Ben Sorscher, Gabriel C. Mel, Samuel A. Ocko, Lisa Giocomo, and Surya Ganguli. A uni- fied theory for the computational and mechanistic origins of grid cells. In bioRxiv preprint (ttp:::22220.1222.4222.222 Published as a conference paper at ICLR 2023
Ruslan Partsey, Erik Wijmans, Naoki Yokoyama, Oles Dobosevych, Dhruv Batra, and Oleksandr Maksymets. Is mapping necessary for realistic pointgoal navigation? Proceedings of IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 17232-17244 2022.
R. Peters. Cognitive maps in wolves and men. Environmental design research, 2:247-253, 1976.
Santhosh K Ramakrishnan, Aaron Gokaslan, Erik Wijmans, Oleksandr Maksymets. Alex Clegg, John Turner, Eric Undersander, Wojciech Galuba, Andrew Westbury, Angel X Chang, et al. Habitat-matterport 3d dataset (hm3d): 1000 large-scale 3d environments for embodied ai. Neural Information Processing Systems Benchmarks and Datasets, 2021.
Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gomez Colmenarejo, Alexander Novikov, Gabriel Barth-Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, et al. A generalist agent. arXiv preprint arXiv:2255.66177 2022.
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied AI Research. In Proceedings of IEFE International Conference on Computer Vision (ICCV), 2019.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, 0ass/177.006447. 2017.
Randall Smith, Matthew Self, and Peter Cheeseman. Estimating uncertain spatial relationships in robotics. In Autonomous robot vehicles, pp. 167-193. Springer, 1990.
2020. doi: 00.1101//220.12.29..222
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, lly Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research (JMLR), 15(1):1929-199 1958. 2014.
Julian Straub, Thomas Whelan, Lingni Ma. Yufan Chen, Erik Wijmans, Simon Green, Jakob J. Engel, Raul Mur-Artal, Carl Ren, Shobhit Verma, Anton Clarkson, Mingfei Yan, Brian Budge, Yajie Yan, Xiaqing Pan, June Yon, Yuyang Zou, Kimberly Leon, Nigel Carter, Jesus Briales, Tyler Gillingham, Elias Mueggler, Luis Pesqueira, Manolis Savva, Dhruv Batra, Hauke M. Strasdat, Renzo De Nardi, Michael Goesele, Steven Lovegrove, and Richard A. Newcombe. The replica dataset: A digital replica of indoor spaces. CoRR, abs/1906.05799 2019. URL /tatp://axivv. org/abs/11 aa9aa////..... 1906. 05797.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 1992.
Andrew Szot, Alex Clegg, Eric Undersander, Erik Wijmans, Yili Zhao, John Turner, Noah Maestre, Mustafa Mukadam, Devendra Chaplot, Oleksandr Maksymets, Aaron Gokaslan, Vladimir Von- drus, Sameer Dharur, Franziska Meier, Wojciech Galuba, Angel Chang, Zsolt Kira, Vladlen Koltun, Jitendra Malik, Manolis Savva, and Dhruv Batra. Habitat 2.0: Training home assis- tants to rearrange their habitat. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic robotics (intelligent robotics and autonomous agents), 2005.
Sivan Toledo, David Shohami, Ingo Schiffner, Emmanuel Lourie, Yotam Orchan, Yoav Bartan, and Ran Nathan. Cognitive baseb navigation in wild bats revealed by new high-throughput tracking system. Science, 369(6500):188 188-1993,18889, 2020.
Edward C. Tolman. Cognitive maps in rats and men. Psychological Review, 55(4):189-22) 1948. doi: 10.1037/h006166.
13

---

Published as a conference paper at ICLR 2023
Jonathan Tompson, Ross Goroshin, Arjun Jain, Yann LeCun, and Christoph Bregler. Efficient object localization using convolutional networks. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 948-656,7 2015.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne, Journal of machine learning research, 9(11), 2008.
Karl Von Frisch. The dance language and orientation of bees. Harvard University Press, 1967.
John Wieting and Douwe Kiela. No training required: Exploring random encoders for sentence clas- sification. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Erik Wijmans, Abhishek Kadian, Ari Morcos, Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. DD-PPO: Learning near-perfect pointgoal navigators from 2.5 billion frames. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Frank Wilcoxon. Individual comparisons by ranking methods. Breakthroughs in statistics, pp- 196-202. Springer, 1992.
Fei Xia, Amir R Zamir, Zhiyang He, Alexander Sax, Jitendra Malik, and Silvio Savarese. Gibson env: Real-world perception for embodied agents. In Proceedings of IEEE Conference Com- puter Vision and Pattern Recognition (CVPR), 2018. License: https: /ttts://storage.... attps://storgge_goooleeeis googleapis. com/gibson_mat
04-18 pdf.
A METHODS AND MATERIALS
A.1 POINTGOAL NAVIGATION TRAINING
Task. PointGoal Navigation, the agent is tasked with navigating to point specified relative to its initial location, i.e an input of (ōx, ōy) corresponds to going dr meters forward and by meters to the right. The agent succeeds if it predicts the stop action within 0.2 meters the specified point. The agent has access to 4 low-level actions move_ move_forward (0.25 meters), turn_left (10%), turn_right (109), and stop. There is no noise in the agent's 's actuations.
The agent has access to solely an idealized GPS+Compass sensor that provides it heading and position relative to the starting orientation and location at each time step. There is no noise in the agent's sensors.
Sensors.
Architecture. The agent is parameterized by a 3-layer LSTM (Hochreiter & Schmidhuber, 1997) with 512-d hidden dimension. At each time-step, the agent receives observations g (the location of the goal relative to start), GPS (its current position relative to start), and compass (its current heading relative start). We also explicitly give the agent indicator of if it is close to goal in the form of min(Ilg - GPS]], 0.5) as we find the agent does not learn robust stopping logic otherwise. All inputs are projected to 32-d using separated fully-connected layers. These are then concatenated with a learned 32-d embedding of the previous action taken to form a 160-d input that is then given the LSTM. The output of the LSTM is then processed by fully-connected layer to produce a softmax distribution of the action space and an estimate of the value function.
Training Data. We construct our training data based on the Gibson (Xia et al., 2018) and Matter- port3D dataset (Chang et al., 2017). We training on 411 scenes from Gibson and 72 from Matter- port3D.
Training Procedure. We train our agents using Proximal Policy Optimization (PPO) (Schulman et al., 2017) with Generalized Advantage Estimation (GAE) (Schulman al., 2016). We use Decen- tralized Distributed PPO (DD-PPO) (Wijmans et al., 2020) to train on 16 GPUs. Each GPU/worker collects 256 steps of experience from 16 agents (each in different scenes) and then performs epochs of PPO with 2 mini-batch per epoch. We use the Adam optimize (Kingma & Ba, 2015) with a learning rate 2.5 x 10 10-4, We set the discount factor y to 0.99, the PPO clip to 0.2, and the GAE hyper-parameter to 0.95. We train until convergence (around 2 billion steps of experience).
14

---

Published as a conference paper at ICLR 2023
At every timestep. t, the agent is in state St and takes action dg. and transitions state S1+- It receives shaped reward in the form:
2.5 Success
if de is Stop
Tt
(1)
A goo dis St+1)
Otherwise
where A dist (Sc, Se41 is the change in geodesic (shortest path) distance to goal between & and 814-1 and x= is a slack penalty encouraging shorter episodes.
Evaluation Procedure. We evaluate the agent in the 18 scenes from the Matterport3D test set. We use the episodes from Savva al. (Savva et al., 2019), which consist of 56 episodes per scene (1008 in total). Episode range in distance from 1.2 to 30 meters. The ratio of geodesic distance to euclidean distance between start and goal is restricted
be greater than equal to 1.1, ensuring that episodes are not simple straight lines. Note that reward is not available during evaluation.
The agent is evaluated under two metrics, Success, whether or not the agent called the stop action with 0.2 meters of the goal and Success weighted by normalized inverse Path Length (SPL) (An- derson et al., 2018). SPL calculated as follows: given the agent's 's path : 87) and the initial geodesic distance to goal de for episode i, we first compute the length of the agent's 's path
4
St S1-1/12
(2)
then SPL for episode i
SPL; Success;
(3)
min inin(d,) 4)
We then report SPL as the average of SPL; across all episodes.
A.2 PROBE TRAINING
Task. The probe task is either navigate from start goal again (SecondNav(S T)) navigate from goal to start (SecondNav(T (-))). For SecondNav(S-<77) the probe initialized at the starting location but with the agent's final heading. For SecondNav(T-SS) the probe is initialized with the agent's 's final heading and position. In both cases, the probe and the agent share the same coordinate system- - i.e. in SecondNav the the final GPS and Compass readings for the agent. When the agent does not successfully reach the goal, the probe task is necessarily undefined and we do not instantiate probe.
the initial GPS and Compass readings for the probe identical
Sensors, Architecture, Training Procedure, Training Data. The probe uses the same sensor suite, architecture, training procedure, and training data as the agent, described in Section A.
Note that no gradients (or rewards) follow from probe to agent. From the agent's perspective, the probe does not exist. From the probe's perspective, the agent provides dataset of initial locations (or goals) and initial hidden states.
Evaluation Procedure. We evaluate the probe in similar manner the agent except that any episode which the agent is unable to complete (5%) is removed due to the probe task being undefined if the agent is unable to complete the task. The agent reaches the goal 95% the time, thus only 50 out of 1008 possible probe evaluation episodes are invalidated. The control probe type accounts for this. We ignore the agent's 's trajectory when computing SPL for the probe.
A.3 OCCUPANCY MAP DECODING
Task. We train a decoding network to predict the top-down occupancy map of the environment from the final internal state of the agent c+). We limit the decoder to only predict within 2.5 meters of any location the agent visited.
Architecture. The map-decoder is constructed follows: First the internal state (h,, c₂) is concate- nated into 512 x 6-d vector. The vector is then passed to a 2-layer MLP with a hidden dimension of 512-d that produces a 4608-d vector. This 4608-d vector is then reshaped into [128, 6, 6] feature- map. The feature map is processed by a series of Coordinate Convolution (CoordConv) (Liu et al., 2018) Coordinate Up-Convolution (CoordUpConv) layers decrease the channel-depth and increase spatial resolution to [16, 96, 96]. Specifically, after an initial CoordConv with an output channel- depth of 128, we series of 4 Coorddlcoonv-CorrcCooo layers where each Cuonn doubles
15

---

Published as a conference paper at ICLR 2023
the spatial dimensions (quadruples spatial resolution) and each CoordConv reduces -hannel-depth by half. We then use a final 1x1 Ix1-Convolution to create a [2, 96, 96] tensor representing the non- normalized log- probabilities of whether or not given location is navigable or not.
Each CoordConv has kernel size 3, padding I, and stride 1. CoordUpCony has kernel size 3, padding 0, and stride 2. Before all CoordConv and CoordUpConv, we use 2D Dropout (Srivastava al., 201 4; Tompson et al., 2015) with a zero-out probability of 0.05. We use Batch Normalization layers (loffe & Szegedy, 2015) and the ReLU activation function (Nair & Hinton, 2010) after all layers except the terminal layer.
Training Data. We construct our training data by having trained agent perform episodes of Point- Goal navigation on the training dataset. Note that while evaluation is done utilizing the final hidden state, we construct our training dataset by taking 30 time steps (evenly spaced) from the trajectory and ensuring the final step is included.
Training Procedure. We train on 8 GPUs with batch size of 128 per GPU (total batch size of 1024). We use the AdamW optimizer (Kingma & Ba, 2015; Loshchilov & Hutter, 2019) with an initial learning rate of 10-3 and linearly scale the learning rate to 1.6 x 10 over the first 5 epochs (Goyal et al., 2017) and use weight-decay of 10-5, We use the validation dataset to perform early-stopping. We use Focal Loss (Lin et al., 2017) (a weighted version of Cross Entropy Loss) with y = 2.0, CNooNavigablee = 0.75, and ('Navigable 0.25 to handle the class imbalance.
Evaluation Data and Procedure. We construct our evaluation data using the validation dataset. Note that the scenes in evaluation are novel to both the agent and the decoder. We evaluate the predicted occupancy map from the final hidden state/final time step. We collect a total of 5,000 episodes.
A.4 PAST AND FUTURE POSITION PREDICTION
Task. We train decoder to predict the change in agent location given the internal state time t (h, c.). Specifically, let &, be the agent's position at time t where the coordinate system is defined by the agent's starting location (i.e. 80 0), and 8 be its position l steps into the future/past, then the decoder is trained to model S(h,, c,)) Sttk - 8t-
Architecture. The decoder is a 3-yyeer MIP that produces 3 dimensional output with hidden sizes of 256 and 128. We use Batch Normalization (loffe & Szegedy, 2015) and the ReLU activation function (Nair & Hinton, 2010) after all layers except the last.
Training Data. The training data is collected from executing a trained agent on episodes from the training set. For each episode, we collect all possible pairs of st, Sttk for a given value of k.
Training Procedure. We use the Adam W optimizer (Kingma & Ba, 2015; Loshchilov & Hutter, 2019) with a learning rate of 10-3, weight decay of 10 4, and a batch size of 256. We use Smooth L1 Loss/Huber Loss (Huber, 1964) between the ground-truth change in position and the predicted change in position. We use the validation set to perform early stopping.
Evaluation Procedure. We evaluate the trained decoded on held-out scenes. Note that the held-out scenes are novel both to the agent and the decoder.
Visualization of Predictions. For visualization the predictions of past vitiation, we found it easier to train second decoder that predicts all locations the agent visited previously on a 2D top down map given the internal state (h, c.). This decoder shares the exact same architecture and train- ing procedure as the occupancy grid decoder. The decoder removes the temporal aspect from the prediction, so it is ill-suited for any time-dependent analysis, but produces clearer visualizations.
Excursion Calibrated Analysis. To perform the excursions forgetting analysis, we use the excur- sion labeled episodes. We marked the end of the excursion the last 10% of the steps that are part of the excursion. For given point in time f, we classify that point into one of [Non-Exoo -xon-Exxursiin, Excursion, Exit). We then examine how well this point is remembered by calculating the error of predicting the point from t + k. i.e. how well can t be predicted when is i steps into the past. When is part of an excursions (both the excursion and the exit) we limit t + the same excursion or not part of an excursion. When is not part of an excursion, t + k must also not be part of an excursion nor can there be any excursion in the range [t, t + is).
either be part of
16

---

Published as a conference paper at ICLR 2023
A.5 COLLISION PREDICTION LINEAR PROBE
Task. The task of this probe is to predict of the previous action taken lead to a collision given the current hidden state. Specifically seeks to learn a function Collided, = f((,, c+)) where (h, ct) is the internal state at time & and Collided, is whether or not the previous action, Qt-1 lead to collision.
The architecture is logistic classifier that takes the concatentation of the hidden state and produces log probability of Collided,.
Architecture.
Training Data. We construct our training data by having a trained agent perform episodes of Point- Goal navigation on the training set. We collect a total of 10 million samples and then randomly select million for training. We then normalize each dimension independently by computing mean and standard deviation and then subtract mean and divide by standard deviation. This ensures that all dimensions have the same average magnitude.
Training Procedure. We training on GPU with a batch size of 256. We use the Adam opti- mizer (Kingma & Ba, 2015) with a learning rate of 5 10 We train for 20 epochs.
Evaluation Data and Procedure. We construct our evaluation data using the same procedure as the training data, but the validation dataset and collect 200,00 samples (which is then subsampled to 20,000).
Important Dimension Selection. To select which dimensions are important for predicting collsions, we re-train our probe with various & penalties. We sweep from 0 to 1000 and then select the penalty that results in the lowest number of significant dimensions without substantially reducing accuracy. We determine the number of significant dimensions by finding the smallest number of dimensions we can keep while maintaining 99% of the full network's performance. This is achieved by sorting the dimensions by the & norm of their weight in descending order and adding dimensions (in sorted order) until 999% of the full network's 's performance is achieved.
The t-SNE manifold is computed using 20,000 samples. This is then randomly subsampled to 1,500 for visualization. We use the techniques proposed in Kobak & Berens (2019) to set our t-SNE parameters.
A.6 DATA AND MATERIALS AVAILABILITY
The Gibson (Xia et al., 2018) and Matterport3D (Chang et al., 2017) datasets can be acquired from their respective distributors. Habitat (Savva et al., 2019) is open source. The environment in the image in Fig. 3 is from the Replica Dataset (Straub et al., 2019).
B ADDITIONAL DISCUSSIONS
B.I RELATIONSHIP TO COGNITIVE MAPS
Throughout the text, we use the term 'map' to mean spatial representation that supports intelligent behaviors like taking shortcuts. Whether or not this term is distinct from the specific concept of 'cognitive map" is debated.
Cognitive maps, as defined by O'keefe & Nadel (1978), imply a set of properties and are generally attached to a specific mechanism. The existence of a cognitive map requires that the agent be able to reach a desired goal in the environment from any starting location without being given that starting location, i.e. be able to navigate against map. Further, cognitive maps refer to a specific mechanism - place cells and grid cells being present in the hippocampus. Other works have also studied 'cognitive maps' and not put such restrictions its definition (Gallistel, 1990; Tolman, 1948), however these broader definitions have been debated (Jacobs, 2003).
Our work shows that the spatial information contained within the agent's hidden state enables map- like properties a secondary agent to take shortcuts through previously unexplored free space and supports the decoding of metric map. However, these do not fully cover the propricties of O'keefe & Nadel (1978)'s 's definition nor do we make a mechanistic claim about how this information is stored in the neural network, though do find the emergence of collision-detectioon neurons.
17

---

Published as a conference paper at ICLR 2023
C ADDITIONAL EXPERIMENTS
C.I BLIND SHORTEST PATH NAVIGATION WITH TRUE STATE
In the main text, we posited that blind agents learn wall-following as this an effective strategy for blind navigation in wnknown environments. We posit that this is because the agent does not have ac- cess to true state (it does not know the current environment nor where is in global coordinates). In this experiment we show that blind agents learn to take shortest paths, as opposed to wall-following, when trained in a single environment (implicitly informing the agent of the current environment) and uses the global coordinate system."
We use an identical agent architecture and training procedure as outline for PointGoal navigation training in the Materials and Methods with two differences: 1) A single training and test environment and 2) usage of the global coordinates within the environment for both goal specific and the agent's s GPS+Compan sensor. We perform this experiment on 3 scenes, from the Gibson val dataset and 2 from Matterport3D val dataset. The average SPI. during training is 99 showing that the blind agent learns shortest path navigation not wall-following. Figure A6 shows examples of an agent trained in a single scene with global coordinates and an agent trained in many scenes with episodic coordinates.
These two settings, i) where the agent uses an episodic coordinate system and navigates in unknown environments, and ii) where the agent uses global coordinates and navigates in known environment can be seen as the difference between a partially observable Markov decision process (POMDP) and a Markov decision process. the POMDP case, the agent must learn a generalizable policy while it can overfit in the MDP case.
C.2 FURTHER ANALYSIS OF THE PROBE'S PERFORMANCE
In the main text, we showed that the probe is indeed much more efficient than the agent, but how is this gain achieved? Our hypothesis is that the probe improves upon the agent's path by taking shortcuts and eliminating excursions (representing an "out and back'). We define an excursion as sub-path that approximately forms a loop. To quantify excursions, we manually annotate excursions in 216 randomly sampled episodes in evaluation environments. Of the labeled episodes, 62% have a least excursion. On average, an episode has 0.95 excursions, and excursions have an average length of 101 steps (corresponding to 8.23 meters). Since excursions represent unnecessary portions of the trajectory, this indicates that the probe should able improve upon the agent's path by removing these excursions.
We quantify this excursion removal via the normalized Chamfer distance between the agent's path and the probe's path. Formally, given the agent's 's path Agent=[s/ ST
(ageutty and the probe's
path Probe= [s] (mmbe)
(prahe)) where R is point in the environment: N
N
PathDiff(Agent, Probe) = N 1=1
min GeoDist(s (agent) I9ST
(probe)).
(4)
where GeoDist(:;.) indicates the geodesic distance (shortest traverseable path-length).
Note that Chamfer distance is not symmetric. PathDif((Probe, Agent) measures the average distance of point on the probe path s (pmhhe from the closest point on the agent path. A large PathDiff(Probe, Agent) indicates that the probe travels through novel parts of the environments (compared to the agent). Conversely, PathDiff(Agent, Probe) measures the average distance of a point on the agent path 8 (ageni) from the closest point the probe path. A large DPattDiif(AAgen,, Probe) PathD- iff(Probe, Agent)) gap indicates that agent path contains excursions while the probe does not; thus, we refer to this gap as Excursion Removal. To visually understand why this is the case, consider the example agent and probe paths in Fig. A7. Point (C) lies on an excursion the agent path. It contributes term to PathDiff(Agent, Probe) but not to PathDiff(Probe, Agent) because (D) is closer to (E) than (C).
'Reaall that in the episodic coordinate system the origin defined by the agent's starting position and orientation. In the global coordinate system the origin is an arbitrary but consistent location (we simply use the origin for given scene defined in the dataset). Thus in the global coordinate system the goal is specified as 'Go to (z, y) where and are specified in the glohal coordinate system, not with respect to the agent's current location.
18

---

Published as a conference paper at ICLR 2023
On both SecondNav(S--1) and SecondNav(T--S), we find that the efficiency of probe in- creases, Excursion Removal also increases (Table A2, row vs. 2, 2 vs. 3), confirming that the TrainedAgentMemorry probe is more efficient because it removes excursions.
We next consider if the TrainedkkentMemorry probe also travels through previously unexplored space in addition to removing excursions. To quantify this, report PathDiff(Probe, Agent) on episodes where agent SPL is less than average (less than 62.9%).² If probes take the same path as the agent, we would expect this metric to be zero. If, however, probes travel through previously unexplored space to minimize travel distance, we would expect this metric to be significantly non- zero. Indeed. on SecondNav(S--IT we find the TrainedAgentWemory probe 0.32 meters away on average from the closest point on the agent's 's path (99% empirical bootstrap of the mean gives a range of (0.299, 0.341)). See Fig. A7 for visual example. On SecondNav(T SS); this effect is slightly more pronounced, the TrainedAggntMemorr probe is 0.55 meters away on average (99% empirical bootstrap of the mean gives a range of (0.52, 0.588)). Taken holistically, these results show that the probe is both more efficient than the agent and consistently travels through new parts of the environment (that the agent did not travel through). Thus, the spatial representation in the agent's memory is not simply 'literal' episodic summarization, but also contains anticipatory inferences about previously unexplored spaces being navigable (e.g. traveling along the hypotenuses instead of sides of a room).
In the text above we reported free space inference only on episodes where the agent gets an SPL. bellow average. In Fig. A12 we provide a plot of Free Space Inference Agent SPL to show the impact of other cutoff' points. In Fig. A13 we also provide a similar plot of Excursion Removal vs. Agent SPL. In both cases, as agent SPL increase, the probe is able to infer less free space or remove less excursions.
C.3 FUTURE VISITATION PREDICTION
In the main text we examined what types of systematic errors are made when decoding past agent locations, here we provide addition analysis and look at predicting future observations as that will reveal if there are any idiosyncrasies in what can be predicted about future vs. what will happen in the future.
Given ground truth location &++ we evaluate the decoder via i) absolute L2 error || Se+ & and ii) relative 1.2 error || - * train a second set of decoders where instead of using the correct internal state (h,, c.) as the input, we randomly select an internal state from different trajectory. This will evaluate if there are any inherent biases in the task.
s+||- To determine baseline (or chance) performance,
In Fig. A8, we find that the decoder is able to accurately predict where the agent has been, even for long time horizons - e.g. 100 time steps the past, relative error is 0.55 and absolute error is 1.0m, compared to relative eтror of 1.0 and absolute error of 3.2m for the chance baseline prediction. For short time horizons the decoder also able to accurately predict where the agent will be in the future e.g. at 10 time steps into the future, relative and absolute error are below chance. Interestingly, we see that for longer range future predictions, the decoder is worse than chance in relative error but on- par in absolute error. This apparent contradiction arises due to the decoders making (relatively) large systematic errors when the agent backtracks. In order for the decoder to predict backtracking, the agent would need to already know its future trajectory will be sub-optimal (i.e. lead to backtracking) but still take that trajectory. This is in contradiction with the objective the agent is trained for, to reach the goal as quickly possible, and thus the agent would not take given path if it knew it would lead to backtracking.
C.4 EXTENSION TO SIGHTED NAVIGATION AGENTS
In the main text we analyzed how 'blind' agents, those with limited perceptual systems, utilize their memory and found evidence that they build cognitive maps. Here, we extend our analysis to agents with rich perceptual systems, those equipped with Depth camera and an egomotion sensor. Our primary experimental paradigm relies on showing that a probe is able to take shortcuts when given the agent's 's memory. This experimental paradigm relies on the probe being able to take shorter
We restrict to subset where the agent has relatively low SPL to improve dynamic range. When the agent has high SPI., there won't 't be excursions to remove and this metric will naturally be low. In the supplementary text we provide plots of this metric vs. agent SPI..
19

---

Published as a conference paper at ICLR 2023
path than the agent. Navigation agents with vision can perform PointNav pear-perfectly (Wijmans et al., 2020) and thus there isn't 't' room for improving. rendering this experiment infeasible. As a supplement to this experiment, also show that metric map (top-down occupancy grid) can be decoded from the agents memory. This procedure can also be applied to sighted agents.
We use the ResNet50 (He et al., 2016) Gibson 2plus (Xia et al., 2018) pre-train model from Wijmans et al. (Wijmans et al., 2020) and train an occupancy grid decoder using the same procedure as in the main text. Note however we utilize only Gibson for training and the Gibson validation scenes as held-out data instead of Matterport3D as this agent was only trained on Gibson. As before, we compare performance from TrainedAgentHemory with UntrainedAgenttemoryy
We find mixed results. When measuring performance with crarsection-ove--Unne (IoU), untraineekkenttemory outperforms TrainedkgentMemorg (40.1% vs. 42.9%). However, when measuring performance with average class balanced accuracy, TrainedAgentMemory outperforms untrainedAgentMeorry (61.8% vs. 53.1%). Fig. A9 and Fig. A10 show the corresponding distri- bution plots.
Overall, this experiment does not provide convincing evidence either way to whether vision- equipped agents build metric maps in their memory. However, it does show that vision-equipped agents, if they do maintain a map of their environment, create one that is considerably more chal- lenging to decode. Further, note this does not necessarily imply similarly mixed results to whether or not vision agents maintain still spatial but sparser representation, such as a topological graph, their rich perception can fill in the details in the moment.
C.5 NAVIGATION FROM MEMORY ALONE
In the main text we showed that agents learn to build map-like representations. A map-like repre- sentation of the environment, should, to degree, support navigation with no external information, ie. by dead reckoning. Given that the actions are deterministic, the probe should be able to perform either task without external inputs and only the agent's internal representation and the previously taken action. The localization performed by the probe in this setting is similar to path integration, however, it must also be able to handle any collisions that occur when navigating.
Fig. All shows performance vs. episode length for SecondNav(S-22 (T) and SecondNav There are two primary trends. For short navigation episodes (55m). the agent is able to complete the task often. We also find that under this setting, SecondNav(T-SS) is an casier task. This is due to the information conveyed to the probe by its initial heading. In SecondNav(T S), the probe can make progress by simply turning around and going forward, while in (avonnNav((S-TT)) the final heading of the agent is not informative of which way the probe should navigate initially. Overall, these results show that the representation built by the agent is sufficient to navigate short distances with no external information.
Experiment procedure. This experiment mirrors the probe experiment described in methods and materials with three differences: 1) The input from the GPS+Compass sensor is zero-ed out. 2) The change in distance to goal shaping in the reward is normalized by the distance from initial state to goal. We find that the prediction of the value function suffers considerably otherwise. 3) An additional reward signal as to whether or not the last action taken decreased the angle between the probe's 's current heading and the direction along the shortest path to goal is added. We find the probe has challenges learning to turn around on the SecondNav(T-S5) task otherwise (as it almost always starts facing 180 in the wrong direction).
Let hg be the heading along the shortest path to goal from the probe's 's current position 8t, hy be the probe's 's current heading, then AngularDistance(((" hhe) is the error in the probe's heading. The full reward for this probe is then
2.5 - Success
if az is Stop
- -10.0 A A dindiiiss, 8141) /GeoDiettsssss....
(1( Gr. St+1)
(5)
-0.25 Teeding (8t, 8(+1)
Otherwise
20

---

Published as a conference paper at ICLR 2023
C.6 MEMORY LENGTH
The method presented in the main text to examine memory length is post-hoc analysis performed on the 'blind" PointGoal Navigation agents and thus the agent is operating out-of-distribution. From the agent's view, it is still performing valid PointGoal navigation episode, just with different starting location, but the agent may not have taken the same sequence of actions started from that location. While we would still expect performance to stature with small k if the memory length indeed short, imprecise with measuring the exact memory length of the agent and does not answer what memory budget is required to perform the task.
Here we examined training agents with fixed memory length LSTM. Fig. A14 shows similar trends to those described in the main paper performance increases as the memory budget increases however performance is higher when the agent is trained for a given memory budget. Due to the increased compute needed train the model (e.g. training model with a memory length of 128 is 128x more computationally costly), we where unable to train for a memory budget longer than 256.
We also note the non monotonicity in Fig. A14, We conjecture that this is consequence of inducing the negative effects of large-batch optimization (Keskar et al., 2017) training with a memory budget of l effectively increases the batch size by factor of k. Keeping the batch size constant has its drawbacks; reducing the number of parallel environments will harm data diversity and result in overfitting while reducing the rollout length increases the bias of the return estimate and makes credit assignment harder. Thus we kept number of environments and rollout length constant.
D SUPPLEMENTARY VIDEOS
Movies S1-3 Videos showing blind agent navigation with the location of the hidden state in the collision t-SNE space. Notice that the hidden state stays within cluster throughout series of actions.
21

---

Published as a conference paper at ICLR 2023
SecondNav(S-1 +
SecondNav(T-SS)
Probe Type
Excursion Removal
Excursion Removal
1 AllZeroMemory
=0011
0.21 +0.04
2 UntrriinedkgentWeeory
0.23
0.25=0.009
TrainedAgentMemory
0.52+00014
0.51
Table A2: Excursion removal result of our trained probe agent under three configurations ini- tialized with an empty representation (AllZeroMemory), representation of random agent walked along the trained agent's 's path UnntrainedAgetMMemryy and the final representation of the trained agent (TrainedAgentWemorry) 95% confidence interval reported over 5 agent-probe pairs.
Novigable
Not Novigable
Puth
Agant Puth
Figure A6: True state trajectory comparison. Example trajectories of agent with true (trained for a specific environment and using global coordinates), green line, compared to an agent trained for many environments and using episodic coordinates, blue line. The later is what examine in this work. Notice that the agent with true state take shortest path trajectories while the agent without true state instead exhibits strong wall-following behavior.
22

---

Published as a conference paper at ICLR 2023
Agent Path
Probe Path
Excursion Removal
PathDif((AP) PathDif((BA)
A
E
Free Space Inference
PathDif((PA)
Figure A7: Two categories of probe shorteut. 'Excursion Removal' is when the probe removes excursions from the agent's path. The dashed line shows the distance between the points in the excursion and the closest point in the probe's path. 'Free Space Inference' occurs when the probe travels through previously unvisited locations in the environments. The dashed lines show the dis- tance between any points in the probe's path and the closest point in the agent's path.
Absolute L2 Error
Relative L2 Error
2.0
1.5
Actual Chance
0.5
-200
-100
100
200
-200
-100
0
100
200
Time Offset
Time Offset
Figure A8: Past and future prediction. Performance of decoders trained to predict where the agent was in the past/will be in the future. On the x-axis is how far into the past future the decoder is predicting (positive values are future predictions and negative values are past predictions). The y-axis is either absolute or relative L2 error between the predicted location of the agent and the true location.
23

---

Published as a conference paper at ICLR 2023
UntrainedAgentMemory
TrainedAgentMemory
0.0
0.2
0.4
0.6
0.8
1.0
Map Prediction Accuracy (loU)
Figure A9: Map prediction accuracy (Intersection over Union) for Depth sensor equipped agents.
UntrainedAgentMemorr
TrainedAgentMemory
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Map Prediction Accuracy (Class Balanced Accuracy)
Figure A10: Map prediction accuracy (class balanced accuracy) for Depth sensor equipped agents.
SecondNav(S TT)
SecondNav(T - S)
Performance LSPL; Higher better)
60
50
30
20
0
5
10 15
20
25
30
20 GeodesiicDistanceeSSartt Goal)
10
15
30
GeodesicDDietnneeeSSattt Goal)
Figure A11: Memory-only probe performance. Performance (in SPL; higher better) as a func- tion of geodesic distance from start to goal for the TrainedAgentMemory probe without inputs on SecondNav(S and SecondNav(T-25) More information can found under the 'Navigation from memory alone" header.
24

---

Published as a conference paper at ICLR 2023
SecondNav(S + T)
SecondNav(T +
1.4
1.2
1.0
Free Space
0.8
0.4
20
40
60
80
20
40
60
80
Agent Performance (SPL; Higher better)
Agent Performance (SPL; Higher better)
Figure A12: Free Space Inference for the Trai Treinerdggetteemory probe on both SecondNav(S TT) and SecondNav(T-SS) as a function of agent SPL. We see that as agent SPL decreases, the probe is able to take paths that inference more free space.
SecondNav(S + T)
SecondNav(T S)
Excursion Removal
2
20
40
60
80
20
40
60
80
Agent Performance (SPL; Higher better)
Agent Performance (SPL; Higher better)
Figure A13: Excursion Removal for the TrainedAgentMemory probe on both SecondNav(S-:T) and SecondNav(T -S)) function of agent SPL. We see that as agent SPI. decreases, excursion removal increases since the probe able to remove additional excursions.
Performance (higher better)
100
80
60
40
Metric
20
SPL
Success
50
100
150
200
250
Memory Length
Figure A14: Performance vs. memory length for agents trained under given memory length. Note that longer memory lengths are challenging to train for under this methodology as induces the negative effects of batce-batch optimization and is computationally expensive.
25

---

Published as a conference paper at ICLR 2023
Ground Truth
Prediction
Ground Truth
Prediction
12.4%
52.4%
UntriinesAgetKeemary
TrainedAggntMeemory
0.0
0.2
0.4
0.5
0.8
Map Prediction Accuracy (laU)
Figure A15: Map prediction with poor examples. In the main text we shows qualitative examples for the average prediction and good prediction. Here we show two additional examples: A, very poor quality prediction. This shows that the decoder sometimes does make large mistakes. B, the average prediction for the UntraineedgentNeeory decoder. This shows the qualitative difference between the average Untrainnddggentemmrr and TrainedAgentMemory prediction.
26


Reviews:
[{"review_id": "sKdgGvzWp1f", "reviewer": "Reviewer_XZvt", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "", "summary_of_the_paper": "While animal navigation assumes that there should be internal spatial representations (internal mental map) built and maintained for navigation, recent machine learning community’s works show that neural network-based models for navigation do not need explicit mapping modules; indeed, many models that do not contain explicit mapping achieve good performance in the exploration/navigation problems. This paper investigates a question “is mapping an emergent phenomenon?” In this work, the authors make their AI agent “blind”, which means that only egomotion sensor is present, making the agent having minimal perceptual system. There is no visual, audio, or any other sensing available to the agent. The paper argues that, under this harsh condition, the emergence of map-like spatial representations in the agent’s unstructured memory. \n", "summary_of_the_review": "I would give acceptance score to this paper, although i'm open to changes after the discussion with other reviewers. ", "strength_and_weaknesses": "- The strength of the paper comes from the novelty of the questions authors are asking. “Can blind agent navigate as well as non-blind agents?” lead to the bold, harsh conditions that agents are only given ego-motion sensors, without vision or any other sensor modalities. \n- The results are meaningful that it is possible to efficiently navigate with just ego-motion sensing. The strong performance by blind agents are explained by the role of memory, and the memory encodes the implicit maps about the environment. \n- In the section 2, the authors explain how the blind agents are becoming effective navigators (e.g. emergence of wall-following behavior and collision-detection neurons). In the section 3, the authors investigate how memory is utilized in the long-horizon settings. \n- Memory also enables shortcuts, shown by the probe agent that is given the original agent’s memory containing spatial representations of the environment. The probe agent leverages the memory to enable shortcuts. \n- I don’t see any weak points about the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eU86u2rkO1", "reviewer": "Reviewer_ccRY", "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": "", "summary_of_the_paper": "The authors test the hypothesis of if memory-free navigation-based agents build maps of their environment. They use blind agents trained to perform PointNav, which are effectively operating in grid-world environments. They show very convincing and creative experiments controlling for the memory length of the agent, predicting occupancy maps, and probing the agent.", "summary_of_the_review": "I found the paper very enjoyable and really interesting to read. The work isn't going to be very practically useful and won't change much from a practitioner's perspective, but tests a creative hypothesis of if maps emerge from blind navigation-based agents, which appears to be true. Overall, I found the experiments were very well thought out and convincing, and think the paper is a clear accept.", "strength_and_weaknesses": "Strengths:\n- The paper is very well written and structured. It was a pleasure to read. I also appreciate the time that went into the figures and outline.\n- The experiments were well thought out and convincing. Both the probing experiments and occupancy map prediction experiments were very interesting and are convincing of the phenomenon of blind agents encoding maps.\n- It is surprising and impressive that blind agents are able to achieve 95% success rate on PointNav.\n- The question posed in this work is intellectually interesting and creative.\n- The experiments controlling for memory length are also great.\n\nWeaknesses:\n- **W1.** This paper presents a neat and interesting observation, and a set of experiments to test their hypothesis. However, the implications of this work don't seem very widespread or practically useful for future work. Suppose the hypothesis that model-free agents build maps without explicitly being trained to build them is true. Who cares? Will this change how you train embodied agents in the future?\n- **W2.** It's disappointing that the experiments with vision-based agents didn't work out. The hypothesis makes sense, but effectively, the experiments in this paper are on grid-world environments. It would have been nice to show the hypothesis holds with vision-based agents or in more complex tasks like rearrangement.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "XQ-5Opnazn", "reviewer": "Reviewer_JNho", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "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": "", "summary_of_the_paper": "This paper is a study of blind point goal navigation agents---agents provided only a GPS+compass signal and expected to reach an unseen point goal---and their ability to form implicit maps and an understanding of the environment through navigation. The paper is a thoroughly interesting investigation and includes experiments to understand (1) how well blind memory-full agents can navigate despite their significant limitations, (2) how memory can be transplanted to imbue another agent with the ability to navigate more effectively (using that experience), and (3) to decode the agents' memories into occupancy grids as a means of scrutinizing their implicit maps of their surroundings.\n", "summary_of_the_review": "Overall, this is an excellent paper. I have only limited changes and suggestions for improvement. The investigation is detailed and thought provoking. The authors should strive to answer my question about the impact of memory on the agent's performance.\n", "strength_and_weaknesses": "The paper is incredibly well written and detailed and the experiments are thought provoking. The paper explores an interesting topic that should be interested to anyone---including both AI/ML scientists and also perhaps cognitive scientists---working in the space of navigation. Each experiment effectively answers its respective \"question\" and is accompanied with convincing visuals. While the paper does not introduce new \"techniques\" for navigation or training navigation agents, this should not be seen as a limitation of the work and the investigation and the analyses are valuable on their own. I have only a few comments and questions.\n\nI have some potential concerns about the results from Sec. 3 (Memory is used over long horizons). The agent is trained in such a way that the LSTM is expecting to receive all the previous observations from the start. As such, are the experiments providing out-of-distribution signals to the agent? Can the authors comment on the possibility of poor performance being a result of this shift in the nature of the data. Similarly, if the agent were retrained with a time-limited memory horizon (e.g., 100 or 500 steps), would we expect an increase in performance; new experiments are likely not necessary, though clarification on this point will be helpful.\n\nRelatedly, it would be helpful to have a separate curve (perhaps on the same plot) showing the success rate versus memory length in Fig. 2, as I believe this to be a key detail for understanding the performance with limited memory.\n\nSmaller questions and comments\n- The line in Sec. 2 \"but also that collisions-vs-not are linearly separable in this space\": I do not believe that this claim logically follows from the previous clause. It may be true, but seems disconnected.\n- The authors may also want to reference \"Learning Deployable Navigation Policies at Kilometer Scale from a Single Traversal\" by Bruce, et al 2018. The appendix of this paper tries to extract localization information from an agent's latent state, and may also be good to mention in the related work [I also believe another early paper in the VisDoom environment used a similar approach, but I am unable to find it.]\n- Introduction: I understand why it is included in the introduction but that \"memory\" is essential for strong performance is a fairly obvious conclusion even if the results in the respective section are more detailed. Consider rephrasing this question and answer to reflect the nuance of the effect under scrutiny.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3rwcRxuQHmu", "reviewer": "Reviewer_XPSp", "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": "", "summary_of_the_paper": "This paper studies the implicit emergence of mapping in simple recurrent blind agents. Removing the visual modality allows authors to reduce the possible strategies to reach the specified goal and to thus isolate the construction of an internal map. As mentioned in the paper, no technical novelty is proposed, but a study about an important and interesting question, i.e. whether simple recurrent agents can learn to implicitly map scenes, is studied. \n\nThe work presents many surprising findings, such as the strong performance of blind agents, the emergence of neurons specialised in collision detection, the impressive long horizon memory developed these agents, the quality of spatial maps decoded from the agents’ hidden state, and finally the capacity to forget information that is not useful for the task at hand. Authors also show that if initialising the hidden state of an agent with the one from another agent that has finished an episode, the new episode navigates more efficiently between the starting and end points, in both directions.", "summary_of_the_review": "Such empirical study is of high importance for the community. This paper provides many interesting and well supported insights. Allowing to better understand the underlying reasoning of simple recurrent agents can help develop better navigating agents in the future. I thus tend to recommend acceptance, but am still looking for answers from the authors to my remarks", "strength_and_weaknesses": "Strengths:\n1. Understanding the internal representation of scenes from neural agents is an important direction, both to make them more interpretable and to study the strategies that can be purely learnt from data.\n2. The context of the work is well defined, and the experiments are detailed and thorough.\n3. This paper presents many surprising findings (stated in paper summary) that are important for the Embodied AI community. \n\nWeaknesses:\n1. I am not convinced with the point made by authors in Section 5 about the ability to properly decode the occupancy maps even in unseen locations. This might suggest the decoding model rather learns some patterns about the average structure of occupancy maps. Results on this decoding task are still interesting, but maybe less strong. It would be interesting to quantify how biased towards some redundant structure in maps the decoding model is.\n2. It would be interesting to consider a comparison with a baseline that shares the same architecture as the blind agent, but composed of an additional explicit map with differentiable write and read operations. This could allow to compare the content of the maps with the ones decoded from the recurrent agent’s hidden state, as well as task performance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%