Optimal parametric discrete event control: Problem and solution

Abstract

We present a novel optimization problem for discrete event control, similar in spirit to the optimal parametric control problem common in statistical process control. In our problem, we assume a known finite state machine plant model G defined over an event alphabet Sigma so that the plant model language L = L M (G) is prefix closed. We further assume the existence of a base control structure M K , which may be either a finite state machine or a deterministic pushdown machine. If K = L M (M K ), we assume K is prefix closed and that K C L. We associate each controllable transition of M K with a binary variable X 1 ,..., X n middot indicating whether the transition is enabled or not. This leads to a function M K (X 1 , ,...,- , X n ), that returns a new control specification depending upon the values of X 1 ,..., X n middot We exhibit a branch-and-bound algorithm to solve the optimization problem minx 1 x,...x n &maxwwepsiK C(w) such that M K (X 1 ,...,X n ) = |= and L M (M K (X 1 ,...,- , X n middot)) epsi C(L). Here . is a set of logical assertions on the structure of M K (X 1 , X 1 ,...,- , X n middot), and M K (X 1 ,...,- , X n middot) = || indicates that M K (X 1 ,...,- , X n ) satisfies the logical assertions; and, C(L) is the set of controllable sublanguages of L 1 .