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

I Introduction

Robotic navigation has conventionally been approached as a geometric problem, where the robot constructs a 3D model of the environment and then plans a path through this model. End-to-end learning-based methods offer an alternative approach, where the robot learns to correlate observations with traversability information directly from experience, without full geometric reconstruction . This can be advantageous because, in many cases, geometry alone is neither necessary nor sufficient to traverse an environment, and a learning-based method can acquire patterns that are more directly indicative of traversability, for example by learning that tall grass is traversable while seemingly traversable muddy soil should be avoided. More generally, such methods can learn about common patterns in their environment, such as that houses tend to be rectangular, or that fences tend to be straight. These patterns can lead to common-sense inferences about which path should be taken through an unknown environment even before that environment has been fully mapped out .

However, dispensing with geometry entirely may also be undesirable: the spatial organization of the world provides regularities that become important for a robot that needs to traverse large distances to reach its goal. In fact, when humans navigate new environments, they make use of both geographic knowledge, obtained from overhead maps or other cues, and learned patterns . But in contrast to SLAM, humans don’t require maps or auxiliary signals to be very accurate: a person can navigate a neighborhood using a schematic that roughly indicates streets and houses, and reach a house marked on it. Humans do not try to accurately reconstruct geometric maps, but use approximate “mental maps” that relate landmarks to each other topologically . Our goal is to devise learning-enabled methods that similarly make use of geographic hints, which could take the form of GPS, roadmaps, or satellite imagery, without requiring these signals to be perfect.

We consider the problem of navigation from raw images in a novel environment, where the robot is tasked with reaching a user-designated goal, specified as an egocentric image, as shown in Figure LABEL:fig:teaser. Note that the robot has no prior experience in the target environment.The robot has access to geographic side information in the form of a schematic roadmap or satellite imagery (see Figure 2), which may be outdated, noisy, and unreliable, and approximate GPS. This information, while not sufficient for navigation by itself, contains useful cues that can be used by the robot. The robot also has access to a large and diverse dataset of experience from other environments, which it can use to learn general navigational affordances. We posit that an effective way to build such a robotic system is to combine the strengths of machine learning with informed search, by incorporating the geographic hints into a learned heuristic for search. The robot uses approximate GPS coordinates and an overhead map as geographic side information to help solve the navigation task, but does not assume that this information is particularly accurate—resembling a person using a paper map, the robot uses the GPS localization and an overhead map as hints to aid in visual navigation. Note that while we do assume access to GPS, the measurements are only accurate up to 2-5 meters (4-10$\times$ the scale of the robot), and cannot be used for local control.

The primary contribution of this work is \algoName, an algorithm that combines elements of end-to-end learning-based control at the low level with a higher-level heuristic planning method that uses this image-based controller in combination with the geographic hints. The local image-based controller is trained on large amounts of prior data from other environments, and reasons about navigational affordances directly from images without any explicit geometric reconstruction. The planner selects candidate waypoints in order to reach a faraway goal, incorporating the geographic side information as a planning heuristic. Thus, when the hints are accurate, they help the robot navigate toward the goal, and when they are inaccurate, the robot can still rely on its image observations to search through the environment. We demonstrate \algoNameon a mobile ground robot and evaluate its performance in a variety of open-world environments not seen in the training data, including suburban areas, nature parks, and a university campus. Our local controller is trained on 42 hours of navigational data, and we test our complete system in 10 different environments. Despite never seeing trajectories longer than 80 meters in its training data, \algoNamecan effectively use geographic side information in the form of overhead maps to reach user-specified goals in previously unseen environments over 2 kilometers away in under 25 minutes.

II Related Work

Robotic navigation has been studied from a number of different perspectives in different fields. Classically, it is often approached as a problem of geometric mapping or reconstruction followed by planning . In unknown environments, the mapping problem can be formulated in terms of information gain with local strategies , global strategies based on the frontier method , or by sampling “next-best views” , but such methods typically aim to map or reconstruct an entire environment, rather than achieve a single navigational goal. Active exploration methods have sought to modify this by jointly incentivizing an exploration objective along with reconstruction of the map . Both the goal-directed and mapping-focused methods aim to reconstruct the geometry of their environment, and do not directly benefit from training with prior data. Some approaches have sought to incorporate learning into mapping and reconstruction , which benefits from prior data, but still aims at dense geometric reconstruction. Our approach uses a model that is trained with data from prior environments to predict traversability rather than geometry, and this model is then used in combination with geographic hints to plan a path to the goal.

