Agent-Oriented Incremental Team and Activity Recognition

1 Introduction

In many real-life scenarios human teams need to cooperate towards the achievement of one or more goals during the enactment of a joint plan. Examples of such scenarios are disaster relief operations, crowd management at major outdoor events, and search-and-rescue missions [Sukthankar et al., 2008]. Monitoring team activity is essential when time is a critical factor for the success the plan and the operating environment is uncertain. Monitoring allows teams to maintain awareness of each other's progress within the plan, it helps to keep interdependent tasks synchronised, and it enables anticipation of information needs. Monitoring has become easier to perform thanks to the development of wireless sensor networks that can collect large amounts of environmental data during plan execution. There is, however, a risk that processing that data may result in cognitive overload for humans, therefore hampering effective decision-making.

We propose the multi-agent architecture illustrated in Figure 1 to monitor team activity during plan execution. At the lower level, a software agent is associated with each team,

∗ This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence and was accomplished under Agreement Number W911NF-06-30001. The views and conclusions contained in this document are those of the author(s) and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.

Katia Sycara

Robotics Institute Carnegie Mellon University Pittsburgh, PA USA

working as that team's assistant. Teammembers usually employ teamwork when acting in a time-critical scenario, hence their movement patterns will be related in time and space. The team as a whole will also exhibit recognisable behaviour patterns (e.g., tactics or manoeuvres). Machine learning techniques can be applied to learn such patterns, so that the agent can infer the team composition and perform activity recognition based on the team members' locations. Recognised activities Ai are represented as hexagons in Figure 1.

At the upper level, activities Ai will be used as evidence about the plan progress by matching them against atomic plan actions. This process can identify active plan branches (bold grey path in Figure 1) but can also be exploited to detect deviations from the expected course of action. We assume that a software agent has some knowledge about the plan structure (STaski) and dependencies (links between STaski). These could be of any nature (e.g., ordering/time constraints, team size) and are usually specified as part of the joint plan.

In this paper we focus on team composition and activity recognition (lower level in Figure 1). Existing research on probabilistic models for activity recognition has mainly focused on single subjects, rather than teams. In addition, prediction is mostly performed on complete observation traces, rather than on a observation window (see Section 2). Even when classification is performed incrementally on a window, the computational cost depends on the window size, and little attention is dedicated to the cost of aggregating sensor data into features for efficient classification. These aspects are key to performing incremental prediction when software assistants are implemented into portable, resource-limited devices. In Section 4 we introduce a probabilistic model to recognise teams and activities incrementally from a stream of observations. The model is based on Conditional Random Fields (see Section 3). It can perform inference over an observation window in polynomial time independent of the window size, or on the entire sequence. It also scales well with respect to the number of observed subjects. In Section 5 we evaluate the model on spatio-temporal observations collected from artificial players acting in a virtual environment. We finally conclude in Section 6.

2 RelatedWork

The two main approaches to activity recognition are template-based matching and probabilistic graphical models.

Template-based matching for team activity recognition [Sukthankar and Sycara, 2006] relies on a library of team behaviours, usually acquired by encoding experts' knowledge about the application domain. This approach attempts to match observed team features against the library in order to find one or more suitable labels for the observations. Template-based matching does not usually require machine learning because relationships between observations and labels are encoded in the library. Considerable effort, however, has to be put into eliciting the appropriate knowledge and encoding it into the library; in addition, particular care is required in designing matching algorithms that are robust to noise in the observations [Nguyen et al., 2003].

In recent years, machine learning techniques, and in particular probabilistic graphical models, have received much attention because of their ability to effectively learn and infer activities from spatio-temporal observations. Conditional Random Fields (CRFs) are probabilistic models that were first applied to pattern recognition tasks in natural language processing, but they have become popular for activity recognition. Linear CRFs have been employed to identify the role of single robots in a game of Tag according to their locations [Vail et al., 2007] and to recognise player roles in the RoboCup domain [Vail et al., 2008], where two teams of computer-controlled robots compete in a football match. Relational Markov Networks [Liao et al., 2007a] have been used to model a person's high-level activities (being at work, being at home, travelling) and significant places visited, based on GPS traces of that person's movements throughout the day. [Liao et al., 2007b] has introduced a Dynamic Bayesian Network for learning and inferring transportation routines. That model was able to detect deviations from the routine, and to predict a person's location both in the short (e.g., change at a bus stop) and long term (e.g., travel to work or home).

Observations other than spatio-temporal traces can be used as well; in [Lian and Hsu, 2009], Factorial CRFs trained with annotated audio recordings were used to learn and classify chatting activity in meetings and public occasions. In [Yin et al., 2009], Dynamic CRFs were shown to perform well in detecting events (e.g., presence of light) generated by a network of sensors distributed in an environment of interest. In common with to our approach, relationships among sensor readings in response to events were exploited to create meaningful features for classification. Most of that work relies on complex probabilistic models which may offer an increased accuracy in recognition, but required iterative, approximate inference algorithms whose running time cannot be characterised well in terms scalability with respect to the window/sequence size and the number of features.

3 Conditional RandomFields

Conditional Random Fields (CRFs) [Lafferty et al., 2001] are probabilistic graphical models to perform relational learning on data sequences. Given a sequence of T observations x = (x1, . . . , xT ) and a sequence of corresponding hidden variables y = (y1, . . . , yT ), a CRF represents a conditional distribution p(y|x) as an undirected graph G. Nodes in G belong to the set {yt}∪{xt} and edges capture dependency relationships between observations and hidden variables. Hidden variables yt assume values from a finite set of labels Y. The distribution p(y|x) is computed as:

In (1), C is the set of cliques in G, Ψc is a potential function, or factor, associated with clique c, yc ⊆ {yt}, xc ⊆ {xt} and ̂ Y = Y T is the set of all possible label sequences. Z is the normalising partition function that guarantees p(y|x) is a valid probability distribution.

In our approach, we use Linear CRFs (LCRF, see Figure 2), which impose a first-order Markov assumption on the hidden variables and have a factor for each sequence position. In LCRFs, factors are defined as a linear combination of M features fi weighted according to a real-valued vector λ:

Features fi are real-valued functions that capture domainspecific relationships between graph nodes belonging to the same factor. They encode preferred label values for the hidden variables yt-1, yt according to some cues gathered from the observation sequence x at time t.

LCRFs are related to Hidden Markov Models (HMMs), but they relax the assumption that the observations in the sequence be mutually independent. This has two advantages:

• The model can accommodate overlapping, interdependent features. In addition, preferred label transitions can be made dependent on the features, making LCRF more suitable to perform inference on spatio-temporal traces [Vail et al., 2007]. 1
• The forward-backward and Viterbi algorithms for efficient exact inference can be adapted to work for LCRFs [Sutton and McCallum, 2006].

Features are represented as a matrix random variable Ft(x) = [Ψt,λ (x, y|(yt-1,yt)=(y′ ,y) )], where (y′ , y) ∈ Y×Y, and the forward and backward vectors α and β are defined as in (3). 2 Marginal probabilities are computed as in (4).

Given a training set E = {(x1, y1) , . . . , (xN, yN)} of N observation/label pairs, a LCRF is trained by computing the optimal weights λ∗ that maximise the log-likelihood ℓλ(E):

where σ is a regularisation parameter to avoid over-fitting. Because ℓλ(E) is convex with respect to λ, the maximisation can be performed via numerical gradient techniques. We employ the limited-memory BFGS algorithm [Zhu et al., 1997].

4 Team and Activity RecognitionModel

Our model is based on the intuition that the spatio-temporal traces of subjects working in a team will exhibit coordination patterns. These patterns can be exploited to learn and classify that team's members and activities. For example, teammates will try to maintain visual contact by remaining close over time; this can be captured by monitoring whether the distance among subjects falls within a particular threshold. Subjects' velocities and accelerations offer good cues as well; teammates usually adjust their speed to maintain uniformity throughout the performance of an activity. Team activities will also show temporal consistency between consecutive time steps. These intuitions are captured in Figure 2; the links between yt-1, yt and x encode those patterns, whereas the link between yt-1, yt guarantees temporal consistency.

1 For example, consecutive measurements of a human subject's position or velocity are dependent, assuming that the sampling is performed at a sufficiently high rate.

2⊥ is a special symbol that identifies the start of the sequence.

In our scenario, S subjects act in a virtual environment. The observation sequence is x = {p1, . . . , pT }, where pt,s contains the 2D position of the s-th subject at time t. S = {s1, . . . , sS,⊖} is the set of all subjects, where ⊖ is a fictitious subject that represents single-subject teams.

4.1 Features

Features play two crucial roles: during learning, they should favour relationships that achieve a good model accuracy; during classification, their computational cost should scale well according to the model size. We define our features as:

In (7), 1A(·) is the indicator function which takes value 1 if (·) belongs to the set A and 0 otherwise; l1 ∈ Y and l2 ∈ Y are label values capturing preferred transitions for two consecutive hidden variables; O ⊆ S is the set of subjects for which the feature is active; so ∈ S is the subject we wish to find a teammate/activity for; g(s1,s2) i computes a spatio-temporal cue for the pair (s1, s2) ∈ S ×S; and scorei aggregates and rates the cues over an observation window of interest. The observation window is centred at the current observation and has length 2W + 1.

