Plan Recognition as Planning

1 Introduction

Plan recognition is an ubiquitous task in a number of areas, including natural language, multi-agent systems, and assisted cognition [Schmidt et al., 1978; Cohen et al., 1981; Pentney et al., 2006]. Plan recognition is planning in reverse: while in planning, we seek the actions to achieve a goal, in plan recognition, we seek the goals that explain the observed actions. Both are abductive tasks where some hypothesis needs to be adopted to account for given data: plans to account for goals, and goals to account for partially observed plans. Work in plan recognition, however, has proceeded independently of the work in planning, using mostly handcrafted libraries or algorithms that are not related to planning [Kautz and Allen, 1986; Vilain, 1990; Charniak and Goldman, 1993; Lesh and Etzioni, 1995; Goldman et al., 1999; Avrahami-Zilberbrand and Kaminka, 2005].

In this work we aim to narrow the gap between plan recognition and planning by exploiting the power and generality of recent classical planning algorithms. For this, we move away from the plan recognition problem over a plan library

Hector Geffner

ICREA & Universitat Pompeu Fabra 08003 Barcelona, SPAIN

hector.geffner@upf.edu

and consider the plan recognition problem over a domain theory and a possible set G of goals. The plan recognition task is then formulated as the problem of identifying the goals G ∈ G such that some optimal plan for G is compatible with the observations. Such goals are grouped into the set G ∗ . The reason for focusing on the optimal plans for G is that they represent the possible behaviors of a perfectly rational agent pursuing the goal G. By a suitable transformation, we show that a goal G is in G∗ if there is an action sequence that achieves optimally both the goal G and the goal G extended with extra goals Go representing the observations. Exploiting this result, we show how the set of goals G∗ can be computed exactly and approximately by minor modifications of existing optimal and suboptimal planning algorithms, and existing polynomial heuristics, that are then tested experimentally over several domains. The suboptimal algorithms and the heuristics appear to provide good approximations of the optimal goal set G∗ , while scaling up as well as state-of-theart planning algorithms and heuristics.

The paper is organized as follows. We provide first the basic planning terminology, define the plan recognition problem over a domain theory, and introduce the transformation that allows us to compile away the observations. We then focus on exact and approximate computational methods, present the result of the experiments, and discuss limitations and generalizations of the proposed framework.

2 Planning Background

A Strips planning problem is a tuple P = 〈F, I, A, G〉 where F is the set of fluents, I ⊆ F and G ⊆ F are the initial and goal situations, and A is a set of actions a with precondition, add, and delete lists Pre(a), Add(a), and Del(a) respectively, all of which are subsets of F .

For each action a ∈ A, we assume that there is a nonnegative cost c(a) so that the cost of a sequential plan π = a1, . . . , an is c(π) = ∑ c(ai). A plan π is optimal if it has minimum cost. For unit costs, i.e., c(a) = 1 for all a ∈ A, plan cost is plan length, and the optimal plans are the shortest ones. Unless stated otherwise, action costs are assumed to be 1.

In the plan recognition setting over a domain theory, action costs c(a) carry implicit information about the probability that the agent will use action a to solve a problem P, as the agent should rationally avoid plans with higher cost than needed. The most likely plans, assuming full rationality, are the optimal plans, and hence, we will focus initially on them.

Algorithms for computing optimal plans cast the planning problem as a problem of heuristic search with admissible heuristics derived automatically from the problem encoding [Haslum and Geffner, 2000] . An heuristic h(s) is admissible if h(s) ≤ h∗ (s) for all the states, where h∗ (s) is the optimal cost from s. Optimal planners use such heuristics in the context of admissible search algorithms like A* and IDA*. Computing optimal plans, however, is much harder than computing plans that are good but not necessarily optimal, and indeed suboptimal planners such as FF and FD, that use more focused search algorithms and more informative heuristics, scale up much better [Hoffmann and Nebel, 2001; Helmert, 2006]. We will thus use optimal plans for providing a crisp definition of the plan recognition task, and develop efficient methods that borrow from suboptimal planning methods and heuristics for producing good approximations that scale up.

3 Plan Recognition over a Domain Theory

