Path Planning by Optimal-Path-Map Construction for Homogeneous-Cost Two-Dimensional Regions
Alexander, Robert S.
Rowe, Neil C.
MetadataShow full item record
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 search. Hence developers of real-time robots have usually not attempted to plan optimal paths. We propose a new way to ensure optimality by a thorough preprocessing analysis of the terrain before the robot is sent out. Our approach builds "optimal-path maps" for regions of near-homogeneous traversal characteristics in the terrain, maps that assign a behavioral description, of the best way to reach a fixed goal point, to every point in that region; the behavioral description is simple enough that the optimal direction at any point can be quickly calculated in real time. Then a robot need only determine where it is periodically, and look up this position in the optimal-path map. This paper provides algorithms to construct optimal-path maps for all single isolated homogeneous-cost polygonal regions, a major subproblem of the general problem of constructing optimal-path maps. We do a complete analysis of the four possible situations, and then provide algorithms to construct behavioral regions within the homogeneous-cost regions, once optimal paths have been found for a particular set of starting points, in @O ( n sup 4 )@ time using @O ( n )@ space, where @n@ is the number of vertices in a polygonal model of the terrain as homogeneous-cost regions. Our algorithm greatly simplifies planning of paths through areas of terrain with near-uniform characteristics, allowing a robot to exploit optimal paths but still have significant time for other matters.
This paper appeared in the Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati OH, May 1990, 1924-1929.
Showing items related by title, author, creator and subject.
Rowe, Neil C.; Alexander, Robert S. (Monterey, California. Naval Postgraduate School, 2008);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 ...
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 ...
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 ...