非線形センサの確率的推定のためのスケジューリング
Scheduling Nonlinear Sensors for Stochastic Process Estimation
多数のセンサから少数を選んで確率過程の状態を推定する問題に対し、非線形測定でも適用でき、計画期間に線形な時間計算量で最適の1/2近似を達成するアルゴリズムを提案した。
著者: Vasileios Tzoumas, Nikolay A. Atanasov, Ali Jadbabaie, George J. Pappas
分類: eess.SY, cs.RO, cs.SY, math.OC
原文アブストラクト
In this paper, we focus on activating only a few sensors, among many available, to estimate the state of a stochastic process of interest. This problem is important in applications such as target tracking and simultaneous localization and mapping (SLAM). It is challenging since it involves stochastic systems whose evolution is largely unknown, sensors with nonlinear measurements, and limited operational resources that constrain the number of active sensors at each measurement step. We provide an algorithm applicable to general stochastic processes and nonlinear measurements whose time complexity is linear in the planning horizon and whose performance is a multiplicative factor 1/2 away from the optimal performance. This is notable because the algorithm offers a significant computational advantage over the polynomial-time algorithm that achieves the best approximation factor 1/e. In addition, for important classes of Gaussian processes and nonlinear measurements corrupted with Gaussian noise, our algorithm enjoys the same time complexity as even the state-of-the-art algorithms for linear systems and measurements. We achieve our results by proving two properties for the entropy of the batch state vector conditioned on the measurements: a) it is supermodular in the choice of the sensors; b) it has a sparsity pattern (involves block tri-diagonal matrices) that facilitates its evaluation at each sensor set.
関連論文
- バッチ状態推定のための準最適センサスケジューリング:計算量・アルゴリズム・限界センサスケジューリング
- マルチステップセンサスケジューリングのための最適プルーニングセンサスケジューリング
