Modelling Variations in Goal-Directed Dialogue 
Jean Carletta* 
University of Edinburgh 
Depa.rtment of Artificial Intelligence 
jcc~aipna.ed.ac.uk 
1 Introduction 
This research investigates human dialogue variations by 
having simulated agents converse about a simple map 
navigation task using a computational theory of human 
dialogue strategies. The theory to be tested is that 
agents have a variety of strategies which they use in 
goM-directed dialogue for deciding what information to 
include, how to present it, how to construct references, 
and how to handle interactions. Agents choose strate- 
gies for each of these a.speets of the dialogue depend- 
ing on the complexity of the current task, responses 
from the partner, and the task's importance; in general, 
agents try to minimize the collaborative effort spent on 
the task but still complete it satisfactorily. The soft- 
ware allows simulated agents to be constructed using 
any combination of strategies, showing how the strate- 
gies interact and allowing the decisions made in human 
dialogues about the same task to be modelled. Cur- 
rently, the system works on a subset of the strategies 
found in Shadbolt \[6\], but a corpus of human dialogues 
is being studied to construct, an improved theory of di- 
alogue strategies, and these strategies will be incorpo- 
rated into later versions of the system. 
2 The Dialogue Domain 
The task domain \['or the dialogues involves navigating 
around a simple map containing approximately fifteen 
landmarks. Two participants are given maps which dif- 
fer slightly; each map may contain some features omit- 
ted on the other, and features in the same location on 
the two maps may have different labels. The first par- 
ticipant also has a route from the labelled start point to 
one map feature. The second participant must draw the 
* Supported by a scholarship from the Marshall Aid Conunem- 
oration Commission. Thanks to Chris Mellish for supervising me 
and Alison Cawsey for helpful comments, 
route on his or her map. In this task, the participants 
must cooperate because neither of them knows enough 
about the other's map to be able to construct accurate 
descriptions. At the same time, small changes in the 
map test how participants hrmdle referential ambigui- 
ties, how information is carried from one part of the 
dialogue to the next, and when agents decide to replan 
rather than repair an existing plan. Despite the possi- 
bilities for referential difficulties, this task minimizes the 
use of real world knowledge as long as all participants 
understand how to navigate. The task is simple enough 
to be completed in computer-simulated dialogue, but 
admits the dialogue variations to be tested in the re- 
search. 
3 The Central Idea 
The central idea behind the research is that agents need 
multiple strategies for engaging in goM-directed dia- 
logue because they do not necessarily know the best 
way to communicate with a given partner. Self \[5\] shows 
that dialogue is crucial where neither agent has all of the 
relevant domain knowledge. Dialogue is also necessary 
for any explanations where agents don't have accurate 
models of their partners \[3\]. Even if agents have all 
of the relevant domain knowledge, they may not know 
how best to present that knowledge, especially since 
explanations are about exactly that part of the task 
which is not mutually known to the dialogue partners 
\[1\]. Shadbolt \[6\] presents evidence that humans han- 
dle uncertainties about what information to give and 
how to present it by having a set of strategies for each 
aspect of the dialogue. Then the agent can tailor ex- 
planations to a particular partner by using the strategy 
that best fits the situation. For instance, human agents 
who believe that much domain information will have to 
be communicated structure their presentation carefully 
and often elicit feedback from the partner, like partici- 
pant A of Sha.dbolt's \[6\] example 6.16: 
A: have you got wee palm trees aye? 
B: uhu 
A: right go just + a wee bit along to them have 
you got a swamp? 
n~ er 
A: right well just go + have you got a watt> 
fall7 
Al,~ents who believe that most domain in\[brmation is 
ki~own to their partner are more likely to rely on inter- 
ru ptions fl'om the partner and replanning, a.s in example 
6.:i 1: 
and "around". The agents converse in an artificial lan- 
guage resembling their shared planning language, but 
substituting referring expressions for internal feature 
identifiers. Under these constraints, the agents use di- 
alogue strategies to decide on the content and form of 
the dialogue. The existing system is a prototype de-. 
signed to show that incorporating such strategies can 
explain some variations in human dialogue and make 
agents more flexible. An improved set of strategies is 
being extracted from the corpus of human dialogues. 
The end result of the project will be a theory of how 
communicative strategies control variations in dialogue, 
and software in which computer-simulated agents use 
these strategies to complete the navigation task. 
A: and then q- go up about and over the bridge 
B: I've not got a bridge I've got a lion's den 
and a wood 
A: have you got a river'? 
Ol~e way to make computer generated explanations look 
m(,re natural is to plan them using strategies modelled 
on ~.he human ones. Although strategies like these could 
be built into the way a system plans an explanation, 
making strategy choices explicit allows the strategies 
themselves to be investigated, providiug a way to test 
oul. how variatio,~s affect the ensuing dialogue. The 
go~d of the present research is both to show how us- 
ing dialogue strategies can improve tile "naturalness" 
of computer-generated task explanations and to pro- 
vide insight into the dialogue strategies which humans 
use and how they interact. 
4 The Project 
The project involves creating a theory of human dia- 
logist strategies a.m:l modelling it. usiug two cotnputer 
processes that converse. Communication for the com- 
i)llter agents, bg~sed or~ the model in Power \[4\] and 
I\[oughtou \[2\], is simplified in a number of ways. A 
convener wakes the agents in turn and interactions are 
made by placing messages in mailboxes, leaving out the 
complications of turn-taking and interruptiom Rather 
than reason from "visual" images of the maps, agents 
begin with sets of beliefs about the positional relation- 
ship.~ among objects and share knowledge about both 
dialogue conventions, expressed a.s interactio'n flames 
\[2\], ~md navigational concel)tS like "toward", "between", 
5 The Program 
The current version of the software uses dialogue strate- 
gies adapted from Shadbolt \[6\]. tte lists seven dif~ 
fercnt aspects of dialogue along which strategies may 
be developed. Agents may vary strategies tbr feedback 
(how they handle the partner's utterances), speciJicao 
lion (how they construct and resolve referring expres- 
sions), o~lology (how they decide from what features 
are available how to construct route descriptions), foe~zs 
(the amount of explMt focus intbrmation given), differ- 
once (the effort spent determining what the partner's 
utterances mean), decenlering (whether intbrmation is 
presented using the agent's or the partner's names tbr 
fe.atures), and hypolhesi~ formalion (the effort spent 
making hypotheses about the partner's knowledge). 
Agents choose strategies tbr each of these aspects de- 
pending on how explicit they want to be, which in turn 
depends on how likely the partner is to misunderstand 
each aspect of the dialogue. Some of Shadbolt's as- 
pects are interrelated; for instance, agents that provide 
explicit information about the current focus do not need 
to construct referring expressions as carefully as agents 
who provide no focusing information at all. Our own 
work divides the strategies slightly differently so that 
they ea.n be divided into sets depending on whether 
they atfect planning the dialogue interaction, planning 
the content, planning the presentation, or realizing ref- 
erences; the goal is to make the strategies ms modular 
as possible so that they can be modelled simply. Each 
simulated agent takes on a set of strategies for tile dura- 
tion of' a dialogue. Currently, the prototype varies how 
much intbrmation about tile structttre of the dialogue is 
explicitly given, which features are included in a route 
description depending on a model of the partner's be- 
325 
liefs, how often an agent allows interactions from the 
partner, and how much repair an agent is willing to 
do rather than replan a description. The agents also 
use heuristics to prefer plans where the partner already 
understands the plan's prerequisites. The output of the 
program is a simulated dialogue where each agent keeps 
the same strategies for the course of the dialogue; an 
obvious future step is to allow agents to adapt to a 
particular partner or part of the task by varying their 
strategies within a dialogue. 
6 Examples 
The system currently has several strategies which affect 
how much structuring information is given in a dialogue 
and how often feedback is elicited from the partner. The 
following dialogue, an English gloss of two simulated 
agents conversing, shows how agent A might act if it 
believed that the maps had many differences: 
A: I'nl going to tell you how to get to the 
buried treasure. I'm going to tell you how 
to navigate the first part of the route. Do 
you have a pahn beach? 
B: Yes. 
A: Do you have a swamp? 
B: No. 
A: Do you have a waterfall? 
B: Yes. 
A: The swamp is between the pMm beach and 
the waterfall. OK? 
B: Yes. 
A: The route goes to the left of the pMm beach 
and around the swamp. OK? 
B: Yes. 
If agent A believes that there will be few misunderstand- 
ings, or that B will understand enough to say what it 
misunderstood, it might choose to give information first 
and repair afterwards: 
7 Conclusion 
The theory and program are designed to show how varb 
ations that occur in human dialogue can be ex.plained in 
terms of deciding among communicative strategies gov- 
erning the form of interaction, the content and presenta- 
tion of information, and the construction of referring ex- 
pressions. The strategies found by examining a human 
corpus of goM-directed dialogues are implemented in a 
dialogue system where two computer processes using an 
artificial language and simplified turn-taking complete 
the task. This approach is useful in itself for determin- 
ing what makes human dialogues seem natural} but it 
also has implications for human-computer interaction, 
since it is one step towards making computer dialogues 
with humans operate flexibly to fit in with human ex- 
pectations. 
A: The route goes to the left of the pahn beach 
and around the swamp. OK? 
B: Where's the swamp? 
A: The swamp is between the pMm beach and 
the waterfall. OK? 
B: Yes. 

References 

S. Garrod. Explanations in dialogues as attempts to 
overcome problems in coordination. In Proceedings 
of the Third Alvey Explanation Workshop, Septem- 
ber 1987. 

G. IIoughton. The Production of Language in Di- 
alogue: A Computational Model. PM) thesis, Uni- 
versity of Sussex, April 1986. 

J. Moore and W. Swartout. A reactive approach to 
explanation. In Proceedings of the I~'ouvth Interna- 
tional Workshop on Nat~tral Language Generation, 
1988. 

1L J. D. Power. A Computer Model of Conversation. 
PhD thesis, University of Edinburgh, 1974. 

J. Self. Bypassing the intractable problem of stu- 
dent modelling. In Intelligent Tutoring Systems, 
1988. 

N. 1{. Shadbolt. Constit~tting reference in naluraI 
language: the problem of referential opacity. PhD 
thesis, Edinburgh University, 1.984. 
