Possessing a sufficient level of situation awareness is essential for effective decision making in dynamic environments. In video games, this includes being aware to some extent of the intentions of the opponents. Such high-level awareness hinges upon inferences over the lower-level situation awareness provided by the game state. Traditional plan recognizers are completely passive processes that leave all the initiative to the observed agent. In a situation where the opponent's intentions are unclear, the observer is forced to wait until further observations of the opponent's actions are made to disambiguate the pending goal hypotheses. With the plan recognizer we propose, in contrast, the observer would take the initiative and provoke the opponent, with the expectation that his reaction will give cues as to what his true intentions actually are.

Plan recognition is a form of abductive reasoning that involves inferring plans that best explain sets of observed actions. Most existing approaches to plan recognition and other abductive tasks employ either purely logical methods that donot handle uncertainty, or purely probabilistic methods thatdo not handle structured representations. To overcome these limitations, this paper introduces an approach to abductive reasoning using a first-order probabilistic logic, specifically Markov Logic Networks (MLNs). It introduces several novel techniques for making MLNs efficient and effective for abduction. Experiments on three plan recognition datasets showthe benefit of our approach over existing methods.

This paper extends existing plan recognition research to handle plans containing loops. We supply an encoding of plans with loops for recognition, based on techniques used to parse lexicalized grammars, and demonstrate its effectiveness empirically. To do this, the paper first shows how encoding plan libraries as context free grammars permits the application of standard rewriting techniques to remove left recursion and ε-productions, thereby enabling polynomial time parsing. However, these techniques alone fail to provide efficient algorithms for plan recognition. We show how the loop-handling methods from formal grammars can be extended to the more general plan recognition problem and provide a method for encoding loops in an existing plan recognition system that scales linearly in the number of loop iterations.

This paper presents a plan recognition algorithm for inferring student behavior using virtual science laboratories. The algorithm extends existing plan recognition technology and was integrated with an existing educational application for chemistry. Automatic recognition of students’ activities in virtual laboratories can provide important information to teachers as well as serve as the basis for intelligent tutoring. Student use of virtual laboratories presents several challenges: Students may repeat activities indefinitely, interleave between activities, and engage in exploratory behavior using trial-anderror. The plan recognition algorithm uses a recursive grammar that heuristically generates plans on the fly, taking into account chemical reactions and effects to determine students’ intended high-level actions. The algorithm was evaluated empirically on data obtained from college students using virtual laboratory software for teaching chemistry. Results show that the algorithm was able to (1) infer the plans used by students to construct their models; (2) recognize such key processes as titration and dilution when they occurred in students’ work; (3) identify partial solutions; (4) isolate sequences of actions that were part of a single error.

One drawback with using plan recognition in adversarial games is that often players must commit to a plan before it is possible to infer the opponent's intentions. In such cases, it is valuable to couple plan recognition with plan repair, particularly in multi-agent domains where complete replanning is not computationally feasible. This paper presents a method for learning plan repair policies in real-time using Upper Confidence Bounds applied to Trees (UCT). We demonstrate how these policies can be coupled with plan recognition in an American football game (Rush 2008) to create an autonomous offensive team capable of responding to unexpected changes in defensive strategy. Our real-time version of UCT learns play modifications that result in a significantly higher average yardage and fewer interceptions than either the baseline game or domain-specific heuristics. Although it is possible to use the actual game simulator to measure reward offline, to execute UCT in real-time demands a different approach; here we describe two modules for reusing data from offline UCT searches to learn accurate state and reward estimators.

In this paper we describe a software assistant agent that can proactively assist human users situated in a time-constrained environment to perform normative reasoning--reasoning about prohibitions and obligations--so that the user can focus on her planning objectives. In order to provide proactive assistance, the agent must be able to 1) recognize the user's planned activities, 2) reason about potential needs of assistance associated with those predicted activities, and 3) plan to provide appropriate assistance suitable for newly identified user needs. To address these specific requirements, we develop an agent architecture that integrates user intention recognition, normative reasoning over a user's intention, and planning, execution and replanning for assistive actions. This paper presents the agent architecture and discusses practical applications of this approach.

