Abductive Validation of a Power-Grid Expert System
12José Ferreira de Castro and Luís Moniz Pereira
Centro de Inteligência Artificial – CENTRIA
Universidade Nova de Lisboa
Monte da Caparica
2889-156 Caparica, Portugal
Abstract. Transportation of electrical energy is normally made through a
network of high-tension lines. In case of an incident, the electrical protections at
both ends of a line are activated. Most of the incidents are short-lived, and can
be solved by fast automatic reclosure of the breakers. When automatic reclosure
fails, or does not happen, a timed reclosure is attempted after a few minutes,
either manually or by automatic systems. When an incident occurs, several
hundred messages sent by the substations can reach the control centers within a
few seconds, making the human operator’s interpretation of the incident very
difficult. The purpose of the previously developed SPARSE (Expert System for
Incident Analysis and Power Restoration Assistance) is to assist the human
operators in handling the emergency situations, giving them readable and
accurate information. SPARSE is based on a logic programming inference
engine reasoning over a set of time-stamped events. The new problem we
addressed was how to validate the inference rules of SPARSE, by showing that
no set of real events and diagnoses could be abduced that would violate the
physical and logical integrity constraints of the problem domain, in order to
certify the correctness of SPARSE with respect to the desired constraints. In
this paper we examine how the sophisticated abductive logic programming
system ABDUAL was employed for this purpose, and the practical tools
developed and implemented to that end.
Keywords: Expert Systems
Introduction and Historical Overview
Transportation of electrical energy is normally made through a network of high-tension lines. In the case of a short-circuit in a line, the protection at both ends is activated. Natural causes (birds, lightning, storms, etc) can originate incidents that are short-lived and are immediately solved by the fast automatic closure of the breakers. When an automatic reclosure fails, or does not exist for that particular line, a timed reclosure is attempted after a few minutes, either manually or by automatic systems.
1 firstname.lastname@example.org 2 email@example.com Contact author
When a serious incident occurs, several hundred messages from the electrical substations, reporting the opening and closing of the circuit-breakers, can reach the control centers in a few seconds. The human operators can be flooded with raw information, quite difficult to read and interpret in real time. The purpose of SPARSE (Expert System for Incident Analysis and Power Restoration Assistance), based on logic programming, is to assist the human operators in handling the emergency situations, giving them readable and useful information.
One can find technical descriptions of SPARSE in the bibliography [1-9]. The system gathers basic information about the state of the network through a system called SCADA (Supervisory Control and Data Acquisition), and processes this information through a data-driven inference engine that offers in real-time the needed interpretation of what is going on. SCADA was first installed in the portuguese electrical network in 1988-89, and was totally remodeled in 2000. The SPARSE system, was actually used in one of the control centers in the north of Portugal, and is now being adapted to the new SCADA configuration. All comments made in this paper refer to the former version of SCADA.
Before being used in real-time mode, SPARSE was tested off-line using sample data gathered from real incidents. Some validation and verification tools were used to detect possible errors in the rule structure of the SPARSE inference engine, reported in [10-12]. But none of these tools can guarantee that an undesired conclusion may not appear due to an unforeseen configuration of the basic SCADA data.
The possibility of applying abduction techniques to SPARSE were studied as part of a master‟s thesis in AI at Universidade Nova de Lisboa (UNL) in 2000 . These
techniques (using ABDUAL ) were developed at the Artificial Intelligence Centre (CENTRIA) of UNL, and a formal extended presentation (in Portuguese) can be found in the thesis, and are here reported for the first time in English.
The goal of applying abduction is twofold. First, we wish to identify all the possible
hypothetical scenarios of the SCADA messages leading to a given conclusion of the SPARSE inference engine. This abductive reasoning allows us to verify that no unexpected and undesired sequences of events can bring about an untoward conclusion, one that violates physical and logical integrity constraints of the problem domain. Second, we wish to find the SCADA scenarios that are needed to achieve some given untoward conclusion. If the set of SPARSE inference rules is sound, these scenarios should be physically impossible to achieve, meaning there should be no realizable physical abductive explanation for them. Otherwise, the inference rules must be corrected on the basis of the abductive scenarios found.
The advantage of abductive reasoning over a set of tests with real data is obvious: it is hard to guarantee any set of tests is complete enough to cover all possible SCADA message configurations. Abduction, on the contrary, lists all possible explanations for a certain conclusion, being akin to model verification. This assurance is essential for the confidence of the final user in the SPARSE system. The results obtained showed the pertinence and usefulness of the abductive approach. The work done was of a very
practical nature, building bridges between existing implemented systems, SPARSE on the one hand, and the logical programming abductive machinery on the other. How SPARSE Works
To understand the challenges involved and the usefulness of the abductive approach, it is worth going a little into some of the details of SPARSE. The set of SPARSE rules used to test the abductive verification concept was a development version, because of copyright restrictions. This was actually convenient to verify the usefulness of abduction to detect potential problems in the version under development.
SPARSE is basically an inference engine reasoning over time-stamped events given by SCADA. For instance, SPARSE uses the time interval between the opening and closing of a circuit-breaker to conclude whether it was a manual or an automatic reclosure. A first production rule says that if the time interval is less than half a second, then the reclosure is automatic. Another production rule says that if the time interval is less than five seconds, then the reclosure is manual. Both rules are triggered by the same event - the opening of the circuit-breaker - and are scheduled to look for data and produce their respective conclusions after a certain amount of time compatible with the time conditions in the rules. In this case, a delay of half a second is necessary for the first rule, and of five seconds for the second. If the first rule succeeds, it takes out from the dynamic database the SCADA facts it used, and the second rule will therefore not succeed.
The main set of messages sent by SCADA is very simple: it gives information about the opening and closing of the circuit breakers, with a special separate message for the breakers‟ sudden opening due to a surge of current (a short-circuit). SCADA sends
also information about the status of the installations where the breakers are located: if they are in local or remote control mode, and in automatic or manual mode. These SCADA facts and the time conditions in the inference rules of SPARSE were chosen to become the abducibles (i.e. the basic facts for the abductive explanations).
Using the basic facts, SPARSE builds up a first level of very simple conclusions, and then uses the first level conclusions and other basic facts to build up more general conclusions of what is going on in the power grid. An important difficulty SPARSE has to deal with is the time attached to each SCADA event: it is not the time of the event itself, but the time when the SCADA information reaches the control centre. Because of unpredictable delays in the transmission, the recorded order of events can be different from what really happened. SPARSE needs to work on the basis of the time proximity of events (using often the module of time differences), but cannot reason with confidence over the order of events reaching the control centre in short intervals of time.
We saw above, in the example for automatic/manual reclosure, that each SPARSE rule is triggered by one of the events sent by SCADA. The actual activation of the
rule and production of conclusions is generally delayed by a predefined time interval, in order to allow for the other relevant facts, listed in the body of the rule, to be recorded in the database. Two or more production rules can be triggered by the same event, with different activation delays. When a set of conclusions is produced by a rule that succeeds, its trigger and the other relevant facts to be retracted from the dynamic database are explicitly indicated in the head of the rule (actually they are changed to “old-facts” for possible analysis). Conclusions are also time-stamped, and
are normally assigned the time of one of the SCADA facts used in the rule.
Rules using the same SCADA triggers to reach different conclusions will therefore be logically linked through the removal of data. In the above example, one can notice that the time conditions for manual or automatic reclosure are not exclusive. They overlap, and the SCADA programmer relied on the removal of data to avoid both rules succeeding. But since SCADA is continuously adding facts to the database, we may need physical considerations to get an assurance that no undesired facts are present when the rule for manual mode is activated. Let us suppose that the two rules for automatic/manual reclosure were triggered at time 0 by the opening of a circuit-breaker. A reclosure 0.3 seconds later would make succeed the rule for automatic reclosure (activated at time 0.5), erasing from the dynamic database the opening and closing information of the circuit-breaker. But we can still imagine a second short-circuit, say 4.6 seconds after the first one, followed by an automatic closure of the circuit-breaker at time 4.9. This would add to the database two SCADA facts allowing the rule for manual to succeed (activated at time 5.0), while the new rule for automatic (triggered at time 4.6 and activated at time 5.1) would fail. This problem could be solved by having SPARSE (a) check the correct time distance of the trigger found by the rule, or (b) by changing the time conditions of the rules to avoid the overlapping or (c) by checking the absence of a previous conclusion for automatic. These and many other even subtler complexities of SPARSE are typical of a program built over a dynamic database heavily using asserts and retracts.
ABDUAL, an implemented abductive goal directed and tabled proof procedure under the well-founded semantics, needs a static set of rules to work with at any one time. A correct translation of SPARSE production rules into the adequate static rules is of the essence, and probably the most delicate and difficult step. How can we guarantee the translated static rules have the same meaning that the SPARSE rules have? In a direct translation we cannot, since there is vital information that cannot be found by a simple examination of the SPARSE rules. For instance:
a) The information about the delays and the triggers that activate the rules is not explicitly indicated within the rules. The resulting priorities among rules (which rule is activated first?) cannot therefore be subjected to an automated translation. b) As we saw in the example above, rules are logically linked by the creation and deletion of dynamic variables.
c) Some SPARSE rules produce multiple conclusions from a given set of SCADA events. Not all events in the body of the rule are related to a given conclusion. For instance, an inference rule can produce the conclusion that a local manual closure was performed after a short-circuit that occurred in a substation. Since both conclusions (the opening due to the short-circuit and the manual closure) are produced by just one rule, abductive reasoning will be unable to distinguish the SCADA facts in the body of the rule pertaining to each conclusion. This needs to be understood and handled through splitting of the original rules.
d) Physical constraints do not appear anywhere in the rules. In the example above, a possible flaw in the rules was imagined supposing two incidents can occur in less than five seconds for the same circuit-breaker. If this is physically impossible, the problem does not exist at all.
A possible alternative is to try to perfectly model the dynamic behavior of SPARSE, including the implicit physical constraints, and translating it into a static logical program well-suited for ABDUAL analysis. But the problem persists: how can we be sure our model reflects all the subtleties of SPARSE behavior? To achieve this assurance, we need a perfect understanding of the way SPARSE interacts with real situations. But if we reach a perfect understanding, we need no further analysis tools. A compromise to gradually reach a better understanding of SPARSE was made, using the following approach:
1. A program was developed to make a fast direct translation of the SPARSE rules into a format that could be utilized by ABDUAL.
2. ABUAL was used to rapidly calculate abductive scenarios for chosen conclusions. 3. The abductive scenarios were then examined, explained, and criticized. Some undesired aspects could be explained by the lack of information, while other aspects could be related to problems in the structure of the SPARSE rules.
4. Adequate modifications were introduced in the original SPARSE rules, and then back to step 1.
The advantage of this approach is that it was simpler to analyze and understand the ABDUAL output than to try to understand directly the SPARSE rules. We started with simple subsets of SPARSE rules, and gradually enlarged this set. An example of a SPARSE rule, together with its direct translation, is given in Appendix A. An example of ABUAL output is also given in Appendix A. For larger sets of rules, this output can become fairly large and hard to read. Some tools were developed in order to quickly analyze the abductive explanations. E.g., we can find answers to the following question: What is the simplest explanation? Are there elements common to all explanations? Are there explanations that are just extensions of simpler ones? Etc.
The production rules of SPARSE often present the chicken-egg type of circularities. For instance, to produce the conclusion that an installation shifted to manual mode, a previous conclusion that it had shifted before to automatic mode must be present in the database. Conversely, to produce the conclusion that an installation shifted to automatic mode, a previous conclusion that it had shifted to manual mode must be present in the database. When we apply abductive reasoning to this type of situations,
we get an infinite regression of explanations (in this case simple WFS circularity detection is not enough because events are time-stamped and thus no actual circularity exists). It is nevertheless possible to obtain a satisfactory solution to this problem using an alphabetical similarity criterion of the abductive explanations to stop the generation of new steps (see the Appendix B for an example of how well-founded semantics deals with other circularities). One must be nevertheless very careful to avoid the undesired masking of explanations caused by similar events coming from different inference rules. Tagging the abducibles with a code that identifies the corresponding rule introducing each one solved this problem, and helped to trace the abductive chains of explanations.
Conclusions and Future Work
One could wonder about the usefulness of an abductive approach in this setting. We obviously need a good understanding of how SCADA and SPARSE work to analyze properly the abductive scenarios given by ABDUAL. When we modify the SPARSE rules we are already starting a debugging process, but we need to understand what we are doing. We initially took SPARSE as-is, without any purpose of improving the rules, but the study carried out suggests that ABDUAL can indeed be most useful in the development phase of this type of programs. We found that if the inference engine is designed having from the start abduction clarity and simplicity in mind, rules are simpler to understand and easier to verify. Since the confidence of the network operators in the correctness of the set of rules is paramount, abduction is a very useful and effective tool to increase the level of confidence in SPARSE for real-life situations.
The utilization of ABDUAL imposed some simple and obvious strategies to limit the number of explanations. Avoiding not‟s in the body of the SPARSE rules is important,
because the number of explanations for a certain fact to be absent is normally much larger than the number of explanations for a fact to be present. It is also better to avoid wherever possible the use of uninstantiated variables in the body of rules. Nevertheless, the implementation of ABDUAL that was employed in this study had a very interesting feature, “constructive negation”, which allows for uninstantiated variables under default negation. The basic idea is that the negation of a fact “f(c)” can be expressed by “f(V),V\=c”, to the effect that V is a variable whose values are distinct from “c”. Thus the goal “not f(V)” evaluates to “f(V),V\=c”, if the only
negative instance for “f(V)” is “c”. Of course, constructive negation must deal with all the other more complex cases arising in a logic program, but that is not the subject of this presentation.
In conclusion, ABDUAL was put to use to detect specification inconsistencies in model-based diagnosis system for power grid failure. Abduction was employed to attempt to abduce hypothetical but physically possible events that might cause the diagnosis system to come up with a wrong diagnosis violating its specification constraints. The method is akin to the model verification stance: One strains to abduce
a model, comprised of abduced physical events, which attempts to make the diagnostic program inconsistent. If this cannot be done, the power grid diagnoser can be certified correct.
The aim of our abductive application was indeed to certify that a given expert system diagnosis module was provably correct with respect to foreseen physical events. To wit, the diagnosis logic program was executed under ABDUAL in order to establish that no sequence of (abduced) physically coherent events (ie. monitoring messages) could be conducive to a diagnosis violating the (temporal) constraints expected of a sound diagnosis.
This proved to be feasible, though it required us to introduce a constructive negation implementation of ABDUAL, not reported here, because the abduced message events had to be time-stamped with temporally constrained conditions, but not anchored to specific temporal time-stamp constants, and occurred often under default negation literals to the effect that no supervening event occurred in some relative time interval. The system, the application, and its use are described in detail in .
A number of open problems worthy of exploration remain in this class of problems, susceptible of furthering the use of the general abductive logic programming techniques brought to bear.
SPARSE System. There is a Web page dedicated to the training and information of power central operators, called Project Satoren. SPARSE is part of this project. The Web address is: http://www.cim.isep.ipp.pt/Projecto-SATOREN/. There one can
find several technical reports, some of them related to SPARSE.
 Z.A.Vale, A.M.Moura,"An Expert System with Temporal Reasoning for Alarm Processing in Power System Control Centers", IEEE Transactions on Power Systems, vol. 8, No. 3, pp. 1307-1314, 1993.
 Z.A.Vale, A.M.Moura, M.F.Fernandes, A.Marques,"SPARSE- An Expert System for Alarm Processing and Operator Assistance in Substations Control Centers", Applied Computing Review, 2(2), pp.18-26, ACM Press, 1994.
 Z.A.Vale, M.Fernanda Fernandes, C.Rosado, A.Marques, C.Ramos, L.Faria, "Better KBS for Real-time Applications in Power System Control Centers: What can be learned by experience?", 1st Int. Conf. on Successes and Failures of Knowledge-Based Systems in Real-World Applications, Bangkok, 1996.
 Z.A.Vale, L.Faria, C.Ramos, M.F.Fernandes, A.Marques, "Towards More Intelligent and Adaptive User Interfaces for Control Center Applications", Int. Conf. on Intelligent Systems Applications to Power Systems (ISAP'96), Orlando, Florida, pp. 2-6, 1996.  Z.A.Vale, C.Ramos, L.Faria, J.Santos, M.F.Fernandes, C.Rosado, A.Marques, "Knowledge-Based Systems for Power System Control Centers: Is Knowledge the Problem?", ISAP'97, pp. 231-235, 1997.
 Z.A.Vale, A.M.Moura, M.F.Fernandes, A.Marques, C.Rosado, C.Ramos, “SPARSE: An Intelligent Alarm Processor and Operator Assistant”, IEEE Expert, vol.12, no. 3, Special Track
on AI Applications in the Electric Power Industry, pp. 86-93, 1997.
 Z.A.Vale, C.Ramos, A.Silva, L.Faria, J.Santos, L.M,Pinho, M.F.Fernandes, C.Rosado, A.Marques, "SPARSE – An Expert System for Power System Control Center Operator
Assistance and Training", 4th World Congress on Expert Systems – Application of Advanced
Information Technologies, ITESM, Mexico City, 1998.
 Z.A.Vale, C.Ramos, A.Silva, L.Faria, J.Santos, M.F.Fernandes, C.Rosado, A.Marques, "SOCRATES- AN INTEGRATED INTELLIGENT SYSTEM FOR POWER SYSTEM
CONTROL CENTER OPERATOR ASSISTANCE AND TRAINING", IASTED Int. Conf. on
AI and Soft Computing, Cancun, Mexico, 1998.
 Z.A.Vale, C.Ramos, L.Faria,"User Interfaces for Control Center Applications", The 1997 Int. Conf. on Intelligent Systems Applications To Power Systems (ISAP'97), Seoul, pp. 14-18, 6-10 July, 1997.
 J.Santos, L.Faria, C.Ramos, Z.Vale, A.Marques,"VERITAS– A Verification Tool for
Real-time Applications in Power System Control Centers", In Procs of the 12th Int. Florida AI Research Society (FLAIRS'99). 511-515. Orlando, Florida, 1999.
 J.Santos, C.Ramos, Z.Vale, A.Marques, "Validation and Verification of Knowledge-Based Systems for Power System Control Centres", In Procs of the European Symp. on Verification and Validation of Knowledge Based Systems (Eurovav'99), Oslo, 1999.  Z.A.Vale, J.Santos, C.Ramos, M.F.Fernandes, C.Rosado, A.Marques,"SPARSE - A Prolog Based Application for the Portuguese Transmission Network: Verification and Validation", 5th Int. Conf. on the Practical Application of Prolog - PAP 97, pp. 291-310, London, 1997.  J.J. Alferes, L.M. Pereira, T. Swift, “Abduction in Well-Founded and Generalized Stable
Models Via Tabled Dual Programs”, Procs. 16th Int. Conf. on Logic Programming (ICLP'99),
pp. 426-440, MIT Press, Las Cruces, New Mexico, 1999. http://centria.di.fct.unl.pt/~lmp/
 J.F. Castro, Verificação Abdutiva de Um Sistema de Diagnóstico Baseado em Regras, Master‟s thesis in AI, Universidade Nova de Lisboa, 2000. http://www.cs.sunysb.edu/~tswift
We present here an example of a SPARSE rule, with its corresponding translation suitable for abduction. SPARSE rules are written using a specific grammar, developed for this purpose. The first line is a tag identifying the rule, with a short description of the type of event the rule detects. The next lines are separated by conjunctions (“and”)
and disjunctions (“or”). This rule identifies an opening of a circuit breaker by manual remote control in two cases: First, if there is an opening of a circuit-breaker (identified by a breaker code „10‟ coming from SCADA) that cannot be associated
with a short-circuit opening (identified by a trigger code „01‟ message from SCADA), because the module of the time interval is larger than 0.3 seconds; Second, if there was an opening of a circuit-breaker without a short-circuit opening being present in the database. The installation also needs to be in manual and remote mode. The breaker opening message is the trigger for the rule. Conclusions in the head of the rule are separated from the body of the rule by the symbol ==>. In this case, two messages are retracted (with the functor “retract-fact”), and a new fact is added (with the
“create-fact” functor). Important new facts are also displayed on the control centre monitor, using the functor “write_message1”. rule j2 : 'OPENING OF BREAKER BY REMOTE CONTROL' : [[ message(Date1,Hour1,[Inst1,Panel1,[Inst2,NL,'BREAKER']],'BREAKER', '10') at T1 and message(Date2,Hour2,[Inst1,Panel1,[Inst2,NL]],'>>>TRIGGERED', '01') at T2 and condition(mod_diff_times_greater(T2,T1,30)) and manual(_,_,Inst1) at T3 and remote(_,_,Inst1) at T4] or [message(Date1,Hour1,[Inst1,Panel1,[Inst2,NL,'BREAKER']],'BREAKER', '10') at T1 and not message(Date2,Hour2,[Inst1,Panel1,[Inst2,NL]],'>>TRIGGERED', '01') at T2 and manual(_,_,Inst1) at T3 and remote(_,_,Inst1) at T4]] ==> [retract_fact(breaker(_,_,Inst1,Panel1,_,_,closed),_,T1), create_fact(FactNo,breaker(Date1,Hour1,Inst1,Panel1,_,remotecontrol, opened),T1), write_message1(FactNo,Date1,Hour1,Inst1,Panel1, [(200,’opening of breaker by remote control')]), retract_fact(message(Date1,Hour1,[Inst1,Panel1,[Inst2,NL,'BREAKER']], 'BREAKER','10'),T1,T1) ].
The automatic translation will prepare static rules (j2-1 and j2-2) with ABDUAL syntax for each disjunction and each newly created fact. In this case, only the second line in the head of the rule actually creates a new fact, which will be used by other rules (this line is indicated within the comment with “production 2”). Doing so, we can easily trace how the translation was achieved, and to what disjunction and head line it refers to. Retracted facts are ignored, since their relationship with other rules must be found using information not available at this level. The resulting translated rules are:
/* j2-1 production 2 */ fact(breaker(Inst1,Panel1,Inst2,remotecontrol,opened), T1) <- fact0(j2,1,2,message(Inst1,_Panel1,[Inst2,NL,breaker]],breaker,io),T1, fact0(j2,1,2,message([Inst1,Panel1,[Inst2,NL]],triggered,oi),T2), condition(j2,1,2,mod_diff_times_greater(T2,T1,30)), fact(manual(Inst1),T3), fact(remote(Inst1),T4). /* j2-2 production 2 */ fact(breaker(Inst1,Panel1,Inst2,remotecontrol,opened), T1) <- fact0(j2,2,2,message([Inst1,Panel1,[Inst2,NL,breaker]],breaker,io),T1,
not fact0(j2,2,2,message([Inst1,Panel1,[Inst2,NL]],triggered,oi),T2), fact(manual(Inst1),T3), fact(remote(Inst1),T4).
From here onwards the ABDUAL implementation works in two steps: First it adds the corresponding dual rules to these translated rules; Then it allows the user to query the transformed program. A typical query would be:
?- absp(fact(breaker(inst1, panel1, i2, remotecontrol, opened),tc)).
This query sends the abductive solutions to a file that can be read by the user and further processed by the specifically developed analysis tools. Here are the basic solutions given:
fact0(j2,2,message([inst1,panel1,[ _h687,_h688,breaker]],breaker,io),tc) not fact0(j2,2,message([inst1,panel1,[_h687,_h688]],triggered,oi),T2)
The first two arguments in each fact indicate the rule and the disjunction inside the rule to which it is related. The other arguments describe the SCADA messages or time conditions that explain the SPARSE conclusion. In this solution we see that two other rules besides j2 are used in the explanation. The first line says the installation is in remote control, the second it is in manual mode, the third identifies the opening of the circuit-breaker, and the last indicates de absence of a short-circuit triggering the automatic opening of the circuit-breaker. In this case there was an incident in T1 that triggered the circuit-breaker, but too distant in time to be related to the opening in tc.
Circularities can be easily handled by ABDUAL, through working over the Well-Founded Semantics (WFS). Consider the following example:
abds([f/0]). f1 ; f, f2. f2 ; f, f1.
where f/0 is declared to be abducible. The queries ?- ab(f1,S) and ?- ab(f2,S) are both answered “no” in the ABDUAL implementation. This is in agreement with WFS, because literals involved in positive loops are considered false. However, the query ?- ab(not f1,S) gives the following solution S = [ ] * [not f] + [ ]. It is not a minimal solution, in the sense that the positive circularity is a sufficient condition to impose not f1. But ABDUAL does not obtain only minimal abductive solutions, this being one of its strengths, since not always does one desire minimality, often one does not want to pay for minimality, or the number of solutions may be infinite. Also, if no abducibles are found or given, the complexity of ABDUAL remains polynomial, because it retains the complexity of WFS. See  for more elaborate examples.