Near-optimal sensor scheduling for batch state estimation: Complexity, algorithms, and limits
Near-optimal sensor scheduling for batch state estimation: Complexity, algorithms, and limits
复制标题
用于批量状态估计的接近最优传感器调度：复杂性、算法和限制
DOI：
10.1109/cdc.2016.7798669
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
George Pappas
中科院分区：
文献类型：
--
作者：
Vasileios Tzoumas;A. Jadbabaie;George Pappas
本文主要研究线性系统的批状态估计问题。该问题在环境场估计、机器人导航和目标跟踪等应用中具有重要意义。其难点在于传感器之间有限的操作资源，例如共享通信带宽或电池电量，限制了每个测量步骤中可激活的传感器数量。因此，必须采用传感器调度算法。然而，当前用于批处理状态估计的传感器调度算法对系统规模和时间范围的适应能力较差。此外，目前用于卡尔曼滤波的传感器调度算法虽然具有更好的可扩展性，但对于批量状态估计误差的最小化没有提供性能保证或近似界限。在本文中，我们的主要贡献之一是提供了一种算法，它既具有批处理状态调度算法的估计精度，又具有卡尔曼滤波调度算法的低时间复杂度。特别是：1)我们的算法是近最优的：它从最优解得到一个乘因子1/2的解，这个因子接近于这个问题在多项式时间内可以实现的最佳近似因子1/e；2)我们的算法具有（多项式）时间复杂度，不仅比当前的批处理状态估计算法低；它也低于或类似于目前的卡尔曼滤波算法。我们通过证明我们的批状态估计误差度量的两个性质来实现这些结果，该度量量化了批状态向量的最小方差线性估计的平方误差：a)它在传感器的选择上是超模的；B)它有一个稀疏模式（它涉及的矩阵是块三对角线），这有利于它在每个传感器集上的评估。
In this paper, we focus on batch state estimation for linear systems. This problem is important in applications such as environmental field estimation, robotic navigation, and target tracking. Its difficulty lies on that limited operational resources among the sensors, e.g., shared communication bandwidth or battery power, constrain the number of sensors that can be active at each measurement step. As a result, sensor scheduling algorithms must be employed. Notwithstanding, current sensor scheduling algorithms for batch state estimation scale poorly with the system size and the time horizon. In addition, current sensor scheduling algorithms for Kalman filtering, although they scale better, provide no performance guarantees or approximation bounds for the minimization of the batch state estimation error. In this paper, one of our main contributions is to provide an algorithm that enjoys both the estimation accuracy of the batch state scheduling algorithms and the low time complexity of the Kalman filtering scheduling algorithms. In particular: 1) our algorithm is near-optimal: it achieves a solution up to a multiplicative factor 1/2 from the optimal solution, and this factor is close to the best approximation factor 1/e one can achieve in polynomial time for this problem; 2) our algorithm has (polynomial) time complexity that is not only lower than that of the current algorithms for batch state estimation; it is also lower than, or similar to, that of the current algorithms for Kalman filtering. We achieve these results by proving two properties for our batch state estimation error metric, which quantifies the square error of the minimum variance linear estimator of the batch state vector: a) it is supermodular in the choice of the sensors; b) it has a sparsity pattern (it involves matrices that are block tri-diagonal) that facilitates its evaluation at each sensor set.