---
kind: concept
slug: topological-map-navigation
title: Topological map navigation
summary: >-
  Moves an agent to places on a graph of places it has seen. LM-Nav matches
  route landmarks to nodes and finds the cheapest walk visiting them in order.
  SAME learns a policy over the graph. NoMaD samples local moves from a
  diffusion policy, using the graph for exploration. Trade-offs: LM-Nav needs a
  map and recognisable landmarks; SAME needs training data; NoMaD takes photo
  goals, not text.
tags: [robotics, navigation, planning]
papers: ["2207.04429", "2310.07896", "2412.05552"]
related: [visual-grounding, zero-shot-learning, llm-planning, simultaneous-localization-and-mapping, mixture-of-experts, imitation-learning, diffusion-models]
status: draft
updated_at: 2026-10-31
---

## Overview

A robot first drives through an environment and records a graph of places.
Each node holds an observation, such as an image and a GPS position, and edges
link nodes that can be reached from each other [arxiv:2207.04429 §5.2]
[arxiv:2207.04429 app. B]. Later, a route given in free-form text is turned
into an ordered list of landmarks. The landmarks are matched to graph nodes,
and the robot follows the walk that visits them in order at low travel cost
[arxiv:2207.04429 §3] [arxiv:2207.04429 §4.4].

Simulated benchmarks use the same kind of graph in a different way. The
environment supplies a discrete graph of navigable viewpoints, and the agent
keeps a topological map of visited and candidate nodes while it moves
[arxiv:2412.05552 §4] [arxiv:2412.05552 app.]. Instead of searching that
graph, a learned policy chooses the next node from the instruction and the
current views [arxiv:2412.05552 §3.2].

The variants share a graph of places the robot has seen or is given. They
differ in what moves the robot over it. LM-Nav's plan is an explicit walk over
its graph. SAME's plan is the sequence of actions its policy picks on that
graph. NoMaD keeps the graph as a memory of visited places and picks
exploration targets on it, while its diffusion policy plans short local paths
in continuous space [arxiv:2310.07896 §III] [arxiv:2310.07896 §IV-B].

## Variants

### Landmark matching with graph search (LM-Nav)

Three frozen pre-trained models each do one job. A language model extracts the
ordered landmarks from the instruction. A vision-language model scores each
landmark against each node's image. A visual navigation model handles the
driving between nearby nodes [arxiv:2207.04429 §3]. The paper reports that no
fine-tuning or language-annotated robot data is used [arxiv:2207.04429 §1].
Card: [LM-Nav](/papers/2207.04429).

Graph edges come from two rules. An edge is added when two observations were
recorded a second apart, or when the learned distance and the GPS gap are both
below thresholds. The paper gives these as 1 s, 80 time steps and 100 m
[arxiv:2207.04429 app. B]. The paper then removes redundant edges by
transitive reduction [arxiv:2207.04429 app. B].

The walk is scored by subtracting a distance penalty from the landmark match at
each node visited. The distance weight is α = −log γ, where γ is a per-step
continuation probability that the paper does not state [arxiv:2207.04429 §4.4]
[arxiv:2207.04429 eq. 3]. The search is a dynamic program over landmarks. It
keeps, for each node, the best score of a walk that ends there after the first
i landmarks, and relaxes scores along edges with the penalty applied
[arxiv:2207.04429 eq. 4] [arxiv:2207.04429 eq. 5]. The walk is recovered by
backtracking from the best final node [arxiv:2207.04429 alg. 1].

Landmark match is a softmax over all nodes of the vision-language model's
score for the landmark text. The text prompt is "This is a photo of" followed
by the landmark [arxiv:2207.04429 §4.3].

### Max-likelihood planner (ablation)

The paper also tests a simpler planner. It picks the single best node for each
landmark and connects those nodes by shortest paths [arxiv:2207.04429 tab. 4].
It is included as a comparison, not as a recommended design. Its planning
success was 0.6 against 0.9 on EnvSmall-10, and 0.2 against 0.8 on
EnvLarge-10 [arxiv:2207.04429 tab. 4]. The paper reports these as author
measurements on its own 20 prompts.

### Learned policy over a topological map (SAME)

