Model-based Navigation in Environments with Novel Layouts Using Abstract $2$-D Maps
Authors: Linfeng Zhao
Lawson L. S. Wong
Venue:  (2021)

Abstract: Efficiently training agents with planning capabilities has long been one of the major challenges in decision-making. In this work, we focus on zero-shot navigation ability on a given abstract 2-D occupancy map, like human navigation by reading a paper map, by treating it as an image. To learn this ability, we need to efficiently train an agent on environments with a small proportion of training maps and share knowledge effectively across the environments. We hypothesize that model-based navigation can better adapt an agent's behaviors to a task, since it disentangles the variations in map layout and goal location and enables longer-term planning ability on novel locations compared to reactive policies. We propose to learn a hypermodel that can understand patterns from a limited number of abstract maps and goal locations, to maximize alignment between the hypermodel predictions and real trajectories to extract information from multi-task off-policy experiences, and to construct denser feedback for planners by $n$-step goal relabelling. We train our approach on DeepMind Lab environments with layouts from different maps, and demonstrate superior performance on zero-shot transfer to novel maps and goals.

Under review as a conference paper at ICLR 2021
MODEL-BASED NAVIGATION IN ENVIRONMENTS WITH NOVEL LAYOUTS USING ABSTRACT 2-D MAPS
Anonymous authors Paper under double-blind review
ABSTRACT
Efficiently training agents with planning capabilities has long been one of the ma- jor challenges in pecision-making In this work, we focus on zero-shot navigation ability given abstract 2-D occupancy map. like human navigation by reading a paper map, by treating it as an image. To learn this ability, we need to efficiently train an agent on environments with small proportion of training maps and share knowledge effectively across the environments. We hypothesize that model-based navigation can better adapt agent's behaviors task, since it disentangles the variations in map layout and goal location and enables longer-term planning abil- ity on novel locations compared to reactive policies. We propose to learn a hyper- model that can understand patterns from a limited number of abstract maps and goal locations, to maximize alignment between the hypermodel predictions and real trajectories to extract information from multi-task off-policy experiences, and to construct denser feedback for planners by n-step goal relabelling. We train our approach on DeepMind Lab environments with layouts from different maps, and demonstrate superior performance on zero-shot transfer to novel maps and goals.
INTRODUCTION
If we provide a rough solution of a problem to an agent, can the agent learn to follow the solution effectively? In this paper, we study this question within the context of maze navigation, where an agent is situated within a maze whose layout has never been seen before, and the agent is expected to navigate to a goal without first training on or even exploring this novel maze. This task may appear impossible without further guidance, but we will provide the agent with additional information: an abstract 2-D occupancy map illustrating the rough layout of the environment, as well as indicators of its start and goal locations ("task context" in Figure 1). This is akin to a tourist attempting to find a landmark in a new city: without any further help, this would be very challenging: but when equipped with 2-D map with a "you are here" symbol and an indicator of the landmark, the tourist can casily plan a path to reach the landmark without needing to explore or train excessively.
Navigation is a fundamental capability of all embodied agents, both artificial and natural, and there- fore has been studied under many settings. In our case, we are most concerned with zero-shot navi- gation in novel environments, where the agent cannot perform further training the new environment; all that is needed to accomplish the task is technically provided by the abstract 2-D map. This differs from the vast set of approaches based on simultaneous localization and map- ping (SLAM) typically used in robot navigation (Thrun et al. (005),, where the agent can explore and build an accurate occupancy map of the environment prior to navigation. Recently, navigation approaches based on deep reinforcement learning (RL) approaches have also emerged, although they often require extensive training in the same environment (Mirowski et al., 2017 2018). Some deep RL approaches are even capable of navigating novel environments with new layouts without further training: however, these approaches typically learn the strategy of efficiently exploring the new environment to understand the layout and find the goal, then exploiting that knowledge for the remainder of the episode to repeatedly reach that goal quickly (Jaderberg et al. 2017). In contrast, since the solution is essentially provided the agent via the abstract 2-D map, require more stringent version of zero-shot navigation, where should not explore the new environment; instead, expect the agent to produce near-optimal path in its first (and only) approach to the goal.
exploration of

---

Under review as a conference paper at ICLR 2021
Env Simulator
reward
action
Task
Ltask
Planner
joint state
Task Context
model
T~p(7)
g
context representation
Figure I: each training episode, we randomly select a task to initialize environment simulation and feed the corresponding task context eт to the agent. We use joint state space IR input to the agent, consisting of position R., orientation R', and translational and rotational velocity RR Each cell the abstract map corresponds 100 units in the agent world.
Although the solution is technically accessible via the abstract 2-D map, some challenges remain use it effectively. First, although we assume that the layout in the 2-D map accurate, the map does not correspond to the state space of the agent in the environment, the agent must learn the correspondence between its state and locations the 2-D map. Second, actions in the 2-D map also cannot be directly mapped into the agent's s action space; moving betweend adjacent "cells" in the 2-D map requires a sequence of many actions, specified in terms of the agent's 's translational and rotational velocities. Hence, one cannot simply perform graph search on the 2-D map, then execute the abstract solution directly on the agent. Instead, we propose approaches that learn to use the provided abstract 2-1) map via end-to-end learning.
Concretely, we propose two approaches for navigation using abstract 2-D maps:
MMN (Map-conditioned Multi-task Navigator): A model- basee approach that learns a hyper- model (Ha et al., (0016), which uses the provided 2-D map to produce parameterized latent-space transition function fo for that map. This transition function fe is jointly trained with Monte-Carde tree search (MCTS) to plan (in latent space) to reach the specified goal [Schrittwieser al. 2019
MAH Mapdcooddtioned Ape-X HER DQN): A model-free approach based on Ape-X Deep Q- Networks (DQN) (Horgan al. 2018), a high-performing distributed variant of DQN, that takes in the provided 2-D map as additional input. Furthermore, we supplement it with our proposed n-step modification of hindsight experience replay (HER) (Andrychowiez et al. 2017).
In experiments performed in DeepMind Lab (Beattie al. 2016), 3-D maze simulation environ- ments shown in Figure 1, we show that both approaches achieve effective zero-shot navigation in novel environment layouts, and the model-based MMN is better at long-distance navigation.
BACKGROUND
We consider distribution of navigation tasks p(T). Each task is different in two aspects: map layout and goal location. (1) Abstract map. The layout of each navigation task is specified by an abstract map. Specifically,
abstract map m NxN is 2-D occupancy grid, where cell with is (black) indicate walls and Os (white) indicate nagivable spaces. A cell does not correspond to the agent's world, so the agent needs learn to localize itself given an abstract 2-D map. We generate set of maps and guarantee that any valid positions are reachable, i.e., there is only one connected component in a map. (2) Goal position. Given a map, we can then specify pair of start and goal position. Both start and goal are represented
"one-hot" occupancy grid g 2 N provided to the agent. For simplicity, we use g to refer to both start and goal, and we denote the provided map and start-goal positions
(m. g) the task context.
We formulate each navigation task as a goal-reaching Markov decision process (MDP), consisting of tuple (S, AS,A, P. Rg, Pu, 7), where S is the state space, A is the action space, P is the transition function P S x A + (SS), Po = p(sp) is the initial state distribution, and y E (0, 1] is the discount factor. We assume transitions deterministic. For each task, the objective is to reach
2

---

Under review as a conference paper at ICLR 2021
subset of state space Sg C S indicated by a reward function Rg S A - R. We denote task as T = (P. Re, Po), since a map and goal specify the dynamics and reward function of a MDP. respectively. In the episodic goal-reaching setting, the objective is typically not discounted (y 1) and the reward is -1 for all non-goal states, i.e., Rg(s,a) = IIs & g). g E Sg.
3 MAP-CONDITIONED PLANNING GIVEN ABSTRACT 2-D MAPS
To build a map-based navigation agent efficient in both training and transfer, there are several tech- nical challenges. (1) A local change in map may introduce entirely different task structure, need the model and planner to adapt to the task context in a different way than conditioning on state, and not directly condition on the entire task context. (2) During training, we can only rely on a very small proportion of training tasks (e.g., 20 of 13 x 13 maps). This requires the agent to be efficient in terms of understanding each task's structure, i.e. the layout of training maps and goal locations. (3) Since reward is sparse and model learning and exploration are done simultaneously, we need to fully utilize the knowledge in the environment train the model and planner, such as transition tuples and failure experiences. Corresponding to the challenges, we introduce the task-conditioned hyper- model first, followed by the forward pass of the planning computation by using the hypermodel in inference. We then detail the backward pass the training target and optimization process.
3.1 MASK-CONDITIONED HYPERMODEL.
We aim to build model adaptive to given abstract 2-D maps for the navigation planner. In single-task training schema, a naive solution is to separately learn a param- eterized transition function f((s, a) for different maps. However, we want to share knowledge between tasks in navigation domain, in which maps have some common computational patterns. For example, in Figure 2 mov- ing right on center of the box on the left map shares some computation with the right one. This also applies to the larger scale of map area and also the reward prediction. When the agent is able to capture this type of computa- tional pattern, it can better predict what will happen when transferring new task.
W
W
W
W3
h
h
Figure 2: Applying hypermodel hyp on two maps. They may share local pat- terns at some scales that can be captured by the hypermodel.
We propose to build a meta network hgg or hypermodel, learn the "computation" of the transition model fy si- multaneously for all maps with abstract 2-D maps as input. The transition model for task T (map- goal pair) is a function f. that maps current (latent) state and action to a next (latent) state. The set {fi} } represents transition functions of all tasks belonging to navigation schema (e.g.. a certain size of map), and these tasks have similar structure. We parameterize a transition function fa as a neural network with its parameter vector di We assume the set of transition networks have similar structure that can be characterized by set of context variables c = (m,g), i.e., the abstract 2-D map and goal This implies that parameter vectors o; live in low-dimensional manifold. Thus, we define a mapping h C + & that maps the context transition function fi- We parameterize h also as network with parameter d
task to the parameter vector Φ, of its
h c Φ. fe f.
(1)
This can be viewed as soft weight sharing between multiple tasks. It efficiently maps low- dimensional structure in the MDP. specified by the map. to computation of the transition model. It may also be viewed as a learned "dot-product" between task context CT and state and action st, at predict the next state. The idea of predicting the weights of main network using another meta-network is also known as HyperNetworks (Ha et al. 2016) von Oswald et al. 2019).
downsampled global occupancy map. cropped local occupancy map, and "onc-hot" goal and start occupancy maps, where N downsampled size.
CConcretely, task context 4 has four components:
We only predict weights of the transition model fo S x A + S which operates on latent state space. The mapping from environment observations to latent states O - S is not predicted by meta network. Since the latent space is low-dimensional, it is feasible predict weight matrices of transition network for it.
3

