Chris posted some cool questions on my earlier post about decentralized behavior in social insects:
so what kinds of things do computer scientists do w/this idea? is sort of what evolutionary computing is about? i picked up the evolution of cooperation recently (tit for tat wins prisoner’s dilemma) you must be familiar w/this, yes?”
There’s really three different (but related) ideas in this question:
- Decentralized and emergent behavior
- Evolutionary computation
- Game theory and cooperation
I’ll take them one at a time, with more on the first of the three, at least for now.
Decentralized and emergent behavior
People in computing are still trying to figure out how to best use the amazing things that we’re learning about critters like social insects. Probably the most promising application area is where you need flexible autonomous agents that don’t require some sort of central control.
One of the easiest examples would be robot exploration of a distant planet like Mars. Communication between here and there is slow enough that if you rely on control from Earth (as we currently do), things move very slowly. If, on the other hand, you “let them loose” there is a real risk that they’ll fall off a cliff or get stuck on a rock or whatever, and the process of replacing them is a lot slower (and more expensive) than the process of controlling them from here. An alternative, though, is to send a lot (dozens, maybe hundreds) of small and (relatively) cheap robots that work independently. In this scenario you expect to lose some, but count on enough surviving that you still accomplish the primary task. So instead of sending the great, lumbering Lost in space robot, you send a swarm of robotic ants, planning to lose a some (like worker ants) but doing great things in aggregate.
And this isn’t just a science fiction exercise. There are very real military applications of these ideas; imagine a hoard of reconnaissance robots, for example, in a battle theatre. You have to presume you’ll lose some of them, and you can’t have them depend on a single central control as that would present a serious weak point. There are also people exploring applications of these ideas for tasks like cleanup in extremely hazardous environment such as Chernobyl. Out on the edges of the spectrum, you have people proposing swarms of micro- or nano-devices, none of which are very smart, but which can in aggregate accomplish significant tasks.
One vision I’ve daydreamed about for several years, for example, would be replacing the massive combine harvester style of agriculture with a swarm of little “agribots”. These could handle things like planting, weeding, pest control, and potentially even harvesting without the need for huge expensive machines or grinding physical labor. One thing this could allow is the use of highly mixed plantings instead of the massive, fragile mono-cultures that define most of modern agriculture. Highly mixed plantings are essentially impossible in the current state of industrial agriculture, which favors vast fields of uniform crops, but were very common in pre-industrial agriculture.
At some level there’s a serious conflict between these approaches to problem solving and traditional computing. Most computer science is built on notions of precision and exact reproducibility. When you sort a list, for example, you want to sort a list in an exact and predictable way. It’s hard to predict with any precision the behavior of distributed systems with no centralized control. You can say things about their general behavior (they “tend” to do this or that), but it’s hard to perform any sort of exact analysis. This has made it hard to sell these ideas in certain quarters, especially if people want or need some level of precise understanding.
Evolutionary computation
These kinds of decentralized, distributed systems are not inherently connected to the area of evolutionary computation (EC), although EC is often used to to aid in the programming them.
In EC you evolve an (often approximate) solution to a problem. You typically start with a randomly generated collection of potential solutions to a problem. Some of these are better solutions than others, so you pull out the best and mutate and/or recombine them in some way to generate a new population. Again, some of those are better than others, so you use the better ones to make a new population. This process is repeated until either a reasonable solution is found, or you get bored and try again.
This can work very well in certain circumstances, usually where (a) you’re OK with an approximate solution (evolution is best at producing solutions that are “good enough” rather than “perfect”), (b) you’re working in a domain that we don’t understand well (there’s no point in goofing around with evolving approximate solutions if we have tools that provide exact solutions), and (c) you do have a good way of judging the quality of solutions (without which you can’t decide who are the “winners” in the evolutionary process).
EC is used in a whole host of settings, some of which are very cool. (There was a great example a few years ago of evolving a satellite antenna which I could say some more about if folks are interested.) Writing programs to control highly distributed, decentralized systems remains a very challenging problem, but we can often measure how well a swarm of agents solves a problem even if we don’t really understand how they accomplish the task. Consequently EC is often at least one of the tools that is considered when developing distributed, decentralized multi-agent systems.
Game theory and cooperation
The prisoner’s dilemma problem has long since been a favorite of mine, and I could blather on about it at great length. Sticking to the general theme here, however, it’s a nice example of a problem where the agents involved have to make decisions without being able to coordinate or communicate beforehand.
I’m definitely aware of (and highly recommend) Axelrod’s Evolution of cooperation and his other work on the prisoner’s dilemma problem; it’s easy to over-interpret some of the ideas in his book, but there is still much to be said there about cooperation, trust, and responding to threats. Hofstadter also has an nice discussion of this and a host of related problems in several chapters of Metamagical themas.
The evolution of cooperation has long been (and remains) a central question in biology as well as in evolutionary computation. Prisoner’s dilemma has, as a result, been a subject of considerable study in the EC community. It (along with numerous other examples from game theory) has also formed the basis of numerous EC studies in areas such economics and market studies.
Thanks to Chris for the excellent questions!
