Journal article
Risk-Aware Submodular Optimization for Multirobot Coordination
IEEE transactions on robotics, v 38(5), pp 3064-3084
Oct 2022
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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 the CVaR has recently been used in the optimization of linear cost functions in robotics, we take the first step toward 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 matroid 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, i.e., 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. We also study the problem of adaptive risk-aware submodular maximization. We design a heuristic solution that triggers the replanning only when certain conditions are satisfied, to eliminate unnecessary planning. In particular, for the online mobility-on-demand study, we propose an adaptive triggering assignment algorithm that triggers a new assignment only when it can potentially reduce the waiting time at demand locations. We verify the performance of the proposed algorithms through simulations.
Metrics
Details
- Title
- Risk-Aware Submodular Optimization for Multirobot Coordination
- Creators
- Lifeng Zhou - University of PennsylvaniaPratap Tokekar - University of Maryland, College Park
- Publication Details
- IEEE transactions on robotics, v 38(5), pp 3064-3084
- Publisher
- IEEE
- Number of pages
- 21
- Grant note
- IIS-1637915 / National Science Foundation (10.13039/501100008982) N00014-18-1-2829 / Office of Naval Research (10.13039/100000006)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000779825100001
- Scopus ID
- 2-s2.0-85127799058
- Other Identifier
- 991021945763904721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Robotics