Benchmarking Classic and Learned Navigation in Complex 3D Environments

  • 2019-01-30 15:50:54
  • Dmytro Mishkin, Alexey Dosovitskiy, Vladlen Koltun
  • 37

Abstract

Navigation research is attracting renewed interest with the advent oflearning-based methods. However, this new line of work is largely disconnectedfrom well-established classic navigation approaches. In this paper, we take astep towards coordinating these two directions of research. We set up classicand learning-based navigation systems in common simulated environments andthoroughly evaluate them in indoor spaces of varying complexity, with access todifferent sensory modalities. Additionally, we measure human performance in thesame environments. We find that a classic pipeline, when properly tuned, canperform very well in complex cluttered environments. On the other hand, learnedsystems can operate more robustly with a limited sensor suite. Both approachesare still far from human-level performance.

 

Quick Read (beta)

Benchmarking Classic and Learned Navigation in Complex 3D Environments

Dmytro Mishkin
Czech Technical University
Work done during an internship at Intel Labs. Contact email address: [email protected]. Project web page: https://sites.google.com/view/classic-vs-learned-navigation.
   Alexey Dosovitskiy
Intel Labs
   Vladlen Koltun
Intel Labs
Abstract

Navigation research is attracting renewed interest with the advent of learning-based methods. However, this new line of work is largely disconnected from well-established classic navigation approaches. In this paper, we take a step towards coordinating these two directions of research. We set up classic and learning-based navigation systems in common simulated environments and thoroughly evaluate them in indoor spaces of varying complexity, with access to different sensory modalities. Additionally, we measure human performance in the same environments. We find that a classic pipeline, when properly tuned, can perform very well in complex cluttered environments. On the other hand, learned systems can operate more robustly with a limited sensor suite. Both approaches are still far from human-level performance.

1 Introduction

Agile navigation in complex three-dimensional environments is a crucial capability for an intelligent agent operating in the physical world. To achieve true autonomy, the agent should effectively and robustly navigate not only in areas that have been mapped in advance, but also when deployed in previously unseen environments.

Autonomous navigation has a long history in robotics and computer vision. A classic approach is to design a modular pipeline that decomposes the problem into a sequence of sub-tasks, such as mapping, localization, planning, and low-level control. Each of the sub-tasks can then be addressed separately with an appropriately engineered solution. Methods of this type have been successfully deployed on a variety of mobile robotic platforms [38, 4, 17].

Despite decades of research, existing robotic navigation algorithms are still less robust, generalizable, and scalable than navigation strategies employed by animals. This motivates the recent surge of interest in applying learning techniques to navigation. Learning-based approaches, in contrast with prior classic methods, do not require extensive hand-engineering, but rather promise to learn the full navigation system directly from data. Potentially, a learning method can optimally exploit regularities in the data and therefore achieve performance superior to hand-crafted systems. Indeed, deep convolutional networks trained end-to-end with reinforcement learning have demonstrated promising progress on a variety of navigation tasks [28, 27, 6].

Classic pipeline Learned agent
Figure 1: Success and failure cases of a classic navigation pipeline (left) and a learned agent (right). Starting position denoted by an orange triangle, the goal by a green sphere, the agent’s path by a thick solid line, and the shortest path by a thin dotted line. Top: classic system successfully recognizes obstacles and navigates around them, while the learned agent tries to go straight for the goal ignoring the obstacles. Bottom: the localization module of the classic pipeline fails in a textureless narrow corridor, while the learned agent succeeds.
Task No GT map No GT pose Continuous state Locomotion
DPF, PF-net [19, 21] Localization no yes yes no
ANL [9] Localization no yes no yes
MapNet [16] Mapping yes yes no no
EgoSM [43] Mapping yes no yes no
VIN, GPPN [36, 26] Planning no no no yes
QMDP-Net, MACN [20, 22] Planning no yes no yes
CogMap [15] Navigation yes no no yes
Neural Map [31] Navigation yes no yes yes
SPTM [33] Navigation video yes yes yes
General RL [18, 11] Navigation yes yes yes yes
This paper Navigation yes yes yes yes
Table 1: Learning-based approaches to mapping, localization, planning, and navigation. Most approaches are not applicable to autonomous navigation in previously unseen environments because they rely on unrealistic assumptions.

Given these two classes of navigation approaches – classic modular pipelines and end-to-end learned models – a natural question arises: How do the two types of approaches compare to each other? Does one dominate the other? Or do both methodologies have characteristic strengths and weaknesses? The answers to these questions are not known, since the two lines of research have been largely incompatible in terms of application areas and evaluation protocols. Classic navigation approaches have been typically deployed on custom robotic platforms or in small-scale simulations, complicating extensive reproducible experimentation. In contrast, new learning-based methods are usually evaluated in specialized simulated environments [28, 34, 15, 16, 41]. Due to these methodological differences, direct comparison has not been undertaken.

In this paper, we take a step towards coordinating and reconciling the two directions of navigation research by performing a fair and thorough comparison of classic modular and learned methods. To this end, we set up approaches of both types in simulated indoor environments. We use a basic navigation setup where the position of the goal relative to the agent is known at every time step. We evaluate the methods on environments of different types (empty vs furnished, synthetic vs scanned) and with different sensory modalities provided to the agents (none, RGB, or RGB-D).

Our experiments show that the classic pipeline is generally strong and, when provided with RGB-D input, outperforms learned approaches by a large margin in cluttered and visually rich environments (Figure 1, top). However, the learning-based agent is more robust when the sensor suite is restricted to color images and in poorly textured areas (Figure 1, bottom). Given the complementary strengths of classic and learned approaches, we expect that hybrid systems combining the best of both worlds will be most successful in the future.

