|Foresight Update 41 - Table of Contents|
Special thanks this issue go to Foresight Senior Associate (and hero) Dave Krieger. We have needed a Slashdot-style discussion forum desperately Dave made it happen. You'll be hearing a lot more about this; meanwhile join the gang at http://nanodot.org. Bravo also to Senior Associate Jeff "Hemos" Bates for cofounding the Slashdot open source project and website.
For our small organization, the effort required to put on the experimental-format Spring Gathering is monumental. Most of this was shouldered by Tanya Jones, this spring's chairperson. Based on participant comments, the net result was wonderful: brava, Tanya.
Another major player was iteration's Matt Taylor, lead facilitator of the DesignShop portion of the meeting, whose work with Gail Taylor along with their donation of immense resources has led to this unusual meeting series. Our first corporate sponsor for a Gathering, Technanogy, helped finance this event as part of Engines of Creation 2000: thanks to Larry Welch and Cory Alder.
Many others helped make the meeting a success everyone who came helped but special mention must be made of Greg Burch, Yakira Heyman, Robin Hanson, Chris Hibbert, Dick Karpinski, Paul Melnyk, Mark & Judy Muhlestein, Ed Niehaus, Eric Raymond, Marcia Seidler, Carol Shaw, Dean Tribble, Elaine Tschorn, and the Stanford School of Business Futurist Club. Robert Grudin brought some non-technical wisdom and even gravitas to the event; thanks for coming, Robert.
In memoriam: our colleague and partner in open source software projects, Alexander "Sasha" Chislenko, died just before the Gathering. His many friends, including others at his company 100x, resolved to carry on his work. We made a start at the Gathering, where Foresight members got to meet four representatives from 100x, including leader Ken Lang. Thanks and kudos will go forever to Sasha for his visionary work in social software.
Due to a merger followed by poor service, we had to change ISPs. Thanks to Carol Shaw and Jim Lewis for pulling us through this painful change, with key assistance from Peter McCluskey.
Thanks as always to everyone who sent (paper) articles of interest. Please keep sending these when they are only available on paper, but if you can find the same article on the web, it's better to post it directly to nanodot, thereby avoiding the bottleneck here at the office.
We can never thank our webmaster, Jim Lewis, enough, but let's keep trying.
Christine Peterson, President, Foresight Institute
|Foresight Update 41 - Table of Contents|
by E. Bonabeau, M. Dorigo, and G. Theraulaz
(in the Santa Fe Institute's Sciences of Complexity series)
Oxford University Press, 1999
Softcover; 307 pages. ISBN 0-19-513159-2
reviewed by J. Storrs Hall, Research Associate
Institute for Molecular Manufacturing
A few years ago I gave a talk at NASA Ames about Utility Fog. The main thrust of the talk was a description of the flow patterns in the mass of microscopic robots that would be necessary to allow the mass to change shape or to have objects move through it unimpeded. This was complicated beyond normal fluid flows by the fact that at a certain level the motion changes from continuous to discrete, so the talk involved a lot of descriptions of how the robots would clamber over each other, do the 3-D equivalent of lane merges, and so forth. At the talk ended and people were leaving, one audience member, a software researcher, remarked, "You'll never convince me that central control will work for that."
I had no answer for him, and it was because I had left unaddressed the really hard problem, which was how to obtain the physical motion patterns I had worked out from a distributed control algorithm. In my defense I could only plead that nobody else knew how to do it, either.
Things are beginning to change. Ever since John Holland's seminal "Adaptation in Natural and Artificial Systems" in 1975, to which the authors give a nod in their title, there has been a slowly growing subcurrent in computer science of algorithms which achieved some overall goal or optimization by simulating some population of simple agents or organisms. Genetic and agoric algorithms have gained significant ground in the past decade, not least because the processing horsepower necessary to run them has become affordable.
Those wishing a quick introduction to the subject covered by Swarm Intelligence may wish to read the cover article in the March 2000 issue of Scientific American by two of the authors and titled "Swarm Smarts."
Swarm Intelligence centers on the technique of adapting models of the interactions of social insects, particularly ants, to distributed algorithms for solving various problems. The authors start with problems similar to the ones the ants actually solve, such as finding efficient paths from a nest to various sources of food. As you read, you will learn about ants as well as algorithms. One of the more interesting things ants do in food searches is to leave pheromone trails along their paths, which are either reinforced as other ants find the paths useful, or fade from disuse.
This is a case of a general phenomenon or technique known as "stigmergy". Stigmergy is a general form of communication or organization in which one ant (or agent or robot) modifies the environment and the other(s) modify their behavior in response to the change. Stigmergy and self-organization are (by the authors' explicit claim) the central concepts of the book.
One of the nice things about the way the authors explain things: they will first explain, often with graphs and diagrams, how ants do something, then give you the algorithm the authors are modelling each ant as using in the behavior (in a pseudocode detailed enough that you could program it in your favorite language if you wanted), and then show you how the algorithm worked out in simulation.
In the first few chapters, they cover a number of ant behaviors and tasks, ranging from path optimization to resource and task allocation to structure building. These range in generality from simulated food-finding to solving traveling salesman problems. By the end of Chapter 4 they are describing clustering of hockey pucks by crews of toy-sized robots.
The next few chapters involve building structures, ranging from ants' nests to configurations of 3-dimensional cellular automata using "discrete stigmergy." There is a very nice section on self-assembling robots of various designs; I only wish it had been longer. The final (substantive) chapter is about cooperative transport, again starting with ants and going on to robots pushing boxes.
My only disappointment with the book is that while the authors tend to give pseudocode algorithms for the simulated ants and the cellular automata, they don't give them for the robots. It's clear that that's because they are describing the work of others, but it would have been useful.
Although ants have been studied for centuries, the field of swarm robotics is still in its infancy. It is likely to become much more important quite rapidly, as the robot population increases over the next few decades. With the advent of molecular manufacturing, it will become a critical part of the technological base, as one of the major methods by which microscopic robots build, extend, modify, and maintain macroscopic mechanisms and structures.
For those interested in the subject from the robotics point of view, I would also recommend Behavior-based Robotics by Ronald Arkin (MIT, 1998), and Mobile Robots by Jones, Flynn, and Seiger (Peters, 1999). If you want to study ants, you're on your own!
More information on the Swarm agent simulation system can be found at the Swarm Development Group website (http://www.swarm.org). The site has extensive resources, including source code and a bibliography.
The Agent Web site (http://agents.umbc.edu/) maintained by the University of Maryland, Baltimore County, is an excellent jumplist of links and resources related to agent-based computing and robotics.
From Foresight Update 41, originally published 30 June 2000.
Foresight materials on the Web are ©1986–2014 Foresight Institute. All rights reserved. Legal Notices.