Design and implementation of the negotiation planner

Two paths could have been taken in the design and implementation of the negotiation planner. One was to maximise reuse and code the negotiation acts as STRIPS rules within the input to the domain-level planner. The other path was to maximise efficiency and hard-code the planner. The first approach seemed quite appealing, especially as pass, tell, request and propose have all been defined using STRIPS operators. At first glance, it would seem that merely providing these plan rules would be enough to equip the domain level planner described in chapter 3 for planning negotiation dialogues. However, the parameters of the STRIPS operators need to be instantiated from the belief set and from the game tree, and so something more than plain plan rules is required. As well as this, direct coding of the negotiation planner rather than use of interpreted rules would result in faster construction of the game tree since the planning and plan recognition processes are bypassed. This path was taken for the current implementation.

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:

• pass this returns a pass act

• ask this returns ask acts for all available indefinite beliefs in the speakers belief set

• tell-true this returns tell acts for all of the speaker's positive beliefs that are indefinite to the hearer. The speaker's belief model is consulted to check whether they are indefinite

• tell-false this returns tell acts for all of the speaker's negative beliefs that are indefinite to the hearer. The speaker's belief model is consulted to check whether they are indefinite.

• propose this returns all of the best strategies from all of the choice nodes in the game tree. A call is made to the domain-level planner to obtain the game tree. To identify the choice node whose best strategy is being proposed, the content of the propose may need to identify the path that leads to the choice node. For example one rendering of a propose might be "If you decide to go shopping, then I will mind the children". To keep things simple for the moment, the current implementation only allows proposals to refer to the choice made at the root of the domain-level game tree.

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.