---

Under review as a conference paper at ICLR 2021
Reward Joint State
eaf-
MCTS
put-)
Predicted
Policy, Value
Reward
Searched Palicy, Value
task
C
model
Figure 3: We use yellow circles indicate predicted states other quantities, and grey or squares from actual interactions. (left) Applying MCTS with hypermodel to search for behavioral policy and value, and act with a sampled action. (right) Computing targets and backpropagating from loss. The blue line indicates ntstep relabelling. We only illustrate backpropagation for one reward node for simplicity. The solid red line to emphasize the gradient flow from the auxiliary model loss the meta network's weight t/. The dashed red line is the gradient from task loss.
3.2 PLANNING USING LEARNED HYPERMODEL.
Equipped with map-conditioned model, we use it to search actions according the map layout and goal location (a'....aa*) a²) Plan( (f [ J. c, fe). We use Monte Carlo tree search (MCTS) (Silver et al. 2017 Schrittwieser et al. 2019) to search with learned hypermodel fe- For multi-tase special benefit is that masel planning disentangles the navigation behavior in terms of goal level and map level, which correspond reward function and transition dynamics, respectively. Intuitively, the navigation computation Plan({*;), , c, f&) is highly non-linear in e = (m, g). and thus disentangling them leads more effective learning and generalizing across tasks.
As shown in Figure we first encode the observed joint state into a latent space 9; with learned encoder co))) the root node of the search tree. Given latent state and candidate action, the next state is predicted using hypermodel fa. For each state (node), another network (a(s;, at) predicts the policy ne and value function v. (Schrittwieser et al., 2019), which are used for aligning with searched quantities in a separate training process. After number of simulations is done and the statistics are backpropagated to the root node, we sample an action from the searched policy. The trajectory and corresponding abstract map and goal (cT, {st, de, Te, $1+1),) },) saved centralized replay buffer. In the training process, these quantities are predicted on latent states and aligned to the saved quantities from actual experiences.
At zero-shot evaluation time, given an unseen abstract map, we apply planning with trained hy- permodel: (1) given map and goal of (mrrgg)) at the beginning of the episode, compute the hypermodel weights o h[c; e) by applying the meta-network on the task context Cr, (2) start MCTS simulations using the hypermodel f [s,, a; o) for latent state predictions, (3) get action and transit to next state, and go to step (2) and repeat. Moreover, if we assume to have a landmark oracle on given maps, can perform hierarchical navigation by generating a sequence of local subgoals {m, 9:) H and plan to sequentially achieve each intermediate landmark.
3.3 CONSTRUCTING LEARNING TARGETS WITH n-STEP GOAL RELABELLING
Jointly training planner with learned model can suffer from lack of reward signal, especially when the model training entirely relies reward from multiple tasks, which is common in model-based agents based on value gradients (Schrittwieser et al., 2019 Oh et al., (017). Motivated by this, we introduce straightforward strategy enhance the reward signal by implicitly defining learning curriculum, named n-step hindsight goal relabelling. This generalizes the single-step version of Hindsight Experience Replay (HER) (Andrychowicz al. 2017) by extending it n-step return.
We adopt a multi-step strategy motivated by single-step HER, by relabelling failed goals to randomly sampled future states (visited area) from the trajectory, and associating states with the relabelled n-
4

---

Under review as a conference paper at ICLR 2021
step return. Concretely, the task-conditioned bootstrapped n-step return is
GT - re+1 + 7T+42 + 7 + , U. TH - CT)
where vo is the the state-value function bootstrapping steps into the future from the search value and conditioned on task context CT. Empirically, this strategy significantly increases the efficiency of our multi-task training by providing smoothing gradients when sampling mini-batch of n-step targets from successful or failed tasks. Additional details are provided in the appendix.
3.4 JOINT OPTIMIZATION
Our training target has two components. The first component is based on value gradients (Schrit- twieser et al. 2019; Oh et al. 2017), where the gradient from value predictions on predicted expe- riences 1s backpropagated from the aforementioned (relabelled) n-step targets, However, the value- gradient-based method is designed for single-task RL, which can be sample inefficient in training on different map layouts and goals. Thus, we propose an auxiliary alignment loss to regularize the dependencies of hypermodel sø(s, a, hig (cT)) and "navigation compulation" Plan({*;), CT; S&) on corresponding task context CT. to enable the hypermodel to be learned more accurately and effec- tively in the multi-task setting. Figure 3 (right), we maximize the mutual information between task context eт and predicted trajectories řт from the hypermodel sampled tasks T ~ p(T):
max ET~ [T)): Nup
where (cT))) is the meta network predicting the weight of transition network fe. Observe that: ((T;c) = (T) ((Tec) 2 H(T) + E,, [log ((T[c)], we can equivalently optimize the RHS max; ET [log ((T(c) D max, E (s...r) [logg(s' ( [s, a; h(c)),, where we omit the subscripts for simplicity. This objective requires us to maximize the agreement of predicted states over the expectation of both (I) sampled states and (2) multiple tasks, i.e., minimizing distances d(s',
4 EXPERIMENTS
In the experiments, we assess our method and analyze its performance on DeepMind Lab (Beattie et al. 2016) maze navigation environment. We focus on the evaluation of zero-shot transfer in this section. We include more training results in Section B. of the appendix.
4.1 EXPERIMENTAL SETUP
We perform experiments DeepMind Lab (Beattie et al. 2016), reinforcement learning envi- ronment suite supporting customizing 2-D map layout. As shown in Figure []] we generate a set of abstract 2-D maps, and use them to generate 3-D environments in DeepMind Lab. Each cell on the abstract map corresponds to 100 units in the agent world. In each generated map. all valid positions reachable, i.e., there is only one connected component in the map. Given sampled map, then generate a start-goal position within a given distance range. Throughout each task, the agent receives the abstract map and start/goal location indicators, the joint state vector o I222 (consisting of position RRS orientation RR, translational and rotational velocity IR), and reward signal r. The action space is (forward, backward, strafe left, strafe right, look left, look right), with an action repeat of 10. This means that, at maximum forward velocity, the agent can traverse a 100 x 100 block in two steps, but typically takes longer because the agent may slow down for rotations.
Training settings. We train set of agents variety of training settings, which have several key options: (1) Map size. We mainly train on sets of 13 x 13, 15 x 15, 17 x 17, 19 x 19, 21 x 21 maps. One cell in the abstract map is equivalent to 100 100 block in the agent's world. (2) Goal distance. During training, we generate start-goal pairs with distance between 1 and 5 in the abstract map. (3) Map availability. For each map size, we train all agents on the same set of 20 generated maps, with different randomly sampled start-goal pairs in each episode.
Evaluation settings and metrics. We have several settings for evaluation: (1) Zero-shot transfer. We mainly study this type of generalization, where the agent is presented with 20 unseen evaluation
5

---

Under review as a conference paper at ICLR 2021
Mulhod
1964
Suc0sss Tra Trajoctory Longte
80
Methood NiW
0.R
Hili
Ni
Successu Rate
MArt-rO 1067
0.6
-20
0.0
10
Distancc Abotrct Nass
Disrancs Abstract Mapa
Figure 4: Zero-shot evaluation performance on 13 x 13 maps from distance to 15. (a) Success rate of all agents. (b) Lengths of successful trajectories of MMN and MAH.
100
1.0
W
0.8
21
Node
onig
0.4
0.4
rect
fig
shulls
02
0.2
Method
NHV
Distance on Abslract Maps
Dicance on Abstrect Maps
Figure 5: Study of performance on (a) different map sizes and (b) perturbation strategies.
maps, and has navigate between randomly generated start-goal pairs of varying distances. (2) Perturbation. To understand how the map input affects the performance, we evaluate agents with input abstract maps perturbed by different strategies. (3) Goal Distance on abstract map. We focus on two scenarios of goal distance on abstract maps: direct navigation and hierarchical navigation. In the direct case, we evaluate on a range of distances ((1, 15)) on set of maps, while in the hierarchical case, we generate a set of landmarks with a fixed distance of 5 between them and provide these to evaluated agents sequentially. (Metrics) We mainly report the average success rate over evaluated maps, and average length of successful trajectories, with 95% confidence intervals.
Methods. We compare model-based method, conciiinito Multi-task Navigator (MMN) with a task-conditioned model-free agent, Map-conditioned Ape-X HER DQN (MAH) and Single- task Ape-X HER DQN (SAH). MAH is based Ape-X DQN and HER, which trains reactive policy also conditioned on abstract 2-D map and goal input. SAH is a single-task model-free base- line, which does not have task context as input. We also use a random agent to demonstrate lower bound of the navigation performance. Details of the MAH and SAH are in the appendix A.
4.2 ZERO-SHOT TRANSFER TO LOCAL GOALS IN NOVEL LAYOUTS
Transfer of locally trained agents. In this setting, train all four agents 20 13x 13 maps with randomly generated local start-goal pairs with distance [1, 5] in each episode. We train the agents until convergence; MAH typically takes 3x more training episodes and steps (see Section B.T]. We evaluate all agents on 20 wnseen 13 x 13 maps and generate 5 start-goal pairs for each distance from 1 to 15 on each map. The results are shown Figure MMN and MAH generally outperforms the other two baselines. MMN has slightly better performance especially over longer distances, both in success rate and successful-traipe trajeccoor length, even though it was only trained on distances 5. Note that we did not include lengths for the two baseline methods due to their low success rates.
Transfer on larger maps. We also evaluated MMN on larger maps from 15 x 15 to 21 x 21. We tested the zero-shot transfer performance on 20 unseen maps of corresponding sizes and generated start-goal pairs with distance [1, 15). As shown in Figure ((a) even though training performance is similar among varying sizes (not shown), zero-shot transter on novel larger maps becomes increas- ingly harder, which shows the difficulty of learning directly from abstract 2-D maps.

---

Under review as a conference paper at ICLR 2021
Figure 6: Trajectories from hierarchical navigation in zero-shot on 13 x 13 maps. The top-right corner is the start, and the bottom-left the goal. Other darker cells are generated subgoals with distance 5. The first row is for MMN and second row is for MAH. For the first 4 tasks (columns), MMN successfully reached the goals, while MAH failed. Both methods failed in the last task.
Success Rate
Average Success Length
Average Common Success Length
MMN
16 16/20
62.25
46.44
MAH
9/20
92.55
92.55
Table 1: Zero-shot transfer results hierarchical navigation
4.3 PERTURBATION OF ABSTRACT 2-D MAPS
To further study the importance of the abstract map input, during evaluation on 13 x 13 maps, we perturb the task context input c = (m, g) and provide an disrupted version to agents. We examine several perturbation strategies: flip, shuffle, and original accurate map input. (1) In zero mode, we give a tensor of zeros as abstract map and start/goal inputs to agents. In this case, the model may malfunction and rely its policy and value prediction function to provide rough estimations. (2) In shufffe mode, we sample another map and start/goal pair within the set evaluation maps. Thus, the entire structure should be entirely different and may largely affect the decision. (3) In flip mode, we randomly change the value of a cell with probability vice versa). Note that flipping only changes the map but not the goal g. thus the agent can still capture rough direction in local navigation. We evaluate on distances between and 8.
80% (from wall to navigable space or
As shown in Figure 5(b) shuffle has the largest effect the performance, since randomly choosing another map not only changes the map input m' to the agent, but also provides a misleading goal g'. Providing a zero map/goal has the second largest performance drop, since does not mislead the agent with wrong map goal, but does not provide the information that is necessary to complete the task without further learning and exploration. This demonstrates that both MMN and MAH are relying on the abstract map and start/goal input to do zero-shot navigation effectively. Surprisingly, the flip strategy turns out to have little performance decay. The reason for this may be that only the map is flipped, and since evaluate on local start-goal pairs with distance [1, 8). the flipping may not greatly affect the path connecting start-goal pairs, and the agent can rely on the unperturbed goal to navigate in the correct direction for short distances.
4.4 HIERARCHICAL NAVIGATION ON NOVEL LAYOUTS
In this section, we provide an additional landmark oracle to generate sequences of subgoals between long-distance start-goal pairs, and evaluate the performance of hierarchical navigation. We use the agent trained 13 x 13 maps, and evaluate on set of 20 13 x 13 unseen maps. On each map, we use the top-right corner the global start position and the bottom-left corner the global goal position, then plan a shortest path in the abstract 2-D map. and generate a sequence of subgoals with distance 5 between them; this typically results in 3 to intermediate subgoals. Consecutive subgoal pairs are then provided sequentially to the agent as local start-goal goal pairs to navigate. The navigation is considered successful only if the agent reaches the global goal by the end.
7

---

Under review as a conference paper at ICLR 2021
We evaluate MMN and MAH these 20 sequences of subgoals. We provide the next subgoal when the current one is reached or until timeout. As shown in Table our model-based MMN out- performs the model-free counterpart by a large margin. MMN which include all 9 successful cases of MAH. We also compute the average successful-trajectoryy length and average common success length, where the latter only considers the overlapping set of 9 tasks that both approaches succeeded in. We visualize five trajectories of zero-shot hierarchical navigation in Figure [ The model-based MMN is more robust to the intermediate failed subgoals by navigating to the new subgoal directly, where the model-free MAH gets stuck frequently.
reach 16 out of 20 global goals,
5 RELATED WORK
Zero-shot navigation. Navigation is widely studied in robotics, vision, RL, and beyond; to limit the scope, we focus on zero-shot navigation in novel environments, which is most relevant to this work. This excludes traditional approaches based on simultaneous localization and mapping (SLAM) (Thrun et al., 2005), since those methods need to explicitly build a map before navigation, and the map can only be used for the corresponding environment and cannot be transferred to other layouts. Learning-bast
methods such as by Mirowski et al. (2017: 2018) also require extensive training data from the same environment; they demonstrate ceneralization to new goals in the en- vironment, but not transfer to new layouts. [Dadebbrg et al. (017);; Chen et al. (201); Gupta et al. 2019):Chaplot et al. (2020) demonstrate agents that learn strategies explore the new environment and potentially build maps of the environment during exploration; in contrast, we are interested in agents that do not need to explore the new environment. The approach of Gupta et al. (2019) does not necessarily explore the new environment: instead, it learns and exploits semantic cues from its rich visual input, which is orthogonal to our work since we use the state directly. Other domains such as must-person-shootiie
games have also used agents that navigate in novel environments (Lample) & Chaplot 2017 Dosovitskiy & Koltun 2017] Zhong et al. 2020), but since navigation not the primary task in those domains, the agents may not need to actually reach the specified goal (often none are specified). Most closely related to our work is by [Brunner et al. (2018), who also use 2-D occupancy maps as additional input and perform experiments in DeepMind Lab. Their approach is very specific to map-based navigation, whereas our model- based approach uses more generic com- ponents such as hypermodels and MCTS, and may be more readily generalizable to other problems.
Model-based RL and planning. Model-based RL algorithms can be roughly grouped into four classes (Wagg et al. 2019). 1. Train a transition model via supervised learning and learn on gener- ated experience (Pong et al., 2018), or Dyna-style. 2. Follow the analytical gradient of the model (Heess et al.) 2015). which may also require certain assumptions on model's form (Deisenroth & Rasmussen 2011). 3. Sampling-based planning selects promising next action by sampling from
a certain action distribution (Hafner et al.] 2018 Chua et al. 2018); this includes MCTS-based al-
gorithms (Silver al., 2017 Schrittwieser al., 2019 Siiverr& & Veness 2010 Tian et al. 2019) in discrete-action setting. 4. Implicitly learn a model by matching value or reward predictions from un-
rolled trajectories to targets from real experience (Tamar al., 2016 Oh al. 2017 Schrittwieser
ct al. 2019). Additionally, a body of work (Parisotto & Salakhutdinov 2017 17 Banino et al.) 2018]
Fortunato et al. 2019 Wayne et al., 2018 Ma et al.) (020) studies learning more structured latent models or representations useful for planning. Our method relies on types 3 and 4 above to learn
an universal transition model on multi-task environments, and is most closely related to MuZero [Schrittwisser et al. 2019), which only predicts task-related quantities, such as rewards and values.
6 CONCLUSION
In this work, we have presented two approaches for enabling agents to navigate in environments with novel layouts without requiring further training or exploration (zero-shot), by using provided abstract 2-D maps and start/goal information. Both approaches MMN and MAH performed well in zero-shot navigation in short distances; for longer distances (with access to a landmark oracle), our model-based approach MAH performed significantly better. In future work, we will replace this oracle with a learned subgoal generator, extend this work to handle visual observation input and perform navigation in rich visual environments, and consider other types of provided task contexts.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in neural information processing systems, pp. 5048-5058, 2017.
Andrea Banino, Caswell Barry, Benigno Uria, Charles Blundell, Timothy Lillicrap. Piotr Mirowski, Alexander Pritzel, Martin Chadwick, Thomas Degris, Joseph Modayil, et al. Vector-based navigation using grid-like representations in artificial agents. Nature, 557(7705):429 433, 2018.
Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, et al. Deepmind lab. arXiv preprint arXiv:1612.03881. 2016.
Gino Brunner, Oliver Richter, Yuyi Wang, and Roger Wattenhofer. Teaching a machine to read maps with deep reinforcement learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Devendra Singh Chaplot, Dhiraj Gandhi, Saurabh Gupta, Abhinav Gupta, and Ruslan Salakhutdi- nov. Learning to explore using active neural slam. In International Conference on Learning Representations, 2020.
Tao Chen, Saurabh Gupta, and Abhinav Gupta. Learning exploration policies for navigation. In International Conference on Learning Representations. 2019.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learn- ing handful of trials using probabilistic dynamics models. In Advances Neural Information Processing Systems, pp. 4754-4765. 2018.
Mare Deisenroth and Carl Rasmussen. Pilco: model-based and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp- 465-472, 2011.
Alexey Dosovitskiy and Vladlen Koltun. Learning act by predicting the future. In International Conference on Learning Representations, 2017.
Meire Fortunato, Mclissa Tan, Ryan Faulkner, Steven Hansen, Adrià Puigdomènech Badia, Gavin Buttimore, Charles Deck, Joel Z Leibo, and Charles Blundell. Generalization of reinforcement learners with working and episodic memory. In Advances in Neural Information Processing Systems, pp. 12448-12457, 2019.
Saurabh Gupta, Varun Tolani, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik. Cognitive mapping and planning for visual navigation. International Journal on Computer Vision, 2019.
David Ha, Andrew Dai, and Quoc V Le. Hypernetworks. arXiv preprint 1609: 2016.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. arXiv preprint arXiv:1811.0455 2018.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. Advances in Neural Information Processing Systems, pp. 2944-2952. 2015.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv: 300033 2018.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In International Conference Learning Representations, 2017.

---

Under review as a conference paper at ICLR 2021
Guillaume Lample and Devendra Singh Chaplot. Playing fps games with deep reinforcement learn- ing. In AAAI Conference on Artificial Intelligence, 2017.
Xiao Ma, Peter Karkus, David Hsu, Wee Sun Lee, and Nan Ye. Discriminative particle filter rein- forcement learning for complex partial observations. arXiv preprint (tt:::2002.09888 2020.
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, et al. Learning to navigate in complex environments. In International Conference on Learning Representations, 2017.
Piotr Mirowski, Matt Grimes, Mateusz Malinowski, Karl Moritz Hermann, Keith Anderson, Denis Teplyashin, Karen Simonyan, Andrew Zisserman, Raia Hadsell, al. Learning navigate in cities without a map. In Advances in Neural Information Processing Systems, pp. 2419-2430, 2018.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Advances in Neural Information Processing Systems, pp. 61 18-61228 2017.
Emilio Parisotto and Ruslan Salakhutdinov. Neural map: Structured memory for deep reinforcement learning. arXiv preprint 1702.0/702.08366 2017.
Vitchyr Pong, Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model- free deep rl for model-based control. arXiv preprint arXiv:1802.0908/ 2018.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon
Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Græepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint
2019.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in neural infor- mation processing systems, pp. 2164-2172, 2010.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self- eelf-play with general reinforcement learning algorithm. arXiv preprint 171.001712.018/5:: 2017.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In Advances Neural Information Processing Systems, pp. 2262, 2016
Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic Robotics. 2005.
Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and C Lawrence Zitnick. Elf opengo: An analysis and open reimplementation of alphazero. arXiv preprint 1rXiv:190..04552, 2019.
Johannes von Oswald, Christian Henning, João Sacramento, and Benjamin F Grewe. Continual learning with hypernetworks. arXiv preprint urXiv:/900 /tt.://90000095, 2019.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model-based reinforce- ment learning. arXiv preprint arXiv: NKi::1907.00057. 2019.
Greg Wayne, Chia-Chun Hung, David Amos, Mehdi Mirza, Arun Ahuja, Agnieszka Grabska- Barwinska, Jack Rae, Piotr Mirowski, Joel Z Leibo, Adam Santoro, al. Unsupervised predictive memory in a goal-directed agent. arXiv preprint 1803 2018.
Victor Zhong, Tim Rocktäschel, and Edward Grefenstette. RTFM: Generalising to new environment dynamics via reading. International Conference on Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL ALGORITHM DETAILS
A.1 DETAILS ABOUT COMPARED METHODS
As focus of our work, we examine the zero-shot transfer performance and compare all four agents in this section: MMN, MAH, SAH, and Random. In the implementation, we keep all components of MMN and MAH the same as much as possible, except that MAH only has a map-conditioned reactive policy network but no hypermodel. We use similar architecture for the Q-value network Q(+, CT). which is also conditioned on abstract 2-D maps and goals, as the policy and value prediction network go CT) in our method. The task input to SAH has been further masked, so the Q-value network is simply a single-task version a() Thus, the main difference between our model-based approach MMN and the multi-task model-free variant MAH is that MAH entan- gles transfer on the map (dynamics) and goal (reward) levels, since the Q-value network needs to generalize value prediction jointly on different latent states 5, goals g, and abstract 2-D maps m.
A.2 ADDITIONAL DETAILS OF n-STEP RELABELLING
As shown in Figure (right), we sample a trajectory of experience (cr, {s,, Tt, specific map and goal cr (mr.gr .r) from the replay buffer. Observe that, if the agent does not reach the goal area Sg (a 100 x 100 cell in the agent space denoted by a coordinate gr on the abstract 2-D map), it will only receive reward r -1 during the entire episode until timeout. In large maps, this hinders the agent to learn effectively from the current map my. Even if the agent partially understands a map. it would rarely experiences specific goal area on the map again This is more frequent on larger maps in which possible navigable space is larger.
Tt, 5(+1)) on a
We adopt a multi-step strategy motivated by single-step HER, by relabelling failed goals to randomly sampled future states (visited area) from the trajectory. To relabel the task-conditioned bootstrapped n-step return, there are three steps. (1) Goal. Randomly select reached state St E R2 from the trajectories, then take the 2-D position (z. y) E R² in agent world and convert it to a 2-D goal support grid gTs. Then, relabel the goal in task context cTg = (mTT 9T: ) keeping the abstracted map and start position unchanged. (2) Reward. Recompute the rewards along the n-step segment. In episodic case, we need to terminate the episode if the agent can reach the relabelled goal area 9Ts> by marking "done" at the certain timestep or assigning zero discount after that step % 0 to mask the remaining segment. (3) Value. Finally, we need to recompute the bootstrapping task-conditioned value vT',, _/= go( (St. CTg). Empirically, this strategy significantly increases the efficiency of our multi-task training by providing smoothing gradients when sampling a mini-batch of n-step targets from successful failed tasks. It can also be applied to other multi-task agents based n-step return.
A.3 JOINTLY TRAINING HYPERMODELS
In the off off-pc implementation, since we need to sample a mini-batch of trajectories, we have a batch of different contexts [c1, C.,,...G Cn] during multi-task training, and need to generate a batch of weight [01, $2, ..... 2n] to compute each mini-batch gradient. To efficiently implement this, it beneficial to use batch matrix multiplication in computing [0]:-.., Øn] = ([c,([ Gx) and [s'.....& [ f((s), ..., sn], [0t, an] [$1, 02, $2, onl) on a batch of randomly sampled transitions on different maps.
A.4 ADDITIONAL DETAILS OF HYPERMODELS
We assume input is M dimeensioonl vectors in a mini-batch of size B, i.e., input tensor is RR Bx The main network is MLP with hidden units L; in layer i. We denote the input layer 0, i.e., Li = M. Thus, the weight matrix from layer i --1 to layer has size W, E LI.II We assume the task context is Z-dimentional and in mini-batch of input each has different task context associated with it, i.c., input tensor to the hypermodel is in I 8x2 The hyperwork is also a MLP with hidden units K; in each layer. The last hidden layer outputs a tensor B x N, where N the
In our extremely low data regime, the agent only has one start-goal pair on small set of map. While on low data regime, the agent can train on randomly sampled pairs on the maps. See the Setup for more details.
11

---

Under review as a conference paper at ICLR 2021
MAH
NINN
MMMN-15KC9
MMN-2121
NMNN-7XLL
1100
-100
220
Eprcddes
Episodes
100,000
200,000
300,000
400,000
500,000
20,000
40,000
60.000
00,000
100,000
(a) Comparison of MMN and MAH
(b) Comparison map sizes
Figure 7: Multi-task training performance of MMN and MAH.
MUNN winhwling)
UAVN
400
3000000
2000 2000 30X13801
Figure 8: Ablation study of n-step relabelling.
dimension of output embedding for generating weights of the main network. The final generation layer has multiple branches. For generating weight tensor W; E g. of the main network for all task contexts, the branch outputs multi-task weight tensor B x Li-1 x L; and thus the mapping hont N + B x 1--1 I, has weight tensor with dimensions N x (L--1 I...
A.5 ARCHITECTURE OF IMPLEMENTATION
Aiming at fair comparability of our method MAH with the model-free method MAH, we implement them unified framework. Both ours (model-based) and model-free baselines have N actor workers, single learner, and a centralized buffer worker. Each actor worker has a copy of the environment instance running single-threaded and take actions using either MCTS Q-network.
B EXTRA EXPERIMENTAL RESULTS
B.1 MULTI-TASK TRAINING PERFORMANCE
We demonstrate some representative results of the training performance of MMN and MAH. First, we compare the training on 20 of 13 x 13 maps with randomly generated goals at each episode, which is the most widely used training setting in our transfer evaluation. In [ our model- based version MMN is much more sample efficient than the reactive MAH. There are two potential reasons: (1) model-based method is usually more sample efficient demonstrated in many single- task environments, and (2) our MMN is able to share knowledge between local patterns via the hypermodel. We also show the training results on larger map sizes with local start-goal pairs [1,5] in Figure (b). Although found the evaluation performance decreases larger maps, the lo- cal training performance w.r.t. episodes is similar. We include more results in the supplementary material.
We also study the ablation of n-step relabelling in Figure Bin special fixed goal setting on 13 x 13 map. With the relabelling, our method is able to get signal earlier and learn faster.
12

---

Under review as a conference paper at ICLR 2021
1.0
Evaluation Setting
0..0
0.8
MMN
Successful Rate
0.4
2
10
12
Distance on Abstract Maps
Figure 9: Ablation study of different hyperparameters in evaluation.
B.2 ABLATION STUDIES OF TRANSFER
Ablation study evaluation hyperparameters. We study two related hyperparameters in the zero-shot transfer: (1) number of simulations, where we change it to 30 from 100, and (2) temper- ature in action sampling, which is set to 0.1 from original value 0.25. We use random goal for distance [1, 15] on 20 of 13 x 13 maps. Figure we found decreasing number of simulations and increasing deterministicity do produce significant difference.
Transfer with few-shot adaptation. To examine if zero-shot transfer still have any room of im- provement, we also experiment on finetuning on same maps with different goals. Suprisingly, we found finetuning on novel maps does not result in improved performance. However, it is understand- able since we have fully trained the agents during multi-task training, and the amount of data and learning steps in finetuning is insignificant compared to the training stage (about 10 vs. 10 steps, and 10 vs. 102 trajectories). leave the further study fhw-shot adaptation with abstract maps for future work.
13


Reviews:
[{"review_id": "hVDgjgQca6", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission tackles the Point Goal navigation task given access to the agent’s starting location, current state (position and velocity), the goal location and a top-down map. The submission presents two approaches for tackling this task. First is MMN (Map-conditioned Multi-task Navigator) which is model-based approach which learns to hyper-network to convert map input to a transition function. Second approach is MAH (Map-conditioned Ape-X HER DQN) which is model-free approach using Ape-X DQN with Hindsight experience replay.\n\nThe submission has several weaknesses:\n- I believe the key challenge in solving the point goal navigation task given access to a top-down 2-D map is localization. However, the authors assume access to the agent’s position and orientation which makes localization trivial. This assumption simplifies the task a lot. In fact, I believe there’s a deterministic solution to this task which would achieve ~100% success rate. The starting location, the goal location, and the map are given as input to the agent. The agent can use any planning algorithm like Dijkstra to plan the path to the goal location. The only minor challenge is that the action space is different from moving cells on the map, but the sequence of actions required to go to the next map cell is easy to obtain given that the actions and transitions are deterministic and the agent has access to its location and velocity at all time steps.\n- There are several existing methods for the PointGoal navigation task in unseen environments without having access to the map (for example [1-4]), which seem to achieve much better performance (90-99% success) in more realistic environments. One or more of these methods should be used as baselines. A lot of these works have also open-sourced the code.\n- The submission uses mazes in the DeepMind Lab for evaluation. I believe the key challenge of understanding abstract maps is highly simplified in this environment. I am not convinced that performance in this environment is indicative of performance in realistic environments as realistic maps are more complex and very different from mazes. There are several more realistic simulation environments available for navigation such as Habitat [5], Gibson [6], AI2Thor [7], etc.\n- One of the desirables when learning to navigate with access to a 2-D map as opposed to navigating without maps is efficiency. Although the authors report success trajectory length, I believe Success weighted by path length (SPL) is a more informative metric to measure efficiency. SPL is commonly used in navigation papers in recent years (for example, [1-5]) and it makes it easier to compare the performance of different methods.\n\nIt is very difficult to access the efficacy of the method since the task is simplistic and there exists a deterministic solution to the task which would achieve ~100% success rate. The submission also lacks competitive baselines.\n\nSuggestions for improvement:\n- The agent should not have access to the true pose and velocity. This assumption makes the task trivial in my opinion.\n- The actions and motion should not be deterministic.\n- Empirical evaluation in a more realistic simulation environment would be more indicative of the efficacy of the proposed method.\n\n[1] Ramakrishnan et al. Occupancy Anticipation for Efficient Exploration and Navigation. ECCV, 2020\n\n[2] Wijmans et al. DDPPO. ICLR, 2020\n\n[3] Chaplot et al. Learning to Explore using Active Neural SLAM. ICLR, 2020\n\n[4] Sax et al. Learning to Navigate Using Mid-Level Visual Priors. CoRL, 2019\n\n[5] Savva et al. Habitat: A Platform for Embodied AI Research. ICCV, 2019\n\n[6] Xia et al. Gibson env: real-world perception for embodied agents. CVPR 2018\n\n[7] Kolve et al. AI2-THOR: An Interactive 3D Environment for Visual AI. 2017\n\n[8] Anderson et al. On Evaluation of Embodied Navigation Agents. 2018\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "N0LEd6zhUGZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tackles the task of going to a point-goal using an abstract 2D map of a given environment. The central idea is to use the given abstract 2D map to predict parameters for the transition function in the environment depicted by the map. This predicted transition function is used to search for actions to execute via planning.\n\nStrengths: The paper tackles an interesting problem, that of how to use an abstract 2D map to navigate. It proposes interesting neural architectures for solving this task.\n\nShortcomings:\n1. While the paper uses 3D environments from DeepMind lab, actual experiments in the paper employ a 12D agent state as input to the policies. Thus, in my view, the paper is actually only solving a 2D problem (even though Fig 1 shows a first-person image). If my understanding about the problem setup is correct, I wonder how would a hand-crafted transition function based on the map do -- we already know where is the free space, the starting location, the goal location, and the fixed scaling between the actual space and the map, can't we build a conservative transition model based on this information? How will such a hand-crafted solution compare? Conceptually, what is the utility of learning on top of such a hand-crafted transition function?\n\n2. I found it challenging to understand the precise model. Section 3.2 is somewhat confusing: are we learning a policy \\pi_t that mimics the outcome of a monte-carlo tree search? How are the functions $h_\\psi$ and $f_\\phi$ trained? What are $W_\\phi$ in Figure 2? Without these details it is hard to fully understand the proposed model.\n\nIn summary, I am not convinced of the experimental setup being used to study the proposed approach. The proposed approach hasn't been described clearly enough to allow for a proper review.\n\nUpdate: I thanks the authors for preparing a response and for providing additional experiments. I believe these additional experiments will benefit the paper. However, these experiments will require a full re-evaluation of the paper which, in my view, is beyond the scope of a response to a rebuttal.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6Jb1uqgD4XI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n## Summary \n\n - The authors propose a method for \"zero-shot navigation\" that learns to navigate mazes from a map of the maze and the start and goal location in the maze. \n\n## Strengths\n\n - This work builds on previous work in similar environment setups such as \"Learning to Navigate in Complex Environments\" (Mirowski et. al. 2017) to the \"zero-shot\" case, i.e., where the agent need not do any exploration when presented with a new environment but can immediately navigate to the goal. \n\n## Weaknesses\n\n - My major concern about this work is that I just don't understand why this is a hard problem. You argue that \"one cannot simply perform graph search on the 2-D map\" but I fail to see why. Any classical planning method would have no trouble generating a plan for agent navigation from the 2-D map provided. The problem then, it seems to me, is reconciling the plan on the 2-D map with the actions that are needed to be taken in the actual environment. But given that there is a deterministic scaling between occupancy grid map and the agent world (\"Each cell on the abstract map corresponds to 100 units in the agent world.\") AND your agent's transition function is deterministic, then this problem is solvable zero-shot with a traditional planner (e.g. one based that generates a roadmap and then searches it but others would work)  and then executing the plan. Learning the dynamic model is also straightforward because you assume that you can directly observe the the joint state $o_t$.  \n\n - Related to the above, you refer to the 2-D map as \"abstract\" but I fail to see what's abstract about it. It is a metric occupancy grid map that gives you full information about the layout of the environment. \n\n - As a result, my impression is that the solution is \"over-engineered\". There are many complex components and \"hyper\" models when something much simpler would have easily solved this problem. \n\n## Minor Questions/Comments\n\n - At the onset you frame with this work with the classical SLAM literature, but this seems puzzling since you are providing the agent with both the map, and its initial location within the map, so both the mapping and localization are solved. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "41ejbm5DVG2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[EDIT AFTER DICUSSIONS] I thank the authors for their answer to my comments. I agree with the summary of the Area Chair and do not wish to modify my score.\n[/EDIT]\n\n##########################################################################\nSummary:\nThis paper presents addresses the problem of zero-shot navigation in environments with novel layouts.  It introduces two approaches (MMN a model-based approach based on Monte-Carlo Tree Search, and MAH, a model-free approach based on Deep-Q networks). The paper also introduces n-step relabelling as a way to leverage failed trials and make learning more efficient. Experiments on the DeepMind Lab environment show that both methods perform well against a random baseline and that MAH extends better to larger maps.\n\n##########################################################################\nReasons for score: \nThis paper presents a novel approach to an interesting problem. The method is sound and the approach rigorous. On the downside, an important claim of the paper is that the method is more generalizable than the latest work on this topic (Brunner et al. 2018) but this claim would have been stronger if supported with evidence, in particular with stronger baselines and more tasks.\n\n ##########################################################################\nPros:\n\n- Clarity: the paper is well-structured, clear, and easy to read\n\n- Impact: the paper addresses an interesting problem, in particular trying to use a general approach that is not specific to map-based navigation\n\n- Rigor: the work presented in this paper is detailed and follows a clear methodology. Equations seem correct. The experimentation study is fairly detailed and the appendix provides significant details about the methods.\n\n##########################################################################\nCons: \n\n- No code is provided with the paper, making it hard for future work to use it as a baseline\n\n- The paper mentions Brunner et al. 2018 as reference work. This work seems to achieve significantly better performance, at the \"cost\" of using a more task-specific, map-based navigation approach.This raises a few questions:\n1. Could the authors have used Brunner et al. as a baseline for this work? Was the code available?\n2. The authors (rightfully) claim that their approach is more generic and may be more readily generalizable to other problems. This statement would be a lot stronger if they actually proved it in the paper, i.e. if they used the same technic to solve a different problem.\n3. The methodology used in Brunner et al. uses a larger variety of map sizes. The authors could have used this approach too to better evaluate their method.\n\n- The paper provides a simple external baseline (random).  Could other (external) stronger baselines have been used, such as asynchronous advantage actor-critic ((Mnih et al.,2016) or model-free episodic control (Blundell et al., 2016)?\n\n- The paper evaluates on a single task and could have been evaluated on more tasks to illustrate robustness to domain shifts, in particular in the light of the comment above regarding the generalization of the method. Examples include Jaco Arm, CoinRun, or the Surreal framework.\n\n#########################################################################\nSome typos: \n\n- Page 2: \"betweend\" in the first paragraph\n- Figures on page 6 are hardly legible on a printed version of the paper.  Try to make them larger maybe?\n- missing upper cases in some references (e.g. POMDPs)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of 2D point-goal navigation in novel environments given access to an abstract occupancy grid map of the environment, together with knowledge of the agent's state and the goal location typical of point-goal navigation. The paper proposes learning a navigation policy in a model-based fashion, whereby the architecture predicts the parameters of the transition function and then uses this learned transition function to plan the agent's actions. The authors also describe a model-free approach that extends a version of DQN to reason over the 2D maps.

The paper was reviewed by four knowledgeable referees, who read the author response. The general problem of learning to navigate a priori unknown environments to reach a desired goal is an interesting problem that has received significant attention of-late in the learning community. In its current form, however, the paper does not adequately convey why this is a difficult problem that can not be solved using existing planning techniques or why it benefits from learning, particularly given access to an abstract map. These concerns apply more generally to point-goal navigation, namely the assumption that the pose of the agent and goal are fully known throughout (or the agent-relative pose of the goal) and that there is no uncertainty in the agent's motion. The practicality of these assumptions is unclear, and they are inconsistent with decades of research in robotics and robot learning, which addresses the more realistic setting in which there is uncertainty in pose and motion. The author response helps to clarify some of these questions, but it is still not fully clear why existing methods are insufficient for this task, whether they use traditional planning methods or are learned. Revisiting the discussion of why this is a hard problem would strengthen the paper, as would a more thorough evaluation that compares against other baselines.
Decision: Reject