Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems

doi:10.1016/j.automatica.2015.08.022

Return

Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems

2015-11-01

111

PRE

Syed Talha Jawaid *

Stephen L. Smith

DOI：10.1016/j.automatica.2015.08.022

Original

Original request for help

Save

Abstract

En 中文

This paper focuses on sensor scheduling for state estimation, which consists of a network of noisy sensors and a discrete-time linear system with process noise. As an energy constraint, only a subset of sensors can take a measurement at each time step. These measurements are fused into a common state estimate using a Kalman filter and the goal is to schedule the sensors to minimize the estimation error at a terminal time. A simple approach is to greedily choose sensors at each time step to minimize the estimation error at the next time step. Recent work has shown that this greedy algorithm outperforms other well known approaches. Results have been established to show that the estimation error is a submodular function of the sensor schedule; submodular functions have a diminishing returns property that ensures the greedy algorithm yields near optimal performance. As a negative result, we show that most commonly-used estimation error metrics are not, in general, submodular functions. This disproves an established result. We then provide sufficient conditions on the system for which the estimation error is a submodular function of the sensor schedule, and thus the greedy algorithm yields performance guarantees. (C) 2015 Elsevier Ltd. All rights reserved.

Keywords:

Kalman filters

Sensor networks

Multi-sensor estimation

Sensor scheduling

Greedy algorithms

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.