[back]

Distributed Collective Building of Two-Dimensional Structures Using Autonomous Robots
Authors: Kjerstin Easton, Alcherio Martinoli Collaborators: Joel Burdick (CNSE, Caltech), Guy Theraulaz (CNRS, Toulouse, France), Dario Floreano (EPFL, Lausanne, Switzerland), Nicolas Reeves (UQAM, Montreal, Canada)

Abstract. Using autonomous robots to build three-dimensional structures is a distant goal, but the first step in approaching collective building is to construct two-dimensional architectures. Using a team of miniature Khepera robots with manipulation and vision capabilities, we will implement a building technique modeled after qualitative stigmergic construction mechanisms used by social insects. This technique will allow the robots to communicate building instructions through modifications to the local environment, avoiding dependence on explicit robot-to-robot communication and lending itself to implementation with any number of robots.

Motivation. As society demands increasing autonomy and complexity of artificial systems, engineers often look to nature for a possible model. Social insects, which with their limited structures and communication capabilities coordinate to construct large and complex nests [Bonabeau, 2000], provide one such analogy to the potential of collective robotics systems. Stigmergic nest-building techniques used by many types of social insects are an example of behavior that, once adapted to artificial systems, could have useful applications in human society. Though a group of specialized robots might someday build structures where humans could not, we must as a foundation first develop a robust collective construction technique.

Research. A stigmergic agent's action is determined by the environmental modifications of other agents' prior actions (Figure 1). In quantitative stigmergy, the stimulus is a continuous variable, the value of which modulates the intensity or probability of an action taken. Qualitative stigmergy differs in that the stimulus is discrete and the action is not modulated, it is switched to a different action altogether.

Figure 1. Quantitative stigmergy example (left)-aggregation of ant corpses behavior in ants (Messor sancta) in which the probability of dropping an ant corpse is modulated by pheromone concentration around the cluster. Qualitative stigmergy example (right)-cutaway wasp nest (Epipona tatua), built cell by cell in a modular structure. The probability of creating a cell is determined only by the local environmental configuration. Stimuli and response are qualitatively different for different environmental configurations. (Pictures courtesy of Guy Theraulaz)

Since we do not use chemical deposition for stigmergic communication in robots, our purposes are best suited to qualitative stigmergic mechanisms that rely only on local environmental modifications that in turn trigger specific actions carried out by agents. "Micro-rules" define action-stimuli pairs for an agent; a set of all micro-rules used by a homogeneous group of stigmergic agents defines their behavioral repertoire and determines the type of structure the agents will create. When a team of agents is simulated, the successive changes to their environment result in an architecture. "Nest," a non-embodied, qualitative stigmergic-agent nest-building simulator described in [Bonabeau, 2000] generates such structures in both two and three dimensions. We have expanded this simulator to include a more robust genetic algorithm for exploring constraints imposed on structures by rule complexity, compass, sensor space, and architecture size. This is the first step toward developing a tool to reverse-engineer structures to find their corresponding micro-rule algorithms. Along with the embodied simulations of the Khepera robots in Webots, this non-embodied two-dimensional simulation and analysis tool is useful in exploring the differences in robot performance in the real world due to noise, friction, embodiment and different implementations of micro-rules.

Figure 2. Serpentine cluster resulting from aggregation behavior [Martinoli, 1999].

Martinoli's aggregation algorithm, which uses two micro-rules (Figure 2, 3 left), was used as a basis for a new aggregate algorithm: building straight rows of evenly-spaced cylindrical "seeds." This new algorithm is successful in Webots simulation (Figure 3 right) and is inspired by the sensorless manipulation techniques used to position an object accurately within a parallel-jaw gripper in assembly and manufacturing. [Rao, 1996] The next step is an experiment with real robots, which, because the experiment will exceed the robots' 20-minute autonomy, will require Kheperas equipped to run on a powered floor. Each Khepera will be programmed with the same set of micro-rules and, upon encountering a stimulating seed configuration, will deposit a seed. With a straight-line-building capability, building more complex multiple-rule structures becomes feasible. Adding vision capabilities to the Khepera robots will allow the robots to use more complex micro-rules, providing color distinction among seeds and a greater sensor space than the Khepera's proximity sensors alone.

Figure 3. Serpentine cluster resulting from Martinoli's aggregation behavior (left) and straight-line clustering (right) as simulated in Webots.

In addition to testing different sets of micro-rules both in simulation and with real robots, there are several other research thrusts we would like to explore:

Further development of evolutionary techniques for improving target structure to micro-rule translation
Effect of team size on the efficiency of construction
Effect seed shape on structure stability
Effect of probabilistic micro-rules on structures
Effect of heterogeneous teams of robots on construction

References
A Scalable, Distributed Algorithm for Allocating Workers in Embedded Systems. W. Agassounon, A. Martinoli, and R. M. Goodman. Proc. of the IEEE Conf. on System, Man and Cybernetics SMC-01, October 2001, Tucson, AR, USA, pp. 3367-3373.

Three-dimensional architectures grown by simple 'stigmergic' agents. Bonabeau, E., Guerin, S., Snyers, D., Kuntz, P., Theraulaz, G., BioSystems 56, 13-32, 2000.

A Probabilistic Model for Understanding and Comparing Collective Aggregation Mechanisms. A. Martinoli, A. J. Ijspeert, and L. G. Gambardella. In D. Floreano, F. Mondada, and J.-D. Nicoud, editors, Proc. of the Fifth Int. European Conf. on Artificial Life ECAL-99. Lectures Notes in Computer Science, pp. 575-584, Lausanne, Switzerland, September, 1999.

Computing Grasp Functions. A. Rao, K. Y. Goldberg. Computational Geometry Theory and Applications, pp. 145-168, 1996.