Engineering Papers⌕ Search

Engineering topics

Griffin, Christopher H.

Publications and source records attributed to Griffin, Christopher H..

Optimal parametric discrete event control: Problem and solution

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 .

42 ENGINEERING↗

Determining a purely symbolic transfer function from symbol streams: Theory and algorithms

Transfer function modeling is a standard technique in classical linear time invariant and statistical process control. The work of Box and Jenkins was seminal in developing methods for identifying parameters associated with classical (r, s, k) transfer functions. Discrete event systems are often used for modeling hybrid control structures and high-level decision problems. Examples include discrete time, discrete strategy repeated games. For these games, a discrete transfer function in the form of an accurate hidden Markov model of input-output relations could be used to derive optimal response strategies. In this paper, we develop an algorithm for creating probabilistic Mealy machines that act as transfer function models for discrete event dynamic systems (DEDS). Our models are defined by three parameters, (l 1 ,l 2 ,k) just as the Box-Jenkins transfer function models. Here h is the maximal input history lengths to consider, l 2 is the maximal output history lengths to consider and k is the response lag. Using related results, We show that our Mealy machine transfer functions are optimal in the sense that they maximize the mutual information between the current known state of the DEDS and the next observed input/output pair.

42 ENGINEERING↗

Exception Handling Controllers: An application of pushdown systems to discrete event control

Recent work by the author has extended the Supervisory Control Theory to include the class of control languages defined by pushdown machines. A pushdown machine is a finite state machine extended by an infinite stack memory. In this paper, we define a specific type of deterministic pushdown machine that is particularly useful as a discrete event controller. Checking controllability of pushdown machines requires computing the complement of the controller machine. We show that Exception Handling Controllers have the property that algorithms for taking their complements and determining their prefix closures are nearly identical to the algorithms available for finite state machines. Further, they exhibit an important property that makes checking for controllability extremely simple. Hence, they maintain the simplicity of the finite state machine, while providing the extra power associated with a pushdown stack memory. We provide an example of a useful control specification that cannot be implemented using a finite state machine, but can be implemented using an Exception Handling Controller.

42 ENGINEERING↗