An Approximation Algorithm for Risk-averse Submodular Optimization
An Approximation Algorithm for Risk-averse Submodular Optimization
复制标题
风险规避子模优化的近似算法
DOI：
10.1007/978-3-030-44051-0_9
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Pratap Tokekar
中科院分区：
文献类型：
--
作者：
Lifeng Zhou;Pratap Tokekar
研究了不确定条件下组合决策中引入风险的问题。我们使用金融分析中常用的风险度量条件风险值(CVaR)，建立了一个选择集合的离散子模块最大化问题。虽然CVaR最近已被用于机器人中线性成本函数的优化，但我们将其扩展到离散子模块优化的第一阶段，并提供了几个积极的结果。具体地说，我们提出了序贯贪婪算法，它为寻找拟阵约束下CVaR代价函数的极大值提供了近似保证。近似保证表明，我们的算法所产生的解在最优解的恒定因子和依赖于最优解的附加项内。我们的分析利用了子模集合函数的曲率，并证明了算法在多项式时间内运行。这就形成了机器人学中出现的许多组合优化问题。我们使用两个这样的问题--按需移动的不确定车辆分配和环境监测失败时的传感器选择--作为案例研究，以验证该方法的有效性。
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 stages 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.