[back]

Modeling Swarm-Based, Distributed Robotic Manipulation
William Agassounon, Kjerstin Easton, and Alcherio Martinoli
Collaborators: Joel Burdick, Kristina Lerman, Wulfram Gerstner

Abstract. We developed a macroscopic modeling methodology for swarm-based, distributed robotic manipulation. The methodology is well-suited for nonspatial metrics as it does not take into account robots’ trajectories or the spatial distribution of objects in the environment. The strength of the proposed models is that they have been built up incrementally, with matching between models and embodied simulations (and sometimes, real robot experiments) verified at each step as new complexity was added. Precise heuristic criteria based on geometrical considerations and systematic tests with one or two embodied agents prevent the introduction of free parameters into the model. Two concrete case-studies were considered. The first case-study, referred to as the aggregation experiment, is a non-collaborative manipulation concerned with gathering and clustering small objects initially scattered in an enclosed arena. The other case-study is involves strictly collaborative manipulation and is referred to as the stick-pulling experiment, as the robots’ task is to collaborate to pull sticks out of holes in the arena floor. Results show that the proposed approach delivers quantitatively accurate predictions, in particular for nonspatial metrics related to both the aggregation and stick-pulling processes, and constitutes a computationally efficient tool. The simplicity of the modeling methodology suggests that it is easily applicable to other experiments characterized by different agent capabilities and individual control algorithms.

Motivation. While Swarm Intelligence principles offer appealing benefits in scalability, robustness, and individual simplicity, they do not provide a way to quantitatively predict swarm performance or analytically optimize experimental parameters. To achieve coordinated, self-organized group behavior based on local interactions, we must develop appropriate tools for understanding how to design and control individual units so the swarm can achieve target behaviors and levels of performance. Models allow the engineer to capture the dynamics of these nonlinear, asynchronous, potentially large-scale systems at more abstract levels, sometimes achieving even mathematical tractability. More generally, modeling is a means for saving time, enabling generalization to different robotic platforms, and estimating optimal system parameters, including control parameters and number of agents in a team.

Research. The central idea of the probabilistic modeling methodology is to describe the experiment as a series of stochastic events with probabilities computed from the interactions' geometrical properties. These properties are measured in systematic experiments with one or two embodied agents. The absolute location of the events in the arena is not considered in the models. The flowchart of the controller of the embodied agent serves as a blueprint for implementing the corresponding models, either microscopic or macroscopic. In the models, the FSM characterizing the embodied agent’s controller becomes a Probabilistic Finite State Machine (PFSM), or Markov chain, whose state-to-state transitions depend on the interaction probabilities of a robot with other teammates and with the environment. While in microscopic models each robot is represented by its own PFSM [Martinoli 1999, Ijspeert 2001], in macroscopic models a single PFSM summarizes the whole robotic team [Agassounon 2001-2002, Lerman 2001, Agassounon 2003, Martinoli 2003], with each of its states representing the average number of teammates in a particular state at a certain time step. In both types of models, the robots' PFSM(s) are then coupled with the environment. This coupling among robots via the environment (or in other experiments, direct peer-to-peer coupling, for example, through explicit communication) shapes the microscopic-to-macroscopic mapping, in particular determining its linear or nonlinear properties. Moreover, in distributed manipulation experiments, the environment can be considered to be a passive, shared resource whose modifications are generated by the parallel actions of the robots. Finally, once the distributed manipulation system is represented by a finite state machine, we describe the dynamics of the variables of the system mathematically using discrete-time models.

Achievements. We validated our modeling methodology, both at the microscopic and macroscopic level, in two different case studies: the aggregation experiment and the stick-pulling experiment. Although these two case studies fundamentally differ on the task the robots have to accomplish and the corresponding dynamics of the environmental modifications, they also share some basic similarities. Indeed, robots are endowed with reactive controller extended with internal timers and the self-organized collective behavior emerges from local interactions among the robots and between the robots and the environment. Furthermore, simple, deterministic time-out mechanisms regulate the activity of the robots in the aggregation experiment while in the stick-pulling experiment, the maximal time a robot may wait for help regulates robot activity. These similarities become quite evident at the model level.

