Deterministic and Randomized Actuator Scheduling With Guaranteed Performance Bounds

Jadbabaie, Ali; Olshevsky, Alex; Siami, Milad

In this paper, we investigate the problem of actuator selection for linear dynamical systems. We develop a framework to design a sparse actuator/sensor schedule for a given large-scale linear system with guaranteed performance bounds using deterministic polynomial-time and randomized approximately linear-time algorithms. We first introduce systemic controllability metrics for linear dynamical systems that are monotone, convex, 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/observability metrics in comparison to when all actuators/sensors are in use. We illustrate the effectiveness of our theoretical findings via several numerical simulations using benchmark examples.