| Sign In to gain access to subscriptions and/or personal tools. |
Finding Optimal-Path Maps for Path Planning across Weighted RegionsComputer Science Department, Code CS/Rp, U.S. Naval Postgraduate School, Monterey, California 93943 USArowe{at}cs.nps.navy.mil
Computer Science Department, Code CS/Rp, U.S. Naval Postgraduate School, Monterey, California 93943 USA 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. The authors address the construction of optimal-path maps for two-dimensional polygonal weighted-region terrain, terrain partitioned into polygonal areas such that the cost per unit of distance traveled is homogeneous and isotropic within each area. This is useful for overland route planning across varied ground surfaces and vegetation. The authors 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 path finding. The algorithm used is more complicated than the current path-caching and wavefront-propagation algorithms, but it gives more accurate maps requiring less space to represent. Experiments with an implementation confirm the practicality of the authors’ algorithm.
Key Words: paths • planning • optimality • weighted regions • maps • Snell’s law
The International Journal of Robotics Research, Vol. 19, No. 2,
83-95 (2000) This article has been cited by other articles:
|
|||||||||||||||
 |
|
|
 |
|
Sign In to gain access to subscriptions and/or personal tools.
