Event-Diagnosis.

We consider event-diagnosis as introduced in [D4]. Given a generator G and a set of observable events Sigma0, a failure type f is associated with a set of unobservable failure events Sigma_f. The occurence of any event from Sigma_f is interpreted as a failure of type f. It is assumed that {Sigma_f| f  F} forms a partition of all failure events, where F denotes all failure types under consideration. This partition can be specified as a FailureTypeMap.

Diagnosability of discrete event systems was first studied in [D1]. A discrete event system is diagnosable, if any failure can be unambiguously detetected after the occurrence of a bounded number of events. Another variant is the notion of i-diagnosability, which weakens the requirement in that a failure f may remain undetected as long as no so called indicator-event from If, If  Sigma0, occured. The functions IsEventDiagnosable and IsIndicatorEventDiagnosable implement the respective polynomial time tests for (i-)diagnosability proposed in [D2].

The actual dagnosis task is performed by a diagnoser , which is a generator with alphabet Sigma0 that provides a state estimate for the original system G. The estimate includes labels that hold information about the occurrence of past failures. A failure is uniquely diagnosed if all such labels in the estimate indicate that a failure happened. The function Diagnoser computes a Diagnoser, such that -- in the presence of diagnosability -- any failure will be unambiguously detected within a bounded number of event occurrences. The realization of the diagnoser automaton is described next.

Diagnoser

Generator with state estimate attribute for event-diagnosis.

A diagnoser is a Generator with state attributes that provides state estimates for the diagnosed system G. While G models nominal and erroneous behaviour over the full alphabet Sigma, the diagnoser runs in parallel, but only synchronized w.r.t. the observable events Sigma0  Sigma.

Each state estimate consists of a set of pairs (q,F). During diagnosis, the q components of the current diagnoser state indicate possible states in which the observed system G might be. The corresponding failure types f are those that occurred so far, provided that G indeed is in state q. In addition to the failures specified in the corresponding FailureTypeMap, f may be one of the predefined symbols N or A, to indicate nominal operation or ambiguity.

In this implementation, states of the original system are given by indices. Future versions may allow for optional symbolic state names to ease token identification.

Example:

The following figure shows a sample diagnoser with the alphabet Sigma={a, b} and the states Q={s1, s2, s3}.

Diagnoser automaton

In state s1 with label 1N, the original system is known to be in state 1 and no failure occred so far. In state s2 with label 3F1 5N, the original system either is in state 3 after a failure of type F1, or in state 5 without any failure so far. In state s3 with label 7F1F2, the original system either is in state 7 after failures of type F1 and type F2, or in state 9 with ambiguous failure history. The file output of the above diagnoser is depicted in the gray box. Here, the global attribute "FailureType" at the end of the token stream is the corresponding FailureTypeMap to define the semantics of each failure label.

<Generator>
"Diagnoser"   

<Alphabet>
"alpha"   "beta"   "gamma" 
</Alphabet>

<States>
%%% state s1
"s1"          
<StateEstimates>
1             
<DiagLabels> "N" </DiagLabels>
</StateEstimates>
%%% state s2
"s2"          
<StateEstimates>
3    <DiagLabels> "F1" </DiagLabels>
5    <DiagLabels> "N"  </DiagLabels>
</StateEstimates>
%%% state s3
"s3"          
<StateEstimates>
7    <DiagLabels> "F1" "F2"  </DiagLabels>
9    <DiagLabels> "A"  </DiagLabels>
</StateEstimates>
</States>

<TransRel>
"s1"          "a"           "s2"          
"s2"          "b"           "s3"          
"s3"          "a"           "s3"          
</TransRel>

<InitStates> "s1" </InitStates>
<MarkedStates></MarkedStates>

<FailureTypes>
%%% failure F1
"F1"   <FailureEvents> "WPblocked"   "WPfelldown"  </FailureEvents>
%%% failure F2
"F2"   <FailureEvents> "sfRunsContinuously" "cb1RunsContinuously" </FailureEvents>
</FailureTypes>

</Generator>

FailureTypeMap

Specification of Failure Types

The failure-type map defines failure-types  F that are each associated to a set Sigma_f of unobservable failure events. The sets Sigma_f of failure events are assumed to be disjoint, i.e. a failure-type map indeed defines a partition {Sigma_f| f  F} of all failure events.

Optionally, each failure type  F may be equipped with a set of observable indicator events If  Sigma0. This feature is used for i-diagnosability, where a failure only needs to be detected after the occurence of a corresponding indicator event.

The example below defines one failure type F1 with failure- and indicator events.

<FailureTypes>
"F1"  
<FailureEvents>   "fail"    "error"  </FailureEvents>
<IndicatorEvents> "alpha"   "beta"    </IndicatorEvents>
</FailureTypes> 

EventDiagnoser

Computes event-diagnoser w.r.t. failure types.

Signature:

EventDiagnoser(+In+ System GArg, +In+ FailureTypeMap FArg, +Out+ Diagnoser GRes)

Detailed description:

Provided that the specified generator is diagnosable, this function computes the corresponding diagnoser.

When a failure-type map FArg is specified, the implementation parses through the given system GArg to iteratively compute the diagnoser. For each diagnoser state, a reachability map is maintained to record the set of system states that are reachable by just one observable event (preceded by arbitrarily many unobservable events). Any occurring unobservable failure event from the failure type map becomes visible in the diagnoser with the next occurring observable event. The diagnoser labels are then set to accumulate possible failures and corresponding system states. For details see [D2].

Parameter Conditions:

Same as with IsDiagnosable and IsLanguageDiagnosable, respectively.

IsDiagnosable

Detailed description:

For a given FailureTypeMap, a system is said to be diagnosable, if every failure type can be unambiguously detected after a bounded number of transitions. If the sytem is diagnosable, a diagnoser may be synthesized by EventDiagnoser.

The algorithm constructs several testing automata and then performs a cycle detection, as proposed in [D2].

Parameter Conditions:

All failure events are unobservable. The failure type map FArg represents a partition of all failure events. The generator GArg is live, see IsComplete. The generator GArg exhibits no cycles with unobservable events only. The current implementation returns false if the requirements are not met.

IsIndicatorDiagnosable

Detailed description:

For a given FailureTypeMap, a system is said to be i-diagnosable, if every failure type f that occurs after an associated indicator event from If, can be unambiguously detected after a bounded number of transitions. If the sytem is diagnosable, a diagnoser may be synthesized by EventDiagnoser.

The algorithm constructs several testing automata and then performs a cycle detection, as proposed in [D2].

Parameter Conditions:

All indicator events are observable. All failure events are unobservable. The failure type map FArg represents a partition of all failure events. The generator GArg is live, see IsComplete. The generator GArg exhibits no cycles with unobservable events only. The current implementation returns false if the requirements are not met.

libFAUDES 2.32b --- 2024.03.01 --- with "synthesis-observer-observability-diagnosis-hiosys-iosystem-multitasking-coordinationcontrol-timed-simulator-iodevice-luabindings-hybrid-example-pybindings"