Given its ubiquity, scale and complexity, few problems have created the combined interest of so many unrelated areas as the evolution of cooperation. Using the tools of evolutionary game theory, here we address, for the first time, the role played by intention recognition in the final outcome of cooperation in large populations of self-regarding individuals. By equipping individuals with the capacity of assessing intentions of others in the course of repeated Prisoner's Dilemma interactions, we show how intention recognition opens a window of opportunity for cooperation to thrive, as it precludes the invasion of pure cooperators by random drift while remaining robust against defective strategies. Intention recognizers are able to assign an intention to the action of their opponents based on an acquired corpus of possible intentions. We show how intention recognizers can prevail against most famous strategies of repeated dilemmas of cooperation, even in the presence of errors. Our approach invites the adoption of other classification and pattern recognition mechanisms common among Humans, to unveil the evolution of complex cognitive processes in the context of social dilemmas.

Multi-Agent Plan Recognition (MAPR) seeks to proposed to formalize MAPR with a new model, revealing identify the dynamic team structures and team behaviors the distinction between the hardness of single and multi-agent from the observed activity sequences (team plan recognition, and solve MAPR problems in the model using traces) of a set of intelligent agents, based on a a first-cut approach, provided that a fully observed team library of known team activity sequences (team trace and a library of full team plans were given as input plans). Previous MAPR systems require that team [Banerjee et al., 2010]; etc. traces and team plans are fully observed. In this Despite the success of previous approaches, they either assume paper we relax this constraint, i.e., team traces and that agents in the same team can only execute a common team plans are allowed to be partial. This is an important activity, i.e., coordinated activities of agents are not allowed task in applying MAPR to real-world domains, in a team, or require that the team trace and team plans are since in many applications it is often difficult complete, i.e., missing values (activities that are missing) are to collect full team traces or team plans due not allowed. In many real-world applications, however, it is to environment limitations, e.g., military operation.

Recent years are seeing an increasing need for on-line monitoring of teams of cooperating agents, e.g., for visualization, or performance tracking. However, in monitoring deployed teams, we often cannot rely on the agents to always communicate their state to the monitoring system. This paper presents a non-intrusive approach to monitoring by 'overhearing', where the monitored team's state is inferred (via plan-recognition) from team-members' routine communications, exchanged as part of their coordinated task execution, and observed (overheard) by the monitoring system. Key challenges in this approach include the demanding run-time requirements of monitoring, the scarceness of observations (increasing monitoring uncertainty), and the need to scale-up monitoring to address potentially large teams. To address these, we present a set of complementary novel techniques, exploiting knowledge of the social structures and procedures in the monitored team: (i) an efficient probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting knowledge of the team's social behavior to predict future observations during execution (reducing monitoring uncertainty); and (iii) monitoring algorithms that trade expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any number of agents and their different activities to be represented in a single coherent entity. We present an empirical evaluation of these techniques, in combination and apart, in monitoring a deployed team of agents, running on machines physically distributed across the country, and engaged in complex, dynamic task execution. We also compare the performance of these techniques to human expert and novice monitors, and show that the techniques presented are capable of monitoring at human-expert levels, despite the difficulty of the task.

In this paper, we present a method for recognising an agent's behaviour in dynamic, noisy, uncertain domains, and across multiple levels of abstraction. We term this problem on-line plan recognition under uncertainty and view it generally as probabilistic inference on the stochastic process representing the execution of the agent's plan. Our contributions in this paper are twofold. In terms of probabilistic inference, we introduce the Abstract Hidden Markov Model (AHMM), a novel type of stochastic processes, provide its dynamic Bayesian network (DBN) structure and analyse the properties of this network. We then describe an application of the Rao-Blackwellised Particle Filter to the AHMM which allows us to construct an efficient, hybrid inference method for this model. In terms of plan recognition, we propose a novel plan recognition framework based on the AHMM as the plan execution model. The Rao-Blackwellised hybrid inference for AHMM can take advantage of the independence properties inherent in a model of plan execution, leading to an algorithm for online probabilistic plan recognition that scales well with the number of levels in the plan hierarchy. This illustrates that while stochastic models for plan execution can be complex, they exhibit special structures which, if exploited, can lead to efficient plan recognition algorithms. We demonstrate the usefulness of the AHMM framework via a behaviour recognition system in a complex spatial environment using distributed video surveillance data.