Supermodular mean squared error minimization for sensor scheduling in optimal Kalman Filtering

摘要

We consider the problem of scheduling a set of sensors to observe the state of a discrete-time linear system subject to a limited energy budget. Our goal is to devise a sensor schedule that minimizes the mean squared error (MSE) of an optimal estimator (i.e., the Kalman Filter). Both the minimum-MSE and the minimum-cardinality optimal sensor scheduling problems are inherently combinatorial, and computationally intractable. We remedy the combinatorial complexity by using a greedy heuristic; the greedy heuristic is guaranteed to return near-optimal solutions when minimizing supermodular objectives. While it is known that the MSE is not supermodular (with counterexamples available in literature), we provide conditions on the prior information matrix and on the observation matrix under which supermodularity holds. More specifically, we require the prior information matrix to be a strictly-diagonally-dominant M-matrix (plus an extra technical requirement on its inverse). Empirical results confirm that random M-matrices lead to supermodular problems, while this is not the case for generic prior information matrices. M-matrices naturally arise in estimation problems over networks and we provide a practical application of our findings to an energy-constrained multi robot localization problem.