Modeling Communication in a Graph Comparison Task

Michael Matessa
Department of Psychology
Carnegie Mellon University
Pittsburgh, PA  15213
+1 412 268 8115
matessa@cmu.edu

John Anderson
Department of Psychology
Carnegie Mellon University
Pittsburgh, PA  15213
+1 412 268 3438
ja0s+@andrew.cmu.edu

ABSTRACT
This paper describes a preliminary attempt to incorporate theories of communication (Clark & Schaefer, 1989; Poesio & Traum, 1998) into a general cognitive architecture (Anderson & Lebiere, 1998) as a first step in creating an interactive problem solving system.  A restricted interface for a communicative task will be introduced that will allow the system to interact with subjects.  An empirical study of paired subjects will be presented that compares the restricted interface to an unrestricted interface, and model predictions will be compared to the results of this study.  Finally, conclusions and future directions will be discussed.
COMMUNICATION TASK
Communication is usually motivated by the desire to complete a certain task.  To begin our modeling efforts, we were interested in a simple two-participant task where both participants have the same abilities and unique knowledge to be communicated.  
We created a two-dimensional task where subjects are given parts of a graph with the goal of creating a whole graph.  The graphs are colored circles connect by lines (similar to those used by Levelt (1982) to study communicative reference) and are designed so that similar colors on the parts can overlap and form a larger graph.  We are interested in communication using text, so the subjects send messages by way of a chat window from two different computers.  In addition to creating a whole graph from two parts, subjects also have the goal of confirming each of the circles.  This is done by each subject selecting one circle at a time -- if the circles are the same, their score is increased, but if the circles are different, the score is decreased.  This confirmation goal gives an objective measure of task performance in terms of a score, and it allows for the use of more complicated dialogue acts such as requesting that the other person confirm a circle or committing to confirming a circle.  
We are not interested in modeling the processing of unrestricted English syntax but in modeling the higher-level communicative acts accomplished with English.  So we eventually intend for our model to interact with people with a restricted set of English phrases.  Our restricted interface allows the composition of a text message by first choosing a topic of discussion and dialogue act to address the topic.  A fixed grammar template can then be filled in with menu-selected word choices.  
A preliminary model was created that can participate in the graph completion task. The predictions of this model that are compared to subject data are that the obligation to answer questions will be followed (Info-request dialogue acts will be followed by Answer dialogue acts) and that requests for confirmation will be grounded before the confirmation is acted on (Action-directive dialogue acts by the speaker will be followed by Agreement dialogue acts by the listener before confirmation actions by the speaker are made).
EXPERIMENT
Of fourteen total pairs, one pair in each of the unrestricted and restricted conditions were unable to complete the task in the hour provided.  To compare task performance between the unrestricted and restricted interface conditions, the number of turns to complete the task, the time to complete the task, and the final score were measured.  There was no significant difference in the number of turns (t=0.798), time (t=0.1551), or final score (t=1.185).  
The conceptual content of the two conditions was also examined, and it was found that subjects made use of all the content expressible by the restricted interface, but that the restricted interface did not allow some content expressed by subjects using the unrestricted interface.  This content included statements and questions regarding the completion of presentation of information, statements and questions of number of circles in specific rows and columns, requests and commitments to add circles, and sequential plans to confirm circles.  
To examine model predictions, paired dialogue acts in the two conditions were examined.  The model predicts that all Info-request dialogue acts will be followed by Answer dialogue acts.  This prediction is supported by the data, where in both restricted and unrestricted interface conditions, 97% of Info-request dialogue acts were followed by Answer dialogue acts.  The model also predicts that confirmation Action-directive dialogue acts will be followed by Agreement dialogue before confirmation actions are made.  This prediction is supported in the restricted interface condition, where 95% of the confirmation Action-directive dialogue acts were followed directly by explicit Agreement acts (a text message) or implicit Agreement acts (confirmation of the circle by the other subject).  In the unrestricted interface condition,  only 54% of the Action-directive acts were followed directly by explicit or implicit Agreement acts.  Part of the reason for this low number is that 70% of these Action-directive acts occurred after an explicit plan had been made on the sequence of circles to be confirmed.  This planning was not supported by the restricted interface or the model.
CONCLUSIONS
Since subjects’ performance in the graph completion task (as measured by score, turns to completion, and time to completion) was not significantly different between the restricted and unrestricted interface conditions, the restricted interface seems to be an appropriate tool in studying this task. For subjects using this restricted interface, the ACT-R model was successful in its predictions of the obligation to answer questions and of waiting for an Agreement dialogue act before confirming circles.  For subjects using the unrestricted interface, the model was only successful in its prediction of the obligation to answer questions.  Most subjects using the unrestricted interface who did not wait for agreement before confirming circles had previously agreed on a sequential plan to confirm circles, and this strategy was not supported in the restricted interface or the model.  Subjects using this strategy apparently assume their reference to a particular circle and their decision to confirm that circle will be acceptable to their partner because of their previous plan.  This strategy, as well as other concepts and abilities found in the unrestricted interface, can be incorporated into the restricted interface and the model in future work.
REFERENCES
Anderson, J. R.,  & Lebiere, C. (1998). The Atomic Components of Thought. Hillsdale, Mawhaw, NJ: Erlbaum.
Clark, H. H., & Schaefer, E. F. (1989). Contributing to discourse. Cognitive Science, 13, 259-294.
Core, M. G., & Allen, J. F. (1997). Coding dialogs with the DAMSL scheme. In Working Notes of the AAAI Fall Symposium on Communicative Action in Humans and Machines, Boston, MA. AAAI.
Poesio, M. & Traum, D. (1998). Towards an Axiomatization of Dialogue Acts, In J. Hulstijn and A. Nijholt (eds.), Proceedings of the Twente Workshop on the Formal Semantics and Pragmatics of Dialogues (13th Twente Workshop on Language Technology), Enschede, pp., 207--222, May 1998.