Citizen phil » Flocking. » results

An Investigation Into Computational Flocking Techniques.Dissertation for final year project for BSc.(Hons) in Applied Computing.

Results.

The following pages contain tables and graphs to show the results of the calculations described earlier for calculating the 'pull' of the flock. After experimenting with the values in the formula, the effect of the pull varied, depending on the amount of tadpoids. For this reason it was decided to have the value of the constant C dependent on the amount of tadpoids.

The effect of this is that two tadpoids separated from the flock when there are twenty tadpoids free, they are not attracted to each other as the larger groups offer much more safety from the predator. This is not the case when there are less tadpoids free.

The tables that the graphs were created from are also displayed.

The computer simulation was designed to allow the attributes of each tadpoid to be modified interactively by the user. By changing the values of the maximum speed and range-of-turn, the movement of the tadpoid changes considerably. The range that the tadpoid has until it is 'out-of-flock' can also be modified.

Discussion: Emergent Behaviour

From observing the tadpoids flocking the following behaviours emerge:

Following

The tadpoids appear to follow the heading of a nearby tadpoid. However, a tadpoid is not programmed with a heading nor instructed to follow the heading of another tadpoid. This 'following' behaviour emerges from the collision avoidance behaviour and the desire of a tadpoid to group. When two flocks head towards each other they merge as one with a fluid, elegant movement.

Flock splitting and break-away flocks

The flock does not always remain a single flock. Periodically, breakaway groups 'peel-off' from the flock. There are several reasons for this to happen.

A large flock heading for an obstacle may split to evade an obstacle. The group may also split without interference, as the tadpoids are free to wander. The front of the group may speed up and the middle part of the flock get separated, turn away and the back of the group follow this breakaway.

The breakaways are a natural flocking occurrence. To force the tadpoids to stay close, regardless of the situation would not be a reactive behaviour. It is reasonable for a slow moving group to be separated from a fast moving group, as is the expectation that a predator heading quickly for a collision with a slow moving group of tadpoids will scatter and the flock will split.

Shoving

A fast moving tadpoid will sometimes appear to 'shove' a slow moving tadpoid out of the way. This is more obvious when a tightly bunched group are moving. This was an unexpected behaviour that resulted from not allowing the tadpoids to overlap, as the tadpoids and the predator are modelled as physically solid objects.

When I first noticed this I increased the size of the tadpoids and removed the tadpoids behaviour to react to the predator, so the effect was visually exaggerated. By making the predator stationary and the tadpoids group close together, the group of tadpoids shoved the stationary predator along until the group had passed around it. The flock swept along the predator. I also tried to force the predator through the group and observed the predator being slowed as it tried to squeeze through the group. This shoving behaviour works well as the tadpoid overlapping a tadpoid from behind will be displaced against the direction it is traveling in, while the tadpoid in front is displaced in the direction it is heading. This has the effect of slowing the tadpoid behind.

Corner crowding

A large flock of tadpoids will sometimes bunch up at the corner of a boundary, bump into each other and then head off, not always together. This corner crowding emerges from the 'shoving' from behind as the front ones slow down to turn to avoid the boundary. It only appears to happen if the group are heading straight for the corner rather than following a wall. The diagram below illustrates this:

Peeling-off

Sometimes a tadpoid may be moving along with the flock and suddenly turn away and continue turning until it rejoins the flock, 'peeling-off' from the flock. This behaviour emerges from a tadpoids freedom to wander and that if a tadpoid wanders so that it is alone, its desire to get closer to other tadpoids increases.

Flock Mind

As mentioned earlier, there is no overall control of the flock, and yet the flock appears to be heading somewhere, as if the flock is making a collective decision where to go. As each tadpoid is not given a heading but is allowed to wander, the collective will of the flock emerges. This emergent behaviour is most evident when the flocking and collision avoidance behaviours are in tandem. To demonstrate this, the collision avoidance behaviour of each tadpoid was removed but the grouping behaviour remained. The tadpoids tended to 'mill about', remaining as a flock but with no collective heading. When the collision avoidance behaviour is included and the grouping behaviour is removed, each tadpoid wanders freely, appearing to have its own heading but not as a flock. However the tadpoids retain the tendency to swoop in and follow tadpoids briefly, periodically forming small groups with a collective heading.