2 Related Work

Navigation research has a long history in robotics [5, 37]. A typical navigation pipeline consists of several modules responsible for sub-tasks of the navigation problem: mapping the environment, localizing the agent against the map, planning a path given the map, and following this path. Each sub-task has been studied extensively. Mapping and localization are typically treated jointly as the simultaneous localization and mapping (SLAM) problem. Most SLAM methods are based on metric maps [12, 7], although topological methods have been developed as well [14]. A survey of classic planning methods is provided by LaValle [25]. Classic navigation pipelines have been deployed on a variety of robotic platforms, including wheeled [38], legged [17], and aerial [4].

The navigation problem has also been addressed by learning-based approaches. Navigation can be interpreted within the framework of reinforcement learning (RL) and addressed with general-purpose RL algorithms [28, 27, 18, 11, 44, 34, 13, 40, 6]. Extending RL agents with specialized memory architectures allows for implicit mapping [30, 31]. While RL-based approaches have demonstrated impressive human-level navigation in maze-like environments [13], they may require a prohibitive number of training samples to reach this performance (up to billions [13]) and have only shown limited success when deployed in previously unseen realistic large cluttered indoor environments [34, 40].

In this line of research, most related to our work is the technical report of Bhatti et al[3]. The authors experiment with providing the output of a SLAM algorithm to an RL agent operating in a simulated 3D environment. However, the evaluation is constrained to a single task in a single small unrealistic environment. In contrast, we conduct experiments in multiple large realistic cluttered environments with a proper train/validation/test split. Moreover, we do not only use a SLAM algorithm, but a full navigation pipeline including path planning and locomotion.

Figure 2: Our modular navigation pipeline. Navigation is decomposed into 4 sub-tasks: mapping, localization, planning, and locomotion. The mapping module outputs a two-dimensional obstacle map of the environment. The localization module estimates the agent’s pose. Together, these are used to plan a path to the goal. Given the planned path, the locomotion module selects an action to follow the path.

An alternative to using general RL architectures is to accept the classic decomposition of the navigation problem and learn specialized modules for localization, mapping, and planning. For mapping, learning of both metric [15, 16, 43] and topological [33] maps has been explored. Localization has been addressed with methods based on Bayes filters [9], including particle filters  [19, 21]. Finally, learning for planning has been studied both in the fully observable scenario [36, 26] and under partial observability [20, 22]. For each task, learning-based approaches have been shown to outperform their hand-crafted counterparts in certain conditions.

However, as summarized in Table 1, each of these works makes unrealistic assumptions about the discrete nature of the state space, availability of the ground-truth map or the agent’s pose, or prior experience with the environment. Therefore, to our knowledge, none of these methods can currently address the realistic autonomous navigation problem we are studying: reaching goals in a previously unseen environment in a continuous state space and without any ground truth information. We expect future research to overcome these limitations and hope that our work will stimulate the development of practical learning-based navigation pipelines.

3 Methods

3.1 Classic modular navigation pipeline

Modular navigation pipelines have been widely used in robotics for decades, yet it is difficult to find a complete functional implementation that could be readily deployed in simulated environments. We therefore implement our own solution, illustrated in Figure 2. Following standard practice, we decompose the navigation problem into a sequence of sub-tasks: localization, mapping, planning, and locomotion. Each of these sub-tasks is solved by a separate module based on established algorithms. We now describe each module. Further details on all modules are provided in the supplement.

Figure 3: Illustration of the mapping and planning modules of the classic pipeline. A local map is generated by reprojecting the depth map to the top view and binning. Using the estimated agent’s pose, the local map is integrated into the global map. The global map is used to plan a path towards the goal.

Localization. The objective of the localization module is to estimate the pose of the agent in the environment. To achieve this, we use ORB-SLAM2, a popular real-time SLAM library [29]. We experiment with two variants of the method: accepting only a color image as input at each step (RGB) or accepting a color image and a depth map (RGB-D). Given the inputs, the algorithm maintains a sparse keypoint-based map of the environment and at each step outputs an estimated 6-DOF metric camera pose. The camera pose estimated by ORB-SLAM2 is the output of the localization module. In case the algorithm fails (typically because tracking is lost due to difficulty of keypoint matching), it outputs a special “Failure” flag. In such case there are two options – try to re-localize on the existing map or reset the map. We found that in practice the latter option gives better results and use that in our experiments. To resolve scale ambiguity in case of RGB-only input, we perform a hard-coded initialization procedure making use of the known height of the agent.

Mapping. The mapping module estimates a two-dimensional obstacle map (Figure 3, middle) that can be used by the planner to find a path towards the goal. We use maps with a fixed cell size, 10x10 cm in our experiments. We use two different mapping strategies depending on the availability of a depth sensor.

When depth maps are available, we re-project the observed points to the top view and discard points above the agent’s height and on the ground level. We then bin the points into map cells. Each cell stores the maximum number of points ever binned into it. Map cells that contain more points than a fixed threshold are marked as occupied. An advantage of implementing mapping separately from SLAM is that the module could easily be extended with learnable components.

If depth map is not provided, we instead use the sparse 3D point cloud predicted by ORB-SLAM. The rest is identical to the depth-based mapper, except that the threshold for a cell to be counted as an obstacle is set to a lower value. The thresholds are tuned on the training set.

Figure 4: A schematic visualization of Belief DFP. Instead of directly regressing future measurements, we predict maps of the expected future location of the agent. By computing the dot product of these belief maps with the measurement maps, we get the predicted measurement values. In practice, we use measurement maps that encode the Euclidean distance to the goal.