In this respect, \algoNameis also related to prior work on learning-based navigation, which is often formulated in terms of the “PointGoal” task . Many such works rely on simulation and reinforcement learning, utilizing millions (or billions) of online trials to train a policy . In contrast, our method learns entirely from previously collected offline data, extrapolates to significantly longer paths than it is trained on, and does not require any simulation or online RL.

A number of prior learning-enabled methods also combine learned models with graph-based planning, using a topological graph to represent the environment . These methods often assume access to data from the test environment to start with a viable graph, which may not be available in a new environment. Some works have studied this unseen setting by predicting explorable areas for semantically rich parts of the environment to accelerate visual exploration . While these methods can yield promising results in a variety of domains, they come at the cost of high sample complexity (over 10M samples) , making them difficult to use in the real world—the most performant algorithms take 10-20 minutes to find goals up to 50m away .

The closest prior work to \algoNameis by Shah et al. (RECON) , which uses a learned representation over feasible subgoals to uniformly explore the environment. Like RECON, our method trains a local model that predicts temporal distances and actions for nearby subgoals, and then incorporates this model into a search procedure that incrementally constructs a topological graph in a novel environment. However, in contrast to RECON, which performs an uninformed search, \algoNameincorporates geographic hints in the form of approximate GPS coordinates and overhead maps. This enables \algoNameto reach faraway goals, up to 25$\times$ further away than the furthest goal reported by RECON, and to reach goals up to 15$\times$ faster than RECON when exploring a novel environment.

III Visual Navigation with Geographic Hints

Our aim is to design a robotic system that learns to use first-person visual observations to reach user-specified landmarks, while also utilizing geographic hints in the form of approximate GPS coordinates and overhead maps. At the core of our approach is a deep neural network that takes in the robot’s current camera observation $o_{t}$, as well as an observation $o_{w}$ of a potential subgoal $w$ (we use “subgoal” and “waypoint” interchangeably), and predicts the time to reach $w$ (or “temporal distance”), the best current action to do so, and the resulting spatial offset in terms of GPS coordinates. This model can also sample latent representations of potential reachable waypoints from the current observation $o_{t}$, which are used as candidate subgoals for planning. The model is trained on large amounts of data from a variety of training environments and, when the robot is placed in a new environment that it has not seen, it is used to incrementally construct a topological (non-geometric) graph to navigate to a distant user-specified goal. This goal is indicated by a photograph with an approximate GPS coordinate, and may be several kilometers away. The learned model alone is insufficient to navigate to such a distant goal in one shot, and therefore our planner uses a combination of the model’s predictions and geographic information to plan a sequence of subgoals that search for a path through the environment, incrementally constructing the graph.

This process corresponds to a kind of heuristic search, where the geographic side information provides a heuristic to bias the robot to explore towards the goal as it constructs the topological graph. The latent goal model is used to determine reachability in this topological graph, and the geographic heuristic is used to steer the graph by exploring the environment. In a novel environment, the robot must incrementally build this graph using physical search, by visiting new nodes and expanding its frontier. The decision about where to actually go is determined by the first-person images, and the geographic information is used only as a heuristic, allowing \algoNameto remain robust to noisy or unreliable side information. We overview our method in Figure 3.

Our low-level model maps the current image observation $o_{t}$ and a waypoint observation $o_{w}$ to: (1) the temporal distance $d_{t}^{w}$ to reach $w$ from $o_{t}$; (2) the first action $a_{t}^{w}$ that the robot must take now to reach $w$; (3) a prediction of the (approximate) offset in GPS readings between $o_{t}$ and $w$, $x_{t}^{w}$. (1) and (3) will be used by the higher-level planner, and (2) will be used to drive to $w$, if needed. We would also like this model to be able to propose, in a learned latent space, potential subgoals $w$ that are reachable from $o_{t}$, and predict their corresponding values of $d_{t}^{w}$, $a_{t}^{w}$, and $x_{t}^{w}$.

We present the model in Figure 4, with precise architecture details in the supplementary materials. The model is trained by sampling pairs of time steps in the trajectories in the training set. For each pair, the earlier time step image becomes $o_{t}$, and the later image becomes $o_{w}$. The number of time steps between them provides the supervision for $d_{t}^{w}$, the action taken at the earlier time step supervises $a_{t}^{w}$, and the later GPS reading is transformed into the coordinate frame of the earlier time step to provide supervision for $x_{t}^{w}$. The model is trained via maximum likelihood. Note that by training the model on data in this way, we not only enable it to evaluate reachability of prospective waypoints, but also make it possible to inherit behaviors observed in the data. For example, in our experiments, we will show that the model has a tendency to follow sidewalks and forest trails, a behavior it inherits from the portion of the dataset that is collected via teleoperation.

