In negotiation dialogue information is exchanged between agents that supports their decision about a domain-level plan.The term 'negotiation' is usually taken to mean a discussion that is used to obtain an agreement, often between self-interested parties. Here it is used to mean discussion between fully cooperative parties as well, and the discussion encompasses communication of proposals to agree upon as well as the communication of information that is used to better understand what the best proposal might be. The meta-level planners described in Section 2.6 are used to plan such dialogues, but those planners do not consider the efficiency of the negotiation acts. Instead, they search over the space of domain plans, generating negotiation subdialogues whenever questionable preconditions are encountered. They use logical belief models, and therefore consider and generate dialogue about all potentially valid plans equally, no matter how good those plans might be. Using these planners, one plan whose preconditions are extremely improbable would be just as much a candidate for discussion as one whose preconditions are almost certain to be satisfied. As an extreme example, such planners would consider negotiation about a plan in which a brain surgeon wears a blindfold, considering that it is unlikely yet still possible that the operation will be a success. There may be many such unreasonable candidates, but few reasonable ones. Such planners would therefore fail to negotiate a good domain-level alternative in a reasonable amount of time.
In contrast, an efficient planner for negotiation dialogues will be described in this chapter which discounts for discussion all but the domain plans that have a reasonable chance of success, and only passes information that will significantly improve the quality of those plans. The planner uses a set of negotiation acts, which use as their subject the beliefs and intentions of the speaking agent. Each of the acts has a pragmatic definition in which their meaning is described in terms of preconditions on the agent's mental state, and so can be planned using ordinary plan rules, in the same way as the domain-level plan. These acts constitute a repertoire of acts that are common to dialogue no matter what the subject, for example, a question-answer pair is a very common subplan in all sorts of dialogues. While they can be specified and planned in much the same way as domain-level acts, they should be built in to the planner rather than given in the input file. They should be automatically plannable too, with the agent being free to mix negotiation subdialogues as appropriate with those that are derived from the domain plan rules given by the user.
The negotiation planner is motivated by the sort of problem where two or more agents must coordinate their actions in some plan. For example, a pair of experts may wish to collaborate in routing trains in a transportation network [2], or a team of robots may want to coordinate themselves in constructing a car. In these problems, there is often a "team talk" that precedes execution of that plan, where the team members must establish who is capable of what, which resources are available and what the state of the environment is, how the goal will be decomposed, and how the subtasks will be ordered.
Constructing a negotiation planner requires only minor modification to the existing domain level planner, adding just the facility to add negotiation acts to the game tree. The evaluation module, and the belief revision module remain identical to those described in chapter 3, and the language used in the input files to describe the domain level plan rules is the same as that used previously to describe dialogue plan rules.
In Section 5.2, the principles on which the value of the negotiation acts is based are explained using a simple example. Then, in Section 5.3, formal pragmatic definitions are given for the negotiation acts, using STRIPS plan rules. Section 5.4 argues that these are an appropriate set of acts. Then, Section 5.5 presents examples of each of the negotiation acts, demonstrating that each is a necessary member of the agent's repertoire, and showing how the utility of negotiation acts is sensitive to the probability values of the belief model. The set of negotiation acts is extended in Section 5.6 to include insincere acts as a complement to the sincere acts in settings of self-interest. Finally, the work described in this chapter is compared with similar previous work by Gmytrasiewicz and Durfee [25].