Organizations: Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907 USA · Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA
We study a target coverage problem in which a team of sensing agents, operating under limited communication, must collaboratively monitor targets that may be adaptively repositioned by an attacker. We model this interaction as a zero-sum game between the sensing team (known as the defender) and the attacker. However, computing an exact Nash equilibrium (NE) for this game is computationally prohibitive as the action space of the defender grows exponentially with the number of sensors and their possible orientations. Exploiting the submodularity property of the game's utility function, we propose a distributed framework that enables agents to self-configure their communication neighborhoods under bandwidth constraints and collaboratively maximize the target coverage. We establish theoretical guarantees showing that the resulting sensing strategies converge to an approximate NE of the game. To our knowledge, this is the first distributed, communication-aware approach that scales effectively for games with combinatorial action spaces while explicitly incorporating communication constraints. To this end, we leverage the distributed bandit-submodular optimization framework and the notion of Value of Coordination that were introduced in [1]. Through simulations, we show that our approach attains near-optimal game value and higher target coverage compared to baselines.
Figures & tables
Fig. 1: Distributed Target Coverage Game. Team of sensing agents choose communication neighbors and orientations to maximize target coverage. Simultaneously, the attacker selects a target deployment strategy to achieve the least coverage for the sensing agents. The algorithms ActSel , NeiSel , and their interaction framework via the Value of Coordination , follows [ 1 ] .
Fig. 2: Payoffs and duality gap. Consider the repeated game dynamics per Algorithm 1 between three sensors each with bandwidth constraint \mathchar28721 (defender) and an \delimiter69640972\mathchar29017\delimiter69640972\mathchar12349\mathchar28722\mathchar28720 possible target deployments (attacker). As \mathchar29012\mathchar12833\mathchar561 , the players asymptotically achieve the approximate NE, with the duality gap, i.e. , the difference between the players’ payoffs, decreasing to its minimum, as shown in Theorem 2 . Results are averaged over 20 Monte Carlo trials, each with 15000 rounds.
Fig. 3: Comparison of neighbor selection strategies. Four algorithms are compared under the same action selection strategy ( ActSel ) and adversarial environment ( EXP3 ), differing only in their neighbor selection strategies. Results are averaged over 20 Monte Carlo trials, each with 10000 rounds.
Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai, China · Department of Control Science and Engineering, Tongji University, Shanghai, China