Besides predicting $d_{t}^{w}$, $a_{t}^{w}$, and $x_{t}^{w}$, our planner requires this model to be able to sample potential reachabale waypoints from $o_{t}$ (see Figure 3). We implement this via a variational information bottleneck (VIB) inside of the model that bottlenecks information from $o_{w}$. Thus, the model can either take as input a real image $o_{w}$ of a prospective waypoint, or it can sample a latent waypoint $z_{t}^{w}\sim r(z_{t}^{w})$ from a prior distribution. We train the model so that sampled latent waypoints correspond to feasible locations that the robot can reach from $o_{t}$ without collision.

Training the latent goal model: The full model, illustrated in Figure 4, can be split into three parts: a waypoint encoder $p_{\phi}(z_{t}^{w}|o_{w},o_{t})$, a waypoint prior $r(z_{t}^{w})$, and a predictor $q_{\theta}(\{a,d,x\}_{t}^{w}|z_{t}^{w},o_{t})$. The latent waypoint representation $z_{t}^{w}$ can either be sampled from the prior (which is fixed to $r(z_{t}^{w})\triangleq\mathcal{N}(0,I)$), or from the encoder $p_{\phi}(z_{t}^{w}|o_{w},o_{t})$ if a waypoint image $o_{w}$ is provided. This latent waypoint is used together with $o_{t}$ to predict all desired quantities according to $q_{\theta}(\{a,d,x\}_{t}^{w}|z_{t}^{w},o_{t})$. The training set consists of tuples $(o_{t},o_{w},\{a,d,x\}_{t}^{w})$, but the model must be trained so that samples $z_{t}^{w}\sim r(z_{t}^{w})$ also produce valid predictions. We accomplish this by means of the VIB , which regularizes the encoder $p_{\phi}(z_{t}^{w}|o_{w},o_{t})$ to produce distributions that are close to the prior $r(z_{t}^{w})$ in terms of KL-divergence. We refer the reader to prior work for a derivation of the VIB , and present our training objective for $p_{\phi}$ and $q_{\theta}$ below:

The outer expectation over all tuples $(o_{t},o_{w},\{a,d,x\}_{t}^{w})\in\mathcal{D}$ in the training distribution is estimating using the training set. The first term causes the model to accurately predict the desired information, while the second term forces the encoder to remain consistent with the prior, which makes the model suitable for sampling latent waypoints according to $z_{t}^{w}\sim r(z_{t}^{w})$. As the encoder $p_{\phi}$ and decoder $q_{\theta}$ are conditioned on $o_{t}$, the representation $z_{t}^{w}$ only encodes relative information about the subgoal from the context—this allows the model to represent feasible subgoals in new environments, and provides a compact representation that abstracts away irrelevant information, such as time of day or visual appearance. An analogous representation has been proposed in prior work , but did not predict spatial offsets and was used only for uninformed exploration without geographic hints.

III-B Informed Search on a Topological Graph

The model described above can effectively reach nearby subgoals, for example those on which the robot has line of sight, but we wish to reach goals that are more than a kilometer away. To reach distant goals, we combine the model with a search procedure that incorporates geographic hints from satellite images or roadmaps. The system does not require this information to be accurate, instead using it as a planning heuristic while still relying on egocentric camera images for control. Our high-level planner plans over a topological graph ${\mathcal{T}}$ that it constructs incrementally using the low-level model in Section III-A as a local planner. We first describe a generic version of the algorithm for any heuristic, and then describe the data-driven heuristic function that we extract from the geographic hints via contrastive learning.

Challenges with physical search: Our “search” process involves the robot physically searching through the environment, and is not purely a computational process. In contrast to standard search algorithms (e.g., Dijkstra, A∗, IDA∗, D∗, etc.), each “step” of our search involves the robot driving to a subgoal and updating the graph. Standard graph search algorithms assume (i) the ability to visit any arbitrary node, and (ii) access to a set of neighbors for every node and the corresponding “edge weight,” before visiting each neighbor. Physical search with a robot violates these assumptions, since robots cannot “teleport” and visiting a node incurs a driving cost. Furthermore, the real world does not provide “edge weights” and the robot needs to estimate the cost to reach an unvisited node before actually driving to it.

