Representation of Action Sequences

Once again, the concept of representation is the primary issue to resolve. In this case, we're interested in representing sequences of actions that produce reactive behaviors.

Actions and Parameters

There is clearly a subset of all possible actions that will allow animats to achieve the two behaviors described (see Table 34.1). Limiting the representation to only the actions needed will not only make the development easier, but also speed up the learning. It would be trivial to extend this at a later date if necessary; the genetic algorithm would cope just as well, if a bit slower.

Table 34.1. Limited Set of Actions Used in Each of the Sequences and Their Corresponding Parameters

Action

Parameter

Look

direction

Move

weights

Fire

Jump

The direction parameter is a symbol taking values (up, down, ahead). The weights are used to blend possible moving directions together.

Some actions are given parameters, which means we don't have to use large numbers of parameterless actions. This also separates the concepts of what to do, and how to do it in the representation (which helps the evolution). There are two parameters to explain:

  • Direction is a parameter used by the look action. This is only needed in rocket jumping, and the animat only really needs to look down. For flexibility (and to not make the problem too simple), we'll include the three directions as possible values for this parameter: up, ahead, and down.

  • Weights are used by the move action. Instead of letting the action specify every possible movement, we provide it with a set of default directions chosen as expert features. There are three of them; move away from (1) the projectile, (2) the closest collision point, and (3) the estimated impact location (see Figure 34.1). The genetic algorithm can decide upon arbitrary weights (both positive and negative) to move almost anywhere.

    Figure 34.1. Top-down representation of the three different direction vectors provided to the genetic algorithm. A weighted combination of the three allows almost any point in space to be chosen.

    graphics/34fig01.gif

Now it's just a matter of combining parameters and actions into sequences of actions.

Sequences

Simple arrays are commonly used to represent sequences. However, by using actions as the elements in the array, our sequences have no sense of timing; the actions will be ordered, but no hints about delays are provided.

For this reason, the AI needs to associate each action with a time. There are two ways to do this, using either of the following:

  • A time offset relative to the previous action

  • Absolute timing, based on the start of the sequence

To make this decision, it's necessary to consider how small changes in the representation affect the sequence. Using relative times, changing the timing of one action will have a knock-on effect on the absolute times of all the other actions thereafter. On the other hand, with absolute times, changes to any particular value will be completely independent from the rest of the action times. Because the absolute approach minimizes the interdependencies between variables of the search space, it provides the most flexibility to the genetic algorithm.

As a consequence of global action times, the order of the actions in the array is not important; it's just a form of storage. The first action in the sequence could easily be the last element of the array. There are two different ways to interpret this:

  • It's beneficial for the genetic algorithm to have a loose representation because it will be able to group actions that work well together.

  • The fact that the order of the array is not important implies there are many symmetric solutions; this is the cost of the loose representation. The size of the search space could be reduced by ordering the array of actions by time.

Both of these factors will affect genetic algorithm. Because the problem does not seem too complex, however, we'll settle for the loose representation. The arrays can be ordered after the evolution is over, for efficiency reasons (to avoid scanning the entire array to check the timings of actions).



AI Game Development. Synthetic Creatures with Learning and Reactive Behaviors
AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors
ISBN: 1592730043
EAN: 2147483647
Year: 2003
Pages: 399

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net