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.
We study how to scale distributed bandit submodular coordination under realistic communication constraints in bandwidth, data rate, and connectivity. We are motivated by multi-agent tasks of active situational awareness in unknown, partially-observable, and resource-limited environments, where the agents must coordinate through agent-to-agent communication. Our approach enables scalability by (i) limiting information relays to only one-hop communication and (ii) keeping inter-agent messages small, having each agent transmit only its own action information. Despite these information-access restrictions, our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time, through distributed online bandit optimization, subject to the agents' bandwidth constraints. Particularly, our approach enjoys an anytime suboptimality bound that is also strictly positive for arbitrary network topologies, even disconnected. To prove the bound, we define the Value of Coordination (VoC), an information-theoretic metric that quantifies for each agent the benefit of information access to its neighbors. We validate in simulations the scalability and near-optimality of our approach: it is observed to converge faster, outperform benchmarks for bandit submodular coordination, and can even outperform benchmarks that are privileged with a priori knowledge of the environment.
Zirui Xu, Vasileios Tzoumas
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA
Autonomous drone swarms deployed for surveillance, environmental monitoring, and infrastructure inspection must maintain reliable coverage of critical assets despite robot failures. This requires multicoverage: each asset must be observed by multiple robots for redundancy, with coverage requirements varying by asset importance. While recent work has solved the centralized problem optimally using integer programming, practical deployments face constraints that demand distributed solutions: robots operate with limited communication ranges, onboard computation restricts global planning, and partial system failures must not cause mission abort. We present a distributed multicoverage algorithm for robot swarms operating with local sensing, local communication, and no global coordination.
This paper investigates mobile target search under imperfect perceptions caused by sensor limitations, malicious jamming, or communication noise. Searchers and targets operate in a grid-shaped area with bounded mobility, leading to a dynamic interplay between search and evasion. To capture this adversarial interaction under imperfect perceptions, we adopt the partially observable stochastic game (POSG) approach, which generalizes partially observable Markov decision processes (POMDPs) by incorporating target intelligence. To handle false alarms and missed detections caused by perceptual uncertainties, we propose a novel detectability concept to determine whether a search strategy guarantees eventual detection, and provide sufficient detectability criteria based on stochastic recurrence analysis. We further develop a server-assisted distributed algorithm that utilizes the aggregative potential game structure for searchers and a KL-divergence-based reduction for target prediction. Numerical simulations validate the effectiveness of the proposed algorithm and support the detectability analysis.
Hanzheng Zhang, Shu Liang, Shuyu Liu
Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai, China · Department of Control Science and Engineering, Tongji University, Shanghai, China