Proceedings PaperNavigation Planning Using Quadtrees
|Format||Member Price||Non-Member Price|
|GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free.||Check Access|
An algorithm is presented for planning a 2-D collision-free path 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.