Event-Based Reasoning for Short Circuit Diagnosis in Power Transmission Networks

1 Introduction

To avoid service interruptions caused by short circuits in a power transmission network, it is necessary to isolate faults as soon as possible. For this reason, there are a number of protection components distributed over the network. The protection system is in charge of detect­ ing dangerous conditions, of disconnecting a component (such as a line, a bus, a transformer or a generation group) as soon as its operating starts to be dangerous, and of keeping in operation non-faulty components as much as possible, in order to avoid a black-out. This is

Paolo Pogliano

CISE s.p.a.

via Reggio Emilia, 39 I-20090 Segrate (Milano), Italy

paolo@sia.cise .it

achieved by tripping the circuit breaker associated with each protection. Each protection has to protect mainly one component, but must also operate as a backup to other protections nearby.

When intervening, all the protections and the break­ ers send logical signals reporting their operation: these are recorded by an event recorder and transmitted to a Regional Control Center (RCC) where they are used for fault localization. Records, called messages, consist of a unique address of the event source, an event code, and possibly a timestamp. Operators of the RCC have to decide within one minute where the fault is located and what recovery actions have to be applied. Normally, due to time constraint reasons, only the current status of the breakers is considered, but this is not generally sufficient for fault localization. It is recognized that as a result of this an automated tool for fault diagnosis is an important requirement.

To this end, a technique based on the modeling of the protection system and on the interpretation of the reac­ tion of the protection system to the occurrence of a short circuit has been defined. Three different interpretation layers are involved: the local interpretation, the global in­ terpretation, and the heuristic interpretation. The focus of this paper is on the first two layers.

2 Modeling the protection system

Each protection component is modeled by means of a finite state machine (FSM), called reactive model, which is driven by a series of input events and generates some other output events when transitions between (reactive) states occur. For example, a distance· protection is started when the impedance on the relevant line goes under a certain threshold (input event). After that, the protection is expected to change state at fixed time intervals (clock input events) and, possibly, to trip the associated breaker (tripping output event). Note that the tripping output event for the protection generates an input (tripping) event for the breaker: we say that the output event is exported by the protection and is imported by the breaker. Reactive states can be either steady or unsteady. This classification improves the se­ mantics of reactive models and indirectly poses a number of constraints on the behavior of protection components which can be conveniently exploited by the interpreta­ tion algorithm. A null event f is a formal notation to specify the absence of events.

Formally, a reactive model M is a record of four el­ ements: M = (E,J, 0, 8), where E is the set of the reactive states, I is the set of input events, 0 is the set of output events, and 8 is the transition function: 8 : E x (I U E) x (2° U E) -> E, (2° is the power-set of 0). This means that a transition T from state S1 to state s2 is in general triggered by an input event i and generates, before changing state, the list of out­ put events < o1, o2, ... , On >. This is denoted by S ilo1 ,o2, ... ,on S Fu h "' "' "' T = 1 ----+ 2· rt ermore, LJ = L.Js U L.Ju, Es n E,. = 0, where Es and E,. denote the set of steady and unsteady states respectively.

The specification of the reactive model of each type of protection component and the instantiation of such cla..'lses of components into a given network topology yields the whole model of the diagnosed system.

Each reactive model describes both the correct and faulty behavior of a class of protection components. Fur­ thermore, the model allows for uncertainty due to pos­ sible loss of messages. Specifically, if during a transition ilm

T1 = S1 ----+ S2, message m may be lost, then the 8 function will include an additional transition T2 = S1 ~ S2.

In the sequel, we assume the completeness of each re­ active model, that is to say, the reactive model is as­ sumed to describe each possible reaction.

3 Misbehaviors, observations, histories

When a short circuit occurs, we say there is a misbehav­ ior f.L of the transmission network. The set of protective components reacting to a misbehavior f.L is called the misbehavior extent of f.L, and is denoted by extent(f.L). After the specification of each reactive model, it is pos­ sible to interpret a given sequence of observations, the messages, in order to eventually find out the sequence of transitions covered by the involved protection compo­ nents during f.L· When a short circuit occurs, each actual protection component is expected to react in a way that corresponds to an instantiation of the model, called the local history of the component. As such, a local history is a sequence of transitions within the reactive model. The initial and final states of the history are required to be steady. The local history is derived on the basis of the local observation of the component P, namely a list of messages relevant to P.

Definition 1 (local history) Let M = (E,I,0,8) be a reactive model of a protective component. A local history of M is a (possibly empty) sequence h =< T1, T2, .. . , Tn > of transitions in M so that h conforms to the following morphology constraints:

