Simply put, the problem for robots, when on a mission or task, is to be able to estimate their position and orientation using visual landmarks and internal maps. This is the same problem that people face, for example, when competing in the sport of orienteering. Conventional landmark navigation fixes the position of the competitor, with respect to known landmarks at the intersection of several position surfaces. For mobile robots, the idea is to implement, as a supporting technology, the ability to estimate their position using visual landmarks. In an ideal situation, the robot would stop, look around, take in all the features of the landscape, and then calculate its position.
There are three basic techniques for finding one's location: measurement of two bearings, measurement of one bearing and one distance, and measurement of two distances. The first technique, measurement of two bearings is the most attractive because it avoids the challenges of measuring depth or range, and it capitalizes on the relatively high angular resolution of standard cameras and lenses used in the robots.
The two-bearing problem formalizes as follows:
Let (x, y) represent the location of the robot in a fixed, external reference frame W. Let p1, . . . , pn be points representing locations in W of the map landmark points. Let r1, . . . , rk be the rays emanating from (x, y) to the landmarks. A ray represents the direction in which a landmark feature is observed, but does not entail distance information.
The problem: given a set of n landmark points and k rays, find all of the poses Q such that each ray pierces at least one landmark point.
An algorithm that searches for pairings of rays and points solves this problem. The minimum number of pairings for a unique solution to exist is three. First, the search considers only cases of three rays to determine candidate solutions, then, additional rays are used to verify the candidates. The computational complexity of the algorithm is 0 (n^3).
This algorithm has been extended by introducing probability distributions on the rays and landmark points. In this statistical approach, inferences about position are obtained by maximization of the posterior distributionÑthat is, the probability of all possible explanations of what the robot has measured-for (x, y).
The introduction of probabilities allows the modeling and accommodation of various sources of noise and disturbances (noise and disturbances can be anything that results in error for the robot when estimating its position) but it also introduces some difficulties. Essentially, the posterior distribution of (x, y) involves a summation over all possible pairings of rays and landmarks. This implies an exponential effort in the determination of best pose-that is, the pose that provides the most probable position for the robot. This complexity is addressed by use of statistical tools, particularly significance tests. In this framework, not all rays are analyzed against all landmarks-positions that are highly unlikely will be regarded as impossible. On the other hand, by introducing probability distributions, positions that are likely will be calculated. The resulting technique offers a sensible statistical version of the original localization algorithm while keeping the polynomial complexity.
The table below illustrates typical results from the position estimation algorithm using simulated landmarks and simulated rays. In this dataset the algorithm found four candidates (listed in the table below). The likelihood for the correct pose* is a hundred times larger than the others, demonstrating the efficacy of the method.
x y likelihood
3.8 1.5 0.04
2.1 2.7 0.04
4.0 6.2 0.03
3.0 3.0 4.63 *
Likelihood computed for candidate poses
Point of Contact:
Eric Krotkov
Carnegie Mellon University
Pittsburgh, PA 15213
412-268-1970
epk@cs.cmu.edu
Telerobotics Program
page
Please email the site webmaster
with any comments, criticisms or corrections
for this page.
Maintained by: Dave Lavery
Last updated: May 10, 1996