Search

In this article, we investigate the problem of actuator selection for linear dynamical systems. We develop a framework to design a sparse actuator schedule for a given large-scale linear system with guaranteed performance bounds using deterministic polynomial-time and randomized approximately linear-time algorithms. First, we introduce systemic controllability metrics for linear dynamical systems that are monotone and homogeneous with respect to the controllability Gramian. We show that several popular and widely used optimization criteria in the literature belong to this class of controllability metrics. Our main result is to provide a polynomial-time actuator schedule that on average selects only a constant number of actuators at each time step, independent of the dimension, to furnish a guaranteed approximation of the controllability metrics in comparison to when all actuators are in use. Our results naturally apply to the dual problem of sensor selection, in which we provide a guaranteed approximation to the observability Gramian. We illustrate the effectiveness of our theoretical findings via several numerical simulations using benchmark examples.

We study the problem of distributed coverage control in a network of mobile agents arranged on a line. The goal is to design distributed dynamics for the agents to achieve optimal coverage positions with respect to a scalar density field that measures the relative importance of each point on the line. Unlike previous work, which implicitly assumed the agents know this density field, we only assume that each agent can access noisy samples of the field at points close to its current location. We provide a simple randomized protocol wherein every agent samples the scalar field at three nearby points at each step and which guarantees convergence to the optimal positions. We further analyze the convergence time of this protocol and show that, under suitable assumptions, the squared distance to the optimal coverage configuration decays as $O(1/t)$ with the number of iterations $t$ , where the constant scales polynomially with the number of agents $n$ . We illustrate these results with simulations.

We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness condition has a worst case running time of at least on the order of n2 on a line network of n nodes. Our results suggest that increased memory or expansion of the state space is crucial for improving the running times of distributed averaging algorithms.

We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We also describe an algorithm within this class whose convergence time is the best among currently available averaging algorithms for time-varying topologies. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, so that they can only converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels.

Motivated by questions in robust control and switched linear dynamical systems, we consider the problem checking whether all convex combinations of k matrices in Rntimesn are stable. In particular, we are interested whether there exist algorithms which can solve this problem in time polynomial in n and k. We show that if k=nd for any fixed real d > 0, then the problem is NP-hard, meaning that no polynomial-time algorithm in n exists provided that P ne NP, a widely believed conjecture in computer science. On the other hand, when k is a constant independent of n, then it is known that the problem may be solved in polynomial time in n. Using these results and the method of measurable switching rules, we prove our main statement: verifying the absolute asymptotic stability of a continuous-time switched linear system with more than nd matrices Ai isin Rntimesn satisfying 0 ges Ai + Ai T is NP-hard.