Exploiting Independence in a Decentralised and Incremental Approach of Diagnosis

1 Introduction

We are concerned with the diagnosis of discrete-event systems [Cassandras and Lafortune, 1999] where the system behaviour is modeled by automata. This domain is very active since the seminal work by [Sampath et al., 1996]. Its aim is to find what happened to the system from existing observations. A classical formal way of representing the diagnosis problem is to express it as the synchronised product of the system model automaton and an observation automaton. This formal definition hides the real problem which is to ensure an efficient computation of the diagnosis when both the system is complex and the observations possibly uncertain.

It is now well-known that the size of the system model is a bottleneck when using model-based approaches to diagnose complex systems. To answer this problem, decentralised/distributed approaches have been proposed [Pencol´e and Cordier, 2005; Lamperti and Zanella, 2003; Benveniste et al., 2005; Jiroveanu and Bo¨el, 2005]. Instead of being explicitly given, the systemmodel is described through its component models in a decentralised way. The global diagnosis is computed by merging local diagnoses in order to take into account the synchronisation events which express the dependency relation which may exist between the components.

∗This work was mainly made when the author was Ph.D student at University of Rennes1/Irisa, Rennes, France.

Alban Grastien∗ National ICT Australia Canberra - Australia alban.grastien@nicta.com.au

A problem, which is far less considered, is the size of the diagnosis itself. However, it can also be a problem, especially when dealing with a long-lasting flow of uncertain observations as remarked in [Lamperti and Zanella, 2003]. We define in this paper two independence properties (stateindependence and transition-independence) and show that they make it possible to get a decentralised representation of the diagnosis without any loss of information. When the diagnosis is performed on a long-lasting temporal window, the transition independence property, which expresses the concurrence between subsystems, has little chance of being satisfied. The idea then is to slice the diagnosis period into smaller periods and to compute the diagnosis in an incremental way. The problem which appears is that the slicing generally removes the state-independence property. The solution we finally propose is to enrich the representation with an abstract description of the diagnosis trajectories and show that it allows us to keep the benefits of the transition-independence based decentralised representation.

After preliminaries in Section 2, two independence properties (state and transition-independence) on automata are defined in Section 3. In Section 4, the decentralised approach is proposed and the decisive role played by the stateindependence property in the diagnosis computation is highlighted. Then it is shown how to take advantage of the transition-independence property to get an efficient representation of the diagnoses. The incremental computation and the use of an abstract representation is considered in Section 5. To illustrate the impact of our proposal on the diagnosis size, experimental results on a toy example are given in Section 6.

2 Preliminaries

We suppose in this paper that the behavioural models are described by automata. We thus begin by giving some definitions concerning automata (see [Cassandras and Lafortune, 1999]). Then, we recall the diagnosis definitions and state some hypotheses.

2.1 Automata, synchronisation and restriction

An automaton is a tuple (Q,E, T, I, F) where Q is the set of states, E the set of events, T the set of transitions (q, l, q′ ) with l ⊆ E, and I and F the sets of initial and final states. For each state q ∈ Q, (q, ∅, q) ∈ T .

A trajectory is a path in the automaton joining an initial state to a final state. The set of trajectories of an automaton A is denoted Traj(A). In the following, we consider trim automata. The trim operation transforms an automaton by removing the states that do not belong to any trajectory.

Example: Let us consider the first trim automaton in Figure 1. The initial states are represented by an arrow with no origin state, and the final states by a double circle. Then, 1 {a1} -→ 3 {a2,c1} -→ 3 {c3} -→ 4 ∅ -→ 4 is a trajectory.

