Coordination without Communication
Abstract: Here we examine situations in which coordinated behaviors
occur without prior planning via communication. Such situations are both
common and effective in multi-agent systems, be they biological or computational.
Such coordination results from stigmergic sampling of the environment and
responding to it. We conclude that stigmergic coordination without communication
should be considered as a control architecture when designing multi-agent
systems.
Keywords: communication, conjoined twins, control architecture, coordination,
ethology, motor control, multi-agent systems, planning, robotics, social
insects, stigmergy
"Hey, Dad. Would you please hold this banner in place while I tape
it to the wall?" asked my eight year old daughter, Sunny, early one
Mother's Day morning. I did. And she did. It was a quite unremarkable example
of coordination of actions following a mutual plan arrived at via communication.
Without giving it any thought, I'd assumed that coordinated actions always
resulted from such planning. The coordination of hunting lionesses reported
by Donald Griffin (1984, p. 86) provides an example of my making such an
assumption. Here's a paraphrase of his account from my Artificial Minds
(1995, p. 59).
A group of five lionesses approached two groups of wildebeest separated
by a road. Two lionesses mounted ant hills so as to be clearly visible but
pose no threat. A third crept along a ditch paralleling the road until she
was between the two bands of wildebeest. Then a fourth lioness charged out
of the woods adjacent to the leftmost band, driving them across the road
toward the other band. The lioness in the ditch easily killed one wildebeest
as it jumped the ditch. All five then began to feed.
I go on to say (1995, p. 59), "It's hard for me to believe that the
lionesses described by Griffin met as a committee to devise their plan.
On the other hand, it's equally hard for me to believe that this scenario
occurred unconsciously and without some sort of communication." While
I still doubt that such coordinated actions could have occurred unconsciously,
I'm no longer at all sure about the need for communication.
The story of the Hensel twins (Life, April 1996, p. 44; Time, March 25,
1996, p. 60) sowed the seeds of doubt. Abigail and Brittany, kindergartners,
share a body. Their separate heads rise from a single pair of shoulders
topping a body with the usual number of arms and legs. Inside, things are
more complex, with two hearts pumping a single circulatory system, three
lungs, two stomachs, and separate spines jointed at the pelvis. Their nervous
systems are disjoint. A touch on the right side is felt only by Abby. Each
controls one arm and one leg. And therein lies the rub. At fifteen months,
they learned to walk. Now they swim, bike, and tie shoe laces, all requiring
considerable coordination of actions. This coordination is apparently achieved
without communication.
"But," I've been told, "they do communicate through the environment.
Each is aware of the other's actions via vision, proprioception, etc. That's
communication." Is it? True, all communications occur when one agent
acts on the environment and the other senses the results of that action.
But would all such acting and sensing comprise communications? I think not.
It's far fetched to call my following the tracks of a bobcat in the snow
communication between the bobcat and me. Communication, in the sense of
the word I intend, requires the sending and receiving of signals. Is the
bobcat signaling when he leaves tracks in the snow? I think not. This situation
is quite analogous to me following a river downstream while canoeing. How
about the tigress marking the boundary of her territory with urine? I think
so. And the difference? Intention, in the folk psychology sense, not the
philosophical sense. The tigress intends her signal to be received and to
be meaningful. But what of animals who send sexual signals via pheromones?
Surely not all such are sent intentionally. It seems that I've painted myself
so far into a corner as to have to postulate unconscious intentionality
brought on by evolution. Such problems are to be expected when we arrive
at the fuzzy edge of any non-mathematical concept. Still, I see no evidence
of Abby communicating with Britty while tying shoes.
Is such coordination without communication possible only under the most
unusual circumstances of the Hensel twins? Let me give you another example
that should have alerted me to the possibility of coordination without communication
years ago. My older children during their teenage years were quite fond
of a maze game called Labyrinthspiel. Picture a roughly one foot square
wooden box some four inches tall. Mounted in the upper interior of the box
were two nested trays. The inner tray was a maze containing some sixty holes
strategically placed as pitfalls for the unwary traveler. The traveler was
a small steel ball, just able to fall through one of the holes into the
bottom of the box. The outer tray, mostly rim, was mounted at its center
on a metal rod running north south. A knob, attached to the rod, could be
rotated, tilting both trays in the east west direction. The inner tray was
independently mounted on a second metal rod perpendicular to the first.
Rotating its knob tilted only the inner tray in the north south direction.
With the ball in the starting position, the player attempted to guide the
ball through the maze, avoiding all the holes. This required well coordinated
manipulation of the two knobs using the principle that balls roll down hill.
It wasn't easy.
Over time, two of the children, Phil and Mimi, completely mastered Labyrinthspiel,
being able to reliably guide the ball back and forth through the maze, missing
all the pitfalls. But such mastery led to boredom. So, they invented two-person
Labyrinthspiel, Mimi controlling one knob and Phil the other. To my amazement,
they were soon able to coordinate their movements so as to successfully
negotiate the entire maze.
It seems to me that this sort of coordination is impossible to achieve in
real time via any sort of signaling. It can only result from each agent
frequently sampling the environment, in this case watching the ball and
the attitude of the maze, and reacting to it with its goal in mind. Reacting,
in this case, should be taken as reacting not only to the ball's location,
but to its velocity (including direction)1 as well. Coordination emerges
incidentally. I also suspect that there are no internal signals from the
right hand's controller to the left's when a single human is playing. Probably
sampling and reacting suffices.
This suspicion is at least partly shared by my neurophysiologist friend
Lloyd Partridge who specializes in motor control. Lloyd doubts that central
nervous system coordination plays much of a role in such activities as playing
Labyrinthspiel that require coordination of the actions of the two hands
(personal conversation).
As another example, consider several adult mongoose attempting to guard
their nest and young from a marauding cobra (as seen on a TV documentary).
One mongoose moves just within the cobra's striking distance. Just as the
cobra prepares to strike a second moves in, distracting him as the first
retreats. Again, just before the cobra strikes, a third advances and distracts
him. This script continues until the cobra wearies and departs. Again, coordination
occurs though signaling seems neither needed nor possible.
Is such coordination without communication possible only by biological agents?
Let's look at another scenario. Genghis, produced by Rodney Brooks and his
students at MIT(1989), is a six-legged, insect like robot that walks. Each
leg is attached to the body at a joint with two degrees of freedom. The
movement of each joint is controlled by two servo motors. When carefully
programmed so that the six legs coordinate well, Genghis walks. Later, Pattie
Maes and Brooks (1990) deprogrammed Genghis, and augmented his sensors.
They fitted Genghis with touch sensors on the under front and under back
of his abdomen which sent a "pain" message whenever his belly
touched the ground. They also attached a trailing wheel which sent a "pleasure"
message when the wheel rolled forward. With this reinforcement and punishment
in place, Genghis learned to walk with an insect's tripod gate. This coordination
of the six legs was achieved with no communications between them.
Can this be so? Genghis is built on Brooks' subsumption architecture (1989)
with twelve leg swing behaviors, six forward and six back. Each of these
behaviors senses its environment and acts on it directly in pursuit of its
own agenda. That is, each behavior, together with its senses and effectors,
is an autonomous agent (Franklin and Graesser, 1996). Each behavior acts
so as to increase it "pleasure" and to minimize its "pain."
Though each behavior samples the environment and can be aware of which legs
are on the ground and which not, no behavior communicates with any other.
Yet they learn to coordinate their actions and walking emerges.
Another robotic example of coordination without communication was modeled
on the behavior of ants (Deneubourg et al, 1990). Noting that dead ants
were carefully removed from an ant colony's nesting area, an entomologist
strewed the area with several thousand dead ants. On the following day he
observed numerous small piles of dead ants. The second day after strewing
brought a smaller number of large piles. By the third day there was only
one (or sometimes two) piles. He conjectured that a probabilistic explanation
of this behavior as follows: Faced with a dead ant, an ant picked it up
with probability inversely proportionate to the number of other dead ants
in the vicinity. While carrying a dead ant, an ant put it down with probability
directly proportional to the density of dead ants in the vicinity. Thus
the coordinated behavior of piling dead ants in a single pile resulted from
a simple local rule controlling the behavior of a single ant. The piling
behavior is accounted for without postulating communication between the
ants.
Hoping to model this complex global behavior emerging from simple local
rules, Beckerts, Holland and Deneubourg (1994) produced small, puck-piling
robots. Picture a fifteen to twenty foot in diameter circular area inhabited
by two or three shoe box size robots and very many hockey-puck sized wooden
discs, uniformly distributed. Each robot is equipped with a scoop in front.
When turned on, a robot moves forward until it accumulated three discs in
its scoop, at which time it backs up, turns in a random direction, and again
moves straight ahead. Hitting a wall also produces this backing and turning
behavior, as does sensing (infrared) an impending collision with another
robot. This simple local behavior results in global behavior modeling that
of the ants, going through the stages of many small piles of discs, fewer
larger piles, and eventually a single pile. All this again with no communication
between the robots. The robots essentially ignore each other except for
avoiding collisions. A single robot will go through the same stages of piling
up discs.
Observing the nest-building behavior of termites led entomologist P. P.
Grassé (1959) to define the notion of stigmergy, referring to actions
of one agent being influenced by the effects of prior actions of other agents.
Here's a description (Beckerts, Holland and Deneubourg, 1994, page 181)
of the kind of collective, coordinated behavior that led to this concept.
When they start to build a nest, termites modify their local environment
by making little mud balls and placing them on the substrate; each mud ball
is impregnated with a minute quantity of a particular pheromone. Termites
deposit their mud balls probabilisticly, initially a random. However, the
probability of depositing a mud ball at a given location increases with
the sensed presence of other mud balls and the sensed concentration of pheromone.
The first few random placements increase the other termites probability
of putting their loads at the same place. By this blind and random game
little columns are formed; the pheromone drifting across from neighboring
columns causes the tops of the columns to be built with a bias towards the
neighbouring columns, and eventually the tops meet to form arches2, the
basic building units.
Clearly we've just seen a description of coordinated behavior. But what
of communication? Here we must face the issue dodged above. Is the impregnating
of mud balls with pheromone signaling with intent to communicate? It's certainly
signaling, even to being arbitrary in that it signals other termites and
not a passing ant or bee. And, one might well postulate an unconscious intent
to communicate evolved into the termite. But is it communication in the
sense of our opening example of taping the mother's day banner to the wall?
I think not. In that case the intent of the communication was to plan the
coordinated action. I also wrongly attributed to the lionesses communication
with the intent of planning their coordinated behavior. In the case of the
termites no plan of coordinated action results from their communication,
rather the carrying out of an evolved-in plan. The example of the termites
requires that I refine my already narrow notion of communication, as used
here, to mean communication with the intent of planning coordinated behavior.
With this clarification, nest-building termites exhibit coordination without
communication.
Nest-building behavior of termites is the prototypical example of stigmergy.
Which of our other examples of coordination without communication could
be classified as stigmergic behavior? Holland and Beckers (1996) distinguish
between cue based stigmergy and sign based stigmergy, the behavior of the
termites being an example of the second and that of the cemetery filling
ants of the first. Pheromones serve as a sign to termites while ant corpses
cue ants. The puck-piling robots modeled after the ants also exhibit cue
base stigmergy. I suspect that shoe tying by the Hence twins is also cue
based stigmergic. The two-person Labyrinthspiel seems almost the epitome
of cue based stigmergy. How about the lionesses preying on the wildebeest?
It seems plausible that the lioness circling into the woods was cued by
the lioness creeping forward in the ditch, and that those on the termite
mounds were cued by the first two. A timeline of the actions comprising
this scenario would be helpful in judging how plausible.
I've conjectured above that a single human tying a shoelace is coordination
without communication. Now I'd classify this behavior as a case of cue based
stigmergy. But what of that human learning to tie shoes? I'd suspect that
conscious planning of the sequence of actions happens. I'm tempted to call
this central nervous system coordination internal communication between
the brain structures controlling the two hands.
So far we've explored a rather diverse collection of examples of coordination
without communication. So what? What are the conclusions? What can we learn
from these scenarios? One obvious observation is that coordination, with
or without communication, is a property of multiple agent systems. Another,
originally less obvious to me, is that coordination without communication
is both common and useful in such multi-agent systems. Yet another is that
repeated and frequent sampling of the environment, and responding thereto,
is the underlying mechanism of such coordination. The act of responding
can be a cognitive one involving prediction, avoidance of pain, etc. This
sampling and responding would include both sign based and cue based stigmergy.
A final conclusion would have us consider stigmergic coordination without
communication as a control architecture when designing multi-agent systems,
be they robots, software agents, artificial life agents, or whatever.
Another conjecture I'm tempted to make is that common long-term goals on
the part of the agents are required, although short-term goals can differ
as exemplified by the Hence twins tying there shoes. But here's a shot at
a counterexample. Let's alter the puck piling scenario described above in
two ways. First, each disc will leave some sort of a trail as it moves.
And second, an additional class of robots will be present who avoid discs
and other robots and remove any disc trails they come across. Coordinated
behavior sans communication will occur, but the long term goals of the two
classes of robots will be different. One creates a puck cemetery, the other
produces a clean floor.
Do note that the issue of common goals is not always a concern of the agents
in a multi-agent system. In many of the systems we've described each agent
is driven only by its local goals. In the case of the puck-piling robots,
each robot is only interested in avoiding other robots and backing and turning
after encountering an obstacle. The piling up of discs is purely a side
effect. An outside observer would describe their global behavior as puck-piling;
the individual robot wouldn't. But to a designer of multi-agent systems,
this issue is immaterial. It's common in computer science to base a system's
behavior on side effects.
This leads us back to the issue of stigmergic coordination without communication
as a control architecture for multi-agent systems. Why should a system designer
consider such an architecture? To possibly save computing resources. Communication
is expensive, requiring additional architecture, and more intelligence.
Planning is expensive in these same ways, and computationally as well. If
a system can accomplish its tasks without communication and planning, so
much the better. Sampling the environment and responding to it is required
in any case. Evolution seems to have come to this same conclusion in many
instances, as we've seen.
Agre and Chapman offer a substitute for planning, participatory improvisation
(1987, p. 2). "Improvisation, like Planning, involves ideas about what
might happen in the future. Improvisation differs from Planning in that
each moment's action results, effectively, from a fresh reasoning-through
of that moment's situation." (They capitalize "Planning"
to denote the formal making of plans. On the other hand, their use of "reasoning-through"
should be read as consideration, not as indicating some inference in a formal
logic.) While improvisation is well beyond the reach of some of the systems
we've discussed, say the puck-piling robots, it fits well in others, say
two-person Labyrinthspiel.
Let me conclude by suggesting an experiment that could shed light on one
of the conjectures made here. The conjecture is that central nervous system
coordination (internal communication) plays little role in such activities
as tying one's shoes or playing Labyrinthspiel. An experiment which compared
learning times for one-person Labyrinthspiel with learning times for two-person
Labyrinthspiel (neither player having previously played) should provide
evidence for or against.
Acknowledgments: I'm grateful to Lloyd Partridge, Michele and Kaveh
Safa, and to participants in the Cognitive Science Seminar at the Institute
for Intelligent Systems of the University of Memphis for helpful discussions
of these ideas.
References:
Agre, Philip E., and Chapman, David. (1987). "From Reaction to
Participation." MIT Artificial Intelligence Laboratory.
Beckers, R., Holland, O. E. and Deneubourg J_L (1994). "From Local
Actions to Global Tasks: Stigmergy in Collective Robotics," in R. Brooks
and P. Maes eds. Artificial Life IV, Cambridge, Mass.: MIT Press, 181-9.
Brooks, Rodney A. (1989). "A Robot That Walks: Emergent Behaviors from
a Carefully Evolved Network." Neural Computation, 1: 253-62
Deneubourg, J. L., Goss, S., Franks, N. R., Sendova-Franks, A., Detrain,
C., and Chretien, L. (1990). "The Dynamics of Collective Sorting: Robot-like
Ants and Ant-like Robots." In Meyer, J-A, and Wilson, S., eds, Simulation
of Adaptive Behaviour: from animals to animats, Cambridge, Mass.: MIT Press,
356-65.
Franklin, Stan (1995). Artificial Minds. Cambridge, Mass.: MIT Press.
Franklin, Stan and Graesser, Art (1996). "Is it an Agent, or just a
Program?: A Taxonomy for Autonomous Agents," Proceeding of the 3rd
International Workshop on Agent Theories, Architectures, and Languages,
Springer Verlag
Grassé P. P. (1959). "La reconstruction du nid et les coordinations
inter-individuelles chez Bellicositermes natalensis et Cubitermes sp. La
theorie de la stigmergie: Essai d'interpretation des termites constructeurs.
Ins. Soc., 6, 41-83.
Griffin, Donald R. (1984). Animal Thinking. Cambridge, Mass.: Harvard University
Press.
Holland, O. E. and Beckers, R. (1996). "The Varieties of Stigmergy:
Indirect Interaction as a Control Strategy for Collective Robotics."
Robotica. Forthcoming.
Maes, Pattie, and Brooks, Rodney A. (1990). "Learning to Coordinate
Behaviors." In Proceedings of the Eight National Conference on Artificial
Intelligence. Menlo Park, Calif.: AAAI. 796-802
Footnotes:
1Though "velocity" is commonly used as a synonym for speed, in
physics it's a vector including both speed and direction.
2I seem to recall that the movement from post and lintel architecture to
true arches was considered a hallmark of human civilization rising to a
higher level.
Email to Stan Franklin