Sage Journals: Discover world-class research

Abstract

We present an efficient algorithm for finding least-cost paths for an agent of negligible size across an important special case of two-dimensional terrain, terrain consisting of (1) a single isotropic homogeneous-cost-per-distance background region, (2) "roads" or narrow transportation corridors of low cost per distance, (3) "rivers" or narrow features of high crossing cost, and (4) untraversable "obstacles. " This work extends that of Mitchell (1987) by including rivers and new pruning heuristics for roads; our algorithm remains O(n² log n) in time complexity. We also show results of a first com puter implementation for this class of algorithms and analyze average-case performance and error sensitivity. This work applies primarily to high-level path planning for robots but also can help plan military maneuvers and guide construction of roads and pipelines.

Get full access to this article

View all access options for this article.

References

Alexander, R. 1989. Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. Thesis. Department of Computer Science, U.S. Naval Postgraduate School.

de Champeaux, B. , and Sint, L. 1977. An improved bi-directional heuristic search algorithm . J. ACM 24:1777-1791.

Chavez, R. , and Meystel, A. 1984 (Atlanta) Structure of intelligence for an autonomous vehicle. IEEE International Conference on Robotics and Automation. New York: IEEE, pp. 584-591.

Gewali, L. , Meng, A. , Mitchell, J. , and Ntafos, S. 1988 (Urbana, Ill., June). Path planning in 0/1/infinity weighted regions with applications. Proceedings of the Fourth Annual ACM Symposium on Computational Geometry. New York: ACM, pp. 266-278.

Lozano-Pérez, T. , and Wesley, M.A. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Comm. ACM 22(10):560-570.

Mitchell, J.S.B. 1987 (New Orleans, La., May). Shortest paths among obstacles, zero-cost regions, and roads. Paper delivered at the Joint National Meeting of TIMS/ORSA.

Mitchell, J.S.B. 1988. An algorithmic approach to some problems in terrain navigation . Art. Intell. 37:171-201.

Mitchell, J.S.B. , and Keirsey, D. 1984. Planning strategic paths through variable-terrain data . SPIE Conference on Applications of Artificial Intelligence, Vol. 485. New York: SPIE, pp. 172-179.

Richbourg, R. , Rowe, N. , Zyda, M. , and McGhee, R. 1987 ( Raleigh, N.C. , March). Solving global two-dimensional routing problems using Snell's Law and A* search. Proceedings of the IEEE International Conference on Robotics and Automation . New York: IEEE, pp. 1631-1636.

10.

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

Roads,Rivers,and Obstacles: Optimal Two-Dimensional Path Planning around Linear Features for a Mobile Agent

Abstract

Get full access to this article

References