Three-Dimensional Shortest Path Planning in the Presence of Polyhedral Obstacles

Abstract

A new algorithm is presented for solving the three-dimensional shortest path planning (3DSP) problem for a point object moving among convex polyhedral obstacles. It is the first non-approximate three-dimensional path planing algorithm that can deal with more than two polyhedral obstacles. The algorithm extends the visibility graph concept from two dimensions to three dimensions. The two main problems with 3DSP are identifying the edge sequence the shortest path passes through and the turning points of the shortest path. A technique based on projective relationships is presented for identifying the set of visible boundary edges (VBE) corresponding to a given view point over which the shortest path, from the view point to the goal, will pass. VBE are used to construct an initial reduced visibility graph (RVG). Optimization is used to revise the position of the turning points and hence the three-dimensional RVG (3DRVG) and the global shortest path is then selected from the 3DRVG. The algorithm is of computational complexity O(n³v^k), where n is the number of verticles, v is the maximum number of vertices on any one obstacle and k is the number of obstacles. The algorithm is applicable only with polyhedral obstacles, as the theorems developed for searching for the turning points of the three-dimensional shortest path are based on straight edges of the obstacles. It needs to be further developed for dealing with arbitrary-shaped obstacles and this would increase the computational complexity. The algorithm is tested using computer simulations and some results are presented.

Keywords

path planning three-dimensional shortest path planning reduced visibility graph polyhedral obstacles collision avoidance

Get full access to this article

View all access options for this article.

References

Lozano-Pérez

Wesley

M. A.

An algorithm for planning collision-free paths among polyhedral obstacles. Communs of the ACM, 1979, 22(10), 560–570.

Udupa

Collision detection and avoidance in computer controlled manipulators. PhD dissertation, Department of Electrical Engineering, California Institute of Technology, 1977.

Sharir

Schorr

On the shortest paths in polyhedral spaces. Proceedings of Sixteenth ACM Symposium on The theory of computing, Washington D.C., 1984, pp. 144–153.

Sharir

Schorr

On the shortest paths in polyhedral spaces. SIAM J. on Computing, February 1986, 15(1).

Sharir

On shortest path amidst convex polyhedra. Technical report 181, CIMS, New York, 1985.

Mount

D. M.

On finding shortest paths on convex polyhedra. Technical report, Computer Science Department, University of Maryland, October 1984.

Mitchell

J. S. B.

Planning shortest paths. PhD dissertation, Department of Operations Research, Stanford University, 1986.

Mitchell

J. S. B.

Mount

D. M.

Papadimitriou

C. H.

The discrete geodesic problem. SIAM J. of Computing, 1987, 16(4), 647–668.

Papadimitriou

C. H.

An algorithm for shortest-path motion in three dimensions. Inf. Processing Lett., 1985, 20(5), 255–263.

10.

Canny

J. F.

The complexity of robot motion planning, 1988 (MIT Press, Cambridge, Mass.).

11.

Latombe

J. C.

Robot motion planning, 1991 (Kluwer Academic Publishers, Dordrecht, The Netherlands).

12.

Reif

J. H.

Storer

J. A.

Single-exponential upper bound for finding shortest paths in 3 dimensions. J. Ass. for Computing Machinery, 1994, 41(5), 1013–1019.

13.

Gemali

L. P.

Ntafos

Tollis

I. G.

Path planning in the presence of vertical obstacles. IEEE Trans. Robotics Automn, June 1990, 6(3).

14.

Ahuja

Chien

R. T.

Yen

Bridwell

Interference detection and collision avoidance among three dimensional objects. Proceedings of First AAAI Conference, Stanford, 1980, pp. 44–48.

15.

Faverjon

Obstacle avoidance using an Octree in the configuration space of a manipulator. Proceedings of IEEE International Conference on Robotics and automation, Atlanda, 1984, pp. 1406–1412.

16.

Hayward

Fast collision detection schema by recursive decomposition of a manipulator workspace. Proceedings of IEEE International Conference on Robotics and automation, San Francisco, Calif., 1986, pp. 1044–1049.

17.

Herman

Fast, three-dimensional, collision-free motion planning. Proceedings of IEEE International Conference on Robotics and automation, San Francisco, Calif., 1986, pp. 1056–1063.

18.

Kambhampati

Davis

L. S.

Multiresolution path planning for mobile robots. IEEE Trans. Robotics and Automn, 1986, 2(3), 135–145.

19.

Fujimura

Samet

A hierarchical strategy for path planning among moving obstacles. IEEE Trans. Robotics and Automn, 1989, 5(1), 61–69.

20.

Tarokh

Fast path planning for robot manipulators. Proceedings of IEEE International Conference on Intelligent robots and systems, Raleigh, 1992, pp. 663–668.

21.

Jun

Shin

K. G.

Shortest path planning in discretized workspace using dominance relation. IEEE Trans. Robotics Automn, June 1991, 7(3).

22.

Williams

R. L.

Lee

T. G.

Determination of minimum 3-dimensional cutting-tool paths in the presence of barriers. Computers and Ind. Engng, 1993, 25(1–4), 211–214.

23.

Liu

Y. H.

Arimoto

Proposal of tangent graph and extended tangent graph for path planning of mobile robots. Proceedings of 1991 IEEE International Conference on Robotics and automation, Sacramento, California, April 1991.

24.

Semple

J. G.

Kneebone

G. T.

Algebraic projective geometry, 1956, 1st edition 1952, p. 348 (Clarendon Press, Oxford).