Share Email Print

Proceedings Paper

Navigation Planning Using Quadtrees
Author(s): Ronald C. Fryxell
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 1 January 1987
PDF: 8 pages
Proc. SPIE 0852, Mobile Robots II, (1 January 1987); doi: 10.1117/12.968255
Show Author Affiliations
Ronald C. Fryxell, Albion College (United States)

Published in SPIE Proceedings Vol. 0852:
Mobile Robots II
Wendell H. Chun; William J. Wolfe, Editor(s)

© SPIE. Terms of Use
Back to Top