From Interaction Data to Plan Libraries: A Clustering Approach

1 Introduction

Plan libraries are the most important knowledge source of many plan recognition systems. They not only contain all possible types of plans (or goals) to be recognized by such a system-thus delimiting the search space of pos­ sible plan hypotheses-, but also represent the details of how these plans have to be executed to actually achieve their associated goals. These "recipes" -the so-called plan decompositions-are necessary to map observed ac­ tions onto the plan hypotheses available which is one of the central steps within the plan recognition process.

Although they are being widely used, the question of how to actually construct plan libraries that support the recognition process in an optimal way has only recently been investigated more thoroughly (e.g. [Lesh and Et­ zioni, 1996]). In [Bauer, 1998] a method was introduced that allows abstract plan decompositions to be gener­ ated from action sequences logged while observing test subjects interacting with an application system. What makes this approach attractive is the fact that it does not rely on the existence of formalized domain knowl­ edge, although it can use possibly available information to improve its results.

·Supported by the German Ministry of Education, Sci­ ence, Research, and Technology under grant ITW 9703.

This join procedure can be considered an instance of a supervised learning algorithm, that is, it requires its training instances to be labeled with their respec­ tive class memberships (the domain goals associated to the various action sequences in this case). Often, how­ ever, only unlabeled interaction data are available that are very tedious to classify by hand as they contain a huge number of irrelevant details like spurious actions. This paper extends the approach from [Bauer, 1998] for the acquisition of plan libraries by a clustering algorithm that determines sets of similar action sequences in un­ labeled training data that can be forwarded to the join algorithm to compute plans to be used in the library. Analyzing these library entries and labeling them with the domain goals they seem to achieve-such that they can actually be used for plan recognition purposes- is then relatively easy as the small number of plans gener­ ated represents the essential aspects of the original ac­ tion sequences only. FUrthermore the resulting libraries can be expected to support the plan recognition process particularly well as they contain abstractions of actual users' behaviors rather than idealized plans designed by a knowledge engineer.

The rest of this paper is organized as follows . Sec­ tion 2 reviews the basic notions introduced in [Bauer , 1998]. Sections 3 and 4 introduce the new clustering al­ gorithm and present empirical findings, respectively. Fi­ nally, Section 5 discusses related work before Section 6 summarizes the results.

2 Joining Action Sequences

A plan decomposition- or simply, a plan-is a tuple (P, Ap, Cp) where Pis a unique identifier, Ap is a set of actions- either concrete or abstract-, and Cp is a set of constraints representing additional details about the internal structure like temporal ordering of the elements of Ap. To optimally support plan recognition, a plan decomposition should not be too restrictive by contain­ ing irrelevant constraints that unnecessarily restrict the number of recognizable user interactions. On the other hand, being too "fuzzy" by leaving out too many de­ tails implies the danger of not being able to discriminate between competing hypotheses. A good compromise is to concentrate on those aspects of a plan-i.e. actions and constraints describing its internal structure-that are absolutely necessary to achieve the associated do­ main goal. Obviously a component of a plan is necessary just in case it occurs in all action sequences that form a valid instance of this plan. As it is hardly ever possi­ ble to enumerate all possible ways to actually carry out a plan, this notion of necessity has to be approximated by collecting a limited number of action sequences and determining what they have in common. These training data are obtained by fixing a set of domain goals to be covered by the plan library and observing a number of test subjects trying to achieve these goals. The action sequences executed are recorded, grouped according to common domain goals, and forwarded to the "join" algo­ rithm as described in [Bauer, 1998]. That is, in contrast to the situation considered in Section 3, there exists a unique labeling of the input data with their associated domain goals.

Let AS\, ... , AS'n be the set of action sequences belong­ ing to some goal g. Each of these sequences consists of a set of temporally ordered actions a1 , ... , a1. where a; = a; (Oil ' 0 0 0' O;n.) 0 Here a; is the action typ/ this in­ stance belongs to (like ls or cp in a UNIX context), and the various O;j are constants representing the domain objects being manipulated (the action parameters).

Besides these action sequences the join procedure can make use of various types of domain knowledge with­ out depending on their actual availability. As will be­ come clear, a logical theory D containing general domain knowledge can be used to infer structural relationships among the elements of an action sequence. Furthermore, an action type hierarchy D a and an object type hierar­ chy Dt representing abstraction relations among action and object types, respectively, will play a central role in the abstraction step of the join procedure. Given a set X of concepts from either Da or Dt, the operation msa computes the most specific non-trivial abstraction of all members of X within the corresponding abstraction hi­ erarchy. Note that the result is undefined if the root concept is the only one subsuming all of X (in this case the elements of X can be considered to have nothing in common). For a precise definition of msa the reader is referred to [Bauer, 1998].

