A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL -- able to express interval temporal networks -- together with the non-temporal logic F -- a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.

Virtual and robotic agents must be able to understand "communicative acts" (utterances, gestures, controlled facial expressions etc.) if they are to interact and collaborate with humans. For researchers in AI, HCI, HRI and related fields, automatic comprehension of communicative acts has turned out to be a very tough nut to crack. Drawing on recent research from cognitive science and evolutionary psychology, the paper argues that an insufficient conceptualization of "context" is at the heart of this problem, and that we should focus on very simple, non-linguistic communicative acts (pointing gestures etc.) in order to investigate how agents can comprehend communicative acts in realistic contexts. I propose a tripartite model of context which is informed by experimental research on how humans recognize objects (via "affordances"), causal relations among objects, and the collaborative activities of fellow-humans. The model is not a formal one, but detailed enough to help in the development of comprehension algorithms in future research.

The collaboration between a human and a robot is here understood as a learning process mediated by the instructor prompt behaviours and the apprentice collecting information from them to learn a plan. The instructor wears the Gaze Machine, a wearable device gathering and conveying visual and audio input from the instructor while executing a task. The robot, on the other hand, is eager to learn both the best sequence of actions, their timing and how they interlace. The cross relation among actions is specified both in terms of time intervals for their execution, and in terms of location in space to cope with the instruction interaction with people and objects in the scene. We outline this process: how to transform the rich information delivered by the Gaze Machine into a plan. Specifically, how to obtain a map of the instructor positions and his gaze position, via visual slam and gaze fixations; further, how to obtain an action map from the running commentaries and the topological maps and, finally, how to obtain a temporal net of the relevant actions that have been extracted. The learned structure is then managed by the flexible time paradigm of flexible planning in the Situation Calculus for execution monitoring and plan generation.

Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach.

Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. In this paper, we formalize MAPR using a basic model that explicates the cost of abduction in single agent plan recognition by "flattening" or decompressing the (usually compact, hierarchical) plan library. We show that single-agent plan recognition with a decompressed library can be solved in time polynomial in the input size, while it is known that with a compressed (by partial ordering constraints) library it is NP-complete. This leads to an important insight: that although the compactness of the plan library plays an important role in the hardness of single-agent plan recognition (as recognized in the existing literature), that is not the case with multiple agents. We show, for the first time, that MAPR is NP-complete even when the (multi-agent) plan library is fully decompressed. As with previous solution approaches, we break the problem into two stages: hypothesis generation and hypothesis search. We show that Knuth's ``Algorithm X'' (with the efficient ``dancing links'' representation) is particularly suited for our model, and can be adapted to perform a branch and bound search for the second stage, in this model. We show empirically that this new approach leads to significant pruning of the hypothesis space in MAPR.

Low-level direct commanding of space robots can be time consuming or impractical for complex systems with many degrees of freedom. My research will adaptively raise the level of interaction between the operator and the robot by (1) allowing the robot to learn implicit plans by detecting patterns in the interaction history, and (2) enabling the human to demonstrate continuous motions through teleoperation. Learned tasks and plans are recorded for future use. I introduce a novel representation of continuous actions called parameterized probabilistic flow tubes that I hypothesize will more closely encode a human's intended motions and provide flexibility during execution in new situations. I also introduce the use of planning for plan recognition in the domain of hybrid tasks.

In this paper we explore challenges related to the engineering of plan libraries for plan recognition. This is an often overlooked problem, yet essential in the design of any real world plan recognizers. We mainly discuss challenges related to the evaluation of equivalence between plan libraries. We explain why this is a potential source of ill-conceived plan libraries. We consider an existing well-established probabilistic plan recognizer as vehicle for our discussion, using the formalism of probabilistic hierarchical task networks to represent plans. We propose avenues for exploring solutions to those challenges within that framework.

Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. Recently, we have introduced a model for MAPR with a flat library structure, to study the complexity of basic MAPR, and also possibly its extensions in the future. Interestingly, this model makes fewer assumptions than existing models, and hence is more general. Therefore, as no existing algorithm would apply to this model, we have developed an hypothesis generation algorithm for this model, and adapted Knuth's Algorithm X for branch and bound search in the resulting hypothesis space. In this paper, we establish the time complexity of hypothesis generation in this model, propose and evaluate 3 different bounding criteria, and also empirically study the dependence of runtimes (hypothesis generation, and search times separately) on the model parameters.

In Real-Time Strategy (RTS) video games, players (controlled by humans or computers) build structures and recruit armies, fight for space and resources in order to control strategic points, destroy the opposing force and ultimately win the game. Players need to predict where and how the opponents will strike in order to best defend themselves. Conversely, assessing how the opponents will defend themselves is crucial to mounting a successful attack while exploiting the vulnerabilities in the opponent's defence strategy. In this context, to be truly adaptable, computer-controlled players need to recognize their opponents' behaviour, their goals, and their plans to achieve those goals. In this paper we analyze the algorithmic challenges behind behaviour recognition in RTS games and discuss a generic RTS behaviour recognition system that we are developing to address those challenges. The application domain is that of RTS games, but many of the key points we discuss also apply to other video game genres such as multiplayer first person shooter (FPS) games.

Previous work on the YAPPR plan recognition system provided algorithms for translating conventional HTN plan libraries into lexicalized grammars and treated the problem of plan recognition as one of parsing. To produce these grammars required a fixed bound for any loops within the grammar and a presented a problem for optional actions within HTN plans. In this work we show that well known transformations from formal language theory can be used to rewrite the plan grammars to remove these limitations on the plan libraries.