Infinite-Horizon Optimal Control of Switched Boolean Control Networks With Average Cost: An Efficient Graph-Theoretical Approach

This study investigates the infinite-horizon optimal control (IHOC) problem for switched Boolean control networks with an average cost criterion. A primary challenge of this problem is the prohibitively high computational cost when dealing with large-scale networks. We attempt to develop a more efficient approach from a novel graph-theoretical perspective. First, a weighted directed graph structure called the optimal state transition graph (OSTG) is established, whose edges encode the optimal action for each admissible state transition between states reachable from a given initial state subject to various constraints. Then, we reduce the IHOC problem into a minimum-mean cycle (MMC) problem in the OSTG. Finally, we develop an algorithm that can quickly find a particular MMC by resorting to Karp's algorithm in the graph theory and construct an optimal switching control law based on state feedback. The time complexity analysis shows that our algorithm, albeit still running in exponential time, can outperform all the existing methods in terms of time efficiency. A 16-state-3-input signaling network in leukemia is used as a benchmark to test its effectiveness. Results show that the proposed graph-theoretical approach is much more computationally efficient and can reduce the running time dramatically: it runs hundreds or even thousands of times faster than the existing methods. The Python implementation of the algorithm is available at https://github.com/ShuhuaGao/sbcn_mmc.