GLOBAL LOCALIZATION

What is a Global Localization?

Global Localization is the estimation of a mobile robot's location in a given environment map, using sensor data. The robot is not aware of its initial position and has to determine it autonomously. Our framework is based on Monte-Carlo localization and Markov localization, the passive probabilistic approaches to localization. In Monte-Carlo localization, the robot tries to localize itself standing at a fixed position, with the help of sensor data. In Markov Localization, the robot maintains a probability density (belief) over the entire configuration space of the robot. However, there is no provision of controlling mobile actuators. In the active approach, the robot actively interacts with the environment and chooses the most optimal action which minimizes the expected future uncertainty.

What is Monte-Carlo Localization?

In Monte Carlo the belief is approximated by a set of samples (or particles) drawn from the space.
There is no initial knowledge (global localization). The system state is initialized by a uniform distribution over the state space. There are two procedures that can be applied to the belief - perceptual data updates for example sensor readings from a sonar module, camera or laser range finder, and motion updates that give information about the robot's movement. Using these we update the belief of the particles. Eventually, the belief converges to set of high-probability points in the space.
 

What is Markov Localization?

The Markov localization approach, divides the state space into regular cells and assigns each cell a value for the belief. In this way, a piecewise constant representation of the belief is established. A great advantage of this method is that every probability distribution can be modeled using just this, and that it is capable of global localization. But the computational complexity along with the need for a huge amount of memory is the drawback of this approach.

Project Outline

In our project, we have designed a tool that uses Monte-Carlo and Markov localization for 2D and 3D (with orientation of robot). We are working for passive as well as active localization. We have come up with a new technique for computing the desired action that breaks symmetries and localizes faster, compared to previous entropy minimization and maximum information gain.

The following figures show the results:

The red dots indicate the grid probabilities. Initially when there is no sensor data yet all grids have equal probabilities.

Based on the first sensor reading the grid probabilities are calculated and the position of the robot is estimated which is indicated by the green dot. With subsequent readings the position of the robot is calculated accurately. Here the robot is in a state of multiple hypotheses of its position shown by the red grids. Over time the red grids don't appear at several places as the robot finds the best direction to move and moves along that direction.

The robot continues to move along the direction which will result in a unique or singular hypothesis of its state

                        The position of the robot has now been estimated accurately.

Send mail to akpandey@research.iiit.ac.in with questions or comments about this web site.
Copyright © 2006 IIIT Robotics Research Lab
Last modified: 07/27/06