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.
If you have any questions or suggestions about these pages please drop me an email