1. Determinism. Each transition T; E h is adorned with at most one allowed input event.
2. Contiguity. For each pair of contiguous transitions T;, Ti+1 in h, the final state ofT; coincides with the initial state of Ti+I·
3. Stability. Both the initial state of T1 and the final state of Tn are in Es.

If the sequence of transitions is empty, his called a null history, and is denoted by E.

Definition 2 (local observation) Let M be a reactive model of a protection component P. A local observation obs of P, obs(P) =< o1,o2, ... ,on >,is a sequence of temporally ordered observable output events, generated by a local history of M. A local observation which is empty is called a null observation and is denoted by E.

4 Local Interpretation

The first step towards the detection of the short circuit is represented by the local interpretation of every local ob­ servation. A local interpretation algorithm (lia) has been defined. The algorithm takes as input a local observation obs(P) and generates a seth* of consistent local histories on the basis of the relevant reactive model. In general, a local interpretation gives rise to several consistent local histories, namely: h* = lia(obs(P)) = [h1,h2, ... ,hn]·

Interestingly, a reactive model M of P can be for­ mally interpreted as the grammar of a regular language L where an observation obs{P) represents a phrase of L [Hopcroft and Ullman, 1979]. Consequently, the problem of determining the local interpretation of obs{P) corre­ sponds to the recognition of a string of tokens (the mes­ sages) as a phrase f of L. What is essential in the local interpretation is to keep track of the sequence h of tran­ sitions which are relevant to the recognition of f.

However, a model M may possibly be non­ deterministic, involving transitions which are not asso­ ciated to any observable event. These are called silent transitions. Moreover, silent transitions may possibly form silent cycles so that h* = lia(obs(P)) may poten­ tially include an unlimited number of local histories, all of them being consistent with obs(P). For example, if h S i1 I m1 S i2 I m2 S . . . h b (P) d 1 = 1 ----+ 2 ----+ 1 IS consistent wit o s , an the model of p includes the silent transition s2 ~ s2, i1 I m1 i I · i2 I m2 . . . then h2 = S1 ----+ S2 ----+ S2 ----+ S1 IS COnSIStent With obs(P) as well, since the silent transition is immaterial for the observation.

In the lia algorithm, a non-deterministic reactive model Mn is first translated into a deterministic model Md, in which a connected subgraph of M involving only silent transitions (called a silent subgraph) is collapsed into a new reactive state. The interpretation of obs(P) is therefore performed on the basis of the new determin­ istic model Md , instead of the original non-deterministic model Mn. However, once a local history h is deter-. i1 I m1 i2 I m2 . mmed, for example h = sl ----+ s ----+ s2' lf s corresponds to a collapsed silent subgraph, then the actual local history relevant to the original model Mn will in­ clude a so-called hypertransition, namely the totality of the paths in s which start at an initial state si and end at i1 I m1 i2l m2 a final states, such that sl ----+ si and s, ----+ s2 are legal transitions in Mn. A hypertransition from Si to Sf is denoted by Si => S 1. A local history involving a hyper­ transition is called a hyperhistory. In the above example, . . i1 I m1 i2 I m2 the hyperhlstory Wlll be: sl ----+ si => s, ----+ s2. A hyperhistory graph is the graph representation of the hy­ per history and is obtained by connecting the graph rep­ resentation of the involved (hyper) transitions to each other.

5 Global Interpretation

Once observations of protective components reacting to a misbehavior f.L are interpreted by lia, the set of consistent global histories must be generated.

Definition 3 (global history) Let [ P1, P2, ... , Pm] = extent(p) be the set of protective components involved in a misbehavior f.L· A global history H of J.L, H(p) = ( h1, h2 , ... , hm ) , is the aggregation of the local histories h1, h2 , ... , hm relevant to P1, P2, ... , Pm respectively.

Definition 4 (global history domain) Let [ obs(P1), obs(P2), ... , obs(Pn)] be the set of local observations relevant to extent(p). The global history domain of J.L, H d (J.L), is the cartesian product of the local interpreta­ tions of P1, P2, :, . , Pn, namely: Hd(J.L) = lia(obs(P1)) x lia(obs(P2)) x · · ~ x lia(obs(Pn)) .

Definition 5 (global interpretation) The global inter­ pretation of J.L, H* (J.L), is a relation among the local inter­ pretations [ lia( obs(P1)), lia( obs(P2) ), ... , lia( obs(Pn))], namely a subset of the global history domain Hd(J.L): H*(p) ~ Hd(J.L) = lia(obs(P1)) x lia(obs(P2)) x · · · x lia(obs(Pn)) so that the following conditions hold:

