Adaptive Goal Recognition

1 Introduction

Goal recognition (e.g. [Kautz, 1987; Carberry, 1990])_ is the task of inferring a person's intentions given a partial view of their actions. As noted in [Maes and Kozierok, 1993; Bauer, 1994; Ardissono and Cohen, 1995], goal recognition is difficult, in part, because people do not all act alike. The same actions can warrant different con­ clusions depending on who executed them. For exa;mple, when I go to the College Inn Cafe the waitress invariably brings me my usual order, scrambled eggs and rye toast, without asking me what I want. With a few exceptions discussed in section 7, previous approaches can provide user-specific recognition only by having a human expert hand-tune the recognizer for each person.

*Many thanks to Sandra Carberry, Oren Etzi~ni, K_eith Golden Steve Hanks, Anna Karlin, Nick Kushmenck, D1ane Litman', Dan Weld, and the reviewers of the submission draft of this paper for comments and discussion. This research was funded in part by Office of Naval Research grant 92-J1946, by ARPA / Rome Labs grant F30602-95-1-0024, by a gift from Rockwell International Palo Alto Research, and by National Science Foundation grant IRI-9357772.

Adaptive goal recognition

Neal Lesh*

Department of Computer Science and Engineering University of Washington, Seattle, WA 98195 neal@cs.washington.edu

(206) 616-1849 FAX: (206) 543-2969

We present the Adapt algorithm for automatically adapting a recognizer to perform well for an individual, given a goal recognizer, a set of adaptations that can be made to the recognizer, and a sample of the person's recent behavior.

We treat the person's recent behavior as training data, and attempt to find the combination of adaptations with which the recognizer performs best on the sample behav­ ior. For tractability, we use hillclimbing to search the space of all possible combinations of adaptations. The primary challenge we address is how to evaluate the per­ formance of the input goal recognizer with a candidate set of adaptations on the input sample data. The input data is not annotated with the person's actual goals.

We perform unsupervised learning by treating goals as verifiable predictions of future behavior, as opposed to mental state [Pollack, 1990] or explanations [Hobbs et al., 1988]. For example, if the recognizer indicates that a computer user's goal is to delete all her backup files, then we view the recognizer's output as predicting that the user will delete all her backup files. This goal-prediction is correct if she does go on to delete her backup files .

We empirically evaluate Adapt on the BOCE goal rec­ ognizer [Lesh and Etzioni, 1995; 1996]. Our experiments in two domains show that applying Adapt to the BOCE recognizer can improve its performance by a factor of two to three.

We use two metrics to gauge the quality of recognition: accuracy, the probability a recognizer's infere~ces a~e correct, and coverage, the probability the recogmzer will draw an inference. We formally prove a tradeoff exists between accuracy and coverage in goal recognition.

Our work makes the following contributions:

1. We present a framework for formally characterizing and comparing the performance of various goal rec­ ognizers.
2. We present an unsupervised algorithm for training a goal recognizer on samples of action sequences that:
3. Learns to filter out spurious actions.
4. Adapts to the particular distribution of goals that an individual pursues.
5. Learns in the presence of noise, such as if the ob­ served person occasionally abandons tasks.

In section 2, we define the adaptive goal recognit}on problem. In section 3, we prove there is a tradeoff be­ tween accuracy and coverage. In section 4, we present a function which estimates accuracy and coverage. In section 5, we present the Adapt function. In section 6, we describe our experiments. In sections 7 and 8, we discuss related work, future work, and conclusions.

2 Formulation

We now define the adaptive goal recognition problem.

2.1 Basic definitions

Let Q be the set of all persons, Q be the set of all possible goals, and A · be the set of all action sequences any per­ son might execute. The exec and goal functions describe the two relevant relationships among persons, goals, and action sequences. Let exec(q, A) hold iff person q is ob­ served to execute action sequence A. Let goal(q,g) hold iff person q has goal g. For simplicity, in this paper, we assume people have one goal at a time.

A goal recognizer maps an action sequence to either a goal g, indicating g is the person's goal, or nil, indicating the recognizer can not determine the person's goal given the current observations. Formally, a goal recognizer is a function from A · to Q U {nil}. While this definition is fairly broad, it does not allow for recognizers that output a probability distribution over goals (e.g. [Pynadath and Wellman, 1995]).

Samples of people's behavior are stored as episodes. An episode is a pair (A, S) where A is an action sequence the person executed and S is the state of the world at the time the person began executing those actions.

