Exact cell decomposition of arrangements used for path planning in robotics

Abstract

We present a practical algorithm for the automatic generation of a map that describes the operation environment of an indoor mobile service robot. The input is a CAD description of a building consisting of line segments that represent the walls. The algorithm is based on the exact cell decomposition obtained when these segments are extended to infinite lines, resulting in a line arrangement. The cells are represented by nodes in a connectivity graph. The map consists of the connectivity graph and additional environmental information that is calculated for each cell. The method takes into account both the path planning and position verification requirements of the robot and has been implemented. 1 Introduction In the field of robotics, one of the main problems is robot motion planning. We consider the case of a car-like robot doing routine service operations, such as mail delivery, in an office building. The emphasis is on providing the robot and its programmer with a practical and rob...