Complementary regions: a surface filling algorithm

Abstract

This paper presents the concept of "complementary regions". It is the basis of our surface filling navigation strategy. It allows a mobile robot 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. Correctness and applicability are demonstrated 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.