[Computational Complexity] Multi-Agent Biological Systems and Nat Algorithms ...
- Guest Post from Aaron Sterling)
Multi-Agent Biological Systems and the Natural Algorithms Workshop
I attended the Natural Algorithms Workshop on November 2nd and 3rd. This was an event held by the Center for Computational Intractability in Princeton (which brought us the Barriers in Complexity Workshop). Bernard Chazelle was the organizer.
Chazelle is interested in applying complexity-theoretic techniques to the mathematical modeling of biological systems. Recently, Chazelle applied spectral graph theory, combinatorics of nondeterministic computation paths, and other techniques, to obtain upper and lower time bounds on two representative models of bird flocking. (Control-theoretic methods, e.g., Lyapunov functions, had obtained only an existence theorem the models converge without providing time bounds.) Chazelle's Natural Algorithms won the Best Paper Award at SODA 2009. (I found the SODA paper hard to read, as it moves through multiple difficult techniques in a compressed fashion. I recommend reading the first thirteen pages of this version instead, to get a sense of what he's doing.)
While computational complexity's entry into this field may be new, other areas of computer science have much longer-standing connection to multi-agent biological systems. A notable example is the work of Marco Dorigo, whose ant colony optimization algorithm has been influential. Dorigo's research group won the AAAI video contest in 2007; their video is a lot of fun to watch.
Back to the Workshop! The speakers were from diverse backgrounds (control theory, robotics, biology, distributed computing, mechanical engineering), and the talks were great. For reasons of space, I'll limit myself to summarizing one talk I found particularly exciting.
Magnus Egerstedt, a roboticist at Georgia Tech, talked about dolphin-inspired robot algorithms. He explained how dolphins feed. They use three basic strategies. In the first, a group of dolphins swims circles around a school of fish, in a formation called a carousel. Once the fish are well trapped by the carousel, the dolphins swim through the school one at a time to eat. The second strategy involves swimming on either side of the fish to herd them in a particular direction. The third involves physically pushing the fish from behind, either into a waiting group of dolphins, or onto dry land. Egerstedt showed a video of dolphins beaching themselves so they could push fish onto the sand. These feeding strategies demonstrate team effort, despite (presumably) limited ability to communicate. As one example, the dolphins have to take turns to feed during the carousel, or the entire strategy will be ruined. Egerstedt's group has used the behavior of dolphins to inspire several multi-agent algorithms. Here is a recent technical paper of theirs that was dolphin-inspired.
All the talks were videotaped, and are supposed to be on the Center's web page soon.
As a final note, Chazelle has written a followup paper to Natural Algorithms, and will be presenting it at ICS in January. There's no online version yet, but the abstract says the paper fits within a larger effort to develop an algorithmic calculus for self-organizing systems. With a battery of tools available, we might see quite a bit of TCS activity in this area over the next couple years.
Posted By GASARCH to Computational Complexity at 11/10/2009 11:11:00 AM