SAME does not search the graph. Its base agent, DUET, has a local branch on the
current panorama and a global branch on the topological map of visited and
candidate nodes, and both branches use cross-attention over the instruction
[arxiv:2412.05552 app.]. SAME replaces the query projection of those
cross-attention layers with a sparse mixture of experts. A router picks the
top experts at each step from the mean of the view features and the
instruction token [arxiv:2412.05552 §3.1] [arxiv:2412.05552 §3.2]
[arxiv:2412.05552 §3.4]. The policy is trained with DAgger, with each batch
drawn from one dataset, on seven vision-language navigation sets in the
discrete Matterport3D graph [arxiv:2412.05552 §4].

The paper reports a single model for all seven tasks. Author-reported, on
validation unseen splits, it reaches 76 SR on R2R, the same as the unified
ScaleVLN baseline and below single-task ScaleVLN at 79 [arxiv:2412.05552
tab. 4]. On REVERIE it reaches 46.4 SR, against 57.0 for single-task ScaleVLN
[arxiv:2412.05552 tab. 4]. Card: [SAME](/papers/2412.05552).

### Goal-masked diffusion policy with a topological memory (NoMaD)

NoMaD is one Transformer policy with two modes. Its goal image is hidden from
attention for about half of the training samples [arxiv:2310.07896 §IV-A]. At
test time the goal can be hidden for undirected exploration, or shown to reach
a place in the photo [arxiv:2310.07896 §IV-A]. Its actions come from a
diffusion model over short 2D sequences, sampled with 10 denoising steps
[arxiv:2310.07896 §IV-B] [arxiv:2310.07896 §IV-C].

The robot keeps a topological graph of visited observations. A frontier-based
planner, taken from the ViKiNG setup, picks exploration targets on that graph,
and the policy supplies the local actions. The paper does not describe the
planner beyond this [arxiv:2310.07896 §III].

Author-reported, on a real LoCoBot in unseen indoor and outdoor places, the
exploration success is 98% with 19M parameters and 0.2 collisions per
experiment. The best published baseline in its table, Subgoal Diffusion, reaches 77% with 1.7
collisions at 335M parameters [arxiv:2310.07896 tab. 1] [arxiv:2310.07896 §V-A].
The number of trials is not stated [arxiv:2310.07896 §V-A]. For goal reaching,
one NoMaD model reaches 92%, the same as the dedicated ViNT Policy
[arxiv:2310.07896 tab. 2]. Card: [NoMaD](/papers/2310.07896).

## When to use which

The two variants answer different questions, so the rows below rest on what
each paper reports about its own constraints. The papers do not compare them
directly.

| Situation | Use | Why |
|---|---|---|
| The robot can drive the environment once before deployment | Build the graph from that drive, with images and GPS per node | The paper's map comes from one manual drive [arxiv:2207.04429 §5.2] |
| No language-annotated robot data and no budget for fine-tuning | Frozen language, vision-language and navigation models, as in LM-Nav | The paper uses frozen models and no robot-specific text data [arxiv:2207.04429 §1] [arxiv:2207.04429 §3] |
| Route includes landmarks that are hard to see or name | Check detection per landmark before deployment; expect misses | Failures came from landmarks such as a fire hydrant or a cement mixer [arxiv:2207.04429 §5.2]. Detection was 0.87 on the authors' test set [arxiv:2207.04429 tab. 3] |
| Route needs several landmarks in a fixed order | Graph search over the whole walk, not per-landmark best node | Planning success was higher with graph search on both environments [arxiv:2207.04429 tab. 4] |
| Route has turn-by-turn commands or verbs | Not covered by LM-Nav's approach | The system keeps landmarks and ignores verbs and commands [arxiv:2207.04429 §6] |
| Heavy per-query compute on the robot | Run the language and vision-language models off board | The paper runs those queries on a remote workstation and the navigation model on board [arxiv:2207.04429 §5.1] |
| One model must handle several instruction styles, such as step-by-step routes, object goals and room-plus-object goals, in a discrete graph | A learned policy over the graph, as in SAME | Against the unified baselines in its table, SAME is higher on most listed splits; single-task models still lead on REVERIE [arxiv:2412.05552 tab. 4] |
| Training data mixes several instruction datasets | Keep each dataset in its own batch | Mixing datasets in one batch cut DAgger's R2R SR from 73.69 to 62.36 in the paper's single runs [arxiv:2412.05552 tab. 6] |
| Policy must run in a continuous space it was not trained in | Expect lower numbers than training there | Zero-shot with a waypoint predictor reached SR 47 on R2R-CE val unseen; the paper lists ScaleVLN trained on R2R-CE at SR 55 [arxiv:2412.05552 tab. 5] |
| The goal is a photo of the place, not a route in text | A goal-image policy, as in NoMaD | NoMaD's goal input is an image [arxiv:2310.07896 §IV-A]; LM-Nav and SAME take text instructions |
| The robot must explore an unknown space with no goal, on a small model | NoMaD's undirected mode, with a topological memory | Author-reported 98% exploration success with 19M parameters on a real robot [arxiv:2310.07896 tab. 1] |
| One model must both explore and reach goals | NoMaD | Its undirected and goal-conditioned results match the dedicated policies in the paper's table [arxiv:2310.07896 tab. 2] |
| No VLN pre-training is available | Pre-train first, or expect a large drop | Without ScaleVLN pre-training, R2R SR fell from 73.69 to 59.05 in the paper's single runs [arxiv:2412.05552 tab. 2] |

