Search

Given a linear dynamical system affected by stochastic noise, we consider the problem of selecting an optimal set of sensors (at design time) to minimize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter, subject to certain selection budget constraints. We show the fundamental result that there is no polynomial-time constant-factor 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 (or supermodularity) 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. We then study the problem of attacking (i.e., removing) a set of installed sensors, under predefined attack budget constraints, to maximize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter. Again, we show that there is no polynomial-time constant-factor approximation algorithm for this problem and show specifically that greedy algorithms can perform arbitrarily poorly. [ABSTRACT FROM AUTHOR]

This article addresses the problem of seeking a common fixed point for a finite collection of nonexpansive operators over time-varying multi-agent networks in real Hilbert spaces. Each operator is assumed to be only privately and approximately known to each individual agent, and all agents need to cooperate to solve this problem by local communications over time-varying networks. To handle this problem, inspired by the centralized inexact Krasnoselski –Mann iteration, we propose a distributed algorithm, called distributed inexact averaged operator algorithm (DIO). It is shown that the DIO can converge weakly to a common fixed point of the family of nonexpansive operators. Moreover, under the assumption that all operators and their own fixed point sets are (boundedly) linearly regular, it is proved that the distributed averaged operator algorithm converges with a rate O(γlog16(4k)) for some constant γ ∈ (0,1), where k is the iteration number. To reduce computational complexity, a scenario, where only a random part of coordinates of each operator is computed at each iteration, is further considered. In this case, a corresponding algorithm, named distributed block-coordinate inexact averaged operator algorithm, is developed. The algorithm is proved to be weakly convergent to a common fixed point of the group of considered operators almost surely, and, with the extra assumption of (bounded) linear regularity, the distributed block-coordinate averaged operator algorithm is convergent in the mean square sense with a rate O(ηlog4(4k)) for some constant η ∈ (0,1). Furthermore, it is shown that the same convergence rates can still be guaranteed under a more relaxed (bounded) power regularity condition. A couple of examples are finally presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We investigate a linear-quadratic-Gaussian (LQG) control and sensing codesign problem, where one jointly designs sensing and control policies. We focus on the realistic case where the sensing design is selected among a finite set of available sensors, where each sensor is associated with a different cost (e.g., power consumption). We consider two dual problem instances: sensing-constrained LQG control, where one maximizes a control performance subject to a sensor cost budget, and minimum-sensing LQG control, where one minimizes a sensor cost subject to performance constraints. We prove that no polynomial time algorithm guarantees across all problem instances a constant approximation factor from the optimal. Nonetheless, we present the first polynomial time algorithms with per-instance suboptimality guarantees. To this end, we leverage a separation principle, which partially decouples the design of sensing and control. Then, we frame LQG codesign as the optimization of approximately supermodular set functions; we develop novel algorithms to solve the problems; and we prove original results on the performance of the algorithms and establish connections between their suboptimality and control-theoretic quantities. We conclude the article by discussing two applications, namely, sensing-constrained formation control and resource-constrained robot navigation. [ABSTRACT FROM AUTHOR]

With the development of large-scale sensor networks, there is an increasing interest for high dimensional distributed decision fusion problem in statistical decision, machine learning, control theory, etc. In this article, we investigate the optimal sensor quantized rules of the distributed decision under a given fusion rule for conditionally dependent and high dimensional sensor observations. We provide a Monte Carlo importance sampling method to reduce the computational complexity of the distributed decision fusion. For the K-out-of-L rule, we derive a group of analytic sensor rules based on the necessary and sufficient condition of the optimal sensor rules. In term of efficiency, it is significantly better than the traditional iterative search algorithms, such as the Riemann sum approximation iteration algorithm. The analytic solution is also a general result since it does not rely on the specific K value of the K-out-of-L rule, the specific conditional probability density function and the dimension of sensor observations. Thus, it can be applied to multisensor decision fusion problems with high dimensional dependent sensor observations. For the general fusion rules rather than the K-out-of-L rule, the Monte Carlo Gauss–Seidel algorithm is also provided. The numerical examples demonstrate the effectiveness of the analytic solution and the Monte Carlo Gauss–Seidel algorithm. [ABSTRACT FROM AUTHOR]

In this note, we consider the problem of choosing, which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time. [ABSTRACT FROM AUTHOR]

