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