Finding Optimal-Path Maps for Path Planning Across Weighted Regions
Rowe, Neil C.
Alexander, Robert S.
MetadataShow full item record
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.
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.
Showing items related by title, author, creator and subject.
Alexander, Robert S.; Rowe, Neil C. (Monterey, California. Naval Postgraduate School, 1990-05);Finding optimal paths for autonomous robots can significantly reduce travel or energy costs or the probability of accident compared to other "reasonable" paths. But finding optimal paths requires a thorough and systematic ...
Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects Rowe, Neil C.; Ross, Ron S. (Monterey, California. Naval Postgraduate School, 1990-10);Anisotropic (heading-dependent) phenomena arise in the "two-and-one-half-dimensional" path-planning problem of finding minimum-energy routes for a mobile agent across some hilly terrain. We address anisotropic friction and ...
Alexander, Robert S. (Monterey, California. Naval Postgraduate School, 1989-09);Fast path-planning algorithms are needed for autonomous vehicles and tactical terrain-analysis tools. We explore a new approach using "optimal-path maps", that give the best path to a goal point from any given start point ...