The plan recognition problem given a plan library for a set G of possible goals G can be understood, at an abstract level, as the problem of finding a goal G with a plan π in the library, written π ∈ ΠL(G), such that π satisfies the observations. We define the plan recognition problem over a domain theory in a similar way just changing the set ΠL(G) of plans for G in the library by the set Π∗P (G) of optimal plans for G given the domain P . We will use P = 〈F, I, O〉 to represent planning domains so that a planning problem P [G] is obtained by concatenating a planning domain with a goal G, which is any set of fluents. We can then define a plan recognition problem or theory as follows:

Definition 1. A plan recognition problem or theory is a triplet T = 〈P, G,O〉 where P = 〈F, I,A〉 is a planning domain, G is the set of possible goals G, G ⊆ F, and O = o1, . . . , om is an observation sequence with each oi being an action in A.

We also need to make precise what it means for an action sequence to satisfy an observation sequence made up of actions. E.g., the action sequence π = {a, b, c, d, e, a} satisfies the observation sequences O1 = {b, d, a} and O2 = {a, c, a}, but not O3 = {b, d, c}. This can be formalized with the help of a function that maps observation indices in O into action indices in A:

Definition 2. An action sequence π = a1, . . . , an satisfies the observation sequence O = o1, . . . , om if there is a monotonic function f mapping the observation indices j = 1, . . . ,m into action indices i = 1, . . . , n, such that af(j) = oj .

For example, the unique function f that establishes a correspondence between the actions oi observed in O1 and the actions aj in π is f(1) = 2, f(2) = 4, and f(3) = 6. This function must be strictly monotonic so that the action sequences π preserve the ordering of the actions observed.

The solution to a plan recognition theory T = 〈P, G, O〉 is given then by the goals G that admit an optimal plan that is compatible with the observations:

Definition 3. The exact solution to a theory T = 〈P, G, O〉 is given by the optimal goal set G∗T which comprises the goals G ∈ G such that for some π ∈ Π∗P (G), π satisfies O.

Figure 1 shows a simple plan recognition problem. Room A (marked with a circle) is the initial position of the agent, while Rooms C, I and K (marked with a square) are its possible destinations. Arrows between Rooms A and B, and F and G, are the observed agent movements in that order. In the resulting theory T, the only possible goals that have optimal plans compatible with the observation sequence are I and K. In the terminology above, the set of possible goals G is given by the atoms at(C), at(I), and at(K), while the optimal goal set G ∗T comprises at(I) and at(K), leaving out the possible goal at(C).

Before proceeding with the methods for computing the optimal goal set G∗T exactly or approximately, let us first comment on some of the limitations and strengths of this model of plan recognition. The model can be easily extended to handle observations on fluents and not only on actions. For this, the observation of a fluent p can be encoded as the observation of a 'dummy' action NOOP(p) with precondition and effect p. Similarly, it is not difficult to account for actions that must be among the observations when they have been executed. For this, it suffices to remove such actions from the domain theory when they haven't been observed. Notice that the same tricks do not work in library-based approaches that are less flexible. Likewise, the assumption that the observations are ordered in a linear sequence is not critical, and can be replaced with no much trouble by a partial order. Library-based recognition can also be accommodated by a suitable compilation of (acyclic) libraries into Strips [Lekav´y and N´avrat, 2007]. A critical aspects of the model is that it does not weight the hypotheses G in G but it just filters them. We will talk more about this in Section 8.

4 Compiling the Observations Away

In order to solve the plan recognition problem using planning algorithms, we need to get rid of the observations. This is actually not difficult to do. For simplicity, we will assume that no pair of observations oi and oj refer to the same action a in P. When this is not so, we can create a copy a′ of the action a in P so that oi refers to a′ and oj refers to a.

We will compile the observations away by mapping the theory T = 〈P, G,O〉 into an slightly different theory T ′ = 〈P ′ , G′ ,O′ 〉 with an empty set O′ of observations, such that the solution set G∗T for T can be read off from the solution set G∗T ′ for T ′ .

Definition 4. For a theory T = 〈P, G,O〉, the transformed theory is T ′ = 〈P ′ , G′ , O′ 〉 such that

• P ′ = 〈F ′ , I ′ ,A′ 〉 has fluents F ′ = F ∪ Fo, initial situation I ′ = I, and actions A′ = A ∪ Ao, where P = 〈F, I, A〉, F0 = {pa | a ∈ O}, and Ao = {oa | a ∈ O},
• G′ contains the goal G′ = G∪Go for each goal G in G, where Go = Fo,
• O′ is empty

