Geometric constraint identification and mapping for mobile robots

A new method of map building for mobile robots is presented. Recent developments have focused on grid-based mapping methods which suffer from the drawback of their size, requiring a great deal of memory and prohibiting the use of many path-planning algorithms. In contrast, geometric maps provide a compact alternative which facilitates path-planning. We propose a new method which identifies geometric models of the constraints imposed upon the robot by the environment. A rigorous approach is taken to the process of constraint identification, which is cast as a minimisation problem. A number of primitive geometric objects are used for constraint modelling including line segments, are segments, cubic segments and, for three degree of freedom systems, polygonal planar patches. A number of operations are also defined which integrate new sensor readings into the existing model. Simulation results are presented fur two and three degree of freedom systems, demonstrating the effectiveness of the constraint identification process. A comparative study is also presented which gives guidelines for the proper selection of primitives and operations. (C) 2001 Elsevier Science B.V. All rights reserved.