Diagnosability Analysis of a Class of Hierarchical State Machines

Abstract

This paper addresses the problem of fault detection and isolation for a particular class of discrete event dynamical systems called hierarchical finite state machines (HFSMs). A new version of the property of diagnosability for discrete event systems tailored to HFSMs is introduced. This notion, called L₁-diagnosability, captures the possibility of detecting an unobservable fault event using only high level observations of the behavior of an HFSM. Algorithms for testing L₁-diagnosability are presented. In addition, new methodologies are presented for studying the diagnosability properties of HFSMs that are not L₁-diagnosable. These methodologies avoid the complete expansion of an HFSM into its corresponding flat automaton by focusing the expansion on problematic indeterminate cycles only in the associated extended diagnoser.

Appendix: The extended diagnoser

The extended diagnoser for a finite state automaton G = (X,E,δ,x ₀) with observable event set $E_o \subseteq E$ and fault event f ∉ E _o was first introduced in Sampath (1993) and reviewed in Debouk et al. (2000).

The extended diagnoser is the Finite State Automaton

$$ \label{gd} G_{d}^e=\left\{Q_{d}^e,E_o,\delta_{d}^e,q_{0}^e\right\} $$

(16)

where $Q_{d}^e$, E _o , $\delta_{d}^e$ and $q_{0}^e$ have the usual interpretation. The initial state of the extended diagnoser is defined to be $\big[(x_0,N);(x_0,N)\big]$. A state $q \in Q_{d}^e$ is of the form

$$ \left\{\big[\big(x_1,l_1\big);\big(x_1^\prime,l_1^\prime\big)\big],\big[\big(x_2,l_2\big);\big(x_2^\prime,l_2^\prime\big)\big], \big[\big(x_1,l_1\big);\big(x_2^{\prime\prime},l_2^{\prime\prime}\big)\big],\ldots, \big[\big(x_n,l_n\big);\big(x_n^\prime,l_n^\prime\big)\big]\right\}\;, $$

where each (x , l) pair is in $Q_o=2^{X_o \times \Delta}$, where

$$ \Delta=\left\{N, F \right\} $$

is the set of normal and fault labels.

A tuple of (x, l) pairs, for example $[(x_1, l_1); (x_1^\prime , l_1^\prime)]$, has the following meaning: $x_1^\prime$ is a component of a system state estimate after the occurrence of an observable event and $l_1^\prime$ is its failure label, while x ₁ is the predecessor state of $x_1^\prime$ through one observable event in G and l ₁ is its corresponding failure label.

The transition function $\delta_d^e$ of the extended diagnoser is constructed in a manner similar to the transition function of the diagnoser (see Sampath et al. 1995), with the additional aspect that every state of G that appears in a state component of G _d is associated with its predecessor state through one observable event in G (along the sub-trace of events under consideration) and both states carry their labels; these labels are obtained following the same label propagation rules as in Sampath et al. (1995). The state space $Q_d^e$ is the resulting subset of Q _o ×Q _o composed of the states of the extended diagnoser that are reachable from $q_0^e$ under $\delta_d^e$. Note that by construction

$$ \mathcal{L}\left(G_d^e\right)= \mathcal{L}(G_d) = P(\mathcal{L}(G))\;. $$

We define the state projection SP:Q _o ×Q _o →Q _o as follows:

$$ q=\left\{\big[\big(x_1,l_1\big);\big(x_1^\prime,l_1^\prime\big)\big],\ldots, \big[\big(x_n,l_n\big);\big(x_n^\prime,l_n^\prime\big)\big]\right\} \rightarrow SP(q) = \left\{\big(x_1^\prime,l_1^\prime\big),\ldots, \big(x_n^\prime,l_n^\prime\big)\right\}\;. $$

Definition 5

A state $q \in Q_d^e$ is said to be f _i -certain if ∀ (x,ℓ) ∈ SP(q) , f _i  ∈ ℓ.

Definition 6

A state $q \in Q_d^e$ is said to be f _i -uncertain if $\;\exists (x,\ell),\big(y,\ell^\prime\big) \in SP(q)$ such that $f_i \in \ell \mbox{ and } f_i \notin \ell^\prime$

Definition 7

A set of states $q_1, q_2,\ldots , q_n \in Q_d^e$ is said to form a cycle in $G^e_d$ if the following is true:

$$ \delta_d^e(q_l,\sigma_l)=q_{l+1}\,\,\; l=1, \ldots , n+1\,, \mbox{ and } \delta_d^e(q_n,\sigma_n)=q_1 $$

for some observable events σ _i , i = 1,..., n.

Definition 8

A set of (x _i ,l _i ) pairs, where (x _i ,l _i ) ∈ Q _o , i = 1, ..., n is said to form a matched cycle in $G_d^e$ if $\exists q_i \in G_d^e$, i = 1, ..., n such that:

$$ \big(\big(x_i,l_i\big),\big(x_{i+1},l_{i+1}\big)\big) \in q_{i+1}\;, \; i=1, \ldots , n-1\;, \mbox{ and } \big((x_n,l_n\big),\big(x_1,l_1)\big) \in q_1\;. $$

Definition 9

A set of states $q_1, q_2 \ldots q_n \in Q_d^e$ forming a cycle of f _i -uncertain states in $G_d^e$ is said to form an f _i -indeterminate cycle if

• 1. There exists a set of (x _j ,l _j ) ∈ SP(q _j ), j = 1, ...n forming a matched cycle in $G_d^e$, with F _j  ∈ l _j , j = 1, ...n;

• 2. There exists a set of $(y{\!_{j}},l^\prime{\!_{j}}) \in SP(q{\!_{j}})$, j = 1, ...n forming a matched cycle in $G_d^e$, with $F{\!_{j}} \notin l^\prime_j$, j = 1, ...n.

An F _i -indeterminate cycle in $G_d^e$ indicates the presence in $\mathcal{L}(G)$ of two traces s ₁ and s ₂ of arbitrarily long length, such that they both have the same observable projection and s ₁ contains a failure event from the set Σ _fi , while s ₂ does not. Therefore, according to the diagnosability definition given in Sampath et al. (1995), a language L is diagnosable with respect to the projection P and the failure partition Π _f on Σ _f if and only if its extended diagnoser $G_d^e$ has no f _i -indeterminate cycle for each failure type F _i .