Planning. Given the 2D obstacle map generated by the mapping module, the agent’s pose (estimated by the localization module), and the goal location relative to the agent, we plan a trajectory to the goal (Figure 3, right). We pose path planning as finding the shortest path in the graph corresponding to the map: each traversable cell is a node, with 8-neighbor connectivity and diagonal edges weighted by 2. Since the environment is partially observable, the trajectory needs to be updated every time the map changes (for the purposes of planning, non-observed cells are considered traversable). We employ the D* Lite algorithm [24] that is specifically designed to perform efficiently in this dynamic scenario. When planning for the first time, it is identical to the A* algorithm. For subsequent re-planning, D* Lite only updates the costs of the nodes that are affected by newly discovered obstacles.

Locomotion. Finally, the locomotion module takes as input the planned path and generates an action to follow this path. A standard solution would use a proportional-integral-derivative (PID) controller. However, a PID controller normally requires a continuous action space, whereas in environments we are experimenting with the action space is severely discretized and consists of only three commands: move forward, turn left, and turn right. We therefore design a simple custom rule-based controller inspired by PID. We first select a waypoint on the planned path at a fixed distance d1 meters from the agent. If the agent’s orientation is not within ϕ degrees from the direction to the waypoint, the agent rotates towards the waypoint. Otherwise, the agent goes forward. If the distance to the waypoint is below d2 meters, a new waypoint is selected. If the planned path changes, the waypoint position is updated accordingly. Parameters d1, d2, and ϕ are tuned on the training set.

3.2 End-to-end learned agent

In this work we use Direct Future Prediction (DFP) [11] as the base end-to-end navigation algorithm, since this method is easy to implement and has been shown to perform well on navigation in 3D environments [11, 34], even when compared to more complex algorithms such as UNREAL [18]. The key idea of DFP is to learn sensorimotor control by predicting future values of behaviorally relevant quantities – measurements – via supervised learning. We now briefly describe the algorithm and refer the reader to Dosovitskiy & Koltun [11] for further details.

Consider an agent interacting with an environment in discrete time. At each time step t the agent receives from the environment an observation 𝐨t=𝐬t,𝐦t that includes (typically high-dimensional) raw sensory information 𝐬tds and a (typically low-dimensional) vector of measurements 𝐦tdm. The key assumption of DFP is that the agent’s objective function can be formulated as a function of future measurements ut=U(𝐦>t),𝐦>t=𝐦t+1,𝐦t+2,. The idea of the algorithm is to use a parametric function approximator F(,𝜽) with parameters 𝜽 to estimate the expected future measurements for each possible action 𝐚 from a discrete action set 𝒜da :

𝐦^>t𝐚=F(𝐨t,𝐚,𝜽). (1)

Action selection then amounts to evaluation of the objective function on each of the predictions and choosing the optimal one:

𝐚t=argmax𝐚𝒜U(F(𝐨t,𝐚,𝜽)). (2)

In practice, we predict future measurements only for several future time steps, and output predictions for all possible actions at once by a single deep network. We predict the distance and the direction to the goal, with the direction represented by its sine and cosine.

Figure 5: Examples of action-conditional expected position maps predicted by the BDFP agent on Matterport3D. When facing free space (top), the agent expects to move forward, turning left or right depending on the action. When facing an obstacle (bottom), the agents expect to go around it on the left or on the right, but fails to predict different consequences of different actions.

3.2.1 Interpretable learning with Belief DFP

The basic version of DFP described above can learn navigation in 3D environments [11]. However, the resulting policy is black-box and therefore difficult to interpret. Since we are interested in better understanding the behavior of different types of navigation policies, we designed Belief DFP (BDFP) – a variant of DFP that is tailored to the navigation task and provides additional insight into the inner workings of the policy. The architecture is inspired by deep networks with attention, as well as the successor representation [10] and successor features [2] in RL.

A schematic visualization of BDFP is shown in Figure 4 and its operation is illustrated in Figure 5. Future measurement prediction is decomposed into two steps. First, for each available action 𝐚𝒜 the agent predicts belief maps 𝐁t,τ𝐚 of the expected agent’s position after τ time steps when taking action 𝐚 at the current time step t. We then compute the dot product of the predicted belief maps with the measurement map 𝐌t containing measurement values associated with each position: 𝐦^t+τ𝐚=𝐁t,τ𝐚𝐌t. These dot products are used as future measurement predictions in DFP. Both maps are represented in the agent’s egocentric coordinate system, with the agent located in the center of the map, facing right. For the navigation task, we set the measurement maps 𝐌t to store the Euclidean distance to the goal, which can be trivially computed given the location of the goal relative to the agent. Therefore, the dot product equals the expected distance to the goal. We select the action that minimizes this expected distance.

BDFP can be trained in the same way as standard DFP – by imposing a loss on the prediction of future measurements. However, we can additionally train the expected future position maps directly, assuming we have access to the corresponding ground truth at training time. We use both these losses in our experiments. Further details are provided in the supplement.

4 Experiments

4.1 Experimental setup

Environment.

We use the MINOS simulator [34] as our evaluation platform. We experiment with environments of two types. The first type are synthetic house models from the SunCG dataset [35]. Environments are relatively simplistic, but the size and the diversity of the dataset allow for reliable experimentation. We use two variants of SunCG: with furniture (“Furnished”) and with all furniture removed (“Empty”). The second type of environments are 3D reconstructions of real indoor spaces from the Matterport3D dataset [8]. This type of data is more realistic both in terms of visual quality and the environment layout and clutter, but the dataset is relatively small – 90 environments in total.

