Agent-Based Swarm Model

March 18, 2012 Comments Off on Agent-Based Swarm Model

Swarming agents that seek a target, navigate through terrain (with fairly primitive means), avoid potential predators, starve, die, eat prey and carcasses. Misc emergent behaviour ensues. With a maze generator to produce a wide range of terrain structures.

Agents are coloured by generation (i.e., according to the time they were spawned), but lose saturation after some time as they start to starve. They will aim for one of three target points which is selected at spawn time. They can survive (and grow) by eating smaller agents, or taking a bite off a carcass.

Agents will avoid larger live agents, and carcasses when they’re not hungry
(the repelling force is a power law distribution relative to agent sizes),
but they won’t notice walls until they hit them, and then bounce off or get
stuck.

There is a limit to the total number of live (and dead) agents on screen.
Once the limit has been reached, new agents can only be spawned when any
agent reaches their target and is removed. (For this reason targets can
also be considered “breeding grounds”.)

Press the “f” key to toggle “flypaper mode“, which makes agents stick to
walls and die instantly. In this mode complex terrains are much harder to
navigate. Since agents will avoid larger carcasses these now act as “beacons”
for nearby walls, and allow new agents to travel farther.

A few histograms show live/dead/arrived agent counts per generation. This
allows to observe how quickly agents manage to find their target, a function
of the terrain. The target histograms are especially interesting in flypaper
mode, where it may take a few generations of dead “beacon” agents to mark a
path along walls until new agents can pass.

Terrain Models and Navigation

Press the space bar to start again with a new terrain. The basis of these
generated terrain models is a graph-based depth-first maze generator that involves a few additional steps to modulate terrain structures (e.g. wall strengths.) A post-processing step may remove random
walls between cells of the maze. A number of terrain types exist, and each new terrain will be a variant of one of these preconfigured types.

Agents navigate through the combination of a few primitive behaviours. They will aim towards their target, avoid colliding with other agents, escape the proximity of potential predators (larger agents), and avoid carcasses unless they are hungry. These agent interactions rely on distance computations and power-law, which allows for a certain degree of prediction. Wall interactions lack any predictive quality; agents cannot perceive walls until they reach them, and then bounce off in random directions or (in flypaper mode) get stuck. A fair amount of time was spent fine-tuning the intensity and interaction of these behaviours in various terrains.

A big limitation of this is the absence of any “line of sight” logic, and of stronger predictive and planning behaviours. As a result agents will e.g. head in the direction of their target even with walls between them, and they will get stuck in corners without the ability to find reasonable alternative routes.

Examples of Emergent Behaviour

With more complex terrains it is worth letting the model run for a few minutes to observe emerging zones. Let’s look at an example of how the system evolves in flypaper mode, broken down into stages.

The start of a new terrain. Agents get stuck on walls and die, start covering larger and larger areas of it; since live agents will avoid dead ones (unless they are hungry) these carcasses now act as wall beacons.

On the left of the terrain agents started assembling in a bay. To the right of the bay the terrain blocks direct access to their targets, and a wall at the top of the bay prevents them from escaping. Any agent that arrives here by itself would be trapped. However agents will avoid colliding with other agents, and will attempt to avoid the close proximity of predators (larger agents), and in combination this results in complex flows and eddies. Once enough agents are part of this flow some agents may get pushed over the edge of the bay, to then slowly build a longer path for later generations, step by step.

Over a period of a few minutes, as agent carcasses begin to cover most of the wall space between the origin and the three target points, live agent numbers steadily decrease. All three target points can now be reached, which allows a process of renewal to take place: every agent that reaches their target allows a new agent to be spawned.

If agents are “bullied” into a detour towards their target they may still encounter open wall space in less-covered areas once they can escape. E.g. a forced clockwise tour around the terrain towards the bottom-right target will lead to some open wall patches in the top right corner of the terrain.

A few minutes later (not shown here) all live agents are of a recent generation, which implies all new agents either reach their target, get eaten, or get stuck and die; all of which allows new agents to be spawned. Agents that are temporarily stuck in bays will not stay there for long, and their presence allows others to pass. The population count has decreased again, but not by much; we may be heading towards a stable state.

About half an hour after starting the simulation the population count appears to remain in the 30-40 range. A delicate equilibrium.

The broad range of agent interactions and emergent behaviour that can be observed, including the examples mentioned above:

  • The distribution of colour across the terrain indicates zones of faster or slower propagation.
  • Groups of agents may push other (smaller) agents in wrong directions away from their target until they get a chance to escape. These “bullied” agents will wiggle their beak as they continuously attempt to change direction.
  • Dense clusters between walls result in complex flows, and agents may start panicking as there is no space to evade nearby predators.
  • Dead ends may result in starvation deaths, which provides food to grow. This allows a few agents to escape once they have become large enough to move in larger steps.
  • Also note the interaction between walls and carcass prey in flypaper mode: an agent may be tempted to eat a wall beacon carcass to survive, but this brings it in closer proximity with the wall, and makes it possible that it will itself get stuck and die. This could be regarded as a form of “weary desperation”.
  • The system may reach an equilibrium where many agents are stuck or dead, but targets are still accessible enough so that there is a steady trickle of renewal. Such equilibria may have any number of live agents.

The Processing source is on GitHub.

Advertisements

CA with Periodic Reorganisation

March 3, 2012 Comments Off on CA with Periodic Reorganisation

Multiple cellular automata interleaved with periodic processes of reorganisation:

  • Randomly move some tiles.
  • Fill all tiles with their dominant colour.
  • Rearrange all tiles in circular order.
  • Sort all rows by colour.

The Processing source is on GitHub.

Where Am I?

You are currently viewing the archives for March, 2012 at COVSPC.