New SWIS Army
Developing collective intelligence
This past spring, my family and I spent the long Memorial Day weekend at a campground in rural Lancaster County, PA. As the unofficial start of summer, many families head “down the shore” for some sun, sand and beach fries, while we prefer the less hectic pace of horse-drawn buggies,
 |
swimming and Hershey’s s’mores. While my son and I were rigging our lines for fishing in a small pond, he noticed a large number of tadpoles teaming near the water’s edge. As we approached them, they spotted our shadows and swam into deeper water, only to be terrorized by roaming sunfish that quickly shepherded them to shore. Not wanting to decimate the school of adolescent amphibians, we backed away and discovered an even larger pod of pollywogs in a nearby water-filled ditch. Localized in their relatively safe environment, they were easy to observe and study as they swarmed around in the puddle. The recent rain ensured their nursery had plenty of water, but I hoped the metamorphosis into air breathers initiated well before the arrival of the intense summer sun.
The schooling and swarming of insects and vertebrates has become an area of interesting research known as swarm intelligence (SI) and this column has looked at developments in genetic algorithms (GA), particle swarm optimization (PSO) and other biomimetic technologies of SI. Application of GA and PSO has primarily benefited simulations and control algorithms for the solutions of specific computationally hard problems, such as asset allocation and curve fitting. Recently, Professor Alcherio Martinoli and his Swarm-Intelligent Systems (SWIS) group at École Polytechnique Fédérale de Lausanne (EPFL) in Lausanne, Switzerland have applied SI to an actual swarm of miniature robots (bots). One of the SWIS projects is concerned with the development of a swarm-intelligent inspection system based on a collection of autonomous bots used for the examination of turbine blades within a jet engine. Usually requiring costly disassembly or the use of time-intensive borescopes, a swarm of mobile bots equipped with local sensors conceivably could enter the intact turbine engine and craw along the surfaces of the shaft and blades while collecting sensor readings.
The SWIS team unrolled the axis-symmetric geometry of the turbine into a flat “playing field” having vertical blade-shaped extrusions, in order to remove the technological obstacle of inverted locomotion. Instead of using a system-wide controller that plans the inspection routes and directs the deployment, each bot contains only local sensors for interaction with its environment, and communication with nearby members of the swarm. An onboard controller cycles through an internal finite state machine (FSM) having a default state causing each bot to roam and search for an obstacle. If the obstacle is determined to be a wall or another bot, the state is switched to one that avoids collision. When a blade is found, the FMS switches to circumnavigate the blade. After this task is completed, the bot pauses to transmit a beacon to nearby bots signaling the blade has been inspected, and then switches back to the search state.
More recently, Professor Martinoli and graduate students James Pugh and Nickolaus Correll have studied the efficiency of replacing the FMS with a PSO algorithm. Rather than using the beacon to inform local bots where not to search, each bot can serve as the physical embodiment of a virtual PSO particle using local neighbor optimization. When a blade is found (an optimal location for inspection), the bot communicates the location to its neighbors and the information is used to predict the search direction of additional blades. As bots meet different neighbors, they can communicate and update each other’s knowledge of the entire environment in a fashion similar to human search teams that report their progress to each other. In this way, the knowledge evolves inside the members of the swarm and the bots do not need to expend their limited energy in communication with a distant system controller.
Upon closer inspection, my son and I discovered the ditch was actually a spring head that flowed into the pond, and not stagnant water from a recent storm. In addition to spawning thousands of eggs in the hopes the supply will outlast the appetite of predators, it is evident the frog population benefits from dispersing their eggs throughout their tiny ecosystem in search of more optimal locations. I like to think my family displays similar collective intelligence by avoiding the bumper-to-bumper traffic on the way to the shore.
Bill Weaver is an assistant professor in the Integrated Science, Business and Technology Program at La Salle University. He may be contacted at editor@ScientificComputing.com