The agent in MINOS is represented by a cylinder with radius of 0.1 m and height 1.09 m. The environments are flat, therefore the agent’s pose can be represented by its 2D position and orientation. Both are continuous. The action space is discrete and consists of 3 actions – go forward, turn left, turn right – which apply, respectively, linear or angular force to the agent. Sensory input includes rendered RGB frames and depth maps at resolution 256x256 pixels for the classic agent and 128x128 for the learned ones. ORB-SLAM does not detect enough keypoints on smaller images, while RL agents do not benefit from higher resolution. The depth maps provide accurate depth information in the range of [0.001, 4.0] meters.

We use the train/validation/test split of environments from the MINOS repository, but we filter out the episodes for which the simulator is unable to compute the shortest path to the goal, as the shortest path is needed to compute some of our evaluation metrics. During training, start and goal positions are randomly generated. In SunCG, texture randomization is applied. For validation and test we use fixed sets of start-goal pairs for each map. We evaluate for 100 episodes on Matterport3D (20 start-goal pairs per map) and for 340 episodes on each of SunCG variants (10 start-goal pairs per map).

SunCG Empty SunCG Furnished Matterport3D
Small Medium Small Medium Small Medium
UNREAL [34] 72.9 63.2 64.1 45.3 38.0 20.0*
DFP [34] 80.3 64.1 64.5 43.6 27.3 18.2*
Ours-DFP 74.5 52.0 64.5 46.7 - 41.0*
Ours-BDFP 78.1 55.0 60.0 47.9 - 41.0*
Table 2: Comparison of learned navigation approaches in MINOS. We report average success rate. Our DFP implementation performs on par with previously reported results. Belief DFP slightly outperforms vanilla DFP. *The exact set of environments and start-goal pairs used for evaluation on Matterport3D is not identical, which may account for part of the performance difference.

Task. We address goal-directed navigation with known position of the goal relative to the agent (PointGoal, according to the terminology of Anderson et al[1]). We chose this simplest scenario over alternative goal specification (for instance, by object class or by room type) to ensure that our evaluation focuses specifically on the navigation capabilities of agents, not semantic understanding of the environment. The PointGoal task is far from trivial: without any prior knowledge of the environment, the agent needs to find the shortest possible path to the goal, avoid obstacles, and backtrack when facing a dead end.

The task is set up as a sequence of goal-directed navigation episodes. In each episode the agent has to reach a fixed goal position from its initial location, given a limited time budget (50 seconds in our experiments, which corresponds to 500 actions). The episode ends after the time budget has elapsed or when the agent takes the special “Done” action. Since the distance to the goal is provided to all agents, we use a simple threshold on this value to output the “Done” action. The agent does not carry any memory across episodes. That is, in the beginning of each episode it has no prior knowledge of the environment and has to explore the environment while navigating towards the goal. The goal position relative to the agent is provided as a two-dimensional vector in the agent’s egocentric coordinate system (in practice, we represent the vector in polar coordinates). Note that this vector is insufficient to globally localize the agent relative to the goal: the agent has three degrees of freedom (2 for the position and 1 for the orientation), while the vector to the goal only provides two values.

We use three evaluation metrics in our experiments: success rate (SR), success weighted by path length (SPL) [1], and “pace”. Success rate is simply the fraction of the episodes in which the agent reaches the goal within the time budget. SPL factors in the length of the path taken by the agent: each successful episode contributes to the score proportionally to the ratio of the shortest path to the executed path. Finally, pace considers time taken to reach the goal: it is the average fraction of the time budget the agent has left at the end of an episode. Detailed definitions are provided in the supplement. In what follows we report all metrics in %. Value of each of the metrics is between 0% and 100% and for all of them higher values are better.

Model details. All learned modules are implemented by deep networks using the PyTorch framework [32]. Potential inputs to the models are: color image, depth map, actions from previous steps, distance to the goal, and the direction to the goal. For each input, we feed a stack of 4 most recent observations to the agent. Color and depth inputs are processed by convolutional networks, while actions and goal information are processed by fully connected networks. The outputs of these feature extractor networks are concatenated and fed into a two-stream fully connected action-expectation network (see Dosovitskiy&Koltun [11]). This network outputs the future measurement predictions for all actions and future time steps at once. For BDFP, the expected position maps have resolution 25×25 and are predicted with fully connected layers.

We train the models with the Adam [23] optimizer with learning rate 1e-5, standard momentum, and mini-batch size 32. We train for a total of 5 million environment steps, corresponding to 5.8 days of real-time experience. Learning rate is divided by 3 every 2M steps. Four simulators are run in parallel. During training we execute an ϵ-greedy policy, starting with the probability of random action ϵ=0.95, linearly decayed to ϵ=0.1 at the end of the training. We have experimented with other training setups (longer training runs of 8-10M samples, different learning rates, exploration schedules, network architectures), but have not observed significant performance improvements. Further training details are provided in the supplement.

SunCG Empty SunCG Furnished Matterport3D Mean
Classic Learned Classic Learned Classic Learned Classic Learned
Blind 52.3 52.9 44.4 13.8 40.9 27.7 45.9 31.4
RGB 9.4 49.9 4.4 44.8 4.7 37.4 6.1 44.0
RGB-D 65.7 54.6 67.7 47.2 70.2 45.5 67.9 49.1
RGB-D + GT pose 82.5 84.5 78.8 82.0
RGB-D + GT pose & map 81.8 81.5 85.1 82.8
Table 3: Performance of a classic modular pipeline and a learned agent when provided with different input modalities. We report Success weighted by Path Length (SPL), as proposed by Anderson et al[1]. For each environment and sensory input, the best of the two results is highlighted in bold. Classic pipeline performs well when provided with RGB-D input, but fails with RGB only.

4.2 Results

