Obtaining Optimal Mobile-Robot Paths with Non-Smooth Anisotropic Cost Functions Using Qualitative-State Reasoning
Loading...
Authors
Rowe, Neil C.
Subjects
Advisors
Date of Issue
1997-06
Date
June 1997
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Realistic path-planning problems frequently show anisotropism, dependency of traversal cost or feasibility on the traversal heading. Gravity, friction,
visibility, and safety are often anisotropic for mobile robots. Anisotropism often differs qualitatively with heading, as when a vehicle has insufficient power to
go uphill or must brake to avoid accelerating downhill. Modeling qualitative distinctions requires discontinuities in either the cost-per-traversal-distance
function or its derivatives, preventing direct application of most results of the calculus of variations. We present a new approach to optimal anisotropic path
planning that first identifies qualitative states and permissible transitions between them. If the qualitative states are chosen appropriately, our approach
replaces an optimization problem with such discontinuities by a set of subproblems without discontinuities, subproblems for which optimization is likely to be
faster and less troublesome. Then the state space in the near neighborhood of any particular state can be partitioned into "behavioral regions" representing
states optimally reachable by single qualitative "behaviors", sequences of qualitative states in a finite-state diagram. Simplification of inequalities and other
methods can find the behavioral regions. Our ideas solve problems not easily solvable any other way, especially those with what we define as "turn-hostile"
anisotropism. We illustrate our methods on two examples, navigation on an arbitrarily curved surface with gravity and friction effects (for which we show
much better performance than a previously-published program 22 times longer), and flight of a simple missile.
Type
Conference Paper
Description
This paper appeared in the
International Journal of Robotics Research, 16, 3 (June 1997), 375-399. The equations were reconstructed in 2007 for better readability.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
This work was supported in part by the U.S. Army Combat Developments Experimentation Center under MIPR ATEC 88-86. This work was also prepared in part in conjunction with research conducted for the Naval Air Systems Command
Funder
funded by the Naval Postgraduate School
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.