Fusion of weighted Voronoi diagram and $\mathrm{A}^{\ast}$ algorithm for mobile robot path planning

摘要

A* algorithm is one of the most common algorithms in path planning for mobile robots, which can complete global search and seek the lowest cost path. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{a}^{\ast}$</tex> algorithm has more search ability compared with other algorithms, but its algorithm has long computation time, more search nodes and other drawbacks have always existed. To address these problems, this paper proposes a way to plan paths by fusing weighted Voronoi map and improved <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{A}^{\ast}$</tex> algorithm, which will adopt the concept of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{A}^{\ast}$</tex> algorithm and combine with the idea of map construction, taking the lead to take the weighted Voronoi point as the priority expansion node, and if there is no directly searchable generation value minimum weighted Voronoi node, the weighted Voronoi edge will be the priority path, and so on. Simulation experimental results show that the algorithm can search for shorter paths in complex environments with relatively faster speed, which not only improves the search efficiency, but also improves the safety and accuracy of the paths.