Share Email Print

Proceedings Paper

Navigation Planning Using Quadtrees
Author(s): Ronald C. Fryxell
Format Member Price Non-Member Price
PDF $17.00 $21.00

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