Onur SOYSAL, Erkin Bahçeci And Erol ŞAHİN

Aggregation in Swarm Robotic Systems: Evolution and Probabilistic Control

In this study we investigate two approachees for aggregation behavior in swarm robotics systems: Evolutionary methods and probabilistic control. In first part, aggregation behavior is chosen as a case, where performance and scalability of aggregation behaviors of perceptron controllers that are evolved for a simulated swarm robotic system are systematically studied with different parameter settings. Using a cluster of computers to run simulations in parallel, four experiments are conducted varying some of the parameters. Rules of thumb are derived, which can be of guidance to the use of evolutionary methods to generate other swarm robotic behaviors as well. In the second part a systematic analysis of probabilistic aggregation strategies in swarm robotic systems is presented. A generic aggregation behavior is proposed as a combination of four basic behaviors: obstacle avoidance, approach, repel, and wait. The latter three basic behaviors are combined using a three-state finite state machine with two probabilistic transitions among them. Two different metrics were used to compare performance of strategies. Through systematic experiments, how the aggregation performance, as measured by these two metrics, change 1) with transition probabilities, 2) with number of simulation steps, and 3) with arena size, is studied. We then discuss these two approaches for the aggregation problem.

Anahtar Kelimeler:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 199-225. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.

Aggregation in Swarm Robotic Systems: Evolution and Probabilistic Control

Keywords:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 199-225. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.,

PDF

___