Comparison to prior learning methods. We start by comparing our implementation of learned agents with prior results reported in the literature. We restrict the comparison to general RL algorithms, since, as explained in Section 2, none of the existing navigation-specific learning approaches can be deployed in our realistic navigation scenario. Table 2 shows that our DFP implementation generally performs on par with the results reported by Savva et al. [34], and Belief DFP outperforms its vanilla counterpart in all cases except one. Motivated by these results, in what follows we use BDFP as the main learning method.

Classic pipeline

Learned agent

Figure 6: Visualization of the trajectories of classic (top) and learned (bottom) agents in three navigation episodes. Trajectories of the classic agent are far from optimal, but do reach the goal in the end. The learned agent fails to navigate around obstacles. The supplementary video shows additional qualitative results.

Classic vs learned navigation. We now turn to the main subject of this work: comparing classic and learned algorithms. We evaluate the modular pipeline and BDFP on three environment types of increasing difficulty: SunCG Empty, SunCG Furnished, and Matterport3D. Moreover, we experiment with providing different modalities as input to the agents: “blind” agents only get the direction and distance to the goal, “RGB” also get color images, and “RGB-D” additionally get depth maps. Furthermore, to estimate the potential for improvement, we evaluate two more setups with ground truth information provided to the agent: agent’s pose or both agent’s pose and a map of the environment. The resulting SPL scores are reported in Table 3 and other metrics are provided in the supplement. These results lead to several interesting conclusions.

SunCG Empty SunCG Furnished Matterport3D
Classic Learned Human Classic Learned Human Classic Learned Human
SPL 65.7 54.6 90.5 67.7 47.2 87.9 70.2 45.5 86.7
Success rate 70.2 56.4 97.0 75.0 48.2 100.0 75.0 47.0 95.3
Pace 57.8 47.9 84.0 58.3 39.0 82.8 56.2 36.6 72.6
Table 4: Comparison to human performance on different navigation performance metrics. For all metrics, higher is better and the best possible result is 100%. Both algorithms get RGB-D input, while the human navigates using RGB images only. Human performance surpasses both algorithms in all environments and metrics. In the most complex environments (Matterport3D), the advantage over the classic pipeline is the smallest.

First, the “blind” classic agent is surprisingly successful, achieving SPL of 40-50% in all environments. This algorithm simply follows the straight path towards the goal, and the degree of its success suggests that many of the goals are reachable with this naive strategy. We believe this agent should serve as a basic baseline for the PointGoal task, not a randomly acting agent as evaluated by Savva et al. [34].

Second, the classic pipeline performs well with RGB-D input, but fails with RGB only. The reason is the performance of the SLAM system. When only provided with color images, the algorithm struggles under our conditions, which feature predominantly purely rotational or purely forward motion, often in presence of poorly textured surfaces. As a result, instead of moving towards the goal, the agent spends time repeatedly re-initializing SLAM (including the time-consuming procedure for scale estimation). The addition of depth input dramatically robustifies the method, allowing for reliable localization.

Third, the performance of the classic method improves for more complex cluttered environments. The explanation is that the more objects are in the environment, the easier it is for the SLAM algorithm to find reliable keypoints and localize reliably. Still, providing ground truth pose to the classic method brings substantial (8-16%) further improvement compared to RGB-D input. A ground truth map adds another 6% SPL in Matterport3D environments. These numbers suggest that the localization and mapping modules can still be improved. Counter-intuitively, in SunCG environments planning with the ground truth map leads to worse performance than using the mapping module. We believe this is caused by imperfections in the maps provided by MINOS (for instance, the maps do not include some doors that block entryways).

Finally, the learned approach only marginally outperforms the “blind” classic method and always performs much worse than the classic pipeline with RGB-D input. This poor performance may be explained by the lack of an appropriate memory structure capable of maintaining an internal representation of the environment. Another hypothesis is that reinforcement learning methods may require longer training time to reach optimal performance: we train for 5 million time steps (corresponding to 5.8 days of real-time experience), while some state-of-the-art RL systems take up to a billion time steps (corresponding to years of real-time experience) [13]. We hope these results will stimulate the development of performant and sample-efficient learned navigation algorithms.

Figure 6 shows qualitative navigation results. We plot trajectories executed by the agents, as well as the shortest path to the goal. Trajectories of the classic method are not smooth and are often far from the shortest path, but the agent eventually reaches the goal by avoiding obstacles and backtracking from dead ends. In contrast, the trajectories of the learned agent are smooth, but the agent often gets stuck near obstacles and is typically unable to make progress towards the goal after that. We encourage the reader to watch the supplementary video for additional qualitative results.

Figure 7: Performance of algorithms on Matterport3D as a function of the length of the shortest path to the goal. We plot cumulative success rate. That is, for a value L on the x-axis we plot the average success rate in all episodes where the shortest path to the goal was shorter than L.

Human baseline and different metrics. We now compare the two artificial navigation systems with a human. To this end, a human subject performed 43 navigation trials in Matterport3D and 68 trials each in SunCG Empty and Furnished. We made the comparison as fair as possible: the human subject used the exact same action frequency and action space as the artificial systems, and has to navigate based on 128x128 pixel RGB images. One remaining inevitable advantage of the human is that when evaluating several start-goal pairs in the same environment, there is a chance that the human remembers the environment layout from previous trials. Based on self-report, we do not expect this to significantly affect the performance.

The results are summarized in Table 4. We evaluate three metrics: success rate, SPL, and pace. Human performance exceeds that of algorithms in all environments and metrics, even though the human is navigating based on color images only, without depth. Interestingly, in the most challenging Matterport3D environment the advantage is the smallest: SPL of 86.7% versus 70.2% for the classic pipeline. Overall, all three metrics are correlated across different agents and environments. In particular, the ranking of the results – learned, classic, human – is consistent for all metrics in all environments.

