LM-Nav: Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action

In plain words

Picture a delivery robot that has already driven around a park with a camera and a GPS receiver, so it has a rough map of places it has seen. You then type a route such as "turn right at the statue, then look for the library". LM-Nav splits that request into the landmarks in order, works out which places on the map look like each landmark, and picks the route that visits them in order without a long detour. The robot then drives that route with a navigation model that learned from its own driving data.

The trick is that nothing is trained for this task. Three existing models each do one job: one reads language, one matches words to pictures, and one knows how to drive between nearby views. No one has to write instruction-annotated robot data for the system to work. The paper reports that it works on outdoor streets with a small wheeled robot, and it fails when a landmark is hard to recognise, such as a fire hydrant.

TL;DR

• LM-Nav combines three frozen pre-trained models for navigation from text: a large language model for landmark extraction, a vision-language model for grounding, and a visual navigation model for execution §3.
• No fine-tuning and no language-annotated robot data are used; the target environment only needs a map built by driving the robot §5, §1.
• The planner is a dynamic program over a topological graph that maximises landmark match minus travel cost §4.4 eq. 3 alg. 1.
• Author-reported: 0.8 net success on 20 instructions over more than 6 km tab. 1 §5.2. Landmark detection by CLIP is the main failure point §5.2.
• Official code (MIT) covers the language, CLIP scoring and graph search; the graph-building and navigation-model code are not in the repository [code].

Problem

Goal-conditioned navigation policies can be trained on large unlabelled robot data, but goals must be given as images or positions, which is an unnatural interface §1. Language-conditioned navigation usually needs trajectories annotated with instructions, which is expensive §1. Simulation-based vision-and-language navigation needs a photo-realistic simulator, which is hard to build for unstructured outdoor scenes §2. The method assumes the landmarks in the instruction exist in the environment and can be recognised by the vision-language model §5.2.

Method

LM-Nav has three components, each used frozen §3 §5:

• Language model (LLM). GPT-3 turns a free-form instruction into an ordered list of landmark descriptions ℓ₁ … ℓₙ §4.2 app. A.1.
• Vision-language model (VLM). CLIP scores how well a landmark text matches each graph node's image §3 §4.3.
• Visual navigation model (VNM). ViNG, a goal-conditioned model that predicts the temporal distance D between two images and the action to take §3. Its distance predictions give the graph edges and their weights.

Graph construction

The map is a topological graph G(V, E). Each node holds an image and GPS position from the data collection drive §5.2 §3. An edge is added when two nodes are close in time, or when the VNM says they are close and GPS says they are near app. B alg. 2. The paper says the graph is then reduced by transitive reduction to remove redundant edges app. B.

# Graph building  [alg. 2] [app. B]
# Input:  nodes n_i, n_j; VNM distance f_d; thresholds (eps, tau, eta)
# Output: whether to add an edge, and its weight

def add_edge(node_i, node_j):
    # Learned distance from the VNM  [app. B]
    learned = f_d(node_i.image, node_j.image)
    # Time gap between the two observations  [app. B]
    time_gap = abs(node_i.timestamp - node_j.timestamp)
    # Spatial gap from GPS  [app. B]
    gps_gap = norm(node_i.gps - node_j.gps)
    # Recorded in quick succession: physically traversed  [app. B]
    if time_gap < eps:
        return True, learned
    # Reachable by the VNM and close by GPS  [app. B]
    if learned < tau and gps_gap < eta:
        return True, learned
    return False, None

Problem formulation

A walk v̄ over the graph should both succeed when driven and satisfy the landmark order. The paper writes the probability that the walk is traversed as a product of per-edge terms γ^D, where γ is a per-step continuation probability and D is the predicted number of steps §4.1 eq. 1. The objective multiplies that by a max over monotone assignments of the walk's nodes to the landmarks §4.1 eq. 2.

Grounding landmarks

For a landmark ℓⱼ and node vᵢ, the probability P(vᵢ | ℓⱼ) is a softmax over all nodes of the CLIP output for that landmark §4.3. The paper calls CLIP's output a logit. The text prompt is "This is a photo of" followed by the landmark §4.3 app. A.2. The paper uses one prompt and no prompt ensembling app. A.2.

Graph search

