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.
Figures & tables
Fig. 1: Information Access Matters: A Multi-Camera Area Monitoring Example. Consider a multi-camera area monitoring task where four cameras must coordinate their fields of view (FOVs) via distributed communication to maximize total coverage. As shown in (a), suppose that cameras 1–3 have already fixed their FOVs (soft orange), and camera 4 must select its FOV from three predefined options (dark red). While the optimal choice for camera 4 depends on the FOVs of all other three, its communication bandwidth allows it to receive information from at most two of them at any current time. The three possible communication neighborhood configurations and the corresponding FOV selections are demonstrated in (b)–(d), among which the design in (c) yields the highest coverage and therefore the optimal FOV decision. This example illustrates that intelligent information access—enabled by active neighborhood design (possibly over multiple time steps)—can optimize action coordination performance in distributed settings with limited communication resources.
Fig. 2: Asymptotic approximation bounds of Anaconda . As \mathchar29012\mathchar12833\mathchar561 , the bounds provided by Theorems 1 , 2 and 3 are shown with varying ranges of \mathchar28948\mathchar29030 and achieved \mathchar28940 (defined in eq. 18 ). The a priori bound (red) varies with the sum of all agents’ VoC ; the a posteriori bound (orange) decreases as \mathchar28940 increases; and the combined bound (blue) takes the maximum of the a priori lower bound and the a posteriori bound.
Fig. 3: Comparison of neighbor selection strategies with varying network density. Across 20 MC trials each with 2000 decision rounds, we compare NeiSel with two benchmark strategies, Nearest Neighbors and Random Neighbors. We tune the network density by varying the map area while fixing the network size at 20 agents: as the camera density grows, the network becomes sparser.
Fig. 4: Comparison of neighbor selection strategies in a structured environment. Three algorithms are compared with the same action selection strategy ActSel but different neighbor selection strategies ( NeiSel vs. nearest neighbors vs. random neighbors) in the same structured environment.
TABLE I: Comparison of coverage performance (%) in the urban scenario as in Fig. 4 with different neighbor selection strategies. The best coverage performance is in bold .
Fig. 5: Comparison of Anaconda , DFS-SG , and DFS-BSG for area monitoring without computation and communication delays. Cameras select their FOV directions using Anaconda with maximum communication neighborhood sizes in {\mathchar28720\mathchar24891…\mathchar24891\mathchar28725} , or using DFS-SG or DFS-BSG . From (a) to (d), the communication range \mathchar29027\mathchar29033 for all cameras \mathchar29033\mathchar12850\mathchar29006 increases from 10 to 16 to 20 to 80, and thus expanding each camera’s coordination neighborhood \mathchar29005\mathchar29033 growing from a small locality to the full set \mathchar29006\mathchar8814{\mathchar29033} . DFS-SG is executed for a single decision round, whereas the other algorithms are run for 4000 rounds. Results are averaged over 20 Monte Carlo trials.
Fig. 6: Comparison of Anaconda vs. DFS-SG vs. DFS-BSG for real-time coverage performance under computation and communication delays. Cameras select their FOV directions using Anaconda with maximum communication neighborhood sizes in {\mathchar28720\mathchar24891…\mathchar24891\mathchar28725} , or using DFS-SG or DFS-BSG . From (a) to (b) to (c), the time \mathchar28956\mathchar29030 for one function evaluation increases relative to the delay \mathchar28956\mathchar29027 for transmitting one action through a communication link, with the ratio \mathchar28956\mathchar29030\delimiter68408078\mathchar28956\mathchar29027 taking values \mathchar28721\delimiter68408078\mathchar28723 , \mathchar28721 , and \mathchar28723 . DFS-SG is executed for a single decision round, whereas the other algorithms are run for a fixed duration of \mathchar28723\mathchar28720\mathchar28720 seconds. Under different delay configurations, the algorithms complete different numbers of decision rounds within this time window. Results are averaged over 20 Monte Carlo trials.
TABLE II: Comparison of average coverage performance (%) within \mathchar28723\mathchar28720\mathchar28720 s across three scenarios with different delay configurations (Fig. 6 ). The highest value in each scenario is highlighted in bold .
Fig. 7: Comparison of Anaconda-5n vs. DFS-BSG in real-time coverage performance with scaling network. Cameras select their FOV directions using Anaconda-5n or DFS-BSG , across five scenarios with different network and map sizes. To keep the camera density constant, the map size scales linearly from \mathchar28722\mathchar28723\mathchar8706\mathchar28722\mathchar28723 to \mathchar28725\mathchar28720\mathchar8706\mathchar28725\mathchar28720 as the network size ranges from \mathchar28721\mathchar28720 to \mathchar28725\mathchar28720 . Results are averaged over 20 Monte Carlo trials, each with a fixed \mathchar28723\mathchar28720\mathchar28720 s time window under delays \delimiter67273472\mathchar28956\mathchar29030\mathchar24891\mathchar28956\mathchar29027\delimiter84054785\mathchar12349\delimiter67273472\mathchar314\mathchar28720\mathchar28721s\mathchar24891\mathchar314\mathchar28720\mathchar28721s\delimiter84054785 .
We study asynchronous distributed decision-making for scalable multi-agent bandit submodular maximization. We are motivated by distributed information-gathering tasks in unknown environments and under heterogeneous inter-agent communication delays. To enable scalability despite limited communication delays, existing approaches restrict each agent to coordinate only with its one-hop neighbors. But these approaches assume homogeneous communication delays among the agents and a synchronous global clock. In practice, however, delays are heterogeneous, and agents operate with mismatched local clocks. That is, each agent does not receive information from all neighbors at the same time, compromising decision-making. In this paper, we provide an asynchronous coordination algorithm to overcome the challenges. We establish a provable approximation guarantee against the optimal synchronized centralized solution, where the suboptimality gap explicitly depends on communication delays and clock mismatches. The bounds also depend on the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only. The clock-mismatch penalty is expressed through a bounded oscillation of the reward in the execution times, which, unlike a Lipschitz condition, is available for discrete-valued rewards such as target monitoring. We validate the approach through numerical simulations on multi-camera target monitoring through the lenses of two different reward structures and simulation setups.
Pranjal Sharma, Zirui Xu, Vasileios Tzoumas
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA
We provide a distributed online algorithm for multi-agent submodular maximization under communication delays. We are motivated by the future distributed information-gathering tasks in unknown and dynamic environments, where utility functions naturally exhibit the diminishing-returns property, i.e., submodularity. Existing approaches for online submodular maximization either rely on sequential multi-hop communication, resulting in prohibitive delays and restrictive connectivity assumptions, or restrict each agent's coordination to its one-hop neighborhood only, thereby limiting the coordination performance. To address the issue, we provide the Distributed Online Greedy (DOG) algorithm, which integrates tools from adversarial bandit learning with delayed feedback to enable simultaneous decision-making across arbitrary network topologies. We provide the approximation performance of DOG against an optimal solution, capturing the suboptimality cost due to decentralization as a function of the network structure. Our analyses further reveal a trade-off between coordination performance and convergence time, determined by the magnitude of communication delays. By this trade-off, DOG spans the spectrum between the state-of-the-art fully centralized online coordination approach [1] and fully decentralized one-hop coordination approach [2].
Zirui Xu, Vasileios Tzoumas
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.
Jayanth Bhargav, Zirui Xu, Vasileios Tzoumas +2
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