Figure 7 shows the dependence of the success rate of different agents on the length of the shortest path to the goal in Matterport3D. (Plots for other environments and metrics are shown in the supplement.) As expected, the success rate of all methods drops for goals that are further away. Human performance is most stable, exceeding even the classic agent with access to ground truth pose and map. Learned RGB-D agent is only slightly better than the “blind” baseline.

Somewhat counter-intuitively, human outperforms even the classic agent that has access to ground truth map and camera pose. This is for two main reasons. First, maps provided by MINOS are imperfect: for instance, some doors that are present in the environment are not in the maps. Second, the locomotion controller, which converts the planned path to the actual motor commands, is not always able to perfectly track the optimal planned path. This can be especially critical in confined spaces and narrow corridors. The design of the locomotion controller is non-trivial, since the state space is continuous, while the action space is severely discretized.

5 Conclusion

We have benchmarked a representative classic modular navigation pipeline against recent navigation approaches based on reinforcement learning and against a human operator. This evaluation led to several surprising findings.

First, the classic pipeline shows very strong performance when provided with RGB-D input. It outperforms the learned agent by a large margin, especially in complex cluttered environments. However, the classic method is sensitive to the set of modalities provided as input: without access to depth information it fails catastrophically.

Second, the learned agent generally performs poorly, only slightly better than a simple baseline that cuts directly to the goal. On the other hand, unlike the classic system, the learning approach does not exhibit catastrophic failure when provided with RGB-only input.

Lastly, even given RGB-D input, the ground truth agent’s pose, and the environment map, both algorithms perform worse than a human using only low-resolution color images.

These results suggest that there is still significant room for improvement in artificial navigation algorithms. We believe that a particularly promising direction of research is combining ideas from classic navigation with learning. We hope that our work will stimulate the development of such hybrid navigation systems.

Acknowledgements. Dmytro Mishkin was partially supported by the Austrian Ministry for Transport, Innovation and Technology, the Federal Ministry of Science, Research and Economy, and the Province of Upper Austria in the frame of the COMET center SCCH, and the CTU student grant SGS17/185/OHK3/3T/13.

