On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering
On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering
复制标题
DOI：
10.1109/tac.2020.3007383
复制
发表时间：
2020-03
影响因子：
6.8
通讯作者：
Lintao Ye;Nathaniel T. Woodford;Sandip Roy;S. Sundaram
中科院分区：
文献类型：
--
作者：
Lintao Ye;Nathaniel T. Woodford;Sandip Roy;S. Sundaram
给定一个受随机噪声影响的线性动态系统，我们考虑选择一组最佳的传感器（在设计时），以尽量减少跟踪的稳态先验或后验误差协方差的卡尔曼滤波器，受到一定的选择预算约束的问题。我们的基本结果是，没有多项式时间常数因子近似算法这个问题。这与文献中研究的其他类别的传感器选择问题形成对比，文献中通常通过利用贪婪算法和成本函数的子模块化（或超模块化）来追求恒定因子近似。在这里，我们提供了一个具体的例子表明，贪婪算法可以任意执行卡尔曼滤波的设计时传感器选择的问题。然后我们研究攻击的问题（即，在预定义的攻击预算约束下，移除）一组安装的传感器，以最大化卡尔曼滤波器的稳态先验或后验误差协方差的轨迹。再次，我们表明，没有多项式时间常数因子近似算法，这个问题，并特别表明，贪婪算法可以任意执行差。
Given a linear dynamical system affected by stochastic noise, we consider the problem of selecting an optimal set of sensors (at design time) to minimize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter, subject to certain selection budget constraints. We show the fundamental result that there is no polynomial-time constant-factor approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity (or supermodularity) of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering. We then study the problem of attacking (i.e., removing) a set of installed sensors, under predefined attack budget constraints, to maximize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter. Again, we show that there is no polynomial-time constant-factor approximation algorithm for this problem and show specifically that greedy algorithms can perform arbitrarily poorly.