skip to main content


Title: On the Complexity and Approximability of Optimal Sensor Selection for Kalman Filtering
Given a linear dynamical system, we consider the problem of selecting (at design-time) an optimal set of sensors (subject to certain budget constraints) to minimize the trace of the steady state error covariance matrix of the Kalman filter. Previous work has shown that this problem is NP-hard for certain classes of systems and sensor costs; in this paper, we show that the problem remains NP-hard even for the special case where the system is stable and all sensor costs are identical. Furthermore, we show the stronger result that there is no constant-factor (polynomial-time) approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering.  more » « less
Award ID(s):
1635014
NSF-PAR ID:
10068255
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2018 Annual American Control Conference (ACC)
Page Range / eLocation ID:
5049 to 5054
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Given a linear dynamical system affected by noise, we consider the problem of optimally placing sensors (at design-time) subject to certain budget constraints to minimize the trace of the steady-state error covariance of the Kalman filter. Previous work has shown that this problem is NP-hard in general. In this paper, we impose additional structure by considering systems whose dynamics are given by a stochastic matrix corresponding to an underlying consensus network. In the case when there is a single input at one of the nodes in a tree network, we provide an optimal strategy (computed in polynomial-time) to place the sensors over the network. However, we show that when the network has multiple inputs, the optimal sensor placement problem becomes NP-hard. 
    more » « less
  2. We study the A-optimal design problem where we are given vectors υ1, …, υn ∊ ℝd, an integer k ≥ d, and the goal is to select a set S of k vectors that minimizes the trace of (∑i∊Svivi⊺)−1. Traditionally, the problem is an instance of optimal design of experiments in statistics [35] where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick k of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks [22], sparse least squares regression [8], feature selection for k-means clustering [9], and matrix approximation [13, 14, 5]. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for A-optimal design. Given a matrix, proportional volume sampling involves picking a set of columns S of size k with probability proportional to µ(S) times det(∑i∊Svivi⊺) for some measure µ. Our main result is to show the approximability of the A-optimal design problem can be reduced to approximate independence properties of the measure µ. We appeal to hardcore distributions as candidate distributions µ that allow us to obtain improved approximation algorithms for the A-optimal design. Our results include a d-approximation when k = d, an (1 + ∊)-approximation when and -approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for k ≤ d and obtain a k-approximation. We also show that the proportional volume sampling algorithm gives approximation algorithms for other optimal design objectives (such as D-optimal design [36] and generalized ratio objective [27]) matching or improving previous best known results. Interestingly, we show that a similar guarantee cannot be obtained for the E-optimal design problem. We also show that the A-optimal design problem is NP-hard to approximate within a fixed constant when k = d. 
    more » « less
  3. Abstract

    The Eisenberg and Noe (EN) model has been widely adopted in the systemic risk management for financial networks. In this paper, we propose a unified EN (U‐EN) model, which incorporates both liquidation and bankruptcy costs. We show that the U‐EN model is polynomial‐time solvable and develop an efficient greedy algorithm to solve it. Then we consider identifying the optimal bailout strategy based on stress testing background and propose a binary EN model with bailout budget constraint (B‐EN‐B). The B‐EN‐B model is shown to be NP‐hard. We present analysis on the parameter selection and design some preprocessing procedures correspondingly. A sequential coefficient strengthening algorithm is designed to solve the B‐EN‐B model. Global convergence of the algorithm is established. Moreover, we show that the systemic risk level obtained from the B‐EN‐B model can be used as a precaution for the social planner. Experiments based on both simulated data and data from the Chinese listed banks' network are reported to demonstrate the efficiency of the proposed algorithms.

     
    more » « less
  4. null (Ed.)
    Supply energy to battery-powered sensor devices by deploying wireless chargers is a promising way to prolong the operation time of wireless sensor networks, and has attracted much attention recently. Existing works focus on maximizing the total received charging power of the network. However, this may face the unbalanced energy allocation problem, which is not beneficial to prolong the operation time of wireless sensor networks. In this paper, we consider the individual energy requirement of each sensor node, and study the problem of minimum charger placement. That is, we focus on finding a strategy for placing wireless chargers from a given candidate location set, such that each sensor node’s energy requirement can be met, meanwhile the total number of used chargers can be minimized. We show that the problem to be solved is NP-hard, and present two approximation algorithms which are based on the greedy scheme and relax rounding scheme, respectively. We prove that both of the two algorithms have performance guarantees. Finally, we validate the performance of our algorithms by performing extensive numerical simulations. Simulation results show the effectiveness of our proposed algorithms 
    more » « less
  5. null (Ed.)
    The increasing availability of autonomous smallsize Unmanned Aerial Vehicles (UAVs) has provided a promising way for data gathering from Wireless Sensor Networks (WSNs) with the advantages of high mobility, flexibility, and good speed. However, few works considered the situations that multiple UAVs are collaboratively used and the fine-grained trajectory plans of multiple UAVs are devised for collecting data from network including detailed traveling and hovering plans of them in the continuous space. In this paper, we investigate the problem of the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which m UAVs are used to collect data from a given WSN, where m ≥ 1. The problem entails not only to find the flight paths of multiple UAVs but also to design the detailed hovering and traveling plans on their paths for efficient data gathering from WSN. The objective of the problem is to minimize the maximum flight time of UAVs such that all sensory data of WSN is collected by the UAVs and transported to the base station. We first propose a mathematical model of the FTP problem and prove that the problem is NP-hard. To solve the FTP problem, we first study a special case of the FTP problem when m = 1, called FTP with Single UAV (FTPS) problem. Then we propose a constantfactor approximation algorithm for the FTPS problem. Based on the FTPS problem, an approximation algorithm for the general version of the FTP problem when m > 1 is further proposed, which can guarantee a constant factor of the optimal solution. Afterwards, the proposed algorithms are verified by extensive simulations. 
    more » « less