Surface Optimal Path Planning Using an Extended Dijkstra Algorithm

Abstract

Extensive studies have been conducted on the Dijkstra algorithm owing to its bright prospect. However, few of them have studied the surface path planning of mobile robots. Currently, some application fields (e.g., wild ground, planet ground, and game scene) need to solve the optimal surface path. This paper proposes an extended Dijkstra algorithm. We utilize the Delaunay triangulation to model the surface environment. Based on keeping the triangle side length unchanged, the triangle mesh on the surface is equivalently converted into a triangle on the two-dimensional plane. Through this transformation, we set up the two-dimensional developable passable channel of the surface and solve the optimal route on this channel. Traversing all the two-dimensional developable and passable paths of the surface, we can get the shortest route among all the optimal paths. Then the inverse transformation from the two-dimensional plane coordinates to the corresponding surface coordinates obtains the surface optimal path. The simulation results show that, compared with the traditional Dijkstra algorithm, this method improves the accuracy of the surface optimization path in single-robot single-target and multi-robot multi-target path planning tasks.