The new actions oa in P ′ have the same precondition, add, and delete lists as the action a in P except for the new fluent pa that is added to Add(oa), and the fluent pb, for the action b that immediately precedes a in O, if any, that is added to P re(oa).

In the transformed theory T ′ , the observations a ∈ O are encoded as extra fluents pa ∈ Fo, extra actions oa ∈ Ao, and extra goals pa ∈ Go. Moreover, these extra goals pa can only be achieved by the new actions oa, that due to the precondition pb for the action b that precedes a in O, can be applied only after all the actions preceding a in O, have been executed. The result is that the plans that achieve the goal G′ = G∪Go in P ′ are in correspondence with the plans that achieve the goal G in P that satisfy the observations O:

Proposition 5. π = a1, . . . , an is a plan for G in P that satisfies the observations O = o1, . . . , om under the function f iff π′ = b1, . . . , bn is a plan for G′ in P ′ with bi = oai , if i = f(j) for some j ∈ [1,m], and bi = ai otherwise.

It follows from this that π is an optimal plan for G in P that satisfies the observations iff π′ is an optimal plan in P ′ for two different goals: G, on the one hand, and G′ = G∪Go on the other. If we let Π∗P (G) stand for the set of optimal plans for G in P , we can thus test whether a goal G in G accounts for the observation as follows: 1

Theorem 6. G ∈ G∗T iff there is an action sequence π in Π∗P ′ (G) ∩ Π∗P ′ (G′ ).

Moreover, since G ⊆ G′ , if we let c∗P ′(G) stand for the optimal cost of achieving G in P ′ , we can state this result in a simpler form:

As an example of the transformation, for the plan recognition task shown in Figure 1, the extra fluents Fo in T ′ are pmove(A,B) and pmove(F,G), while the extra actions Ao are omove(A,B) and omove(F,G); the first with the same precondition as move(A,B) but with the extra fluent pmove(A,B) in the Add list, and the second with the extra precondition pmove(A,B) and the extra effect pmove(F,G). Theorem 7 then means that a goal G accounts for the observations in the original theory T , and thus belongs to G∗T , iff the cost of achieving the goal G in the transformed domain P ′ is equal to the cost of achieving the goal G′ = G∪Go. In the transformed problem, thus, observations have been replaced by extra goals that must be achieved at no extra cost.

1 Note that while a plan for G′ = G∪Go is always a plan for G, it is not true that an optimal plan for G′ is an optimal plan for G, or even that a good plan for G′ is a good plan for G.

5 Computation

We present next a method for computing the optimal goal set G∗T exactly, and two methods that approximate this set but scale up better. The first method is based on domainindependent optimal planning techniques, while the latter two are based on suboptimal planning algorithms and heuristic estimators respectively.

5.1 Exact Methods

Optimal planning algorithms are designed for computing an action sequence in Π∗P (G), if one exists, for any planning domain P and goal G. The cost of such a plan is the optimal cost c∗P (G). This computation is done by running an admissible search algorithm like A* or IDA* along with an admissible heuristic h that is extracted automatically from the problem [Haslum and Geffner, 2000].

Theorem 7 can be used to check whether a goal G is in G ∈ G∗T using an optimal planner for computing the optimal cost c∗P ′(G) of achieving G in P ′ , and then using this cost as an upper bound in the search for an optimal plan for the goal G′ = G ∪ Go in P ′ . This computation is not exactly the solution to two planning problems as the search in the second problem is heavily pruned by the use of cost c∗P ′(G) as a bound. The bound can be used profitably in either A* or IDA* searches, in both cases, pruning right away nodes n with cost f(n) = g(n) + h(n) greater than cP ′(G)∗ . In the experiments below, we use the latest implementation of the optimal HSP* planner due to Haslum, that uses the A* algorithm modified to accommodate this pruning.