The search maximises a score R that sums the CLIP match at the matched nodes and subtracts α times the travelled distance, where α = −log γ §4.4 eq. 3. The score is maximised with dynamic programming Q(i, v), the best score for a walk that ends at v after visiting the first i landmarks §4.4 eq. 4. The update for each landmark adds its CLIP score at v, then propagates the scores along edges Dijkstra-style, with a cost of α times the edge distance §4.4 eq. 5. The best final node is the argmax of Q(n, ·), and the walk is recovered by backtracking alg. 1.

# LM-Nav graph search: landmark-by-landmark dynamic program  [alg. 1]
# Input:  landmarks (n strings); graph G; start node S; alpha
# Output: walk (list of nodes)

def find_walk(landmarks, graph, start, alpha):
    # Q(0, v): minus the shortest-path cost from the start  [eq. 4]
    scores = unreachable_scores(graph)
    scores[start] = 0
    scores = propagate(scores, graph, alpha)  # Dijkstra-style  [eq. 5]
    for landmark in landmarks:
        # Add the CLIP match of every node for this landmark  [§4.4]
        scores = scores + clip_match(graph, landmark)  # (V,)
        # Relax along edges: max over neighbours, minus alpha * D  [eq. 5]
        scores = propagate(scores, graph, alpha)
    # Best node after the last landmark  [alg. 1]
    destination = argmax(scores)
    return backtrack(destination, scores)  # [alg. 1]

The paper's constraint is that the matched node indices are non-decreasing, which allows the same node to match two consecutive landmarks §4.4 eq. 3.

Hyperparameters

Results

Author-reported. Real robot, Clearpath Jackal UGV, outdoor suburban environments; the graph is built from a manual drive; LLM and VLM queries are pre-computed on a remote workstation §5.1 §5.2.

Headline: 0.8 net success in both environments, with 0 and 0.1 disengagements per experiment, and efficiency 0.96 (small) and 0.89 (large) tab. 1. The text reports 85% of experiments followed the instruction without collisions or disengagements, and about one intervention per 6.4 km §5.3.

tab. 1 Instruction following, 20 experiments (author-reported):

tab. 2 LLM candidates for landmark extraction, 20 prompts. Metric: longest common subsequence over ground-truth length, articles ignored app. C.2:

tab. 3 VLM candidates, 100 images and 30 landmarks, success if any of the top 3 predictions matches:

tab. 4 Planner ablation. Max-likelihood picks the best node per landmark and connects them by shortest paths app. C.1:

Setup: the paper describes the ablations on the 20 prompts of §5.3 app. C.2. Table 4 uses planning efficiency, which is not the same metric as Table 1 efficiency.

Paper vs code

Code read at commit 8c6b9e01708aa844518b1c68dae257c90a2d0f02 (the code repo is linked from the project page, owned by author Błażej Osiński) [code].

