Voronoi Diagram based Collision-free A* Algorithm for Mobile Vehicle in Complex Dynamic Environment

Abstract

Path planning is the research focus of robot development and design. As technology advances, mobile vehicles for various jobs are used in different environment. Therefore, it is an important research to plan an optimal path that is able to avoid obstacles and consider time and distance to reach the goal. In this paper, to improve the efficiency of mobile vehicle path planning, the Voronoi diagram is used to describe the map, and the shortest path tree is built by Dijkstra algorithm. Re-planning path task is activated when moving obstacles approach the mobile vehicle. The collision-free A* algorithm that take account of the directions and positions of the moving obstacles will effectively avoid collisions and find optimal path according to the shortest path tree. In the simulation results, there are several random moving obstacles in the map to simulate the complex dynamic environment. The mobile vehicle could reach the goal without any collisions, and only add a small amount of time and distance.