Construction of optimal-path maps for homogeneous-cost-region path-planning problems.
Alexander, Robert S.
Rowe, Neil C.
MetadataShow full item record
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 in cross-country two-dimensional terrain for a moving agent of negligible size. Such maps allow fast point-location algorithms at run-time to categorize die start point according to the behavior of the optimal path to the goal, from which the path can be reconstructed. We study terrain modelled by piecewise-linear roads and rivers, polygonal obstacles, and by convex polygonal homogeneous-cost areas ("weighted regions"). We explore two methods for constructing optimal-path maps, one based on wavefront-propagation point-to-point path planning, and a more exact divide-and-conquer algorithm that reasons about how optimal paths must behave. In the exact approach, boundaries caused by terrain features are characterized using analytical geometry and optimal-path principles, and partial optimal-path maps are merged into complete ones.
Approved for public release; distribution is unlimited.
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 ...
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 ...