2.2 Adaptable recognizers

We refer to adjustments that can be made to a goal recognizer as adaptations. Notationally, for any set of adaptations T, let Rr be recognizer R with adaptations T. Different types of adaptations will be appropriate for different goal recognizers. We now provide a simpli­ fied description of the BOCE goal recognizer [Lesh and Etzioni, 1995; 1996] and two adaptations for BOCE.

BOCE recognizes goals based on an input set of ac­ tion schemas ACT, a set of goal predicates P1UV, and a set of background goals BQ. BOCE composes the ac­ tions in ACT into candidate plans and the predicates. in P1UV into candidate goals based on assumptions about what type of plans and goals people have. In particular, BOCE assumes (1) the person's goal is a conjunction of the input predicates, and (2) every action in the person's plan will either enable another action in that plan or en­ able the person's goal. The background goals in BQ are used to filter out actions that are not causally connected to the person's goal. For example, if BQ contains the goal "have cash" then BOCE will essentially disregard observing a person stop at an automatic teller machine rather than conclude that getting cash is in service of her current goal.

Two types of adaptations available for BOCE, which are discussed in greater detail in section 6, are:

• Add/remove background goal to BQ: Adding a background goal makes BOCE less sensitive to noise.
• Add/remove goal predicate to PR£V: Adding a predicate increases the number of candidate goals. This can improve accuracy but can also delay recogni­ tion because there are more goals to rule out.

Many other types of adaptations are possible. For example, an adaptation might add or remove a precon­ dition or effect from the domain operators. This could potentially improve recognition by allowing the goal rec­ ognizer to build plans based on what preconditions and effects the observed person believes actions have. In the widely used framework for plan recognition described in [Kautz, 1987], one possible adaptation is to add or re­ move an abstraction link between nodes in the plan hi­ erarchy. Another adaptation in Kautz's framework is adding or removing ordering constraints between steps in the plan hierarchy. Finally, the notion of background goals could be applied to almost any goal recognizer as a way of filtering out actions that typically reduce the performance of that recognizer.

2.3 Analytic model of recognition

We now present terms that allow us to analyze, evaluate, and compare goal recognizers.

The coverage of recognizer R is the probability that R will not return nil. Let domain V R be all action se­ quences A E A* such that R(A;) ::/:- nil. The coverage of recognizer R on person q is:

A recognizer's accuracy is the probability that it will correctly identify the person's goal given that it produces a goal. Formally, ACC(R,q), is: 0 if COV(R, q) = 0, else

A score function maps the accuracy and coverage of a recognizer to a single value. For example, a simple score function is ( 5 x accuracy) + coverage.

Different score functions will be appropriate for differ­ ent applications. An application that uses goal recog­ nition to offer to complete people's tasks might require very high accuracy to avoid bothering people with inap­ propriate assistance. On the other hand, a security sys­ tem using a recognizer to detect potentially dangerous behavior might sacrifice accuracy for coverage if it could tolerate false positives but did not want to fail to alert the authorities to any potentially dangerous behavior.

The above definition of accuracy measures the prob­ ability of the recognizer being correct on the portion of the behavior that the recognizer covers. The score func­ tion accuracy x coverage ranks recognizers according to their absolute-accuracy, or the probability of the recog­ nizer correctly identifying the person's goal. For many applications, however, accuracy x coverage is not a use­ ful evaluation metric because it does not differentiate between returning the wrong goal and returning no goal.

For the remainder of the paper, when clear from con­ text we will omit q. For example, we will use COV(R) instead of COV(R, q).

2.4 Adaptive goal recognition problem

As shown in figure 1, the input to Adapt is a set of episodes £, a score function score, a goal recog­ nizer R, and a set of adaptations T. The output should be the Ti ~ T that maximizes the function score(ACC(Rr;, q), COV(Rr;, q)).

• Given a set of episodes £, a score function score, a recognizer R, and a set of adaptations T
• Find Ti ~ T that maximizes the function:

• Where q is the person who executed the action se­ quences in episodes £, and Rr; is recognizer R with adaptations Ti.

Figure 1: The adaptive goal recognition problem

In section 4 we present an algorithm that estimates accuracy and coverage given episodes £. If£ sufficiently reflects q's behavior, then the recognizer that maximizes the above equation is the best recognizer for that person under the given score function. In section 6, we examine how large£ has to be to reflect the person's behavior.

3 Accuracy vs. coverage