References

  • [1] P. Anderson, A. X. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V. Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savva, and A. R. Zamir. On evaluation of embodied navigation agents. arXiv:1807.06757, 2018.
  • [2] A. Barreto, W. Dabney, R. Munos, J. J. Hunt, T. Schaul, H. P. van Hasselt, and D. Silver. Successor features for transfer in reinforcement learning. In Neural Information Processing Systems (NIPS), 2017.
  • [3] S. Bhatti, A. Desmaison, O. Miksik, N. Nardelli, N. Siddharth, and P. H. S. Torr. Playing Doom with SLAM-augmented deep reinforcement learning. arXiv:1612.00380, 2016.
  • [4] M. Blösch, S. Weiss, D. Scaramuzza, and R. Siegwart. Vision based MAV navigation in unknown and unstructured environments. In International Conference on Robotics and Automation (ICRA), 2010.
  • [5] F. Bonin-Font, A. Ortiz, and G. Oliver. Visual navigation for mobile robots: A survey. J. Intell. Robotics Syst., 53(3):263–296, 2008.
  • [6] J. Bruce, N. Sunderhauf, P. Mirowski, R. Hadsell, and M. Milford. Learning deployable navigation policies at kilometer scale from a single traversal. In Conference on Robot Learning (CoRL), 2018.
  • [7] C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. D. Reid, and J. J. Leonard. Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age. Transactions on Robotics (T-RO), 32(6):1309–1332, 2016.
  • [8] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Niessner, M. Savva, S. Song, A. Zeng, and Y. Zhang. Matterport3D: Learning from RGB-D data in indoor environments. In International Conference on 3D Vision (3DV), 2017.
  • [9] D. S. Chaplot, E. Parisotto, and R. Salakhutdinov. Active neural localization. In International Conference on Learning Representations (ICLR), 2018.
  • [10] P. Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 1993.
  • [11] A. Dosovitskiy and V. Koltun. Learning to act by predicting the future. In International Conference on Learning Representations (ICLR), 2017.
  • [12] H. F. Durrant-Whyte and T. Bailey. Simultaneous localization and mapping: Part I. Robotics and Automation Magazine (RAM), 13(2):99–110, 2006.
  • [13] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, S. Legg, and K. Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In International Conference on Machine Learning (ICML), 2018.
  • [14] E. Garcia-Fidalgo and A. Ortiz. Vision-based topological mapping and localization methods. Robot. Auton. Syst., 2015.
  • [15] S. Gupta, J. Davidson, S. Levine, R. Sukthankar, and J. Malik. Cognitive mapping and planning for visual navigation. In Computer Vision and Pattern Recognition (CVPR), 2017.
  • [16] J. F. Henriques and A. Vedaldi. MapNet: An allocentric spatial memory for mapping environments. In Computer Vision and Pattern Recognition (CVPR), 2018.
  • [17] M. Hutter, C. Gehring, D. Jud, A. Lauber, D. Bellicoso, V. Tsounis, J. Hwangbo, K. Bodie, P. Fankhauser, M. Bloesch, R. Diethelm, S. Bachmann, A. Melzer, and M. A. Höpflinger. ANYmal - a highly mobile and dynamic quadrupedal robot. In Intelligent Robots and Systems (IROS), 2016.
  • [18] M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In International Conference on Learning Representations (ICLR), 2017.
  • [19] R. Jonschkowski, D. Rastogi, and O. Brock. Differentiable particle filters: End-to-end learning with algorithmic priors. In Robotics: Science and Systems (RSS), 2018.
  • [20] P. Karkus, D. Hsu, and W. S. Lee. QMDP-Net: Deep learning for planning under partial observability. In Neural Information Processing Systems (NIPS), 2017.
  • [21] P. Karkus, D. Hsu, and W. S. Lee. Particle filter networks with application to visual localization. In Conference on Robot Learning (CoRL), 2018.
  • [22] A. Khan, C. Zhang, N. Atanasov, K. Karydis, V. Kumar, and D. D. Lee. Memory augmented control networks. In International Conference on Learning Representations (ICLR), 2018.
  • [23] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
  • [24] S. Koenig and M. Likhachev. D* Lite. In National Conference on Artificial Intelligence, 2002.
  • [25] S. M. LaValle. Planning Algorithms. Cambridge University Press, 2006.
  • [26] L. Lee, E. Parisotto, D. S. Chaplot, E. Xing, and R. Salakhutdinov. Gated path planning networks. In International Conference on Machine Learning (ICML), 2018.
  • [27] P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell. Learning to navigate in complex environments. In International Conference on Learning Representations (ICLR), 2017.
  • [28] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. P. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning (ICML), 2016.
  • [29] R. Mur Artal and J. D. Tardós. ORB-SLAM2: An open-source SLAM system for monocular, stereo and RGB-D cameras. In Transactions on Robotics (T-RO), 2017.
  • [30] J. Oh, V. Chockalingam, S. P. Singh, and H. Lee. Control of memory, active perception, and action in Minecraft. In International Conference on Machine Learning (ICML), 2016.
  • [31] E. Parisotto and R. Salakhutdinov. Neural map: Structured memory for deep reinforcement learning. In International Conference on Learning Representations (ICLR), 2018.
  • [32] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in PyTorch. In NIPS Workshops, 2017.
  • [33] N. Savinov, A. Dosovitskiy, and V. Koltun. Semi-parametric topological memory for navigation. In International Conference on Learning Representations (ICLR), 2018.
  • [34] M. Savva, A. X. Chang, A. Dosovitskiy, T. Funkhouser, and V. Koltun. MINOS: Multimodal indoor simulator for navigation in complex environments. arXiv:1712.03931, 2017.
  • [35] S. Song, F. Yu, A. Zeng, A. X. Chang, M. Savva, and T. Funkhouser. Semantic scene completion from a single depth image. Computer Vision and Pattern Recognition (CVPR), 2017.
  • [36] A. Tamar, S. Levine, P. Abbeel, Y. Wu, and G. Thomas. Value iteration networks. In Neural Information Processing Systems (NIPS), 2016.
  • [37] S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. The MIT Press, 2005.
  • [38] S. Thrun, M. Montemerlo, H. Dahlkamp, D. Stavens, A. Aron, J. Diebel, P. Fong, J. Gale, M. Halpenny, et al. Stanley: The robot that won the DARPA Grand Challenge. J. Robot. Syst., 2006.
  • [39] Y. Wu and K. He. Group normalization. In European Conference on Computer Vision (ECCV), 2018.
  • [40] Y. Wu, Y. Wu, G. Gkioxari, and Y. Tian. Building generalizable agents with a realistic and rich 3D environment. arXiv:1801.02209, 2018.
  • [41] F. Xia, A. R. Zamir, Z.-Y. He, A. Sax, J. Malik, and S. Savarese. Gibson Env: Real-world perception for embodied agents. In Computer Vision and Pattern Recognition (CVPR), 2018.
  • [42] B. Xu, N. Wang, T. Chen, and M. Li. Empirical evaluation of rectified activations in convolutional network. arXiv:1505.00853, 2015.
  • [43] M. Zhang, K. T. Ma, S.-C. Yen, J. H. Lim, Q. Zhao, and J. Feng. Egocentric spatial memory. In Intelligent Robots and Systems (IROS), 2018.
  • [44] Y. Zhu, R. Mottaghi, E. Kolve, J. J. Lim, A. Gupta, L. Fei-Fei, and A. Farhadi. Target-driven visual navigation in indoor scenes using deep reinforcement learning. In International Conference on Robotics and Automation (ICRA), 2017.

Supplementary Material

Appendix A Implementation Details

A.1 Classic agent

Localization. ORBSLAM2 and mapper parameters are shown in Table 5.

Because of monocular SLAM systems inherently output scale-less point cloud and the slam-to-world scale is typically set by detecting some kind of calibration pattern. Since the environment is unknown and there is no such pattern, we designed the following procedure for RGB-only case. After SLAM initialization, “look down” action is executed until the camera looks vertically down. Median y-coordinate of observed keypoints is linked to the (known) agent height, providing needed scale. Then the “look up” action is executed until horizontal orientation is recovered. This procedure takes some time from the total time budget of the episode (approximately 4 seconds in our experiments). In case of SLAM reset, the procedure needs to be done again.

Locomotion. Waypoint on the planned path at a fixed distance d1=0.5 meters from the agent is selected. If the agent’s orientation is not within ϕ=15 from the direction to the waypoint, the agent rotates towards the waypoint. Otherwise, the agent goes forward. If the distance to the waypoint is below d2=0.15 meters, a new waypoint is selected. If planned path changes, the waypoint position is updated accordingly. Finally, with probability p=0.1 random action is selected.

RGB-D RGB
Resolution 256x256 512x512
Max. #features 1000 5000
Min.FAST threshold 1 1
Obstacle Hmin [m] 0.1 0.1
Obstacle Hmax [m] 1.145 1.145
Points to create obstacle 128 30
Table 5: ORBSLAM2 agent parameters used in experiment.