The synchronisation operation on two automata A1 and A2 builds the trim automaton where all the trajectories of both automata which cannot be synchronised according to the synchronisation events (i.e E1 ∩ E2) are removed. Formally, given two automata A1 = (Q1,E1, T1, I1, F1) and A2 = (Q2,E2, T2, I2, F2), the synchronisation of A1 and A2, denoted A1 ⊗A2, is the trim automaton A = Trim(A′ ) with A′ = (Q1 ×Q2, E1 ∪E2, T ′ , I1 ×I2, F1 ×F2) such that: T ′ = {((q1, q2), l, (q′1 , q′2 )) | ∃l1, l2 : (q1, l1, q′1 ) ∈ T1∧ (q2, l2, q′2) ∈ T2 ∧ (l1 ∩ (E1 ∩ E2) = l2 ∩ (E1 ∩ E2)) ∧ l = l1 ∪ l2}. When E1 ∩ E2 = ∅ (no synchronising events), the synchronisation results in the concurrent behavior of A1 and A2, often called the shuffle of A1 and A2. The number of states of the shuffle is the product of the number of states of A1 and A2 and no trajectory is removed.

Example: Figure 1 gives an example of synchronisation. The synchronising events are the ci events.

The restriction operation of an automaton removes from I all the initial states which are not in the specified set of states. Due to the trim operation, all the states and transitions which are no longer accessible are removed fromQ. Formally, given an automaton A = (Q, E, T, I , F ), the restriction of A by the states of I ′ , denoted A[I ′ ], is the automaton Trim(A′ ) with A′ = (Q, E, T, I ∩ I ′ , F ).

2.2 Diagnosis

Let us recall now the definitions used in the domain of discrete-event systems diagnosis where the model of the system is represented by an automaton. t0 corresponds to the starting time and tn to the ending time of diagnosis. More details can be found for instance in [Pencol´e and Cordier, 2005].

Definition 1 (Model).

The model of the system, denoted Mod, is an automaton.

The model of the system describes its behaviour and the trajectories of Mod represent the evolutions of the system. The set of initial states IMod is the set of possible states at t0. We suppose as usual that F Mod = QMod (all the states of the system may be final). The set of observable events is denoted EMod Obs ⊆ EMod .

Let us turn to observations which can be uncertain and are represented by an automaton, where the transition labels are observable events of EMod Obs .

Definition 2 (Observation automaton).

The observation automaton, denoted Obs, is an automaton describing the observations possibly emitted by the system during the period [t0, tn].

The diagnosis of a discrete-event system can be seen as the computation of all the trajectories of the model that are consistent with the observations sent by the system during the period [t0, tn]. The automaton defined as the synchronisation of the model and the observations represents all these trajectories.

Definition 3 (Diagnosis).

The diagnosis, denoted Δ, is a trim automaton such that Δ = Mod ⊗ Obs.

3 Independence properties

In this section, we present two independence properties that enable a decentralised (compact yet sufficient) representation of the diagnosis presented in the next section.

Let us first define the state-independence property which concerns the decomposition of an automaton A into two automata A1 and A2.

Definition 4 (Decomposition of A).

Two automata A1 and A2 are said to be a decomposition of an automaton A iff A = (A1 ⊗A2)[I] where I are the initial states of A.

Let A′ = A1 ⊗ A2. Note that we do not require that A = A′ , but that A′ is a super-automaton (i.e an automaton that contains all the trajectories of A and possibly more). The reason is that, when decomposing A into A1 and A2, the links existing between the initial states of A1 and A2 can be lost. We thus have Q ⊆ Q′ , I ⊆ I ′ , and F ⊆ F ′ where A′ = (Q′ , E′ , T ′ , I ′ , F ′ ) and A = (Q, E, T, I, F ).

The state-independence property is a property of a decomposition A1 and A2 which ensures that A = A′ .

Definition 5 (State-independence decomposition wrt A). Two automata A1 and A2 are said to be a state-independent decomposition wrt A iff A = A1 ⊗A2.

Property 1: If A1 and A2 have both a unique initial state, and if they are a decomposition of A, then A1 and A2 are a state-independent decomposition wrt A.

Let us turn now to the transition-independence property which states that two (or more) automata do not have any transition labeled with common synchronisation events.

Definition 6 (Transition-independence).

A1 = (Q1,E1, T1, I1, F1) and A2 = (Q2,E2, T2, I2, F2) are transition-independent (TI) iff every label l on a transition of T1 or T2 is such that l ∩ (E1 ∩E2) = ∅.

Two transition-independent automata are concurrent automata and their synchronisation is equivalent to a shuffle operation (see Section 2). Moreover, we have :

