Finding Optimal-Path Maps for Path Planning Across Weighted Regions
Loading...
Authors
Rowe, Neil C.
Alexander, Robert S.
Subjects
Advisors
Date of Issue
2000-02
Date
February 2000
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Optimal-path maps tell robots or people the best way to reach a goal point from anywhere in a known terrain area,
eliminating most of the need to plan during travel. We address the construction of optimal-path maps for twodimensional
polygonal weighted-region terrain, terrain partitioned into polygonal areas such that the cost per unit
distance traveled is homogeneous and isotropic within each polygon. This is useful for overland route planning across
varied ground surfaces and vegetation. We propose a new algorithm that recursively partitions terrain into regions of
similar optimal-path behavior, and defines corresponding "path subspaces" for these regions. This process constructs
a piecewise-smooth function of terrain position whose gradient direction is everywhere the optimal-path direction,
permitting quick finding of optimal paths. Our algorithm is more complicated than the current path-caching and
wavefront-propagation algorithms, but gives more accurate maps requiring less space to represent. Experiments with
an implementation confirm the practicality of our algorithm.
Type
Conference Paper
Description
This paper appeared in the International Journal of Robotics Research, 19, 2 (February 2000), pp. 83-95, with
elaborating additions from [Rowe and Alexander, 1997]. The equations were redone for greatly improved clarity in
2008.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
This work was supported in part by the U.S. Army Combat Developments Experimentation Center under MIPR ATEC 88-86. This work was also prepared in part in conjunction with research conducted for the Naval Air Systems Command and funded by the Naval Postgraduate School.
supported in part by the U.S. Army Combat Developments Experimentation Center under MIPR ATEC 88-86. This work was also prepared in part in conjunction with research conducted for the Naval Air Systems Command and funded by the Naval Postgraduate School.
supported in part by the U.S. Army Combat Developments Experimentation Center under MIPR ATEC 88-86. This work was also prepared in part in conjunction with research conducted for the Naval Air Systems Command and funded by the Naval Postgraduate School.
Funding
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.