Distributed Task Allocation With Minimum Makespan for Heterogeneous Multiplayer Pursuit-Evasion Games

• 成果类型: Article
• 署名作者: Li, Shuai; Wang, Chen; Sun, Jinan; Zhang, Shikun; Xie, Guangming
• 署名单位: Peking University; Peking University; Peking University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3485433
• 发表日期: 2025
• 页码: 2827-2842
• 关键词: games; resource management; sensors; Robot sensing systems; mathematical models; Heuristic algorithms; decentralized control; Usability; Biomimetics; TOPOLOGY; differential games; Distributed control; multiagent systems; pursuit-evasion games; task allocation

摘要

In the domain of multiplayer pursuit-evasion games, it is crucial to address the practical aspects of the players' heterogeneity, the distributed control manner, and the pursuers' goal of minimum makespan. However, the three topics have received limited attention in existing literature, both separately and in combination. In this article, we address the multiplayer pursuit-evasion game integrating these key topics, where the pursuers with simple motions strive to capture as many evaders, characterized by damped double integrators, as possible, meanwhile minimizing the task makespan. To this end, we establish an overall framework and sequentially tackle four key issues, leading to an effective solution to the entire problem. We first propose a novel isochron-based method to derive the capture condition and acquire the optimal pursuit and evasion strategies. Then, we enhance the usability of the capture condition by geometrically deriving the analytical form of the pursuer's winning region with respect to a given evader. Third, leveraging the concept of winning regions, we determine the lower boundary of pursuers' sensing range, ensuring sufficient information acquisition for evader allocation while avoiding selection conflicts. Finally, we propose a fully distributed allocation algorithm for each pursuer allowing the pursuer team to converge to the optimal evader allocation. By combining these contributions, we successfully provide an effective solution to the entire problem. Various simulations are conducted to show the effectiveness of our proposed methods.