基于分组拍卖的集群机器人启发式图形构造算法

Heuristic shape formation algorithm in swarm robots based on group auction

集群机器人的图形构造问题是指通过控制集群机器人的运动趋使其形成一个特定的图形.集群机器人中的图形构造问题通常可以分解为两个子问题:机器人与目标点之间的任务分配以及机器人与目标点之间的路径规划.根据集群机器人图形构造问题规模大、易拥堵、碰撞的特点,提出了一种集中优化、分组拍卖以及分布式交互相结合的OGADI(optimized grouping auction and distributed interaction)方法,以缩短图形构造的完成时间.将OGADI算法与最短路径集诱导顶点排序算法对比,结果表明,在集群机器人规模分别为500, 1000, 1300下, OGADI算法图形构造任务平均完成时间分别缩短了16.1%, 13.6%, 14.4%,仿真验证了OGADI算法的可行性和有效性.

The shape formation refers to forming a special shape by controlling the movement of the swarm robots. The problem of shape formation in swarm robots can often be reduced to two sub-problems: the task allocation and the path planning between the robots and the targets. According to the characteristics of large-scale, easy congestion and collision in the shape formation problem, the optimized grouping auction and distributed interaction(OGADI) algorithm is proposed to shorten the completion time of the task.The OGADI algorithm is compared with the shortest path set induced vertex ordering algorithm. The results show that the average completion time of the OGADI algorithm on a scale of 500, 1000, 1300 swarm robots are shortened by 16.1%, 13.6%, and 14.4%,respectively. Some simulation results verify the effectiveness of the proposed method in this paper.