## Mapping and Localization

### The Mobile Robot Location Problem

Monte Carlo sampling of probability distributions: Make the computer play roulette. |

The method is called after the city in the Monaco principality, because of a roulette wheel, a simple random number generator. The name and the systematic development of Monte Carlo methods dates from about 1944, and the name implies that the computer randomly draws from a probability density function in a non-biased manner. A Markov chain is a series where the next element in the series, Y, is dependent only on the current state, X, and occurs with probability, P(Y|X). So the even number series (2, 4, 6, 8...) forms a Markov chain but the Fibonacci sequence (1, 1, 2, 3, 5, 8...) does not. Markov Chain Monte Carlo (MCMC) is a technique for sampling from space that might be difficult to sample. The elements might be a numerical result from Monte Carlo sampling within a multivariate system, which cannot be sampled directly, but are generated from other sampled variables. |

The robot localization problem can be divided into two sub-tasks: global position estimation and local position tracking. Global position estimation is the ability to determine the robot's position in an a priori or previously learned map, given no information other than that the robot is somewhere in the region represented by the map. Once a robot’s position has been found in the map, local tracking is the problem of keeping track of that position over time. While existing approaches to position tracking are able to estimate a robot's position efficiently and accurately, they typically fail to globally localize a robot from scratch or to recover from localization failure. Global localization methods are less accurate and often require substantially more computational power. Within SRI’s algorithm, the representation of the robot's state space is based on Monte Carlo sampling. Introduced in 1970, Monte Carlo (see inset) methods have more recently been applied in the fields of target tracking, computer vision, and robot localization, with good results. The Monte Carlo technique inherits the benefits of previously introduced Markovian probability grid approaches for position estimation, and provides an extremely efficient technique for mobile robot localization.