Plan, Activity, and Intent Recognition (eBook)

Theory and Practice

Hung Hai Bui, Christopher Geib, Robert P. Goldman, David Pynadath, Gita Sukthankar (Herausgeber)

eBook Download: PDF | EPUB

2014 | 1. Auflage
424 Seiten
Elsevier Science (Verlag)
978-0-12-401710-8 (ISBN)

Infos

Plan recognition, activity recognition, and intent recognition together combine and unify techniques from user modeling, machine vision, intelligent user interfaces, human/computer interaction, autonomous and multi-agent systems, natural language understanding, and machine learning. Plan, Activity, and Intent Recognition explains the crucial role of these techniques in a wide variety of applications including: - personal agent assistants - computer and network security - opponent modeling in games and simulation systems - coordination in robots and software agents - web e-commerce and collaborative filtering - dialog modeling - video surveillance - smart homes In this book, follow the history of this research area and witness exciting new developments in the field made possible by improved sensors, increased computational power, and new application areas. - Combines basic theory on algorithms for plan/activity recognition along with results from recent workshops and seminars - Explains how to interpret and recognize plans and activities from sensor data - Provides valuable background knowledge and assembles key concepts into one guide for researchers or students studying these disciplines

Textauszug

Chapter 1

Hierarchical Goal Recognition

Nate Blaylocka and James Allenb,    aNuance Communications, Montreal, QC, Canada, bFlorida Institute for Human and Machine Cognition, Pensacola, FL, USA

Abstract

This chapter discusses hierarchical goal recognition: simultaneous online recognition of goals and subgoals at various levels within an HTN-like plan tree. We use statistical, graphical models to recognize hierarchical goal schemas in time quadratic with the number of the possible goals. Within our formalism, we treat goals as parameterized actions, necessitating the recognition of parameter values as well. The goal schema recognizer is combined with a tractable version of the Dempster-Shafer theory to predict parameter values for each goal schema. This results in a tractable goal recognizer that can be trained on any plan corpus (a set of hierarchical plan trees). Additionally, we comment on the state of data availability for plan recognition in general and briefly describe a system for generating synthetic data using a mixture of AI planning and Monte Carlo sampling. This was used to generate the Monroe Corpus, one of the first large plan corpora used for training and evaluating plan recognizers. This chapter also discusses the need for general metrics for evaluating plan recognition and proposes a set of common metrics.

Keywords

Plan recognition

Goal recognition

Activity recognition

Plan corpus

Plan recognition metrics

Plan recognition evaluation

Acknowledgments

This material is based on work supported by a grant from DARPA under grant number F30602-98-2-0133, two grants from the National Science Foundation under grant numbers IIS-0328811 and E1A-0080124, ONR contract N00014-06-C-0032, and the EU-funded TALK project (IST-507802). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views any of these organizations.

1.1 Introduction

Much work has been done over the years in plan recognition which is the task of inferring an agent’s goal and plan based on observed actions. Goal recognition is a special case of plan recognition in which only the goal is recognized. Goal and plan recognition have been used in a variety of applications including intelligent user interfaces [6,18,20], traffic monitoring [26], and dialog systems [13].

For most applications, several properties are required in order for goal recognition to be useful, as follows:

 Speed: Most applications use goal recognition “online,” meaning they need recognition results before the observed agent has completed its activity. Ideally, goal recognition should take a fraction of the time it takes for the observed agent to execute its next action.

 Precision and recall: We want the predictions to be correct (precision), and we want to make correct predictions at every opportunity (recall).

 Early prediction: Applications need accurate plan prediction as early as possible in the observed agent’s task execution (i.e., after the fewest number of observed actions). Even if a recognizer is fast computationally, if it is unable to predict the plan until after it has seen the last action in the agent’s task, it will not be suitable for online applications; those need recognition results during task execution. For example, a helpful assistant application needs to recognize a user’s goal early to be able to help. Similarly, an adversarial agent needs to recognize an adversary’s goal early in order to help thwart its completion.

 Partial prediction: If full recognition is not immediately available, applications often can make use of partial information. For example, if the parameter values are not known, just knowing the goal schema may be enough for an application to notice that a hacker is trying to break into a network. Also, even though the agent’s top-level goal (e.g., steal trade secrets) may not be known, knowing a subgoal (e.g., gain root access to server 1) may be enough for the application to act. (Our approach enables both types of partial prediction.)

