Semi-parametric Topological Memory for Navigation

• Deep-learning navigation methods include reactive systems, LSTM-based memory, and navigation-specific metric maps.Source: §1 · p. 1
• Animal navigation evidence motivates landmark-based and non-metric representations rather than strong reliance on metric maps.Source: §1 · p. 1
• SPTM combines a non-parametric graph of environmental locations with a parametric retrieval network using observations to localize graph nodes.Source: §1 · p. 1
• The graph stores connectivity rather than metric relations, while exploration adds observations and visually similar shortcut connections.Source: §1 · p. 1
• Three-dimensional maze evaluation uses walkthrough images from previously unseen environments, followed by navigation to a new image-specified goal.Source: §1 · p. 2
• 3× higher average success rate than the best-performing baseline was achieved after 5 minutes of maze walkthrough footage.Source: §1 · p. 2

• Animal studies describe landmark-based mechanisms, while cognitive-map theories debate whether internal environmental representations are metric.Source: §2 · p. 2
• Robotic navigation systems typically construct metric maps from sonar, LIDAR, RGB-D, or RGB inputs, including vision-based SLAM.Source: §2 · p. 2
• Reactive deep-learning navigation lacks explicit memory, while other systems use general-purpose LSTM memory or specialized map-like representations.Source: §2 · p. 2
• Prior deep-learning navigation systems use metric maps, whereas SPTM uses a topological map instead of building a global metric map.Source: §2 · p. 2
• Topological-map robotics has been applied to simple two-dimensional mazes and physical robotic systems.Source: §2 · p. 3

3 METHOD

• The agent first explores an environment from recorded traversal footage, then uses the resulting internal representation for episodic goal-directed navigation.Source: §3 · p. 3

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.Source: §3.1 · p. 3
• The retrieval network localizes current and goal observations to graph vertices, after which a shortest path is computed between them.Source: Figure 2 · p. 4, §3.1 · p. 5
• The retrieval network classifies observation pairs as temporally close or distant using self-supervised trajectory-derived examples.Source: §3.1 · p. 4
• Graph vertices store exploration observations, and edges connect consecutive observations or visually similar observations that form shortcut connections.Source: §3.1 · p. 4
• The waypoint is selected as the furthest vertex on the planned path that remains confidently reachable, rather than using a fixed distance.Source: §3.1 · p. 5

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.Source: §3.2 · p. 5

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.Source: §4 · p. 6, §4.1 · p. 6
• 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.Source: §4.1 · p. 7

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.Source: §4.2 · pp. 7–8

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.Source: §4.3 · p. 8, Table 1 · p. 8
• 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.Source: §4.3 · p. 8
• 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.Source: §4.3 · pp. 9–10

• 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.Source: §5 · p. 10
• SPTM can serve as a planning module that reaches goals in unseen environments after only 5 minutes of footage.Source: §5 · p. 10

Future work

• Improving the retrieval and locomotion networks is identified as a way to improve overall system quality.Source: §5 · p. 10
• Adding noisy ego-motion estimation and path integration is proposed as a potential way to improve robustness.Source: §5 · p. 10
• Memory size grows linearly with exploration duration, which may become problematic in very large environments or lifelong learning scenarios.Source: §5 · p. 10

• Both retrieval and locomotion networks are based on ResNet-18 and receive 160×120 pixel images.Source: S1.1 NETWORK ARCHITECTURES · p. 13
• The retrieval network encodes two observations into 512-dimensional embeddings before processing their concatenation through a four-layer fully connected network.Source: S1.1 NETWORK ARCHITECTURES · p. 13
• 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.Source: S1.1 NETWORK ARCHITECTURES · p. 13
• 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.Source: S1.2 TRAINING · p. 13

• The feedforward and LSTM baselines are based on an open A3C implementation and architectures from prior navigation work.Source: S2 BASELINE DETAILS · p. 13
• The feedforward baseline uses two convolutional and two fully connected layers, while the LSTM variant replaces the second fully connected layer with LSTM.Source: S2 BASELINE DETAILS · p. 13
• Baseline inputs are stacks of four recent 84×84 frames, with grayscale models reported because they performed better than RGB models.Source: S2 BASELINE DETAILS · p. 13
• Baselines are trained for 80 million action steps, equivalent to 320 million simulation steps with action repeat.Source: S2 BASELINE DETAILS · p. 13

• The supplementary evaluation varies texture distributions and exploration-sequence properties to test robustness.Source: S3.1 HOMOGENEOUS TEXTURES AND… · p. 13

Homogeneous textures and automated exploration

• Automated exploration causes only a minor decrease in final performance, although SPTM trajectories become qualitatively noisier.Source: S3.1 HOMOGENEOUS TEXTURES AND… · p. 14
• Sparser textures affect results more because visual self-localization becomes challenging, yet SPTM still outperforms baselines by a large margin.Source: S3.1 HOMOGENEOUS TEXTURES AND… · p. 14

Per-pixel matching

• Per-pixel matching performs poorly and produces catastrophically wrong visual shortcuts; local normalization worsens results by discarding absolute color intensity.Source: S3.2.1 PER-PIXEL COMPARISON · p. 15, Figure S3 · p. 15

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.Source: S3.2.2 TEACH-AND-REPEAT · p. 15