Negotiation acts and their pragmatic definition

There are a number of negotiation acts that can reveal an agent's belief state. Selection of an appropriate repertoire of acts was motivated by a number of desirable properties:

• Adequacy The repertoire should be strong enough that it can, if necessary, be used to communicate all of each agent's beliefs, leading to a perfectly correct belief model, and therefore the most efficient plan possible given the agents' capabilities and beliefs about the environment. If this were not possible, there would be something lacking in the expressive power of the repertoire.

• Efficiency Adequacy does not guarantee efficiency, but the acts should communicate as much as possible with the least dialogue cost.

• Necessity The repertoire should not contain unnecessary members. This property might be proved by finding example problems in which one member dominates all of the others. The purpose of this property is to guarantee that the repertoire of acts is divided into basic, orthogonal acts, with no redundancy of expressive ability, therefore obtaining the simplest possible set of acts.

• Realism The repertoire should correspond with the repertoire of negotiation acts seen in corpora of natural language collaborative planning dialogues, so that the expectation of the user's contribution to the dialogue is correct. This allows the planner to generate correct expectations about subsequent turns when the act for the current turn is being chosen. Being able to predict the user's act also implies being able to understand his utterance. The acts chosen by the planner must also be realistic so that the user can generate similar expectations and understand the system.

• Simplicity The negotiation acts should refer to simple expressions of the elements of the agent's mental state. Since the agent's decision rests on the evaluation of game trees using a belief set, the only available candidates are descriptions of beliefs and descriptions of the intentions that come from the evaluation of the game tree. Acts other than these could only express some combination of the elements of the mental state, offering no efficiency gain over the elemental acts. The acts should also have a simple pragmatic form, being definable by STRIPS rules, and therefore requiring no more than the basic forms of belief revision that are already available to the planner.

The selected set of negotiation acts is now specified using STRIPS plan rules. By using STRIPS rules the repertoire can be formally specified and programmed within the plan-rule language of the domain-level planner. The repertoire was chosen by enumerating the different STRIPS rules that could be used for an act. Only two were found, one whose precondition refers to a belief of the agent, and one that refers to its intention. These respectively correspond with informing and proposing types of act. The control structures were also investigated, leading to different ways of assembling subdialogues with these acts. For example, in a question and answer pair, the questioner may intend that the hearer unconditionally answers his question, in which case one control structure is used, or he may intend that the hearer choose between answering his question and something else. The control structures are expressed using different rules of decomposition for the subdialogues. Each of the acts that emerged from this investigation was checked for adherence to the properties listed above.

• pass allows the agent to pass the turn without giving any information. It is defined by the following plan rule:

  name:             pass
  parameter:        {}
  precondition:     {}
  effects:          {}
  decomposition:    {}
  

  Since pass has no preconditions and effects, it has no direct effect, through the belief revision process (Section 3.4.7), on the belief state of the speaker and hearer. However, the dry-land component of the belief revision process may change the belief state, in explaining why the agent chose to say nothing.

• tell-true is used to simply give information that a proposition is valued as true. It is defined by the following plan rule:

  name:             tell-true
  parameter:        P
  precondition:     bel(P)
  effects:          {}
  decomposition:    {}
  

  Since tell-true has a precondition that the speaker believes the proposition, the belief revision process will update the belief at level three, five, and so on.

• tell-false is the complement to tell-true. It is defined by:

  name:             tell-false
  parameter:        P
  precondition:     bel(not(P))
  effects:          {}
  decomposition:    {}
  

• tell can be decomposed to both of tell-true and tell-false, allowing an agent to plan a tell, without knowing at plan-time the belief state of the speaker of the tell.

  name:             tell
  parameter:        P
  precondition:     {}
  effects:          {}
  decomposition:    { [tell-true(P)], [tell-false(P)] }
  

• propose is used by an agent to tell the intention that it has formed as a result of evaluating the game tree. That intention can be about just the next act or it can be tree representing the best play for the game tree. It is defined by:

  name:             propose
  parameter:        P
  precondition:     {intend(P)}
  effects:          {}
  decomposition:    {}
  

  Understanding a propose requires the hearer to apply the dry-land algorithm. The hearer uses the algorithm to search for the simplest belief state in which the speaker would choose the proposed alternative in the domain-level plan. This state must also be one in which the speaker would choose to propose. There is a simpler pragmatic sense for propose, and that is for the hearer to merely prune the game tree at the choice node of the proposed alternative. While it is partly effective, it does not allow the hearer to take advantage by revising beliefs using the dry-land algorithm.

• request is like propose, in that it declares the agent's preference, but it obliges the hearer to adopt the requested intention. It is realised by an act request-pair, whose decomposition has two steps. In the first step, agent 1 makes the request. In the second step, agent 2 executes the requested act.

  name:             request-pair(P)
  parameter:        P
  precondition:     {intend(P)}
  effects:          {}
  decomposition:    { [request(P), P ]}
  

  name:             request(P)
  parameter:        P
  precondition:     {}
  effects:          {}
  decomposition:    {}
  

  The hearer of a request revises his beliefs in a way that is similar to that for a propose. He searches for a state in which the speaker would both choose the requested alternative in the domain-level plan, and in which the speaker would choose a request in the negotiation plan.

• ask

  ask is defined as either a propose to tell, or a request to tell:

  name:           ask-forced
  parameter:      P
  precondition:   {}
  effects:        {}
  decomposition:  { [request(tell(P))] }
  

  name:           ask-autonomous
  parameter:      P
  precondition:   {}
  effects:        {}
  decomposition:  { [propose(tell(P))] }
  

Finally, some plan rules are required that construct a sequence of negotiation acts, and append the domain-level plan. These are:

name:           negotiation-plan
parameter:      {}
precondition:   {}
effects:        {}
decomposition:  { [domain-plan],
                  [negotiation-act, negotiation-plan] }

name:           negotiation-act
parameter:      {}
precondition:   {}
effects:        {}
decomposition:  { [request],
                  [propose],
                  [tell],
                  [pass] }

Lacking any empirical data, it was impossible to find suitable cost values for each of the acts. Instead, estimates were used, with each act valued at ten units, except pass, which due to its empty propositional content, was given a value of four. It was assumed, as it was in chapter 4 (see Sections 4.5.1 and 2.13), that these costs are additive over the dialogue.

utility(pass,-4).
utility(tell-true(_),-10).
utility(tell-false(_),-10).
utility(propose(_),-10).
utility(request(_),-10).

Since these values are estimated, they may not reflect the real performance of the planner very well. However, it was found that the results obtained in the examples of this chapter do not vary much in character given small variations to the estimates.