Complementary regions: a surface filling algorithm

This paper presents the concept of 'complementary regions'. It is the basis of our surface filling navigation strategy. It also allows to: obtain a compact topological graph representation of the environment, solve the 'terrain acquisition' problem, and plan point to point trajectories. This space decomposition concept is general and can be adapted to other robotics problems. The algorithm for a 2D surface region filling operation is introduced. It has been successfully tested using an autonomous mobile robot. Its correctness and applicability are demonstrated by its capability of exploring and navigating the entire accessible area of an a priori unknown indoor environment. A high level of performance has been reached.