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.
Figures & tables
Fig. 1 : Simulation layout and sample snapshot of camera (black vertices) and target (black crosses) configuration. \mathchar28721\mathchar28726 cameras are placed on a \mathchar28724\mathchar8706\mathchar28724 grid over a \mathchar28721\mathchar28720\mathchar28720\mathchar8706\mathchar28721\mathchar28720\mathchar28720 workspace. Each camera has a sector FOV with half-angle \mathchar28723\mathchar28720\mathchar8718 and sensing range of \mathchar28722\mathchar28720 units (light gray wedges show the selected heading of each camera). Colored edges denote the one-hop communication links between grid neighbors, with warmer colors representing higher delays.
Fig. 2 : Coverage over time (mean \mathchar8710\mathchar28729\mathchar28725% CI, \mathchar29038\mathchar12349\mathchar28722\mathchar28720 runs, running average over \mathchar28725\mathchar28720 time steps) for DOG-IU and DOG under increasing maximum one-hop delay \mathchar29028ˉ on a \mathchar28721\mathchar28720\mathchar28720\mathchar8706\mathchar28721\mathchar28720\mathchar28720 workspace with \mathchar28721\mathchar28726 grid-placed cameras, \mathchar28728 headings, and \mathchar28728\mathchar28720 clustered targets (8 clusters). The gap widens as delay increases, illustrating the benefit of intermediate updates under more severe communication delays.
Fig. 3 : Layout and sample snapshot of the information-gathering simulation. \mathchar28721\mathchar28726 agents (black squares) are fixed at the vertices of a \mathchar28724\mathchar8706\mathchar28724 grid over a \mathchar28721\mathchar28720\mathchar28720\mathchar8706\mathchar28721\mathchar28720\mathchar28720 workspace, each orienting a \mathchar28724\mathchar28725\mathchar8718 sensing sector. Gray shading indicates sensing accuracy: it tapers smoothly across the sector edge to the floor \mathchar29031\mathchar29039\mathchar29045\mathchar29044 and decays with range, rather than terminating at a hard field-of-view boundary, which is what makes the reward continuous in the execution times. \mathchar28727\mathchar28722 targets (black crosses) in \mathchar28728 clusters follow linear-Gaussian dynamics with continuous-time maneuvers. Colored edges denote the one-hop communication links, with warmer colors representing higher delays.
Fig. 4 : Preliminary results on the information-gathering task; shaded bands are \mathchar28729\mathchar28725% confidence intervals and are narrower than the plot markers throughout. (a) Mean reward against the maximum one-hop delay \mathchar29028ˉ ( \mathchar29038\mathchar12349\mathchar28722\mathchar28720 seed-paired runs): DOG-IU is essentially unaffected by delay, whereas DOG degrades monotonically, so the advantage of intermediate updates grows with \mathchar29028ˉ and reaches \mathchar28721\mathchar28724\mathchar314\mathchar28728\mathchar28721% at \mathchar29028ˉ\mathchar12349\mathchar28723\mathchar28720 . (b) Reward relative to synchronous execution against the timing mismatch bound \mathchar28954 ( \mathchar29038\mathchar12349\mathchar28721\mathchar28720 seed-paired runs): degradation is smooth and close to proportional in \mathchar28954 , and the curves at \mathchar29028ˉ\mathchar12349\mathchar28720 and \mathchar29028ˉ\mathchar12349\mathchar28721\mathchar28720 coincide, indicating that communication delay and clock mismatch act as separate cost channels.