EXPECT THE UNEXPECTED
THE RIDDLE OF EMERGENT BEHAVIOR
What comes after, is not what was meant to be.
Ants don’t build anthills. Well that statement just doesn’t seem to work, does it? Clearly there is an anthill and clearly there are ants working on, in and around it. So they must be building it. What makes it interesting is that they didn’t mean to build it .
I discovered this interesting fact while researching my latest project: an experiment that involves emergent behavior in a robot swarm. Swarms are not new. In short, a robot swarm is a distributed robotic system. Swarms use a large number of identical, small, simple and usually inexpensive robots instead of a single, complex system. One advantage to the redundancy is surviveability of the system. When a there is a critical failure on a small robot, it simply drops off-line and the group is unfazed since all the robots on either side close the gap.
The end result is that the work continues and no “down time” is logged. The failed robot is collected later, unless it is inaccessible, but even then, owing to its low cost, the loss is insignificant compared to all the hardware or the work value provided by the entire system.
NASA has seriously explored this method of deployment for interplanetary exploration, most notably for landing on Mars. There are many reasons why it is a good system. The landing does not rely on all robots surviving. Many can be damaged and many can fail and the system remains reliable, conducts the expected work and returns the desired science.
Still NASA has yet to deploy a swarm on any planet, rock or moon. There are probably a few very good reasons for this, too. Since I am not on staff at NASA, I can only guess that one of the biggest detractors would likely be the communication systems necessary to talk back to earth, which might not be easily distributed among the swarm with enough power to make a usable signal for interplanetary communication. So, if you can’t do it with a lot of small robots, then a single system is required for the mission and we have seen that in the recent rovers that have been crawling on the surface. Sitting here in my darkened kitchen, however, I can foresee an even more sinister possible out- come that would cause the engineers at NASA to avoid swarms: Emergent Behavior.
Emergent Behavior is any behavior that is not expected, based on the inputs available and the planned outputs. Basically the system develops new properties that result from interaction of the robots in a swarm, at the most basic levels. In other words, the robots are doing something the designer didn’t intend for them to do!
According to the research of Dr. Debra Gordon, who studies harvester ants in the Arizona desert, the nest that ants build is completed without the benefit of central cognition. In other words, nobody is in charge. No single ant, like the queen for example, or even a committee of ants is deciding the next steps necessary to build the colony. In the face of a changing environment or disturbance to the nest, the same simple rules are followed and the result is still success.
Dr. Debra Gordon’s research suggests that, at least in the case of the Arizona ants, there are basically only four types of ant jobs in the ant world. Pretty limiting in terms of advancement, but hey, we are talking ants here. Even though there are only four basic jobs, the result is an amazingly successful, complex and on a certain level even beautiful structure built and sustained using a brain that employs a mere half million neurons or fewer.
An Anthill Is An Emergent Behavior
Systems like this emerge in other places in nature. Many social insects display forms of Emergence. It also appears in higher order animals like, for instance, birds. Bird flock- ing is one example. The behavior of bird flocks can be reproduced when models are equipped with just a few simple rules.
- Stay away from other birds that come to close.
- Stay close to birds that stray too far.
- Proceed in the same basic direction as other birds that are nearby.
Following these three basic rules, a flock develops and moves in an undulating pat- tern through the sky. Maybe it is not an efficient behavior, but it is an emergent behavior nonetheless.
I am very interested in multi-robotic systems, so I decided that I would embark on an experiment to explore an emergent behavior, but I must be cautious. If I devise an experiment that is guaranteed to display an emergent behavior is the behavior emergent at all or is it designed into the system from the start? Even if I try to simulate an existing system that displays an emergent behavior and succeed, I can be accused of preparing the experiment to show exactly what I expected to find. Maybe I could be accused of designing the outcome into the original system.
On the other hand, I can waste a lot of time trying out rule sets to see if one will develop a behavior. So how then, does one design a rule set that allows an emergent behavior to develop without intentionally creating an environment in which it must emerge?
Like fractal images. With a given seed, you get a repeatable result. So was it emergence only the first time, or can it be called emergence each time it repeats? Anthills repeat themselves, with minor variances and each time an anthill forms, it is emergent. So without intentionally creating a behavior, I seek to design an experiment from which a truly unexpected behavior emerges. This behavior may be extremely subtle and risks creating a very boring experiment, but if the emergence can be defined, then I will have success.
Onward to the experiment itself. I will describe it here in some terms, but please don’t be mad at me if the actual experiment evolves somewhat from this initial description. The creation of the experiment may reveal limitations or opportunities that I may wish to incorporate or that I would have to work around. One such limitation evidenced itself before I even began this journey. Originally, my plan was to simulate a basic, automated car environment. The vehicles would be allowed to change lanes, stop, turn and make routing choices, but never leave a closed course. I wanted to see if emergence would develop in traffic patterns.
I suspect that this would have resulted in an emergence, but as I began to consider the requirements, it became obvious that this lofty goal easily exceeds the computing capabilities of the Boe-Bot by a wide margin and starts to encroach on the level of a DARPA challenge. Ok, maybe that’s an overstatement, but basically, I’m just not there with the system I have chosen. Simpler systems, besides being easier to work with, will likely display an emergent behavior both more quickly and more measurably. The Boe-Bot platform lends itself well to an application of this type. An attempt at simulating a more insect-like intelligence is considerably more practical.
The rules are more basic. There will be several groups of similarly tasked bots. The tasks will be complementary and dependent. Task switching will be an option for each robot. Tasks will be virtual and represented by LED outputs.
Communication between the Boe-Bots will be accomplished with an IR transceiver circuit.
My initial list follows (this will be refined and may have changes):
- Collect “food” from “food” source. If meeting another robot that has no food, pass food to that robot.
- Robots with “food” will only move that “food” west.
- Collect “refuse” if meeting another robot that has no refuse, pass refuse.
- Robots will only move “refuse” east
- Avoid an obstacle by touch. This includes collision avoidance between robots.
I will provide the Boe-Bots (Boe-Bugs?) with a “food” supply and a supply of “refuse”, both of which will be provided by an IR signal from a stationary Board of Education at each end of the field. The field itself will have a border to contain the swarm, since navigation will be very rudimentary. As the “hive” works together, exchanging the two payloads, I will begin to introduce obstacles and observe how the robots adjust to the intrusion. With any luck, a result will emerge somewhere in the mix that is not planned.
To conduct this experiment, I have obtained 12 standard Parallax Boe-Bot robots and two Board of Education boards, also equipped with Basic Stamp (BS2) chips. Enough cannot be said about this versatile little platform.
It is an excellently equipped robot with lots of experimental capabilities. I am very excited to get my hands on the new version that comes with the Propeller chip. That should significantly enhance this already amazing bot.
However, I have already started with the Stamp equipped model, so I will finish the experiment with these robots. The intelligence I am attempting to duplicate is simple enough that the stamp will per- form an adequate job and it will be easy to program.
Due to the complexity involved in this experiment, I cannot promise results by the next issue, but I will at the very least, provide you with a progress report. So make sure you keep reading ROBOT, to see what happens when I turn on a dozen Boe-Bots at once. That should be exciting.