Abstract: The following is a short overview of my idea about how to create a novel control system / problem solver using ideas from the field of swarm intelligence.

Note: I have written an 18p term paper on this topic: TLints_Flockheadz_2006_EST.pdf, but it is in Estonian.

Swarm Intelligence

Swarm Intelligence (SI) is a branch of artificial intelligence (or maybe more specifically, of computational intelligence, see http://en.wikipedia.org/wiki/Computational_Intelligence). It is inspired by the behavior of animal / bird / fish / insect swarms, flocks, herds and schools in nature. Artificial swarms, be they soft- or hardware, are typically made up of a population of simple agents interacting locally with one another and with their environment (http://en.wikipedia.org/wiki/Swarm_intelligence). Even though the agents can be very simple and "dumb", the resulting group behavior may be quite interesting and/or useful. SI can be broadly divided into two branches. One of them mainly wants to imitate natural swarms, e.g. to create a swarm of robots that cooperates like a colony of ants or maybe to create a natural-looking software simulation of flocks and herds for use in movies and computer games. The other takes a more abstract approach and uses a virtual artificial swarm as a problem-solving tool, often not even bothering to visualize the moving agents.

Examples of the first approach:

Examples of the second, more abstract approach:

  • Ant Colony Optimization (ACO) -- a probabilistic algorithm for solving computational problems which can be reduced to finding good paths, typically on graphs (http://en.wikipedia.org/wiki/Ant_colony_optimization). Basically the algorithm simulates ants who wander around and leave a trail of pheromones to the ground on certain circumstances (e.g. to indicate for other ants the path towards food). For a simple explanatory visualization of foraging ants see http://ccl.northwestern.edu/netlogo/models/Ants and choose "Run Ants in your browser" (or download the whole NetLogo package with a great many interesting models).
  • Particle Swarm Optimization (PSO) is based on the idea that members of a swarm may communicate with each other, mainly in the form of reporting the situation in their immediate neighborhood. For example if someone finds food, she can call all others to eat there as well. In PSO the members of swarm are usually represented by moving particles, whose speed vector is influenced by the announcements of other particles. The goal of the algorithm typically is to find the optimums of some function in the multi-dimensional search space of problem-related parameters. For a more detailed description see http://en.wikipedia.org/wiki/Particle_swarm_optimization. For some pictures of PSO in action see http://pages.cpsc.ucalgary.ca/~khemka/pso/model.html.

Flockheadz

While ACO is quite narrowly specialized on finding the optimal paths, PSO can be applied to somewhat wider set of problems. However, PSO has restrictions as well, e.g. the algorithm should, in most cases, be able to compute the fitness value for whatever position any of the particles happens to be in.

My idea is not to create a replacement for ACO or PSO, but to try out a new approach, which may be more inclined towards control systems than problem solvers (though it may well be applicable in other areas as well. Or nowhere at all :D ). (Note: I call the idea new because I am not aware of any similar idea by anybody else. If you know, let me know as soon as possible!)

The idea is to create a "brain" (a control or problem solving system of some weird kind) through the following steps:

  • Take a simulated flock (like the boid flocks by Craig Reynolds).
  • Put it in a closed virtual space.
  • Add some sensors to the boids, e.g. for sensing the intensity and direction of light.
  • Add some rules to the boids so that the sensor readings will influence their behavior.
  • Create input channels to this "brain", for example map the input parameters to the parameters of light sources in the virtual space (light position, intensity, color, ...).
  • Create output channels by mapping swarm-related variables (location and speed vector of swarm center, density of the swarm, etc.) to output variables.

To give a very simple example: imagine we have a virtual creature in a computer game and it must avoid bad guys.

Flockheadz_avoidance.jpg

In the upper right corner above you can see the good green guy confronted by two bad red creatures. Let's put the swarm (small blue triangles) into a circular two-dimensional room, which is the "brain" of the good creature. Bad guys are represented as light sources on the edge of the circle. Swarm members are repelled by the light and move downwards (big blue arrow). When swarm reaches the lower part of the circle, the good green guy will also start moving down (4 grey arrows in the circle indicate the relation between swarm position and output signal that controls the green creature; left and right arrows indicate turning of the creature).

The described hand-constructed system is not very good:

  • When bad guys encircle the good one, the swarm moves to the center and creature will stay in one place (which is not necessarily bad, though).
  • More importantly, the avoidance of bad guys is directly written in by the system designer: swarm members are made to behave like the creature itself should behave.

The second point does NOT necessarily mean that using a "swarm-brain" is not justified and rules should be written directly for the creature -- the Flockheadz approach may make the creature move a bit less expectedly and therefore more interestingly. Instead, the problem is: when the complexity of the task increases, human designers are less likely to be able to come up with an effectively constructed swarm-brain.

One way to overcome this problem is to try using genetic algorithms (see http://en.wikipedia.org/wiki/Genetic_algorithms for more information on GAs) for generating appropriate "brains" for given tasks. It is encouraging to note that GAs have already been successfully used to find good control systems, composed of various building blocks, for many virtual creatures. For inspiration, see the Karl Sims 1994 video at http://www.archive.org/details/sims_evolved_virtual_creatures_1994 (references to Sims' papers are also there). Another very cool example is the work of Julian Miller and Simon Harding, who took a matrix LCD screen (a real piece of hardware, not some simulation) of a usual pocket calculator and evolved it, in one of their experiments, to become a controller of a simulated robot, which then moved around, avoiding obstacles. Their general suggestion is to try genetic algorithms on all kinds of potentially evolvable physical materials that can be influenced using electrical signals (most non-electrical systems are just immensely harder to evolve in a lab), e.g. liquid crystal, nanoparticle suspensions, Langmuir-Blodgett films, conducting and electroactive polymers, voltage controlled colloids, irradiated Silicon and microbial consortia. Harding's publications are listed at http://www.cs.mun.ca/~simonh/publications.html (see the section "Publications on Evolution In Materio").

When evolving Flockheadz, the changeable variables might include: the mappings between "brain" input and virtual signal sources inside the "brain"; the mappings between swarm parameters and "brain" output; the functions governing boid behavior. For more complex tasks it may be necessary to increase the system complexity: different species of boids, different sensors and signal sources, etc.

You

If you have any comments or suggestions, then please let me know! If you are interested in doing some work on this idea (just for fun or for writing scientific papers or for profit or whatever), then feel free to contact me, let's cooperate! :)