Joint Sensor and Actuator Placement for Infinite-Horizon LQG Control

We consider the problem of sensor and actuator (SaA) placement to minimize an infinite-horizon linear quadratic Gaussian (LQG) cost for a discrete-time Gauss-Markov system. Due to financial, topology, and bandwidth limitations, only a subset of SaAs can be selected for placement. Different from existing literature, which successively iterates partial selection to reach a suboptimal solution, this article focuses on a joint placement and encounters fundamental difficulty in the sense that joint SaA placement introduces a term in the LQG cost that is difficult to be convexified. A branch-and-bound algorithm is introduced to search for solutions to an approximate problem obtained by relaxing the Boolean constraints. By deriving a compact search space where any optimal solution belongs to or resides, we derive lower and upper bounds to the optimal solution in each subregion of the search space, and subsequently refine the search space. A suboptimal solution to the original problem is obtained from integer rounding and the optimality gap is further analyzed. Numerical examples are provided to illustrate the effectiveness of the proposed algorithm. This algorithm has significant reduction of iteration numbers compared with the brute-force enumeration especially when the number of states is not large but the number of placement choices is large. In addition, an improvement of LQG cost is obtained compared with the successively iterating partial selection methods, a canonical algorithm for SaA placement in the literature.

Automated summary

This article addresses the problem of sensor and actuator placement and proposes a branch-and-bound algorithm to search for solutions. By deriving lower and upper bounds in the search space, a suboptimal solution is obtained and the optimality gap is analyzed. Numerical examples demonstrate the effectiveness of the algorithm, showing significant reduction in iteration numbers and improvement in LQG cost compared to the canonical algorithm.