Source-linked AI summary
Cognitive Mapping and Planning for Visual Navigation
Saurabh Gupta, Varun Tolani, James Davidson, Sergey Levine, Rahul Sukthankar, Jitendra Malik
TL;DR
Visual navigation in novel environments requires agents to build useful spatial representations and plan despite incomplete observations. CMP jointly learns a first-person mapper and differentiable planner, and it outperforms alternative learning-based methods across reported navigation metrics, while retaining stated scope limitations.
Problem
The paper addresses how robots can navigate novel environments when useful spatial structure and common-sense regularities are not explicitly available from classical mapping.
Method
CMP jointly learns a spatial memory that forms an egocentric top-down belief map and a differentiable planner that selects actions from partial observations.
Results
CMP outperforms the evaluated learning-based methods across metrics and input modalities, improving success rate from 53.0% to 62.5% with RGB and from 71.8% to 78.3% with depth.
Takeaways & Limitations
The learned mapping-and-planning architecture supports navigation in novel environments and outperforms direct methods that lack explicit mapping and planning modules.
Takeaways & Limitations
The approach assumes perfect odometry and metric representations that do not scale well to large environments, with coarser scales potentially losing connectivity information.
Abstract
from arXiv · showhide
We introduce a neural architecture for navigation in novel environments. Our proposed architecture learns to map from first-person views and plans a sequence of actions towards goals in the environment. The Cognitive Mapper and Planner (CMP) is based on two key ideas: a) a unified joint architecture for mapping and planning, such that the mapping is driven by the needs of the task, and b) a spatial memory with the ability to plan given an incomplete set of observations about the world. CMP constructs a top-down belief map of the world and applies a differentiable neural net planner to produce the next action at each time step. The accumulated belief of the world enables the agent to track visited regions of the environment. We train and test CMP on navigation problems in simulation environments derived from scans of real world buildings. Our experiments demonstrate that CMP outperforms alternate learning-based architectures, as well as, classical mapping and path planning approaches in many cases. Furthermore, it naturally extends to semantically specified goals, such as 'going to a chair'. We also deploy CMP on physical robots in indoor environments, where it achieves reasonable performance, even though it is trained entirely in simulation.
1 Introduction
The paper targets navigation in novel environments by combining spatial memory and planning in a unified, task-driven architecture. CMP learns an egocentric belief map from first-person views and uses differentiable planning to act under partial observation.
- 1 Introduction: Classical systems separate geometric mapping and path planning, leaving unobserved structure unknown and making the overall system fragile to mapping errors.The paper contrasts this with learning patterns such as likely hallway, room, and object locations.
- 1 Introduction: CMP combines a spatial memory with a planner that plans paths from partial information in novel environments.The mapper and planner are jointly trained so mapping can exploit task-relevant regularities.
- 1 Introduction: The mapper fuses observations over time into a metric egocentric multi-scale top-down belief, while the planner repeatedly outputs actions toward a specified goal.The belief is updated using ego-motion and current visual observations.
- 1 Introduction: Trainable, differentiable, hierarchical value iteration learns exploration under partial observation, trains the mapper for navigation, and plans toward distant goals efficiently.The hierarchical planner has time complexity logarithmic in the number of steps to the goal.
- 1 Introduction: Unlike classical approaches, CMP can learn indoor regularities task-dependently, improve robustness through joint training, and operate online without a pre-constructed map.The paper also positions CMP against memory-less visual navigation methods that cannot map, plan, or explore new environments.
3 Problem Setup
The study evaluates navigation policies in static simulated indoor environments derived from real scans, with exact maps and topology unavailable in novel test environments. It considers geometric and semantic goals under simplified robot and odometry assumptions.
- 3 Problem Setup: The robot operates in static environments with fixed-size geometry, fixed camera placement, grid-world motion, and relatively high-level macro-actions.The macro-actions are staying, rotating left or right, and moving forward.
- 3 Problem Setup: The robot is assumed to have precise egomotion, corresponding to perfect visual odometry, while joint learning of odometry is deferred to future work.This assumption removes low-level control and localization uncertainty from the studied problem.
- 3 Problem Setup: The geometric task specifies a target location in the robot’s coordinate frame, whereas the semantic task specifies an object of interest such as a chair.Neither the exact environment map nor its topology is available in these novel environments.
- 3 Problem Setup: At each step, the policy receives the current image, egomotion, and target specification, then outputs an action intended to reach the target quickly.The target may be geometric or semantic.
- 3 Problem Setup: The experiments use scanned real-world indoor environments in simulation, training on two buildings and testing on scans from a third building.The testbed is the S3DIS dataset of large-scale indoor areas from educational and office buildings.
4 Mapping
CMP’s mapper converts first-person observations into a latent, egocentric top-down spatial memory that is updated over time. The learned representation can encode task-useful information and predict unobserved space using visual and semantic regularities.
- 4 Mapping: The learned map is a latent general spatial memory rather than a purely free-space representation because it feeds directly into the learned planner.The mapper is free to store whatever information helps generate successful plans.
- 4 Mapping: The mapper maintains a cumulative multi-channel 2D feature map representing free space metrically in the robot’s top-down coordinate frame.The estimate uses the current image, the previous cumulative estimate, and intervening egomotion.
- 4 Mapping: The update warps the previous estimate according to egomotion, predicts current-view free space with a CNN, and accumulates both estimates.The functions W, φ, and U respectively transform, predict, and combine the representations.
- 4 Mapping: The mapper can use scene surfaces, furniture, and learned size and shape priors to estimate partially visible or previously unobserved free space.The paper describes this as leveraging statistical structure in indoor environments.
- 4 Mapping: The mapper architecture uses convolutional and up-convolutional residual networks to transform image-space features into egocentric top-down belief updates.The image representation is transformed through fully connected layers before upsampling.
- 4 Mapping: The network produces both free-space estimates and confidence values, with confidence accumulated over time to support uncertainty-aware updates.The confidence estimate functions similarly to an update gate in a gated recurrent unit.
5 Planning
CMP uses a trainable hierarchical value-iteration planner that operates on the mapper’s multi-scale belief and remains applicable when the map is incomplete. Differentiability connects planning signals back to the mapper.
- 5 Planning: Hierarchical planning addresses long-horizon difficulty by conducting value iterations from coarse spatial scales to progressively finer resolutions.The procedure reduces runtime complexity and the number of steps through which gradients must flow.
- 5 Planning: The planner implements value iteration with convolutions and channel-wise max-pooling, producing a policy from the mapper’s egocentric multi-scale belief.This makes the planning computation differentiable with respect to its inputs.
- 5 Planning: The planner is trainable and differentiable, allowing gradients to back-propagate into the mapper and enabling task-driven mapping.The architecture jointly optimizes mapping and planning for navigation.
- 5 Planning: Because the planner is learned, it can account for partially observed maps and learn when and where to explore.The mapper also supplies uncertainty alongside its world belief.
6 Joint Architecture
CMP jointly updates a learned multi-scale belief map and uses it to plan actions end-to-end, without direct map supervision. Across geometric and semantic navigation, it outperforms the evaluated learning-based baselines and often compares favorably with classical approaches, while its internal representations capture spatial and task-relevant structure.
- Architecture: At each time step, CMP updates a multi-scale world belief from the current observation and feeds it to a differentiable planner that outputs the next action.The mapper and planner are trained end-to-end, and the mapper is not directly supervised to match ground-truth maps.
- Training: CMP is trained with DAGGER using shortest-path supervision, while the architecture can also support alternate policy-learning paradigms such as reinforcement learning.The authors chose DAGGER because it was more sample efficient and stable in their domain.
- Geometric Task: CMP outperforms the evaluated learning-based navigation methods across metrics and input modalities, including higher success rates and SPL than the LSTM baseline.For RGB and depth input, CMP reaches success rates of 62.5% and 78.3%, compared with 53.0% and 71.8% for LSTM.
- Semantic Task: In semantic navigation, CMP performs better than the other learning-based baselines across metrics, while comparisons with the classical exploration-and-segmentation baseline are largely favorable.The task requires finding object categories that may initially be invisible and therefore requires exploration.
- Representation Analysis: The learned mapper produces spatial representations that predict nearby free space, infer free space behind doorways, and distinguish hallway from room space.These capabilities extend beyond directly visible geometric observations and were not explicitly trained as separate mapping objectives.
- Representation Analysis: CMP value maps correspond to the agent’s current actions and change when newly discovered information makes a previously hypothesized path infeasible.This visualization supports a link between the planner’s value estimates and the agent’s observed behavior.
8 Real World Deployment
The learned policy was deployed on a TurtleBot 2 after simulation-only training, achieving 68% success across ten real-world test configurations despite noisy depth sensing. Failures mainly involved infractions or difficulty navigating around obstacles.
- Robot setup and policy: The robot used an Orbbec Astra camera, wheel-encoder and IMU estimates, ROS, and a GPU-equipped laptop for control.Macro-actions were executed with iLQR feedback control to compensate for deviations from reference trajectories.
- Evaluation: The evaluation covered ten configurations without straight paths to the goals, including leaving rooms, crossing cubicles, and navigating around tables and kitchen counters.Five runs were conducted for each configuration.
- Results: 68% of runs succeeded under the criterion of reaching within 80cm without brushing against or colliding with objects.The success rate was reported across the ten configurations.
9 Discussion
The discussion presents CMP as an end-to-end architecture for navigation in novel environments while identifying important deployment and scalability constraints. Perfect odometry, metric representations, and exclusive use of DAGGER limit the current scope.
- Discussion: CMP combines learned mapping from first-person views with planning over the learned map for navigation in novel environments.The authors report that it outperforms direct methods without explicit mapping and planning modules.
- Limitations: The approach assumes perfect odometry, although real-world robots do not have perfect odometry.The authors state that modeling movement uncertainty is essential before real-world deployment.
- Limitations: Maintaining metric spatial representations does not scale well to large environments.The multi-scale representation supports larger environments but makes planning more approximate at coarser resolutions and can lose connectivity information.
- Limitations: Training exclusively with DAGGER can produce expert-optimal policies that are infeasible under the agent’s current information.The authors suggest guided policy search or reinforcement learning as possible alternatives, especially for the semantic task.
A1 Backward Flow Field ρ from Egomotion
The robot’s egomotion relates corresponding points between successive top views, allowing the original location of each new-view point to be computed.
- A1 Backward Flow Field ρ from Egomotion: The equation relates corresponding points p and p′ across top views after rotation by θ and forward motion t.Rθ denotes the rotation matrix for angle θ.
- A1 Backward Flow Field ρ from Egomotion: The transformation accounts for a robot that first rotates about its position and then moves forward.
- A1 Backward Flow Field ρ from Egomotion: Given θ and t, the mapper can compute where each point in the new top view originated in the original top view.
A2 Mapper Performance in Isolation
The mapper is evaluated independently on free-space prediction from first-person observations during rotation, with supervision provided only at the end.
- A2 Mapper Performance in Isolation: The isolated mapper task predicts free space within a 3.20 meter neighborhood while the agent rotates about its current position.
- A2 Mapper Performance in Isolation: Supervision is provided only at the end of the agent’s rotation.
- A2 Mapper Performance in Isolation: The mapper predicts free space in regions where no direct observations are made.
A3 Additional Experiments
Additional experiments compare CMP with baselines across Matterport environments, navigation hardness, ablations, transfer, and longer-horizon goals. CMP generally outperforms competing models, while planning and learned mapping affect performance and computational cost.
- Additional Matterport Experiments: CMP consistently outperforms the 4-frame reactive baseline and LSTM on 10 test environments from an internal Matterport dataset.The dataset contains 41 scanned environments: 27 training, 4 validation, and 10 test environments.
- Ablations: Single-scale planning slightly improves performance but increases planning cost relative to the multi-scale planner.
- Ablations: Removing the planner causes a performance drop, especially for RGB inputs, compared with the full system.
- Ablations: The analytic mapper performs worse than the learned mapper, supporting the choice to learn the mapping component.
- Far-Away Goals: Both LSTM and CMP suffer when run for 79 steps, while performance improves with more time for back-tracking.
- Far-Away Goals: The performance gap between LSTM and CMP is larger for far-away-goal scenarios, highlighting the benefit of the mapping-and-planning architecture.
- Generalization and Transfer: CMP shows a smaller performance drop when trained on one scene and transfers slightly better from the internal Matterport dataset to Stanford S3DIS.
- Navigation Hardness: CMP is generally better than LSTM across navigation hardness values, particularly for high-hardness RGB cases.Hardness is the normalized gap between ground-truth and Manhattan distances.
A4 Simulation Testbed Details
The simulation setup uses traversable-space meshes and macro-actions, while separately developing mapper and planner components before combining them in the final system.
- Simulation Testbed Details: Preprocessed meshes provide the robot’s traversable space for training, validation, and testing environments.Top views visualize the layouts and their differences across splits.
- Simulation Testbed Details: The robot’s action space consists of macro-actions with θ set to π/2.
- Simulation Testbed Details: The mapper and planner were developed independently using first-person free-space prediction and ground-truth top-view mazes, respectively.The separation was used to understand each component before constructing the final system.
A5 Macro-action Implementation using ILQR
This section describes the simulated environments and the iLQR-based macro-action implementation used for navigation control. The robot dynamics and optimization settings define how planned trajectories are executed.
- Robot dynamics: The robot state comprises 2D location and orientation, while linear and angular velocities serve as control inputs.The dynamics function models how these controls update the robot state.
- Trajectory optimization: iLQR solves an optimization problem from an initial state s0 to a desired final state sT.The optimization produces a reference trajectory and feedback matrices for control execution.
- Evaluation environments: The evaluation uses geometric navigation problems across multiple mapped areas, with area4 reserved for testing all models.The maps depict traversable space and example routes from circle start nodes to star goal nodes.
- Trajectory optimization: The cost settings encourage rapid target reaching while penalizing large velocities, with parameters tuned experimentally across start-goal pairs.Q, R, Δt, and T determine the target, control, execution frequency, and macro-action duration trade-offs.
- Trajectory optimization: Because Dubins Car dynamics are nonlinear, iLQR repeatedly linearizes the system around the current solution.The resulting feedback control uses the estimated state from wheel encoders and the IMU.
A6 Change Log
The change log records successive versions that expanded experiments, comparisons, deployment details, and visual analysis.
- Change log: The IJCV version added semantic-task experiments, recent-work context, SPL metrics, classical-method comparisons, real-world deployment details, and visualizations of learned representations.The CVPR 2017 version also added semantic experiments and released code on the project website.