TL;DR
This paper proposes a novel approach to generating concise and effective natural language descriptions of complex plans by modeling the hearer's plan reasoning capabilities. Instead of simply listing plan components, the system generates partial descriptions that leverage the hearer's ability to infer the full plan, thereby avoiding information overload and improving communication efficiency.
What Problem Does This Paper Address?
Generating natural language descriptions of complex plans is challenging because simply listing all the steps can lead to overly verbose and ineffective communication. Existing systems often struggle with the sheer volume of detail required for realistic plans, either by dealing with simplified artificial plans or by producing descriptions that are too long. The core problem is determining what information to include in a plan description to make it understandable and useful for the hearer, without overwhelming them or providing too little detail, which could lead to misinterpretation. This paper tackles the problem of selecting an appropriate subset of plan components to describe, ensuring the hearer can reconstruct the intended plan efficiently.
Methods
The paper introduces a computational model that views plan description interpretation as a "refinement search" through a space of partial plans. The speaker's system models the hearer's plan reasoning process, considering the hearer's plan preferences and resource limitations.
- Plan Representation: Plans are represented using a plan-space search framework, where nodes represent partial plans and arcs represent refinement operations (e.g., adding a step). This aligns with how hierarchical planning systems operate.
- Hearer Model: The hearer's interpretation process is modeled as a search within this plan space. This model incorporates:
- Planning Algorithm: Specifically, a partial-order, causal-link planner (DPOCL) is used, which supports hierarchical plan representations.
- Search Limit Function: This models the hearer's resource constraints, limiting the depth or breadth of their search.
- Plan Ranking Function: This function evaluates and ranks partial plans based on the hearer's preferences.
- Description Generation: The speaker's system uses this hearer model to anticipate how the hearer will complete a partial description. The goal is to select a subset of plan components that, when presented to the hearer, will lead them to reconstruct a plan that is both acceptable to the speaker and identifiable within the hearer's limited reasoning capabilities. The paper emphasizes finding a minimal set of constraints that achieve this.
Datasets
Not discussed in the paper. The paper uses a hypothetical "travel from London to Paris" domain for illustrative examples.
Key Insights and Ideas
- Description as a "Hint": The core idea is that a good plan description doesn't need to be exhaustive. Instead, it acts as a "hint" or a partial plan that guides the hearer's own planning process to the intended solution.
- Modeling the Hearer is Crucial: Effective communication hinges on understanding the recipient's cognitive processes, specifically their planning abilities, preferences, and limitations.
- Balancing Detail: There's a sweet spot for detail. Too much detail can eliminate acceptable alternative plans or overtax the hearer. Too little detail can lead to ambiguity or an inability to find the correct plan.
- Plan-Space Search as a Unifying Framework: Using plan-space search as the underlying model allows the approach to be applicable to various planning systems and representations.
- Minimal Descriptions for Efficiency: The paper advocates for finding the smallest set of descriptive constraints that still achieve the communication goal, aligning with Gricean maxims of quantity.
Key Results
The paper presents qualitative results through three example descriptions for a "travel from London to Paris" scenario:
- Description 1 (Too Much Detail): Leads to a plan space with only one solution (the source plan), making it acceptable but overly specific and potentially eliminating other valid, acceptable plans.
- Description 2 (Insufficient Detail): Leads to a plan space where the hearer's limited resources (search depth < 5 nodes) result in only unacceptable plans being found, making the description unacceptable.
- Description 3 (Appropriate Detail): This description leads to a partial plan that, when completed by the hearer, results in a plan space containing only acceptable plans (#8 and #9 in the example graph), and it is identified as a minimal description.
Limitations and Future Work
- Computational Cost: The brute-force method for finding minimal descriptions is computationally expensive, especially for complex plans.
- Uniqueness of Descriptions: The minimal description search might yield multiple equally valid descriptions, and the paper suggests heuristics (like referential coherence) for choosing among them.
- Future Work:
- Investigating additional forms of constraints (e.g., negative imperatives).
- Extending the model to multi-agent dialogue for coordinating plan-related beliefs.
- Developing techniques for reconciling differences between the speaker's model of the hearer and the hearer's actual reasoning.
Summary updated