# Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks arXiv: https://arxiv.org/abs/2407.10382 ยท HTML: https://mlsanity.com/paper/2407.10382/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Builds on 30 of its 70 references that are in the map. - First posted on arXiv 15 Jul 2024. ## Builds on (most cited first, 30 of 30) - [AirSim: High-Fidelity Visual and Physical Simulation for Autonomous Vehicles](https://mlsanity.com/paper/1705.05065/) (2017) - [Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems](https://mlsanity.com/paper/2106.14386/) (2021) - [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016) - [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022) - [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013) - [A Comprehensive Overview on 5G-and-Beyond Networks with UAVs: From Communications to Sensing and Intelligence](https://mlsanity.com/paper/2010.09317/) (2020) - [Efficient Informative Sensing using Multiple Robots](https://mlsanity.com/paper/1401.3462/) (2014) - [Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions](https://mlsanity.com/paper/1311.2110/) (2013) - [RACER: Rapid Collaborative Exploration with a Decentralized Multi-UAV System](https://mlsanity.com/paper/2209.08533/) (2022) - [SlideSLAM: Sparse, Lightweight, Decentralized Metric-Semantic SLAM for Multi-Robot Navigation](https://mlsanity.com/paper/2406.17249/) (2024) - [Distributed Submodular Maximization with Limited Information](https://mlsanity.com/paper/1706.04082/) (2017) - [Optimal Algorithms for Submodular Maximization with Distributed Constraints](https://mlsanity.com/paper/1909.13676/) (2019) - [Multi-Sensor Next-Best-View Planning as Matroid-Constrained Submodular Maximization](https://mlsanity.com/paper/2007.02084/) (2020) - [Resilient Active Information Acquisition with Teams of Robots](https://mlsanity.com/paper/2103.02733/) (2021) - [Distributed Strategy Selection: A Submodular Set Function Maximization Approach](https://mlsanity.com/paper/2107.14371/) (2021) - [Distributed Resilient Submodular Action Selection in Adversarial Environments](https://mlsanity.com/paper/2105.07305/) (2021) - [The Impact of Information in Greedy Submodular Maximization](https://mlsanity.com/paper/1807.10639/) (2018) - [Execution Order Matters in Greedy Algorithms with Limited Information](https://mlsanity.com/paper/2111.09154/) (2021) - [Scalable Distributed Planning for Multi-Robot, Multi-Target Tracking](https://mlsanity.com/paper/2107.08550/) (2021) - [Meeting-Merging-Mission: A Multi-robot Coordinate Framework for Large-Scale Communication-Limited Exploration](https://mlsanity.com/paper/2109.07764/) (2021) - [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022) - [Jacobi-Style Iteration for Distributed Submodular Maximization](https://mlsanity.com/paper/2010.14082/) (2020) - [ROS-NetSim: A Framework for the Integration of Robotic and Network Simulators](https://mlsanity.com/paper/2101.10113/) (2021) - [Submodular Maximization with Limited Function Access](https://mlsanity.com/paper/2201.00724/) (2022) - [Energy-Aware, Collision-Free Information Gathering for Heterogeneous Robot Teams](https://mlsanity.com/paper/2208.00262/) (2022) - [FlyNetSim: An Open Source Synchronized UAV Network Simulator based on ns-3 and Ardupilot](https://mlsanity.com/paper/1808.04967/) (2018) - [Actuator Placement for Optimizing Network Performance under Controllability Constraints](https://mlsanity.com/paper/1903.08120/) (2019) - [BotNet: A Simulator for Studying the Effects of Accurate Communication Models on Multi-agent and Swarm Control](https://mlsanity.com/paper/2108.13606/) (2021) - [Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution](https://mlsanity.com/paper/2210.09868/) (2022) - [Multi-Robot Planning for Filming Groups of Moving Actors Leveraging Submodularity and Pixel Density](https://mlsanity.com/paper/2404.03103/) (2024) ## Built on by (most cited first, 2 of 2) - [HERCULES: An Open-Source Simulation Framework for Heterogeneous Multi-Robot SLAM, Collaborative Perception, and Exploration](https://mlsanity.com/paper/2606.22756/) (2026) - [Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach](https://mlsanity.com/paper/2603.27803/) (2026) ## Abstract (arXiv) We provide a communication- and computation-efficient method for distributed submodular optimization in robot mesh networks. Submodularity is a property of diminishing returns that arises in active information gathering such as mapping, surveillance, and target tracking. Our method, Resource-Aware distributed Greedy (RAG), introduces a new distributed optimization paradigm that enables scalable and near-optimal action coordination. To this end, RAG requires each robot to make decisions based only on information received from and about their neighbors. In contrast, the current paradigms allow the relay of information about all robots across the network. As a result, RAG's decision-time scales linearly with the network size, while state-of-the-art near-optimal submodular optimization algorithms scale cubically. We also characterize how the designed mesh-network topology affects RAG's approximation performance. Our analysis implies that sparser networks favor scalability without proportionally compromising approximation performance: while RAG's decision time scales linearly with network size, the gain in approximation performance scales sublinearly. We demonstrate RAG's performance in simulated scenarios of area detection with up to 45 robots, simulating realistic robot-to-robot (r2r) communication speeds such as the 0.25 Mbps speed of the Digi XBee 3 Zigbee 3.0. In the simulations, RAG enables real-time planning, up to three orders of magnitude faster than competitive near-optimal algorithms, while also achieving superior mean coverage performance. To enable the simulations, we extend the high-fidelity and photo-realistic simulator AirSim by integrating a scalable collaborative autonomy pipeline to tens of robots and simulating r2r communication delays. Our code is available at https://github.com/UM-iRaL/Resource-Aware-Coordination-AirSim.