Path Planning by Optimal-Path-Map Construction for Homogeneous-Cost Two-Dimensional Regions
Loading...
Authors
Alexander, Robert S.
Rowe, Neil C.
Subjects
Advisors
Date of Issue
1990-05
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
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.
Type
Conference Paper
Description
This paper appeared in the Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati OH, May 1990,
1924-1929.
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.