In this paper, the decentralized partially observable Markov decision process (Dec-POMDP) systems with discrete state and action spaces are studied from a gradient point of view. Dec-POMDPs have recently emerged as a promising approach to optimizing multiagent decision making in the partially observable stochastic environment. However, the decentralized nature of the Dec-POMDP framework results in a lack of shared belief state, which makes the decision maker impossible to estimate the system state based on local information. In contrast to the belief-based policy, this paper focuses on optimizing the decentralized observation-based policy, which is easily to be applied and does not have the sharing problem. By analyzing the gradient of the objective function, we have developed a centralized stochastic gradient policy iteration algorithm to find the optimal policy on the basis of gradient estimates from a single sample path. This algorithm does not need any specific assumption and can be applied to most practical Dec-POMDP problems. One numerical example is provided to demonstrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

We present an on-line sensor selection strategy (SSS) for the Sequential Probability Ratio Test (SPRT) with multiple sensors. Each sensor incurs an associated observation cost. We aim to design an SSS, in which the sensor selection may depend causally on the measurement values, that minimizes the expected total observation cost. In general, the optimal SSS can be obtained by solving a dynamic program; however, the problem is computationally quite demanding. We propose a computationally efficient algorithm in which we partition the state space into three regions and solve for the SSS in each region. The computational complexity of the proposed algorithm is linear in the number of sensors and numerical results show that it can well approximate the optimal SSS. [ABSTRACT FROM PUBLISHER]

The problem of designing a switching and control policy for regulating the state of a switched linear system to zero while minimizing a quadratic cost appears in numerous applications. However, obtaining the optimal policy is in general computationally intractable. Here, we propose a class of suboptimal policies that exploit information, in terms of upper or lower bounds, on the optimal cost. We analyze the performance of these novel policies, obtaining new bounds on the optimal cost which are tighter than the initial ones. The usefulness of these policies and performance bounds is illustrated in the context of resource-aware control. [ABSTRACT FROM AUTHOR]

This technical note presents a method for the identification of Hammerstein Output Error (HOE) models corrupted by bounded noise. The method is based on an iterative scheme using two Optimal Bounding Ellipsoid (OBE) type algorithms. The proposed approach allows the joint estimation of the linear part and of the nonlinear part with a low computational burden. A numerical example is given so as to show the efficiency of the method. [ABSTRACT FROM PUBLISHER]

This paper deals with the update step of Gaussian MAP filtering. In this framework, we seek a Gaussian approximation to the posterior probability density function (PDF) whose mean is given by the maximum a posteriori (MAP) estimator. We propose two novel optimization algorithms which are quite suitable for finding the MAP estimate although they can also be used to solve general optimization problems. These are based on the design of a sequence of PDFs that become increasingly concentrated around the MAP estimate. The resulting algorithms are referred to as Kalman optimization (KO) methods. We also provide the important relations between these KO methods and their conventional optimization algorithms (COAs) counterparts, i.e., Newton's and Levenberg-Marquardt algorithms. Our simulations indicate that KO methods are more robust than their COA equivalents. [ABSTRACT FROM AUTHOR]

We apply diffusion strategies to develop a fully-distributed cooperative reinforcement learning algorithm in which agents in a network communicate only with their immediate neighbors to improve predictions about their environment. The algorithm can also be applied to off-policy learning, meaning that the agents can predict the response to a behavior different from the actual policies they are following. The proposed distributed strategy is efficient, with linear complexity in both computation time and memory footprint. We provide a mean-square-error performance analysis and establish convergence under constant step-size updates, which endow the network with continuous learning capabilities. The results show a clear gain from cooperation: when the individual agents can estimate the solution, cooperation increases stability and reduces bias and variance of the prediction error; but, more importantly, the network is able to approach the optimal solution even when none of the individual agents can (e.g., when the individual behavior policies restrict each agent to sample a small portion of the state space). [ABSTRACT FROM AUTHOR]

The classical approach to system identification is based on stochastic assumptions about the measurement error, and provides estimates that have random nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds, and establishes guaranteed estimates, thus being in principle better suited for the use in control design. However, a main limitation of such deterministic bounds lies in their potential conservatism, thus leading to estimates of restricted use. In this paper, we propose a rapprochement between the stochastic and worst-case system identification viewpoints, which is based on the probabilistic setting of information-based complexity. The main idea in this line of research is to “discard” sets of measure at most $\epsilon$, where $\epsilon$ is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic “risk.” In the case of uniformly distributed noise, we derive new computational results, and in particular we compute a trade-off curve, called violation function, which shows how the radius of information decreases as a function of the accuracy. To this end, we construct randomized and deterministic algorithms which provide approximations of this function. We report extensive simulations showing numerical comparisons between the stochastic, worst-case and probabilistic approaches, thus demonstrating the efficacy of the methods proposed in this paper. [ABSTRACT FROM AUTHOR]