# Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making

arXiv: https://arxiv.org/abs/2204.07520 · HTML: https://mlsanity.com/paper/2204.07520/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 15 Apr 2022.

## Builds on (most cited first, 17 of 17)

- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Submodular Trajectory Optimization for Aerial 3D Scanning](https://mlsanity.com/paper/1705.00703/) (2017)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions](https://mlsanity.com/paper/1311.2110/) (2013)
- [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)
- [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)
- [Jacobi-Style Iteration for Distributed Submodular Maximization](https://mlsanity.com/paper/2010.14082/) (2020)
- [A Resource-Aware Approach to Collaborative Loop Closure Detection with Provable Performance Guarantees](https://mlsanity.com/paper/1907.04904/) (2019)
- [Robust and Adaptive Sequential Submodular Optimization](https://mlsanity.com/paper/1909.11783/) (2019)
- [Submodular Maximization with Limited Function Access](https://mlsanity.com/paper/2201.00724/) (2022)
- [Higher order monotonicity and submodularity of influence in social networks: from local to global](https://mlsanity.com/paper/1803.00666/) (2018)

## Built on by (most cited first, 6 of 6)

- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (2024)
- [When Should a Robot Think? Resource-Aware Reasoning via Reinforcement Learning for Embodied Robotic Decision-Making](https://mlsanity.com/paper/2603.16673/) (2026)
- [Leveraging Untrustworthy Commands for Multi-Robot Coordination in Unpredictable Environments: A Bandit Submodular Maximization Approach](https://mlsanity.com/paper/2309.16161/) (2023)
- [Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design](https://mlsanity.com/paper/2409.01411/) (2024)

## Abstract (arXiv)

Multi-robot decision-making is the process where multiple robots coordinate actions. In this paper, we aim for efficient and effective multi-robot decision-making despite the robots' limited on-board resources and the often resource-demanding complexity of their tasks. We introduce the first algorithm enabling the robots to choose with which few other robots to coordinate and provably balance the trade-off of centralized vs. decentralized coordination. Particularly, centralization favors globally near-optimal decision-making but at the cost of increased on-board resource requirements; whereas, decentralization favors minimal resource requirements but at a global suboptimality cost. All robots can thus afford our algorithm, irrespective of their resources. We are motivated by the future of autonomy that involves multiple robots coordinating actions to complete resource-demanding tasks, such as target tracking, area coverage, and monitoring. To provide closed-form guarantees, we focus on maximization problems involving monotone and 2nd-order submodular functions. To capture the cost of decentralization, we introduce the notion of Centralization Of Information among non-Neighbors (COIN). We validate our algorithm in simulated scenarios of image covering.