An algorithm for informed physical search: To solve these challenges, we design \algoName-A∗, an A∗-like search algorithm that uses our latent goal model and a learned heuristic to perform physical search in real-world environments. While \algoName-A∗ does prefer shorter paths, it does not aim to be optimal (in contrast to A∗), only to reach the goal successfully. We will use a heuristic $h(w)$, fully described in the next section, which we assume provides a comparative evaluation of candidate waypoints in terms of their anticipated temporal distance to the destination. Algorithm 1 outlines \algoName-A∗.

Like A∗, \algoName-A∗ maintains a priority queue “open set” $\Omega$ of unexplored fringe nodes and a “current” node that represents the least-cost node in this set, which we refer to as $w_{t}$. It also maintains a graph with visited waypoints, $\mathcal{T}$, where nodes correspond to images seen at those nodes, and edges correspond to temporal distances estimated by the model in Section III-A. At every iteration, the robot drives to the least-cost node in the open set (L5), using a procedure that we outline later. When it reaches $w_{t}$, it observes the image $o_{t}$ using its camera (L6). This allows it to add $o_{t}$ to the graph $\mathcal{T}$ (L7), connecting it to other nodes by evaluating the distances using the model in Section III-A. The graph construction is analogous to prior work . If the robot is close to the final goal image $o_{G}$ according to the model (L8), the search ends. $o_{t}$ also allows it to sample nearby candidate waypoints using the model in Section III-A (L10): first sampling $z_{t}^{w}\sim r(z_{t}^{w})$ from the prior, and then decoding distances $d_{t}^{w}$, $a_{t}^{w}$, and $x_{t}^{w}$, from which it can compute absolute locations as $x_{w}=x_{t}+x_{t}^{w}$. Each sampled waypoint is stored in the open set, and annotated with the current image $o_{t}$ and $d_{t}^{w}$. We refer to $w_{t}$ as the parent of $w$, and index it as $\text{Pr}[w]$. Note that we do not have access to the image $o_{w}$, as we have not visited the sampled waypoint $w$ yet, and therefore we must store the current image $o_{t}$ instead. This also means that we cannot connect these waypoints to the graph $\mathcal{T}$ except through their parent. Next, we re-estimate the cost of each waypoint in the open set, including the newly added waypoints.

The cost for each waypoint $w\in\Omega$ from the current point $w_{t}$ consists of four terms (L14): (1) $g(t,w)$, the cost to navigate to the parent of $w$, which is part of the graph $\mathcal{T}$; this can be computed as a shortest path on the graph $\mathcal{T}$, and is zero for the current node. (2) $d_{\text{Pr}[w]}^{w}$, the distance from the parent of $w$ to $w$ itself. (3) $h(w)$, the heuristic cost estimate of reaching the final goal from $w$ (see Section III-C). (4) $v(\text{Pr}[w])$, the visitation count of $\text{Pr}[w]$, computed as $CN(\text{Pr}[w])$, where $C$ is a constant and $N(\text{Pr}[w])$ is a count of how many times the robot drove to $\text{Pr}[w]$ via the DriveTo subroutine; this acts as a novelty bonus to encourage the robot to explore novel states, a strategy widely used in RL . Summing these terms expresses a preferences for nodes that are fast to reach from $w_{t}$ (1 + 2), get us closer to the goal (3), and have not been heavily explored before (4). At the next iteration (L4), the robot picks the lowest-cost waypoint and again drives to it.

III-C Learning a Goal-Directed Heuristic for Search

We now describe how we extract a heuristic $h$ from geographic side information. As a warmup, first consider the case where we only have the GPS coordinates for a waypoint ($x_{w}$) and final goal ($x_{G}$). We can use $\|x_{g}-x_{w}\|$ as a heuristic to bias the search to waypoints in the direction of the goal, and this heuristic can be readily obtained from the model in Section III-A. However, we would like to compute the heuristic function using some side information $c_{t}$, such as a roadmap or satellite image, that does not lie in a metric space. Thus, we need to learn the heuristic function from data. Since \algoName-A∗ does not aim to be optimal (only seeking a feasible path), we do not require the heuristic to be admissible.

We train the heuristic $h_{\text{over}}(x_{w},x_{G},x_{t},c_{t})$ to score the favorability of a sampled candidate waypoint $w$ for reaching the goal $G$ from current location $x_{t}$, given side information $c_{t}$. In our case, $c_{t}$ is an overhead image that is roughly centered at the current location of the robot. Our heuristic is based on an estimator for the probability $p_{\text{over}}(w\rightarrow G|x_{w},x_{G},x_{t},c_{t})$ that a given waypoint $w$ lies on a valid path to the goal $G$. We use the same training set as in Section III-A to learn a predictor for $p_{\text{over}}$. Given $p_{\text{over}}$, we can generate a heuristic $h_{\text{over}}:=\lambda_{\text{over}}(1-p_{\text{over}})$ to steer \algoName-A∗ towards the goal (Alg. 1 L13). Note that, since we evaluate the heuristic for sampled candidate waypoints, we do not have access to $x_{w}$, but we can predict it by using the model in Section III-A to infer the offset $x_{t}^{w}$ using $o_{t}$ and the sampled latent code, and then calculate $x_{w}$ from $x_{t}$ and $x_{t}^{w}$. Thus, the heuristic is technically a function of $c_{t}$, $o_{t}$, $x_{t}$, and $x_{G}$.

Our procedure for training $p_{\text{over}}(w\rightarrow G|x_{w},x_{G},x_{t},c_{t})$ is based on InfoNCE , a contrastive learning objective that can be seen as a binary classification problem between a set of positives and negatives. At each training iteration, we sample a random batch ${\mathcal{B}}$ of sub-trajectories $k$ from our training set, where $x_{S}$ is the start of $k$ and $x_{E}$ is the end, and $c_{S}$ is an overhead image centered at $x_{S}$. We sample a positive example by picking a random time step in this subtrajectory, and using its position $x_{w^{+}}$. The negatives $x_{w^{-}}$ are locations of other randomly sampled time steps from other trajectories, comprising the set ${\mathcal{W}}^{-}$. In this way, we train a neural network model to represent $p_{\text{over}}(w\rightarrow G|x_{w},x_{G},x_{t},c_{t})$ (see Figure 4, right) via the InfoNCE objective:

This heuristic can only reason about waypoints and goals at the scale of individual trajectories in the training set (up to 50m). For kilometer-scale navigation, the heuristic needs to make predictions for goals that are much further away, so we take inspiration from goal chaining in reinforcement learning and combine overlapping trajectories in the training set (according to GPS positions) into larger trajectory groups. For a batch ${\mathcal{B}}$ of trajectories, we combine two trajectories if they intersect in 2D space. The resulting macro-trajectories thus have multiple start and goal positions, and can extend for several kilometers. We then sample the sub-trajectories for $x_{S}$, $x_{E}$, and $x_{w^{+}}$ from these much longer macro-trajectories, giving us positive examples between very distant $x_{S}$, $x_{E}$ pairs. This allows $p_{\text{over}}$ to be trained on a vast pool of long-horizon goals and improves the reliability of the heuristic. We provide more details about this procedure in Appendix -A.

IV \algoNamein the Real World

We now describe our experiments deploying \algoNamein a variety of real-world outdoor environments for kilometer-scale navigation. Our experiments compare \algoNameto other learning-based methods, evaluate its performance at different ranges, and study how it responds to degraded or erroneous geographic information.

We implement \algoNameon a Clearpath Jackal UGV platform (see Fig. LABEL:fig:teaser). The default sensor suite consists of a 6-DoF IMU, a GPS unit for approximate global position estimates, and wheel encoders to estimate local odometry. Under open skies, the GPS unit is accurate up to 2-5 meters, which is 4-10$\times$ the size of the robot. In addition, we added a forward-facing $170^{\circ}$ field-of-view RGB camera. Compute is provided by an NVIDIA Jetson TX2 computer, and a cellular hotspot connection provides for monitoring and (if necessary) teleoperation. Our method uses only the monocular RGB images from the onboard camera, unfiltered measurements from onboard GPS, and overhead images (roadmap or satellite) queried at the current GPS location, without any other processing.

IV-B Offline Training Dataset

Our aim is to leverage data collected in a wide range of different environments to (i) enable the robot to learn navigational affordances that generalize to novel environments, and (ii) learn a global planning heuristic to steer physical search in novel environments. To create a diverse dataset capturing a wide range of navigation behavior, we use 30 hours of publicly available robot navigation data collected using an autonomous, randomized data collection procedure in office park style environments . We augmented this dataset with another 12 hours of teleoperated data collected by driving on city sidewalks, hiking trails, and parks. Notably, \algoNamenever sees trajectories longer than 80 meters, but is able to leverage the learned heuristic (Section III-C) to reach goals over a kilometer away at over 80% of the average speed in the training set. The average trajectory length in the dataset is 45m, whereas our experiments evaluate runs in excess of 1km. The average velocity in the dataset is 1.68 m/s, and the average velocity the robot maintains in testing is 1.36 m/s. We provide more details about the dataset in Appendix -B.

