Communication-and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks

Zirui Xu, Sandilya Sai Garimella, Vasileios Tzoumas

TL;DR

When multi-robot teams coordinate on information-gathering tasks like search or mapping, existing near-optimal submodular algorithms suffer from cubic time complexity due to network-wide message passing. This paper presents Resource-Aware distributed Greedy (RAG), an algorithm that restricts communication strictly to local 1-hop neighborhoods, driving decision times down to linear scaling ($O(|N|)$) while preserving rigorous approximation guarantees. In high-fidelity AirSim simulations with up to 45 drones, RAG plans up to three orders of magnitude faster than state-of-the-art methods while achieving superior coverage under realistic communication delays.

What Problem Does This Paper Address?

Active information-gathering tasks—such as collaborative mapping, visual search, and target tracking—exhibit submodularity (diminishing marginal returns): two nearby drones viewing the same road segment yield redundant information. To maximize collective coverage, robots must coordinate their actions.

However, existing near-optimal distributed submodular optimization methods (such as Sequential Greedy / Coordinate Descent and continuous consensus algorithms) require actions or gradient estimates to be relayed across the entire network. Over wireless robot-to-robot (r2r) mesh networks with limited bandwidth (e.g., 0.25 Mbps for Zigbee modules), this leads to quadratic or cubic decision-time complexity ($O(|N|^2)$ to $O(|N|^3)$). For networks of tens or hundreds of robots, coordinating a single motion step can take minutes or even hours. Conversely, heuristic methods that achieve real-time speeds ignore submodular overlap, leading to severe performance loss when robots operate in close proximity.

Methods

The authors introduce Resource-Aware distributed Greedy (RAG), which restricts communication and computation to local neighborhoods:

  • Local Coordination Protocol: Each robot $i$ communicates solely with a subset of neighbors $\mathcal{N}_i$ chosen under onboard bandwidth constraints (e.g., $k$-nearest neighbors). Undecided robots evaluate their local candidate actions, exchange their best marginal gains ($g_i$), and only the robot with the highest marginal gain among its uncommitted neighbors commits to an action.
  • Parallel Execution: Robots in disjoint neighborhoods commit to actions simultaneously without waiting for a global sequence or multi-hop token relay.
  • Theoretical Framework:
  • Centralization of Information ($\text{coin}$): A novel metric that quantifies how much an agent’s selected action overlaps with non-neighbors, capturing the suboptimality penalty of decentralization.
  • Performance Guarantees: The authors derive a priori and a posteriori approximation bounds showing that RAG achieves near-optimal performance (matching the centralized greedy bound of $1/(1+\kappa_f)$ when fully connected, where $\kappa_f$ is curvature) and gracefully degrades as networks become sparser.
  • Simulator Extension: To evaluate realistic r2r delays, the authors extended Microsoft AirSim with multi-threaded ROS wrappers and an r2r network simulation module modeling finite bandwidth, range limits, and message serialization overhead.

Datasets

  • AirSim Urban Environment Benchmark: The paper does not use static machine learning datasets. Instead, it evaluates coordination dynamically in a photorealistic AirSim simulation of an urban environment where 15 to 45 quadrotors perform real-time collaborative road detection and visual coverage using downward-facing gimbaled cameras and semantic segmentation.

Key Insights and Ideas

  • Network Sparsity Favors Scalability: The marginal improvement in approximation guarantees grows sublinearly with neighborhood size (approximate submodularity of the bound), whereas coordination delays grow with neighborhood density. Consequently, maintaining sparse local neighborhoods (e.g., $k \ge 2$) captures most of the performance benefits without incurring communication bottlenecks.
  • Eliminating Multi-Hop Relays: By prohibiting the relay of action histories from distant robots, computational complexity per robot drops to $O(|V_i||\mathcal{N}_i|)$ and communication rounds scale as $O(|N|)$, independent of the network diameter.
  • Task-Aware Guarantees: Unlike prior decentralized greedy analyses that are task-agnostic and scale poorly with network size (e.g., bounds degrading as $O(1/|N|)$), RAG’s bounds adapt directly to the objective function's curvature $\kappa_f$ and actual spatial overlap ($\text{coin}$).

Key Results

  • Linear vs. Cubic Scalability: Moving from 15 to 45 robots, RAG's coordination time scaled linearly (at most a $3\times$ increase). In contrast, Sequential Greedy (SG) and Depth-First Search SG (DFS-SG) scaled cubically or super-cubically, suffering a $30\times$ to $60\times$ slowdown (ballooning from ~14 seconds to over 850 seconds per planning step at 0.25 Mbps).
  • Up to $1000\times$ Speedup: In scenarios with realistic low bandwidth (0.25 Mbps Digi XBee 3), RAG executed decisions in real-time (1–3 seconds per step, including ROS message overhead), running up to three orders of magnitude faster than baseline near-optimal algorithms.
  • Superior Coverage: Because baselines froze robots in place while awaiting sequential replanning, RAG-knn ($k \ge 2$) achieved higher total road-area coverage over fixed mission durations.

Limitations and Future Work

  • Synchronous Communication Assumption: The current algorithm relies on synchronized coordination rounds. While adaptable to asynchronous execution, theoretical guarantees under asynchronous message loss remain open.
  • Message Payload Size: The benchmark evaluated 25 KB compressed semantic segmentations. Future work will investigate high-bandwidth payloads such as dense 3D metric-semantic submaps (several megabytes).
  • Long-Horizon History: RAG currently focuses on coordinating non-overlapping trajectories for the immediate look-ahead horizon; extending the framework to maintain long-term global map histories and network connectivity over time is left for future exploration.

Summary updated

Abstract

We provide a distributed coordination paradigm that enables scalable and near-optimal joint motion planning among multiple robots. Our coordination paradigm contrasts with current paradigms that are either near-optimal but impractical for replanning times or real-time but offer no near-optimality guarantees. We are motivated by the future of collaborative mobile autonomy, where distributed teams of robots will coordinate via vehicle-to-vehicle (v2v) communication to execute information-heavy tasks like mapping, surveillance, and target tracking. To enable rapid distributed coordination, we must curtail the explosion of information-sharing across the network, thus limiting robot coordination. However, this can lead to suboptimal plans, causing overlapping trajectories instead of complementary ones. We make theoretical and algorithmic contributions to balance the trade-off between decision speed and optimality. We introduce tools for distributed submodular optimization, a diminishing returns property in information-gathering tasks. Theoretically, we analyze how local network topology affects near-optimality at the global level. Algorithmically, we provide a communication- and computation-efficient coordination algorithm for agents to balance the trade-off. Our algorithm is up to two orders faster than competitive near-optimal algorithms. In simulations of surveillance tasks with up to 45 robots, it enables real-time planning at the order of 1 Hz with superior coverage performance. To enable the simulations, we provide a high-fidelity simulator that extends AirSim by integrating a collaborative autonomy pipeline and simulating v2v communication delays.
BibTeX
@article{xu2025communication,
  author = {Zirui Xu and Sandilya Sai Garimella and Vasileios Tzoumas},
  title = {{Communication-and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks}},
  journal = {IEEE Trans. Robotics},
  year = {2025},
  doi = {10.1109/tro.2025.3567540},
}
Figure