Three other optimizations have been made in the code for HSP*. First, the cost c∗P ′(G) of achieving the goal G in P ′ is equivalent to the cost c∗P (G) of achieving the same goal in the original problem P that has no extra fluents or actions, and thus, can be solved more efficiently. This is because every occurrence of an actions oa in P ′ that is not in P can be replaced by the corresponding action a in P. Second, since the difference between the action oa in P ′ and the action a in P is that oa adds the fluent pa that is never deleted, it is not necessary to consider plans for G′ in P ′ where such actions are done more than once. And last, since there cannot be plans for G′ in P ′ with cost lower than c∗P ′(G), in the second part of the computation we are just testing whether there is one such plan for G′ with cost equal to c∗P ′(G). For this, it is wasteful to use A*; it is more efficient to run a single IDA* iteration with memory and setting the initial bound to c∗P ′ (G), avoiding the use of a heap.

5.2 Approximate Methods

Suboptimal planners such as FF and FD scale up to much larger problems than optimal planners as they can use more informed heuristics that are not necessarily admissible and more focused search algorithms. We want to use such suboptimal planners for computing approximations of the optimal goal set G∗T . This approximation can be understood as replacing the test that checks the existence of an action sequence π in Π∗P ′(G) ∩ Π∗P ′(G′ ), by the weaker test that checks for the presence of an action sequence π in ΠsP ′ (G) ∩ ΠsP ′ (G′ ), where ΠsP (G) denotes a set of 'good plans' for G not necessarily optimal. For example, while planners such as FF produce a single plan for a goal G in a domain P , we can think of ΠsP (G) as the set of plans that FF is capable of producing if ties were broken in all possible ways. Yet, we do not need to make this intuition precise because we will not compute such sets of plans explicitly: rather we will modify FF so that it will 'break ties' for producing a single plan πG for G in P ′ that achieves as many goals from G′ (observations) as (greedily) possible.

The FF planner in Enforced Hill Climbing (EHC) mode iteratively moves from one state s to another state s′ with lower heuristic value hFF that is found by a local breadth first search from s that considers a small fragment of the actions applicable in a state, called the helpful actions [Hoffmann and Nebel, 2001]. Both the helpful actions in s and the heuristic value hFF(s) are derived from the relaxed plan π(s) that is obtained efficiently from every state s explored.

In this process, there are two decision points where the extra goals pa ∈ G′ \G, encoding the observations in O, can be used to bias the search towards plans that achieves as many atoms pa fromG′ as possible. First, rather than moving from s to the first state s′ that improves the heuristic value hFF(s) of s, we exhaust the local breadth first search space bounded by g(s′ ), and commit to the state s′′ in this local space that improves the heuristic value of s and maximizes the measure |π(s′′ )∩Ao|. Second, rather than computing the relaxed plans π(s) as in FF, we follow the formulation of the set-additive heuristic in [Keyder and Geffner, 2008], where the relaxed plans π(p; s) for all fluents p from the state s are computed recursively. For biasing the construction of the relaxed plan π(s) in s for accounting for as many dummy goals pa in G′ as possible, we just choose as the 'best supporter' ap of a fluent p, the action a that adds p and minimizes c(π(a; s)), while maximizing, in addition, the measure |π(a; s) ∩ Ao|, where π(a; s) = {a} ∪ ∪q∈P re(a)π(q; s).

With this modified version of the FF planner, we define the approximation GsT of the optimal goal set G∗T , as the set of goals G in G for which the measure |πP ′(G) ∩ Ao| is highest, where πP ′(G) is the plan produced by the modified FF planner for achieving the goal G in P ′ .

We will actually test below a second approximation Gh T of the optimal goal set G∗T that is polynomial and requires no search at all. We will call Gh T , the heuristic goal set, and GsT , the suboptimal goal set. The heuristic goal set Gh T is defined as the set of goals G ∈ G for which |π(G; s0)∩Ao| is highest, where π(G; s0) is the relaxed plan obtained for the goal G in P ′ from the initial state s0 = I of P ′ . In other words, while the computation of G∗T involves an optimal planner, and the computation of the approximation GsT involves a suboptimal planner, the computation of the approximation Gh T involves the computation of one relaxed plan and neither search nor planning. Below, we compare the accuracy and scalability of these different methods where we will see that the computation of the the sets GsT and Gh T yields good approximations of the optimal goal set G∗T and scale up much better.