S. Camazine, N. R. Franks, J. Sneyd, E. Bonabeau, J.-L. Deneubourg, G. Theraulaz, Self-Organization in Biological Systems. Princeton, NJ, USA: Princeton University Press, 2001. ISBN: 0691012113.
M. Dorigo, V. Trianni, E. S¸ahin, R. Groß, T. H. Labella, G. Baldassarre, S. NolŞ, J.-L. Deneubourg, F. Mondada, D. Floreano, L. M. Gambardella, “Evolving self-organizing behaviors for a swarm-bot,” Autonomous Robots, vol. 17, no. 2-3, pp. 223–245, 2004.
E. S¸ahin, W. Spears, eds., Swarm Robotics Workshop: State-of-the-art Survey, vol. 3342 of Lecture Notes in
Computer Science. Berlin Heidelberg: Springer-Verlag, 2005.
E. Bah¸ceci, E. S¸ahin, “Evolving aggregation behaviors for swarm robotic systems: A systematic case study,” in IEEE Swarm Intelligence Symposium, (Pasadena, CA, USA), 2005.
O. Soysal, E. S¸ahin, “Probabilistic aggregation strategies in swarm robotic systems,” in Proc. of the IEEE Swarm Intelligence Symposium, (Pasadena, California), pp. 325–332, June 2005.
J. L. Deneubourg, A. Lioni, C. Detrain, “Dynamics of aggregation and emergence of cooperation,” Biological Bulletin, vol. 202, pp. 262–267, June 2002.
R. Jeanson, C. Rivault, J. Deneubourg, S. Blanco, R. Fournier, C. Jost, G. Theraulaz, “Self-organised aggrega- tion in cockroaches,” Animal Behaviour, vol. 69, pp. 169–180, 2005.
C. Melhuish, O. Holland, S. Hoddell, “Convoying: using chorusing to form travelling groups of minimal agents,” Journal of Robotics and Autonomous Systems, vol. 28, pp. 206–217, 1999.
P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, “Gathering of asynchronous robots with limited visibility.,” Theoretical Computer Science, vol. 337, no. 1-3, pp. 147–168, 2005.
N. Gordon, I. A. Wagner, A. M. Bruckstein, “Gathering multiple robotic a(ge)nts with limited sensing capabil- ities,” in Lecture Notes in Computer Science, vol. 3172, pp. 142–153, Jan 2004.
V. Gazi, K. M. Passino, “Stability analysis of swarms,” IEEE Transactions on Automatic Control, vol. 48, pp. 692 – 697, April 2003.
V. Gazi, “Swarm aggregations using artiŞcial potentials and sliding mode control,” in 42nd IEEE Conference on Decision and Control, vol. 2, pp. 2041– 2046, 2003.
V. Gazi, K. M. Passino, “A class of attractions/repulsion functions for stable swarm aggregations,” International Journal of Control, vol. 77, pp. 1567–1579, Dec 2004.
Z. Lin, B. Francis, M. Ma, “Necessary and suﬃcient graphical conditions for formation control of unicycles,” IEEE Transactions on Automatic Control, vol. 50, pp. 121–127, Jan 2005.
S. T. Kazadi, Swarm Engineering. PhD thesis, Caltech, 2000.
C. Lee, M. Kim, S. Kazadi, “Robot clustering,” in IEEE SMC [submitted], 2005.
J. H. Holland, “Outline for a logical theory of adaptive systems,” J. ACM, vol. 9, no. 3, pp. 297–314, 1962.
J. H. Holland, Adaptation in natural and artiŞcial systems. Ann Arbor, MI, USA: University of Michigan Press, N. Zaera, C. Cliﬀ, J. Bruten, “(Not) evolving collective behaviours in synthetic Şsh,” in From Animals to Animats : Proceedings of the Fourth International Conference on Simulation of Adaptive Behaviour, (Camb ridge, MA), pp. 635–6, MIT Press, 1996.
M. J. Mataric, D. Cliﬀ, “Challenges in evolving controllers for physical robots,” Journal of Robotics and Autonomous Systems, vol. 19, pp. 67–83, Oct. 1996.
H. H. Lund, J. Hallam, “Evolving suﬃcient robot controllers,” in Proceedings of the Fourth IEEE International Conference on Evolutionary Computation, (Piscataway, NJ), pp. 495–499, IEEE Press, 1997.
M. Dorigo, E. Tuci, R. G. V. Trianni, T. H. Lab ella, S. Nouyan, C. Ampatzis, “The SWARM-BOTS project,” in Swarm Robotics Workshop: State-of-the-art Survey (E. S¸ahin and W. Spears, eds.), no. 3342 in Lecture Notes in Computer Science, (Berlin Heidelberg), pp. 31–44, Springer-Verlag, 2005.
G. Baldassarre, S. NolŞ, D. Parisi, “Evolving mobile robots able to display collective behaviors.,” ArtiŞcial Life, vol. 9, pp. 255–268, Aug. 2003.
V. Trianni, R. Groß, T. Labella, E. S¸ahin, M. Dorigo, “Evolving Aggregation Behaviors in a Swarm of Robots,” in Advances in ArtiŞcial Life - Proceedings of the 7th European Conference on ArtiŞcial Life (ECAL) (W. Banzhaf, T. Christaller, P. Dittrich, J. T. Kim, J. Ziegler, eds.), vol. 2801 of Lecture Notes in ArtiŞcial Intelligence, pp. 865–874, Springer Verlag, Heidelberg, Germany, 2003.
M. Dorigo, V. Trianni, E. S¸ahin, R. Groß, T. H. Labella, G. Baldassarre, S. NolŞ, J.-L. Deneubourg, F. Mondada, D. Floreano, L. M. Gambardella, “Evolving self-organizing behaviors for a swarm-bot.,” Autonomous Robots, vol. 17, no. 2-3, pp. 223–245, 2004.
C. R. Ward, F. Gobet, G. Kendall, “Evolving collective behavior in an artiŞcial ecology.,” ArtiŞcial Life - Special issue on Evolution of Sensors in Nature, Hardware and Simulation, vol. 7, no. 2, pp. 191–209, 2001.
F. Mondada, G. C. Pettinaro, A. Guignard, I. Kwee, D. Floreano, J.-L. Deneubourg, S. NolŞ, L. Gambardella, M. Dorigo, “Swarm-bot: A new distributed robotic concept,” Autonomous Robots, vol. 17, no. 2–3, pp. 193–221, J.-M. Valin, F. Michaud, J. Rouat, D. Letourneau, “Robust sound source localization using a microphone array on a mobile robot,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 2, pp. 1228–1233, 2003.
R. Sedgewick, Algorithms in C. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1990.
O. Soysal, E. S¸ahin, “A macroscopic model for self-organized aggregation in swarm robotic systems,” in Second International Workshop on Swarm Robotics at SAB 2006 (E. S¸ahin, W. M. Spears, A. F. T. WinŞeld, eds.), vol. 4433, (Berlin, Germany), pp. 27–42, Springer Verlag, 2006.