In a collaborative planning environment in which the agents are autonomous and heterogeneous, it is inevitable that discrepancies in the agents' beliefs result in conflicts during the planning process. In such cases, it is important that the agents engage in collaborative negotiation to resolve the detected conflicts in order to determine what should constitute their shared plan of actions and shared beliefs. This paper presents a plan-based model for conflict detection and resolution in collaborative planning dialogs. Our model specifies how a collaborative system should detect conflicts that arise between the system and its user during the planning process. If the detected conflicts warrant resolution, our model initiates collaborative negotiation in an attempt to resolve the conflicts in the agent's beliefs. In addition, when multiple conflicts arise, our model identifies and addresses the most effective aspect in its pursuit of conflict resolution. Furthermore, by capturing the collaborative planning process in a recursive Propose–Evaluate–Modify cycle of actions, our model is capable of handling embedded negotiation during conflict resolution.
In collaborative planning, the participants are often autonomous and heterogeneous;
thus, it is inevitable that con#icts arise among them. For example, some agents may have
more extensive and accurate domain knowledge than other agents, and knowledge about
the circumstances of a particular planning task may be more readily available to some
agents than to others. Thus, there are discrepancies in the agents' beliefs that may result
in con#icts among the agents as they collaborate on constructing a plan. In order for the
collaborative planning process to proceed as smoothly as possible, the agents must be
able to detect these con#icts as soon as they become evident, and attempt to resolve them
in the most e$cient and e!ective manner. As a result, the agents will engage in
collaborative negotiation subdialogs to resolve the discrepancies in their beliefs. We follow
Sidner (1994) in referring to these subdialogs as collaborative negotiation subdialogs
because the agents are working cooperatively to reach an agreement regarding the issue
in dispute. In particular, collaborative negotiation subdialogs have the following features:
(1) the agents are open and honest with one another, (2) the agents do not insist on
winning an argument and may change their beliefs if convincing evidence is presented to them, and (3) the agents are interested in sharing beliefs with one another to determine
whether their own beliefs should be revised. Such negotiation di!ers from argumentation
(Birnbaum, Flowers & McGuire, 1980; Reichman, 1981; Cohen, 1987; Quilici, 1992;
Maybury, 1993) and other kinds of negotiation, such as labor negotiation (Sycara, 1989),
in that the participants are not trying to enforce their views on one another or to
maximize their own bene"ts, but rather are trying to share their individual knowledge
and beliefs in order to determine what really is best for the agents as a group (Chu-
Carroll & Carberry, 1995c).
The following dialog segment, taken from a transcript of naturally occurring dialogs
between travel agents and customers (SRI Transcripts, 1992), illustrates a collaborative
negotiation subdialog to resolve a con#ict between two agents:
(1) C: I talked to C.D. again, about going from Hong Kong to Moscow.
(2) He made me feel like there had to be some other options besides going through
Heathrow.
(3) ¹: Ok.
(4) C: ¹here had to be several di+erent cities you can go through like Beijing, to Helsinki,
there has to be some options.
(5) ¹: Ok well, what I do is ask for connections available and that1s what I1m getting is
through Heathrow.
(6) C: Ok, so if somebody was in some other city and wanted to go toMoscow there has to
be other options doesn1t there?
(7) ¹: Oh I see what you mean, departing from a di+erent city rather than Hong Kong.
(8) C: >eah.
(9) ¹: Oh sure.
In this dialog, T and C share a common goal*to construct the best plan for C to travel
from Hong Kong to Moscow. T and C have previously constructed a plan in which
C will travel from Hong Kong to Moscow by way of Heathrow Airport in London.
However, in utterance (2), C expresses his belief that an alternative plan to traveling by
way of London must exist, and in (4), provides his reasons for holding this belief. In
utterance (5), T justi"es her con#icting belief that going through London is the only
available plan by explaining to C how this plan was obtained. In (6), C again
insists on his original belief that other options exist and provides a di!erent
reason to support it. Finally in utterance (7), T con"rms C's reason provided in (6) and in
utterance (9) accepts C's belief that an alternative plan must exist. Thus, utterances (5)}(9)
in this dialog constitute a collaborative negotiation subdialog for the purpose of
squaring away the agents' con#ict about whether or not an alternative to their original
plan exists.
Although many researchers have developed systems that respond to user queries
(McKeown, 1985; Paris, 1988; Sene!, Hirschman & Zue, 1991; Maybury, 1992; Moore
& Paris, 1993; Cawsey, 1993; van Beek, Cohen & Schmidt, 1993, Logan, Reece, Cawsey,
Galliers & Jones, 1994; Raskutti & Zukerman, 1994), with the exception of Logan et al.
(1994), they either do not consider possible disagreements between the system and the
user, or assume that the user will always accept the system's point of view when con#icts
arise. However, our analysis of collaborative planning dialogs shows that con#icts between agents are not always resolved immediately; instead, extended collaborative
negotiation subdialogs, such as the dialog segment in utterances (5)}(9), occur quite
frequently. Thus, it is important that a collaborative system be able to engage in such
negotiation subdialogs in a manner that will result in the con#icts being resolved
naturally and e$ciently.
We have implemented a plan-based system, COn#ict REsolver (CORE), for con#ict
detection and con#ict resolution during collaborative planning activities. Given a user
proposal, CORE evaluates the proposal based on its private knowledge and is able to
detect con#icts regarding both the validity and optimality of the proposed plan as well as
con#icts about the truth of proposed beliefs. In situations where a detected con#ict
warrants resolution, CORE initiates negotiation subdialogs with the user to resolve the
relevant con#ict. In cases where multiple con#icts are detected, CORE is capable of
selecting the most e!ective aspect to address in its pursuit of con#ict resolution using its
private domain beliefs and its model of the user's beliefs. Furthermore, by capturing the collaborative planning process in a recursive Propose}Evaluate}Modify cycle of actions,CORE is able to handle embedded negotiation during con#ict resolution.
In order for an agent to successfully collaborate with other agents in developing a plan to achieve a goal, she must be capable of dealing with situations in which con#icts occur.
Con#ict detection requires that an agent evaluate proposals based on her private beliefs,
while con#ict resolution involves communication among agents for the purpose of squaring away the detected con#icts. This paper has presented a plan-based model that speci"es how a collaborative agent should detect and attempt to resolve con#icts that arise during collaborative planning. Our model provides an overall framework for modelling such activity by capturing collaborative activities in a recursive Propose }Evaluate}Modify cycle of actions. Instead of slavishly accepting proposals made by the executing agent, our system evaluates a proposal based on its private beliefs about the domain and about the executing agent in order to determine the validity and optimality of the proposed plan and the truth of the proposed beliefs. In situations where a relevant con#ict is detected, our system initiates a collaborative negotiation subdialog in an attempt to resolve the con#ict. Our mechanism for con#ict resolution identi"es, in cases where multiple con#icting beliefs exist, the focus of modi"cation based on its predicted success in resolving the con#ict about the rejected top-level proposed belief,thus leading the agent to engage in e!ective and e$cient dialogs. In cases where an
agent's "rst attempt to resolve a con#ict fails, our model will allow the agent to apply the
same con#ict detection and resolution methods to the other agent's new proposal,
resulting in an embedded negotiation subdialog captured by recursive meta-plans. In
addition, our model accounts for why questions are sometimes never answered even in
the most cooperative of environments.The authors would like to thank Candy Sidner, Stephanie Elzer, Kathy McCoy, Lance Ramshaw,and Suzanne Mannes for their helpful comments and discussions, David Traum and the anonymous reviewers for their comments on an earlier draft of this paper, and Rachel Sacher for her help in the implementation of CORE. This material is based upon work supported by the National Science Foundation under Grant No. IRI-9122026.