For improving the quality of the approximations further, the implementation below accommodates two additional changes. The purpose of these changes is to allow 'gaps' in the explanation of the observations. In the description used up to now, if the observation sequence is O = o1, . . . , om, no plan or relaxed plan is able to account for the observation oi if it doesn't account for all the observations ok preceding oi in the sequence. This restriction is used in the definition of the optimal goal set G∗T and is needed in the methods that compute this set exactly. On the other hand, it imposes unnecessary limits on the approximation methods that are not required to account for all the observations. Clearly, a goal G1 that explains all the observations oi except for the first one o1 should be selected over a possible goal G2 that explains none, yet unless we allow suboptimal and relaxed plans to 'skip' observations, this is not possible. Thus, in the implementation, we allow 'relaxed plans' to skip observations by computing the set-additive heuristic and the relaxed plans using a further relaxation where the preconditions pa that express the precedence constraints among the actions oa that account for the observations, are dropped. Instead, during the computation of the heuristic, we set the heuristic value of an action oa to infinity if its support includes an action ob such that the observation a precedes the observation b in O. The precedence constraints, however, are preserved in the execution model used in FF for performing the state progressions. In such a phase though, when the planner selects to execute the action a instead of the action oa that accounts for the observation a in O, the planner compares a with a new action forgo(a) that is not considered anywhere else by the planner. Basically, while the action oa is like a but with a precondition pb if b comes right before a in O and postcondition pa, the action forgo(a) is like oa but without the precondition pb. The action forgo(a) thus says to leave the observation a ∈ O unaccounted for (as oa will not make it then into the plan), but by adding pa to the current state, it opens the possibility of accounting for actions d that follow a in the observation sequence. The planner chooses then between a and forgo(a) as between any two actions: by comparing the heuristic value of the resulting states s′ and by breaking ties in favor of the action that maximizes |π(s′ ) ∩ Ao|.

6 Example

As an illustration, we consider an example drawn from the familiar Blocks World, with six blocks: T, S, E, R, Y and A, such that the initial situation is

The possible goals in G are towers that express words: 'year' (G1), 'yeast' (G2), and 'tray' (G3). The following observation sequence is then obtained

that results in the following extra (fluents and) goals in the transformed theory T ′ :

The exact method described in Section 5.1 proceeds by establishing that c∗ (G1) = 14 and c∗ (G1 ∪ Go) > 14, so that G1 is ruled out as a possible goal. Then it determines that c∗ (G2) = 14 and c∗ (G2 ∪ Go) > 14, so that G2 is ruled out as well. Finally, it computes c∗ (G3) = c∗ (G3 ∪Go} = 14, and concludes that G∗T = {G3}, and hence that G3 is the only goal the agent may be trying to achieve. The first approximate method described in Section 5.2 computes plans π(G1), π(G2), π(G3) for each of the goals with the modified FF planner, and finds that |Ao ∩ π(G1)| = |Ao ∩ π(G2)| = 2 while |Ao ∩ π(G3)| = 3, so that the suboptimal and optimal goal sets coincide; namely, GsT = {G3}. On the other hand, in this example, the heuristic goal set Gh T is weaker, not excluding any of the possible goals in G. In the domains below, however, we will see that the heuristic approach can do very well too.

7 Empirical Evaluation

We have tested the optimal and approximate algorithms proposed on several PR theories defined from Planning domains used as benchmarks in the official planning competitions. 2 In the GRID-NAVIGATION domain the tasks can be summarized with the question "where is the agent going?" with the hypothetical goals being a subset of the nodes in the navigation graph. The graphs were built by randomly connecting chainlike graphs of fixed-length, connecting nodes so that every node was reachable from any other node. In IPC-GRID+ the query is the same, and to the challenges posed by GRIDNAVIGATION, we added the fact that, fixed the set of possible destinations, we tossed the keys necessary to reach those destinations at a restricted set of places. This has the effect that (potentially) many observations are relevant to many different hypotheses. 3 For LOGISTICS the question is "where are the packages being transported to?". Here the number of valid plans to consider is not as large, but these plans have many actions in common. In BLOCK-WORDS the question is "which is the 'word' the agent is trying to build?". Here we built three dictionaries with 20 English words, not featuring a letter twice, and further constrained to use only 8 different letters. Here we have both a potential combinatorial explosion of possibilities as well as the problem of ambiguity: if many words use the letter 'E', their plans will share a considerable number of actions involving the block 'E'.

