Path planning for an intelligent robot 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, the findpath problem can be formulated as a graph-searching problem. This is known as the VGraph algorithm. However, its first drawback is related to the rotation of a moving object. This drawback has been solved by using the sliced projection method. 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 latter is to find the collision-free shortest path in 3 D without increasing the complexity of the VGraph, and it is shown to converge the shortest path in 3 D. It is noted that, simplifying the VGraph, the extended VGraph algorithm can save not only the memory space to represent the VGraph but also the graph-searching time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>