Finding the 3D shortest path with visibility graph and minimum potential energy

Abstract

Finding a three dimensional shortest path is of importance in the development of automatic path planning for mobile robots and robot manipulators, and for practical implementation, the algorithms need to be efficient. Presented is a method for shortest path planning in three-dimensional space in the presence of convex polyhedra. It is based on the visibility graph approach, extended from two to three-dimensional space. A collineation is introduced for the identification of visible edges in the three-dimensional visibility graph. The principle of minimum potential energy is adopted for finding a set of sub-shortest paths via different edge sequences, and from them the global shortest path is selected. The three dimensional visibility graph is constructed in O(n/sup 3/v/sup k/) time, where n is the number of vertices of the polyhedra, k is the number of obstacles and v is the largest number of vertices on any one obstacle. The process to determine the shortest path runs recursively in polynomial time. Results of a computer simulation are given, showing the versatility and efficiency of the approach.