Understanding Plan Ellipsis

Diane J. LitmanAAAI 1986

Abstract

This paper introduces a unified framework for resolving "plan ellipsis"—incomplete utterances that cannot be understood through linguistic context alone. By modeling conversation as a series of discourse plans acting upon domain-specific goals, the system can infer a speaker's hidden intentions. This approach allows for the resolution of fragments even in the absence of direct linguistic antecedents, moving beyond traditional substitution-based methods.

Introduction

In natural conversation, speakers rarely communicate in complete, standalone sentences. Instead, they rely heavily on fragments and ellipses. Traditional Natural Language Processing (NLP) systems of the mid-1980s primarily handled ellipsis through linguistic substitution: if a user asked "Trains to Ottawa?" and followed with "Montreal?", the system would swap the destination in the previous query.

However, this method fails in two critical scenarios:

  1. Initial Fragments: When a dialogue begins with a fragment (e.g., "Trains to Ottawa?"), there is no prior sentence to serve as a template.
  2. Plan-based Ellipsis: When a fragment modifies an underlying goal rather than a specific word. For instance, if a passenger asks "How about Wednesday?" after learning about a train schedule, they are not replacing a word in the clerk's sentence; they are modifying their own travel plan.

Diane Litman addresses these challenges by proposing a system that utilizes pragmatic knowledge—understanding the speaker's plans and goals—to fill in these communicative blanks.

Methodology: Domain and Discourse Plans

The proposed framework integrates two distinct layers of knowledge:

  • Domain Plans: These represent the task-specific actions, such as TAKE-TRAIN-TRIP, which includes sub-steps like selecting a train, buying a ticket, and boarding.
  • Discourse Plans (Meta-plans): This is the paper's core innovation. These domain-independent plans model how individuals manage a conversation. Examples include INTRODUCE-PLAN (starting a topic), MODIFY-PLAN (changing a parameter), and IDENTIFY-PARAMETER (clarifying details).

By decoupling the "what" (the domain task) from the "how" (the discourse management), the system becomes highly flexible. The discourse plans remain consistent regardless of whether the topic is travel, medical diagnosis, or technical support.

The Resolution Process

Ellipsis resolution involves a multi-stage plan recognition algorithm:

  1. Surface Act Recognition: The system parses an utterance into a "Surface-NP" (e.g., "Wednesday").
  2. Forward Chaining: The system chains upward from the surface act to a speech act (like a REQUEST), then to a discourse plan (like MODIFY-PLAN), and finally links it to a domain plan (like TAKE-TRAIN-TRIP).
Figure 1: The system recognizes an initial fragment by chaining from a surface noun phrase to an INTRODUCE-PLAN discourse act.
  1. Plan Stack Management: The system maintains a stack of active and suspended plans to track dialogue context, using "coherence heuristics" to prefer interpretations that logically extend or modify the current plan.
  2. Linguistic Cues: The framework incorporates "clue phrases" (e.g., "how about") to prioritize specific discourse plans, such as plan modification, over simple topic shifts.

Key Results and Insights

The paper demonstrates the system's logic through qualitative traces. It successfully interprets the opening fragment "Trains going from here to Ottawa?" by inferring the TAKE-TRAIN-TRIP domain plan. Furthermore, it resolves "How about Wednesday?" as a MODIFY-PLAN act, recognizing "Wednesday" as a temporal parameter that replaces a default value in the passenger's travel plan—even if that default was never explicitly mentioned.

Figure 2: Resolving plan ellipsis through the MODIFY-PLAN discourse plan, allowing the system to update parameters of a travel goal.

This proves that ellipsis resolution is often a search problem through a "plan space" rather than a string-manipulation problem in "text space."

Limitations and Future Work

The system's effectiveness depends on a pre-defined library of domain plans; recognition fails if the user's goal is unknown to the system. Additionally, searching deep hierarchies of meta-plans can be computationally expensive. Future research directions include expanding discourse plans to handle complex subdialogues, such as "debugging" a plan when a user's goal is impossible (e.g., "There are no trains on Wednesdays").

Summary updated

BibTeX
@inproceedings{litman1986understanding,
  author = {Diane J. Litman},
  title = {{Understanding Plan Ellipsis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure