|
Potential Fields
Potential fields provide such a means of extracting global routing knowledge.
Essentially for every position in the environment there is a direction
that provides the shortest route to the exit. This shortest route is found
by choosing the direction that has the cell with the lowest value (distance).
Potential field generation can be done in different ways, each with varying
success; This is to be covered in the next chapter. For the examples shown
below, each cell has flooded its count with an increment of 1 to all adjacent
cells and sqrt(2) to all diagonal cells. If a new value is flooded to
another cell, the previous value is compared and the lesser of the two
is stored. This recursive flooding gives an approximation to the shortest
Euclidean distance traveled from the exit to any point in the environment
(provided it is reachable). Figure (a) below shows the rings of equidistance
propagating from the exit on the right of the map.
 |
 |
|
(a)
|
(b)
|
Here we see the rings of equal value (distance)
propagating out from the source in (a), and how well potential fields
apply to multiple exits (b). The lines represent contour information.
The potential fields technique also provides a simple way to implement
multiple exits. During the creation of the potential fields, each exit
can be flooded in turn and the resulting values at each point correspond
to the shortest distance to any exit on the map. This routing technique
stays true to human direction finding since it provides the direction
to the closest exit if multiple exits are available. An example of this
is shown in figure (b) above where an extra exit has been added to the
bottom left. A ridge is visible between each exit, this corresponds to
the ridge of equi-distance. For any entity on this ridge, they will non-deterministically
choose either direction.
Perhaps the most powerful aspect of the potential field technique is
in the way it deals with obstacle avoidance. Clearly if a cell contains
an obstacle then the obstacle cell will not flood its neighbours. As simple
as this is, it restricts the propagation of the wave and allows refraction
to occur around obstacles. This is important as it allows us to stop thinking
in terms of `walls' and `obstacles' but to abstract a whole class of things
as obstacles, and reduce the number of states a cell in the environment
can take (i.e. empty, obstacle, pedestrian). This means that walls are
now essentially just a line of obstacles, an example of the effect of
obstacles on a field is shown below.
The wave front diffraction propagates through the environment and simplifies
routing for even the most complex environments.
Since we can now arbitrarily assign what is considered as an obstacle,
we can easily include pedestrians as obstacles. This introduces a whole
array of interesting scenarios, for example: When should pedestrians be
considered as obstacles? If no direct route can be found when pedestrians
are obstacles, what backup field should be used? How does the extra calculation
per timestep effect the simulation performance? Of these questions it
was the time performance issue that made me decide to leave this embellishment
for later research.
Given that we now have a distance map from the optimal exit for each
point we can begin to appreciate the usefulness of this data. Plotting
the distance field in 3D allows us to visually see how this field is used
to extract a direction for each point.
The outward counting done during potential field
generation can be represented as a 3D height field as shown here.
Cleaner ring generation is possible
however the rounder the circle becomes, the more work the CPU must do
to achieve the results. The image above shows a 100*100 cell height map.
|