1. V H = ( h1, h2, ... , hn) E H* (J.L), His globally con­ sistent with respect to the interface constraints, and
2. --,:J a globally consistent H' E Hd(J.L) such that H' ~ H*(p).

A systematic approach for selecting non spurious global histories is to apply a balance function to every pair of local histories (h1, h2), where h1 E lia(obs(P1)), h2 E lia(obs(P2)), and P1 is connected to P2. In the simplest case in which both h1 and h2 are plain local histories (not hyperhistories) , balance is a boolean function checking the consistency of h1 and h2 with respect to the inter­ face constraints relevant to h1 and h2 only. Informally, each event of h1 exported by P1 to P2 is required to be imported by h2 and vice versa.

To this end, a consistency matrix is used, where the result of each application of balance is recorded. A con­ sistency matrix :=:,. is relevant to a misbehavior J.L and is composed of rows and columns associated with local interpretations relevant to extent(p). Thus, :=:,. ( h1, h2) denotes the element of the matrix which corresponds to histories h1 and h2. The inconsistency set of:=:,., denoted by~(::::,.) is the set composed of those local history pairs (h1, h2) for which balance(h1, h2) =false. On the ba­ sis of the inconsistency set we are allowed to remove the inconsistent global histories from the global history do­ main Hd(J.L). This operation corresponds to the deletion of the global histories which include a pair of the in­ consistency set. Therefore, H E Hd(J.L) is a consistent global history if and only if ·:l(h1, h2) E ~(:=:,.) so that (h1, h2) ~H.

However, the trouble arises when the approach based on the consistency matrix is extended to deal with hy­ perhistories: in this case, balance is expected to return more information than a single boolean value. For ex­ ample, if h and h* denote a local history and a hyper­ history respectively, three different cases are possible for balance(h, h*), namely:

1. balance(h, h*) = 0. This is the easiest case since it establishes that every candidate global history in­ volving both hand h* is to be discarded. :=:,.(h, h*) is marked with the empty set symbol.
2. balance(h,h*) = [h1,h2, ... ,hn]· In that case the hyperhistory is resolved and a finite number of lo­ cal histories is determined (possibly a singleton). :=:,.(h, h*) is marked with a reference to this set.
3. balance(h,h*) = h'* = [hl,h2, ... ,hn,hn+l, ... ], h'* ~ h* . The hyper history is reduced but not re­ solved. A reference to the hyperhistory graph of h'* is put in :=:,.(h, h*).

But the real problem is how to extend the global his­ tory generation process once the :=:,. has been filled with this information. When all the local interpretations are composed of a limited number of local histories, we are able to enumerate all the candidate global histories HE Hd(J.L). In that case we say that we have an exten­ sional representation. By contrast, the possible inclu­ sion of hyperhistories in the local interpretation forces us to maintain a so called intensional representation, by means of the hyperhistory graph.

Definition 6 (hyper global history) Let HEHd(J.L) be a candidate global history. If there exists a hyperhistory h · E H, then H is called a hyper global history.

Extending the scope of balance to cope with hyper­ histories, requires :=:~-' to record a more complex set of information. Specifically, the codomain of bal­ ance must be represented by a set V including ele­ ments which can be classified as follows (h* denotes either a hyperhistory or a finite set of local histories): V = [true,false,0,h*,(0,0),(h*,0),(0,h*),(ht,h2)] 1 which in turn can be seen as the union of three parts: V \lh,h' U Vh ,h· U "ilh·,h'·, whereby: \lh,h' = [true,false], Vh ,h· = [0,h*J, and \lh. ,h,. = [ (0, 0) , (h*, 0) ,. (0, h*), (hi, h2)], corresponding respec­ tively to the domain of two local histories, a local history and a hyperhistory, and two hyperhistories.

