ERCIM News No.42 - July 2000 [contents]

Map Building and Robot Localization

by Patrick Rives and Alessandro Corrêa-Victorino

Safety navigation and reliable localization are two elementary functions absolutely necessary to operate autonomous vehicles in unknown environment. In many applications of mobile robotics, the localization can be carried out by integrating the odometry data but it is not very reliable because of the wheels slipping and the uncertainties about the mechanical structure of the robot. It is then interesting to be able to compensate this drift while being readjusted with respect to the environment.

In the ICARE research team at INRIA, we are dealing with techniques which allows us to locate the robot and to build a map of the environment simultaneously. The difficulty of the problem lies on the fact that a reliable localization depends on the quality of the map building process carried out from the elements of the environment previously observed and which remain visible at current time. On the other hand, more the accuracy on the localization will be large, more the map building step will be reliable. A trade-off is thus to be made between the function of exploration (ie discover the maximum of unknown elements of environment) and the function of localization (ie keep the maximum of known landmarks during the motion). It will be the role of the strategy of perception.

The Robot Anis

In the ICARE research team, we developped an approach based on the fusion of 2-D Laser Range Finder data and odometry data for the mapping and the localization of a mobile robot moving in a structured but unknown environment. We showed that the robustness of these tasks can be notably increased when the robot is constrained to move on certain trajectories during its exploration. These trajectories must have some properties such as:

The Voronoi Diagram satisfies such requirements and, moreover, can be incrementally built from the laser data in a straightforward manner. With a sensor based control technique using the laser data as feedback, we are able to constrain the robot to move along the Voronoi Diagram. Thanks to the closed loop control, we ensure a bounded error during the robot displacement.

The localization of the robot is obtained by the fusion between the range sensor readings and the odometry data, using an Extended Kalman Filter in order to cope with the occasional and systematic uncertainties of the observations and getting an optimal state estimate of the robot. A map of the environment is incrementally built and updated using both the laser scans and the Voronoi Diagram constraints (see Figure 2).

This approach has been validated with the Robot ANIS (see Figure 1) developped in the ICARE research team at INRIA-Sophia Antipolis. This robot is instrumented with a 2D-Laser Ranging Finder which provides 2000 points of readings at 80ms rate, thanks to the microelectronics developed in our Laboratory.

ICARE research team:

Please contact:
Patrick Rives - INRIA Sophia Antipolis
Tel: +33 4 92 38 77 52