In a first step, these action sequences are transformed into labeled graphs G A5; making the interrelationships among the constituents of AS'; explicit. While the action instances contained in AS'; form the nodes, there are two types of edges. An edge a; ~ ai represents the tem­ poral order between both actions (in this case a; occurs before aj), while an edge

represents the fact that relation p holds between the ac­ tion arguments o;k and Oji· The resulting action graph then has the form GA5, = (AS';,T; US;) with a set of temporal edges T; = {a; ~ ai I i < j} and a set of structural edges S; = {a; (~) aj I D F p( Oik' 0 ·I)} 0 If D = 0, i.e. if virtually nothing is known about fhe domain, only the equality of two objects can be recognized and made explicit within G A5;.

Given two action sequences in the form of action graphs G1 = (A1, T1 U 81) and G2 = (A2, T2 u S2), their common abstraction or "join" G1 Q9 G2 is computed as follows. Let a;= a;(o;1, ... ,o;n) E A;,i = 1,2. Then al ®a2 = a(ol, ... ,on) where a= msa({al,a2}) and for all 1 ~ i ~ n: 01; = 02; = o; is a constant or o; is a variable of type msa( { type(o1;), type(o2;)} ).

That is, the abstract representation of the common information contained in two action instances al and a2 is a new action instance the type of which is the msa of both action types-if defined-and the arguments of which are either a concrete domain object represented by a constant o; (if both actions had the same object as a parameter in the same place) or a newly introduced variable the type of which is determined from the types of the originally occurring domain action arguments. If Da = 0, ii1 and ii2 can only be joined if a1 = a2.

A temporal or structural edge_is considered to be com­ mon to both G1 and G2 iff the corresponding action nodes to which the edge is incident could be joined us­ ing the above criterion. That is,

if iiu Q9 a21 = al and al2 Q9 a22 = a2 and undefined otherwise. The join of two structural edges with identical labels is defined analogously.

Summarizing, the join of two action sequences repre­ sented as action graphs G1 and G2 is G1 ®G 2 = (A, TUS)

where A

In many cases the above result G1 ®G 2 does not yet rep­ resent a plan decomposition with the desired properties as some actions may be used several times to create a new action node. A maximum subgraph of G1 Q9 G2 in which each action of G1 and G2 is joined at most once with another action is called a valid join. The set of all valid joins can be ordered using the measure

called the degree of restrictiveness. P A ~ A is the set of primitive actions contained in A, i.e. those tha~ do ~ot abstract another domain action in the abstract10n hter­ archy Da . If Da = 0, PA and A are obviously identical. The non-negative numerical weights wa, Wp, Wt, and Ws assess the relative influence of the various components of a plan decomposition. As the most restrictive valid joi.n, i.e. the one containing the maximum amount of detatls regarding plan execution (and t.hus maximi~ing ~egr) is the one to be used in the expenments descnbed m Sec­ tion 4 it will be identified with Gt ® G2 throughout the rest of this paper. Obviously, the resulting action graph can be easily retransformed into a plan decomposition tuple of the form (P, Ap, Cp).

Example: Consider the action graphs Gt and G2 from the cooking domain as depicted in Figure 1. For sake of simplicity, only structural and direct temporal edges connecting subsequent actions are shown. That is, temporal edges like the one between a1 and a3 are left out. Action arguments like "spag_1" refer to particular domain objects. Da contains informa­ tion about the abstract actions make_pasta (subsum­ ing make..:;paghetti and make_fettucini) and make...sauce (subsuming make_pesto and makeJnarinara) . The ac­ t ion graphs Gn and Gt2 as depicted in Figure 2 repre­ sent the two valid joins contained in Gt ® G2. Both are partially ordered plans (i.e. the temporal order among the actions is only partially defined) made up of one con­ crete and two abstract actions each. They mainly differ in the inclusion of either a1 ® b2 or a1 ® b4 (including both of them simultaneously would violate the above­ mentioned "valid join" condition). The number of tem­ poral and structural edges is an immediate consequence of this choice (cf. the rule on how to join edges). Using the numerical weights Wa = Wp = Wt = 1 and Ws = 2- a combination that proved to yield reasonable results in experiments- , the degree of restrictiveness of Gu be­ comes 6 while the value for Gt2 is 9. As a consequence the latter would be the representative for Gt ® G2.

3 The Clustering Algorithm

