Obstacle avoidance path planning by the Extended VGraph Algorithm

摘要

In many path planning algorithms, attempts are made to optimize the path between the start and the goal in terms of Euclidean distance. Since the moving object is shrunk to a point in the configuration space, findpath can be formulated as a graph searching problem. This is known as the VGraph Algorithm. Lozano-Perez points out the drawbacks of the VGraph Algorithm. The first drawback is related with rotation of a moving object. This drawback can be solved by using the sliced projection method. However, the VGraph Algorithm has serious drawbacks when the obstacles are three-dimensional. The Extended VGraph Algorithm is proposed to solve the drawbacks of the VGraph Algorithm by using the Recursive Compensation Algorithm. The Recursive Compensation Algorithm is proposed to find the collision-free shortest path in 3D and it is proved to guarantee the convergence of the shortest path in 3D without increasing the complexity of the VGraph.