IV-C Kilometer-Scale Testing

For evaluation, we deploy \algoNamein a variety of previously unseen open-world environments to demonstrate kilometer-scale navigation. Figure 5 shows the path taken by the robot in search for a user-specified goal image and location. \algoNameis able to utilize geographic hints, in the form of a roadmap or satellite image centered at its current position, to steer its search of the goal. In a university campus (Fig. 5(a, c)), we observe that the robot can identify large buildings along the way and plan around it, rather than following a greedy strategy. Since the training data often contains examples of the robot driving around buildings, \algoNameis able to leverage this prior experience and generalize to novel buildings and environments. On city roads (Fig. 5(b)), the learned heuristic shows preference towards following the sidewalks, a characteristic of the training data in city environments. It is important to note that while the robot has seen some prior data on sidewalks and in suburban neighborhoods, it has never seen the specific areas (see Appendix -B for further details). For videos of our experiments, please check out our project page.

These long-range experiments also exhibit successful backtracking behavior—when guided into a cul-de-sac by the planner, \algoNameturns around and resumes its search for the goal from another node in the “openSet”, reaching the goal successfully (see Figure LABEL:fig:teaser(h)). While the learned heuristic provides high-level guidance, the local control is done solely from first person images. This is illustrated in Figure LABEL:fig:teaser(g), where the robot navigates through a forest, where the satellite image does not contain any useful information about navigating under a dense canopy. \algoNameis able to successfully navigate through a patch of trees using the image-based model described in Section III-A. We can also provide \algoNamewith a set of goals to execute in a sequence to provide more guidance about the path (e.g., an inspection task with landmarks), as demonstrated in the next experiment.

A hiking \algoName: We deploy \algoName, with access to satellite images as hints, on a 2.7km hiking trail with a 70m elevation gain by providing a sequence of six checkpoint images and their corresponding GPS coordinates. Algorithmically, we run \algoName-A∗ on every goal (one at a time) while reusing the topological graph ${\mathcal{T}}$ across goals. Figure 6 shows a top-down view of the path taken by the robot—\algoNameis able to successfully combine the strengths of a learned controller for collision-free navigation with a learned heuristic that utilizes the satellite images to encourage on-trail navigation between checkpoints. Since the offline dataset contains examples of trail-following, the robot learns to stay on trails when possible. This behavior is emergent from the data—there is no other mechanism that encourages staying on the trails, and in several cases, a straight-line path between the goal waypoints would not stay on the trail (e.g., the first checkpoint in Figure 6).

Autonomous visual inspection: We further deploy \algoNamein a suburban environment for the task of visual inspection specified by five images of interest. \algoNameis able to successfully navigate to the landmarks by using satellite imagery, traveling a distance of 2.65km without any interventions. Figure 7 shows the specified images and a top-down view of the path taken by the robot on the trail.

IV-D Quantitative Evaluation and Comparisons

We compare \algoNameto four prior approaches, each trained using the same offline data as our method. All methods have access to the egocentric images, GPS location, and satellite images, and control the robot via the same action space, corresponding to linear and angular velocities.

Behavioral Cloning: A goal-conditioned behavioral cloning (BC) policy trained on the offline dataset that maps the three inputs to control actions .

PPO: A policy gradient algorithm that maps the three inputs to control actions. This comparison is representative of state-of-the-art “PointGoal” navigation in simulation .

GCG: A model-based algorithm that uses a predictive model to plan a sequence of actions that reach the goal without causing collision . We use GCG in the goal-directed mode with a GPS target, using the onboard camera and satellite images as input modalities.

RECON-H: A variant of RECON, which uses a latent goal model to represent reachable goals and plans over sampled subgoals to explore a novel environment . We modify the algorithm to additionally accept the GPS and satellite images as additional inputs alongside the onboard camera image.

We evaluate the ability of \algoNameto discover visually-indicated goals in 10 unseen environments of varying complexity. For each trial, we provide an RGB image of the desired target and its rough GPS location (accurate up to 5 meters). A trial is marked successful if the robot reaches the goal without requiring a human disengagement (due to a collision or getting stuck). We report the success rates of all methods in these environments in Table I and visualize overhead plots of the trajectories in one such environment in Figure 8.