## Implementation sketch

The steps below follow the paper's graph search, written in our own words.
Lines are at most 80 characters. Each step cites where it comes from.

```pseudocode
# Build the map: a node per observation, with image and position
# [arxiv:2207.04429 §5.2]
# Add an edge if two observations are close in time, or if the learned
# distance and GPS gap are both small  [arxiv:2207.04429 app. B]

# Split the route into ordered landmark texts  [arxiv:2207.04429 §4.2]
landmarks = extract_landmarks(instruction)

# Start at the start node with score 0; spread scores along edges with
# the distance penalty  [arxiv:2207.04429 eq. 4]
score = [-inf] * num_nodes
score[start] = 0
score = relax(score, graph, alpha)

# Per landmark: add its match to every node, then relax again
# [arxiv:2207.04429 alg. 1] [arxiv:2207.04429 eq. 5]
for landmark in landmarks:
    score = score + landmark_match(landmark, graph)
    score = relax(score, graph, alpha)

# Walk ends at the best final node; trace back to recover it
# [arxiv:2207.04429 alg. 1]
walk = backtrack(argmax(score))
```

`relax` sets each node's score to the best neighbour score minus alpha times
the edge distance, as in the paper's update [arxiv:2207.04429 eq. 5]. The
paper does not give alpha as a value, only as −log γ [arxiv:2207.04429 eq. 3].

SAME replaces the search with a learned choice at each step. The sketch below
is for LM-Nav only; SAME's routing is described in its own card.

NoMaD does not search the graph either. Its policy samples short action
sequences by denoising from Gaussian noise, and the graph only supplies
exploration targets [arxiv:2310.07896 §IV-B] [arxiv:2310.07896 §III]. Its
sampling loop is in its card.

## Contradictions

- Success rate, LM-Nav: the text reports that 85% of experiments followed the
  instruction without collisions or disengagements [arxiv:2207.04429 §5.3].
  Table 1 reports 0.8 net success in both environments [arxiv:2207.04429
  tab. 1]. The paper does not reconcile the two figures.
- Efficiency, LM-Nav: the paper states that the planning efficiency in Table 4
  is not the same metric as the efficiency in Table 1 [arxiv:2207.04429 tab. 4].
  Compare the two columns only within their own table.
- Not comparable across papers: LM-Nav reports net success on a real robot
  over 20 outdoor instructions [arxiv:2207.04429 tab. 1]. SAME reports SR and
  SPL on simulated benchmarks [arxiv:2412.05552 tab. 4]. NoMaD reports
  exploration and goal-reaching success with collisions, on a real robot, with
  image goals [arxiv:2310.07896 tab. 1]. Do not set these numbers side by side
  as if they measured the same thing.
- Lambda, SAME: the text says a balance weight of 0.2 "performs worse than all
  other variants" [arxiv:2412.05552 §4.2]. Table 7 shows 0.2 as the best or
  close to best on R2R SPL and ObjectNav SPL, and the lowest on REVERIE SR
  [arxiv:2412.05552 tab. 7]. The claim holds only for some metrics.

## Papers

- [LM-Nav](/papers/2207.04429): combines a frozen language model, a vision-language model and a navigation model to follow text routes over a topological graph built from one drive.
- [NoMaD](/papers/2310.07896): one goal-masked diffusion policy that explores when its goal is hidden and reaches a shown goal image, with a topological memory of visited places.
- [SAME](/papers/2412.05552): a mixture-of-experts layer in DUET's visual cross-attention, trained with DAgger to handle seven vision-language navigation tasks with one model.