A sound and fast goal recognizer

A Sound and F ast Goal RecognizerNeal Lesh and O r e n E t z i o n i* Department of Computer Science and Engineering University of Washington, Seattle, WA 98195neal@, etzioni@ (206) 616-1849 F AX: (206) 543-2969A b s t r a c tT h e bulk of previous work on goal and planrecognition may be crudely stereotyped in oneof t w o ways. "N e a t" theories — rigorous, jus-tified, but not yet practical. "Scruffy" systems— heuristic, domain specific, but practical. Incontrast, we describe a goal recognition m o d-ule that is provably sound and polynomial-timeand t h a t performs well in a real domain. Ourgoal recognizer observes actions executed by ah u m a n, and repeatedly prunes inconsistent ac-tions and goals f r o m a graph representation ofthe d o m a i n. We report on experiments on hu-man subjects in the U n i x domain t h a t demon-strate our a l g o r i t h m to be fast in practice. Theaverage t i m e to process an observed action w i t han i n i t i a l set of 249 goal schemas and 22 actionschemas was 1.4 cpu seconds on a SPARC-10.1 I n t r o d u c t i o n and m o t i v a t i o nPlan recognition (e.g. [Kautz, 1987; Pollack, 1990]) is the task of identifying an actor's plan and goal given a partial view of t h a t actor's behavior. We have focused on identifying the actor's goal. There are several poten-tial applications for an effective goal recognizer. Goal recognition is useful for enhancing intelligent user i n-terfaces [G o o d m a n and L i t m a n, 1992]. urthermore, a goal recognizer would allow an autonomous agent to pro-vide useful services to the people it interacts w i t h, such as completing their current tasks and offering advice on how to better achieve future goals. T h i s paper describes a goal recognition module. We do not consider how to integrate a goal recognizer into an agent's architecture.In our scheme, the system observes the actor executing a sequence of actions. T h e actor does not necessarily know she is being observed (this is keyhole recognition). T h e system attempts to identify the actor's goal as early "Many thanks to Denise Draper, Terrance Goan, Robert Goldman, Steve Hanks, Henry Kautz, Nick Kushmerick, Di-ane Litman, Mike Perkowitz, Rich Segal, Tony Weida, and Dan Weld for comments and discussion. Special thanks to Keith Golden and Mike Williamson for their ongoing sup-ply of critique and coffee. This research was funded in part by Office of Naval Research grant 92-J-1946 and by National Science F oundation grant IRI-9357772. as possible. W h a t does it mean to identify the actor's goal? To a t t r i b u t e a goal to an actor is to predict t h a t the actor's actions, b o t h observed and unobserved, w i l l be the execution of one of the plans for t h a t goal. The actor's goal may be a conjunction of various goals such as "T a k i n g out the trash and fixing the car".T h e following scenario illustrates the sort of conclu-sions we want our goal recognizer to produce. T h e ob-served actor is a computer user, entering commands into a U n i x shell. Suppose we observe:>cd /p a p e r sThere are many plausible goals at this point. T h e actor might be searching for a particular file. Or perhaps she wants to know how much memory is used by the /p a p e r s directory. B u t her goal is not to find a free printer. Nor is she reading her m a i l. W h y bother to change directo-ries for these goals? Changing directories is irrelevant to these goals and we assume the actor does not execute irrelevant commands. If we allowed a r b i t r a r i l y many ir-relevant actions then we could not predict the actor's goal because all the observed actions m i g h t be unrelated to her goal. Suppose that we next observe:>l sp a p e r.t e x p a p e r.p sT h e second line is the o u t p u t f r o m I s. T h e goals we previously rejected are still rejected. Let's reconsider the goal of determining the memory usage of /p a p e r s. T h e o p t i m a l approach is to execute du instead of I s. If actors acted optimally, we could reject this goal. B u t actors do not always act optimally. T h i s actor may next execute I s -1 o n p a p e r.t e x and o n p a p e r.p s and add the memory usages of the files together. T h u s, Is may be part of a suboptimal plan to determine the memory usage of /p a p e r s. Now we observe:>g r e p m o t i v a t i n g p a p e r.t e xWe now reject the memory usage goal. We also reject the goal of searching for a file named p a p e r.t e x because the g r e p command does not contribute to i t. T h e actor might, however, be looking for a file t h a t contains "m o-t i v a t i n g" or perhaps for a file t h a t contains "m o t i v a t i n g" and is named p a p e r.t e x.In the following sections we articulate the definitions, assumptions, and a l g o r i t h m we use to express, j u s t i f y, and produce these conclusions. A l t h o u g h we validate our system in U n i x, our a l g o r i t h m and f o r m a l results are domain independent.1704 PLANNING2 Overview of the paperO u r objective is to b u i l d a goal recognizer that performs well in large, real domains. We need a way to quickly determine if a goal is inconsistent w i t h the observed ac-tions. Informally, a goal is inconsistent w i t h the observed actions if the actor could not possibly have executed the actions as part of a plan to satisfy the goal. To determine consistency, we must reason about all plans for each can-didate goal. To reason tractably, we borrow techniques for constructing and m a n i p u l a t i n g graph representations of planning problems, originally developed to produce search control for generative planners [Etzioni, 1991; S m i t h and Peot, 1993]. By analyzing interactions among the actions, action schemas, and goal schemas in our con-sistency graphs (defined below), we detect cases where no valid plan exists for a goal.Most plan recognition algorithms run in exponential t i m e and have not been shown to perform well on large problems. In contrast:• Our a l g o r i t h m is sound (never rejects a goal G un-less our assumptions entail that G is not the ac-tor's goal) and runs in polynomial t i m e in the size of the i n p u t goal recognition problem. T h i s input issmaller t h a n the corresponding i n p u t to most plan recognizers.• Our i m p l e m e n t a t i o n is fast. We have tested our sys-t e m on data collected f r o m human subjects in the U n i x d o m a i n. T h e average time to process an ob-served action w i t h an i n i t i a l set of 249 goal schemasand 22 action schemas was 1.4 cpu seconds.1In our f o r m u l a t i o n, goal recognition is semi-decidable. It follows t h a t our p o l y n o m i a l-t i m e algorithm is incom-plete, i.e. it is not guaranteed to reject every inconsistent goal. In our experiments, however, the a l g o r i t h m rejects most inconsistent goals.T h i s paper is organized as follows. Section 3 defines our terms, the i n p u t and o u t p u t of a goal recognizer, and states our assumptions. Section 4 introduces consistency graphs, describes our a l g o r i t h m, and works through an illustrative example. Section 5 describes our empirical validation. F inally, sections 6 and 7 discuss related work, the l i m i t a t i o n s of our system, and future work.3 Problem formulationWe begin w i t h the i n f o r m a l story. The actor constructs and then executes a plan to solve her current goal. A l-though plans may contain conditionals, the observable behavior t h a t results f r o m the execution of any plan is a sequence of actions. T h e system observes a prefix of this action sequence. A plan is consistent w i t h the observed actions A iff t h a t plan has an execution w i t h prefix A. A goal is consistent w i t h A iff there exists a consistent plan for t h a t goal. A key question is w h a t constitutes a plan for a goal? We assume the actor constructs plans w i t h-out any irrelevant actions. We further assume the actor constructs plan P for goal G only if P might achieve G :T h e data we have collected is publicly available. Send mail to neal@ for details. given the actor's beliefs about the world. T h i s assump-tion suggests the system has access to the actor's beliefs.The system is given, as i n p u t, an arbitrary subset of the actor's beliefs. T h e more of the actor's beliefs the systemis given, the more goals it can prove inconsistent.3.1 P l a n n i n g l a n g u a g eOur formulation is general enough to accommodate many planning languages. We use U W L [Etzioni et ai, 1992], an extension of the S T R I P S language, because itcan express information-gathering goals and actions w i t h sensory effects. T h i s is necessary to distinguish between Unix commands such as pwd and cd. In U W L, statesare sets of literals. A literalis a possibly negated atomic formula. T h e conjunction of literals in a state describesall relevant relationships in that world state. Models and goals are also sets of literals. T h e conjunction ofthe literals in a model or goal is a partial descriptionof a state. A goal schema is a set of literals which can contain variables. A schema can be instantiated by re-placing variables w i t h constants. F or example, the goal schema for searching for a file w i t h some name ?n (where?n is a variable) can be instantiated to f o r m the goal of searching for a file named p a p e r. t e x. An action schema consists of a name, a precondition set, and an effects set.An action is an instance of an action schema, w i t h a unique id number. The CD action schema, for example,can be instantiated into many different actions, such ascd /p a p e r s or cd b i n. M u l t i p l e executions of the same action are distinguished by their id numbers.Informally, plans are programs composed of nested conditionals and actions.For brevity, we w i l l not de-fine plans but instead make use of a function, Executor, which acts as an interpreter for plans. Executor is a many-to-one mapping that maps a plan and state to the action sequence t h a t results f r o m executing the plan inthe state. We often refer to an action being in a p l a n, orone action coming before another. A c t i o n A i is in planP iff there exists a state S such that Executor(P ,S) —* [..,Ai,..]. If Ai and Aj are b o t h actions in plan P, thenA1 is before A3 iff in every execution of P in which A j appears, A1 appears prior to A j.3.2 C o n s i s t e n c yA plan is consistent w i t h the observed actions if some execution of the plan might produce those observations.D e f i n i t i o n 1 Plan P is consistent with sequence of ac-tions A iff there exists state S such that Executor mapsP and S to a sequence of actions of which A is a prefix.Consistency of a goal is defined relative to a set of action schema A and a model M. A goal is consistentw i t h the observed actions only if there exists a consistent plan, b u i l t out of A, for that goal. A plan for a goal must potentially-achieve the goal, given model M, and containno irrelevant actions. We now define these terms.D e f i n i t i o n 2 Plan P potentially-achieves goal G given model M iff there exists a state S such that M C S andG is satisfied by executing P in S.If P potentially-achieves G given M then P also potentially-achieves G given any subset of M.T h i sLESH AND ETZIONI 1705• A goal recognizer takes a goal recognition problemII as i n p u t and returns a set of goal schemas G'.• T h e i n p u t II = (A,M,A,G) where— A is a sequence of actions. A is assumed to bea prefix of the actions executed by the actor.— M is a set of beliefs. M is assumed to be a subset of the actor's beliefs.— A is a set of action schemas. A is assumed to be a superset of the action schemas the actorplans w i t h.— G is a set of goal schemas. The actor's goal is assumed to be an instance of an element in G.• T h e o u t p u t Q' is a subset of G such that for every goal schema in G Q' there exists an instance of t h a tgoal schema G,- and a plan P such that:— P could achieve goal G, given the actor'sbeliefs (constrained by M).— P contains no irrelevant actions.— P is composed of actions f r o m A.— Some execution of P is a sequence ofactions w i t h prefix A.• M u l t i p l e Goals: T h e actor's goal may be the con-j u n c t i o n of various goals, such as "T a k i n g out thetrash and fixing the car and w r i t i n g a paper"Figure 1: Input/output specification for a goal recognizer. makes it easy to treat the beliefs M in the i n p u t II as asubset of the actor's beliefs.W h a t does it mean for a plan to contain no irrelevant actions? We require t h a t every action in the plan support some action in the plan or the goal.2 We define support between actions as follows (the definition of an action supporting a goal is very similar).D e f i n i t i o n 3 Let A i and Aj be actions in plan P. A x supports Aj iff A i is before Aj, A i has an effect that uni-fies with a precondition p of Aj, and no action between A i and Aj in P has an effect which negates p.Support is blocked only by an action that negates the supporting effect. One upshot is that we allow redundant sensory actions in the actor's plans. In other words, we do not assume that the actor remembers everything she learns f r o m executing sensory actions. We can now define consistency for goals.D e f i n i t i o n 4 Goal G is consistent with action sequence A, given model M and action schemas A, iff there ex-ists plan P such that (1) P is consistent with A, (2) every action in P is an instance of a schema in A, (3) P potentially-achieves G given model M, and (4) every action in P supports an action in P or supports G.A goal schema is consistent if any instance of that goal schema is consistent.2This is a much weaker requirement than that the plan be minimal in order to contain no irrelevant actions. 3.3 I/O o f a g o a l r e c o g n i z e rA goal recognition problem II is a four-tuple {A, M, A, G) where A is an action sequence (the observations), M isa model (a subset of the actor's beliefs), A is a set of action schemas (the actor's plan is composed of actionsin this set), and G is a set of goal schemas, A goal rec-ognizer takes a goal recognition problem and returns G'C G. Ideally, G' is the set of goal schemas in G t h a t are consistent w i t h A, given M and A. F igure 1 summarizes the i n p u t/o u t p u t specification for a goal recognizer.We view goal recognition as the process of discarding goal schemas f r o m the i n p u t set G and returning the re-maining, unrejected goals. A sound recognizer never dis-cards a consistent goal. A complete recognizer discards every inconsistent goal.When the recognizer returns G'', this means "the ac-tor's goal is an instance of a schema in G*.n If the recog-nizer is sound, this conclusion is justified by the following assumption.A s s u m p t i o n 1 The actor's goal is consistent, given model M. and action schemas A, with the (full) action sequence the actor executes, of which A is a prefix. Fur-ther, the actor's goal is an instance of a schema in G. Determining consistency is exponential in the length of the longest plan (t h a t doesn't go through the same state twice). In an unbounded domain, consistency is semi-decidable. In the next section, we describe a sound, polynomial-time, but incomplete goal recognizer.4 Our goal recognizerWe now present our goal recognizer, i.e an a l g o r i t h m which takes a goal recognition problem II and returnsa set of goal schemas. T h i s goal recognizer is provably sound and runs in polynomial t i m e. In this section, we present our theorems and provide intuitions for why they are true. The full proofs are in [Lesh and E t z i o n i, 1995].In section 5, we validate our a l g o r i t h m using data gath-ered in the Unix domain.Our goal recognizer constructs and manipulates a sin-gle consistency graph T based on the i n p u t I I. A con-sistency graph is a directed graph in which the nodes are actions, action schemas, and goal schemas. F igure 2 shows a simple consistency graph.Informally, the consistency graph represents the plans the actor might be executing. T h e actions in T represent the observed part of the actor's plan. T h e action schemasin T represent possible unobserved actions. T h e goal schemas in T represent the goals the actor m i g h t have. The edges in T indicate when one action can support another action or goal. A consistency graph is correct if all consistent plans are represented by the graph.D e f i n i t i o n 5 A consistency graph(V,£) is correct, relative to the input goal recognition problem II = {A, M, A,G), iff the following three properties hold:(P I) V contains every consistent goal schema in G,(P2) V contains action schema A E A if an instance of X is in any consistent plan for a goal in G, and(P3) S contains the edge (Vi—*Vj) for every Vi,Vj G V where V i (or an instance of V i) supports Vj (or an in-stance ofV j) in some consistent plan for a goal in G.1706 PLANNINGLESH AND ETZIONI 1707strength of this assumption, we can reject a goal if no plan exists which could achieve i t , given the actor's be-liefs. A simple case where this arises is when a conjunct of some goal is false in the model M and not supportable by any effect of any schema inT h e o r e m 6 (Impossible Conjunct)I F G i s insupportable and false i n M THEN - G is legal.T h e Obsolete Rule leverages our assumption that ev-ery action supports, directly or indirectly, the goal. If some action schema is not path-connected to any goal in then no instance of can support any goal inSince is correct, it contains every consistent goal. Thuscannot be in any consistent plan for a consistent goal.The following a l g o r i t h m is a sound goal recognizer t h a t runs in p o l y n o m i a l t i m e in the size of I I.F u n c t i o n 2 recognize(II) ::: Apply the rules to quies-cence on i n i t i a l i z e (I I ). Return all goal schemas in the resulting graph.T h e o r e m 8 Recognize is sound and polynomial-time in the size of XI.T h e initialize function produces a correct graph, and since we only apply legal rules, the final graph is correct as well. A correct graph contains every consistent goal schema. Thus our a l g o r i t h m returns every consistent goal schema and therefore is sound.T h e i n i t i a l graph contains \G U Au A\'2 elements. In every iteration, we potentially apply every rule to every element. Each rule can be applied to an element in linear time in the size of the graph. Our a l g o r i t h m halts as soon as applying all the rules fails to remove anything. Thus, the m a x i m u m number of iterations is the number of elements in the i n i t i a l graph. An upper bound for the worst case r u n n i n g t i m e is thus k x \Q U A U A|6 where k is the number of rules. T h i s is a loose upper bound, intended only to show t h a t our a l g o r i t h m is polynomial. Our actual implementation is optimized for our cur-rent rule set. We have analyzed the dependency relation-ships among our rules, and fire only a subset of the rules in each iteration. A d d i t i o n a l l y , we often apply many rules in a single procedure. We test, for example, the connectedness between an observed action and all goals w i t h one procedure rather than a call for each goal. T h i s is roughly times faster than checking every goal sepa-rately. Furthermore, although the above a l g o r i t h m pro-cesses all observed actions at once, our actual system is incremental. We fold new actions into the processed graph rather t h a n re-initialize the graph every time a new action is observed. W h e n we observe a new action A n , we add to fully connect A n to and f r o m every node and then apply our rules to this new graph.4.1 E x a m p l e t r a c eNow we present a sample trace. T h e i n p u t to the recog-nizer is II = (A ,M , A, 0) where A = [cd /p a p e r s , g r e pm o t i v a t i n g p a p e r.t e x ], contains representations o f C D , LS, G R E P , and L P Q , is empty (we know none of the actor's beliefs), G contains G\ = "F i n d a file named paper.tex", G 2 = "F i n d a file named paper.tex t h a t con-tains m o t i v a t i n g ", and G 3 = "F i n d a free printer."T h e initialize function produces a graph similar to the one in Figure 2 except t h a t it is f u l l y connected.In the first iteration, the M a t c h i n g Rule removes 61 edges, resulting in the graph shown in Figure 2. T h eOrder Rule removes edge p a p e r s ). The Prefix Rule removes e d g e s 'p a p e r s ), (LS /p a p e r s ), and ep). In the second iteration, Goal Connection removes G 1, G 3, and edges and because they point to removed goals.In the t h i r d iteration, the Obsolete Rule removes L P Q. In the fourth iteration, no rules fire. Set is re-turned.5 Experimental validationIn this section, we describe how we collected our data, how we converted it into goal recognition problems, and how our system performed on these problems.We gather the raw data as follows. A f t e r reading some instructions, the subjects (students in our department) are given English goal descriptions. T h e subjects try to solve each goal by executing Unix commands. For each task, the subjects indicate success or failure. We p r o h i b i t subjects f r o m using certain constructs and commands such as pipes and the command awk.We converted this raw data into goal recognition prob-lems. To generate the observed actions A, we matched each observed U n i x command to an instance of our ac-t i o n schema for t h a t c o m m a n d. We filtered o u t com-mands we considered to be typos. We let A be our ac-tion schemas for 22 U n i x commands, including all those used by our subjects. We let indicating t h a t we know n o t h i n g about the actor's i n i t i a l beliefs. T h i s is the most conservative setting. T h e goal space consisted of 249 goal schemas: 129 file-search goal schemas (goals of locating a file t h a t has some qualities), 15 assorted (non file-search) goals, and the 105 pairs of these 15 goals. We evaluated our goal recognizer on the following goals:(G 1) Find a file named "core".(G 2) F i n d a file t h a t contains "m o t i v a t i n g " andwhose name ends in ".t e x ".(G 3) F i n d a machine t h a t has low load; anddetermine if Oren Etzioni is logged into the ma-chine named chum.(G 4) Compress all large 10,000 bytes) files in theTestgrounds subdirectory tree. Goals G\ and G 2 are two of the 129 file-search goals. Goal G3 is one of the 105 pairs of the assorted goals. This goal demonstrates our ability to handle interleaved plans for multiple goals. Goal G 4 is one of the 15 assorted goals. Table 1 summarizes our results. An update is when one observed action is processed. T h e length of the plan is the number of actions the subjects executed to achieve the given goal. T h e remaining goals are the goals still in the graph after the last update.1708 PLANNINGOur goal recognizer performed very well on these data. T h e average t i m e to process an observed action was1.4 cpu seconds on a S P A R C 10 by code w r i t t e n in lisp.A l t h o u g h the goal recognizer is incomplete in general, it detected every inconsistency between the goals and observations in our experiments. Thus, our a l g o r i t h m solved the goal recognition problem, as we have formu-lated it, very thoroughly and very quickly.B u t did it work? D i d our mechanism recognize peo-ple's goals? In some sense, goal recognition occurs when the recognizer returns a single, consistent goal. T h i srarely occurred in our experiments.F or example, forgoal G1, over half the goals remain. T h e subjects only executed cd and Is until they found c o r e. These com-mands b o t h support almost all file related goals. Thus, almost all file related goals are consistent w i t h the entire plans executed to solve goal G\.A common assumption in many plan recognition paradigms is t h a t the actor's actions w i l l eventually serve to distinguish a single plan (or goal). Our investigations suggest this is unlikely to be true in the Unix domain, even w i t h relatively small sets of possible goals. We view our goal recognizer, which quickly prunes out the incon-sistent goals, as a useful module. The next step might be to assign probabilities to the remaining goals. In [Lesh and E t z i o n i, 1995] we propose a very different solution based on version spaces [Mitchell, 1982]. We view goals as hypotheses. W h e n a single, strongest consistent goal-hypothesis exists, we know t h a t achieving this goal w i l l benefit the actor. Due to space limitations, we describe a special case of this approach, subset convergence,t h a t works well on these problems.We define subset convergence to occur when all the goals in the space share a common (non-empty) subset. Subset convergence is useful because an agent m i g h t be able to make use of the fact t h a t some goal G' is part of the actor's goal. T h e last column in Table 1 indicates when subset convergence occurred for each goal (except goal G, for which subset convergence did not occur).Consider goal G2.A l l but 37 goals are rejected when a g r e p is observed. T h e remaining 37 goals all involve searching for a file t h a t contains some word and, possi-bly, has some other characteristics (e.g. name ends in ".t e x"). T h e goal of looking for a file t h a t contains some w o r d is a subset of all 37 of these goals. F or G2, subset convergence occurred, on average, after four actions were observed, which was an average of 12 actions before the subjects completed the task.For goal G3, the subject's first command always i n d i-cated t h a t part of their goal either was to find a machinew i t h a low load, or to determine if Oren was logged into chum. Thus, subset convergence occurred immediately.By the second or t h i r d command, the goal space con-verged to goal G3.For goal G4, the 15 unrejected goals are G4 itself andthe 14 pairs of the assorted goals that include G4.N o t h-ing the subjects did to achieve G4 was contrary to (or inconsistent w i t h) the goal of compressing all large files and, for example, finding a free printer. A g a i n, subset convergence detects, early o n, t h a t all 15 goals includethe goal of compressing the large files.6 Related workMost plan recognizers (e.g. Kautz's) require, as i n p u t, a plan or event hierarchy which consists of top-level goals,p r i m i t i v e actions, and composite or complex actions. Our input, however, differs significantly. Essentially, we take only the goals (input G) and p r i m i t i v e actions (in-put A). Our definition of w h a t constitutes a valid planfor a goal replaces the complex actions. Under our for-m u l a t i o n, the goal recognizer must consider how the low level actions can be composed i n t o plans. E l i m i n a t i n g the complex actions is significant in t h a t there may beup to 2'A I complex actions in the hierarchy. A l t h o u g h our input is more compact, it is less expressive; we do not allow arbitrary constraints to be placed between stepsin plans. We do, however, allow a r b i t r a r i l y long plans which an acyclic plan hierarchy does not.A rarely duplicated feature of Kautz's theory and sys-tem is the ability to recognize concurrent, interleaved plans. Kautz assumes t h a t actors execute the m i n i m u m number of consistent plans. We can proceed similarly ifwe assume t h a t the concurrent execution of plans P1...P nfor goals G\...G n is always the execution of some single plan P for G\f\ ... A G n-T h e technique to recognize interleaved goal-solving is to first run our a l g o r i t h m, asn o r m a l, on the given goal space G. If all goals are re-jected then run recognition on all pairs of goals, G2 . If this space collapses, run recognition on G3.A n d so on.T h i s approach is not polynomial or sound because we ap-proximate consistency, if we allow arbitrary numbers of plans (or goals) to be interleaved. We believe, however,t h a t people rarely interleave large numbers of plans. If we assume that actors only pursue at most, say, 3 or 4 goals simultaneously then our technique, which can ter-minate at G6 or G4, becomes p o l y n o m i a l and sound.There has been some work (e.g. [Pollack, 1990]) on recognizing invalid plans. We allow some invalid plans, because we allow all plans which could achieve the goal based on the actor's incomplete model of the w o r l d. Some of these plans w i l l not achieve the goal when exe-cuted f r o m the actual world state. We cannot recognize plans b u i l t out of incorrect models of the action schemas,as Pollack's system can. Her system does not considerall allowable plans, as ours does, but instead searches fora good explanatory p l a n.There is some work on t r y i n g to select the best or most probable plan or combination of plans (e.g. [Charniak and G o l d m a n, 1991]). O u r work complements this re-LESH AND ETZIONI 1709。