论文部分内容阅读
为了解决随着机器人数量的增加,多机器人追逃中的最优联盟求解时间复杂度呈指数增长给实时计算带来的困难,本文在证明机器人追逃问题中的联盟收益独立性的基础上,根据逃跑者的数量来决定联盟结构中子联盟的数量,提出基于贪婪最优收益的追捕联盟算法.该算法首先根据逃跑机器人的数量确定联盟的个数,然后根据追捕机器人–逃跑机器人的追逃收益确定各个子联盟及其领导者,最后利用“贪婪最优”算法扩展新成员进入各子联盟直到所有的追捕者全部进入各个联盟.本算法简化了联盟结构每层的搜索量,总的搜索复杂度为O(m×(n m)),极大地缩短了算法的搜索时间,实际实验仿真结果也证明了本算法在追捕搜索效率和总追捕消耗时间上的优越性.
In order to solve the problem of real-time computation with the exponential increase of the complexity of solving the optimal alliance in multi-robot chasing after the increase of the number of robots, on the basis of proving the independence of alliance revenue in the pursuit of robots, According to the number of runners to determine the number of neutron coalitions in the coalition structure, a chase coalition algorithm based on greedy optimal profit is proposed. The algorithm firstly determines the number of coalitions according to the number of escaped robots, The benefits are determined by each sub-union and its leader, and finally the new members are expanded into sub-alliances by using “greedy optimal” algorithm until all the pursuers enter the alliances.The algorithm simplifies the search volume of each layer of the coalition structure, The search complexity is O (m × (nm)), which greatly shortens the search time of the algorithm. The actual experimental simulation results also prove the superiority of this algorithm in hunting search efficiency and total hunting time.