🚀 go-pugleaf

                                PhD. Defense
                               Curry I. Guinn
                       Department of Computer Science
                              Duke University

                    10:30am, Monday, September 12, 1994.
                   D243, Levine Science Research Center,
                              Duke University

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


                                   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 (cite below). 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 mechanisms.  

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.   


N. A. Kartram and Wilkins, D. E., "Toward a foundation for evaluating AI
planners", Artificial Intelligence for Engineering Design, Analysis and
Manufacturing, 4(1):1-13, 1990.