Cooperative Plan Identification: Constructing Concise and Effective Plan Descriptions

AAAI 1999

TL;DR

This paper introduces the Cooperative Plan Identification (CPI) architecture, a computational model that generates concise and effective natural language descriptions of AI-generated plans. By modeling communication as a cooperative effort, CPI aims to provide descriptions that are just detailed enough for a human to reconstruct the intended plan, leading to significantly fewer errors and better goal achievement in task execution compared to direct translation methods.

What Problem Does This Paper Address?

When intelligent agents create plans to guide actions, they often need to communicate these plans to humans. However, AI-generated plans can be extremely detailed, containing far more information than a human typically needs or can easily process. Simply listing all plan components results in overly verbose and ineffective instructions. This paper addresses the challenge of automatically generating concise and effective plan descriptions that adhere to Grice's maxim of Quantity – saying "no more and no less than what is needed." The core problem is bridging the gap between the detailed internal representation of a plan and the human need for efficient, understandable communication.

Methods

The paper proposes the Cooperative Plan Identification (CPI) architecture, a generate-and-test framework.

  • Cooperative Plan Identification (CPI): This architecture models plan description generation as a collaborative process between a speaker (the AI) and a hearer (the human). The goal is to produce a description that is brief but contains enough information for the hearer to reconstruct the original plan, considering the hearer's limited reasoning resources and plan preferences.
  • Hearer Model: A crucial component is the model of the hearer's interpretation process. This involves a plan reasoning algorithm (DPOCL, a hierarchical planner) that can fill in missing details from a partial description. The model also incorporates:
  • Resource Bounds: A limit on the hearer's computational effort for plan reconstruction.
  • Plan Preferences: The hearer's biases towards certain plan structures.
  • Generator Functions: CPI uses generator functions to create candidate descriptions. Two cooperative algorithms are presented:
  • Local Brevity: This algorithm starts with a complete plan description and iteratively removes components based on heuristics derived from comprehension studies, prioritizing components that are more crucial for understanding.
  • Plan Path: This algorithm follows the path taken by the source planner to construct the original plan, selecting candidate descriptions from this path.
  • Evaluator Function: This function assesses whether a candidate description is "acceptable" by checking if the hearer model can reconstruct a plan sufficiently similar to the source plan within its resource limits. An "optimum" description is the most concise acceptable one.
  • Direct Translation Algorithms (for comparison):
    • Exhaustive Algorithm: Generates a description that includes every component of the source plan.
  • Primitive Algorithm: Generates a description consisting only of the primitive (lowest-level) steps of the plan, ordered temporally.

Datasets

The paper does not introduce new datasets. Instead, it uses four distinct planning problems within a simulated domain (a college campus where subjects ran errands) to generate source plans. These plans were then used to create descriptions via the four algorithms for the empirical evaluation.

Key Insights and Ideas

  • Communication as Cooperation: The fundamental insight is that effective plan description is not just about conveying information, but about doing so cooperatively, anticipating the listener's cognitive load and inferential capabilities.
  • The Importance of "Just Enough" Detail: The research strongly suggests that conciseness, achieved by omitting unnecessary details, is key to effective communication, rather than simply providing all available information.
  • Hearer Modeling is Crucial: Understanding the hearer's reasoning process, including their resource limitations and preferences, is essential for generating descriptions that are truly effective.
  • Generate-and-Test for Efficiency: The CPI architecture's generate-and-test approach, combined with intelligent search strategies (like Local Brevity and Plan Path), provides an efficient way to navigate the vast space of possible plan descriptions.

Key Results

An empirical evaluation involving 24 human subjects performing tasks in a simulated environment demonstrated the superiority of the cooperative techniques:

  • Subjects following instructions generated by the Local Brevity and Plan Path algorithms committed significantly fewer execution errors (SFAIL) and achieved more of their top-level goals (GFAIL) compared to those following instructions from the Exhaustive and Primitive algorithms.
  • The statistical significance for SFAIL was F(3,63) = 7.06 (p < .05) and for GFAIL was F(3,63) = 3.52 (p < .05).
  • The cooperative algorithms did not differ significantly from each other, nor did the direct translation algorithms differ significantly from each other in most comparisons.
  • When results were adjusted for text length, the cooperative techniques still showed superior performance, indicating that their effectiveness is not solely due to producing shorter texts, but rather to the content and structure of the descriptions.

Limitations and Future Work

  • Parameter Tuning: The paper acknowledges that the scaling factors used in the weighting functions (e.g., kp, ke, ka, k₁) are user-specifiable and were set based on empirical estimation. Further experiments would be needed to determine optimal values across different domains.
  • Hearer Model Specificity: While the hearer model is domain-independent, the specific plan preferences used in the experiment were general (preferring shorter, hierarchical plans). More nuanced preference modeling could potentially improve results.
  • Future Work: The authors suggest that the CPI architecture and its underlying principles can be extended to other areas of natural language generation where concise and effective communication is paramount. The success of the cooperative approach opens avenues for further research into how AI systems can better understand and adapt to human cognitive processes in communication.

Summary updated

BibTeX
@inproceedings{1999cooperative,
  title = {{Cooperative Plan Identification: Constructing Concise and Effective Plan Descriptions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure