Search

We consider a scenario where a system experiences a disruption, and the states (representing health values) of its components continue to reduce over time, unless they are acted upon by a controller. Given this dynamical setting, we consider the problem of finding an optimal control (or switching) sequence to maximize the sum of the weights of the components, whose states are brought back to the maximum value. We first provide several characteristics of the optimal policy for the general (fully heterogeneous) version of this problem. We then show that under certain conditions on the rates of repair and deterioration, we can explicitly characterize the optimal control policy as a function of the states. When the deterioration rate (when not being repaired) is larger than or equal to the repair rate, and the deterioration and repair rates as well as the weights are homogeneous across all the components, we show that the policy that targets the component with the largest state value at each time step is optimal under certain conditions. On the other hand, if the repair rates are sufficiently larger than the deterioration rates, the optimal control policy is to target the component whose state minus the deterioration rate is least in a particular subset of components at each time step. [ABSTRACT FROM AUTHOR]

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]

We investigate the vulnerabilities of consensus-based distributed optimization protocols to nodes that deviate from the prescribed update rule (e.g., due to failures or adversarial attacks). We first characterize certain fundamental limitations on the performance of any distributed optimization algorithm in the presence of adversaries. We then propose a secure distributed optimization algorithm that guarantees that the nonadversarial nodes converge to the convex hull of the minimizers of their local functions under the certain conditions on the graph topology, regardless of the actions of a certain number of the adversarial nodes. In particular, we provide sufficient conditions on the graph topology to tolerate a bounded number of adversaries in the neighborhood of every nonadversarial node, and necessary and sufficient conditions to tolerate a globally bounded number of adversaries. For situations, where there are up to $F$ adversaries in the neighborhood of every node, we use the concept of maximal $F$ -local sets of graphs to provide lower bounds on the distance-to-optimality of achievable solutions under any algorithm. We show that finding the size of such sets is NP-hard. [ABSTRACT FROM AUTHOR]