Deterministic finite automata representation for model predictive control of hybrid systems

As is well known, the computational complexity in the mixed integer programming (MIP) problem is one of the main issues in model predictive control (MPC) of hybrid systems such as mixed logical dynamical systems. Thus several efficient MIP solvers such as multi-parametric MIP solvers have been extensively developed to cope with this problem. On the other hand, as an alternative approach to this issue, this paper addresses how a deterministic finite automaton, which is a part of a hybrid system, should be expressed to efficiently solve the MIP problem to which the MPC problem is reduced. More specifically, a modeling method to represent a deterministic finite automaton in the form of a linear state equation with a smaller set of binary input variables and binary linear inequalities is proposed. After a motivating example is described, a derivation procedure of a linear state equation with linear inequalities representing a deterministic finite automaton is proposed as three steps; modeling via an implicit system, coordinate transformation to a linear state equation, and state feedback binarization. Various significant properties on the proposed modeling are also presented throughout the proofs on the derivation procedure.