Given a linear dynamical system affected by noise, we consider the problem of optimally placing sensors (at designtime) subject to certain budget constraints to minimize the trace of the steadystate error covariance of the Kalman filter. Previous work has shown that this problem is NPhard 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 polynomialtime) to place the sensors over the network. However, we show that when the network has multiple inputs, the optimal sensor placement problem becomes NPhard.
On the Complexity and Approximability of Optimal Sensor Selection for Kalman Filtering
Given a linear dynamical system, we consider the problem of selecting (at designtime) 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 NPhard for certain classes of systems and sensor costs; in this paper, we show that the problem remains NPhard 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 constantfactor (polynomialtime) approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constantfactor 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 designtime sensor selection for Kalman filtering.
 Award ID(s):
 1635014
 Publication Date:
 NSFPAR ID:
 10068255
 Journal Name:
 2018 Annual American Control Conference (ACC)
 Page Range or eLocationID:
 5049 to 5054
 Sponsoring Org:
 National Science Foundation
More Like this


We study the Aoptimal 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 kmeans clustering [9], and matrix approximation [13, 14, 5]. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for Aoptimal 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 Aoptimal design problem can be reduced to approximate independence properties of the measure µ. We appeal to hardcore distributions as candidate distributions µ that allow usmore »

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 finegrained 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 Finegrained Trajectory Plan for multiUAVs (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 NPhard. To solve the FTP problem, we first study a special case of the FTP problemmore »

Waiting at the right location at the right time can be critically important in certain variants of timedependent shortest path problems. We investigate the computational complexity of timedependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomialtime hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers timedependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the fieldmore »

Supply energy to batterypowered 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 NPhard, 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