Table 1 summarizes the experimental results of the three computational methods over hundreds - exact numbers reported under domain name - of plan recognition problems T = 〈P, G, O〉 drawn from these four domains, where P is a planning problem without goals, G is a set of possible goals, and O is an observation sequence. The problems were generated by considering for each domain, the combination of several 'incomplete' planning problems P, several goal sets G, and many observation sequences O. For a given P and a given (hidden) goal G in G, we generated several observation sequences O by randomly taking a certain percentage of the actions in an optimal plan for P[G]. A ratio of 10% means that the observations contain 10% of the actions in the optimal plan, while a ratio of 100% means that the observation sequence is the whole plan. In the tables, five ratios are considered, and for each P and G, 13 different samples of observations O were generated: one for 100%, three for each of the other ratios. For each of the four domains, each row expresses averages taken for each observation ratio while varying P and G.

2 The pages for the different competitions can be obtained from http://ipc.informatik.uni-freiburg.de

3 This domain is a modification of the one in IPC-1 where the agent is not limited to carry a single key at any time.

Table 1 shows these averages: the number of goals in G, the ratio and number of observations used, the length of the optimal plans, the total time to compute the optimal goal set G∗T and its resulting size. It then includes the length of the suboptimal plans found, the total time to construct the suboptimal goal set GsT , and its resulting size too. Last is the information about the second approximation Gh T : the total time to compute it and its average size. The columns headed by the letters FPR, AR, and FNR provide further information about the quality of the suboptimal and heuristic approximations GsT and Gh T . False Positives indicate cases where the approximate methods fail to exclude a possible goal, and False Negatives, when they fail to include a possible goal. More precisely, in the columns of the table the False Positive Ratio (FPR) is |GsT \ G∗T |/|GsT ∪ G∗T |, the False Negative Ratio (FNR) is |G∗T \ GsT |/|GsT ∪ G∗T |, and the Agreement Ratio (AR), shown in bold, is |GsT ∩ G∗T |/|GsT ∪ G∗T |. The ratios for the heuristic method are the same with Gh T in place of GsT .

From the table, we can see that the approximate methods are orders of magnitude faster than the optimal method, and that they manage to filter the goal hypotheses in a way that often coincides with the optimal account. Indeed, both the suboptimal and the heuristic method, that is polynomial and does no search at all, do very well in 3 of the domains, and slightly worse in the more challenging 'Blocks-word' domain, where they fail to rule out some of the hypotheses. The optimal algorithms make no error at all, as they are used to define and compute the optimal goal set exactly. They are displayed here nonetheless to provide a reference to the other algorithms and to illustrate the type of problems that they can effectively solve. For larger problems, approximate methods are the way to go, and we believe that further progress in heuristics and search algorithms with these plan recognition problems in mind, can potentially deliver more powerful and more accurate recognition algorithms.

8 Discussion

We have provided a crisp definition of the plan recognition task given a domain theory and have developed good approximation methods that use domain-independent planning techniques and are able to scale up. The proposed model is more flexible than library-based approaches and admits certain straightforward extensions such as dealing with the observation of fluents, handling actions that must be observed when executed, and partial orders on the observations. A critical aspect of the model, however, is that it does not weight the possible hypotheses (goals) but it just filters them. A natural extension of the model involves attaching a weight Δ(G) to each possible goal given by the difference between the cost c∗P ′ (G′ ) of solving the goals G′ = G∪G0 of the transformed domain P ′ , and the cost c∗P ′ (G) of solving the goal G alone.

Indeed, such weight Δ(G) provides a measure of how far the agent has to move away from the best plans for achieving G in order to account for the observations: the greater the distance, the less probable the hypothesis G given the observations. Indeed, such weights can be used to define a probability distribution over the goals given the observation, something that has not been easy to do over the space of all plans. In this work, we have considered the special case where the hypotheses G selected are the most likely with Δ(G) = 0.

Acknowledgments

H. Geffner thanks the members of the NLP-Planning Seminar at the University of Edinburgh for interesting discussions about NLP, Planning, and Plan Recognition. We thank P. Haslum for making available HSP optimal planner code and documentation. This work is partially supported by grant TIN2006-15387-C03-03 fromMEC/Spain.