一种基于Voronoi_Obstacle场的移动机器人路径规划算法

A path planning algorithm for mobile robots based on Voronoi_Obstacle field

传统Voronoi场计算复杂度高,计算时间长,在空间变大、毛刺增多、栅格变密等情况下,基于Voronoi图的传统路径规划计算缓慢。为此提出了一种基于Voronoi_Obstacle场的移动机器人路径规划算法,采用分层思想构建Voronoi_Obstacle场,并使用启发式搜索算法规划路径。实验结果表明,Voronoi_Obstacle场比传统Voronoi场的复杂度降低O(n^(0.5)),且基于Voronoi_Obstacle场的路径规划时间比传统的基于Voronoi图的路径规划时间缩短34.53%,比改进的基于Voronoi图的路径规划时间缩短31.76%。研究结果表明,基于Voronoi_Obstacle场的移动机器人路径规划算法具有一定的可行性和优越性。

The traditional Voronoi field has high computation complexity and long computation time,and the traditional path planning based on Voronoi diagram is slower when space becomes larger,burrs increase and grids become dense.In order to solve the above problem,this paper proposes a mobile robot path planning algorithm based on Voronoi_Obstacle field.It adopts a hierarchical idea to construct the Voronoi_Obstacle field,and uses a heuristic search algorithm to find a path.The experimental results show that the complexity of the proposed Voronoi_Obstacle field is lower than the traditional Voronoi field by O(n^(0.5)).Moreover,the proposed path planning based on Voronoi_Obstacle field is 34.53%shorter than the traditional path planning based on Voronoi diagram,and 31.76%shorter than the improved path planning based on Voronoi diagram.The results show the feasibility and superiority of the mobile robot path planning algorithm based on Voronoi_Obstacle field.