Giorgio Grisetti, Luca Iocchi, Daniele Nardi
Dipartimento di Informatica e Sistemistica
University "La Sapienza" Roma, Italy
Global localization is the process of determining the pose of the robot in an environment without using any knowledge on an estimated position of the robot.
Gloabl localization is useful not only for kidnapped robots, but also in those situations in which position tracking is not effective.
Localization problem
Computing the probability distribution for the robot pose p( l | S ) l = (x y th)
Representation of probability distribution
- single Gaussian is used in EKF-based approaches for position tracking
(previuous work on Hough Localization)- explicit is used in Markov-based approaches for global localization
- multiple Gaussians are used for tracking multiple hypotheses in global localization
(present work on Global Hough Localization)
Position tracking => point corrispondences in the Hough space are easy to determine => O ( n )
Global localization => finding point correspondences in the Hough space is difficult and using a trivial extension of Hough method leads to high computational time.
Data association presented here is based on a property of the Hough Transform that allows for defining a method that has a worst-case complexity of O ( n + k^3 ) and average-case complexity of O ( n + k ).
GHL is based on the following property of the HT:
Given HTS and a translation/rotation of the robot, the HTS computed from the new pose of the robot is such that:
1. if the robot does not rotate then theta does not change
2. if the robot does not translate rho does not change.Robot alignment can be divided in two steps: first determine possible orientations with a null translation, then determine translations for each possible orientation.
This decomposition allows for low time complexity.
1. Compute HTS for all sensor data
2. Compute posible orientation corrections
3. For every orientation computed in step 2, compute possible translation corrections
4. From the set of pairs (orientation,translation), compute a set of Gaussians denoting possible poses
Different sets of hypotheses computed over time must be integrated.
In our current implementation:
- hypotheses that are confirmed over time increase a confidence factor
- hypotheses that are not confirmed over time decrease a confidence factor
- new hypotheses may be considered
- hypotheses with low confidence may be discarded
In this environment the robot was initially facing a corner without any on its initial position.
The first steps of the GHL have determined five possible poses (numbered 1 to 5 below)
During the navigation these hypothesis have been compared with new ones and when matching failed some of them (from 2 to 5) have been discarded.
After a while the hypothesis 1 was the only feasible for the sensor data acquired over time.
Video clip from GermanOpen 2002 (Paderborn, April 2002)
S.P.Q.R. - ISePorto
Advantages of the method
- low complexity O(|S|+|M|) ( < 100 ms )
- robust in dynamic environments (e.g. RoboCup)
- adequate for low accuracy range sensorsLimitations
- polygonal environment (map represented as a set of segments)
- possible lack of features (e.g. parallel lines)