outperforms all the prior methods, successfully navigating to goals that are over up to 500 meters away in our comparisons, including instances where no other method succeeds. RECON-H is the most performant of the other methods, successfully reaching most goals in the easier environments. Visualizing the robot trajectories (Fig. 8) reveals that RECON-H is unable to successfully utilize the geographic hints and explores greedily on encountering an obstacle. It also gets stuck and is unable to backtrack in 2/10 instances. While GCG also performs well in simpler environments, it is limited by its planning horizon (up to 5 seconds) and gets stuck. PPO and BC both are both unable to learn from prior data and produce collisions with bushes and a parked car, respectively. In contrast, \algoNameis able to effectively use the local controller to avoid the obstacles and reach the goal.

Analyzing the performance in the harder tasks with ranges of up to 500 meters (Table II), the average displacements and velocities before a user disengagement (due to collision or getting stuck) during these runs further confirm that \algoNameis able to effectively use the geographic hints to steer the search without running into obstacles. While RECON-H manages to reach some faraway goals, it takes a greedy path to do so and is over 3$\times$ slower than \algoName(see Fig. 8).

V The Role of Geographic Hints

In this section, we closely examine the role of geographic hints on the performance of \algoNameby studying how it deals with a low-fidelity roadmap (versus a satellite image), and with incorrect hints and degraded geographic information. For the experiment in Section V-A, we use models trained on the same dataset, but using schematic roadmaps as geographic hints. In Sections V-B and V-C, we use the same satellite image model from Section IV, with no additional retraining to accommodate missing or imperfect geographic information.

To understand the nature of hints learned by the heuristic for different sources of geographic side information, we compare two separate versions of \algoName: one trained with schematic roadmaps as hints, and another trained with satellite images. Note that the method is identical in both cases, only the hint image in the data changes. For identical start-goal pairs, we observe that a model trained with roadmaps prefers following marked roads, whereas one trained with satellite images often cuts across patches of traversable terrain (e.g., grass meadows or trails) to take the quicker path, despite being trained on the same data. We hypothesize that this is due to the ability of the learned models to extract better correlations from the feature-rich satellite images, in contrast to the more abstract roadmap. Figure 9 shows a top-down view of the paths taken by the robot in the two cases in one such experiment.

V-B Outdated Hints

To test the robustness of \algoNameto outdated hints, we set up a goal-seeking experiment in one of the earlier environments and added a new obstacle—a large truck—blocking the path that \algoNametook in the original trial. Since the satellite images are queried from a pre-recorded dataset, they do not reflect the addition of the truck, and hence continue to show a feasible path. We observe that the robot drives up to the truck and takes an alternate path to the goal, without colliding with it (see Figure 10). The lower-level latent goal model is robust to such obstacles and only proposes valid subgoal candidates that do not lead to collision; since the learned heuristic only evaluates valid subgoals, \algoNameis robust to small discrepancies in the hints.

V-C Incorrect Hints

Next, we set up a goal-seeking experiment in one of the easy environments with modified GPS measurements, so that the satellite images available to \algoNameare offset by a $\sim$5km constant. As a result, this hints to the robot that there may be a road that it should follow, where in fact there isn’t one (see Figure 11). We observe that the robot indeed deviates from its earlier path (with a valid map, the robot drives straight to the goal); upon overlaying this trajectory on the invalid map, we find that the learned heuristic indeed encourages the robot to follow the curvature of the road, but this path is still successful because it corresponds to open space.

V-D A Disoriented \algoName

Finally, we analyze the effects of disabling the geographic hints and GPS localization on the goal-seeking performance of \algoName. Towards this, we run two variants of our algorithm:

No GPS: The robot does not have access to GPS or satellite images. To accommodate this, we remove the heuristic $h$ from \algoName-A∗, making it an uninformed search algorithm.

Figure 12 summarizes the path taken by the robot, distance traversed, and time taken. When we disable the overhead hints and only use $h_{\text{GPS}}$, \algoName-A∗ can still reach the destination, but takes significantly longer to do so, initially exploring a dead-end path that it then has to back out of. That said, this experiment also illustrates the ability of \algoName-A∗ to handle less useful heuristics: while the path is significantly longer, the method is still able to eventually reach the destination, and in some sense the mistakes the method makes are to be expected of any system that has no prior map information. If we remove GPS as well, \algoName-A∗ corresponds to a Dijkstra-like uninformed search (resembling RECON ). In this case, the robot searches its environment without any guidance and is unable to reach the goal in over 30 minutes.

VI Discussion

