Example problem

To aid in describing the operation of the planner, a simple example is used. In this example, a goal act ask-pair is used by the first agent to ask a question. The first agent executes the first act in the decomposition, ask, and expects the second agent to parse the plan and produce the response reply. Reply can be further decomposed to either of tell-true or tell-false. tell-true has a precondition that the agent believes the proposition, whereas tell-false has the precondition that the agent believes the negation of the proposition. The STRIPS rules for this problem are as follows:

name:           ask-pair
parameter:      P
precondition:   {}
effects:        {}
decompostion:   { ask(P); reply(P) }

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

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

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

To build the game tree (figure 3.2), the agent starts with the goal of ask-pair. It decomposes this in a focussed fashion, using the level 1 plan rules, finishing with a terminal node ask. Since this is the only way to decompose ask-pair, it forms the only strategy at the root node of the game tree (see figure 3.2). To generate the second level of the game tree, the planner starts with the node ask. Since this constitutes a full parse tree, it adds a parent, using the intention rules at level 2. The probability distribution of the candidate parents is obtained. There is in fact only one candidate, ask-pair. This is connected to the root of the tree, forming a tree of two nodes, with ask-pair as the parent and ask as the child. Now using the beliefs at level 2, leftmost searching obtains ask-pair as the first focussed non-full node. reply is then added. Since this is a non-terminal act, it is decomposed further. There are two children that can be added - tell-true and tell-false. Since each has a precondition whose value is uncertain, the planner must insert a chance node before the choice node. The acting agent's belief set spawns a pair of belief sets, each corresponding with the outcome of its belief about the proposition at the chance node. As result, the planner produces the alternatives tell-true and tell-false. These spawned belief sets are propagated through the following subtrees since the acting agent's belief needs only be checked once. This prevents further chance nodes being inserted.

Figure 3.2: Game tree for a question and answer