A recent paper by members of the DCIST alliance proposes a new resource allocation game that studies a dynamic, adversarial resource allocation problem in environments modeled as graphs. By combining ideas from Colonel Blotto games with a population dynamics model, the proposed formulation incorporates: (i) dynamic reallocation in time-varying situations, and (ii) the presence of adversarial agents. A blue team of defender robots are deployed in the environment to protect the nodes from a red team of attacker robots. The engagement is formulated a discrete-time dynamic game, where the robots can move at most one hop in each time step. The game terminates with the attacker’s win if any location has more attacker robots than defender robots at any time. The goal is to identify dynamic resource allocation strategies, as well as the conditions that determine the winner: graph structure, available resources, and initial conditions. The authors analyze the problem using reachable sets and show how the outdegree of the underlying graph directly influences the difficulty of the defending task. Furthermore, they provide algorithms that identify sufficiency of the attacker’s victory. The proposed model has a potential for being extended to various scenarios to study dynamic and adversarial engagement between robots with traversability constraints.

Capability: T2C1B: Distributed Control for Dynamic Resource Allocation in Adversarial Environments

Points of Contact: Daigo Shishika (PI), Scott Guan, Michael Dorothy 

Paper: https://arxiv.org/pdf/2112.09890.pdf

Citation: Daigo Shishika, Yue Guan, Michael Dorohy, and Vijay Kumar, “Dynamic Defender-Attacker Blotto Game,” (under review), arXiv preprint, arXiv:2112.09890 (2021).