Property 2: Let A1 and A2 be two transition-independent automata and state-independent automata wrt A. The states (resp. initial states, final states) of A correspond exactly to the Cartesian product of the states (resp. initial states, final states) of A1 and A2.

4 Improving diagnosis representation in a decentralised approach

In this section, we first highlight the role of stateindependence property when computing diagnoses in a decentralised way. We propose then an efficient diagnosis representation based on transition-independence property.

4.1 The decentralised approach and the role of state-independence

The global model of a real-world system is too large to be explicitly built. To answer this problem, decentralised / distributed approaches have been proposed [Lamperti and Zanella, 2003; Pencol´e and Cordier, 2005; Benveniste et al., 2005; Jiroveanu and Bo¨el, 2005]. In this article, we consider the decentralised approach of [Pencol´e and Cordier, 2005].

The idea (see Figure 2) is to describe the system behaviour in a decomposed way by the set of its subsystems models. The so-called decentralised model is thus dMod = {Mod1, . . . ,Modn} where Modi is the behavioural model of the subsystem (possibly a component) si. The decentralised model is designed as a decomposition of the global model Mod. It is generally assumed that the global model has a unique initial state and that the subsystems models also have a unique initial state. They are thus a state-independent decomposition wrt Mod and the global model can thus be retrieved, if needed, by Mod = Mod1 ⊗ . . . ⊗ Modn.

The observations Obs can be decentralised as follows: dObs = {Obs1, . . . ,Obsn} such that Obsi contains the observations from the subsystem si and such that: Obs = Obs1 ⊗ . . . ⊗ Obsn.

Given the local subsystem model Modi and the local subsystem observations Obsi, it is possible to compute the local diagnosis Δsi = Modi ⊗ Obsi. These diagnoses represent the local subsystem behaviours that are consistent with the local observations. It was shown in [Pencol´e and Cordier, 2005] that the set of local diagnoses is a decomposition of Δ. As they all have a unique initial state, it is also a state-independent decomposition of Δ. It is then possible to directly compute the global diagnosis of the system by synchronizing the subsystem diagnoses as follows: Δ = Δs1 ⊗ . . . ⊗Δsn . This synchronisation operation of subsystem diagnoses is often also called a merging operation.

It is clear that, rather than directly merging all the subsystems diagnoses together, it is possible to compute the global diagnosis by successive synchronisation operations. Let s1 and s2 be two disjoint subsystems (possibly being components) and let s12 = s1 ⊎ s2 be the subsystem that contains exactly s1 and s2. The subsystem diagnosis Δs12 can be computed as Δs12 = Δs1 ⊗Δs2 . The diagnosis of the system is equivalently obtained by replacing Δs1 ⊗ Δs2 by Δs12 . We have Δ = Δs12 ⊗ Δs3 ⊗ . . . ⊗ Δsn .

Algorithm 1 computes the system diagnosis by starting from the component local diagnoses and merging them until ExitLoopCondition is satisfied. In this case, ExitLoopCondition checks that all pairs of diagnoses have been merged.

Algorithm 1 Computing diagnoses in a decentralised way

input: local diagnoses {Δs1 , . . . ,Δsn } dΔ = {Δs1 , . . . , Δsn } while ¬ ExitLoopCondition do Choose Δs1 , Δs2 ∈ dΔ s = s1 ⊎ s2 Δs = Δs1 ⊗ Δs2 dΔ = (dΔ \ {Δs1 , Δs2 }) ∪ {Δs} end while return: dΔ

4.2 An efficient diagnosis representation based on transition-independence

The diagnosis Δ built with a decentralised approach is equal to the synchronisation Mod ⊗ Obs. It can be expected Obs sufficiently contraints the behaviours of the system to significantly reduce the size of the Δ compared to Mod. However Δ can still be large, especially because merging concurrent diagnoses corresponds to computing the shuffle of these diagnoses. It is why we propose to avoid these expensive shuffles by representing the system diagnosis as a set of transitionindependent subsystem diagnoses.

Definition 7 (Decentralised diagnosis). A decentralised diagnosis dΔ is a set of subsystem diagnoses {Δs1 , . . . ,Δsk } such that Δsi is the diagnosis of the subsystem si, {s1, . . . , sk} is a partition of the system Γ, and ∀i, j ∈ {1, . . . , k}, i ̸= j ⇒ Δsi and Δsj are transitionindependent.

