Planning Shortest Paths among 2D and 3D Weighted Regions Using Framed-Subspaces

Abstract

The standard shortest path planning problem determines a collision- free path of shortest distance between two distinct locations in an environment scattered with obstacles. This problem, in fact, corre sponds to a special case of the weighted region problem, in which the environment is partitioned into a set of regions, with some regions (obstacles) having an associated weight of oo and other regions (free space) having a weight of 1. For the general weighted region problem, the environment consists of regions, each of which is as sociated with a certain weight factor. A path through the weighted region incurs a cost that is determined by the geometric distance of the path in that region times that region's weight factor. The weighted region problem can be used to model path planning for autonomous vehicles over different environmental terrains. This paper studies the problem of computing a shortest path between two distinct locations through a 2D or 3D environment consisting of weighted regions. The authors propose a novel cell decomposi tion approach based on new framed-subspace data structures: the weighted framed-quadtree and the weighted framed-octree.

Get full access to this article

View all access options for this article.

References

Barraquand, J. , Langlois, B. , and Latombe, J. 1992. Numerical potential field techniques for robot path planning . IEEE Trans. Sys. Man Cybernetics 22(2):224-241.

Borgefors, G. 1984. Distance transformations in arbitrary dimensions . Computer Vision, Graphics, and Image Processing 27:321-345.

Brooks, R. 1983. Solving the find-path problem by good representation of free space. IEEE Trans. Sys. Man Cybernetics 13(3):190-197.

Celenk, M. , and Bohora, A. 1989. Visual robot guidance in dynamic environment using quadtree data structure and parallel processing. Proc. SPIE—The International Society for Optical Engineering, pp. 435-446.

Chan, R.H.T. , Tam, P.K.S. , and Leung, D.N.K. 1991. Robot navigation in unknown terrains via multi-resolution grid maps. Int. Conf. Industrial Electronics, Control and Instrumentation, pp. 1138-1143.

Chen, D.Z. , Klenk, K.S. , and Tu, H. T.1995 (June). Shortest path queries among weighted obstacles in the rectilinear plane. Eleventh Annual ACM Symp. Computational Geometry.

Chen, D.Z. , Szczerba, R.J. , and Uhran, J. J. Jr. 1995 (October, Vancouver). Determining conditional shortest paths in an unknown, three-dimensional environment using framed-octrees. IEEE Int. Conf. Systems, Man and Cybernetics (SMC '95), vol. 5, pp. 4101-4016.

Chen, D.Z. , Szczerba, R.J. , and Uhran, J.J. Jr. 1997. A framed quad-tree approach for determining Euclidean shortest paths in a 2D environment. IEEE Trans. Robotics and Automation 13(5):668-681.

Cormen, T.H. , Leiserson, C.E. , and Rivest, R.L. 1990. Introduction to Algorithms. New York : McGraw-Hill.

10.

Fujimura, K. , and Samet, H. 1989. A hierarchical strategy for path planning among moving obstacles. IEEE Trans. Robotics and Automation 5(1):61-69.

11.

Gewali, L. , Meng, A. , Mitchell, J. , and Ntafos, S. 1988 (June). Path planning in 0/1/∞ weighted regions with applications. Proc. Fourth Annual Symp. Computational Geometry , pp. 266-278.

12.

Hart, P. , Nilsson, N. , and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Science and Cybernetics 4(2):100-107.

13.

Herman, M. 1986. Fast, three-dimensional, collision-free motion planning . Proc. IEEE Int. Conf. Robotics and Automation, pp. 1056-1063.

14.

Hughes, K. , Tokuta, A. , and Ranganathan, N. 1992. Trulla: An algorithm for path planning among weighted regions by localized propagations. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp. 469-476.

15.

Hwang, Y. , and Ahuja, N. 1992. Gross motion planning—A survey. ACM Computing Surveys 24(3):219-291.

16.

Jarvis, R.A. , and Byrne, J.C. 1986 (November). Robot navigation: Touching, seeing and knowing . Proc. 1st Australian Conf. Artificial Intelligence .

17.

Kambhampati, S. , and Davis, L. 1986. Multiresolution path planning for mobile robots . IEEE J. Robotics and Automation RA-2(3):135-145.

18.

Latombe, J. 1991. Robot Motion Planning. Boston : Kluwer.

19.

Lee, D.T. , Yang, C.D. , and Chen, T.H. 1991. Shortest rectilinear paths among weighted obstacles . Int. J. Computational Geometry and Applications 1(2):109-124.

20.

Lozano-Perez, T. , and Wesley, M. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22(10):560-570.

21.

Mitchell, J. , and Papadimitriou, C. 1991. The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. ACM 38:18-73.

22.

Noborio, H. , Naniwa, T. , and Arimoto, S. 1990. A quadtree-based path-planning algorithm for a mobile robot. J. Robotic Sys. 7(4):555-574.

23.

Preparata, F. , and Shamos, M. 1985. Computational Geometry—An Introduction. New York: Springer-Verlag.

24.

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

25.

Samet, H. 1985. An overview of quadtrees, octrees, and related hierarchical data structures. NATO ASI Series F40:51-68.

26.

Schwartz, J. , Sharir, M. , and Hopcroft, J. 1987. Planning, Geometry, and Complexity of Robot Motion Hillsdale, NJ: Ablex.

27.

Szczerba, R.J. , Chen, D.Z. , and Uhran, J. J. Jr. 1996 ( Lille, France, July). An efficient approach for determining shortest paths among 2D and 3D weighted regions. Proc. IEEE-SMC IMACS Multi-Conf. Computational Engineering in Systems Applications (CESA'96).

28.

Trovato, K. 1990. Differential A*: An adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment. Int. J. Pattern Recognition 4(2):245-268.

29.

Zelinsky, A. 1992. A mobile robot exploration algorithm. IEEE Trans. Robotics and Automation 8(6):707-717.