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 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 paper 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.