ViKiNG: Vision-Based Kilometer-Scale Navigation with Geographic Hints

Authors: Dhruv Shah, Sergey Levine · RSS 2022

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

ViKiNG pairs an image-based local controller with an A*-like search guided by satellite images or roadmaps, reaching goals over a kilometre away after training on runs under 80 m.

Why it matters

It shows how cheap, imperfect map data can guide long-range robot navigation without building a geometric map, while control stays robust when the map is out of date. Following sidewalks and trails and backing out of dead ends come from the training data and the search, not from hand-written rules.

Problem

A robot sent to a distant goal in an unseen outdoor environment needs both local traversability reasoning and knowledge of the wider geography. Geometric mapping methods do not benefit from prior data, learned navigation policies have reached only short ranges, and the available maps and GPS (accurate to 2–5 m, 4–10× the robot's size) may be outdated or wrong, so they cannot be trusted for control.

Proposed solution

A latent goal model trained on 42 hours of offline driving data takes the current image and a subgoal image and predicts the temporal distance, the next action and the GPS offset; a variational information bottleneck lets it also sample reachable candidate subgoals. A second model, trained with a contrastive objective on training trajectories stitched together by GPS, scores whether a subgoal lies on a path to the goal given an overhead satellite image or roadmap. ViKiNG-A, an A-like physical search over a topological graph built while driving, uses that score only as a heuristic, while every driving action comes from the camera image.

Key insights

Using geographic hints only as a search heuristic, with control from camera images, kept the robot working when the map was outdated (a truck parked across the previous path) or wrong (satellite images offset by about 5 km).
Stitching overlapping training trajectories into longer macro-trajectories by GPS position lets the heuristic learn to score goals far beyond the length of any single training run.
The type of hint changes behaviour: the roadmap-trained model kept to marked roads, while the satellite-trained model cut across meadows for a shorter path.
Navigation behaviours such as following sidewalks and forest trails are inherited from the teleoperated part of the training data; there is no separate mechanism that rewards staying on trails.
Physical search differs from graph search: the robot cannot jump to arbitrary nodes and does not know edge costs before driving, so ViKiNG-A* adds driving cost and a visitation-count novelty term to each candidate's cost.

Main results

Goal-seeking in 10 unseen environments (Table I): ViKiNG 3/3 easy (<50 m), 4/4 medium (50–150 m) and 3/3 hard (150–500 m); RECON-H 3/3, 3/4, 1/3; GCG 3/3, 2/4, 0/3; behavior cloning and offline PPO 2/3, 1/4, 0/3.
Before a disengagement on the harder runs (Table II), average displacement was 250.0+ m at 1.36 m/s for ViKiNG versus 188.3 m at 0.41 m/s for RECON-H, 78.3 m at 1.40 m/s for GCG, 47.2 m for offline PPO and 19.5 m for behavior cloning.
Single kilometre-scale runs of 1.05 km, 1.20 km and 1.55 km in unseen campus and city environments, a 2.73 km hiking trail with six checkpoints and 70 m elevation gain (written as 2.7 km in the text), and a 2.65 km suburban inspection loop with no interventions.
The abstract states goals up to 3 km away and the introduction states goals over 2 km away reached in under 25 minutes; the longest runs reported in the experiments are 2.73 km and 2.65 km.
Without overhead images (GPS-distance heuristic only), the robot took 17:20 and 0.73 km versus 06:40 and 0.31 km with satellite images; with neither GPS nor images it did not reach the goal in over 30 minutes.
Average speed in deployment was 1.36 m/s against 1.68 m/s in the training data, whose trajectories average 45 m.

Limitations

The paper has no limitations section. Its discussion names, as future work, using other hint sources such as schematics, paper maps or textual instructions, and says only satellite images were used, although Section V-A also tests schematic roadmaps.
GPS is needed: with neither GPS nor overhead images the search becomes uninformed and did not reach the goal in over 30 minutes.
The baseline comparison is small, with one trial in each of 10 environments and goals up to 500 m; the kilometre-scale runs and the outdated- and wrong-hint tests are single demonstrations.
The heuristic on its own reasons only at the scale of single training trajectories, stated as up to 50 m in Section III-C, while the abstract and Section IV-B give 80 m as the longest training trajectory; long-range scoring depends on stitching trajectories by GPS.
Under a dense tree canopy the satellite image carries no useful information, so progress there relies only on the local image-based model.

Field impact

Finalist for the RSS 2022 Best Systems Paper Award, and cited 121 times. The paper does not link code; its project page shares experiment videos, including third-person views of the robot's runs.

Abstract

Robotic navigation has been approached as a problem of 3D reconstruction and planning, as well as an end-to-end learning problem. However, long-range navigation requires both planning and reasoning about local traversability, as well as being able to utilize information about global geography, in the form of a roadmap, GPS, or other side information, which provides important navigational hints but may be low-fidelity or unreliable. In this work, we propose a learning-based approach that integrates learning and planning, and can utilize side information such as schematic roadmaps, satellite maps and GPS coordinates as a planning heuristic, without relying on them being accurate. Our method, ViKiNG, incorporates a local traversability model, which looks at the robot's current camera observation and a potential subgoal to infer how easily that subgoal can be reached, as well as a heuristic model, which looks at overhead maps and attempts to estimate the distance to the destination for various subgoals. These models are used by a heuristic planner to decide the best next subgoal in order to reach the final destination. Our method performs no explicit geometric reconstruction, utilizing only a topological representation of the environment. Despite having never seen trajectories longer than 80 meters in its training dataset, ViKiNG can leverage its image-based learned controller and goal-directed heuristic to navigate to goals up to 3 kilometers away in previously unseen environments, and exhibit complex behaviors such as probing potential paths and doubling back when they are found to be non-viable. ViKiNG is also robust to unreliable maps and GPS, since the low-level controller ultimately makes decisions based on egocentric image observations, using maps only as planning heuristics.

Open Source Robotics