[back]

Labor Division and Distributed Sensing in Swarm Systems
William Agassounon, Alcherio Martinoli
Collaborators: Robert McEliece (Caltech), Erik Antonsson (Caltech), David H. Lewis (TRW), Willy Behrens (TRW), Guy Theraulaz (CNRS, Toulouse, France), Deborah Gordon (Stanford), Jean-Louis Deneubourg (ULB, Bruxelles, Belgium).

Abstract. This research project aims to devise distributed scalable control algorithms for division of labor and task allocation in mobile embedded swarm systems. Our approach is inspired by social insect societies (ants, bees, termites, etc) whose collective behavior often emerges from a series of local agent-to-agent and agent-to-environment interactions. We are currently developing response threshold-based algorithms to achieve efficient and robust division of labor, and probabilistic models that provide accurate forecast of the resulting collective behavior. These swarm systems are therefore analyzed at several implementation levels, from macroscopic and microscopic probabilistic models to real robot experiments through embodied sensor-based simulations.

Motivation. Recent studies on social insects have shown that complex control can emerge due to local interactions between agents and between agents and the environment. In particular, any useful task to the survival of the colony can be accomplished without any need for a central task planning or task assignment unit. The overall behavior of these colonies has been shown to be based upon simple local rules of distributed sensing, communication, and action. For instance, the number of agents allocated to each task is controlled through local decision-making rules based upon the needs of the colony, the changes in the environment, and the availability of work. Our goal is to apply these biologically inspired rules to autonomous embodied agents or robots to create groups of individuals capable of controlling the division of labor within the group based solely on their local estimations of the availability of work. This will allow the team to optimize the use of resources (energy, mechanical wear and tear, etc) as well as, if several tasks have to be carried out simultaneously, to create specialists for each task and in turn enhance the efficiency of the team as a whole without the use of any external supervisor.

Research. Traditional approaches to task allocation problems have mainly focused on the study of the quantitative response of groups of autonomous robots to demand for work from different tasks. Current literature shows either solely theoretical approaches to the study of the demand-task relationship [Pacala et al., 1996 and Bonabeau et al., 1998] or experimental work with strong constraints (e.g. existence of a global supervisor) and lacking theoretical framework [Billeter and Krieger, 2000]. Moreover, none of the theoretical approaches has ever taken into consideration the partial perception in time and space of the demand and the environment. In our collective system, the 'propensity' for any given agent to act is given by a response threshold that takes into account many environmental variables. If the demand is above an agent's threshold then that agent continues to perform the task, conversely if the demand is below its threshold then the agent stops performing that particular task. The thresholds can be either fixed or variable over time, adapted through a learning algorithm. The demand can be estimated individually or via information sharing with other teammates.

Achievements. The first case study we used for evaluating the efficiency of the distributed worker allocation algorithms is concerned with the gathering of small objects scattered in a square arena [Martinoli 1999]. In past research, the size of working robots was kept constant during the whole aggregation process. These experiments define our baseline for efficiency comparison. Two team performance measurements over time are considered, both based on aggregation: the average cluster size and the average number of clusters. Both performances, which indirectly represent the amount of work carried out by the team, are then integrated in a combined metrics (cost function) with the number of active workers at a certain time. The integrated value of the cost function over the whole observation time corresponds to the total cost for the execution of the task.

Figure 2. Experimental setup: the central red area is to the working zone and the surrounding area is the resting zone (for inactive agents). Left, typical situation at the beginning of the aggregation with 6 agents. Right, typical single cluster situation at the end of the experiment (e.g. 4 h simulated time).

This experiment has been studied at three different experimental levels. In a numerical microscopic model [Martinoli 1999], we describe the experiment as a series of stochastic events with probabilities based on simple geometrical considerations and systematic interaction experiments with a single real robot or embodied agent. We derived an analytical macroscopic model using a set of difference equations to capture the evolution of the aggregation process [Agassounon 2001]. Finally a sensor-based, kinematic simulator (Webots) is currently used as validation tool until real robot experiments will be conducted. Figure 3 and Figure 4 illustrates the good agreement between these different implementation levels for the aggregation experiment in an 80X80 cm arena.

Figure 3. Results of the aggregation experiment with a team of 10 robots without worker allocation.

Figure 4. Results of the aggregation experiment with worker allocation using a team of 10 robots. Left, avg. cluster size and number of clusters over time, right, avg. number of active workers over time.

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

Fixed Response Thresholds and the Regulation of Division of Labour in Insect Societies. E. Bonabeau, G. Theraulaz, and J.-L. Deneubourg. Bulletin of Mathematical Biology, 1998, Vol. 60, pp. 753-807.

A Probabilistic Model for Understanding and Comparing Collective Aggregation Mechanisms. A. Martinoli, A. J. Ijspeert, and L. G. Gambardella. Proc. of the Fifth Int. European Conf. on Artificial Life ECAL-99, September 1999, Lausanne, Switzerland, pp. 575-584.

The Call of Duty: Self-Organized Task Allocation in a Population of Up to Twelve Mobile Robots. M. B. Krieger and J. B. Billeter. Robotics and Autonomous Systems, 2000,Vol.30, No. 1-2, pp. 65-84.

Effects of Social Group Size on Information Transfer and Task Allocation. S. W. Pacala, D. M. Gordon, and H. C. J. Godfray, Evolutionary Ecology, 1996, Vol. 10, pp. 127-165.