Failure Processing in a System for Designing Complex Assemblies
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
© 1979 International Joint Conferences on Artificial Intelligence
Abstract
We believe that the capacity to recover intelligently from intermediate failures and to learn from these failures is an essential ingredient of attempting to solve complex real-wor~d problems. Intelligent failure recovery requires the problem-solver not only to diagnose the causes of its failures, but also to cmrcumscribe carefully the propagation of recovery updating . Learning from failures requires that the problem-solver remember the conditions of its failures in such a way that it will not recreate these conditions. In this paper, we describ e method s providing such capabilities. We have implemented and eXPerimented with thes e methods in a rulebased system used for designing complex assembli e s such as electromechanical e quipment.
- R.DAVIS, B.G.BUCHAtlAN(1977):"Metal-level knowledge : Overview and applications", IJCAI 77, Cambridge, 1977.
- J.OOYLE(1977) : "Truth-maintenance systems for problem solving", Haster thesis, HIT, Cam- bridge, 1977. IJCAI
- P.HAYES(I975) :"A representation for robot plans", IJCAI 75, Tbilisi, 1975. IJCAI
- J.C.LATOUBE(1976) :"Artificial Intelligence in computer-aided design: the TROPIC system" SRI AIC, Technical note 125, Hclhlo Park, January 1976.
- J.C.LATDrffiE(I977):"Unc application d~ !'In- telligence Artificielle a la conc~ption assistee par ordinateur (TROPIC)", These d'Etat, Grenoble 1977 (in French).
- J.C.LATOlffiE(I979):"Problcm-solvinp. methods in a system for designing complex assemblies" Rapport de recherche !HAG, Grenbble, 1979 (in preparation).
- D.V.lfcDERtf.lTT(1977):"Flexibility and <' ffi.- ciency in a computer program for designing cir- cuits", AI Lab. TR 402, HIT, Cambridge, June 77.
- N.J.NILSSON(197l):"Problem-solving methods in Artificial Intelligence", HcGraw-Hill, 1971.
- E.D.SACEROOTI(I977):"A structure for plans and behavior", American Elsevier Pub! ishing Company, 1977.
- R.STALLHAN, G.J.SUSSHAN(I976):"Forward Rea- soning and dependency-directed backtracking in a system for computer-aided circuit analysis", lHT AI Lab, Hcmo 380, Cambridge, September 1976.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
FAILURE PROCESSING IN A SYSTE~~ FOR DESIGNING COMPLEX ASSEMBLIES
Jean-Claude LATOMBE
ntAG, BP 53 X, 3804 I GRENOBLE cedex France
We believe that the capacity to recover intelligently from intermediate failures and to learn from these failures is an essential ingredient of attempting to solve complex real-wor~d pro blems. Intelligent failure recovery requires the problem-solver not only to diagnose the causes of its failures, but also to cmrcumscribe carefully the propagation of recovery updating . Learning from failures requires that the problem-solver remember the conditions of its failures in such a way that it will not recreate these conditions. In this paper, we describe methods providing such capabilities. We have implemented and eXPerimented with these methods in a rule based system used for designing complex assembli es such as electromechanical equipment.
I. INTRODUCTION
A traditional difficulty in automating the pro blem-eolvinp, process is that of dealing with the combinatorial eXPlosion of the search space. Another difficulty is the difficulty of handling large amounts of domain-dependent knowledge. In this paper, we present new methods for coping with both these difficulties simultaneously.They combine a search representation based on the di~ tinction between control data and logical data, and procedures working with this representation that facilitate selective recovery and learning from failures. The recovery ·procedure diagnoses the causes of the failures in order to perform selective backtracking and the representation makes it possible to circumscribe carefully the propagation of recovery updating. This combina tion turns out to be particularly important in reducing unnecessary operations on knowledge.
We have implemented and experimented with these methods in a rule-based system named TROPIC, a problem-solving tool for designing complex as semblies such as electromechanical equipment[4]. Problems with which this system can deal con sists of generating models of devices. TROPIC is not restricted to a particular discipline, and we have used it to design e lectric power transformPrs among oth<'r applications [5]. This appl i cad on required us to Pncode 1 arge amounts
This work was carried out under contract IRIA/SESORI n° 77052
of special-purpose knowledge (about 350 rules) related to such fields as electricity, electro magnetism, mechanics and thermodynamics. Only a few aspects of TROPIC are presented here.More detailed descriptions can be found in r5J & [6].
Although we claim originality for the methods to be discussed in this paper, the fundamental issues underlying these methods arc not new in Artificial Intelligence. For example, the dis tinction between control data and logical ·data has been an important aspect of NOAHr9J; failure diagnosis and learning has been studied in EL/ARS [10]. Re lations of TROPIC to these works will be discuss ed in Section 8.
2. OVERVIEW OF THE PROBLEU-SOLVING IDDEL USED BY TROPIC
The problem-solving model used by TROPIC is based on the concurrent execution of a problem-solving process; wh ich we call "task-reductive synthesis" and a deduction process, which we call "fact deduct iv.:~ analysis" :
- Task-reductive synthesis consists of assu mi ng facts about a potential device (for example the type of components, the connection between these components and the values of various para meters), whil e partitioning a given "ini t ial task" into successive subtasks. For example,if the problem is to design a transformer tr l , a step of this process might be to assume that parts of trl are a magnetic circuit mel and an electrical circuit eel, and to reduce the task "design transformer trl" into three subtasks, "design magnetic circuit mel", "design <> l ectri cal circuit <>c l" ancl "se lect a cooler for trl".
One can regard the facts that are assumed when a task is reduced as a solution to this t~sk at some level of abstraction, and task-reducrive synthesis as a process of adding succesJi·edetail to a description. The system may have to choose among alternative ways of partitioning the same task, each of them corresponding to different assumptions. For example, the task "select a ~ooler for trl" may be reduced to the empty set by assuming that trl's cooler is air; it may also be reduced to the sub task "design tank tk I" based on the assumption that trl 's cooler is oil, and that it is contained in a tank tkl. As we will see next, some combinations of choices may produce contradictions.
- Fact-deductive analysis consists of dedu cing new facts from the assumed facts and a ·con troling the consistency of the set of both assu med and deduced assertions. Deductions are made by using such kinds of knowledge as constraints and approximations to physical laws. For exam ple, the design constraints "if air is the coolar of a transformer, then the voltage between the terminals of any coil in this transformer must be lower than 3KV ; otherwise it must be lower than SKV" may be used to deduce the fact "the voltage between the terminals of ell is lower than SKV" from the facts "the cooler of trl is oil","cll is a part of trl" and "ell is a coil". Contrad~ctions among assumed and deduced facts produce failures, from which the system recovers by resum1ng task-reductive synthesis at a pre vious decision point. For example the facts " . the number of turns of ell is 3SO","the voltage per turn of ell is 18V","the voltage between the terminals of ell is lower than SKV", and "the voltage between the terminals of ell is equal to the number of turns of ell times the voltage per turn of ell" are contradictory facts.
A problem is specified as an initial task, a set of synthesis rules to be used for task-re ductive synthes1s, and a set of analysis rules to be used for fact-deductive analys1s. It 1s solved when the initial task has been reduced to the empty set in such a way that no contradic tion derives from the assumptions generated by this reduction.
3. TASK-REDUCTIVE SYNTHESIS
3.1. Form and use of synthesis rules
Knowledge for task-reductive synthesis is repre sented in TROPIC by means of synthesis rules. The form of these rules is the product1on :
- t => ( { f I , ... , fm} , { t I , ... , tn}) where t, t I, ... , tn (n ~ 0) are expressions representing tasks and f I , ... , fm (m ~ 0) are expres sions representing facts. The right-hand side may also be a function that evaluates to the ex pression ({fl, ... ,fm}, {tl, .·. ,tn}).
The production uses to c6ntain variables that are instantiated when it is applied.
Given an initial task and a set of synthesis ru+ .· les, task-reductive synthesis proceeds according to a depth-first search by successive expansion of an AND/OR tree, which we call task-reduction ~· The AND nodes of this tree are labeled with instantiated tasks, and its OR nodes are la beled with instantiated synthesis rules. At every moment during the problem-solving process, this tree represents the partitioning of the initial task that is currently considered by the system.
Initially, the task-reduction tree consists of a sinRle node that is labe led with the initial tas~ Next, each expansion of the tree is carried out by applying a synthesis ru~e such that the task in its left-hand side matches the task asso~iated to a pending AND node N of the current tree. The following two operations are then executed : (I) An OR node N' is added to the tree as a suc cessor of N, and the instantiated synthesis rule is associated with it.
- Each task in the right-hand side of the ins tantiated rule is associated with an AND node that is added to the tree as a successor of N'· if the set of tasks in the rule's right-hand ' side is empty, then N' is a terminal node.
Simultaneously, the facts contained in the rule's instantiated right-hand side are entered into a factual data base as new assumptions about the dev1ce be1ng designed.
The task-reduction tree is terminal when all its pending nodes are terminal nodes. If there is no contradiction in the factual data base, the pro blem is solved then. TROPIC applies various ge neral -purpose and input domain-specific heuris tics to guide task-reductive synthesis [6].
3.2. Examples
These synthesis rnles correspond to the informal examples of section 2 :
SYI:(design-transformer &tr) => (progn (setq &me (!me)) (setq &ec (! ec)) (i&({(part-of &tr &me), (=(is-a &me) magnetic-circuit), (part-of &tr &ec) , (=(is-a &ec) electrical-circui~}, {(design-magnetic-circuit &me), (design-electrical-circuit &ec), (select-cooler-for &tr)}))) SY2:(select-cooler-for &tr) => .(progn (setq &tk (! tk)) (i&({(=(cooler-of &tr)oil), (part-of &tr &tk), (=(is-a &tk)tank)}, {(design-tank &tk)})))
SY3:(select-cooler-for &tr)
=> ({(=(cooler-of &tr) air)},nil)
[ Comment : When rule SYI is applied, the varia ble "&tr" (all atoms prefixed by "&" are varia bles) is firtt bound to a constant (for example: "trl") by unifying the left-hand side of the rul e with an instantiated task ; next, the right-hand side of the rule is evaluated. This evalu~tion binds the variables "&me" and "&ec" to constants (for example "mel" and "eel") generated by evalua ting (!me) and ( !ec) (" !" generates a new atom each time it is evaluated by concatenating its quoted argument and an integer). The evaluation of thE\ TROPIC function "i&" then returns the ins tantiated expression ({(part-of trl mel), ... }, {(design-magnetic-circuit mel), ... }). When rule SY3 is applied, its right-hand side is merely instantiated).
About 100 synthesis rules were necessary to run the transformer eKample.
3.3. Fundamen~al aspects of task-reductive synthesis
Task-reductive synthesis explicitly represents the problem-solver's control state (the task-re duction tree) and logical state (the factual dat? base). At any moment, the logical state containf the facts that are currently believed to be true by the system, while the control state records both the choices on which these beliefs ·are based and the control dependencies among these choices. This twofold representation may be regarded as a combination of the "state-space" and "problem-re duction" representation[ 8]. The failure recovery procedure used by TROPIC draws much of its power from the following two possibilities :
I - When a choice is rejected, the explicit knowledge of the current control state permits the system to circumscribe the extent of the updating necessary. Only that part of the task-reduction tree which is rooted at the rejected choice,and the subsequent assumptions, need to be discarde~ Other choices can be kept effective even if they arc more recent choices. This possibility may save a lot of effort reintroducing large parts of the solution that were needlessly discarded. It is not provided by the state-space representatio~ at least in an easy way.
2 -The logical state permits tne system to consider the combined effects of the individual choices recorded in the control state . Choices, which may not be linked among them by control de pendenci es, may concur to generate contradictory assertions, so that the maintenance of the logi cal state's consistency permits tne system to ta ke into account logical dependencies among such choices. This possibility to consider transver sal interactions among choices is critical becau~ the hypothesis according to which design tasks a~
reducible to independent subtasks would be unre a listic. Its is not p~ovided by the probl em- r edu c tion representat i on.
4. FACT-DEDUCTIVE ANALYSIS
4.1. Form and use of analysis rules
Knowledge for f act-deductive anal ysi s i s rcprese~ ted in TROPIC by means of analysi s rul cs . Thc form of these rules is the production
{fl, ... ,fm} => {fl', ... ,fn'} where fl, ... ,fm, fl', ... ,fn' (m ~ O, n ~ O) ar c expressions represent i ng facts. The r ight-hand side may also be a function that evaluate s to t he ex Press i on {fl', .. . ,fn 1 } (n ~ O).
Each analyses rule is subject t o pattern-d i r ec ted invocat i on. When the facts in its l ef t-hand side match facts i n the factual data base, i ts right-hand side i s i nstantiated or eval uat ed ac cording to the match i ng substitut ion and the r e suiting facts are entere9 into the dat a base . These facts may in turn contribute t o the i nvoca tion of other analysis rul es. Rul es wi th empt y l e ft-hand side s arc i nvoked as soon as problem solving starts so that f acts i n their r ight-hand s i des arc premises to the solut ion. A dedu ct ion graph records all the deductions t hat have r esul t ed from the invocation of analys is rul es . When a contradiction is noted, it is used i n r everse to determine the set of assumpt i ons th a t ar c an tecedents of the cont r adi ct ory f ac ts. Dur i ng far lure re covery, i t i s used in the forward di r ec tion to update the factual data base.
4. 2. Examples
These are sample analysis rules :
-{(=(is-a &tr) transformer),(=( coo l e r of &t r) &cf), (part-of &tr &cl), (=( i s-a &cl ) coil ) }
='> (progn
( i f(eq &cf ai r)
then (i&{(<(voltage &cl) 3c3) })
else (i&{(<(voltagc &cl) Se3) })))
This rule implements: "if ai r i s the coo l e r of a transformer, then the voltage be tween the t ermi nals of any coil in this transformer mu!l: be lowe r than 3KV ; otherwise, it must be l ower than SKV" .
- {(=(is-a &tr) transformer),
(part-of &tr &tk), (=(is- a &tk) t ank )}
=>{(=(temperature-rise-in-oil-of &tr)
(temp-oil (losses-in &tr)
(radiating-surface-of &tk))) }
This rule encodes a physical law in i t s r i ght-hand side. Atom "temp-oil" i s the name of an i nput f unc t i on that computes the temperature rise l n the oil based on the losses i n the transformer and t he ra di ating surface of the tank.
4.3. Detection of contradictions
A contradiction occurs when some f acts i n the fac tual data base cannot be true s i multaneously.
Two programs of TROPIC are r~sponsible for de tecting contradictions. One is based on heuris- ' tic numerical search techniques. We refer the reader to [5] for a description of these pro grams. Contradiction~produce failures from which TROPIC immediately attempts to recover.
5. RECOVERY FROM FAILURES
5. 1 . Principle
When a failure is noted, the failure recovery procedure used by TROPIC determines the logical support of the contradiction, i.e. the subset of those assumptions from which the contradictory facts were derived. Then, it rejects the choice of a synthesis rule the application of which has produced at least one of these assumptions. Thus, it never tries to reject a choice that is irrel~ vant to the failure. In addition, only those choi ces which are subordinated to the rejected choice by control dependencies are immediately discarded However, there are usually several relevant choi~ ces that may be rejected alternatively in order to recover from a failure. The recovery proce dure must be able to consider them in a systema tlc way 1n order to avo1d perpetual 1terat1on through success1vefa1lures or om1ss1on of possi ble solut1ons. Indeed, the cho1ce that 1s reJec ted w1ll be replaced later by another choice and it may happen that this new choice leads to an other failure from which it is possible to reco ver by reintroducing the previously rejected choice. But, since this choice already led to failure, its return, if it is not accompanied with other actions, will drive TROPIC into an in finite loop of successive failures. On the other hand, ruling out the possibility of reactivating this choice may result in omitting potential sol~ tions, if there was more than one way to recover from the earlier failure. This difficulty requi res that the system remembers the conditions of its failures so that, if a once rejected choice is to be reintroduced, the recovery procedure can previously correct the failure responsible for this choice being rejected in a different way.
The recovery procedure of TROPIC avoids infinite loops through failures and omission of possible solution as follows
- The conditions of the failures that are encoun tered ate remembered in expressions called fai lure indicators, which are attached to the dhOice nodes (AND nodes) corresponding to the rejected choices. If recovering from a new failure is pos sible by reactivating a previously rejected choi ce, then the recovery procedure can use the .·cor responding failure indicator to recover diffe rently from the failure that was responsible for this choice being rejected. It is only after ma king this change that the once rejected choice is reintroduced. In this way, the system never tries the same combination of choices more than once.
- The recovery procedure avoids omitting poten tial solutions by operating chronologically. It never rejects a choice such that rejecting a more recent choice would enable TROPIC to recover from the current failure without recreating the condi tions of an earlier failure.
5.2. A simple expository example
We now describe a possible behavior of TROPIC on the oversimplified problem defined by Table 1, "A" being the initial task. For the sake of sim plicity, we represent tasks by capital letters and facts by lower-case letters. Each fact has the form "a" or "-a" (negation of "a"), so that a contradiction can only occur between a fact and its negation. In addition, we omit synthesis ru les providing alternative ways of reducing tasks A,B,C, ... , because they will not be used in the particular solution considered below ; similarly, the analysis rules that will never be invoked are now sho~m. Three failures will be encountered before a solution is ultimately produced.
Suppose that TROPIC applies synthesis rules <1>, <2>, <5>, <3>, <8>, <9>.,<15>, <16>, <4>, <II>,, <13>, <17>, ~18> and <6> 'successively. Then, the task-reduction tree is that of figure I. For the sake of readibility, the assumed facts have been associated with the corresponding OR nodes of the tree. The oriented dashed line that is superposed on the tree connects the exPanded AND nodes in the chronological order of their expansion. We call it the decision path and it is generated du ring task-reductive synthesis.
At this moment, the system notes the first fai lure, since fact -e, which is contradictory with assumption e, is deduced (invocation of analysis rules <1 1 > and<2 1 >). An exPression, called tne diagnostic exPression, is then initialized to ({e,h,ci,O,nil), where {e,h,cl,f} is the logical support of the contradiction (cf.§ 5.1.). The ge neral form of this expression is (A,T), where A is a set of assumed facts and T is a set of tasks. It is always such that the conjunction of the co~ di tions "each element of A is an assumption in the factual data base" and "each element of T is a task labeling an AND node of the task-reduction tree" is a sufficient condition for having en countered a fa1lure.
Then, the system traces back the decision path until it meets an AND node N that satisfies the following two criteria :
Cl : An assumption or a task contained in the set A or T of the diagnostic expression (A,T) has been generated whE'n N was expanded.
C2 : There exists an alternative synthesis rule for exPanding N, the application of which would not result in generating this assumption or this task.
N is called the recovery node. In the present ca s~t is the node labeled by task F, since the re duction of F by rule <7> would not generate assump tion f. The ·expression (({e,h,c1},nil),({f}, nil)) is then dram from the diagnostic expression and it is associated with N as a failure indicator ~ 1 · The general form of this expression is ((A1 ~T 1 ), (A2,T2)), where A1 and A 2 are sets of assumed or assumable facts, and T1 and T2 are sets of tasks. It is a conditional statement saying that expanding N with a synthesis rule that generates each assumption in A2 and each task in T2 always leads to failure if each element of .A 1 is an assumption in the current factual data base and if each element of T1 is a task labeling an AND node of the current task-reduction tree. Ex pressions (A 1 ,T 1 ) and (A 2 ,T 2 ) are respectively called the antecedent and the consequent of the failure ind~cator. When the conditions "each element of A1 is an assumption in the data fac tual tiata base" and "each element of T 1 is a task labeling an AND node of the task-reduction tree" are true because of the expansion of AND nodes that are all predecessors of N in the decision path, the failure indicator is ON ; otherwise, it is OFF. All failure indicators recorded by TROPIC are ON at the time of their creation ; it is in particular the case of ~ 1 ·
The choice of synthesis rule <6> is now rejected, so that fact f is no longer assumed and analysis rules <I'> and <2'> are desinvoked. Then, task reductive synthesis is resumed by applying syn thesis rule <7> · At this moment, the task-reduc tion tree is that of figure 2 but the system no tes the second failure since fact-b is deduced (invocation of analysis rul es <3'>, <4 ' > ·~d <5 '>). It sets the diagnostic expression to ({b,g,f' 2 , c2,f' 1 },nil) and it traces back the decision path:
The node labeled by F satisfies both cuteria Cl and C2 stated above since the application of rule <6> would note generate assumptions f 1 1 and f'2· But failure indicator ~I· which is currently ON, shows that reselecting rule <6> would inevi tably recreate the conditions of an earlier fai lure. Therefore, this node is not chosen for re covery node. Instead, the system executes the following two operations :
- it draws the expression (({b,g,c 2 },nil),({f'1, f' 2 },nil)) from the current diagnostic expression and it associates that expression with the node labeled by F as a failure indicator ~ 2 .
it sets the diagnostic expression to ({b,g,c2, e,h,c1},{F}), by combining the antecedents of ~I and ~ 2 . Indeed, in order to recover from the cur rent failure, TROPIC may now either reject a choir ce r esponsible for one of the assumptions b, g and c 2 (so that a cause of the current failure will be removed) , or reject a choice responsible for one of the assump tions e, h and c 1 (so that it will be possible to reselect rule <6>), or r eject the choice responsi ble for the generation of task F (so that the need for assuming either f, or f' 1 and f'2· will be re moved) .
Nodes labeled by Q,P,J,I,D,N and M do not ve rify criterion Cl. None of them is chosen for re covery node. Thus, the system passes over seven backtrackable nodes that would have been succes sively considered by a blind chronological pro cedure.
The node labeled by H satisfies both criteria C.l and C2, since applying rule < 10> would not ge nerate assumption h. No ON failure indicator being associated with this node, TROPIC chooses it for recovery node and associates the failure indica tor <I> 3 = (({b,g,c 2 ,f¥ 1 },{F}),({h},nil)) with it. The recovery node and the node labeled by F,the expansion of which made the current failure effec tive, belong to two different AND paths. This means that the corresponding two choices are not logically independent.
The system now updates the current solutions.f i rst, its rejects the choice of rule <9>, so that fact h is no longer assumed. Because they are subordi nated to this choice by control dependencies, ru les <IS> and <16> are also discarded. Next, TROPIC notes that failure indicator ¢ 1 has become OFF (because of the removal of assumption h), whil e failure indicator ¢ 2 remains ON. The consequent of ¢ 2 shows that the choice of rul e <7> cannot be maint.!lined which means that the current failure has not been remedied yet. However, since rcse lecting rule <6> has just been made possible ( ~ 1 being OFF), TROPIC can now reject the choice of rule <7>, whi ch was a choice responsible for thi ~ failure. After rejecting this choice, the task reduction tree is that of figure 3 (note the up dated decision path). Several parts of the cur rent solution remain unchanged although they were produced after the recovery node was expanded.
Task-reductive synthesis is resumed again: rul es <10> and <6> (because of ¢ 2 ) are succcsively ap plied (cf. figure 4). This leads the system to note the third failure because fact -g is dedu ced (invocation of analysis rules <6'>, <7'> and<8'>). The diagnostic expression is set to ({g,d,i,f,h' 1 }, nil) and the decision path is traced back :
The node labeled by F satisfi es both criteria Cl ans C2, but because of ¢2, which is currently ON, it is not chosen for recovery node. The failur e indicator <!> 4 = (({g,d,i,h' 1 },nil),({f},nil)) is associated with this node and the diagnostic ex pression is se t to ({g,d,i,h' 1 ,b,c 2 },{F}).
- The nodr> labeled by H satisfies both cr i t eria
Cl and C2, but because of ~ 3 , which is currently ON, it is not chosen for recovery node. The fai lure indicator ~ 5 = (({g,d,i,b,c 2 },{F}),({h'l , nil)) is associated with this noae and the d~ag nostic expression is set to ({g,d,i,b,c~,e,c 1 }, {F,H}). Note that this expression comb~nes con ditions of the first two failures and conditions of the current failure.
- Nodes labded by Q,P and J do not satisfy cri terion Cl. None of them is chosen for recovery node.
The node labeled by I satisfies both criteria Cl and C2. No ON failure indicator being associa ted with this node,it is chosen for recovery node and the failure indicator ~ 6 = (({g,d,b,cz,e,c 1 }, {F,H}) ,({i} ,nil)) is associated with it.
TROPIC rejects the choice of rule <11 >, so that fact i is no longer assumed. Then, it examines the failure indicators that have been associated with successors of the node labeled by I in the deci sion path. Because fact i is no longer assumed, failure indicators ~~ and ~ 5 are now OFF, so that the system recognizes that it has recovered from the current failure. Thus, no other choice is re jected.
Task-reductive synthesis is resumed by applying rule <12> and rule <14>. At this moment, the task-reduction tree is terminal (cf.figure 5). Since no contradiction is detected, the problem is solved.
This example shows that, each time a failure is recovered from, an ON failure indicator ~ is asso ciated with the recovery node N. This indicator prevents the system from rcselecting the rejected synthesis rule as long as it r~mains ON. Since ~ nay be turned OFF only if an AND node, which pre ceded N in the decision path when N was chosen for recovery node, is chosen for recovery node in turn, the same combination of choices cannot be tried more than once, and therefore perpetuel iteration is impossible. On the other hand, the diagnostic expression always determines a sufficient condi tion for encountering a failure. Thus, by tra cing back the decision path, the recovery proce dure always chooses for recovery node the most re cently expanded AND node that may enable the sys tem to resume task-reductive synthesis without re creating the conditions of an earlier failure.In this way, omission of potential solutions is im possible.
6. LEARNING FROM FAILURES
Failure indicators arc efficient means of recor ding failure :conditions because they are connected to the choice nodes of the task-reduction tree. However they do not completely preventthe system from re-achieving the conditions of earlier fai lures. Indeed,due to interv~ning failures, an ON
failure indicator may be turned to OFF,so that the conditions determined by its consequent may then be achieved by the application of a synthesis rule; if it happens later th~t the conditions in its an tecedent are also achieved, then the occurrence of a failure is inevitable.
OFF failure indicators are not needed to avoid in finite loops and omission of possible solutions and they also have little chance to become ON again. Thus, TROPIC discards them, so that updating the ON/OFF status of failure indicators merely consists of erasing the failure indicators that are no lon ger ON. However, the information they contain is not systematically fer p,otten: : when a failure in dicator ((A 1 ,T 1 ),(A 2 ,T 2 )) is discarded,the system may decide to generate the failure expression tA 1 u A 2 ,T 1 u T 2 ) that determines a context ~n wh~ch failure is unavoidable. Failures expressions are stored separately from the task-reduction tree. When expanding an AND node N, TROPIC eliminates from conside-ration every rule the application of which would reestablish the conditions recorded ~ther in an ON failure indicator associated with H, or in a failure expression.
In order to keep the list of failure expressions a reasonable size, TROPIC converts an OFF failure indicator into a failure expression only if it combines the conditions of several failures. In addition, it reconverts failure expressions into ON failure indicator whenever possible : let(A,T) be a failure expression, and let call A 1 and T 1 the subsets of A and T determining cond1tions that are already achieved before the expansion of an AND node N ; if there exists a synthesis rule applicable toN, the application of which would achieve all the conditions in A 2 z A- A 1 and in T 2 = T - T 1 , then not only does TROPIC not apply tnis rule, it also reconverts the failure expres sion ~nto an.ON failure indicator ((A 1 ,T 1 ),(A 2 ,T 2 )) assoc~ated w1th N.
Failure indicators and failure expressions provide means of a good compromise for recording failure conditions. ON failure indicators avoid infinite loops and omission of potential solutions and they can be used efficiently. Failure expressi6ns enable the system to convertinto a usable form information contained in OFF failure indicators. They are less efficiently used, but their number may be arbitra rily limited since they have no effect on the completeness of the problem-solver.
7. RELATION TO OTHER WORKS
Other systems use representations that distinguish between control and logical data, but they do not exploit this distinction in the same way nor for the same purpose as TROPIC. One of them is NOAH [9], a program for generating plans of actions at varying levels of detail. NOAH's control state is a hierarchical net of actions that combines the decomposition of an action into successively more detailed subactions and the partial orderings of the plans at each level of detail. All actions bring their effects into a model of the world and logical interdependences among actions are consi dered in this model. When a conflicting interde pendence is noted in a plan, correction is attemp ted only by cnforcinp, ord~ring of the partially ordered actions. Research on tiOAll was deliberately restricted to non-search aspects of problem sol ving and consequently the system includes no pro vision for backtracking.
Another related system is NASL [7], a program for designing electronic circuits. NASL's control state is a net of design tasks similar to NOAH's net of actions. As in TROPIC, the goal of the sys tem is to produce the model of a device. NASL in cludes no backtracking procedure and Me Dermott proposes an alternative scheme according to which correcting a mistake is treated as a task like another, drawn from the description of the mis take. However, the recovery procedure based on this scheme was not implemented.
Hayes f3] describes a representation for robot plans that consists of two interlinked data struc tures representing the subg6al structure of a plan and the logical relationships of the decisions taken in constructing the plan. Hayes states that "the representation enables a decision to be re, made without remaking chronologically subsequent but logically independent decisions". Nevertheless, the improved backtracking procedure was not im plemented.
Selective backtracking has been investigated in EL/ARS [10] a system for analyzing electrical circuits. The recovery procedure implemented in this system has been generalized by Doyle [2]. It has no explicit representation of the problem solver's control state in the sense of Section 3.3. Subsequently the conditions of the encountered failures are recorded into NOGOOD lists that are very similar to the TROPIC's failure e~pressions. Jn order to avoid perpetual looping, these lists nu!t: all be C'xamined b~for~ making a choice. A possible improV'!ml'nt is de-emphasizing some condi tions in the NO<DOD lists in order to produce con ditional expressions which arc similar to TROPIC's failure indicators, except they are not connected to a control structure. De-emphasis reduces the number of NOGOODs to be considered at any moment, but is difficult to implement because it has no sound domain-independent basis.
SYNTHESIS RULES
<I> A ~~> ({a} ,{B,C,O })
<2> B => ({b} ,{E,F})
<3> c => ({c} ,ct} ,{G,H})
<:4> D => ({d ,{ ,J})
<5> E => ({e} ,nil)
<6> F => ({f} ,{K})
<7'> F ~~> ({f' 1 ,r' y} ,{L})
<8> G ~> ({g} ,nil
<9> H ~> ({h} ,hf,N})
<10> H => ({h' 1,h'2},nil)
<II> I => ({i},nil)
<12> I => ({i'},ni l)
<13> J => ({j},{P,Q})
<14> K => ({k} ,nil)
<15> tl => ({m} ,nil)
<16> N ~> ({n} ,nil)
<17> p ~> ({p} ,nil)
<!8> Q => ({q},nil)
ANALYSIS RULES
<I'> {f. cl} ~ {-r}
<2'> {-r,h} ='> { -e}
<3'> {f'l,cT}~ {s}
<4'> {f'2,g => {t}
<5'> {s,t} ='> { -b}
<6'> {h' I ,f} ~> {u;-v}
<7'> {u,d ~ {w}
<8'> { -v ,w ,d}=> { -g}
Table I
@inproceedings{ijcai1979p114,
title = {Failure Processing in a System for Designing Complex Assemblies},
author = {Latombe, Jean-Claude},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/114},
}
TY - CPAPER TI - Failure Processing in a System for Designing Complex Assemblies AU - Latombe, Jean-Claude T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/114 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards