# Risk-Aware Submodular Optimization for Multi-Robot Coordination

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2020.

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

- [Large Language Models for Multi-Robot Systems: A Survey](https://mlsanity.com/paper/2502.03814/) (2025)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysis](https://mlsanity.com/paper/2403.08955/) (2024)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Risk-aware Safe Control for Decentralized Multi-agent Systems via Dynamic Responsibility Allocation](https://mlsanity.com/paper/2305.13467/) (2023)
- [Supportive Token Revealing for Fast Diffusion Language Model Decoding](https://mlsanity.com/paper/2606.04236/) (2026)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)
- [Fine-Tuning Diffusion Language Models with Context Selection and Target Weighting](https://mlsanity.com/paper/2609.38385/) (2026)

## Abstract (arXiv)

We study the problem of incorporating risk while making combinatorial decisions under uncertainty. We formulate a discrete submodular maximization problem for selecting a set using Conditional-Value-at-Risk (CVaR), a risk metric commonly used in financial analysis. While CVaR has recently been used in optimization of linear cost functions in robotics, we take the first step towards extending this to discrete submodular optimization and provide several positive results. Specifically, we propose the Sequential Greedy Algorithm that provides an approximation guarantee on finding the maxima of the CVaR cost function under a matroidal constraint. The approximation guarantee shows that the solution produced by our algorithm is within a constant factor of the optimal and an additive term that depends on the optimal. Our analysis uses the curvature of the submodular set function, and proves that the algorithm runs in polynomial time. This formulates a number of combinatorial optimization problems that appear in robotics. We use two such problems, vehicle assignment under uncertainty for mobility-on-demand and sensor selection with failures for environmental monitoring, as case studies to demonstrate the efficacy of our formulation. In particular, for the mobility-on-demand study, we propose an online triggering assignment algorithm that triggers a new assignment only can potentially lead to reducing the waiting time at demand locations. We verify the performance of the Sequential Greedy Algorithm and the online triggering assignment algorithm through simulations.