The approach to the acquisition of abstract plan descrip­ tions presented in the previous section relies on the train­ ing data being labeled with their respective classes, i.e. their associated domain goals. Often, however, all we can get is an unlabeled collection of interaction data. In such a situation it is necessary to first identify groups of "similar" action sequences that can be forwarded to the join algorithm. The members of such a group are ex­ pected to also achieve similar domain goals. The result­ ing abstract plans- that are reduced to their essential components-can then be classified by a .d?main e~pert , thus providing the basis for plan recogmtwn. Thts sec­ tion introduces a clustering method based on a frequent set analysis of the action types occurring.in the training data.

Assume a set of action sequences S = {AS\, ... , AS'n} are given. The crucial idea is to identify sets of act~on types that co-occur frequently and join only those act10n sequences containing all of them. The approach taken here is similar to the cluster mining algorithm introduced in [Perkowitz and Etzioni, 1998] that is us.e~ to ~etect groups of Web sites that are frequently vtstted m the same session. The algorithm works as follows .

1. Let A= {at, ... , am} be the set of all act~on types o~­ curring in S. Construct a complete graph (1.e. each patr of nodes is connected by an edge) with nodes at , ... , am and label each edge connecting two nodes ai and aj with the numerical value min(P(a;jaj), P(ajlai)) which rep­ resents the minimum co-occurrence probability of ai and aj in the sequences current!~ in ~ . . . .

2. Determine all maximum stze cltques wtthm thts graph containing only edges the label of which is ~ cf .t The effect of the parameter cf E ]0, 1], the "clustering fac­ tor" , will be discussed below.

3. For each clique C-which represents a set of action types all of which co-occur frequently in the training data-determine the set S(C) of action sequences con­ taining each of its members.

4. Compute the join of each maximum size cluster S(C)-it will be used as one library entry- , remove the members of S(C) from S, and repeat this procedure starting from step 1 until S = 0.

The higher the value of cf, the smaller the size of the cliques of action types co-occurring with probability ~ cf becomes. Consequently the size of clusters of action se­ quences containing these cliques grows (the smaller a set of action types, the higher the probability to find an action sequence containing it), and the number of clusters- and thus, plans in the library- decreases. Si­ multaneously, the plans become less complex, i.e. the degr values go down as each plan represents the aspects common to a larger set of action sequences. A small value for cf has the opposite effect of producing many clusters each of which consists of few action sequences only and yields a plan with high degr value.

Example: Assume the training set contains the fol­ lowing action sequences (for sake of simplicity, only the action types contained are listed and both ac­ tion parameters and constraints are omitted) : AS't = {at, a2, a3}, AS'2 = {at, a3}, AS'3 = {at, a4}. With the value cf = 1.0 the trivial clique {at} is identified that leads to the cluster {.AS\, .AS'2, .AS'3}. For cf = 0.6, the algorithm successively detects the cliques { a1, a4} and { a1 , a3} with associated clusters { .AS'3} and { .AS'1, .AS'2}. The results of joining the members of these clusters are AS1 l3l .AS'2 l3l .AS'3 = {at}, (for cf = 1.0) and

1 A clique is a complete subgraph of a graph, i.e. every two nodes must be connected by an edge in a clique. While this problem is known to be NP-complete, the removal of all edges with label < cf usually reduces the graph to a tractable size.

.AS'1 13l .AS'2 = {a1 , a3}, AS3 = {a1,a4} (for cf = 0.6). These results correspond to what could be expected after the above discussion.

4 Experiments

A total of 53 action sequences from the UNIX domain containing up to 24 steps and belonging to 6 different domain goals formed the basis of the experiments re­ ported about in this section. Typical goals were the search for files with certain properties or status checks for printers. For unbiased results, no additional domain knowledge was used, i.e. D = Da = Dt = 0. The ob­ jective of the experiments was to determine the impact of varying clustering factors on the clusters of action se­ quences computed and the feasibility of plan libraries created from them for plan recognition purposes. To this end the following experiments were performed using a 10-fold cross validation strategy 2 with the value of the clustering factor ranging from 0.1 to 1.0 in steps of 0.1.

1. Compute a clustering of the training data as described in Section 3.

2. For each resulting cluster compute the join of all its elements as described in Section 2.

1. Try to recognize the test action sequences using the plan library containing all plans created in step 2.

Remarks: 1. The plan computed in the second step is labeled to belong to the prevailing class among the action sequences contained in the cluster. In case of a tie- i.e. two or more classes occur with the same (high­ est) frequency- a corresponding number of copies of this plan is included in the plan library, each marked with one of these classes. 3 Labeling the plan library entries­ usually the task of a domain expert- is an important prerequisite for the plan recognition process. The plan recognizer's task consists in identifying all plans within the library that are completely instantiated by the cur­ rent action sequence-i.e. the sequence contains all of the plan's actions and satisfies all of its constraints- and as­ signing their respective classes (as plan hypotheses) to this sequence.

