The Birds and the Bees Revolutions
Swarms and Multiagent Systems
Michael Crichton published his novel Jurassic Park in 1990 and the screenplay was made into a blockbuster movie in 1993. The science-fiction thriller introduced the populace to the topics of genetic engineering, cloning, and related biotechnologies that, a scant decade later, have become the subject of science-fact laws and regulations governing these areas of research. Crichton’s 2002 novel PREY is poised to have the same effect on nanotechnology and multiagent systems. If you are interested in future technologies of optimization, network routing, fault location, distributed manufacturing or data mining I highly suggest you stop by the bookstore on your way home and pick up a copy of this bestseller.
The technology leveraged in PREY represents the next level of complexity in evolutionary programming described in the previous two installments of this column. After an appropriate computational framework is achieved through genetic algorithms, learning and reasoning in individuals can be developed using artificial neural networks (ANNs). As in nature, intelligent entities often coalesce into societies such as flocks, colonies, hives, schools, packs, tribes and cultures for mutual protection, food, and comfort. In addition to the communal benefits enjoyed by each member, groups comprised of individuals having limited ability can perform remarkable tasks through synergy; a concept in systems science known as an emergent property.
Teamwork and cooperation are abilities we emphasize to our children early in life. Athletics, music, and drama programs impart the importance of group effort above and beyond the level of individual excellence. While it is an honor to be selected for the All-Star game, a collection of best athletes often performs at a level beneath the lowest team in the league. Without weeks of practicing together, the emergent property of cooperative execution is not expressed.
Similar to the modeling of ANNs after neuron physiology in the brain, Professor Marco Dorigo of Université Libra de Bruxelles, Belgium, has lead the development of emergent multiagent systems based on the behavior of ant colonies. Entomologists have chronicled the behavior of ants while foraging for food, nest building, regulating nest temperature, and sorting eggs and larvae; all emergent behaviors performed by the entire colony without the direction of a centralized manager. When foraging for food, the collection of ants efficiently discovers the shortest route to the best food supply with no advanced knowledge of the surrounding terrain. Rather than communicating back to a central high-level authority assigned the task of mapping the environment, individual agent ants perform their duties with a small set of simple rules.
Upon leaving the nest, each ant secretes a chemical trail of pheromones as it travels in search of food. When faced with an obstacle, the ant chooses a direction at random and continues until it finds something tasty. The ant grabs its prize and then follows the pheromone trail back to the nest while laying down a second layer of the chemical. Additionally, when faced with a choice of direction, ants are programmed to follow the strongest pheromone trail. Ants that have returned to the nest with food have reinforced their pheromone-laden path, thereby increasing the likelihood that subsequent foragers will follow the successful trail. The most direct paths will be reinforced at the highest frequency and, for this reason, will carry the heaviest traffic. If an obstacle such as a fallen leaf disrupts the trail, the ants will revert to a random choice of direction around the roadblock. Returning ants trapped on the other side of the new obstacle also will try multiple directions and the shortest path will be the first to reconnect the trail and provide a pheromone track for the outgoing agents to follow. The volatile chemical dissipates over time causing incorrect or outdated paths to be abandoned.
Professor Dorigo and his colleagues have applied this method of path finding to the Traveling Salesman Problem (TSP) with great success. Swarm Intelligence (as it is known) is currently used to route network traffic. Utilizing the timestamp carried by each information packet, the shortest route between nodes can be determined and new routes can be found around the location of transmission line failures or congestion.
AgentLink, the recently launched network of European agent technology researchers located [now] at http://www.fipa.org/, has posted a road map of predicted agent developments. Initially limited to internal agent systems operating with predefined rules and protocols, the organization sees cross-boundary and open system agents navigating between corporations and governments utilizing learned protocols and emergent languages in as little as five years. If Hollywood plans to bring Crichton’s latest fictional story to the big screen, they had better act now before it becomes a documentary.
This material originally appeared as a Contributed Editorial in Scientific Computing and Instrumentation 21:5 April 2004, pg. 12.
William L. Weaver is an Associate Professor in the Department of Integrated Science, Business, and Technology at La Salle University in Philadelphia, PA USA. He holds a B.S. Degree with Double Majors in Chemistry and Physics and earned his Ph.D. in Analytical Chemistry with expertise in Ultrafast LASER Spectroscopy. He teaches, writes, and speaks on the application of Systems Thinking to the development of New Products and Innovation.
