Efficiency improvement in Monte Carlo localization through topological information

Monte Carlo localization is known to be one of the most reliable methods for pose estimation of a mobile robot. Many studies have been conducted to improve performance of MCL. Although MCL is capable of estimating the robot pose when the initial pose of a robot is not given, it takes much time for convergence because a large number of random samples are required, especially for the large-scale environment. For practical implementation of MCL, therefore, it is desirable to reduce the number of samples without affecting the localization performance. This paper presents a novel approach to reduce the number of samples used in the particle filter for efficient implementation of MCL. To this end, the topological information is extracted in real time through the thinning algorithm from the range data of a laser scanner. The topological map is first created from the given grid map of the environment. The robot scans the local environment and generates a local topological map. The robot then navigates along this local topological edge, which coincides with the global topological map obtained off-line from the given global grid map. By constraining the robot's motion on this local edge, random samples are drawn only around the neighborhood of the topological edge rather than over the entire free space. Hence the sample size required for MCL can be drastically reduced, thereby reducing computational time for the MCL process. A series of experiments based on this proposed MCL/TI show that the number of samples can be reduced considerably, and thus the time required for pose estimation can be substantially decreased.