Quadtree decomposition of configuration space for robot motion planning

Abstract

This paper presents a method to solve the general problem of path planning in the field of robotics. For autonomous mobile robots the configuration space is given by an occupancy matrix represented by a bitmap. Quadtree decomposition is used to decompose the configuration space in order to achieve a representation, which needs less memory than the original representation with a bitmap. A connectivity graph is generated from the decomposed configuration space using neighbour finding techniques. A final graph search yields a feasible path, e.g. a shortest path. Due to smaller data structures the search of the free space of the configuration space for a feasible path can be done much faster. The presented algorithms are implemented using C++. The results of simulations for typical environments together with execution times are presented.