2. Note that a plan library does not necessarily contain just one plan for each class (goal).

3. To produce unbiased results in the third step, a purely consistency-based, incremental plan recognizer was used that applied no focusing heuristic to discard unwanted plan hypotheses. Instead, consistency of observed actions with the plan decompositions was the only criterion to decide whether or not to maintain a hypothesis.

2 That is, the set of action sequences was randomly parti­ tioned into 10 subsets of about equal size. In each of the 10 repetitions of the experiments, 9 of these subsets were used as training data whereas the respective remaining subset formed the set of test data.

3 0f course the class memberships of the training data were not used during the clustering process.

As a comparison, alternative clusterings were com­ puted using Cobweb [Fisher, 1987]. Cobweb incremen­ tally constructs a hierarchy of clusters containing "sim­ ilar" instances. Finally each node of the tree represents a concept, i.e. an intensional description of the class of instances subsumed in terms of the attribute values oc­ curring within this class. While the leaves of this hierar­ chy contain the various instances, the root represents the most general class containing all instances encountered during the learning process. As Cobweb expects its input to be described in terms of attribute values, each action sequence was encoded as a vector of 39 Boolean values, each indicating the (non-) occurrence of one part icular command within the sequence. To enable a fair compari­ son with the clustering procedure described in Section 3, a particular class of concepts was selected from the Cob­ web hierarchies the subsumed instances of which form a partition of the training set while containing a "reason­ able" number of elements.

Remark: The leaf concepts would have been inappro­ priate as they only contain one instance each, while very abstract concepts (i .e. those being close to the root of the hierarchy) increase the danger of producing "bad" clus­ ters containing instances from many different classes.

A class C (represented as a node in the tree) is said to be "appropriate" iff

• C is not a leaf,
• none of the siblings of C is a leaf, and
• none of the descendants of C (as a node in the tree) is appropriate.

The clustering used in the experiments then corresponds to the collection of sets of instances subsumed by the appropriate classes.

The analysis of the empirical findings has to take into account several different aspects the first of which con­ cerns the clusters detected.

How "good" are the clusters? Obviously, an optimal clus­ ter contains only elements belonging to the same class, i.e. action sequences achieving the same domain goal. The degree of "disorder" within a cluster C can be mea­ sured by the entropy e(C) defined as

where c ranges over the possible classes (goals) an in­ stance (sequence) can belong to and Pc is the relative frequency of instances belonging to class c among all in­ stances contained in C. This numerical value can be used to quantitatively assess how well a cluster is "sorted" (note that e(C) assumes its minimal value of zero when all instances contained in C belong to the same class). In order to allow the results of experiments with vary­ ing numbers of classes to be compared, we use a relative measure of entropy by dividing the values obtained by ( 1) by the entropy of the original set of instances (action sequences) such that a value close to 1.0 corresponds to a random selection of sequences from the training data. Figure 3 depicts the average values of this relative en­ tropy measure along with the average values of the rela­ tive degree of restrictiveness. The latter corresponds to the degr values of the plan library entries created divided by the average degr value of the original action sequences contained in the training data. 4 As could be expected, an increasing value of cf yields clusters with high entropy values (the larger the cluster, the higher the probability to include sequences from more than one class) and the complexity of the plans produced-measured by degr­ decreases. It can be seen that the cf values between 0.4 and 0.7 offered the best compromise between reduc­ ing the complexity of plan descriptions-without being over-restrictive or trivial-and maintaining a relatively low cluster entropy.

The results for Cobweb indicate that even the small clusters used in this comparison (most of them contained only 2 or 3 action sequences) have a relatively high en­ tropy, i.e. these clusters are not "well sorted". As a consequence, joining the action sequences contained in these clusters produced an average of 4 "void" plans containing no actions or constraints in each repetition of the experiment, i.e. the sequences within such a clus­ ter were highly incompatible with each other. 5 These plans were removed from the library before starting the plan recognition process. The relative degr and entropy values when ignoring void plans are 0.175 and 0.22, re­ spectively. The high degr values result from the small number of elements per cluster.

The second-and in this context even more import­ ant- question is how good are the plan libraries pro­ duced? To answer this question, the abovementioned plan recognition experiment was conducted the results of which are depicted in Figures 4 and 5. Here coverage stands for the percentage of action sequences for which the plan recognizer produced a non-empty result , cor­ rect (unique) is the percentage of sequences recognized correctly (correctly and uniquely 6 ). Plan hypotheses as- To summarize the results, a clustering factor of about 0.6 yielded the best results for this domain (other do­ mains may require different values for c/). Here almost 90% of all action sequences where covered, more than 77% were correctly recognized, and for more than 28% this result was even unique. The results for the libraries generated using the Cobweb clustering (78%, 68%, and 11%) are similar to those for the clustering factor 0.4. Note, however, that the degree of ambiguity measured by the ~umber of plan hypotheses assigned is signifi­ cantly htgher for the Cobweb-based libraries than for all other competitors. With cf = 0.6, for example, each ac­ tion sequence is assigned at most two hypotheses while the average in the Cobweb case is almost 2.5 (out of 6 different classes). Additionally, for cf = 0.6 the plan rec­ ognizer worked about ten times as fast as for cf = 0.1 or cf = 0.2 which is a direct consequence of the large num­ ?er of library ent~ies of high complexity (degr values) m these cases, whtle the Cobweb-based libraries slowed down recognition even more. The smaller libraries ob­ tained for very high cf values speed up this process even more, but the recognition results are relatively poor.

:All values computed with Wa = Wp = Wt = 1 and w. = 2. Note that the clustering method introduced in Section 3 never lead to void plans.

6 Note that in many cases more than one plan hypothesis from the library proved compatible with the current action

5 Related Work

Abstracted versions of previous problem solutions have been studied both in the fields of AI planning (e.g.

sequence- d. Figure 5.

[Minton, 1985)) and programming by demonstration (e.g. [Cypher, 1993]). In the former case they are reused for efficient planning from second principles, in the latter they enable a system to autonomously perform certain tasks on behalf of their users. As in both cases the aim is to generate an executable procedure, exact character­ izations of actions (including preconditions and effects) as well as general domain laws are required. In contrast to this, the joining of action sequences as presented in this paper aims at producing recognizable structures and does not presuppose any domain knowledge.

In the plan recognition context, the explanation-based learning (EBL) procedure described in [Mooney, 1988] and the machine-learning inspired approach presented in [Lesh and Etzioni, 1996] have to be mentioned. In the first case the objective is to detect the general plan un­ derlying a short narrative. As EBL is a very knowledge­ intensive method, rich domain knowledge has to be avail­ able in order to produce generic structures that can be used to analyze similar, unknown stories. In the latter case the goal and plan libraries are only implicitly defined by a set of goal predicates and actions and corresponding biases that allow the search space to be enumerated. As a consequence, only certain classes of domain goals can be handled and the system requires complete planning knowledge.

The IPAM algorithm presented in [Davison and Hirsh, 1998] is a knowledge-free method to construct a proba­ bilistic model of action patterns contained in action se­ quences that is used to predict future actions. This is in contrast to [Yoshida and Motoda, 1995] where infor­ mation about IO relationships among UNIX commands is exploited to produce a probabilistic predictive model. Unlike IPAM, this graph induction method needs rela­ tively few training data to successfully make predictions. Both approaches do not explicitly mention plans, but try to detect regularities in user behaviors.

Clustering algorithms on the basis of shared subse­ quences (e.g. [Zaki et al., 1998)) are not able to abstract from the observed temporal relations among the actions in the training sequences. As a consequence they are not feasible for the task of generating abstract plans for plan recognition libraries.

6 Conclusion and Future Work

This paper introduced a clustering method that allows groups of similar action sequences to be detected that can be used to generate plan library entries, even in the complete absence of domain knowledge. The empirical findings indicate that the libraries produced by this clus­ tering algorithm in combination with the join algorithm can indeed be successfully used for plan recognition pur­ poses. At least for certain values of the clustering factor the results were better than those produced by using Cobweb to compute a clustering of the training data. It is important to note that the library entries generated are not necessarily executable "recipes", but structures that can be used to recognize the underlying domain goal. The recognition process is particularly well sup­ ported as these plans reflect the actual user behavior rep­ resented by the interaction samples used in the training data (including suboptimal and faulty behavior) while hand-coded libraries often concentrate on optimal or at least correct plans. Another application of the cluster­ ing/joining procedure is the generation of alternative de­ compositions for one single class in situations where the training data are already labeled with their respective class memberships, but contain strongly diverging ways of achieving the same goal.

Future work will include the application of the meth­ ods presented to additional domains and the investiga­ tion of the impact of various degrees of domain knowl­ edge that could be used to improve the quality of plans and support the domain expert labeling the library en­ tries. Furthermore, comparisons with other clustering algorithms will be performed.