The Role of Plans in Automated Consultation

1. Int.roduction

Consider a person trying to solve a problem with a com­ pulf'r ~>ystcm he docs not fully understand, and assume that. he has encountered a difficulty due to his lack of knowlf'cl~te of that sy~>tem. For example, he might be un­ aware of t.he capabilities available or not know the names of it.s commands, or he might get an unexpected result he r.an 't explain . The simplest way Cor him to acquire just the information he needs is t·o ask a consultant Cor help. Then, armed with the consultant's advice, he may sur· mount the difficulty and solve; t.he problem. Consultation is a rnr.thod widely used in computer centers as well as in domains like business, law, and medicine; and, as com· puter technology becomes more pervasive and computer "Y"Lems more complex, the need for consultation will ~row. Unfortunately, human consultants arc scarce, ex· pensive, and often unavailable wht.n needed. This paper describC'S the implementation of an autom.lted consultant to fill t.his need.

The type of difficulty described above can be called a rc$ourc:c usage difficulty to distinguish it from a difficulty inhering in the problem or a difficulty in learning about the resource wit.hout a specific problem in mind. A resource usa~e difficulty i11 one which is encountered in trying to llolve a problem using a resource and due to the problem

!lolvcr'll lack of knowledge or that rellource. The con­ tmlt.ant's task is io remedy the deficiency in the user's knowledge underlying a resource usage difficulty.

The hardest resource usage difficulty to handle is a vio­ lated expect. a lion which t.hc user can't explain. In other casC's, the dt·ficiency in the user's knowledge is implicit in hi,; question, and the answers can simply be looked up in a data base (e.g. "how do I invert a matrix?" or "what arc the argument.R to MAP?"). In the case of an unexplainable violated cxpect.ation, even the user is unaware of the na­ ture of his "misconception". The consultant's first step, therefore, is to identify this misconception, after which he can generate his advice.

The method described here for the identification of the user's misconception is based on the assumption that the UReJ·'s ad.ions are "rational", i.e. ·that he has some "plan" for achieving his goal. This plan explains why he chose the commands he did in terms or his belir.fs about the input-output ~>pecifications of those commands. The key to t.hc identification or the user's misconception is the reron~>t.ruction and debugging of this plan.

The plan reconstruction procedure is based on the as· !lumpt.ion t.hat. t.hc user of a complex resource behaves (up t.o ordering of strategies) in accordance with a standarcl heurist.ic problem solving procedure, called MtJSER. 1\.fl.JSBJl is a larJ!;r.ly domain indeprndent problem solver wit.h the ability to invoke domain dependent methods when nrcr.l'sary. In 6olving a prohlcm the user implicitly ~cnrratcs a graph of goals and subgoals, in accordance with t.his algorit.hm. MUSER is guaranteed to produce only c:orrr.d Rolut.ions (given a correct data base), :and so this goal-suhgoal graph com·Lit.uleR a direct proof that the tlf;r.r'r; commands achieve hill goal (in terms or his beliefs). In t.hc consult.ant delicribcd here, t.hc notion of the user's plan (as proof) is identified with the goal-subgoal graph of hi11 solution.

With this view, plan rr.confilruction is a complell "parsing" prohlem, in which the user's actions are the "sentences" and in which the MUSER algorithm is the "grammar". The plan reronfitrudion pror.r.11s con11ists of heuristic sug· gr.,; I ion of partial parsinJ!:s toj!;ether with forward and bark ward symbolic evaluation of the problem solving pro­ cedure t.o filter these suggeRt.ions. Some of the partial parsings arc suggested by the patterns in a library of frc· qur.nt.ly recurring errors. Others arc SIIJ!:gcsted by correct fartr; ahout MACSYMA and the structure of the MUSER model. Although the rr.c.ognition of standard errors playa a large part in cffcct.ivc consultation, it is possible to rcronst.ruct .Plans containing misconceptions using just the MlJSBJl model and correct facts about MACSYMA.

