A Dynamic Fusion Pathfinding Algorithm Using Delaunay Triangulation and Improved A-Star for Mobile Robots

Abstract

Although many studies exist on mobile robot path planning, the disadvantages of complex algorithms and many path nodes in logistics warehouses and manufacturing workshops are obvious, mainly due to the inconsistency of map environment construction and pathfinding strategies. In this study, to improve the efficiency of mobile robot path planning, the Delaunay triangulation algorithm was used to process complex obstacles and generate Voronoi points as pathfinding priority nodes. The concept of the grid was used to extract obstacle edges to provide obstacle avoidance strategies for robot pathfinding. Subsequently, the search for priority and regular path nodes used the improved A-star (A*) algorithm. The dynamic fusion pathfinding algorithm (DFPA), based on Delaunay triangulation and improved A*, was designed, which realizes the path planning of mobile robots. MATLAB 2016a was used as the simulation software, to firstly verify the correctness of the DFPA, and then to compare the algorithm with other methods. The results show that under the experimental environment with the same start point, goal point, and number of obstacles, the map construction method and pathfinding strategy proposed in this paper reduce the planned path length of the mobile robot, the number of path nodes, and the cost of overall turn consumption, and increase the success rate of obtaining a path. The new dynamic map construction method and pathfinding strategy have important reference significance for processing chaotic maps, promoting intelligent navigation, and site selection planning.

Keywords

• Delaunay triangulation
• A-star algorithm
• mobile robot
• map modeling
• path planning