Supermodular Batch State Estimation in Optimal Sensor Scheduling
Prince Kumar Singh, Sze Zheng Yong, Emilio Frazzoli · IEEE Control Systems Letters · 2017
This letter addresses the problem of activating, at each time-step in a finite time horizon problem, a subset of available sensors to generate a “high quality” estimate of the state of a discrete-time linear system operating under limited resources. We propose a sensor schedule that minimizes the mean square estimation error of the batch state vector of the system-the batch state estimation (BSE) problem. Due to the presence of limited resources, we address the cardinality-constrained BSE problem, which is inherently combinatorial and computationally intractable when working with large-scale systems. This NP-hard complexity is overcome by employing a greedy algorithm, which returns a near-optimal sensor schedule with performance guarantees when minimizing a supermodular objective over matroids. To this end, we prove (despite the existence of counter-examples in literature) that our objective function is supermodular when the batch prior information matrix is a strictly diagonally dominant M -matrix (with a constraint on its inverse and conditions on the measurement model). Hence, we obtain a near-optimal solution to the BSE problem via a greedy algorithm. Additionally, we provide its time complexity.