A tradeoff between accuracy and coverage has been observed empirically in many fields including machine learning (e.g. [Mitchell et al., 1994]) and natural lan­ guage processing (e.g. [Soderland, 1997]). In this sec­ tion, we prove a tradeoff exists between accuracy and coverage in goal recognition.

For a given person q, we define the most accurate rec­ ognizer, MAR1, as follows . Recall that for any action sequence A and goal g there is some probability that g is q's goal given that q has executed A. For example, there might be a 25% chance that q's goal is to print her resume if she has executed the Unix command lpq -Palpha. Let P1 be the highest probability of any goal given any action sequence. Recognizer MAR1 out~uts goal g if the probability of g given the observed actwns is P1, otherwise MAR1 outputs nil. The second most accurate recognizer, MAR2 , returns g given action se­ quence A if the probability of g given A is the highest or the second highest probability, P2, over all goals and actions.

Formally, let Pi be the ith highest value of P(goal(gk) I exec( Ai)) for all Aj E A · and 9k E Q. The most accu­ rate recognizer is:

We define MARn recursively given the recognizer MARn-1· Formally, for n > 1, MARn(A) =

The following theorems establish the tradeoff between accuracy and coverage. Theorem 1 says MAR1 is the most accurate recognizer. . Theorems 2 and 3 state that MAR1 ,MAR2 , ... are ordered in terms of decreasing ac­ curacy and increasing coverage. Theorem 4 states that these recognizers represent the maximal points along the tradeoff between accuracy and coverage.

Theorem 1 (Most accurate recognizer) For all recognizers R1, ACC(Ri) ~ ACC(MARI).

Theorem 2 (Decreasing accuracy) For all i > 1, ACC(MARi) ~ ACC(MARi+I).

Theorem 3 (Increasing coverage) For all i > 1, COV(MARi) ~ COV(MARi+I).

Theorem 4 (Tradeoff) For all i ~ 1, there does not exist any recognizer R such that both ACC(R) > ACC(MARi) and COV(R) > COV(MARi) .

For brevity we omit the proofs, which will appear in the author's thesis.

4 Estimating accuracy and coverage

We now present an algorithm which estimates the accu­ racy and coverage of a recognizer on a person given a sample of that person's behavior.

Estimate takes a recognizer R and a set of episodes £ and returns two real numbers in the range [0,1] which are the estimated accuracy and coverage of R on the person whose behavior is described by£.

Estimate treats goals as predictions of future behav­ ior. Suppose that after observing six actions in a fifteen action sequence the recognizer reports that the person's goal is to compress all large files. This predicts the per­ son will compress all large files. This prediction is cor­ rect if the person compresses all large files, i.e. if the remaining nine actions serve to complete the goal.

To implement this idea, we need a means to determine if a given action sequence satisfies a given goal. The pro­ cedure Achieves(A,S,g) returns true iff action sequence A satisfies goal g assuming that it was executed from initial state S. Our implementation of Achieves returns true iff g does not hold in S but g does hold in stateS' where S' is the state reached by executing sequence A in state S . 1 Most planning languages provide a similar definition for Achieves, such as the Modal Truth Criterion [Chapman, 1987] for Strips [Fikes and Nilsson, 1971].2

1 A problem with this Achieves function is that it allows up to IAI - 1 irrelevant actions to be executed in service of achieving a goal, and thus might highly reward a goal

We assume the recognizer will be called after each ob­ served action until it infers a goal. For each episode (A, S), the recognizer is fed incrementally longer pre­ fixes of A until it produces some goal or outputs nil when given A. If the recognizer does produce a goal, we then determine if A achieves that goal from state S. In the following pseudo code, the Inputs variable counts the number of calls to the recognizer and Inferences and Correct count the number of inferences and correct inferences, respectively, made by the recognizer:

Estimate(recognizer R, episodes E)

1. Let Inputs= 0, Inferences= 0, Correct= 0.
2. For each ({a1, ... ,an},S) E E:
3. (a) Let i = 0
4. (b) WHILE i <nAND R(a1, ... ,a;)= nil
5. Let i = i + 1
6. Let Inputs= Inputs+ 1
7. (c) IF R(a1, ... ,a;)-::/= nil THEN
8. Let Inferences= Inferences+ 1
9. -IF Achieves(a1···an,S,R(a1, .. . ,a;)) THEN let Correct= Correct+ 1

,

The Estimate function requires up to lEI calls to Achieves and up to l x lEI calls to recognizer R, where lis the average length of action sequences in E. We further discuss complexity and running time in section 5.