Features for Team Recognition

Grouping subjects into teams is challenging because the number of possible teams grows exponentially with S, even if subjects cannot belong to multiple teams [Sukthankar and Sycara, 2006]. Considering all possible teams as label values Y would render inference infeasible. The same would happen if the cues gi were defined over all subject subsets. For these reasons, we created features that match one subject with one of the possible teammates. Because there are only O(S2 ) subject combinations, we can introduce a O(S2 ) number of simple features, where the cost for individual feature is O(1). Therefore, the feature computational cost scales well with respect to the team size. The cost can be reduced even further if features are computed locally by sensors attached to each subject and then collected centrally for classification.

We encoded the features listed in Table 1 in a single LCRF (rather than one per subject) where we set Y = S. The LCRF will learn to associate each subject so with a teammate. Note that cues in Table 1 are not based on raw subject positions pt,s. This would make the model dependent on the particular environment (e.g., the same team often appears at a particular location). Although this might improve the performance for that environment, it would also result in overfitting.

could be computed with an application of (8) to x∗t+1,W , but we compute it more efficiently by updating the forward-backward vectors as αt+1 = 1 · At+1, βt+1 = Bt+1 · 1⊤ where At+1 and Bt+1 are the solutions of the linear systems:

with a time complexity of O(|Y|3 ) (matrix multiplication and system solution computation). Both (8) and (9) require O(W |Y|3 ) memory to store the Fi over the window. Because computing the features requires O(|Y|2 ) time at each time step (see Section 4), inference complexity remains O(|Y|3 ).

There is a limitation in this approach; if some of the Fi are ill-conditioned, the system solutions may be very difficult to compute, even for mainstream linear-algebra packages (e.g., LAPACK). When this happens, we regularise Fi using the Singular Value Decomposition (SVD) [Neumaier, 1998]. When Fi is ill-conditioned, some of its singular values are very close to zero, or zero. We set those to 1, so that Fi becomes fullrank and the system solutions can be computed. Computing the SVD requires O(|Y|3 ) time, but has a significant hidden constant (22); however, because few Fi require regularisation, this cost can be amortised throughout the window. This approach does not completely avoid recomputing the window via (8); round-off errors will eventually make it necessary. This condition can be detected by checking At+1 and Bt+1 for negative entries. Those are invalid because At+1 and Bt+1 are products of matrices with non-negative entries (see (2)). We analyse how often this happens in Section 5.

4.3 Incremental Viterbi

Instead of assigning the best label to each yt, the Viterbi algorithm in (10) can be used to compute the most likely sequence of labels y∗ = arg maxy∈ ̂ Y p(y|x∗ ), given an unseen sequence x∗ . In (10), δt(y) is proportional to the probability of the most likely label sequence (y∗ 1 , . . . , y∗ t-1 ) ending with yt = y; φt(y) encodes the optimal label transition path leading to yt = t given the optimal labels up to time t - 1.

Features for Activity Recognition

Subjects can perform a finite set of behaviours B (see also Section 5), so we created a second single LCRF with Y = B. The LCRF will learn to associate each subject so to the activity the team so belongs to is performing. Features are similar to those listed in Table 1, where values for l1 and l2 belong to B rather than S. We left out cues of type 1.3 and instead included label transition features linked to the subjects' individual speeds and accelerations. We also included label transition features accounting for each subject's team size.

Scores

Each cue g(s1,s2) i in Table 1 is associated to a score 0 ≤ scorei ≤ 1 expressing how likely is that s1 and s2 belong to the same team. For example, cues 1.3 and 1.4 will be given a proportionally higher score the closer s1 and s2 are. Similarly, cues 1.7 will be given a higher score the more similar the subjects' velocities are. It is essential that cue scores be aggregated incrementally over the observation window. In our model we simply average the cue scores. An average ∑Ni=1 xi/N can be incrementally computed by keeping numerator and denominator separate. When a new value xN+1 arrives, the numerator is updated by subtracting x1 and adding xN+1. Other scoring algorithms can be used as long as the incremental update property is guaranteed.

4.2 Incremental Forward-Backward

Classification on a moving window consists of assigning the best individual label to each hidden variable yt. Given an unseen observation window x∗t,W = (x∗t-2W , . . . , x∗t+2W ), yt = argmaxy′∈Y p(y′ |x∗t,W ), where t is the current time step. This can be performed by applying the forward-backward algorithm in (3) and (4), where αt and βt are:

with a time complexity of O(W|Y|3 ) (window size times matrix multiplication). When a new observation arrives, yt+1

