Source-linked AI summary
Semi-parametric Topological Memory for Navigation
Nikolay Savinov, Alexey Dosovitskiy, Vladlen Koltun
TL;DR
Navigation in previously unseen environments requires representing a maze from limited walkthrough footage and using that representation to reach image-specified goals. The paper proposes SPTM, a graph-and-network memory that plans through retrieved locations and supplies reachable waypoints to locomotion. With 5 minutes of footage, SPTM achieves three times the average success rate of the best-performing baseline across test mazes.
Problem
Goal-directed navigation in previously unseen mazes requires agents to represent environments from walkthrough images and use those representations to navigate to goals.
Method
SPTM combines a non-parametric connectivity graph with a parametric observation-retrieval network and uses planned reachable waypoints for locomotion.
Results
3× higher average success rate than the best-performing baseline was achieved across test environments after 5 minutes of maze walkthrough footage.
Takeaways & Limitations
SPTM can build a topological representation from limited footage and use it to navigate confidently toward goals in previously unseen environments.
Abstract
from arXiv · showhide
We introduce a new memory architecture for navigation in previously unseen environments, inspired by landmark-based navigation in animals. The proposed semi-parametric topological memory (SPTM) consists of a (non-parametric) graph with nodes corresponding to locations in the environment and a (parametric) deep network capable of retrieving nodes from the graph based on observations. The graph stores no metric information, only connectivity of locations corresponding to the nodes. We use SPTM as a planning module in a navigation system. Given only 5 minutes of footage of a previously unseen maze, an SPTM-based navigation agent can build a topological map of the environment and use it to confidently navigate towards goals. The average success rate of the SPTM agent in goal-directed navigation across test environments is higher than the best-performing baseline by a factor of three. A video of the agent is available at https://youtu.be/vRF7f4lhswo
1 INTRODUCTION
SPTM is introduced as a topological-memory navigation architecture inspired by animal landmark navigation. It is evaluated on goal-directed navigation in previously unseen 3D mazes using walkthrough footage, where it substantially outperforms baselines.
- Deep-learning navigation methods include reactive systems, LSTM-based memory, and navigation-specific metric maps.
- Animal navigation evidence motivates landmark-based and non-metric representations rather than strong reliance on metric maps.
- SPTM combines a non-parametric graph of environmental locations with a parametric retrieval network using observations to localize graph nodes.
- The graph stores connectivity rather than metric relations, while exploration adds observations and visually similar shortcut connections.
- Three-dimensional maze evaluation uses walkthrough images from previously unseen environments, followed by navigation to a new image-specified goal.
- 3× higher average success rate than the best-performing baseline was achieved after 5 minutes of maze walkthrough footage.
2 RELATED WORK
Related navigation systems span animal-inspired landmark mechanisms, metric robotic maps, deep-learning memory, and earlier topological approaches. SPTM is positioned as a deep-learning system using a topological rather than global metric map.
- Animal studies describe landmark-based mechanisms, while cognitive-map theories debate whether internal environmental representations are metric.
- Robotic navigation systems typically construct metric maps from sonar, LIDAR, RGB-D, or RGB inputs, including vision-based SLAM.
- Reactive deep-learning navigation lacks explicit memory, while other systems use general-purpose LSTM memory or specialized map-like representations.
- Prior deep-learning navigation systems use metric maps, whereas SPTM uses a topological map instead of building a global metric map.
- Topological-map robotics has been applied to simple two-dimensional mazes and physical robotic systems.
3 METHOD
SPTM builds a graph from exploration observations, retrieves current and goal locations, plans a graph path, and selects reachable waypoints for short-range locomotion. Its retrieval and locomotion networks are trained from self-supervised trajectory data.
- 3 METHOD: The agent first explores an environment from recorded traversal footage, then uses the resulting internal representation for episodic goal-directed navigation.
- 3.1 SEMI-PARAMETRIC TOPOLOGICAL MEMORY: SPTM uses a memory graph of location observations and a retrieval network, with a locomotion network repeatedly moving the agent toward generated waypoints.
- 3.1 SEMI-PARAMETRIC TOPOLOGICAL MEMORY: The retrieval network localizes current and goal observations to graph vertices, after which a shortest path is computed between them.
- 3.1 SEMI-PARAMETRIC TOPOLOGICAL MEMORY: The retrieval network classifies observation pairs as temporally close or distant using self-supervised trajectory-derived examples.
- 3.1 SEMI-PARAMETRIC TOPOLOGICAL MEMORY: Graph vertices store exploration observations, and edges connect consecutive observations or visually similar observations that form shortcut connections.
- 3.1 SEMI-PARAMETRIC TOPOLOGICAL MEMORY: The waypoint is selected as the furthest vertex on the planned path that remains confidently reachable, rather than using a fixed distance.
- 3.2 LOCOMOTION NETWORK: The locomotion network maps current and target observations to action probabilities and is trained from nearby observation-action pairs generated by random exploration.
4 EXPERIMENTS
The experiments test SPTM for goal-directed navigation in previously unseen 3D mazes using image-only walkthrough footage, then compare it with memoryless and recurrent baselines. SPTM outperforms the baselines across test mazes, while shortcuts improve graph connectivity and localization remains a challenge in large environments.
- 4.1 SETUP: The evaluation uses simulated 3D Doom mazes, with different layouts for training, validation, and testing to assess generalization.Training uses one layout with randomized goals and textures; three mazes are used for validation and seven for testing.
- 4.1 SETUP: Each agent receives approximately 5 minutes of human exploration footage, then attempts goal-directed trials from new maze locations using goal images.Each maze has 96 trials, and success requires reaching the goal within 5,000 simulation steps.
- 4.2 BASELINES: The baselines include a goal-agnostic agent without memory, a goal-directed feedforward network, and goal-agnostic and goal-directed agents with LSTM memory.The comparison excludes methods requiring ground-truth depth maps or ego-motion, matching the image-only continuous-state setting.
- 4.3 RESULTS: SPTM is superior to the baselines in all mazes, with an average success rate three times higher than the best-performing baseline and typically faster goal reaching.Success is measured as the percentage of navigation trials completed within 5,000 steps.
- 4.3 RESULTS: Feedforward and LSTM baselines perform similarly and inconsistently, suggesting standard LSTM memory does not efficiently use long walkthrough sequences.The 10,000-step walkthrough duration is identified as beyond the capabilities of standard recurrent networks.
- 4.3 RESULTS: Vision-based shortcuts reduce the average shortest path to the goal in Val-3 from 990 to 155 steps, while large-environment self-localization can produce unnecessary loops.The Val-3 example attributes the longer trajectory to difficulty with vision-based self-localization; an ablation also finds shortcut removal causes a dramatic performance decline.
5 CONCLUSION
The paper proposes SPTM as a hybrid topological memory and demonstrates its use for goal-directed navigation in previously unseen environments. It also identifies robustness and scalability directions for future work.
- SPTM combines a non-parametric topological graph with a parametric deep network that retrieves graph nodes from observations.The graph represents locations and connectivity without metric relations.
- SPTM can serve as a planning module that reaches goals in unseen environments after only 5 minutes of footage.
- Future work: Improving the retrieval and locomotion networks is identified as a way to improve overall system quality.
- Future work: Adding noisy ego-motion estimation and path integration is proposed as a potential way to improve robustness.
- Future work: Memory size grows linearly with exploration duration, which may become problematic in very large environments or lifelong learning scenarios.
S1 METHOD DETAILS
The retrieval and locomotion networks use image-based ResNet-18 architectures, trained online from random-agent experience with replay-buffer updates.
- Both retrieval and locomotion networks are based on ResNet-18 and receive 160×120 pixel images.
- The retrieval network encodes two observations into 512-dimensional embeddings before processing their concatenation through a four-layer fully connected network.
- The locomotion network jointly processes two observations and predicts seven actions with a softmax output.The actions include no-op, four movement directions, and two turning actions.
- Training data are generated online by a random agent, using a replay buffer of size |B| = 10,000 and 50 mini-batch iterations after 10,000 random-agent steps.
S2 BASELINE DETAILS
The baselines use feedforward and LSTM variants of an A3C architecture, trained on stacked grayscale frames and evaluated using reward-selected snapshots.
- The feedforward and LSTM baselines are based on an open A3C implementation and architectures from prior navigation work.
- The feedforward baseline uses two convolutional and two fully connected layers, while the LSTM variant replaces the second fully connected layer with LSTM.
- Baseline inputs are stacks of four recent 84×84 frames, with grayscale models reported because they performed better than RGB models.
- Baselines are trained for 80 million action steps, equivalent to 320 million simulation steps with action repeat.
S3 ADDITIONAL RESULTS
Additional experiments test maze textures, exploration sources, and key SPTM components. SPTM remains strong under automated exploration and sparse textures, while per-pixel matching and teach-and-repeat perform substantially worse.
- The supplementary evaluation varies texture distributions and exploration-sequence properties to test robustness.
- Homogeneous textures and automated exploration: Automated exploration causes only a minor decrease in final performance, although SPTM trajectories become qualitatively noisier.
- Homogeneous textures and automated exploration: Sparser textures affect results more because visual self-localization becomes challenging, yet SPTM still outperforms baselines by a large margin.
- Per-pixel matching: Per-pixel matching performs poorly and produces catastrophically wrong visual shortcuts; local normalization worsens results by discarding absolute color intensity.
- Teach-and-repeat: Teach-and-repeat performs significantly worse than SPTM despite using recorded actions, partly because it lacks shortcut connections and cannot recover after trajectory divergence.