面向群组机器人自组装的Voronoi图边界求交细分路径规划方法

Self Assembly Path Planning of Swarm Robots Based on Voronoi Diagram Boundary Intersection and Tessellation

自组装是群组机器人实现各种目标配置的有效途径,群组路径规划是群组机器人自组装实现的关键问题所在.本文在CVT算法基础上提出了一种基于Voronoi图边界求交细分的VBIT算法.首先根据群组机器人成员位置绘制相应Voronoi图,然后利用匈牙利算法为机器人与目标地分配对应关系,通过将机器人与目标地连线和机器人所在单元的交点作为下一次机器人移动起始点,多次迭代后达到目标配置.实验结果证明在自组装的精度、耗时、适用性方面比现有算法更优.

Self-assembly is an effective way for swarm robots to realize various target configurations.Path planning is the key problem of swarm robots self-assembly.In this paper.we propose a voronoi diagram boundary intersection and tessellation(VBIT)algorithm based on centroidal Voronoi tessellation(CVT)algorithm.First,drawthe Voronoi diagram according to the position of the swarm robot,Then use the Hungarian algorithm to assign the correspondence between the robot and the target.By using the intersection of Robot position and depart point connection and the cell where the robot is as the starting point for the robot’s next move,Reach the target configuration after many iterations.Experimental results showthat it is superior to the existing algorithms in the accuracy,time-consuming and applicability of self-assembly.