Obtaining Optimal Mobile-Robot Paths with Non-Smooth Anisotropic Cost Functions Using Qualitative-State Reasoning
Rowe, Neil C.
MetadataShow full item record
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.
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.
Showing items related by title, author, creator and subject.
Rowe, Neil C.; Kanayama, Yutaka (Monterey, California. Naval Postgraduate School, 1994-10);We determine near-optimal paths with respect to work against friction and gravity on the surface of a vertical-axis ideal cone, assuming a moving agent of negligible size, friction proportional to the normal force, and ...
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 ...
Cool, Thomas C. (1987-06);The Stylist is a Waterloo Pascal program that analyzes the style of English prose. A "style checker", The Stylist pertains to Computational Stylistics and Computer Assisted Composition Instruction (CACI). The Stylist ...