摘要
为了解决随着机器人数量的增加,多机器人追逃中的最优联盟求解时间复杂度呈指数增长给实时计算带来的困难,本文在证明机器人追逃问题中的联盟收益独立性的基础上,根据逃跑者的数量来决定联盟结构中子联盟的数量,提出基于贪婪最优收益的追捕联盟算法.该算法首先根据逃跑机器人的数量确定联盟的个数,然后根据追捕机器人–逃跑机器人的追逃收益确定各个子联盟及其领导者,最后利用"贪婪最优"算法扩展新成员进入各子联盟直到所有的追捕者全部进入各个联盟.本算法简化了联盟结构每层的搜索量,总的搜索复杂度为O(m×(n m)),极大地缩短了算法的搜索时间,实际实验仿真结果也证明了本算法在追捕搜索效率和总追捕消耗时间上的优越性.
With the increasing number of robots, the time complexity of solving the optimal coalition problem increases exponentially, which brings difficulty to real-time computation. To solve the predicament, the independence of coalition gain is proved in pursuit-evasion games, and the number of sub pursuers-coalitions can be obtained according to the number of the evaders. Based on these, the pursuit-coalition algorithm based on greed optimal gains is proposed. In the algorithm, the number of pursuers-coalitions is determined according to the number of the evaders. Then, the sub pursuers-coalitions and the leaders of each sub pursuers-coalition are determined according to the corresponding pursuit gains of pursuers and evaders. Finally, all others pursuers are assigned tO the each sub optimal coalition based on greed optimal method. The algorithm simplifies the search volume of each level in the coalition structure and greatly improves the search time to O（m × （n -m））. The experiments show the superiority of the proposed algorithm in pursuit search efficiency and pursuit time.
出处
《机器人》
EI
CSCD
北大核心
2013年第2期142-150,共9页
Robot
基金
国家自然科学基金资助项目(61070131
61175051
61175033
61075076)
国家863计划计划资助项目(2012AA011005)
关键词
多机器人系统
追逃问题
联盟结构
联盟收益
联盟生成算法
贪婪最优收益
multi-robot system
pursuit-evasion game
coalition structure
coalition gain
coalition construction algorithm
greed optimal gain
