For the algorithm to work correctly, the time
spent in metalevel thinking must be small compared to the time it
takes to do an actual node expansion and propagation of a new solution
(i.e. a *PE*(*t*,*l*)). Otherwise, the agent is probably better off
choosing nodes to expand at random without spending time considering
which one might be better.

A node expansion involves the creation of a new matrix *M*. If we
assume that there are *k* agents and each one has *n* possible
actions, then the number of elements in the matrix will be
. Each one of these elements represents the utility of the
situation that results after all the agents take their actions. In
order to calculate this utility, it is necessary to simulate the new
state that results from all the agents taking their respective actions
(i.e. as dictated by the element's position in the matrix) and then
calculate the utility, to some particular agent, of this new situation
(see Figure 5). The calculation of this utility can be an
arbitrarily complex function of the state, and must be performed for
each of the elements in the matrix.

**Figure 5:** A very simplified version of the Pursuit Problem with only 3
agents and in a 4 by 4 grid. Given the old situation, each one of the
elements of the matrix corresponds to the payoff in one of the many
possible next situations. There is one for each combination of moves
the agents might take (e.g. North, East, Idle). Sometimes, the moves of
the predators might interfere with each other. The predator calculating
the matrix has to resolve these conflicts when determining the new
situation, before calculating its utility.

The next step is the propagation of the expected strategy. If we
replace one of the ZK leaf strategies by some other
strategy, then the time to propagate this change all the way to the
root of the tree depends both on the distance between the root and
leaf, and the time to propagate a strategy past a node. Because of the
way strategies are calculated, it is almost certain that any strategy
that is the result of evaluating a node will be a pure
strategy. If all the children
of a node are pure strategies, then the strategy the node evaluates to
can be found by calculating the maximum of *n* numbers. In other
words, the k-dimensional matrix collapses into a one-dimensional
vector. If *c* of the children have mixed strategies, we would need to
add numbers and find the maximum partial sum. In the worst
case, *c*=*k*-1, so we need to add numbers.

We can conclude that propagation of a solution will require a good
number of additions and max functions, and these must be performed for
each leaf we wish to consider. However, these operations are very
simple since, in most instances, the propagation past a node will
consist of one *max* operation. This time is small,
especially when compared to the time needed for the simulation and
utility calculation of different possible situations. A more
detailed analysis can only be performed on an application-specific
basis, and it would have to take into account actual computational
times.

** Next:** Implementation Strategies
**Up:** Algorithm
** Previous:** Algorithm

jmvidal@umich.edu

Sun Mar 10 12:52:06 EST 1996