In our work, we model goals, subgoals, and actions as parameterized action schemas from the SHOP2 HTN planner [23]. With this formalism, we can distinguish between recognition of a goal schema and its corresponding parameter values. The term instantiated goal recognition means the recognition of a goal schema together with its parameter values. Additionally, we consider the task of hierarchical goal recognition, which is the recognition of the chain of the agent’s currently active top-level goal and subgoals within a hierarchical plan. As an illustration, consider Figure 1.1; it shows a hierarchical plan tree and a corresponding set of goal chains for left-to-right execution.

Figure 1.1 A hierarchical plan and corresponding goal chains.

Here, the root of the tree () is the agent’s top-level goal. Leaves of the tree () represent the atomic actions executed by the agent. Nodes in the middle of the tree represent the agent’s various subgoals within the plan. For each executed atomic action, we can define a goal chain which is the subgoals that were active at the time it was executed. This is the path that leads from the atomic action to the top-level goal . We cast hierarchical goal recognition as the recognition of the goal chain corresponding to the agent’s last observed action.

Recognizing such goal chains can provide valuable information not available from a system that recognizes top-level goals only. First, though not full plan recognition, which recognizes the full plan tree, hierarchical goal recognition provides information about which goal an agent is pursuing as well as a partial description of how (through the subgoals).

Additionally, the prediction of subgoals can be seen as a type of partial prediction. As mentioned before, when a full prediction is not available, a recognizing agent can often make use of partial predictions. A hierarchical recognizer may be able to predict an agent’s subgoals even when the top-level goal is still not clear. This can allow a recognizer to make predictions much earlier in an execution stream (i.e., after less observed actions).

The remainder of this chapter first discusses previous work in goal recognition. We then detail the need for annotated data for plan recognition and present a method for generating synthetic labeled data for training and testing plan recognizers. This is followed by a discussion of how best to measure plan recognition performance among a number of attributes. We then describe our own hierarchical goal recognizer and its performance. Finally, we conclude and discuss future directions.

1.2 Previous Work

We focus here exclusively on previous work on hierarchical goal recognition. For a good overview of plan recognition in general, see Carberry [14].

Pynadath and Wellman [27] use probabilistic state-dependent grammars (PSDGs) to do plan recognition. PSDGs are probabilistic context-free grammars (PCFGs) in which the probability of a production is a function of the current state. This allows, for example, the probability of a recipe (production) to become zero if one of its preconditions does not hold. Subgoals are modeled as nonterminals in the grammar, and recipes are productions that map those nonterminals into an ordered list of nonterminals or terminals. During recognition, the recognizer keeps track of the current productions and the state variables as a Dynamic Bayes Network (DBN) with a special update algorithm. The most likely string of current productions is predicted as the current hierarchical goal structure.

If the total state is observable, Pynadath and Wellman claim the complexity of the update algorithm to be linear in the size of the plan hierarchy (number of productions).1 However, if the state is only partially observable, the runtime complexity is quadratic in the number of states consistent with observation, which grows exponentially with the number of unobservable state nodes.

Additionally, the recognizer only recognizes atomic goals and does not take parameters into account. Finally, although the PSDGs allow fine probability differences for productions depending on the state, it is unclear how such probability functions could be learned from a corpus because the state space can be quite large.

Bui [10] performs hierarchical recognition of Markov Decision Processes. He models these using an Abstract Hidden Markov Model (AHMM)—multilevel Hidden Markov Models where a policy at a higher level transfers control to a lower level until the lower level “terminates.” The addition of memory to these models [11] makes them very similar to the PSDGs used by Pynadath in that each policy invokes a “recipe” of lower-level policy and does not continue until the lower level terminates.

Recognition is done using a DBN, but because this is intractable, Bui uses a method called Rao-Blackwellization (RB) to split network variables into two groups. The first group, which includes the state variables as well as a variable that describes the highest terminating state in the hierarchy, is estimated using sampling methods. Then, using those estimates, exact inference is...

Produkt-Details

• Erscheint lt. Verlag: 3.3.2014
• Sprache: englisch
• Themenwelt: Informatik ► Software Entwicklung ► User Interfaces (HCI)
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• ISBN-10: 0-12-401710-X / 012401710X
• ISBN-13: 978-0-12-401710-8 / 9780124017108