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.
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!
:)