As seen before, a decentralised diagnosis dΔ = {Δs1 , . . . ,Δsk } is a state-independent decomposition of the global diagnosis. We get an economical representation of the global diagnosis which can be computed, if needed, by synchronising all the subsystem diagnoses, by

Δ = Δs1 ⊗ . . .⊗Δsk , which, due to Property 2, corresponds to a shuffle operation. Its final states can be obtained by a simple Cartesian product on the final states of all Δsi (see Property 2).

Algorithm 1 can be used to compute the decentralised diagnosis from the local (component) diagnoses by changing ExitLoopCondition into ∀Δs1 ,Δs2 ∈ dΔ, Δs1 and Δs2 are transition-independent. Until all pairs of diagnoses are transition-independent, the algorithm chooses two transitiondependent diagnoses and merges them.

An important point to remark is the decisive role of the state-independence property of the decomposition which, combined to the transition-independence property, allows us to get an efficient representation of the system diagnosis. The state-independence property comes directly from the unique initial state property of the system and subsystems models.

5 Improving diagnosis representation in a decentralised and incremental approach

In this section, we propose to build the diagnosis on successive temporal windows, to benefit from the short duration independences. We then show that the state-independence is generally no longer satisfied, and present in the last part the abstraction operation that enables us to deal with statedependent subsystems.

5.1 Incremental diagnosis

In the previous section, we assumed that the diagnosis was computed on a unique period. This means that the observation automaton represents the observations emitted during [t0, tn]. The problem of this approach is that long periods transition-independent behaviours are infrequent, because each component eventually interacts with most of its neighbours. Thus, all the local diagnoses will eventually be merged in a huge global diagnosis. For this reason, it can be interesting to divide the diagnosis period into temporal windows as presented in [Pencol´e and Cordier, 2005], to benefit from short duration independent behaviours.

Let us consider that the diagnosis Δi-1 of [t0, ti-1] was built and that the set of final states of this diagnosis is F i-1 Δ . Given the observations Obsi of the temporal window [ti-1, ti], it is possible to compute the diagnosis of this temporal window by: Δi = (Mod⊗ Obsi )[F i-1 Δ ] where Modis the system model Mod where all the states are considered as initial states. The trajectories consistent with the observations for the period [t0, ti] (i.e the trajectories of Δi if this automaton were built) can be retrieved by the concatenation of the trajectories fromΔi-1 and the trajectories of Δi . It can also be proved that the final states of Δi are the final states of Δi . It is thus possible to incrementally add the observations of [ti, ti+1] and compute the diagnosis.

5.2 Loss of the state-independence property

Our goal is to use a decentralised computation based on a decentralised model and to represent the diagnosis of the temporal windowWi = [ti-1, ti] by a set of transition-independent subsystem diagnoses similar to Section 4. However, contrary to Section 4, the unique initial state hypothesis can no longer be made and thus the state-independence decomposition property can no longer be considered as satisfied.

Let I i be the set of initial states on the system for the temporal windowWi . Given I i , the set of initial states of a subsystem s is called the projection of I i on s and denoted I i ↓ s. Let us remark that (I i ↓ s) × (I i ↓ s′ ) ⊇ I i ↓ (s ⊎ s′ ). Algorithm 1 can be modified as presented in Algorithm 2 to compute a set dΔi of transition-independent subsystems diagnoses.

Algorithm 2 Computing transition-independent diagnoses in case of non state-independence

input: local diagnoses {Δs1 , . . . ,Δsn } + the set of initial states I i

dΔ = {Δs1 , . . . , Δsn } while ∃s1, s2 : Δs1 and Δs2 are not transitionindependent. do

Let us now consider the transition-independent diagnoses of dΔi and more precisely their final states F iΔsj . The problem is that, due to the loss of the state-independence property, F i is only a subset of FΔis1 ×. . .×FΔisk . Let us illustrate the problem on an example (Figure 3).

