Research: Landmark Based Navigation

Matthew Deans


Landmark based navigation is intended to greatly improve robot position estimation over dead reckoning by tracking visual features in the environment and using them as landmarks. This measurement returns bearing to the visual feature only. No a priori knowledge regarding the position of the landmarks assumed, so the problem is one of simultaneously mapping and localizing. This is analogous to being placed in an entirely unknown environment and using the existing environment to localize while building a model of the environment. As posed, this problem has even less a priori information than the "Drop-off" problem posed by Thompson, which assumes a known map and an unknown position.

Robot localization can be viewed as a partially observable Markov process where at each step, the robot has a location that is entirely described by the last position and the translation made since the last step. Furthermore, at each step, observations may be made about the environment that provide information regarding the current position. In general, neither the previous location nor the translation are well known, and the observations are noisy and insufficient to provide unambiguous pose.

Several Bayesian estimation techniques may be brought to bear on this problem. Under the assumptions of linear state transition, linear measurements, and Gaussian noise, Kalman filtering is provably optimal. Relaxing these assumptions leads to the Extended Kalman Filter (EKF) and the Extended Iterated Kalman Filter (EIKF). Recently, a method called Covariance Intersection (CI) has been suggested to compensate for unknown and unmodeled correlations in observation noise, which leads to an algorithm which is mathematically similar to the EKF and EIKF, but provides more conservative and more consistent estimates. This same group has developed the Unscented Filter, a method of nonlinear state propagation and measurement prediction that improves upon the linearizing assumptions in the EKF. Also, several researchers have suggested particle based approaches to state estimation and density representation, where state estimates are represented as a set of samples in state space, and conditional probabilities are computed using Importance Resampling. These techniques have had the names Condensation, Bootstrap Filter, and SIR filter, among others. The above methods are all designed to recursively estimate the map and robot position as information is  gathered. An alternative batch method is to iteratively compute the maximum likelihood map and trajectory given all of the available observations made during a traverse. I will call this method Iterative Maximum Likelihood (IML). In the context of Landmark Based Navigation, an EIKF, CI filter, Unscented/CI filter, particle filter, and IML algorithm have all been implemented.

The current hardware configuration for landmark based navigation consists of a Dalsa CA-D7 camera connected to a Bitflow Road Runner framegrabber on board a dual-Pentium PC mounted on Nomad, as well as wheel encoders and steering encoders on Nomad's chassis. The PC will be used to log images directly from the framegrabber, and to log NDDS messages containing telemetry while Nomad drives on the ice. Telemetry and images will be processed off-line to produce mapping/localization results. This off-line processing has several advantages over processing on-the-move, including:

Current State of Technology

Visual tracking software exists for processing a sequence of panoramic images and storing the bearing to each visual target in each frame over the sequence. Software also exists to process telemetry logs and extract steering encoder and wheel encoder values. These make up a pre-processing step that is the same for all mapping and localization methods. Several estimation methods have been implemented for processing odometry and visual measurements.  These include EKF, EIKF, CI filter, CI/Unscented Filter, Particle based Filter, and IML estimator.

Find out about the landmark based navigation experiment in the current Antarctic expedition.

Back to Research

Robotic Search for Antarctic Meteorites 1998
All material on this page is property of NASA and Carnegie Mellon University. Any image or text
taken from this site and incorporated into another document without consent violates the Copyright
Law of the United States and the Berne International Copyright Agreement.
Send comments, questions, or suggestions to Dimitrios Apostolopoulos.
This document prepared by Michael Wagner.