The experiments described in section 6 indicate that good estimates can be produced from reasonably small samples of behavior. We believe that in many domains collecting sample data is relatively cheap and easy. In software domains, for example, the commands executed by a computer user can be tecorded. A key problem is task segmentation: how to know when a goal-solving episode starts and stops. It may be best that this prob­ lem is handled by the goal recognizer, since it will be difficult to perform task segmentation without also per­ forming some form of goal recognition. In this case, the goal recognizer would be fed a continuous stream of goal solving behavior and output a sequence of goals. How­ ever, in our experiments and the current formulation of the problem, we assume the person's recent behavior is already segmented prior to adaptation.

recognizer that always returns a goal that is achieved by the first action in A. Modifying Achieves to allow no irrelevant actions would be problematic in that we are interested in adapting goal recognizers to handle spurious, i.e. irrelevant actions. Our current solution is to restrict the goal recognizer to output only legitimate top-level goals, corresponding to End events in Kautz's plan hierarchies [Kautz, 1987].

2 We do not actually need the full power of the Modal Truth Criterion since A is a totally ordered set of actions.

5 An adaptive goal recognizer

We now present an algorithm that tunes a given recog­ nizer to perform well on a sample of a person's behavior.

Let T be the set of all possible adaptations. Adapt uses steepest ascent hill climbing to search the space of possible combinations of adaptations in set T. The starting point for the search is a recognizer without any adaptations. The neighbors of a recognizer are those rec­ ognizers with exactly one more, or one less, adaptation. In each iteration, we use Estimate to evaluate the accu­ racy and coverage of the current best recognizer and all its neighbors. We then reset the current search point to the recognizer with the best combination of accuracy and coverage, as determined by the input score function. We repeat the process until we encounter a recognizer with a higher score than all its neighbors, and then return this recognizer's adaptations. The pseudo code is:

Adapt(recognizer R, episodes E, score function s, adaptations T )

1. Let BEST= 0
2. REPEAT
3. (a) For all t; E (T- BEST), let score; = s( Estimate( R<BEST +til ,E))
4. (b) Let m be the integer for which scorem is the highest .
5. (c) IF scorem > s(Estimate(R(BEST),E)) THEN let BEST= BEST+ tm . ELSE RETVRN(BEST) .

The Adapt algorithm requires ITI x k calls to Esti­ mate where k is the number of iterations until a local maximum is found. Although Adapt is computationally intensive, our notion is that it would be allowed to run overnight, perhaps once a month, to adapt to changes in a person's behavior. Furthermore, Adapt can be in­ terrupted at any time; set BEST will always be a set of adaptations with a higher estimated value than any set of adaptations previously considered. We believe that a small number of adaptations will often significantly im­ prove recognition. Finally, the Adapt algorithm is highly amenable to parallelization. In any iteration, all the calls to Estimate can be processed in parallel, and the Esti­ mate function itself is easily parallelizable.

6 Experimental validation

In this section, we describe experiments that measure how much our adaptive techniques improve recognition.

We apply Adapt to data that contain different idiosyn­ cratic behaviors. For example, one person might spuri­ ously execute the Unix command date while another might spuriously execute the pwd command. Our hy­ pothesis is that adapting the recognizer to each individ­ ual behavior will outperform applying any recognizer to all behaviors. We measure:

· Impact: What percentage of someone's work can be done by offering to complete the goal that the recog­ nizer outputs?

· Error: How often does the recognizer produce an in­ correct goal?

In all of our experiments, we use separate data for train­ ing and testing Adapt.

6.1 Spurious actions

We ran the first set of experiments on action sequences generated by Toast [Agre and Horswill, 1992], a reactive agent that solves goals such as making omelets, cleaning dirty dishes, or setting the table. To generate "noisy" behavior, we randomly insert actions into Toast 's be­ havior, such as causing Toast to randomly add butter to a pan on the stove, or periodically wash its spatula.

The BOCE goal recognizer identifies Toast's goal by ruling out all but one of the goals Toast might have. BOCE rejects a goal if an observed action is not part of any plan to achieve the goal. For example, BOCE would reject the goal "make poached eggs" if Toast adds butter to a pan. Spurious actions can cause BOCE to reject Toast's actual goal which can, in turn, cause BOCE to either fail to infer any goal or infer the wrong goal.

