Int . J . Human – Computer Studies (1996) 45 , 305 – 335 Applications of abduction: knowledge-level modelling T I M M E N Z I E S † Department of Software De ! elopment , Monash Uni ! ersity , Caulfield East , Melbourne , Australia , 3 1 8 5 email : timm ê insect .sd .monash .edu .au ( Recei ! ed 5 September 1 9 9 5 and accepted in re ! ised form 2 5 March 1 9 9 6 ) A single inference procedure (abduction) can operationalise a wide variety of knowledge-level modelling problem solving methods ; i . e . prediction , classification , explanation , tutoring , qualitative reasoning , planning , monitoring , set-covering diagnosis , consistency-based diagnosis , validation , and verification . This abductive approach of fers a uniform view of dif ferent problem solving methods in the style proposed by Clancey and Breuker . Also , this adbuctive approach is easily extensible to validation ; i . e . using this technique we can implement both inference tools and testing tools . Further , abduction can execute in vague and conflicting domains (which we believe occur very frequently) . We therefore propose abduction as a framework for knowledge-level modelling . ÷ 1996 Academic Press Limited 1 . Introduction In the 1970s and early 1980s , several high-profile expert system successes were documented : e . g . MYCIN (Yu et al . , 1979) , CASNET (Weiss , Kulikowski & Amarel , 1978) , PROSPECTOR (Campbell , Hoilister , Duda & Hart , 1982 ; Duda , Hart & Reboh , 1985) and XCON (Bachant & McDermott , 1984) . However , despite careful attempts to generalize this work (e . g . Stefik et al . , 1982) , expert systems construction remains a somewhat hit-and-miss process . By the end of the 1980s , it was recognized that our design concepts for knowledge-based systems were incomplete (Buchanan & Smith , 1989) . A new expert system design approach (which has come to dominate the knowledge acquisition field) is the search for reusable abstract domain-independent problem-solving strategies . We call this approach KL since it is a variant of B Newell’s knowledge le ! el (KL) modelling approach (Newell , 1982 , 1993 ; Newell , Yost , Laird , Rosenbloom & Altmann , 1991 ; Menzies , 1995) . The fundamental premise of KL is that a knowledge base should be divided into domain-specific B facts and domain-independent abstract problem solving inference procedures [e . g . Clancey’s (1992) model construction operators , Steels’ (1990) components of expertise , Chandrasekaran’s task analysis , SPARK / BURN / FIREFIGHTER (Marques , Dallemagne , Kliner , McDermott & Tung , 1992) and KADS (Wielinga , Schreiber & Breuker , 1992)] . KL refers to Newell’s research on the knowledge A † Past papers available from http : / / www . sd . monash . edu . au / ! timm / pub / docs / papersonly . html . 305 1071-5819 / 96 / 090305 " 31$18 . 00 / 0 ÷ 1996 Academic Press Limited 306 T . MENZIES level (Newell , 1982 , 1993 ; Newell et al . , 1991) and the SOAR project (Yost & Newell , 1989 ; Rosenbloom , Laird & Newell , 1993) . KL does not explicitly model A problem-solving procedures . The observation that a KL system such as SOAR is A performing classification is a user-interpretation of the following . (1) The application of domain-specific knowledge controlling . . . (2) . . . a single inference procedure (operator selection over a problem space traversal) (Yost & Newell , 1989) . This paper argues for a variant on the KL approach . Like KL , we will use a A A single inference procedure (abduction) . However , we take a graph-theoretic approach rather than the production-system approach used by SOAR (see Section 6 . 2 . for a comparision of our approach and SOAR) . We find that a wide-variety of problem solving strategies are merely dif ferent types of calls to the same abduction procedure . Such uniformity simplifies the construction of interfaces between the inputs and outputs of dif ferent problem solving types . Breuker argues that such interfacing is essential since most problem solving types are used in combination to perform some task (Breuker , 1994) . Far from being a radical proposal , we find that our abductive process directly operationalizes the theory subset extraction process that Breuker (1994) and Clancey (1985 , 1992) argue is at the core of expert systems . Clancey of fers a two-layered extraction process (qualitative model to situation-specific model) while Breuker of fers a four-layered view (generic domain model to case model to conclusion to argument structure) . We take theory subset extraction to be a literal description of the internals of expert systems inference . Our research goal is the description of the minimal architecture necessary to perform this process . This paper is organized as follows . A summary of the terms introduced in this article is given in Figure 1 . Section 2 describes the theory subset extraction described by Clancey and Breuker . Section 3 describes our abducti ! e framework . Section 4 discusses the use of abduction for a variety of KL tasks ; i . e . prediction , B classification , explanation , tutoring , qualitative reasoning , planning , monitoring , set-covering diagnosis , consistency-based diagnosis , validation , and verification . Section 5 discusses the practicality of our proposal . Section 6 discusses some related work and issues . Note that this work is part of our abducti ! e reasoning project . We believe that abduction provides a comprehensive picture of declarative knowledge-based systems (KBS) inference . Apart from the problem solving methods discussed here , we also believe that abduction is a useful framework for intelligent decision support systems (Menzies , 1995 a ) , diagrammatic reasoning (Menzies & Compton , 1994) , single-user knowledge acquisition , and multiple-expert knowledge acquisition (Menzies , 1995 c ) . Further , abduction could model certain interesting features of human cognition (Menzies , 1995 d ) . Others argue elsewhere that abduction is also a framework for natural-language processing (Ng & Mooney) , design (Poole , 1990 a ) , visual pattern recognition (Poole , 1990 b ) , analogical reasoning (Falkenhainer , 1990) , financial reasoning (Hamscher , 1990) , machine learning (Hirata , 1994) and case-based reasoning (Leake , 1993) . APPLICATIONS OF ABDUCTION : KNOWLEDGE-LEVEL MODELLING 307 " X" , X ! Y Size of the set X , the intersection of the sets X and Y S A statement provided by an expert . T A theory comprising a set of statements ; e . g . Figures 2 and 9 . D A dependency graph showing connections between literals in T ; e . g . Figures 3 and 10 . # V , E $ Vertices and edges in D . Vertices are either and-vertices V and or or-vertices V o r . I An invariants predicate reporting pairs of incompatible vertices in D . NOGOODS Sets of incompatible vertices ; generated using I . model compiler A translator from T to D . F The fanout of D ; i . e . average number of edges from a vertex . " E" F # . " V" OUT The subset of V we are trying to explain . IN The subset of V which are acceptable starting-points of an explantion . FACTS Vertices we cannot doubt . DEFAULTS IN vertices that are not FACTS . P Proof trees connecting OUT to IN . Each proof P using vertices i V used , and avoids the vertices V forbid . i i A Assumptions made by P ; i . e . P used $ FACTS . i A Assumptions which I tells us are contradictory . C A The most upstream controversial assumptions . B ENV Maximal (with respect to size) consistent (defined using I ) subsets of A . B W A world : the set of proofs that are consistent with ENV ; e . g . i i Figures 4 and 5 . co ! er , causes Outputs and inputs in a world . co ! er # " OUT ! W i " ; causes # " IN ! W i " . BEST Competing worlds are judged by the BEST assessment operator . TASK The goal of an inference procedure : TASK # # BEST , IN , OUT $ . F IGURE 1 . Summary of terms . 2 . Clancey & Breuker In this section , we argue that the common theme between Clancey’s and Breuker’s view of expert systems inference is the extraction of sub-theory from a super-theory . 2 . 1 . MODEL CONSTRUCTION OPERATORS Clancey characterizes expert system inference as model construction operators that create a situation - specific model (SSM) from a general qualitati ! e model (QM) in the knowledge base (KB) . Clancey’s QM is like a first-order theory whose relations model causality , sub-types , and temporal relations . At runtime , portions of this 308 T . MENZIES theory are accessed and the variables are bound . This ground subset of the full theory is the SSM ; i . e . ‘‘the specific model the program is constructing of the particular system it is (processing)’’ (Clancey , 1992) . This specific model is the subset of the QM that is relevant to the task at hand . Clancey argues that there are two basic problem-solving methods used by expert systems : heuristic classification and heuristic construction (Clancey , 1992) . By heuristic classification , Clancey means that the inference engine merely selects a pre-existing inference path . In heuristic classification , this pathway would include the following . $ Inference to an abstracted description of the problem at hand . $ A partial match of this problem to an abstracted solution . $ An inference that specialises the abstracted solution to a solution relevant to the current problem . By heuristic construction , Clancey means that the inference engine constructs its conclusions from partial inferences supplied in the knowledge base . Construction is much harder than mere selection . Literals in dif ferent partial proofs may be mutually exclusive ; i . e . while we can believe A ∨ B , it may not be true that we can believe A ∧ B . The constructed SSM must be built with care in order to take into account these cancelation interactions . Multiple , mutually exclusive , SSMs may be possible and these must be mamaged separately . Extra architecture is required to handle conflicts and dependencies within the SSM . 2 . 2 . COMPONENTS OF SOLUTIONS Breuker explores the relationships between problem solving techniques used in expert systems (i . e . modelling , planning , design , assignment , prediction , assessment , monitoring and diagnosis) (Breuker , 1994) . He of fers an abstract description of the ‘‘components of a solution’’ generated by these techniques which , he argues , are of four types . $ A case model (equivalent to Clancey’s SSM) that represents some understand- ing of a problem . $ A conclusion , which is some answer to a question posed by the problem definition . $ An argument structure , which is supporting evidence for the conclusion generated . $ The case model which is generated from some generic domain model (equivalent to Clancey’s QM) . An argument structure is extracted from the case model . The conclusion is the portion of an argument structure that is relevant to the user . In the case where all the solution components are represented as a ground propositional theory whose APPLICATIONS OF ABDUCTION : KNOWLEDGE-LEVEL MODELLING 309 ++ x y ++ ++ ++ d ++ a ++ e c ++ g ++ –– ++ b f –– F IGURE 2 . An indeterminate qualitative theory . dependency graph has edges E , then : edges ( answer ) ‘ edges ( argument structure ) ‘ edges ( case model ) ‘ ( edges ( generic domain model ) # E ) where edges ( X ) denotes the edges of the dependency graph present in X . 2 . 3 . THEORY SUBSET EXTRACTION : AN EXAMPLE We now describe theory subset extraction in detail using a theory of vertices V and edges E . This example will informally introduce many of the concepts we will return to later . In summary , we will search our theory for a subset of its edges that are relevant to some problem . The found subset must be internally consistent (i . e . we have to check for cancelation ef fects between mutually exclusive assumptions) . Consider the qualitative theory (Iwasaki , 1989) of Figure 2 . In that figure : $ all vertices can take one of three values : UP , DOWN , or STEADY ; "" $ X ÅÅ 5 Y denotes that Y being UP or DOWN could be explained by X being UP or DOWN respectively ; $$ $ X ÅÅ 5 Y denotes that Y being UP or DOWN could be explained by X being DOWN or UP respectively . Let us make some qualitative reasoning assumptions about Figure 2 : $ the conjunction of an UP and a DOWN can explain a STEADY ; $ no change can be explained in terms of a STEADY (i . e . a STEADY vertex has no children) . With these assumptions , we can expand Figure 2 in to Figure 3 . That figure contains one vertex for each possible state of the vertices of Figure 2 . It also contains and vertices that models combinations of influences (for example , aUp and bUp leads to cSteady ) . Figure 3 represents the superset of all explanations possible from Figure 2 ; i . e . it is an explicit ground version of Clancey’s QM and Breuker’s generic domain model . Given some inputs (denoted IN ) and some desired goals (denoted OUT ) , then we can use Figure 3 to generate a set of explanatory proofs (denoted P ) . For example , 310 T . MENZIES &008 &007 xSteady xUp yUp dUp aUp eUp cUp gUp bDown fUp &003 &001 cSteady fSteady &005 &004 &002 xDown yDown &006 dDown aDown eDown dSteady cDown gDown bUp fDown F IGURE 3 . The edges E tacit in Figure 2 . if IN # % aUp , bUP & OUT # % dUp , eUp , fDown & then all the proofs which can link members of IN to members of OUT across Figure 3 are : p(1) # aUp 5 xUp 5 yUp 5 dUp p(2) # aUp 5 cUp 5 gUp 5 dUp p(3) # aUp 5 cUp 5 gUp 5 eUp p(4) # bUp 5 cDown 5 gDown 5 fDown p(5) # bUp 5 fDown Some of these proofs are contradictory since that make conflicting assumptions . An assumption is a literal that is not one of the known FACTS (typically , FACTS # IN " OUT ) . Our assumptions are % xUp , yUp , cUp , gUp , cDown , gDown & . If we assume that an entity can’t be in two dif ferent states at the same time , then the following assumptions are conflicting and controversial : % cUp , gUp , cDown , gDown & . Note that , in Figure 2 , g is fully determined by c . Therefore , in terms of sorting out the various possibilities , the key controversial assumptions are % cUp , gUp & and % cDown , gDown & . Depending on which controversial assumptions we adopt , we can believe dif ferent things . In this example , we have two possibilities : one for % cUp , dUp & and one for % cDown , dDown & . The proofs that are consistent with % cUp , dUp & are % P , P , P , P & 1 2 3 5 and the proofs that are consistent with % cDown , dDown & are % P , P , P & . The union of 1 4 5 the proofs that we can believe at the same time are the Clancey SSM or the APPLICATIONS OF ABDUCTION : KNOWLEDGE-LEVEL MODELLING 311 xUp yUp dUp aUp eUp cUp gUp bUp fDown F IGURE 4 . Case model 4 1 : the union of proofs that are consistent with % cUp , gUp & . Breuker case model (we will call them worlds below) . There are two such case models , shown in Figure 4 and Figure 5 . Queries can be executed over each case model to generate Breuker’s argument structures or conclusions . For example , in case model 4 1 (Figure 4) , an argument structure for the conclusion dUp could be aUp 5 xUp 5 yUp 5 dUp . 3 . Abduction We believe that abduction is a powerful framework for describing the above theory subset extraction process . In this section , we repeat the above example in terms of HT4 (Menzies , 1995 c ) , our preferred abductive framework . In the next section , we will argue that many KL tasks are just dif ferent ways of calling HT4 . B 3 . 1 . DEFINITIONS Informally , abduction is typically defined as inference to the best explanation (e . g . Rourke , 1990) . Given % , & , and the rule R : % ! & , then deduction is using the rule 1 and its preconditions to make a conclusion ( % ∧ R é & ) ; induction is learning R 1 1 after seeing numerous examples of & and % ; and abduction is using the postcondi- tion and the rule to assume that the precondition could explain the postcondition ( & ∧ R é % ) (Levesque , 1989) . Abduction is not a certain inference and its results 1 must be checked by an inference assessment operator [which we call BEST and Bylander , Allemang , Tanner & Josephson (1991) call the plausbility operator pl ] . 3 . 2 . HT4 AND ABDUCTION More formally , abduction is the search for assumptions A which , when combined with some theory T achieves some set of goals OUT without causing some contradiction (Eshghi , 1993) . That is : EQ : V " A ! OUT 1 EQ 2 : T " A Ö ! " xUp yUp dUp aUp cDown gDown bDown fDown F IGURE 5 . Case model 4 2 : the union of proofs that are consistent with % cDown , gDown & . 312 T . MENZIES While abduction can be used to generate explanation engines (see Section 4 . 3) , we believe that EQ and EQ are more than just a description of ‘‘inference to the best 1 2 explanation’’ . EQ and EQ can be summarized as follows : make what inferences 1 2 you can that are relevant to some goal , without causing any contradictions . Note that the proof trees used to solve EQ and EQ are the case models / SSMs / worlds 1 2 we seek to compute . To execute HT4 , the user must supply a theory T (e . g . T # Figure 2) comprising a 1 set of uniquely labelled statements S . For example , from Figure 2 , we could say x that : s[1] # plus – plus(a , c) . s[2] # minus – minus(b , c) . etc . An S statement is like a macro that expands into the super-set of explanations i acceptable to the author of S . This super-set is the search space for the proof i generation . We represent this search space as a dependency graph D . D is directed and possibly cyclic . Figure 3 shows D , the dependency graph generated from T . D 1 1 is an and-or graph comprising ## V a n d , V o r $ , E , I $ ; i . e . a set of directed edges E connecting vertices V containing invariants I . I is defined in the negative ; i . e . — l I means that no invariant violation has occurred . Each edge E and vertex V is x y labelled with the Z that generated it . Figure 3 contains sample and-vertices and z or-vertices . For example : $ xUp is an or-vertex which we can believe if we also believe dUp or aUp . $ &OO3 is an and-vertex which we can believe if we also believe gUp and bUp (but see Section 4 . 2 for alternative ways of handling and-vertices) . Not shown in Figure 3 are the invariants I . For a qualitative domain , where entities can have one of a finite number of mutually exclusive values , the invariants are merely all pairs of mutually exclusive assignments ; e . g . : %i(X , Y) : X and Y cannot be believed together i(aUp , aSteady) . i(aSteady , aUp) . i(aUp , aDown) . i(aDown , aUp) . i(bUp , bSteady) . i(bSteady , bUp) . i(bUp , bDown) . i(bDown , bUp) . etc . 3 . 3 . THE MODEL COMPILER When converting T to D , a model compiler is required to capture any special i i domain semantics . For example , in a qualitative reasoning domain , we can reach a STEADY via a conjunction of two competing upstream influences (e . g . &003 ) . In practice , these model compilers are very small . Our qualitative domain compiler is less than 100 lines of Smalltalk . HT4-style inference is feasible for representations that support such a translator between T and D . Recall that D is an explicit and-or graph of literals (positive or negative propositions) that represents the superset of explanations acceptable to the author of T . Such and-or graphs can be extracted from many representations APPLICATIONS OF ABDUCTION : KNOWLEDGE-LEVEL MODELLING 313 including propositional expert systems and certain types of equational systems (Iwasaki & Simon , 1986 ; Iwasaki , 1988) . HT4 could also be used for first-order theories , but only where that theory can be partially evaluated to an equivalent ground (i . e . no variables) theory . Once such a model-compiler is available , then the practical limit to HT4 is the size of D . These limits are explored further in Section 5 . 3 . 4 . PROOFS OF OUT PUTS HT4 extracts subsets of E which are relevant to some user-supplied TASK . Each TASK is a triple # IN , OUT , BEST $ . Each task comprises some OUT puts to be x reached , given some IN put ( OUT ‘ V and IN ‘ V ) . IN can either be a member of the known FACTS or a DEFAULT belief which we can assume if it proves convenient to do so . Typically , FACTS # IN " OUT . If there is more than one way to achie ! e the TASK , then the BEST operator selects the preferred way(s) . To reach a particular output OUT ! OUT , we must find a proof tree P using z x vertices P used whose single leaf is OUT and whose roots are from IN (denoted x z P roots ‘ IN ) . All immediate parent vertices of all and-vertices in a proof must also x appear in that proof . One parent of all or-vertices in a proof must also appear in that proof unless V or ! IN (i . e . is an acceptable root of a proof) . No subset of P used may y x contradict the FACTS ; e . g . for invariants of arity 2 : — l ( V y ! P u xsed ∧ V z ! FACTS ∧ I ( V y , V z )) 3 . 5 . ASSUMPTION SETS The union of the vertices used in all proofs that are not from the FACTS is the HT4 assumption set A ; i . e . ’ ( A # ! % V ! P used & $ FACTS y x V y Recall from the above that the proofs in our example made the assumptions : a # % xUp , yUp , cUp , gUp , cDown , gDown & The union of the subsets of A which violate I are the contro ! ersial assumptions A : C A # ! % V ! A ∧ V ! A ∧ I ( V , V ) & C x y x y V x The controversial assumptions of our example were : ac # % cUp , gUp , cDown , gDown & The base contro ! ersial assumptions ( A ) are the controversial assumptions which B 314 T . MENZIES have no controversial assumptions in their ancestors (i . e . are not downstream of any other controversial assumptions) . The base controversial assumptions of our example are : ab # % cUp , cDown & 3 . 6 . WORLD GENERATION Maximal consistent subsets of P (i . e . maximal with respect to size , consistent with respect to I ) are grouped together into what we call worlds W ( W ‘ E ) (recall that i world ) case model ) SSM) . Each world W contains a consistent set of beliefs that i are relevant to the TASK . The union of the vertices used in the proofs of W is i denoted W used . i In terms of separating the proofs into worlds , A are the crucial assumptions . We B call the maximal consistent subsets of A the en ! ironments ENV ( ENV ‘ A ‘ B i B A ‘ A ‘ V ) . The environments of our example are : C env(1) # % cUp & env(2) # % cDown & The union of the proofs that do not contradict ENV is the world W . One world is i i defined for each environment ; i . e . " W " # " ENV " . In order to check for non- contradiction , we use I to find the vertices that are forbidden by each proof : P forbids # ! % V ! P used ∧ I ( V , V ) & j k j k l V i For example , P forbids # % bDown , bSteady , fUp , fSteady & . 5 A proof P belongs in world W if its forbids set does not intersect with ENV ; i . e . : j i i * + W # ! P forbids ! ENV # C i j i P j Note that each proof can exist in multiple worlds . The worlds of our example are : w(1) # % p(1) , p(2) , p(3) , p(5) & w(2) # % p(1) , p(4) , p(5) & W is shown in Figure 4 and W is shown in Figure 5 . 1 2 3 . 7 . ASSESSING WORLDS For any world W , W causes are the members of IN found in W ( W causes # W used ! i i i i i IN ) . The achievable or co ! ered goals OUT in W are the members of OUT found in i that world ( W co ! ered # W used ! OUT ) . Continuing our example : i i causes(w(1)) # % aUp , bUp & causes(w(2)) # % aUp , bUp &