We present a method for context-dependent and incremental intention recognition by means of incrementally constructing a Bayesian Network (BN) model as more actions are observed. It is achieved with the support of a knowledge base of readily maintained and constructed fragments of BNs. The simple structure of the fragments enables to easily and efficiently acquire the knowledge base, either from domain experts or automatically from a plan corpus. We exhibit experimental results improvement for the Linux Plan corpus. For additional experimentation, new plan corpora for the iterated Prisoner's Dilemma are created. We show that taking into account contextual information considerably increases intention recognition performance.
We propose a method for intention recognition in a
dynamic, real-world environment. An important aspect of
intentions is future-directedness, i.e. if we intend something
now, we mean to execute a course of actions to achieve
something in the future [
Generally, intention recognition (also called goal
recognition) is defined as the process of becoming aware of the
intention of another agent and, more technically, as the
problem of inferring an agent’s intention through its actions and
their effects on the environment [
In this work, we use Bayesian Networks (BN) as the
intention recognition model. The flexibility of BNs for
representing probabilistic dependencies and the efficiency of
inference methods for BN have made them an extremely
powerful and natural tool for problem solving under
uncertainty [
It is inspired in that knowledge experts often consider
a related set of variables together, and organize domain
knowledge in larger chunks. An ability to represent
conceptually meaningful groupings of variables and their
interrelationships facilitates both knowledge elicitation and
knowledge base maintenance [
Definition 1 A BN is a pair consisting of a directed acyclic
graph (DAG) whose nodes represent variables and
missing edges encode conditional independencies between the
variables, and an associated probability distribution
satisfying the Markov assumption of conditional independence,
saying that variables are independent of non-descendants
given their parents in the graph [
In a BN, associated with each node of its DAG is a specification of the distribution of its variable, say A, conditioned on its parents in the graph (denoted by pa(A))—i.e., P (Ajpa(A)) is specified. If pa(A) = ; (A is called root node), its unconditional probability distribution, P (A), is specified. These distributions are called Conditional Probability Distribution (CPD) of the BN.
The joint distribution of all node values can be determined as the product of conditional probabilities of the value of each node on its parents P (X1; :::; XN ) = QiN=1 P (Xijpa(Xi)), where V = fXij1 i N g is the set of nodes of the DAG.
Suppose there is a set of evidence nodes (i.e. their values are observed) in the DAG, say O = fO1; :::; Omg V . We can determine the conditional probability distribution of a variable X given the observed value of evidence nodes by using the conditional probability formula
P (XjO) =
P (X; O)
P (O) =
P (X; O1; :::; Om)
P (O1; :::; Om) (1) where the numerator and denominator are computed by summing up the joint probabilities over all absent variables with respect to V . 3
In [
C-1 C-2 . . .
C-x
Intentions
I-1 . . .
I-y
Actions A-1 . . . .
A-z present a method for incrementally constructing such BN model for performing incremental intention recognition.
A BN for intention recognition (IRBN) W is a triple hfCs; Is; Asg; pa; PW i where
Cs, Is and As are the sets of cause/reason nodes, intention nodes and action nodes, respectively. They stand for binary random variables (i.e. their value is either true (T) or false (F)). pa is a mapping which maps a node to the set of its parent nodes such that: pa(C ) = ; 8C 2 Cs; pa(I ) Cs 8I 2 Is; and ; 6= pa(A) Is 8A 2 As. CPD tables are given by the probability distribution PW , i.e. PW (Xjpa(X)) defines the probability of X conditional on pa(X) in W, 8X 2 Cs [ Is [ As. The intention recognition method will be performed by incrementally constructing an IRBN as more actions are observed. The construction is based on a prior knowledge base consisting of Unit BN Fragments.
Definition 3 (Unit Fragments) There are two types of unit fragments used for IRBN model construction: 1. A unit fragment for an action A consists of an intention I connecting to (i.e. causally affecting) A, and is denoted by UFA(I ; A). 2. A unit fragment for an intention I consists of a contextindependent and fixed over time set of causes/reasons Cs connecting to (i.e. causally affecting) I, and is denoted by UFI(Cs; I ).
base KB consists of a set of actions , a set of intentions , a set of unit fragments for each action in and a single unit fragment for each intention in , satisfying that An intention I has a unique unit fragment in KB. The set of its parents (causes) and the CPD table associated with it are fixed. Let C(I) denote the set of parents of I and PKB(IjC(I)) define its CPD table. I1 . . . .
IN A cause C has the same prior probability distribution in all the unit fragments (for intentions) that it belongs to, denoted by PKB(C).
The simple structures of unit fragments enable domain experts to easily construct and maintain the knowledge base. The fragments also can be learnt from appropriate datasets, as we shall see later with the Linux and IPD corpora. Before presenting the intention recognition algorithm, let us define some (original) operators for handling CPD tables and IRBNs. 3.1
As a new action A is observed, we need to incorporate it
into the current IRBN. First, appropriate unit fragments for
A are selected from KB. Let select(A) denote the set of all
unit fragments for A from KB 1. They are then combined
using the Noisy-OR method [
for action A is an IRBN with a single action, denoted by irBN (A) = hfCs; Is; fAgg; pa; PW i. It is obtained via Noisy-OR method as follows. Let select (A) = fUFA(I1 ; A); ::::; UFA(IN ; A)g and for 1 i N , P (A = T jIi = T ) = qi (defined in fragment UFA(Ii ; A)). Then,
Is = fI1; :::; IN g; Cs = SI2Is C(I);
pa(I) = C(I) 8I 2 Is; pa(A) = Is;
PW (C) = PKB(C) 8C 2 Cs; PW (I) =
PKB(I) 8I 2 Is; and, according to the Noisy-OR
method, PW (A = T jpa(A)) = 1 Qi:Ii=T (1 qi).
The rationale and appropriateness of the application of the
Noisy-OR method here for combining unit fragments is
based on the intuition that each intention can be interpreted
as a “cause” of action A; and action A occurs when one or
more of the intentions are active. Detailed arguments for
this can be found in [
1The selection can be done in a context-dependent manner, but it is beyond the scope of this paper.
ble defining P (XjV ), the probability of a random variable X conditional on a set of random binary variables V, and V 0 ( V . The project of Tb on V 0, denoted by proj(Tb; V0), is the part of Tb corresponding to all variables in V n V 0 being false.
Now we need to combine the obtained unit IRBN, irBN(A), with the current IRBN. For that, in the sequel we define how to combine two IRBNs. Intuitively, we simply add up all the new nodes and links of the new IRBN to the current IRBN, keeping the CPD tables from the original IRBNs.
W1 = hfCs1 ; Is1 ; As1 g; pa1 ; P1 i and W2 = hfCs2 ; Is2 ; As2 g; pa2 ; P2 i be two IRBNs, such that As1 \ As2 = ; (the actions in As2 which are already in As1 are renamed). The combination of these two IRBNs is an IRBN, denoted by comb(W1; W2) = hfCs; Is; Asg; pa; PW i, where As = As1 [ As2; Is = Is1 [ Is2; Cs = Cs1 [ Cs2; pa(I) = C(I) 8I 2 Is; pa(A) = pa1(A) [ pa2(A); PW (C) = PKB(C) 8C 2 Cs; PW (Ijpa(I)) = PKB(IjC(I)) 8I 2 Is; PW (Ajpa(A)) = PWk (Ajpak(A)) if A 2 Ask (with k = 1; 2).
Note that here it is allowed the possibility that the observed agent follows multiple intentions simultaneously. When some intentions are found irrelevant—e.g. because they are much unlikely2—those intentions should be removed from the IRBN. This is enacted by considering them as completely false and employing the project operator.
W = hfCs; Is; Asg; pa; PW i be an IRBN and R Is a strict subset of Is. The result of removing the set of intentions R from W is an IRBN, denoted by remove(W; R) = hfCsR; IsR; AsRg; paR; PRi, where AsR = As; IsR = Is n R; CsR = SI2IsR C(I); paR(I ) = C(I ) 8I 2 IsR; paR(A) = pa(A) n R 8A 2 AsR; PR(C) = PKB(C) 8C 2 CsR; PR(IjpaR(I)) = PKB(IjC(I)) 8I 2 IsR; and for each A 2 AsR, PR(AjpaR(A)) is defined by the CPD table proj(Tb; paR(A)) where Tb is the CPD table for A in W, i.e. defined by PW (Ajpa(A)).
Based on these operators, we now describe an algorithm for incremental intention recognition in a real-time manner.
the following steps until some given time limit is reached; the most likely intention in previous cycle is the final result.
2One intention is much less likely than the other if the fraction of its likelihood and that of the most likely intention is less than some small threshold. It is up to the KB designer to provide it. Let A be a new observed action. Combine the current IRBN W with irBN(A) to obtain W0 = comb(W; irBN(A)). If A is the initially observed action, let W0 = irBN(A).
Compute the probability of each intention in W 0, conditional on the set of current observations in W 0. Remove the intentions which are much less likely than the others (following Definition 8). 4
When considering the case in which the observed agent may pursue multiple intentions simultaneously, it is undoubtedly indispensable to take into account and express the relations amongst the intentions in the model. Pursuing one intention may exclude some other intention to be pursued. We introduce a so-called exclusive relation e—a binary relation on the set of intention nodes—representing that if one intention is pursued, then the other intention cannot be pursued. It is usually, although perhaps not always, the case that intentions exclusiveness is symmetric. Here we assume that e is symmetric; it can be renamed mutually exclusive relation.
Intentions I1 and I2 are mutually exclusive iff they cannot be pursued simultaneously, i.e. P (I1 = T; I2 = T ) = 0. Thus, for any action A, if I1; I2 2 pa(A) then the CPD table for A is undefined. Hence, the BN needs to be restructured. The mutually exclusive intentions must be combined into a single node since they cannot co-exist as parents of a node. Each intention represents a possible value of the new combined node. Namely, let I1; :::; It be such that e(Ii; Ij ); 8i; j : 1 i < j t. The new combined node, I, stands for a random variable whose possible outcomes are either Ii; 1 i t, or I~—the outcome corresponding to the state that none of Ii = T . Note that if the intentions are exhaustive, I~ can be omitted. Next, I is linked to all the action nodes that has a link from one of Ii; 1 i t. There remains to re-define CPD tables in the new BN. They are kept the same for action A where I 62 pa(A). For A such that I 2 pa(A), the new CPD table at I = Ii corresponds to the CPD table in the original BN at Ii = T and Ij = F 8j 6= i, i.e. P (AjI = Ii; :::) = P (AjI0 = F; :::; Ii 1 = F; Ii = T; Ii+1 = F; :::; It = F; ::::). Note that the left hand side is defined in the new BN, and the right hand side is defined in the original BN. Similarly, the new CPD table at I = I~ corresponds to Ii = F 81 i t. We now specify the CPD table of I. In the new BN, the causes/reasons of each intention are connected to the combined node, i.e. pa(I) = St i=1 C(Ii). Applying the Markov assumption (Def.1) we have P (I = Iijpa(I)) = Pi(Ii = T jC(Ii)) and P (I = I~jpa(I)) = Qt i=1 Pi(Ii = F jC(Ii)), where Pi is the probability distribution of the unit fragment for Ii.
In the next section we focus on the single intention recognition case, showing how the approach to representing relationships amongst intentions can significantly decrease the complexity of the probability inference therein. We then present experimental results on the Linux Plan corpus. After that, in Section 6, we provide further experimentation on our novel, so-called IPD plan corpora. 5 5.1
Suppose the observed agent pursues a single intention. In this case, all intentions are mutually exclusive, and they can be combined into a single node. The IRBN then has a single intention node, linking to all action nodes. All cause/reason nodes are connected to the intention node. Let I1; :::; In be the intentions in the original IRBN. As usual, they are assumed to be exhaustive, i.e. the observed agent is assigned an intention from them. The combined node I thus has n possible outcomes Ii; 1 i n. Let As = fA1; :::; Amg be the set of current observed actions. The set of all cause/reason nodes are Cs = [in=1C(Ii). Suppose Ce Cs is the set of cause/reason nodes which are observed (evidence nodes). Let Cne = Cs n Ce. Applying Eq. 1, we obtain the probability of each intention conditional on the current observations, for 1 j n, P (I = Ij jCe; As) =
P (Ij ; Ce; As) Pn i=1 P (Ii; Ce; As)
; where m P (Ij ; Ce; As) = Y P (AijIj ) i=1
X P (Ij jCs) Y P (C) Cne
C2Cs ! This implies that, when not including causes/reasons of intentions (Cs = ;) as in case of Linux Plan corpus below, our intention recognizer has a linear complexity O(jnj). If all the cause/reason nodes are not observable, i.e. Cne = Cs (as in the case of the Linux Plan we examine in the next subsection), it is easily seen that: P (Ij ; Ce; As) = P (Ij ) Qm
i=1 P (AijIj ). If all of them are observed (Cne = ;) (as we shall see in the IPD Plan corpora), the term QC2Cs P (C) is simplified in the fraction. Thus, in these two cases, we do not need to define prior probabilities distribution of the root nodes in Cs. Note that in the latter case we still need to compute the conditional probabilities P (Ij jCs). 5.2
The Linux Plan Corpus. Plan corpus is the term used
to describe a set of plan sessions and consists of a list of
goals/intentions and the actions a user executed to achieve
them [
The Linux Plan corpus is an important (especially in the
interface-agents domain [
ment UFA(I ; A), the conditional probability of A given
I is defined by the frequency of A in a plan session for
achieving the goal/intention I divided by the frequency of
any action for achieving I: P (A = T jI = T ) = frfreeqq((AII)) .
For better understanding, in the plan corpus each action is
marked with the intention which the action is aiming at.
Then, freq (AI ) is the frequency of A being marked by I,
and freq (I ) is the frequency of seeing the mark I.
Prior probabilities of all the intentions in the corpus are
given initially, and used for generating tasks for users [
Evaluation Metrics. For evaluating our system and
comparing with the previous ones [
i=1 correct(ai))=Z, where z and Z are the number of predictions made (when the recognizer is confident enough) and the total number of prediction opportunities (i.e. when = 0), respectively.
On the other hand, convergence is a metric that indicates how much time the recognizer took to converge on what the current user goal/intention was. Let t be such that correcti = 0 for 0 i t 1 and 1 for t i n (i.e. t is the first time point which from there on the system always correctly predicts), convergence for Seq is defined as: convergence(Seq) = (z t + 1)=z.
Finally, the overall precision, recall and convergence are
obtained by taking averages over all testing sessions.
Experiments and Results. Because of the small size of
the Linux corpus, similar to previous works, we ran
experiments using the one-out cross validation method [
We present new plan corpora in the context of iterated
Prisoner’s Dilemma (IPD) [
Prisoner’s Dilemma (PD) is a symmetric two-player nonzero game defined by the payoff matrix
C D
C R; R T; S
D S; T P; P Each player has two options in each round, cooperates (C) or defects (D). A player who chooses to cooperate with someone who defects receives the sucker’s payoff S, whereas the defecting player gains the temptation to defect, T . Mutual cooperation (resp., defection) yields the reward R (resp., punishment P) for both players. PD is characterized by the payoff ranking T > R > P > S (and, in addition, 2R > S + T for IPD). Thus, in a single round, it is always best to defect, but cooperation may be rewarded if the game is iterated. Let r denote the (average) number of rounds the game is iterated.
IPD is usually known as a story of tit-for-tat (TFT), which
won both Axelrod’s tournaments [
Next, we describe how training and testing plan corpora are created employing these strategies. We made an assumption that all strategies to be recognized have the memory size bounded-up by M (M 0)—i.e. their decision at the current round is independent of the past rounds that are at a time distance greater than M . The strategies described above have memory M = 1. Abusing notations, R; S; T and P are referred to as game states (in a single round or interaction). We too use E (standing for empty) to refer to the game state having had no interaction. An action in the corpus is of the form s1:::sM , where si 2 fE; R; T; S; P g, 1 i M , are the states of the M last interactions, and 2 fC; Dg is the current move. We denote by M the set of all possible types of action. E.g, 1 = fEC; RC; T C; SC; P C; ED; RD; T D; SD; P Dg. This encoding method enables to save the game states without having to save the co-player’s moves, thus simplifying the corpus representation, described below.
Suppose we have a set of strategies to be recognized. The plan corpus for this set consists of a set of plan sessions generated for each strategy in the set. A plan session of a strategy is a sequence of actions played by that strategy (more precisely, a player using that strategy) against an arbitrary player. As an example, let us consider TFT and the following sequence of its interactions with some other player (denoted by X), in the presence of noise round : 0
TFT :
X : TFT-states : E 1 C C R 2 C D S P 3 D D 4 D C T 5 D D P The corresponding plan session for TFT is [EC; RC; SD; P D; T D]. At 0-th round, there is no interaction, thus the state is E. TFT starts by cooperating (1-st round), hence the first action of the plan session is EC. Since player X also cooperates in the 1-st round, the game state at this round is R. TFT reciprocates in the 2-nd round by cooperating, hence the second action of the plan session is RC. Similarly for the third and the fourth actions. Now, at the 5-th round, TFT should cooperate since X cooperated in 4-th round, but because of noise, it makes an error to defect. Therefore, the 5-th action is TD. 6.3
Let us start by generating a plan corpus for seven most popular strategies within the IPD framework: AllC (always cooperate), AllD (always defect), TFT, GTFT (probability of forgiving a defect is p = 0:5), WSLS, GRIM and FBF. We collect plan sessions of each strategy by playing a random move (C or D) in each round with it. To be more thorough, we can also play all possible combinations for each given number of rounds r. E.g, if r = 5, there are 25 combinations: C or D in each round. When noise is present, each combination is played repeatedly several times. The training corpus to be used here is generated by playing with each strategy all the possible combinations 10 times, for each number of rounds r from 5 to 10. The testing dataset is generated by playing a random move with each strategy in each round, also for r from 5 to 10. We continue until obtaining the same number of plan sessions as of the training dataset (corpus). Both datasets are generated in the presence of noise (namely, an intended move is wrongly performed with probability 0.05).
In this testing dataset, intention (strategy)
changes/abandonment are not taken into account. The
players use the same strategy in all the rounds. We
refer to this testing dataset as Testset-IRFIX. For
testing the context-dependent aspect of our intention
recognizer, as well as taking into account intention
changes/abandonment, we next introduce the concept of
social learning within the framework of evolutionary game
theory [
In social learning, individuals in a population can observe
the behavior of others and the outcomes of those
behaviors. They copy the behavior of others whenever these
appear to be more successful [
It is now allowed the possibility that a player can change his/her strategy (intention) by imitating the randomly met player’s strategy (intention), depending on how the latter player is more successful. The two players’ ongoing success difference (SD) causally affects the imitating player’s current intention. In addition, this intention is causally affected by the so-called imitation event (IE), stating whether the player is meeting some other player for learning/imitating. Now we have an IRBN with two cause/reason nodes, a single intention node, and observed Imitation Event
(IE) Success Difference (SD)
Intention (I)
A-1 . . . .
A-m
We define the conditional probability distribution P (Ii jIE ; SD ). If the player does not meet any other player for imitation (i.e. IE = F ), Ii is independent of the success difference SD: P (Ii jIE = F ; SD ) = P (Ii jIE = F ). Now, let us consider the case IE = T . If the successes are also observable (thus, SD is observed, say, equal )3, but the strategy of the imitated player is not, we have P (Ii jIE = T ; SD = ) = (1 u)pi +
u S 1
X pj (2) j6=i where u = (1+e ) 1; pi is the probability that Ii was the player’s intention in the last prediction; and S is the number of strategies in the corpus. The formula is explained as follows. With probability (1 u)pi the imitating player’s strategy remains Ii. Moreover, not being observed, the probability that Ii was the imitated player’s strategy is (assumed) equal 1=(S 1). The second term expresses the probability that the player adopts the new strategy Ii by imitation. Now, in case the imitated player’s strategy is also observable, denoted by Ii? , similarly we have
P (Ii? jIE = T ; SD = P (Ii jIE = T ; SD = ) = (1 ) = (1 u)pi + u X pj u)pi 8 i 6= i? j6=i? (3) Testing Dataset. The testing dataset in this setting is generated by using a simplified evolutionary simulation as follows. We play a random choice with each of the seven above mentioned strategies for 10 rounds. The payoff of each strategy is accumulated over all the rounds. Then, for each strategy, another strategy is randomly chosen from the other six for imitation using the pairwise comparison rule. After all the seven strategies are given the chance to change their strategy (imitate another), the interactions are repeated for 10 more rounds. At the 10-th round, we save the accumulated payoff values of the imitating and imitated strategies. We experiment until obtaining the same number of plan sessions as in the training dataset. The PD payoff 3There may be noise in the evaluation of the successes. The observed value of SD is randomly taken in the range ((1 ) 1; (1 + ) 1), where is a small positive number (here we use = 0:01) and 1 is the exact value of the difference.
1 best 2 best 3 best c. 0.8
N=1
No Info Successes Strategy 0.0 0.2 0.4 0.6
0.8 Τ a. 1.0 The intention recognition model is acquired using the training corpus. Figures 4a and 4b show the precision and convergence of the model with respect to the Testset-IRFIX. Given that the training as well as the testing datasets are generated in presence of noise, the achieved performance is quite good. Namely, for big enough , both precision and convergence scores are greater than 0.9, even for the 1-best case.
In Figure 4c we show the effects of having different levels of contextual information on the intention recognition performance, using Testset-IRCHANGE dataset. Namely, in the first setting (blue curves), there is no information about the imitation event (IE) – it is not known if the recognized player may imitate and adopt another strategy. In the second setting (black curves), IE and the successes are observable. In the third setting (red curves), the strategy of the imitated player is also observable. It is clearly shown that the performance is considerably increased as more contextual information is available. Namely, comparing with the first setting where no contextual information is taken into account, an increase of about 5% and 15% precision is achieved in the second and third settings, respectively. 7
RELATED WORK
terior probability of explanations (for the set of observed
actions). These works address a number of important
issues in intention/plan recognition (see [
Different from all above mentioned works, our model is context-dependent, which is achieved by including in it causes/reasons of intentions. This way, our model can appropriately deal with the abandonment/changes of intentions—when the causes/reasons do not support or force the intending agent to hold those intentions anymore. 8
Bayesian Networks have been one of the most successful
models applied for the intention/plan recognition problem,
e.g. in [
For further experimentation, we have created the so-called
IPD plan corpora for the famous strategies in the
context of the iterated Prisoner’s Dilemma. We employed
the famous model of (human) behaviors by means of
social learning and evolutionary game theory to simulate
intention changes/abandonment—enabling us to evaluate
the context-dependent aspect of our intention recognizer
and as well as its capability of dealing with intention
changes/abandonment. Our experimental results show that
taking into account contextual information is crucial,
enabling to achieve significant recognition improvements.
The good performance of our method with respect to
the Linux corpus shows its applicability to the important
interface-agents domain [
In Section 4 we made an implicit assumption that the intentions to be combined are perfectly mutually exclusive. This assumption can be relaxed by utilizing a latent variable for any subset of perfectly mutually exclusive intention nodes. We are exploring this direction to provide a more general method for representing relationships amongst intention nodes. 9
We thank the reviewers for useful comments. HTA acknowledges the support from FCT-Portugal, grant SFRH/BD/62373/2009.