Submodular Optimization for Coupled Task Allocation and Intermittent Deployment Problems
Submodular Optimization for Coupled Task Allocation and Intermittent Deployment Problems
复制标题
耦合任务分配和间歇部署问题的子模块优化
DOI：
10.1109/lra.2019.2925301
复制
发表时间：
2019
影响因子：
5.2
通讯作者：
Ryan K. Williams
中科院分区：
文献类型：
--
作者：
Jun Liu;Ryan K. Williams
在这封信中，我们展示了一个配方优化耦合次模最大化问题可证明的次最优性界。在机器人应用中，优化问题相互耦合，因此无法独立解决，这是很常见的。具体来说，我们认为两个问题耦合，如果第一个问题的结果影响的第二个问题，在一个较长的时间尺度上运作的解决方案。例如，在我们的激励问题的环境监测，我们认为，多机器人任务分配将潜在地影响环境动态，从而影响未来的监测质量，在这里建模为多机器人间歇性部署问题。解决这种类型的耦合问题的一般理论方法是通过这个激励的例子证明。具体来说，我们提出了一种方法来解决耦合问题建模的子模集函数与拟阵约束。提出了一个求解这类问题的贪婪算法，沿着了次优性保证。最后，通过Monte Carlo模拟，实际的最优性比显示，该算法可以产生高效率的近优解。
In this letter, we demonstrate a formulation for optimizing coupled submodular maximization problems with provable sub-optimality bounds. In robotics applications, it is quite common that optimization problems are coupled with one another and therefore cannot be solved independently. Specifically, we consider two problems coupled if the outcome of the first problem affects the solution of a second problem that operates over a longer time scale. For example, in our motivating problem of environmental monitoring, we posit that multi-robot task allocation will potentially impact environmental dynamics and thus influence the quality of future monitoring, here modeled as a multi-robot intermittent deployment problem. The general theoretical approach for solving this type of coupled problem is demonstrated through this motivating example. Specifically, we propose a method for solving coupled problems modeled by submodular set functions with matroid constraints. A greedy algorithm for solving this class of problem is presented, along with sub-optimality guarantees. Finally, practical optimality ratios are shown through Monte Carlo simulations to demonstrate that the proposed algorithm can generate near-optimal solutions with high efficiency.