Rossum -> Papers and RFC's -> Localization and Exploration

The algorithm determines the robotís position by correlating a local map (generated by a range sensor sweep), with a global map. While the global map can be supplied in advance, this algorithm does not require prior knowledge of the robotís environment. Instead, it uses sensor data to construct the global map dynamically.

The algorithm estimates the robotís location by comparing the global and local maps. To do so, it computes positions called feasible poses, where the expected view of the robot approximately matches the observed range sensor data. It then selects a best fit from the feasible poses.

To evaluate feasible poses efficiently, the algorithm represents the global map as an occupancy grid (a matrix of cells, each having a value that indicates whether that cell is empty or occupied). Using its sensors, the robot determines range vectors (distance and bearing from detected objects or features) which are then compared against all occupied cells in the grid. If a range vector can be overlaid on the grid without interference by other occupied cells, it indicates a feasible pose. In addition to its occupancy value, each cell in the grid is also assigned a certainty value indicating the likelihood that the robot is located at that position. Each time a feasible pose is identified, the certainty value of the corresponding cell is incremented. After all feasible poses are considered, the grid cell with the highest certainty value is selected as the robotís present position.

Ensuring that the algorithm identifies feasible poses requires information about the robot's orientation. Orientation can be measured from a digital compass, a gyro or even calculated from odometry data. While systems for measuring orientation are often prone to error, the algorithm is quite robust and can tolerate considerable inaccuracy. The algorithm can also be extended to provide corrections for measured orientation.

To create a useful local map, the algorithm requires range measurements in a number of different directions. Such measurements are readily obtained by sweeping the sensor. The robot used in this project features a sonar sensor that is mounted on a servo, so a 180-degree sweep is possible.

This algorithm is inspired from the paper 'Mobile Robot Self-Localization without Explicit Landmarks' by R.G.Brown and B.R.Donald. More information on the positioning software can be found from the paper 'Robot Localization and Map Construction Using Sonar Data'.

If you have any questions or suggestions about these pages please drop me an email
Copyright Vassilis Varveropoulos
Last updated 20 Apr 2001