The method of consultation is exemplified by an automated consultant for MACSYMA novir.cs, Cilllcd the Advisor. It is a program distinct from MACSYMA, with it.s own Rcparat.c dat.a baRe and expertise. The Ad\' isor ar.r.r.ptR a deRr.ript.ion or a re~urce usage difficulty from its user and generates advice tailored to his need. Event.ually, t.hc Advioor ~>hould he able to converse in English; however, at present, all communication' is con· dud.r.d in the Advirmr's LISP-like data base language.

This docs not mean that the consultation technology described here is in any way restricted to MACSYMA. Con,;ult.at.ion is useful in any ~>ituation where the user of a rrsource r.nust do some problem solving with partial knowlr.dge of the rr.scmrre. Thr. Advisor could equally well be applied to any complex, interactive computer system, such as a text editor, a document production· program, or a data haRe query Rystem.

2. An J~xamplc of a Rr.~ourcc Usage Difficulty

AR a r<mrrete example or a rr.6ource ul\i\ge diffiGulty, conaider t.l1e MACSYMA interaction and consultation ses­ sion ~;hown in figure 1. The command lines (e,g. C6) are t~1>ed by the user; the display lines (e.g. 06) arc MACSYMA's response. A command line may be ter­ minatrd by a ";" or a "$"; if the latter is used, the dis­ play line is supprc5scd (e.g. C7). Expressions arc entered in linear form (e.g, (J-2·Z)/Z); ":" is the assignment operator; and other commands arc applied using func· tiona! not.ation (e.g. R.ATSIMP(D1)) . Parentheses delimit compound stat.emr.nh.

(C6) llATSIMP(D1);

