Topological map navigation

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 2207.04429 §5.2 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 2207.04429 §3 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 2412.05552 §4 2412.05552 app.. Instead of searching that graph, a learned policy chooses the next node from the instruction and the current views 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 2310.07896 §III 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 2207.04429 §3. The paper reports that no fine-tuning or language-annotated robot data is used 2207.04429 §1. Card: LM-Nav.

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 2207.04429 app. B. The paper then removes redundant edges by transitive reduction 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 2207.04429 §4.4 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 2207.04429 eq. 4 2207.04429 eq. 5. The walk is recovered by backtracking from the best final node 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 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 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 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 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 2412.05552 §3.1 2412.05552 §3.2 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 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 2412.05552 tab. 4. Card: SAME.

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 2310.07896 §IV-A. At test time the goal can be hidden for undirected exploration, or shown to reach a place in the photo 2310.07896 §IV-A. Its actions come from a diffusion model over short 2D sequences, sampled with 10 denoising steps 2310.07896 §IV-B 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 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 2310.07896 tab. 1 2310.07896 §V-A. The number of trials is not stated 2310.07896 §V-A. For goal reaching, one NoMaD model reaches 92%, the same as the dedicated ViNT Policy 2310.07896 tab. 2. Card: NoMaD.

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.

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.

# 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 2207.04429 eq. 5. The paper does not give alpha as a value, only as −log γ 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 2310.07896 §IV-B 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 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 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 2207.04429 tab. 1. SAME reports SR and SPL on simulated benchmarks 2412.05552 tab. 4. NoMaD reports exploration and goal-reaching success with collisions, on a real robot, with image goals 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" 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 2412.05552 tab. 7. The claim holds only for some metrics.

Papers

• LM-Nav: 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: 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: a mixture-of-experts layer in DUET's visual cross-attention, trained with DAgger to handle seven vision-language navigation tasks with one model.