Figure 1. Left: Example of FSM representing the basic aggregation robot controller. Transitions between states are deterministically triggered by sensory measurements. Right: Results of aggregation experiment with worker allocation and groups of 1and 5 robots with 20 seeds in an 80 x 80 cm2 arena. The upper plot represents the average cluster size over time while the lower plot shows the average number of active workers over time. In both plots the results obtained with a realistic simulator are overlapped with the prediction of the corresponding macroscopic model.

First case-study: the aggregation experiment - The aggregation experiment is a non-collaborative manipulation task concerned with gathering and clustering small objects initially scattered in an enclosed arena. In most of the work done so far, the size of the working team was kept constant during the whole aggregation process. By introducing a worker allocation mechanism to the aggregation controller, team efficiency was improved over the results achieved with constant team sizes [Agassounon 2002]. Our modeling methodology was able to quantitatively predict the collective performances characterized by constant and variable team-sizes. In this case study, we used three primary team performance metrics: the average cluster size, the average number of clusters, and the average number of active workers in the environment. Figure 1 illustrates a sample FSM representing an aggregation controller endowed with worker-allocation algorithm and presents selected results.

Second case-study: the stick-pulling experiment - The task is for robots equipped with grippers to locate sticks in a circular arena and to pull them out of holes in the arena floor by collaborating with another robot. Due to the sticks’ length, a single robot cannot pull a stick out of the ground alone; collaboration between two robots is necessary for success [Easton 2002]. In this case study, the primary metric used for assessing the team performance was the collaboration rate, i.e., the number of sticks successfully pulled out per time unit. Figure 2 shows the FSM describing the stick-pulling controller and presents selected results.

Figure 2. Left: FSM representing the stick-pulling controller. Right: Results of embodied simulations, microscopic and macroscopic models for 8, 16, and 24 robots, 16 sticks, and an arena 80 cm in radius.

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

Agassounon W. and Martinoli A. “A Macroscopic Model of an Aggregation Experiment using Embodied Agents in Groups of Time-Varying Sizes”. Proc. of the IEEE Conf. on System, Man and Cybernetics SMC-02, October 2002, Hammamet, Tunisia.

Agassounon, W. and Martinoli, A. “Efficiency and Robustness of Threshold-Based Distributed Allocation Algorithms in Multi-Agent Systems.” Proc. of the First Int. Joint Conf. on Autonomous Agents and Multi-Agent Systems AAMAS-02, Bologna, Italy, July 2002, pp.1090-1097.

Agassounon, W., “Modeling Artificial, Mobile Swarm Systems”. Unpublished Ph.D. Manuscript, Electrical Engineering, California Institute of Technology, 2003.

Easton K. and Martinoli A., “Efficiency and Optimization of Explicit and Implicit Communication Schemes in Collaborative Robotics Experiments”. Proc. of the 2002 IEEE Int. Conf. on Intelligent Robots and Systems IROS-02, September-October 2002, Lausanne, Switzerland, pp. 2795-2800.

Ijspeert A. J., Martinoli A., Billard A., and Gambardella L.M., “Collaboration through the Exploitation of Local Interactions in Autonomous Collective Robotics: The Stick Pulling Experiment”. Autonomous Robots, Vol. 11, No. 2, pp. 149-171, 2001.

Lerman K., Galstyan A., Martinoli A., and Ijspeert A. J., “A Macroscopic Analytical Model of Collaboration in Distributed Robotic Systems”. Artificial Life, Vol. 7, No. 4, pp. 375-393, 2001.

Martinoli A., Ijspeert A. J., and Mondada F., “Understanding Collective Aggregation Mechanisms: From Probabilistic Modelling to Experiments with Real Robots”. Robotics and Autonomous Systems, Vol. 29, pp. 51-63, 1999.

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

Martinoli A. and Easton K., “Modeling Swarm Robotic Systems”. In Siciliano B. and Dario P., editors, Proc. of Eighth Int. Symp. on Experimental Robotics, July 2002, Sant’Angelo d’Ischia, Italy. Springer Tracts in Advanced Robotics (2003), pp. 285-294.

Martinoli A. and Easton K., “Optimization of Swarm Robotic Systems via Macroscopic Models”. In Schultz A., Parker L., and Schneider F., Proc. of the Multi-Robot Systems Workshop, Naval Research Laboratory, March 2003, Washington, DC, pp. 181-192.