Near-Minimum-Energy Paths on a Vertical-Axis Cone With Anisotropic Friction and Gravity Effects

Abstract

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 propor tional to the normal force, and power-maximum and stability limitations on the agent. This can provide good paths across hilly terrain for mobile robots. Our previous work required difficult-to-obtain polyhedral terrain models; cone surface patches permit easier and better models. We prove that our near-optimal paths on a vertical-axis cone surface are not much more complex than on polyhedra: There are qualitatively 22 kinds of path behavior (as opposed to four on a polyhedral face), and the area of the surface optimally reachable from a fixed start point by a given qualitative behavior has mathemat ically simple boundaries (only line segments, circle arcs, and arcs of logarithmic spirals in azimuth projection). We examine the possible cases based on agent characteristics and cone steepness and provide "behavior maps" for quickly finding near-optimal paths between any two points on the cone surface. Our models incorporate discontinuous effects with respect to traversal heading. Comparisons with a program using uniform- grid path planning show our methods run considerably, faster in less space, and our paths are much simpler to describe and easier to follow in the real world.

Get full access to this article

View all access options for this article.

References

Alexander, R.S. , and Rowe, N.C. 1990 (May). Path planning by optimal-path-map construction for homogeneous-cost two-dimensional regions. Proc. IEEE International Conference on Robotics and Automation, Cincinnati, OH, pp. 1924-1929.

Bekker, M.S. 1969. Introduction to Terrain-Vehicle Systems. Ann Arbor, MI: University of Michigan Press . Brooks, R.A. 1983. Solving the find-path problem by good representation of free space. IEEE Trans. Sys. Man Cybernet. SMC-13(3):190-197.

Forbus, K. 1988. Qualitative physics: Past, present, and future . In Shrobe, H. (ed.): Exploring Artificial Intelligence. San Mateo, CA: Morgan Kaufmann, pp. 239-296.

Gaw, D. , and Meystel, A. 1986 (April). Minimum-time navigation of an unmanned mobile robot in a 2-1/2D world with obstacles. Proc. IEEE International Conference on Robotics and Automation, pp. 1670-1677.

Kuipers, B. 1986. Qualitative simulation. Artificial Intell. 29:289-388.

McGhee, R. , and Iswandhi, G. 1979. Adaptive locomotion of a multilegged robot over rough terrain. IEEE Trans. Sys. Man Cybernet. SMC-9(4):176-182.

Mitchell, J.S.B. , and Keirsey, D. 1984. Planning Strategic Paths Through Variable Terrain Data. Applications of Artificial Intelligence. Vol. 485. New York: SPIE, pp. 172-179.

Mitchell, J.S.B. , Mount, D.M. , and Papadimitriou, C.H. 1987. The discrete geodesic problem . SIAM J. Computing 16(4):647-668.

Mitchell, J.S.B. , and Papadimitriou, C.H. 1991. The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. Assoc. Computing Machinery 38(1):18-73.

10.

Papadakis, N.A. , and Perakis, A.N. 1990. Deterministic minimal time vessel routing. Operations Res. 38(3):426-438.

11.

Parodi, A.M. 1985. Multi-goal real-time global path planning for an autonomous land vehicle using a highspeed graph search processor. Proc. IEEE International Conference on Robotics and Automation . New York: IEEE, pp. 161-167.

12.

Pavlidis, T. 1982. Graphics and Image Processing. Rockville, MD: Computer Science Press.

13.

Rowe, N.C. 1992 (September). Obtaining optimal mobile-robot paths with non-smooth anisotropic cost functions using qualitative-state reasoning . Technical report NPS-CS-012. Computer Science Department, U.S. Naval Postgraduate School, Monterey, CA.

14.

Rowe, N.C. , and Kanayama, Y. 1992 (September). Near-minimum-energy paths on a vertical-axis cone with anisotropic friction and gravity effects: The details. Technical report NPS-CS-013. Computer Science Department, U.S. Naval Postgraduate School, Monterey, CA.

15.

Rowe, N.C. , and Richbourg, R.F. 1990. An efficient Snell's-law method for optimal-path planning across multiple homogeneous-cost regions. Int. J. Robot. Res. 9(6): 48-66.

16.

Rowe, N.C. , and Ross, R.S. 1990. Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects. IEEE Trans. Robot. Automation 6(5):540-553.

17.

Rula, A.A. , and Nuttall, C.J. 1971 (July). An analysis of ground mobility models (ANAMOB) . Technical report M-71-4. U.S. Army Corps of Engineers, Waterways Experiment Station, Vicksburg, MS.

18.

Sharir, M. , and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Computing 15(1):193-215.

19.

Turnage, G.W. , and Smith, J.L. 1983 (September). Adaptation and condensation of Army Mobility Model for cross-country mobility mapping. Technical report GL-83-12. U.S. Army Corps of Engineers, Waterways Experiment Station , Vicksburg, MS.