LINGUIST List 13.2013

Wed Jul 31 2002

Diss: Computational Ling: Guinn "Meta-Dialogue..."

Editor for this issue: Karolina Owczarzak <>


  1. cig, Computational Ling: Guinn "Meta-Dialogue Behaviors..."

Message 1: Computational Ling: Guinn "Meta-Dialogue Behaviors..."

Date: Tue, 30 Jul 2002 14:15:12 +0000
From: cig <>
Subject: Computational Ling: Guinn "Meta-Dialogue Behaviors..."

New Dissertation Abstract

Institution: Duke University
Program: Linguistics Program
Dissertation Status: Completed
Degree Date: 1994

Author: Curry I Guinn 

Dissertation Title: 
Meta-Dialogue Behaviors: Improving the Efficiency of Human-Machine
Dialogue - A Computational Model of Variable Initiative and
Negotiation in Collaborative Problem-Solving

Dissertation URL:

Linguistic Field: Computational Linguistics

Dissertation Director 1: Alan Biermann
Dissertation Director 2: Randall Hendrick
Dissertation Director 3: Don Loveland
Dissertation Director 4: John Reif

Dissertation Abstract: 

This is a study of communication in collaborative problem-solving. We
provide a model of collaboration that integrates natural language
dialogue and multi-agent planning. Agents are assumed to be
autonomous, but they only possess limited knowledge and
capabilities. Although the agents may share the same common goal, they
do not have direct access to their collaborators' knowledge and
plans. Agents must use natural language dialogue to request resources
from other agents, provide assistance to others, coordinate
problem-solving and negotiate conflicts.

Kartram and Wilkins argue that the most important issues for
evaluating single-agent planners are soundness, completeness,
optimality, efficiency and search control [1]. We believe these same
criteria should be used in evaluating multi-agent problem-solvers. In
this thesis, we identify the domain conditions and dialogue behaviors
necessary for soundness and completeness within our model of
collaboration. We provide an account of efficiency and search control
within the model. We show that the dialogue mechanisms of variable
initiative and negotiation vastly improve the efficiency and search
control of the collaborative problem-solving between two agents. We
demonstrate that the benefit of variable initiative and negotiation
mechanisms cannot be realized without proper plan recognition. We show
that a particular class of summarizing statements can enhance plan
recognition and thereby greatly improve the efficacy of these

We examine and verify our model of collaboration using both analytical
and experimental means. We analyze the collaborative model by
presenting an explicit algorithm that each collaborating agent uses
during problem-solving. We call this algorithm the Collaborative
Algorithm. Using this explicit formalism, we can determine the
properties necessary for soundness, completeness and efficiency of the
algorithm. The Collaborative Algorithm has been implemented, and
computer-computer problem-solving experiments have been conducted in
several domains. These experiments validate the conclusions of the
formal analysis. Furthermore, these computer-computer problem-solving
sessions provide a technique for exploring behaviors of the
Collaborative Algorithm that cannot be formally analyzed.
Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue