Matching-Based Capture-the-Flag Games for Multiagent Systems
Jiali Wang, Zhao Zhou, Xin Jin, Shuai Mao, Yang Tang
Abstract
Competition and cooperation among agents in multi-agent systems can be effectively modeled as differential games. One of the typical tasks is capturing the flag, in which the agents can be divided into attackers’ alliance and defenders’ alliance with two-phase competitive behaviors. The attackers’ alliance aims to capture flags in the first phase and then return to the safe region in the second phase, while the defenders’ alliance aims to protect the flags and apprehend as many attackers as possible. Throughout the interaction, agents are actively involved in perception, cognitive learning, and the formulation of optimal decisions rooted in their acquired knowledge. Consequently, this paper delves into the central challenges posed by capture-the-flag differential games, particularly in terms of task allocation and coordinated apprehension strategies among defenders. First, we use the Apollonius circle to transform the multi-player capture-the-flag problems into one-defense-one or two-defense-one scenarios. By analyzing the advantages of cooperation between defenders, a two-stage joint optimal strategy is obtained. Moreover, we propose an approximation algorithm that achieves optimal task assignment, significantly reducing computational complexity. The performance and effectiveness of the proposed algorithm are demonstrated through numerical simulations.