Definition 7 (resolvable hyper global history) Let H* be a candidate hyper global history involving a number of infinite hyperhistories: H* ( h1, h2, ... , hk, hk+l> hk+2> ... , h~) = ( h1, h2, ... , hk) X hk+l xhZ,+2 X·· · Xh~. = [HI,H2, ... ,Hi,Hi+l,···l· Ifit is possible to enforce the interface constraints so that H* is reduced to a finite set H+ = [ H~, H~, . .. , H;] C H*, then H* is called a resolvable hyper global history.

Definition 8 (symbolic intersection) Let hi and h2 be two hyperhistories relevant to the same protective com­ ponent P. The hyperhistory graph corresponding to h* = hi n h2 is called the intersection graph of hi and h2. The process of deriving the intersection graph is called sym­ bolic intersection.

Definition 9 (residue) Let H* be a candidate hyper global history. Let h* E H* be a hyperhistory embraced by H*. Let hi, h2, ... , h~ be the list of reduced hyper­ histories relevant to balance(h;, h*), h; E H*, h; # h*. The residue of h* in the context of H*, denoted by R( h ·, H*), is the symbolic intersection of hi, h2, ... , h~, namely R(h*, H*) =hi n h2 n .. . n h~.

5.1 Global Interpretation Algorithm

The gia global interpretation algorithm can be concisely described as a function having as input a global his­ tory domain Hd(J.L) and returning a global interpretation H*(J.L) ~ Hd(J.L) by means of the following steps:

1. H*(J.L) +-- Hd(J.L);
2. create the consistency matrix :=:~-';
3. by applying balance, associate with each element of :=:~-' a relevant instantiation of a symbol in V;
4. build the inconsistency set SS(31-') as composed of the pairs of (possibly hyper) histories (hi, h 1 ) for which: balance( hi, h1) =false V balance( hi, h1) = 0 V balance(hi,hj) = (0, h1,) V balance(hi,h1) = (hi',0) Vbalance(hi,h1) = (0,0);
5. remove from .the global interpretation those global histories Hincluding a pair (hi, h1) E SS(31-'), namely:
6. H*(J.L) f-- H*(J.L) - [H I :J(hi, hj) ~ H, (hi, hj) E SS(3~-<) ];
7. for each hyperhistory h* of every hyper global history H* E H*(J.L), replace h* with the corre­ sponding residue, namely: VH* E H* (J.L), 'r/h · E H*, h*+--R(h*,H*).

6 Comparison with related work

Several attempts to develop automated support tools for fault diagnosis in power transmission networks are re­ ported in the literature. Somewhat surprisingly, they are based on a variety of different technological approaches including neural networks [Kezunovic et al. , 1994], fuzzy expert systems, [Cho et al., 1994], Petri nets [Wang and Trecat, 1994], model-based diagnosis [Tornielli et al., 1994; Beschta et al., 1993], and temporal reasoning tech­ niques [Baroni et al., 1995].

In [Kezunovic et al., 1994] a neural network is trained to recognize typical fault patterns, by processing in in­ put the values of voltage and current measured in a given substation. Therefore this system aims mainly to pro­ vide a detailed characterization of a local fault, within the context of a specific substation and of its electrical and structural configuration, rather than to perform a diagnosis at the level of the overall network, considering the behavior of the protection system. Moreover, even within this limited context, it seems that a major dif­ ficulty of this approach is related to the huge amount of preliminary work required, since the neural network must be trained on a wide number of different cases each time it has to be applied to a different substation con­ figuration.

In [Cho et al., 1994], explicit relations between the lo­ cation of a fault in the networks and the operation of protections and breakers are represented through sagit­ tal diagrams. Temporal behavior of the components is not considered, however in order to encompass the fact that some protections should operate before others when a fault is located in a given position, a numerical label is associated with each relation, representing the possi­ bility that each protection operates when the fault is in the considered position. Different diagnostic hypothe­ ses can be generated starting from observations and are ranked according to their possibility value. This ap­ proach, not including an explicit model of the diagnosed system, suffers from all the well-known limitations of first-generation, rule-based, diagnostic systems (see for instance a discussion in [Beschta et al., 1993]) .

An alternative approach [Wang and Trecat, 1994] re­ sorts to Petri nets in order to build a model of the pro­ tection system behavior. However this model is over­ simplified: temporal aspects are not considered and the overall protection system behavior is modeled as a sim­ ple two steps activity. More detailed models are used in [Tornielli et al., 1994; Beschta et al., 1993], where a classical model-based diagnosis approach is adopted, us­ ing the GDE+ diagnostic engine [Struss and Dressler, 1989]. The approaches differ in the nature of the model adopted. In [Tornielli et al., 1994], the behavior of net­ work components is defined in terms of equations be­ tween the admittance values seen from different points, whereas the behavior of the components of the protec­ tion system is related to the impedance value seen by the component itself. The approach of [Beschta et al., 1993] is quite similar but a qualitative evaluation of the fault distance is used instead of the admittance value in the component models. A major problem with these ap­ proaches is that the component models adopted, being quite abstract and not very detailed, do not take into account the rather complex behavior of the protection system and are not able to produce detailed diagnoses about its malfunctions.

Detailed models of component behaviors, including temporal features, are used in [Baroni et al., 1995], where an original diagnostic algorithm for time-varying systems is proposed and applied to power networks. This algo­ rithm is able to produce a detailed temporal reconstruc­ tion of the events occurred in the network, but it relies on the assumption that the timestamp of each message received is available, that is not always the case in prac­ tice. By contrast, the approach presented in this paper, while retaining the advantages of using detailed compo­ nent models, does not rely on the availability of temporal information.

An approach whose rationale has some significant sim­ ilarities with the work presented here has been devel­ oped in the frame of diagnosis of communication proto­ cols [Riese, 1993] . In this context the problem consists of verifying, starting from a set of observations, if an implementation of a communication protocol is compli­ ant with its formal definition. The protocol is modeled through a FSM and observations are matched with the possible evolution of the FSM, simulated on a discrete time scale. If none of the possible evolutions matches with the observations, the algorithm searches for modi­ fications of the FSM that can explain the observations: each modification corresponds to a lack of compliance with respect to the standard. A detailed comparison with this work is beyond the scope of the present paper. However it can be noted that, even though the nature of the diagnostic problem is rather different, we share the use of FSM-based techniques, involving observation matching, propagation, and interpretation, in order to deal with complex diagnostic problems of time-varying systems.

This choice differs with respect to other approaches proposed in literature for diagnosis of dynamic systems, a topic that has been addressed by many researchers in recent years [Dvorak and Kuipers, 1989; Gluckenbiehl and Schafer-Richter, 1990; Hamscher, 1991; Ng, 1991; Lackinger and Nejdl, 1991; Dressler and Freitag, 1994] .

As a matter of fact, even though the importance of dynamic system diagnosis and the need of specific tech­ niques for this problem was recognized early [Pan, 1984; Hamscher and Davis, 1984], the classical theory of di­ agnosis [Reiter, 1987; de Kleer and Williams, 1987] has been conceived for static systems only. Subsequent at­ tempts to overcome this limitation have been, however, strongly influenced by the approach initially adopted for static systems. In fact , most of these approaches [Dvorak and Kuipers, 1989; Hamscher, 1991; Ng, 1991; Lackinger and Nejdl, 1991, Friedrich and Lackinger, 1991, Dressler and Freitag, 1994] share a common ra­ tionale: Reiter's algorithm is simply applied iteratively to subsequent instantaneous snapshots of the behavior of the system,, generated through a suitable dynamic model. This method presents however some significant drawbacks, since it is unable to deal with faults whose manifestation involves several time instants and does not exploit efficiently knowledge about system dynamic be­ havior. An approach closer to our ideas is presented in [Gluckenbiehl and Schafer-Richter, 1990] where the di­ agnostic activity for a dynamic system is seen as the task of reconstructing the history of the system starting from some temporally located information about system attributes and using a model of system behavior. How­ ever the behavioral representation adopted is made up of if-then rules including temporal information and suffers therefore from limited expressiveness.

7 Discussion and conclusions

Although featuring an original approach to model-based diagnosis of event-based dynamic systems, the proposed method relies on the availability of correct observations. More precisely, besides the intrinsic unavailability of messages, the method can cope with lost messages, but it assumes that those messages which are available are correct. The knowledge about possible missing messages must be specified in the model, as illustrated in Sec­ tion 2. Intuitively, the richer is the set of observations, the smaller is the number of diagnostic alternatives pro­ duced. Furthermore, the algorithm is clearly designed for domains where discrete (and complete) models of cor­ rect and faulty behaviors are available.

Another important point concerns the resolvability of hyper global histories, which can be guaranteed by en­ forcing some safety constraints on a reactive model M. Intuitively, safety may be achieved when either no silent cycles are incorporated in M or when, under additional assumptions, interface events are associated with silent transitions within silent cycles.

Finally, a formal analysis of the complexity of the method and real benchmarks of the implementation are expected for the future. However it is already evident that the performance of the algorithm will strongly de­ pend on the complexity of the reactive models exploited, and the extent to which they allow an accurate inter­ pretation of the available observations. It is also worth pointing out that local interpretations might in principle be generated in parallel, either by a single parallel ma­ chine or by several machines installed in different sub­ stations.

Acknowledgments

The present work is partially supported by the Commis­ sion of the European Union under the ongoing Esprit III Project 8491 Timely (Time-Constrained Integrated Management of Large-Scale Systems).