Optimal feedback linearization control of finite state machines

Abstract

Optimal control of finite state machines (FSMs) is crucial in applications where executing events incurs state‐dependent costs. This paper proposes a matrix‐theoretic approach for optimal FSM control. Our objective is to design a closed‐loop state feedback controller that steers the current state to a target state along a minimum‐cost trajectory and subsequently halts the system. To achieve this, we introduce key concepts, including cost functions, cost vectors, controlled transition matrices, and optimal feedback control, into the FSM framework. Using algebraic methods, we first establish a necessary liveness condition for FSM stabilizability via matrix‐based analysis. Furthermore, we derive an algebraic stabilizability criterion by examining the powers of controlled transition matrices and provide a topological analysis of their properties. Finally, leveraging semi‐tensor product (STP) operations, we develop an optimal control algorithm for stabilizable FSMs.