论文标题
通过混合整数编程在随机字段中的信息路径计划
Informative Path Planning in Random Fields via Mixed Integer Programming
论文作者
论文摘要
我们为随机字段中离散的信息路径计划问题提供了一种新的混合整数配方。目的是计算预算约束路径，同时收集线性估计的测量结果，其线性估计会导致一组有限的预测位置的最小误差。该问题已知是NP-HARD。但是，我们努力通过利用混合整数优化的进步来计算最佳解决方案。我们的方法基于扩展搜索空间，因此我们不仅优化了收集的测量子集，而且优化了所有线性估计器的类别。这使我们能够制定一个混合整数二次程序，该程序是连续变量中的凸。该配方是一般的，不仅限于该领域的任何协方差结构。在模拟中，我们证明了方法对先前分支和结合算法的有效性。
We present a new mixed integer formulation for the discrete informative path planning problem in random fields. The objective is to compute a budget constrained path while collecting measurements whose linear estimate results in minimum error over a finite set of prediction locations. The problem is known to be NP-hard. However, we strive to compute optimal solutions by leveraging advances in mixed integer optimization. Our approach is based on expanding the search space so we optimize not only over the collected measurement subset, but also over the class of all linear estimators. This allows us to formulate a mixed integer quadratic program that is convex in the continuous variables. The formulations are general and are not restricted to any covariance structure of the field. In simulations, we demonstrate the effectiveness of our approach over previous branch and bound algorithms.
