Supermodular batch state estimation in optimal sensor scheduling

Prince Singh, Sze Yong, Emilio Frazzoli

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)292-297
Number of pages6
JournalIEEE Control Systems Letters
Issue number2
StatePublished - Oct 2017


  • Approximation algorithms
  • Batch state estimation
  • Large-scale systems
  • Optimal scheduling
  • Sensor networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Control and Optimization


Dive into the research topics of 'Supermodular batch state estimation in optimal sensor scheduling'. Together they form a unique fingerprint.

Cite this