A Novel Framework for Integrating Discrete Event System Control and Diagnosis

A Novel Framework for Integrating Discrete Event System Control and Diagnosis

Gregory Provan*

Rockwell Scientific Company 1049 Camino Dos Rios, Thousand Oaks, CA 91360

l Towards an Integrated Control/Diagnosis Framework

Diagnosis of discrete event systems (DES) is an impor­ tant task, with several desiderata that include the ability to ( 1) encode both control and diagnosis properties within a single representation, and (2) to compose system models from com­ ponent models in a simple and efficient manner, e.g., without the kind of state explosion that can occur during parallel com­ position of component Finite State Machines (FSMs).

Many formalisms have been proposed for the Model-Based Diagnosis (MBD) of a DES, but each has drawbacks. The representations based on FSMs, e.g., [Sampath eta!., 1995], have a clear control semantics but suffer from incompletely­ specified diagnostic semantics and state explosion during model composition. MBD representations, e.g., [Darwiche, 1998], have been used to model DESs using space-efficient compositional methods [Darwiche and Provan, 1996], but lack well-developed control-theoretic specifications.

This article proposes a framework based on FSMs that has a clear control and diagnostics semantics, yet enables model composition without state-space explosions. We propose a two-level modeling framework, based on a system hyper­ graph 7-{ that can serve as a generator for MBD and FSM models. 7-{ specifies the component causal relations using the graphical framework described within causal networks (CN) [Darwiche, 1998], whereby we can clearly specify in­ dependence relations for system variables, and as a conse­ quence compose system models with system state spaces lim­ ited through independence relations. Our representation is not significantly more complex than that of either FSM or CN alone, yet is equivalent to both these representations. We in­ troduce to MBD modeling additional requirements for speci­ fying control transitions, and to FSM modeling requirements on state descriptions and causal independence of components.

2 A Discrete Event Modeling Framework

We adopt a representation that is a hybrid of two key mod­ eling approaches, an MBD approach, Causal Networks (CN) [Darwiche, 1998 ], and an FSM control/diagnosis approach [Sampath eta!., 1995].

*email: gprovan@rwsc.com

We propose a two-level, component-based framework to model complex discrete event systems. 1 Our higher level system representation, termed System Causal Graph (SCG), provides a well-defined approach (based on bond graphs) for describing the high level component (or sub-system) config­ urations and the physical/causal inter-relations of the com­ ponents (or sub-systems). We model the behaviors of indi­ vidual components using a lower level representation, called a Control Causal Network (CCN). The CCN models can be converted into regular Finite State Machines or Proposi­ tional Logics for further analysis using FSM-based discrete event system techniques (e.g., supervisory control theory) or model-based reasoning techniques (e.g., CN diagnostics), re­ spectively [Provan and Chen, 2003]. The behaviors of the complete system are described by (the composition of) the individual component models.

2.1 Component-Based Modeling Approach

This section describes the CCN framework we adopt for mod­ eling the components of a system. This representation adopts the CN graphical structure and diagnostics specifications, and encodes propositional equations for each node in the graph based on an extension of FSMs. To explain our framework, we first briefly introduce CNs and FSMs.

We adopt the CN model specification [Darwiche, 1998], called a system description <I>, which defines a tuple (P, Q, Ill), where (a) Pis a finite set of discrete-valued vari­ ables comprising two disjoint variable types: P m represents the failure modes of the components, and P m represents sys­ tem properties other than failure modes; (b) Q is a directed acyclic graph that defines the causal relations over the vari­ ables in P; (c) Ill is a set of propositional sentences, the do­ main axioms, constructed from members in P. This approach has a number of important properties, such as compositional modeling based on the independence properties specified in Q: if component i has behavior equations Ill i, then the system behavior is specified simply by the union of the component equations, i.e., Ill = U i Ill i [Darwiche, 1998]. Specifications of, and algorithms for computing a diagnosis, minimal diag­ nosis, etc., are all well-defined [Darwiche, 1998].

An FSM is defined as G = (Q, ~. o, q0), where Q is the state space, ~ is the set of events, 0 is the partial transition function o : Q x I: --> Q (and defines the transitions between states in Q), and q0 is the initial state of the sys­ tem. This framework has been extended for failure diagnosis through the use of unobservable failure transitions and auto­ construction of an observer G diag [Sampath et al., 1995].

10ur approach can be easily expanded into a multi-level nested hierarchical structure to accommodate more complex systems.

In our hybrid representation, we model each component using a control causal network (CCN) consisting of a tuple (P, {L:,Q,r,o,(qo,Po),Qm},Q,w), where Pis the set of parameters, I: is the event set, Q the state set, r the set of guards (or pre-conditions), 0 : L; X Q X r X p --> Q X p the transition function, q 0 the initial state, Po the initial value of parameters, Qm the marked states, Q a graph, and Ill a set of propositional equations. 2 Parameters in the parame­ ter set P are discrete-valued, and guards 1 E r are pred­ icates on the parameters in P . We can view o as a set of transitions. An equation describing transition T E o, de­ noted l r 1\ ar => fr(p), can be interpreted as follows: If at state q the guard 1 r is true and the event a r occurs, then the next state is q' and the parameters at q' will be updated to fr(p). We call the functions fr(P) the actions of the tran­ sition T . The set of all sequences of event labels (traces) of a CCN given initial parameter setting p0 is the language L it generates. We have shown in [Provan and Chen, 2003] that this representation possesses the control-theoretic properties of the finite state machine with parameters representation, and is based on standard propositional logic with well-known se­ mantics.

2.2 System Causal Graph

An SCG 1{ : (N, £) is a directed graph whose nodes in N represent the components of the system and whose edges in £ : N x N denote the causal relations between the compo­ nents. A node Ni E N is associated with a CCN component model Ai, which represents the component's behaviors.

The SCG's graph 1{ has properties similar to those of the graph Q of a CCN. 1{ must preserve a number of control and simulation/diagnostics properties. 3 As an example, in or­ der to prevent possible ambiguity and direct circularity in the causal semantics, we assume that the system represented in an SCG should be structured such that any component in the SCG may not be both the (direct) predecessor and the (direct) successor of the same component in the SCG.

3 Properties of Integrated Representation

In the full paper [Provan and Chen, 2003 ], we prove a num­ ber of important properties of the SCG. One key property in­ volves the sound FSM and CN models that can be generated, where by sound we mean that the model obeys the syntactic and semantic requirements of the (FSM or CN) representation in question:

2 The definition is a discrete-parameter restriction of Finite State Machines with Parameters [Chen and Lin, 2000], such that we use a logical representation for state transitions. Our representation ex­ tends the representation and control semantics of the causal network models defined in [Darwiche and Provan, 1996] by adding an ex­ plicit transition framework for each CN sentence in w.

3 The full paper, [Provan and Chen, 2003], discusses 1i and its properties in detail.

Lemma 1 Mapping an SCG into an FSM (CN) produces a sound system-level FSM (CN), respectively.

To show the CN model created by the above procedure is equivalent to the FSM model, we show that they generate the same language.

Theorem 1 Given an FSM G and a CN model <I> generated from an SCG with initial state-setting ( qo , Po), the FSM and CN languages are equal, i.e., L( G, qo) = L( <I>, Po) .

From a control perspective, this means that the FSM and CN possess the same control properties, e.g., Iiveness, cor­ rectness, etc. From a plant modeling perspective, we can use the logical representation of the SCG to validate a plant model using a theorem prover.

In addition, [Provan and Chen, 2003] shows the equiva­ lence of diagnostic capabilities of the generated models. We assume that, to per.form fault isolation, for the FSM (CN) ap­ proach we use a diagnoser Gdiag (CN model <I>), respectively.

Theorem 2 If we map an SCG into a FSM G and a CN model <I>, then: (a) Given observation set G, G is diagnosable (i.e., we can isolate failure events) iff <I> is diagnosable,· (b) Given observation set G, the set of diagnoses for G is equivalent to the set of diagnoses for <I>.

This result means that we can now establish equivalent di­ agnostic capabilities between an FSM and a CN representa­ tion, if they can be encoded by the same SCG. Hence, the important MBD properties, e.g., completeness and soundness of diagnostics given a model <I>, can be inherited by an appro­ priate FSM model.

In summary, these properties indicate that this approach acquires the control semantics of FSMs, and the diagnos­ tic semantics of CNs. On the practical side, although we can generate and use algorithms for either FSM or CN mod­ els, further research is necessary to identify the model type most appropriate to a particular class of applications, since model/algorithm efficiency is domain-dependent. In addition, we need to analyze the tradeoffs associated with the extra modeling requirements of the SCG graphical framework ver­ sus the linear (rather than worst-case exponential, as in an FSM) growth associated with system model composition.