Navigation Planning Using Quadtrees

Abstract

An algorithm is presented for planning a 2-D collision-free for a mobile robot in an unstructured work environment. The algorithm assumes the existence of a pixel map of all or part of the environment, where each pixel is either on (implying blocked) or off (implying clear). The goal is to compute a reasonable path between two points in a minimal amount of time, and this is achieved through a compressed representation of the pixel map using a modified quadtree data structure and a procedure for smoothing the resulting path. The algorithm has been coded in the C programming language to facilitate portability, and the results of tests made on realistic indoor environments are presented. A discussion on how the environmental maps were obtained is also included.