Share Email Print

Proceedings Paper

Updating Distance Maps When Objects Move
Author(s): Terrance E. Boult
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

Using a discrete distance transform one can quickly build a map of the distance from a goal to every point in a digital map. Using this map, one can easily solve the shortest path problem from any point by simply following the gradient of the distance map. This technique can be used in any number of dimensions and can incorporate obstacles of arbitrary shape (represented in the digital map) including pseudo-obstacles caused by unattainable configurations of a robotic system. This paper further extends the usefulness of the digital distance transform technique by providing an efficient means for dealing with objects which undergo motion. In particular, an algorithm is presented that allows one to update only those portions of the distance map that will potentially change as an object moves. The technique is based on an analysis of the distance transform as a problem in wave propagation. The regions that must be checked for possible update when an object moves are those that are in its "shadow", or in the shadow of objects that are partially in the shadow of the moving object. The technique can handle multiple goals, and multiple objects moving and interacting in an arbitrary fashion.

Paper Details

Date Published: 1 January 1987
PDF: 8 pages
Proc. SPIE 0852, Mobile Robots II, (1 January 1987); doi: 10.1117/12.968252
Show Author Affiliations
Terrance E. Boult, Columbia University (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