Adding background goals can reduce the confusion caused by spurious actions. For example, adding a back­ ground goal "have butter in pans" will essentially cause BOCE to disregard any observations of Toast adding butter to pans. BOCE must, however, add background goals judiciously because ignoring relevant actions can delay or even prevent BOCE from identifying Toast 's goal. In the extreme, if all possible background goals are added then BOCE will never output a goal.

We vary two parameters: the frequency of spurious actions and the number of distinct spurious actions. For example, if 10% of Toast's actions are either a spuri­ ous washing of the spatula or a spurious adding of but­ ter, then the frequency is 0.1 and there are 2 distinct spurious actions. In each trial, we train BOCE on 100 episodes and test BOCE on another set of 100 episodes. The numbers reflect averages from 500 trials. We use a score function that weights accuracy 20 times as much as coverage.

In any given episode, BOCE outputs at most one goal. In our testing phase, we record the number of times BOCE makes no inference, correctly identifies Toast's goal, and incorrectly identifies Toast's goal. We also measure plan length, defined as the number of actions Toast executes per goal. Toast halts execution if BOCE correctly identifies, and presumably completes, its goal.

As shown in figure 2, the adapted recognizer performs significantly better than the unadapted recognizer when Toast has 3 distinct spurious actions. As the frequency of spurious actions increases, the unadapted recognizer's performance degrades rapidly. In contrast, the adapted recognizer never mistakenly attributes a goal to Toast.

As shown in figure 3, the performance of the adapted recognizer degrades as the number of distinct spurious actions increases. This happens because Adapt must add more and more background goals, which interfere with BOCE's ability to identify Toast's goals. Note that the adapted case is still far superior to the unadapted case in that it does not make any incorrect inferences.

The table in figure 4 shows that as the frequency of spurious actions increases, the impact of adapting the recognizer grows considerably.

The results shown in figures 2 and 4 show that Adapt improves recognition by a factor of two to three over unadapted recognition.

6.2 Goal distribution

In the second set of experiments, we simulate people whose goals are to find an object with a conjunction of properties, such as finding a computer with no users working on it that has over 32 MB RAM. We vary the probability with which goals include each predicate.

In our simulations, the person searches until she finds, or the recognizer suggests, an object that satisfies her goal. The recognizer can make one suggestion after each time the person polls an object. We measure plan length, the average number of objects polled by the person, and error, the average number of incorrect suggestions.

Adapt adjusts the recognizer by adding or removing predicates from PRt:V, the set of predicates with which BOCE forms goals. If PRt:V lacks a predicate a per­ son uses then BOCE can suggest a wrong object to the user. For example, the person might poll five comput­ ers with 32 MB RAM but if PRt:V does not contain the large .memory predicate, then BOCE would suggest a computer with small memory. On the other hand, if Pnt:V contains too many predicates then BOCE will be delayed in suggesting a useful object to the person.

Figure 5 compares 18 recognizers, each described by a point where the X-coordinate is the average plan length and theY-coordinate is the average error. A perfect rec­ ognizer would be positioned on the origin of the graph.

