Acquisition of Abstract Plan Descriptions for Plan Recognition

AAAI 1998

TL;DR

This paper introduces a novel method for automatically learning abstract descriptions of user plans from logged action sequences. This is crucial for building plan recognition systems, especially in domains where detailed prior knowledge is scarce, by enabling the creation of plan libraries without manual expert input.

What Problem Does This Paper Address?

Plan recognition systems are powerful tools for understanding user intent by matching observed actions to a library of known plans. However, a significant bottleneck exists: how do we create this plan library in the first place? This is particularly challenging when developing systems for existing software where domain knowledge isn't readily available, forcing a "reverse-engineering" approach. Manually crafting these plan descriptions is time-consuming and error-prone. This paper tackles the problem of automatically acquiring these abstract plan descriptions from real-world user interaction data.

Methods

The core of the paper lies in an "abstraction mechanism" that takes multiple logged action sequences (assumed to be attempts to achieve the same goal) and finds commonalities to form a generalized plan description.

Here's a breakdown of the key techniques:

  • Action Graph Representation: Each action sequence is transformed into a labeled graph. Nodes represent individual actions (with their types and parameters), and edges capture temporal ordering and structural relationships between action arguments (e.g., one action's output being another's input).
  • Domain Knowledge Integration: The system can optionally leverage domain knowledge, such as object type hierarchies and action type hierarchies, to facilitate abstraction. For instance, it can recognize that "boil_water" and "boil_pasta" both fall under a more general "boil" action.
  • The join Operator: This is the central algorithmic contribution. The join operator takes two action graphs and produces a new graph representing their commonalities. It abstracts action types using a "most specific common abstraction" (msa) function and handles arguments by either keeping constants or introducing new variables with abstracted types. Temporal and structural edges are also joined if their corresponding action nodes can be joined.
  • Abstraction Heuristics (APL+ and APL-): To manage the combinatorial explosion of possible joins, especially with long sequences, the authors propose heuristics. These heuristics aim to find either the most restrictive (APL+) or least restrictive (APL-) abstract plan description. This is achieved by assigning a "degree of restrictiveness" score to each potential abstract action and then greedily building the plan based on these scores. The restrictiveness is quantified by a weighted sum of primitive actions, abstract actions, temporal edges, and structural edges.

Datasets

The paper evaluates its approach on two main datasets:

  • UNIX Domain: Real-world command sequences collected at the University of Washington, featuring up to 24 steps. These sequences were grouped by goal, and the experiments involved joining 8 collections of 11 sequences each, repeated 10 times with randomized input.
  • Cooking World: Artificially generated action sequences based on a "cooking world" library (from Kautz 1991), including basic and abstract goals, and spurious actions. These sequences were shorter, averaging around 7 actions.

Key Insights and Ideas

  • Automating Plan Library Acquisition: The most significant insight is that abstract plan descriptions, crucial for plan recognition, can be learned automatically from observed behavior, reducing the reliance on manual knowledge engineering.
  • Abstraction as Finding Common Ground: The join operator elegantly captures the idea that common elements across multiple instances of a goal-directed behavior reveal the essential structure of the underlying plan.
  • Balancing Specificity and Generality: The APL+ and APL- heuristics highlight the trade-off between creating a plan description that is specific enough to be discriminative and general enough to cover variations in user behavior.
  • Robustness to Noise: The method is shown to be robust to "spurious" or irrelevant actions, as these elements are naturally filtered out when finding commonalities across multiple sequences.

Key Results

  • Feasibility Demonstrated: The proposed abstraction mechanism and heuristics were shown to be feasible and effective on both real-world (UNIX) and artificial (Cooking World) datasets.
  • Near-Optimal Results: Both APL+ and APL heuristics were able to approximate the optimal (most and least restrictive) plan decompositions efficiently. In the Cooking World domain, optimal results were achieved with as few as 4 joins.
  • Quality of Decompositions: The acquired plans were comparable to those presented in prior work (Kautz 1991) for the Cooking World domain, often requiring only 4-10 samples.
  • Robustness to Noise: Experiments showed that adding up to 100% spurious actions had minimal impact on the performance of the heuristics, demonstrating their resilience.
  • Potential for Plan Recognition: Preliminary tests suggest that the acquired plans can be successfully used by a plan recognition system.

Limitations and Future Work

  • Limited Temporal and Control Structures: The current approach primarily handles simple temporal ordering and doesn't explicitly model more complex control structures like loops or conditional execution.
  • Handling of Domain Knowledge: While the system can use domain knowledge, its absence limits abstraction to basic actions and variable replacement.
  • Future Directions: The authors propose extending the work to handle richer temporal relations and control structures. A key future direction is the acquisition of "abstraction relations among plans" to build hierarchical plan libraries. They also aim to further investigate the integration of domain knowledge and explore more sophisticated similarity tests for joining action graphs.

Summary updated

BibTeX
@inproceedings{1998acquisition,
  title = {{Acquisition of Abstract Plan Descriptions for Plan Recognition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure