Minimum-Time Control of Boolean Control Networks: A Fast Graphical Approach

This brief presents an efficient approach for minimum-time control of Boolean control networks (BCNs) based on graph theory. All three cases of the problem are considered depending on whether the initial state, desired state, or both are fixed. To facilitate the use of graph-theoretical tools, the dynamics of a BCN is first characterized by its state transition graph (STG). Subsequently, the equivalence between a time-optimal state trajectory and a shortest path in the STG is established. We then develop efficient algorithms based on the breath-first search of the STG to quickly identify the reachable set, count the distance of each reachable vertex, and collect time-optimal controls for each state. Finally, all state-feedback gain matrices for minimum-time control are characterized. Our approach is featured by its high versatility and superior time efficiency. The proposed graphical framework handles all three cases uniformly and can be easily extended to more variants with minor or even no algorithm modifications. This is in contrast to existing methods that only target specific cases. The time complexity of our approach is considerably lower than that of existing methods, contributing to higher scalability for relatively large networks.