Points U1 to U15 represent unadapted recognizers: Ui is a recognizer where PR[V contains i random predi­ cates, out of 15 possible predicates. As the size of PRCV increases the number of errors decrease but the plan length increases. Note that no unadapted recognizer has both better error and plan length than any other.

T20, T60, and TlOO describe recognizers trained on 20, 60, and 100 training examples. In these experiments, a recognizer trained on 60 or 100 examples saves the person twice as much work as any unadapted recognizer with comparable error, and has much less error than any unadapted recognizer that is nearly as effective.

We ran these experiments on actions collected from Toast, as described in section 6.1. We varied the fre­ quency with which Toast would abandon its current goal after executing half its plan. Essentially, corrupting the input data in this fashion causes Adapt to add extrane­ ous background goals in an effort to avoid mistakes in the tainted training cases. As · shown in table 6, Adapt performs reasonably well with up to 15% noise levels. We used 400 training examples in these experiments be­ cause the results were poor with 100 examples. 3 Note that although the percentage of correct inference goes down, BOCE still never makes an incorrect inference but rather outputs no goal in more cases.

observations to the closest previously encountered situ­ ation. In contrast, we do not specifically analyze the past behavior of the observed person but instead eval­ uate how well a given recognizer, with various adapta­ tions, performs on this behavior. Note that our algorithm, Adapt, might be used to adjust the parameters of interface agents to perform better on a sample of past behavior.

[Elzer et al., 1994; Ardissono, 1996] integrate user u"un modeling and plan recognition to support dialogue un·o+-~~__:T..::Il.ll!!..--.....-~-----.....-~~----,..-.-u_."...__ derstanding. For example, if the user model indicates that John is terrified of flying, then the plan recognizer Figure 5: . Learning which goals different people pursue: Points T20, T60, and TlOO represent a recognizer trained on 20, 60, and 100 training examples respectively. Points U1 through U15 represent 15 different unadapted recognizers. 6.3 Adapting in the presence of noise We also measured the effect of one type of noise in the training data: we removed the second half of the exe­ cuted plan from some of the input episodes. can reject the plan of flying to Chicago when John says "I want to go to Chicago". In principle, this work could allow a plan recognizer to take advantage of the many techniques developed by the user modeling community for acquiring user preferences and beliefs. While our work has similar motivation, our approach is more di­ rect, or "low-level", in that we find a goal recognizer which works well on a person's recent behavior rather than infer a declarative model of that person's idiosyn­ crasies or beliefs. Again, our approach could be used in conjunction with this work by adapting a recognizer that uses user-specific information or even adapting the way in which the recognizer reasons about the user model.

7 Related work

There have been several other approaches to various as­ pects of the general problem of providing user-specific plan and goal recognition.

[Maes and Kozierok, 1993] apply machine learning techniques to detect recurrent patterns of behavior of computer users. Their interface agents learn from ob­ serving the user, as we do, but also learn from user feed­ back and direct training sessions. They focus on pre­ dicting the user's next action by matching the current Our work most closely resembles that described in [Bauer, 1994; 1996]. Bauer runs a plan recognizer on a set of input episodes from a typical user (just as we do), and then gathers statistical data based on the re­ sults of running the plan recognizer on the entire ob­ servable behavior in each episode. For example, Bauer's techniques can learn that a particular computer user will save email with 80% certainty, unless the email is from her manager, in which case she deletes it with 90% cer­ tainty. This analysis enables a plan recognizer to reach the same conclusions with fewer observed actions. Al­ though we both treat past planning episodes as training data, we learn very different information: Bauer learns statistical rules while we learn, for example, a good set of background goals. Bauer's approach is restricted to rec­ ognizers that use probabilistic information while our al­ gorithm is restricted to recognizers that produce a single goal, whether or not they use probabilistic information. Additionally, we do not assume our recognizer will work well without adaptation. As shown in figure 2, when the frequency of spurious actions is 0.29, the unadapted rec­ ognizer correctly identifies only about 20% of the actor's goals and is wrong on about 40% of the goals. Adapt im­ proves the recognizer so that it correctly identifies 80%

3 Gathering this many training examples may be infeasible in some domains.

of the goals and never makes a wrong prediction.

[Mooney, 1990] employs explanation-based learning to add new plans to the plan library when a person is ob­ served to execute a plan that is not in her known reper­ toire. They address the question of how to generalize the new plan so that structurally similar plans can be rec­ ognized in the future. One difference between this work and ours is that our adaptations can remove as well as add plans and goals from the plan library.

Finally, [Caruana and Freitag, 1994] examine several variations of hillclimbing to select which attributes a con­ cept learner should use. Attribute-selection is similar to predicate-selection, which we explore experimentally in section 6.2. They face different problems than we do in that they receive labeled training data while our al­ gorithm performs unsupervised learning. Furthermore, adding or removing goal predicates is just one of the adaptations that Adapt considers.

8 Future wor~ and conclusions

In future work, we will apply Adapt to more types of adaptations and to other goal recognizers. We are inter­ ested in adapting a recognizer to better reflect charac­ teristic mistakes that people make. For example, peo­ ple sometimes have flawed domain operators. We could adapt for this by introducing a new adaptation that adds or removes a precondition or effect from the domain op­ erators that BOCE forms plans from. We hypothesize that recognition will work best when BOCE builds plans based on what preconditions and effects the observed person believes actions have. Another line of future work is to examine search strategies other than hillclimbing.

The primary contribution of this work is the Adapt algorithm for adapting a goal recognizer to perform well on a sample of behavior. Adapt is an unsupervised­ learning algorithm in that the sample data is not an­ notated with the person's actual goals. Adapt is a recognizer-independent algorithm in that it can be ap­ plied to any goal recognizer for which there is an avail­ able set of adaptations. Our experiments in two domains show that applying Adapt to the BOCE recognizer can improve its performance by a factor of two to three.