多机器人追逃问题中的追捕联盟生成算法

为了解决随着机器人数量的增加,多机器人追逃中的最优联盟求解时间复杂度呈指数增长给实时计算带来的困难,本文在证明机器人追逃问题中的联盟收益独立性的基础上,根据逃跑者的数量来决定联盟结构中子联盟的数量,提出基于贪婪最优收益的追捕联盟算法.该算法首先根据逃跑机器人的数量确定联盟的个数,然后根据追捕机器人–逃跑机器人的追逃收益确定各个子联盟及其领导者,最后利用"贪婪最优"算法扩展新成员进入各子联盟直到所有的追捕者全部进入各个联盟.本算法简化了联盟结构每层的搜索量,总的搜索复杂度为O(m×(n m)),极大地缩短了算法的搜索时间,实际实验仿真结果也证明了本算法在追捕搜索效率和总追捕消耗时间上的优越性.