Citizen phil » Flocking. » dissertation

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

I became interested in behavioural simulation when imagining whether a computer programmed agent would be capable of herding a flock of animals (say sheep) into a pen by using its own artificial intelligence. This led me to looking into how one would generate agents that would flock in a natural looking way whilst also attempting to flee from a predator.

This work was my final year project at University. The behavioural simulation of a herding agent was used later to create an online game, 'One Man & His Two Dogs' . This dissertation, "An Investigation Into Computational Flocking Techniques" - May 1999. shows the ideas and methods used.

I would like to thank Matty Bickerton and John Pratt for their help with the project.

Abstract.

In this study I investigate and develop a behaviour-based system from which flocking may emerge.

Flocking is a particularly evocative example of emergence: where complex global behaviour can arise from the interaction of simple local rules.

Flocking simulations are developed in this study that display realistic movement, but they do not yet represent herding by another agent. The ability of an agent to coerce the flock into a fixed area has not been explored but I hope to develop such behaviour, in a future study.

I hope to develop autonomous creatures that interface with their environment through perception and action. In this way they will react to situations as they happen and take appropriate action.

I have developed a computer model of co-ordinated animal motion such as sheep flocks or cattle herds. It has been developed using Borland C++ v4.5 and an Object-Oriented Design methodology. The model allows a user-controlled predator to be manipulated to interact with and influence the flock.

Terms of Reference.

I will investigate methods currently used in computer graphics and also look at behaviour-based systems that are being used to build autonomous mobile robots. The robots deal in real-world environments rather than simulations so useful tasks may be carried out in an environment which has not been specially structured or engineered for it.

In this way I hope to develop creatures that do not have fixed responses to situations but react appropriately in a natural way based on how they perceive each situation.

A working simulation of the 'flock' and 'predator' in action is created in order to discover whether the predator can successfully herd the flock into a desired pen.

I hope to simulate completely autonomous agents that are seen as intelligent beings in their own right. I will call such agents TADPOIDS, for the purposes of the project. A collection of tadpoids forms a flock.

I will call the agent herding the tadpoids the PREDATOR.

There are some requirements for each element of the flock, a tadpoid, which must be considered.

  • A tadpoid must cope appropriately and in a timely fashion with changes in its dynamic environment.
  • A tadpoid should be able to maintain multiple goals and, depending on the circumstances it finds itself in, change which goals it is actively pursuing; thus it can both adapt to changing situations and react with urgency if required to do so.
  • the behaviour of a tadpoid should be self-determined

I hope that through the development of realistic behaviours, including fleeing from the predator, the tadpoids may be herded into the pen. As the emergent flock emanates from randomly generated motion, it is by essence unpredictable in its movement. Therefore, the problem of trying to coerce them into a specific area is not trivial. For this reason I see it as a suitably challenging Artificial Intelligence (AI) problem.

Intelligent Behaviour

At the Massachusetts Institute of Technology (MIT) AI Laboratory, Rodney Brooks has developed robots with multiple behaviours to handle a variety of tasks (Brooks, 1991).

The robots implement the same abstract architecture, called subsumption architecture (Brooks, 1986). This embodies the fundamental ideas of decomposition into layers of task achieving behaviours, and incremental composition through debugging in the real world (Brooks, 1991).

Each activity or behaviour producing system individually connects sensing to action. An activity producing system layer is referred to as a layer. An activity is a pattern of interactions with the world. The layers must decide when to act for themselves, not be some subroutine to be invoked at the beck and call of some other layer (Brooks, 1991).

(Maes and Brooks, 1990) programmed an early six-legged robot to learn to walk using the subsumption architecture along with the behaviour activation schemes of (Maes, 1989). This example is the closest to the machine learning ideas in reinforcement learning. This shows that by incorporating layers of control at increasing levels of competence an autonomous intelligent agent may be created.

This approach to a gradual behavioural sophistication is appropriate for the development of a tadpoid. The initial behaviour of wandering may be developed, then allow it to avoid collisions, evade the predator and so on.

Consider a single tadpoid heading back to the flock and the predator attempting to intercept it. The urgency of the fleeing action of the tadpoid makes it evade the predator until the predator is no longer an influence.

Subsumption architecture allows multiple goals to be achieved. By having prioritised levels of competence the 'flee-predator' level subsumes the 'return-to-flock' level, so the tadpoid can evade capture. The lower 'return-to-flock' level continues to function as the higher 'flee-predator' level is added.

However, I would like the tadpoid to attempt to return to the flock whilst still evading the predator. This is primarily as the tadpoid is safer when in a group so will try to return to the group even if it means taken a longer route to get there.

Rather than have a hierarchical priority of levels of competence, I propose that each tadpoids movement is a sum of the reactions to all the influences at that time. In this way the tadpoid will be able to achieve multiple goals without suppressing lower layers of control.

The architecture is still subsumption in that a basic tadpoid is created so it can move at first and higher levels of competence are added. The initial layer allowing the tadpoid to move is unchanged. In this way I aim to develop a realistic intelligent agent that can avoid collisions, seek safety by grouping, and evade the attentions of the predator utilising real-world physics.

Flocking

How is it possible to create a flock?

In 1986 Reynolds developed a computer model of co-ordinated animal motion such as bird flocks and fish schools. It was based on three-dimensional computational geometry of the sort normally used in computer animation or computer aided design. The software is called BOIDS.

The approach to flocking described by Craig Reynolds (Kelly, 1994) follows only a few simple rules encoded into an algorithm. He used this algorithm to control the movement of computer generated bats in the film Batman Returns. A horde of large black bats swarms through flooded tunnels into downtown Gotham. A single bat was created and given leeway to automatically flap its wings. One bat was copied until the animators had a mob. Then each bat was instructed to move about on its own following only a few simple rules encoded into an algorithm: don't bump into another bat, keep up with your neighbours, and don't stray too far away. When the algorithmic bats were run, they flocked like real bats.

As the scenario I require is a field surrounded by a fence and a pen, I will implement two-dimensional geometry. This will be a more realistic environment for a flock to be penned, as herding by an agent is primarily done on the ground. Imagine the task of trying to herd a flock of birds into a cage.

Methods