• Edge weights. The paper weights edges by the VNM's learned distance D §4.1. NavigationGraph.add_edge defaults to the Euclidean distance between node positions navigation_graph.py. The graph used in the notebooks is loaded from a pickle navigation_graph.py that is not in the repository, so the weight source there is not verified.
• α. The paper defines α = −log γ and does not give γ eq. 3. The code uses α = 0.0002 pipeline.py. The default α of 0.2 in find_optimal_route is never used by the pipeline optimal_route.py.
• Similarity used by the search. The paper applies a softmax over nodes to CLIP outputs §4.3. The code uses the raw cosine similarity between the text and image embeddings, with no softmax and no logit scale, and takes the maximum over all images stored at a node optimal_route.py. The paper's Algorithm 1 uses one image per node alg. 1.
• CLIP prompt and model. The paper uses "This is a photo of" §4.3 and does not name the CLIP variant. The code uses "A photo of " and ViT-L/14 optimal_route.py optimal_route.py.
• Image preprocessing. The code crops and rectifies each image before CLIP optimal_route.py. The paper does not describe this.
• LLM prompt. The paper says three examples are used §4.2 and shows two in its appendix app. A.1. The code's default prompt has three different examples, and the two-example prompt is used only when simple_prompt=True landmark_extraction.py landmark_extraction.py.
• LLM engine and decoding. The paper names GPT-3 only app. A.1. The code uses text-davinci-002 with temperature 0 and max 256 tokens [code: lm_nav/landmark_extraction.py#L62-L63] landmark_extraction.py.
• Graph search. The per-landmark update in find_optimal_route (add the similarity to every node, then relax with α times the edge weight, then take the argmax at the end) matches Algorithm 1 and eq. 5 [code: lm_nav/optimal_route.py#L71-L86]. No discrepancy found.
• Start score. The paper sets Q(0, v) to minus the shortest-path cost §4.4. The code sets the start to 0, the others to -1e9, then relaxes [code: lm_nav/optimal_route.py#L71-L73]. Same result, different sentinel.
• Not in the repository. Graph building (Algorithm 2, ε, τ, η, transitive reduction), the navigation model, robot execution and the GPS-Nav ablation are not in the code. The max-likelihood planner is described in the appendix app. C.1 but is not in lm_nav/.
• Search for code. The paper's project page (sites.google.com/view/lmnav) links the GitHub repository above, and its owner is author Błażej Osiński. That link was enough, so no further GitHub search was run. The same page links a Colab notebook, colab_experiment.ipynb, in that repo.

No other discrepancies found.

Pitfalls

• Scale of the CLIP term. The score in eq. 3 is only correct up to a constant if the CLIP term is a log-probability or a scaled logit. The paper calls CLIP outputs logits and then uses a softmax over nodes §4.3. The softmax's per-landmark constant adds the same amount to every walk, so it does not change the chosen walk eq. 2 eq. 3. The scale does: the code uses unscaled cosine similarity optimal_route.py, so the balance against α·D depends on whether that scale is used. Keep the code's choice when reproducing numbers.
• Units of D. The paper defines D as predicted time steps from the VNM §4.1. The code's default edge weight is a metre-scale distance between positions navigation_graph.py. Using α = 0.0002 on one when the other is intended changes the search trade-off a lot.
• Repeated landmark match. The constraint allows the same node to match consecutive landmarks eq. 3. The code does not prevent it. For instructions with two landmarks that sit at the same place, check the walk.
• Unreachable nodes. The code uses -1e9 in a float32 array as the start value optimal_route.py. Scores of unreachable nodes stay very negative; this is fine for argmax if the graph is connected from the start, but the sentinel is not -inf.
• Recomputed CLIP features. Each query re-encodes every stored image with CLIP ViT-L/14 on the GPU, with no caching optimal_route.py. The cost grows with the number of images in the graph. Each query also calls the LLM once landmark_extraction.py.
• Graph building is not reproducible from this repo. Algorithm 2 and its thresholds (ε = 1 s, τ = 80 steps, η = 100 m) are in the appendix app. B, but the code is not released here. Plan to implement it from alg. 2.
• Missing and hard landmarks. Failure cases come from the VLM not detecting landmarks such as a fire hydrant or cement mixer §5.2 fig. 4. Detection rate is 0.87 on the authors' test set tab. 3, and the paper does not report a per-landmark breakdown.
• Verbs and commands are dropped. The system keeps only landmarks and ignores verbs and other instructions such as "go straight for three blocks" §6.
• Prompt examples. The text says three in-context examples §4.2; the appendix shows two app. A.1. The code's default prompt uses three other examples landmark_extraction.py. Use the code's prompt if you need to match the released system.
• Reported success differs. The text says 85% §5.3; Table 1 reports 0.8 in both environments tab. 1. Treat the 0.8 figure as the table value.
• Efficiency is clipped. The efficiency metric is capped at 1 when the robot takes a shorter route than described §5.3, so efficiency can hide shortcuts.
• Planning vs execution. LLM and VLM queries run on a remote workstation, and the navigation model runs on board, using forward RGB and unfiltered GPS §5.1. Latency and connectivity during execution are not reported.

Lineage

• Builds on: ViNG, the visual navigation model §3 (Shah et al., 2020, as cited in the paper); GPT-3 for landmark extraction §4.2 (Brown et al., 2020); CLIP for grounding §4.3 (Radford et al., 2021). arXiv ids are not given in the paper's bibliography.
• Compared against: other LLMs for extraction tab. 2; Faster-RCNN and ViLD for grounding tab. 3; GPS-Nav without the VNM and the max-likelihood planner tab. 1 tab. 4.
• Superseded by: not stated in this card's sources.