Introduction
Many
contemporary games use a data-driven approach to control various
aspects of a game. In a racing game, for example, an external file may
be used to specify the values for various physics parameters of a
vehicle, or the behavioral parameters of an AI opponent. Deciding on
values for these parameters can be a difficult task, since a change
made to one parameter value might affect several aspects of behavior.
Although it is sometimes possible to calculate the ideal values
mathematically, in most cases a trial and error approach needs to be
used.
In
this article, I will discuss how we have used the Particle Swarm
Optimization (PSO) algorithm to arrive at good values for both our
physics and AI parameters. The first part of this article provides a
quick overview of function optimization. This is followed by a
discussion of the PSO algorithm, after which I will show how we have
used PSO within our racing game.
Function Optimization
Algorithms
such as PSO and Genetic Algorithms (GA) are generally used on functions
that take several input parameters and return a single output value.
The algorithm aims to find the input values that will generate the
maximum (or minimum) output value, also referred to as the global
optimum, within the valid range of input values. The number of
parameters is referred to as the dimensionality of the function and the
range in which valid input values can be found is referred to as the
search space.
For example, consider the following one-dimensional function:
f(x) = sin(x) + sin(x/2)
Figure
1 shows a plot of the output values for all input values in the range
0.0 to 12.6. From this graph it is clear that the global optimum is
somewhere around x = 11, at one of the low turning points of the function. At about x
= 5.2 there is another low turning point. This is commonly referred to
as a local optimum: an optimum within a sub-range of the global range.
|
|
 |
 |
 |
Figure 1: The graph of the function, sin(x) + sin(x/2), shows clearly the global and local minima.
|
Craig Reynolds's Flocking Model
Many
of us are familiar with the name Craig Reynolds, whose work became the
basis for many simulated swarms in games. Reynolds was intrigued by the
behavior of swarms, such as a flock of birds or school of fish, which
seem to move in a synchronized manner without any central control. He
studied their behavior and came up with a model of their movement, from
which he created a graphical simulation of bird-like objects flying
around (he called them “boids,” from bird-oids). His model consisted of
four steering behaviors: separation to make the boids avoid colliding with one another, alignment to make a boid steer in the common direction of his neighbors, cohesion to make a boid steer towards the common position of his neighbors, and avoidance to make a boid steer away from other obstacles [Rabin 2002].
Particle Swarm Optimization
In
1995, James Kennedy and Russell Eberhart applied Craig Reynolds's model
to the problem of finding optima in a search space, which can be
compared to a flock of birds looking for a food source, and created the
PSO algorithm. They kept the alignment and cohesion behaviors of the Reynolds model, but did away with the behaviors of separation and avoidance.
In
PSO, a collection of particles (called a “swarm”) move around in search
space looking for the best solution to an optimization problem. All
particles have their own velocity that drives the direction they move
in. This velocity is affected by both the position of the particle with
the best fitness and each particle's own best fitness. Fitness refers
too how well a particle performs: in a flock of birds this might be how
close a bird is to a food source, in an optimization algorithm this
refers to the proximity of the particle to an optima.
Each
particle's location is given by the parameters of the given
optimization problem, and a particle moves around in search space by
adapting and changing these parameter values. At each time step, the
particle's fitness is measured by observing the parameter values
(location) of the particle. A particle keeps track of the best position
it has reached so far (called the personal best position), and is also aware of the position of the overall best particle at a certain time step (called the globally best position).
At each time step the particle tries to adapt its velocity (i.e. speed
and direction) to move closer to both the globally best position and
the personal best position, in order to try and improve its fitness.
|
|
 |
 |
 |
Figure 2: This screenshot shows how particles “swarm” towards the global optimum, as indicated by the cross.
|
The PSO Algorithm
The standard PSO algorithm can be summarized as follows [Engelbrecht 2002]:
- Set d equal to the dimension of the fitness function.
- Create n particles, p0 to pn, each with a position vector, x, of dimension d.
- Assign random position values to each particle
- For each particle, pi:
- Evaluate fitness (pass position vector values into fitness function and assign return value as fitness)
- If fitness better than personal best fitness, then assign current position as personal best position (xpbesti)
- If fitness better than global best fitness, then assign current position as global best position (xgbest)
- For each particle, pi:
- Update velocity, vi:
vi (t) = w v i (t-1) + l (xpbesti - xi (t)) + g (xgbest - xi (t))
-
- Update position, xi:
xi (t) = xi (t-1) + vi (t)
- If criteria met, end simulation, else repeat from step 4.
The
criteria for ending the simulation is usually based on whether the
global best fitness is sufficient, or whether the simulation has run
for the maximum amount of epochs (iterations). It is also important to
note that in step 3, the personal best fitness of each particle, and
the global best fitness need to be initialized to very poor values. At
this stage, each particle's velocity is also usually set to zero,
although they may be initialized to random values.
The number of particles, n, inertia weight, w, and the local and global component variables, l and g, are all system parameters of the PSO algorithm. These are discussed next.