The negotiation planner is quite simple, since it does little more than prepend a game tree to the domain level plan. There is a set of act generators, each of which supplies a set of alternatives at each choice node. They are:
The game tree is constructed recursively. There is a function that calls each of the generators. Each generator returns a set of edges corresponding with acts, and the function gathers these to form a choice node. Each generator recursively calls the function to obtain the remainder of the game tree. At each choice node, a special act is used to end the negotiation and begin the domain-level plan. This represents the possibility that either agent could choose to end the negotiation at any time and begin execution of the domain-level plan.
The belief revision module is called as the game tree is constructed. This prevents the planner from doing things like asking the same question many times.
One important issue with the negotiation planner, more so than with the problems given in chapter 4 is the branching factor of the game tree. The tell generator produces as many alternatives as there are beliefs in the belief set, and the propose generator produces as many alternatives as there are choice nodes in the domain-level game tree. For even small problems, dozens of alternatives could be produced. The recombination planner would not be of much use here since, for example, a tell act on a proposition can occur as an alternative at each step of the negotiation (see the discussion of the conditions for recombination to be of use, Section 3.4.9). A form of heuristic search, (Section 3.4.9) would be much more useful. For the heuristic, the utility of the domain-level plan can be used by calling the evaluation function of the domain-level planner, in the context of the revised belief model, and subtracting the cost of the negotiation acts in the path. A beam search would be a good way to perform the heuristic search since the complexity of the search would then be guaranteed to be linear with the plan depth.
The negotiation planner provides much the same game tree that the use of the STRIPS rules would have, but without the flexibility of being able to add new rules. In particular, generators for non-cooperative dialogues have not so far been specified. The request act is also unavailable, but both pragmatic forms of ask are available.
A description of the implementation of the negotiation planner is given in the appendix.