A.2 Learned agent

Architectures of the feature extraction and action-expectation networks are shown in Tables 6,7, 8. We observed no benefit in color images compared to grayscale, so grayscale is used for all learned agents. All modalities are composed by stacking current and 3 previous inputs. We found that Group Normalization [39] makes training more stable and less sensitive to hyperparameters. In case of Belief DFP, each 16x16 belief map is normalized by softmax function.

Loss is MSE loss on measurements: distance to the goal, sin and cos of the direction to the goal. In case of Belief DFP additional MSE loss on belief map is applied.

Visual and depth networks, input = 128x128x4
Conv2d 9x9, 32 channels, stride = 4, pad = 0
LReLU(0.3), GN (4 groups)
Conv2d 3x3, 64 channels, stride = 2, pad = 1
LReLU(0.3), GN (8 groups)
Conv2d 3x3, 128 channels, stride = 2, pad = 1
LReLU(0.3), GN (8 groups)
Conv2d 3x3, 64 channels, stride = 1, pad = 1
LReLU(0.3), GN (8 groups)
Conv2d 8x8, 256 channels, stride = 1, pad = 0
Action history and measurements network, input = 4*3
Fully connected, 128
LReLU(0.3), GN (8 groups)
Fully connected, 128
LReLU(0.3), GN (8 groups)
Fully connected, 128
Goal network, input = 3
Fully connected, 128
LReLU(0.3), GN (8 groups)
Fully connected, 128
LReLU(0.3), GN (8 groups)
Fully connected, 128
Table 6: Feature networks architecture. GN stands for GroupNorm [39], LReLU(0.3) for max(x, 0.3x[42].
ExpectationNet
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 6*3
ActionNet
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 6*6*3
Table 7: Action-expectation networks architecture for plain DFP agents. GN stands for GroupNorm [39], LReLU(0.3) for max(x, 0.3x[42].
ExpectationBeliefNet
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 6*16*16
ActionBeliefNet
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 256
LReLU(0.3), GN (16 groups)
Fully connected, 6*6*16*16
Table 8: Action-expectation networks architecture for plain DFP agents. GN stands for GroupNorm [39], LReLU(0.3) for max(x, 0.3x[42].

A.3 Experimental setup

SunCG Empty SunCG Furnished Matterport3D
Figure 8: Performance of algorithms on SunCG Empty (left), SunCG Furnished (middle) and Matterport3D (right) as a function of the length of the shortest path to the goal. We plot cumulative success rate (top), cumulative SPL (middle) and cumulative pace (bottom).
Metrics.

We use three main evaluation metrics in our experiments: success rate, success weighted by path length (SPL) [1], and “pace” measuring how fast the agent reaches the goal. Value of each of the metrics is between 0 and 1, and in what follows we report all metrics in %.

For each of the N evaluation trials denote by Si the binary success indicator, by i the shortest path from start to the goal, by pi the length of the actual executed path, and by Ti.

Success rate is simply the fraction of episodes in which the agent manages to reach the goal within the given time budget:

SR=1Ni=1NSi (3)

SPL takes into account the length of the executed trajectories, not just the binary success indicator:

SPL=1Ni=1NSiimax(i,pi). (4)

This is a stricter metric: to achieve a perfect score of 1, the agents needs not only reach the goal in every episode, but also follow the shortest path.

Pace is the average time left unused after the episode is finished, divided by available time budget (500 steps):

P=1Ni=1N(1-Ti). (5)

The higher this number, the faster, on average, the agent reaches the goal. An important advantage of this metric over SPL is that it takes into account time spent standing still or rotating. A disadvantage is that the perfect score of 1 is not achievable: it would correspond to instantly teleporting to the goal.

Appendix B Additional Results

We show success rate and pace for different modalities in Tables 9,10. All metrics for all environments as a function of the shortest path to the goal are shown in Figure 8.Note that on SPL the human performance is suboptimal for short path lengths. This is because 1) the human often takes some steps in the beginning of an episode to self-localize, and 2) the goal representation in polar coordinates is not very intuitive, in particular, estimating distances is difficult, which sometimes leads to suboptimal trajectories. However, for longer trajectories the robustness of human navigation compensates for these drawbacks.

SunCG Empty SunCG Furnished Matterport3D Mean
Classic Learned Classic Learned Classic Learned Classic Learned
Blind 52.9 58.2 44.9 16.4 40.9 30.0 46.3 34.9
RGB 9.4 49.9 10.0 44.8 9.0 37.4 9.4 44.0
RGB-D 70.2 56.4 75.0 48.2 75.0 46.9 73.4 50.5
RGB-D + GT pose 90.8 92.0 87.9 90.3
RGB-D + GT pose & map 85.8 87.0 87.9 86.9
Table 9: Average success rate. Performance of a classic modular pipeline and a learned agent when provided with different input modalities. For each environment and sensory input, the best of the two results is highlighted in bold.
SunCG Empty SunCG Furnished Matterport3D Mean
Classic Learned Classic Learned Classic Learned Classic Learned
Blind 48.5 46.7 40.9 9.5 36.4 22.7 41.9 26.3
RGB 7.2 49.9 8.2 44.8 8.3 37.4 7.9 44.0
RGB-D 57.8 47.9 58.3 39.0 56.2 36.6 57.4 41.2
RGB-D + GT pose 71.9 72.1 64.7 69.5
RGB-D + GT pose & map 71.4 71.6 70.0 71.0
Table 10: Average pace. Performance of a classic modular pipeline and a learned agent when provided with different input modalities. For each environment and sensory input, the best of the two results is highlighted in bold.