Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays
This addresses scalable information-gathering in unknown environments for multi-agent systems, but it is incremental as it extends prior work by handling heterogeneity and asynchrony.
The paper tackles the problem of asynchronous distributed decision-making for multi-agent bandit submodular maximization under heterogeneous communication delays and mismatched local clocks, providing an algorithm with a provable approximation guarantee that depends on delays and topology, validated through simulations on multi-camera area monitoring.
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. We validate the approach through numerical simulations on multi-camera area monitoring.