Finite-Horizon Optimal Control of Boolean Control Networks: A Unified Graph-Theoretical Approach

This article investigates the finite-horizon optimal control (FHOC) problem of Boolean control networks (BCNs) from a graph theory perspective. We first formulate two general problems to unify various special cases studied in the literature: 1) the horizon length is a priori fixed and 2) the horizon length is unspecified but finite for given destination states. Notably, both problems can incorporate time-variant costs, which are rarely considered in existing work, and a variety of constraints. The existence of an optimal control sequence is analyzed under mild assumptions. Motivated by BCNs' finite state space and control space, we approach the two general problems intuitively and efficiently under a graph-theoretical framework. A weighted state transition graph and its time-expanded variants are developed, and the equivalence between the FHOC problem and the shortest-path (SP) problem in specific graphs is established rigorously. Two algorithms are developed to find the SP and construct the optimal control sequence for the two problems with reduced computational complexity, though technically, a classical SP algorithm in graph theory is sufficient for all problems. Compared with existing algebraic methods, our graph-theoretical approach can achieve state-of-the-art time efficiency while targeting the most general problems. Furthermore, our approach is the first one capable of solving Problem 2) with time-variant costs. Finally, a genetic network in the bacterium E. coli and a signaling network involved in human leukemia are used to validate the effectiveness of our approach. The results of two common tasks for both networks show that our approach can dramatically reduce the running time. Python implementation of our algorithms is available at GitHub https://github.com/ShuhuaGao/FHOC.