We proposed a method for efficiently learning vision-based navigation in previously unseen environments at a kilometer-scale. Our key insight is that effectively leveraging a small amount of geographic knowledge in a learning-based framework can provide strong regularities that enable robots to navigate to distant goals. We find that incorporating geographic hints as goal-directed heuristics for planning enables emergent preferences such as following roads or hiking trails. Additionally, \algoNameonly uses the hints for biasing the high-level search; the learned control policy at the lower-level relies solely on egocentric image observations, and is thus robust to imperfect hints. While we only use overhead images in our experiments, an existing avenue for future work is to explore how such a system could use other information sources, including paper maps or textual instructions, which can be incorporated into our contrastive objective.

Acknowledgments

This research was partially supported by DARPA Assured Autonomy, ARL DCIST CRA W911NF-17-2-0181, DARPA RACER, and Toyota Research Institute. The authors would like to thank Blazej Osinski, Dieter Fox, Tambet Matiisen, Brian Ichter, and Katie Kang for useful discussions.

References

-A Implementation Details

Inputs to the encoder $p_{\phi}$ are pairs of observations of the environment—current and goal—represented by a stack of two RGB images obtained from the onboard camera at a resolution of $160\times 120$ pixels. $p_{\phi}$ is implemented by a MobileNet encoder followed by a fully-connected layer projecting the $1024$-dimensional latents to a stochastic, context-conditioned representation $z_{t}^{w}$ of the goal that uses $64$-dimensions each to represent the mean and diagonal covariance of a Gaussian distribution. Inputs to the decoder $q_{\theta}$ are the context (current observation)—processed with another MobileNet—and $z_{t}^{w}$. We use the reparametrization trick to sample from the latent and use the concatenated encodings to learn the optimal actions $a_{t}^{w}$, temporal distances $d_{t}^{w}$ and spatial offsets $x_{t}^{w}$. Details of our network architecture are provided in Table III. During pretraining, we maximize ${\mathcal{L}}_{\text{VIB}}$ (Eq. 1) with a batch size of 128 and perform gradient updates using the Adam optimizer with learning rate $\lambda=10^{-4}$ until convergence.

-A2 Learned Heuristic (Section III-C)

Inputs to the encoder $p_{\text{over}}$ are (i) satellite image $c_{S}$ and (ii) the triplet of GPS locations $\{x_{w},x_{S},x_{G}\}$. $p_{\text{over}}$ is implemented as a multi-input neural network with a MobileNet encoder to featurize $c_{S}$, which is then concatenated with the location inputs. This is followed by a series of fully-connected layers down to a single cell to predict the binary classification scores. During pretraining, we minimize ${\mathcal{L}}_{\text{NCE}}$ with a batch size of 256 and perform gradient updates using the Adam optimizer with learning rate $\lambda=10^{-4}$ until convergence.

-A3 Miscellaneous Hyperparameters

We provide the hyperparameters associated with our algorithms in Table IV.

-B Offline Trajectory Dataset

For the offline dataset discussed in Section IV-B, we use a combination of a 30 hours of autonomously collected data, and 12 hours of human teleoperated data. The complete dataset was collected by 3 independent sets of researchers over the course of 24 months in environments spanning multiple cities. We provide more information below.

We use the published dataset by Shah et al. , that contains over 5000 self-supervised trajectories collected over 9 distinct real-world environments. These trajectories capture the interaction of the robot in diverse environments, including phenomena like collisions with obstacles and walls, getting stuck in the mud or pits, or flipping due to bumpy terrain.

During data collection, a robot is equipped with a 2D LIDAR sensor to detect collisions ahead of time and generate autonomous pseudo-labels for collision events. To ensure that the control policy achieves sufficient coverage of the environment while also ensuring that the action sequences executed by the robot are realistic, we use a time-correlated random walk to gather data.

-B2 Human Teleoperated Data

The above dataset contains extremely diverse dataset that is great for learning general notions of traversability and collision avoidance. However, the random nature of the dataset means that it does not contain any semantically interesting behavior that may be desired of a robotic system, such as following a sidewalk or through a patch of trees. To enhance the quality of learned behaviors, we augment this dataset with about 12 hours of human teleoperated data in semantically rich environments such as hiking trails, city sidewalks, parking lots and suburban neighborhoods. These environments represent realistic scenarios where such a robotic system would be deployed.

Table V summarizes key statistics of the trajectories, such as length and velocity. Table VI summarizes the various environments in which the dataset was collected, and their relative composition. Figure 13 visualizes the geographic locations of these data collection sites (location anonymized for the double-blind review process). We ensure no overlap between the training and test environments—success in these test environments requires true generalization to unseen environments.

-C Project Page

We share experiment videos, including third-person perspectives of trajectories traversed by \algoName, on our project page: sites.google.com/view/viking-release.