Example Figure 3 deals with the diagnosis of two components which can be either in a Ok state or a Faulty state. The figure presents a two-windows diagnosis, each in a box. During the first window (Figure 3, left), one of the two components failed but it is not possible to determine which component did. The initial states of each component at the beginning of the second window are obtained by projecting the final states of the first window and they are O and F for one component and O′ and F ′ for the other one. Nothing happened during the second window. Since the local diagnoses are transition-independent, the algorithm proposes the two local diagnoses (top and bottom in Figure 3, right) but it can be seen that the links between the initial states were lost during the projection. The decomposition of the global diagnosis is not state-independent. We have F 2 ⊂ {O, F} × {O′ , F ′}. To get the exact final states F 2 , one solution would be to synchronise the local diagnoses in conjunction with the restriction operation on the set of final states of the first window as argument, which we want to avoid.

5.3 TI + abstract representation

To obtain the final states F i we propose, instead of merging the state-dependent diagnoses of dΔi , to merge their abstract representations, which is much more efficient. We thus propose to enrich the set of transition-independent diagnoses with the abstract representation of the state- and transitionindependent diagnoses.

The information required relies on the initial and final states only. Thus, we define an abstraction that keeps only the information that there exists a trajectory between an initial state and a final state.

Definition 8 (Abstraction).

Let A = (Q,E, T, I, F) be a trim automaton. The abstraction of A, denoted Abst(A), is the (trim) automaton A′ = (I ∪ F, {e}, T ′, I, F) where T ′ = {(q, {e}, q′) | ∃traj = q0 l1 -→ . . . ln -→ qn ∈ Traj(A) ∧ q0 = q ∧ qn = q′ }.

The following two properties can be easily proved.

Property 3: Let A1 and A2 be two transition-independent automata. Then, Abst(A1) ⊗ Abst(A2) = Abst(A1 ⊗ A2).

Property 4: Let A1 and A2 be two transition-independent automata and let I be a set of states. Then, (Abst(A1) ⊗ Abst(A2))[I] = Abst((A1 ⊗ A2)[I]).

It is now possible to merge the abstract representations of the state-dependent, transition-independent diagnoses as presented in Algorithm 3 until getting a set of state- and transition independent diagnoses. This result is called the abstract decentralised diagnosis, and denoted adΔi . Given the properties 3 and 4, we have the following result:

Proposition 1.

The set of final states F i is the set of final states of adΔi , i.e ΠΔ∈adΔi FΔ.

Let us define an extended decentralised diagnosis as follows :

Definition 9 (Extended decentralised diagnosis).

An extended decentralised diagnosis on Wi is a pair (dΔi , adΔi ) such that

• dΔi is the decentralised diagnosis of the system onWi ,
• adΔi is the abstract decentralised diagnosis onWi .

The transition-independent diagnoses dΔi provide the set of trajectories during the temporal window Wi and the abstract representation of state- and transition-independent diagnoses adΔi provides the set of final states of the temporal window Wi . It is thus a safe representation of the diagnosis on Wi . It can be used as shown in 5.1 to compute the diagnosis on the whole period in an incremental way.

6 Experiments

We present the experimental results on a simplified case inspired by a real application on telecommunication networks.

Algorithm 3 Computation of the abstract decentralised diagnosis adΔi

input: local transition-independent diagnoses dΔi = {Δis1 , . . . ,Δisk } + the set I i of initial states adΔi = {aΔisj | ∃Δisj ∈ dΔi : aΔisj = Abst(Δisj )} while ∃aΔis1 , aΔis2 ∈ adΔi such that aΔis1 and aΔis2 are not state-independent wrt (aΔis1 ⊗aΔis2 )[I i ↓ s1 ⊎s2] do s = s1 ⊎ s2 aΔis = (aΔis1 ⊗ aΔis2 )[I i ↓ s] adΔi = (adΔi \ {aΔis1 , aΔis2 }) ∪ {aΔis} end while return: adΔ

6.1 System

The system to diagnose is a network of 14 interconnected components as presented in Figure 4.