(C7) (A:COEFF'(D6,X,2),B:COBFF(D6,X,l),

C:COEF'F(D6,X,O))$

(C9) HELP()$

U,;er: J wa~; tryin~~: to solve D6 for X and I got 0.

Advi,;or: Did you expect COF:FF to return the coefficient of Dfi?

User: Yes, doc5n't it?

Advisor: COF:FF(I·;XP, VAU, POW) returns the correct cot'fficirnt of VARPow in EXP only if EXP is expanded with respect. to V AR. Either expand first and then use COEFF or use RATCOEF.

User: Ok, t.hanks. Bye.

F'ip;. 1 - An example of MACSYMA consultation

In t.his cx;unplc, the user's difficulty was due to his "misconception" that COEFF always returns the corffirirnt of its argument . This misconception gave rise to the erroneous use of COEFF in line C7 without a preliminary expansion of 06. However, the user didn't observe t.hi,; "hug" until the zero appeared in line DB. Bcin~t unable t.o explain the violation of his expectations, the Ulicr then appealed to the on-line consultant for help.

Onr. mmmon llu~ge,;tion for eliminating such difficulties is to switch the name.s COEFF and RATCOEFF. One reason I. hi,; hasn't. been done is that. COEFF is much more efficimt t.han RATCOEFF; by giving COEFF the morr. common name, the hope is that users will try the more efficient command fir6t . Even if they were switched, not all problems would be eliminated. For example, a user who want.s to Rolve a polynomial over a polynomial domain would need a version of COEFF with the present semantics; seeing a command called COEFF he might believe that it does what he wants and would get the wrong answer. So long as there arc commands with different interpretations depending on the the type of problem the user is trying to solve, there will be violated expectations and a need for consultants.

3. The MUScH. Model and Plans

In order to di11cover the misconception underlying the user's violated expectation, it is first neocbi>ary to know why he expected it. The user must have had in his mind some argument explaining how his particular sequence of commands was structured to achieve his expectation. For Rin~ll'! r.ommands, an adequate explanation is sir;nply a belief about the command involved. For a sequence of several r.ommands, t.he explanation requires an enumera· tion of the intrinsic properties of the individual commands t.ogdhcr wit.h an argument showing how they co-operate to achieve the expectation. A plan is a formalization of this not. ion of co-operation, essentially a formal proof that the r.ommand sequence results in the expectation.

This view of plans raises two questions. How does one characterize plans, i.e. is there any syntax for or constraint on plan !il.ructure? Second, how does the Advisor acquire knowlrdge of t.hc user's plan and how is it debugged! The answer t.o the first question is given as a formal modd for t.he problem solving behavior of theMACSYMA novire. The Advisor's techniques for plan reconstruction and dchu~~ing are described in the sections thereafter.

3.1 The MUSER Model

In l'olving problrms MACSYMA novices do not randomly explore all possible combinations of commands. In fact, the analyRis of more than a hundred problem sol~ing sea· sions supports t.he conjecture that novices act in accord· ance with a st.andard heuristic problem aolving procedure called MUSER. The differences between users sttim from di!Terencr.s in their knowledge of MACSYMA iutd their ordering of strategies. The strategies themselves seem to be common.

The MACSYMA user typically has a mathematical problem he is trying to solve and approaches MACSYMA for its powerful abilities at algebraic manipulation. Thus, in any MACSYMA problem, there arc two distinct domains involved, viz. mathematics and MACSYMA. In the MUSER mpdel, knowledge about these domains is grouped into thrcl'! categories (see figure 2). The "Task Environment" is a body of mathematical facts and pro­ cedures; the "St.atic Model of MACSYMA" contains the input-output spccificat.ions of MACSYMA 's commands; and t.he "State Description" is a data base of facts about the current MACSYMA (such as variable bindings and funct.ion definitions). The MUSER problem solver is a domain independent procedure which accepts a problem statement in a domain independent formalism similar to predicat.e calculus and produces a sequence of MACSYMA commands t.hat solves it. In doing so, it utilizes the facts stored in the data bases and implic.itly gent·rates a goal· sub goal graph, or "Plan" .

8

Fi~ . 2 · 1\HJSEH'" data structures

The M\JSER problem solver is guaranteed to produce only r.orrr.d liolutions (~iven a correct data base), and so this goal-subgoal graph constitutes a direct proof that the commandli achieve the goal (in1.erms of the facts in the data bases). Any errors in a solution must derive from inr.orrrd tmlrieR in one of the data bases. A resource usage difficulty ort.cn arises due to an error in the user's static model of MACSYMA, and the purpose of consultat.ion is t.o r.orrr.d ·snr.h r.rrorR.

The MUSER problem solver is represented as a "parametr.rized procr.dural net", or PPN. A PPN is a hierarchical network of actions at varying levels of detail in whirh each ar.t.ion node has af;sociated with it sets of input and output objects and sets of ''prerequisites" and "postrequisites" (conditions which must be true for the adion to Rncr.eed and those which become true after its execution). In the procedural nets described by Sarcrdot.i (Sacerdoti], each ar.tion node is described in terms of sprcific objects in t.he world being modeled. In a parameterized procedural net, the flow or data into and out of an adion iR de~;crihecJ in terms or the iflpUts and outputs of othrr ar.t.ions without naming any specific real world ohjeds. 'fhuR, a PPN is a kind of partial program. Except. for its hierarchical character and the explicit rep. rcsrntation of prerequisites and postrequisitca, this for· mali~m is Rimilar to the dataflow ~eraphs described by Drnnis n)ennis] .

Fir.ure 3 ,;how11 a vrry ,;mall fragment of the MUSER PPN. Thr square boxes rrpresent problem solving methods at varyin~ levels of detail. Mr.thodR at different levels arc mnnrrt.rd hy vcrl.ical "~iupergoal-subgoal" links. Links with rrosshar11 drnotc conjunctive suhgoals; those without., denote alternative ~;ugbJ~;oals. The rounded boxes rrprrsrnt data base assertions. In order to simplify the pn~sr. 11l.al.ion and ernphafiize their hierarchical character, PPN11 arc drawn hrre as trer~> without control or dataHow links and with varioufi problem solving methods dupli· cat.rd (r.r, . "Obtain an object"). In looking at such ab­ hrc,·iat rd diar.rams, the reader should bear in mind that thr 01rl ion uoclc" arc actually intrrconnected through their inputs ;111cl outputR and through their prerequisites and po!;f rc ·quisil. t~f\.

Earh prohlrm fiolvin~ method in MUSER satisfies a par· t.irular type of stoal hy a partic:nlar method or a choice of mrtlwdR. For example, thr. ~oal of "Obtain an object" i& to "oht.ain" t.he object specified as its argument (either t.o print. it out. or pass it as argument to a function) . In MACSYMA one can do this eit.her by finding an already computed exprr~;sion (the "Find a variable" method) or by wmt.rur.tin~ one anew (the "Construct an object" method).

In the "Find a variable" method, MUSER searches its data base to rind a variable with the goal as value and thr.n evaluate~> il. Jn.t.he terms Ufied in figure 3, it looks a variable t1 tmr.h t.l{at Vnl(v) = g, where g is the specified goal.

The ''Fr.t. r.h" method is MUSER's data base access rune· tion . It ,;earchcs the data base for a fact or the form !ipr.riricd in t.hc assertion aU.ached to it. (This includes more t.han exact matches. "Fetch" employs a fast hut limited inference algorithm [Genr.sereth 1977] to do property inhcril.anrcfi and. set intersections as well .) In this case, t.hr. goal g would be supplied as an input to "Fr.t.rh" and the variable v would be returned as output.

The "Act.ion" method is MUSER's way of executing a r.ommand in MACSYMA. Given a command and a set of ohjr.dfi as inputs, "Action" will cause MACSYMA to call the rommand with the object.s as arguments and will rrt.urn an intrrnal represr.ntation of the answer as its out­ put. In t.he case of "Find a variable", the command is MACSYMA'Ii ~~valuator 1\ffiVAL.

The alternative to obtaining a pre-computed object is to const.rur.t a new one. The goal of the "Construct an ob­ ject" mrt.hod is t.o produce an object defined as /(a). The fitrat . c~y is to !ir.arclt the data hat;e for a command c which computes /, ~ivr.n preconditions p on the argument and ~rnrral prrrcquisite q, as shown in figure 3. The outputs of "Fetch" arc the c.ornmand c, the preconditions p, and the prerequisite q. Ilaving found such a command, the method t.hr.n obtains the ar~mnent a in a form that satisfies p, ar.hievr.s q, and r.xer.utes the command. The extension to multiplr. argument functions is straightforward.

The ;tr~umentK of a funr.t.ion are obtained by the "Obtain ar~mHr.nt.-" method . If a particular argument must satisfy a prr.rondition, MlJSEil. usefi the "Obtain and Convert" mrt.hod . If not, it ~>imply calls "Obtain" recursively.

The ~t.ral.rgy of "Oht.ain and Convert" is to obtain the ar~mnr.nt and then transform it to satisfy the precondi· tion. In doing so, it searches for a suitable transformation, arhicvrs its prerCCJllillit.eR, and applies the transformation, as ~>hown.

The full MUSF:Il. model is con,;iderably larger than the smaiJ fra~mcnt shown here (sec (Gcncscrcth 1978]). In ad­ dition, MUSER has the ability to invoke doma\n depend­ ent. pron>:durrll when appropriate. As MUSER generates earh suh~oal in solving a problem, it searches its data base for auy clomain dependent methods with a matching goal. If r;nrh a procedure is found, it is used just as if it were a method In the MUSER model. As an example, consider the procedure SOLVEQD r;hown in figure 4. SOLVEQD comput.rs the coefficients of the quadratic and then plugs the resnlt.11 into t.he quadratic formula. Jf MUSER needed to ohtain the root of a quadratic, it would find SOLVEQD and invoke it wit.h the corresponding "Obtain an object" mC'f.hod a11 1Hiprrgoal.

A plan i11 thr re,;ult of executing a parameterized proce­ dural net. with part.icular bindings for the parameters. More formally, a plan is a PPN in which all network objects arc bound to real world objects, all parent-child cycles have bern eliminated by copying, and all disjunctions havr brrn rr11olvr.d. Additionally, a plan includes pointers to aiJ dat.a base assertions accessed in constructing it.

Figure 5 ~;howN a plan for computing the coefficitnt ClG6 of X in an expression G6. The data base documents that the COEF'F command computeR the coefficient of an ex­ ,preNsion w long ali it i11 expanded. In trying to obtain the argument. in expanded form, MUSER finds that the EXP,\ND r.mmnand return11 an r.xpanded ver11ion mathe­ mat.ically equivalent to it.s argument. Hence,. EXPAND is call rei on thr. value of no, and the result (GE) is p;1ssed as ar~unu·nt t.o COBFF. Note that this plan is completely corred, unlike the u,;cr's plan in figure 1.

4. Overview o( the Consultant

In hanclling a violated expectation, the Advisor's first step is to rr.nmst.rud the user',; plan. When the Advisor is called, it ha" il dat.a the relevant sequence of MACSYMA command~; and, if t.hr. u~cr has not already supplied it, the Advilior obtains from him a statement of his overall goal. The romLnands arc assumed to represent the fringe of a plan in which t.he root is the user's goal. The pur­ pose of plan reconstruction is to fill in the intervening t;l.rur.t.ure.

The Advisor's plan reconstruction procedure ha& three part.s. The first st.r.p is t.o convert the user's actions into a sin~lc-level dat.aflow graph. The second step is mcchanic'al plan rrcoj!;ni.tion. In principle, the plan could be obtained hy askin~ t.lu~ u~>r.r to describe in detail how he intended to achieve his goal. However, human consultants are able t.o bypass most. and sometimes all such questioning, and it would be preferable if the Advisor could do as well. Furthermore, in practice the user often won't know what term,; t.o mr. in de,;crihing hi,; intentions, or the description might. he too tedious for his patience to bear. Therefore, to hr. r.lfedivr., a consultant must reconstruct as much of t.he user's plan as possible with as little questioning as possible. The third p.hase of plan acquisition ia user int.r.rro~at.ion. Whrn t.he Advisor's plan recognition pro­ cedure fails t.o produce a complete plan, the Advisor tells t.hr. user what it ha,; figured out and a,;ks for help.

The plan recognition procedure is a he~ristic "parsing" procedure that searches the partially reconstructed plan for plan fragments (from its "Plan Library") or error frag­ ment. ~ (from its "Error Library"). Since the user's plan is assumrd t.o be an instantiation of the MUSER model, the Advisor also uses t.hc MUSER model as data in inferring furt.hr.r ,;t.rud.ure. AIJ possible parsings are simultaneously cxplorrd unl il a single plan is found that ties the user's goal t.o his dataflow graph. The first such "parsing" of the r.raph to be found is trntat.ivcly adopted by the Advisor as the correct plan. If at some later stage the Advisor finds that. itli lent.at.ivr. plan does not correspond with the user's, the Advi~>or rliminates it from consideration and searches for a not. her parsing. In some cases, the recognizer elm rule out potential plans by checking the component data base assertions against its model of the user's beliefs. If the tent.at.ivr. plan includes a misconception the user is known not t.o possess, t.he plan is rejected and another sought. In the rpisode shown in figure 1, the Advisor was able to reconstruct t.he plan shown in figure 6. lh comparing this plan to the one shown as figure 5, note the different data hasr assertion about the command COEFF and the rrsult.ing me of the "Obtain" method instead of "Obtain and Convert" .

Once t.he Advisor has a version of the user'a plan, it tries to idrnt.ify t.hr. miRronception . Thr. first st.ep in doing this is t.o acquire a ~<u~;picion of what might be wrong. Suspicion can he aronsr.d r.it.her by recognition of some standard error in t.he usrr's plan or by a general model debugging procrss. Once a suspicion is aroused, the Advisor confirms that. it i~; a mi~;ronccption by a~king the user whether or not. he hrlievcs it . In the example, the Advisor found that the assertion about COEFF in the reconstructed plan was incorrect and then asked the user whether he believed it.

Onc:r. " misconception has heen identified, the Advisor rorrr.ds it. ;mel ~r.nr.rat.es advir.e. Jn the current implemen· tat.ion all standard errors have scripts associated with t.hr.m. When sur.h an rrror is detected and confirmed, the script. is recited to the user. These scripts arc prepared by the Aclvisor'.s pro~rammer and contain all the neces· sat·y dired.ionfl. rn other caflefl, the Advisor follows a more general procedure.

In t.hi" more ~cnrral procedure, correct.ing the misconcep­ tion is easy; the user is simply told that his misconception is wrong. Jr there is a corresponding r.orrect fact about the command or variable involved, this information is then supplied. In this example, the user was first told the correct information about COEFF.

llnfortunat.cly, Rimply rdat.ing thr. correct information about t.hr. wrong r.ommand doesn't alway11 help the URer find the ri~ht command or option. Misconception correc· tion is intended t.o impron Ute mer's knowledge about the commt11tcl or vari.1h/c Ufled. Helping him to useful infor· mat.ion t.o i\c:hicvr. t.he goa/ involved is the purpose of the "misc:onr.r.pt.imr altrrnat.ivc" step of advice generation. In ordrr to find an alternative, t.hc Advisor executes (on its own clata hasr.) t.he same "Fetr.lt" call with which the user rct.rievecl hi" misronccplion (as indicated in the plan). If it succeeds, t.he information is conveyed to the user, as in the example. Hit fails, no further action is taken. In either case t.hc Advisor considers its work done and the epi!ioclc ends.

.5. Summary

The Aclvi,;or iR implemented in MACLJSP and r.onsists of about. JO pa~cs of vrry compac.t code, includin& the data base manipulation 'routines and the MUSER problem sol­ ver hut not. r.ounting the dat.a base about MACSYMA. (At the moment the data base includes information about a few clozr.n r.ommands only.) As mentioned earlier, there is no n<~t.tar<~l lan~ua~c interface. Prdiminary testing of the system by hand tran!ilat.ing c:on11ultation sessions into the Aclvi sor'11 internal lan~tuap;e 11hows that the major shortcomings arc its lack of knowledge of the task environ· mr.nt (matl;cmatics) and the weakness of the MUSER model. A full description of the impl'ementation and the t heory on which it is based can be found in [Genesereth Hl7R] .

The important contributions of this research arc (1) its r.mpha~;iR on the need for con~>ultation in any suffitiently r.omplrx domain and (2) its consultation technique. In general, a consultant is ner.essary whenever one is faced with a problem solving situat.ion in a domain one docs not fully undcrst.and. The lack of knowledge may be incidcn· tal, as it is whC'n the domain or device is fairly simple but. t.imc r.onst.raints make it impo11sible for the user to learn all that is necessary (e.g. using a calculator or os­ cillosrope). Or it may be essential, as when the domain is very complex and the user un 't possibly learn everything (e . ~ . MACSYMA).

The implementation described here is based on the belief that a r,ood ronsultant must possess not only substan· tial knowlcd~c of its material but also a good model of its nser'R knowledge. The key point of the paper is that pl<~n rcc:onfltrudion and analysis is a good way to gain thi~> user model. The consultant described here utilizes a formal domain-independent problem solving model as a ~rilmmar for plan reconstruction. Alt.hough the Advispr also u~;es an rrror library, the plan grammar allows it to clia~nosc bug11 it has not previously encountered. This not.ion of a person's "plan" for ~>olving a problem iR central t.o consultation and should prove useful far man-machine inter<~ct.ion in general.