Maintaining multi-level planar maps in intelligent systems

Abstract

We present algorithms that allow an intelligent system to dynamically convert between two representations of spatial occupancy, namely, certainty grids and object boundary curves. These algorithms can be used to accomplish many real-time tasks of a mobile robot such as mapping, navigation, object recognition, and robot localization. For conversion from certainty grid to object boundaries, an edge linking algorithm is appropriately modified. Certainty grid 'images' are transformed into a set of object boundary curves. The latter are expressed as oriented piecewise linear segments. Image processing techniques, such as edge detection, thinning, curve tracing, and linear approximation are employed with various modifications. Modifications include a new method for linear curve approximation that is simple, accurate, and efficient. This method monitors chord and arc length and its excellent performance is demonstrated against similar algorithms. The certainty grid to object boundary algorithm is tested against simulated noisy certainty grid maps. An algorithm to do the inverse operation, namely, to convert object boundary curves to an occupancy grid, is also presented.