Each component has the same behaviour: when a fault occurs, it reboots, sends a IRebooti observation and forces its neighbours to reboot by sending them a reboot! message. A component can also be asked to reboot by one of its neighbours. In this case, it enters into a waiting state W before rebooting and sends the IRebooti observation. In this state, it can be asked to reboot by another component (and sends then the IRebooti observation). When the reboot is finished, the component sends the observation IAmBacki and reenters the state O.

The model is presented in Figure 5. The reboot! message indicates that reboot is sent to all the neighbours, and the reboot? message indicates that a neighbour has sent the reboot message to the component. So, for example, on component 1, there are three transitions from state O to state W corresponding to a reboot? message received respectively from one of its three neighbours 2, 3 and 14. They are respectively labeled by {reboot2→1, IReboot1}, {reboot3→1, IReboot1} and {reboot14→1,IReboot1}.

Let us remark that the decentralised modeling contains exactly 4 × 14 states, while the global model would contain nearly 414 ≊ 250 000 000 states.

6.2 Results

The algorithms were programmed in Java, and run on a Linux machine with a 1.73 GHz Intel processor. We deal with 45 observations. The experiments results are given Table 1.

The first experiment was made with a unique temporal window as presented in section 4. The computation was more than 26 mn and produced 4 automata, one of which contains 9 085 states and 557 836 transitions. It can be noted that taking into account the transition-independence property of diagnoses in the decentralised representation is interesting as four independent subsystems are identified. It saves us from computing the shuffle for these subsystem diagnoses, which is certainly very beneficial. However, due to the length of the window, one of the automata is still very large.

Using the method described in section 5, the observations are now sliced into 4 temporal windows. The diagnosis was computed in less that 1 second, producing 39 small automata. The number of states (479) is 5% of the number of states used in the previous automaton, and the number of transitions (4 038) is less than 1% of the transitions of the previous automaton. It confirms that slicing observations is beneficial in that it increases the number of independent subsystems, and thus diagnoses.

Let us stress now the importance of the slicing on the good results of the method. In a third experiment, the first temporal window of the previous experiment was sliced into two. The number of states of the diagnosis increased by about 20% and the number of transitions by 30%. Moreover, the computation time increased to 10 seconds. The reason is that you sometimes need to have enough observations on a subsystem to conclude that this subsystem did not communicate with another subsystem. In a fourth experiment, two temporal windows of the first slicing are merged into a unique window. The corresponding computation time is then about 3 minutes and the number of states and transitions exploded. It confirms that the slicing operation is a critical operation and that deciding what is the best slicing is an interesting area for further works.

7 Conclusion

In this paper, we consider the diagnosis of discrete-event systems modeled by automata. To avoid the state-explosion problem that appears when dealing with large systems, we use a decentralised computation of the diagnosis. We show that the global diagnosis can be safely and economically represented by the set of diagnoses of its transition-independent subsystems. An important point is that this decentralised representation relies on the state-independency property.

When the period of observation is important, independent subsystems occur infrequently, since each component eventually interacts with most of its neighbours. A solution is to slice the diagnosis period into temporal windows, in order to get, on these windows, transition-independent subsystems. The problem is that the state-independency property does not hold anymore. It is then impossible to get the exact final states, at least in an economical way. On the one hand, such a set of diagnoses for transition- but not stateindependent subsystems gives us only a superset of the global diagnosis, which is not satisfying. On the other hand, computing the set of transition-independent and state-independent subsystem diagnoses would be too expensive.

We propose in this paper to keep the decentralised diagnosis representation (a set of transition-independent subsystem diagnoses), and to add an abstract representation of both state- and transition-independent diagnoses, which produces the final states in an economic and efficient way. We show that we get a safe and efficient representation of the global diagnosis.

This work opens at least two interesting prospects. As can be seen in Algorithm 3, it is necessary to have an efficient way to check whether two abstract diagnoses are or are not state-independent, and we are currently working on this point. Another concern is about the slicing. As shown in section 6, a bad slicing can lead to a very little benefit. An interesting prospect would be to automatically find the best slicing to obtain a diagnosis represented as efficiently as possible.

Acknowledgements

A. Grastien is currently supported by National ICT Australia (NICTA) in the framework of the SuperCom project. NICTA is funded through the Australian Government's Backing Australia's Ability initiative, in part through the Australian National Research Council.