Statistical Goal Recognition

Home | People | Projects | Publications | Resources


Plan recognition is the general problem of inferring an agent's plan(s) and goal(s) by observing its actions. Goal recognition is a special type of plan recognition in which we only attempt to recognize the agent's goal(s).

Plan and goal recognition have been used in a number of applications including user modeling, system intrusion detection, intelligent software help systems, and, the area we are most interested in, natural language understanding.

The goal of our work is to produce a goal recognizer which

  • performs online recognition, i.e., makes a prediction after every observation
  • is computationally fast - fast enough to be done in real time
  • makes early predictions, i.e., is able to predict the goal after just a few observations
  • makes partial predictions when unable to predict the full goal
  • is domain independent
  • is easily portable to new domains
  • is robust to replanning by the agent

Our Basic Approach

We use machine learning techniques to predict the most likely goal after each observation. A goal consists of its schema and parameter values, all of which need to be predicted to make a full prediction. We separate the processes of goal schema and parameter recognition, and then find the most probable combination. The recognizer can make partial predictions by not predicting some or all of the parameter values (when it is not sure enough to predict them).

Plan Corpora

We estimate goal schema and parameter value probabilities using a plan corpus - a labeled corpus of goals and then actions an agent executed to achieve them. Obtaining a labeled corpus is difficult in the plan recognition domain, and very few exist.

We describe here two corpora we have gathered.

Human Corpus: The Linux Plan Corpus

Following the Unix Corpus, gathered by Neal Lesh at the University of Washington, we gathered the Linux Plan Corpus. Linux users at the University of Rochester were given a Linux goal (such as "find a file that ends in .tex") and then their Linux commands were recorded as they attempted to accomplish it.

The corpus consists of 457 successful plan sessions with 19 goal schemas. On average, a session consisted of 6.2 actions.

More details and download

Artificial Corpus: The Monroe Plan Corpus

In most domains, obtaining a labeled corpus from humans is infeasible or impractical. In fact, even an unlabeled corpus would be difficult to get in many domains, since observing actions would require e.g., an advanced computer vision system to recognize actions. We propose a method of artificially creating corpora using an AI planner. Given a plan library for a domain, we stochastically choose a goal and generate a start state. Using a modified version of the SHOP2 Planner, we randomly generate a valid plan for the goal and start state. This process can be iterated to generate a corpus of any desired size. Using this process, we have created an artificial corpus for the Monroe domain - a disaster management domain. It contains 5000 plan sessions and 10 goal schemas with an average of 9.6 actions per session.

More details and download

Current projects

These are the extensions we are currently working on:
  • Hierarchical goal recognition: we are looking at ways to recognize not only the top-level goal, but also all current subgoals.
  • Replanning: the assumption that an agent first creates an entire plan and then subsequently executes it without problem is untrue in all but the simplest of worlds. In reality, things go wrong during execution, causing agents to constantly replan. We are looking at ways to make the goal recognizer more robust to replanning.

Current Researchers

Publications

  • Nate Blaylock and James Allen. Fast hierarchical goal schema recognition. In Proceedings of AAAI-06, Boston, July 2006. [pdf]

  • Nate Blaylock and James Allen. Hierarchical instantiated goal recognition. In AAAI Workshop on Modeling Others from Observations (MOO-2006), Boston, July 2006. [pdf]

  • Nathan J. Blaylock. Towards Tractable Agent-based Dialogue. PhD thesis, University of Rochester, Dept. of Computer Science, August 2005. [pdf]

  • Nate Blaylock and James Allen. Generating artificial corpora for plan recognition. In Liliana Ardissono, Paul Brna, and Antonija Mitrovic, editors, User Modeling 2005, number 3538 in Lecture Notes in Artificial Intelligence, pages 179-188. Springer, Edinburgh, July 24-29 2005. [pdf]

  • Nate Blaylock and James Allen. Recognizing instantiated goals using statistical methods. In Gal Kaminka, editor, Workshop on Modeling Others from Observations (MOO-2005), pages 79-86, Edinburgh, July 30 2005. [pdf]

  • Nate Blaylock and James Allen. Statistical goal parameter recognition. In 14th International Conference on Automated Planning and Scheduling (ICAPS'04), Whistler, British Columbia, June 3-7 2004. [pdf]

  • Nate Blaylock and James Allen. Corpus-based, statistical goal recognition. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-2003), pages 1303-1308, Acapulco, Mexico, August 9-15 2003. The published version contained errors in the reported results. This is the corrected version. [pdf]


Last change: 8 Jun 2006 by blaylock