The sequence y∗ is retrieved by starting from the most likely final label y∗T = argmaxy′∈Y δT (y′ ) and evaluating y∗ t = φt+1(y∗ t+1 ), T - 1 ≥ t ≥ 1. This, however, requires reaching the end of the observation sequence before obtaining any labelling. It also means that the memory required to store δ and φ may exceed that available on the host system.

We shall instead apply the incremental Viterbi algorithm introduced in [Bobbin, 2007]. The algorithm relies on the path matrix P = [φ1, . . . , φk, . . . , φt] shown in Figure 3. P is a collection of trees where nodes at time t represent label values for yt. Tree paths in Φ identify the most likely label sequences ending with yt = y. It may happen that at some time k, all paths are rooted at a unique initial label y∗ 1 (common root). When this happens again, let us assume at time t, it is possible to output the classification (y∗ 1 , . . . , y∗ k ) up to time k (the black path in Figure 3). At this point the mechanism can restart on a new path matrix P ′ = [φk+1, . . . , φt, . . . , φt′ ]. The incremental Viterbi algorithm does not guarantee to output a new prediction for each new observation, and the worstcase complexity is O(T |Y|2 ). Nonetheless, a partial classification can be obtained based on the frequency of the common roots, hence dramatically reducing memory usage.

5 Experimental Evaluation

We evaluated our recogniser on spatio-temporal traces collected from the shooter game OpenArena, an off-the-shelf game that provides a challenging environment for activity recognition. 3 Teams form and disband rapidly and players' behaviour is highly dynamic. We collected data from a capture-the-flag game; two opposing squads (red and blue) aim to get a flag located in the middle of the game scenario and to bring it to the opponent's base, while protecting their own base. When a squad succeeds, the flag returns to the middle.

We have instrumented the game to run simulated games using the embedded AI players (bots). Bots are implemented as finite state machines whose states identify basic actions (e.g., fight, swim). Bot squads can organise themselves in smaller teams pursuing higher level tasks (e.g., defend own base, get flag, attack enemy base). We trained two LCRFs on 30 minutes of data sampled every 2 seconds on a game played by two squads of 10 players each. For the first LCRF

3 See http://openarena.ws for more information.

we labelled each subject with a teammate, whereas for the second we labelled each subject with the corresponding team activity. The results are based on three-fold cross validation.

Team recognition

The team recognition performance is based on a comparison between the recognised teams and the ground truth at each time step. Given that team-recognition produces pairs of subjects and their probability of belonging to the same team, we need to reconstruct teams from these pairs. We order the subject pairs by decreasing probability, then we greedily group pairs into teams by merging pairs with common subjects according to the ordering. We order the recognised and actual teams by size, then we evaluate the average precision and recall. Given P = {recognised team members}, M= {actual teammembers}, Precision=|P ∩M|/|P| and Recall=|P ∩M|/|M|. The results are shown in Table 2, for different sizes of the observation windowW.

For W = 0 (no window) the model is similar to a HMM, because all features linked to label transitions (e.g., velocity, acceleration) are not considered. This results in a lower recall. The recall increases sharply as soon as the window opens. Precision and recall do not show large variations with respect to the window size, but they tend to decrease as the window size increases. This means that a shorter window better captures team dynamics than a longer one. When the window size grows, increasingly old observations become less relevant and degrade the model performance. Note also that the number of times it is necessary to recompute the window for the incremental forward-backward (W reset) decreases as the window size increases. Considering a larger window probably allows the linear system solver to perform better.

Activity recognition

Although bots can still perform different basic actions when in the same team, we are interested in recognising the higher level team activities. Therefore, we trained the activity-recognition LCRF by labelling each teammate with the corresponding team-level activity. The label set is B = {attack enemy's base, stay at own base, patrol own base, get flag, recover flag when lost, bring flag to enemy's base}. We then evaluated the LCRF on the average number of correct label assignments using different window sizes. Results are shown in Table 3, for different sizes of the observation windowW.

Given that the probability of randomly guessing a subject's activity is 16.67%, the model performs better than chance, but not extremely well. Activities are probably challenging to recognise using the features we introduced in Section 4 because they depend on that subject's raw position; for example capturing the flag often happens in the middle of the map, and the location of the bases offers a good indication about whether a subject is attacking or defending. There is, as before, a sharp improvement in the performance when W > 0 and a slight decrease as the window size increases.

6 Conclusion

In this paper we introduced a probabilistic model to perform incremental team composition and activity recognition on a stream of observations. We evaluated the model on spatiotemporal traces collected from artificial players acting in a highly dynamic environment. The model performed reasonably well when recognising team composition, whereas performance for activity recognition is not very conclusive. In the future, we shall investigate in more detail whether it is possible to improve the activity recognition performance. Finally, we plan to evaluate the performance of our model on traces collected during a simulation with human subjects.