The combination of the collision avoidance and flocking behaviour allows the 'flock mind' to emerge. The sum of the flock is greater than its constituent parts.

Future Work

In this study, flocking methods and reactive behaviours have been investigated and a working computational model has been developed. The predator can be user-controlled, allowing the flock to possibly be herded into a pen. A strategy can be formed to perform such an action through interacting with the tadpoids, but as the movement of the flock is unpredictable the user has to constantly re-evaluate their strategy.

If the predator was an autonomous agent and had the task of herding the tadpoids into the pen, the agent would have to somehow learn to herd the flock, as there are no hard-and-fast methods for flock control.

Reinforcement learning, one of the most active research areas in machine learning, Artificial Intelligence (AI) and neural networks, is a computational approach to learning whereby an agent tries to maximise the total amount of reward it receives when interacting with a complex, uncertain environment (Sutton and Barto, 1998).

A flock that emerges from the sum of the individual tadpoids is a complex uncertain environment. The predator is the learning agent whose overall goal is to pen the tadpoids. It would do so by learning from interaction, which is a fundamental idea underlying nearly all theories of learning and intelligence. Reinforcement learning focuses on goal-directed learning from interaction.

The basic idea is simply to capture the most important aspects of the real problem facing a learning agent interacting with its environment to achieve a goal. Such an agent must be able to sense the state of the environment to some extent and must be able to take actions that affect the state. The agent must have a goal or goals relating to the state of the environment. The formulation is intended to include just these three aspects - sensation, action, and goal - in their simplest form without trivialising any of them (Sutton and Barto, 1998).

The task of learning to herd a flock appears suited to reinforcement learning as there is not a fixed way of performing the task. The flock is constantly changing and so only by experience with interactions with the tadpoids can the predator improve its performance.

Supervised learning, where learning is achieved from examples provided by a knowledgeable external supervisor, is not adequate for learning from interaction. In interactive problems it is often impractical to obtain examples of desired behaviour that are both correct and representative of all the situations in which the agent has to act (Sutton and Barto, 1998). The possibilities with regard to an emergent flock are too bewildering to contemplate using this method.

One of the challenges that arise in reinforcement learning and not in other kinds of learning is the trade-off between exploration and exploitation. To obtain a lot of reward, a reinforcement learning agent must prefer actions that it has tried in the past and found to be effective in producing a reward. However, to discover such actions, it has to try actions that is has not selected before. The agent has to exploit what it already knows in order to obtain reward, but it also has to explore in order to make better selections in the future. Therefore, the dilemma is that neither exploration nor exploitation can be pursued exclusively without failing at the task. The agent must try a variety of actions and progressively favour those that appear to be best.

Can an agent teach itself or learn the rules to control what is in essence a chaotic system and learn to have overall global control?

Reinforcement appears suited to the problem of a predator learning autonomously to herd a flock, and I would like to research this in a future study.

Conclusion

Complex global behaviour may emerge from the interaction of tadpoids that have a few self-determined behaviours. By altering a single behavioural parameter one observes that the entire interaction of the tadpoids alters in ways which would at first appear unrelated to the initial change.

A single change within a complex system has knock-on effects, which even with a thorough knowledge of the components of the system is hard to predict. For example, by increasing the maximum possible speed of the tadpoids, the movement of the flock is not a faster version of the slower flock. Also, by increasing the distance that tadpoids need to be within other tadpoids, does not result in a similar flock with the tadpoids spaced further apart, but creates an altered state that has far reaching effects on the individual interactions and hence the global behaviour.

By using the pull of the flock algorithm this allows for natural looking, realistic flocking to emerge. This is because each tadpoid has a choice on where to head based on its individual perception of the environment and the tadpoids head for other tadpoids, whereas using the Reynolds centring algorithm each tadpoid when 'out-flock' is forced to a given heading - the average position of the flock. This position could be where there are not any tadpoids, so is an unnatural method.

By strategically controlling the predator's movement, a user may learn to coerce the tadpoids and maybe even herd them into a pen. However, if the tadpoids flocking algorithm is removed, the task of trying to 'round-up' the tadpoids increases in difficulty as they have to be penned more or less one by one.

The introduction of the predator's influence upon a tadpoid as a summative effect allowed the tadpoid to evade the predator while simultaneously seeking the safety of the flock.