Abstract
Adaptation is an essential requirement for self–organizing multi–agent systems functioning in unknown dynamic environments. Adaptation allows agents to change their actions in response to environmental changes or actions of other agents in order to improve overall system performance, and remain robust even while a sizeable fraction of agents fails. In this paper we present and study a simple model of adaptation for task allocation problem in a multi–robot system. In our model robots have to choose between two types of task, and the goal is to achieve desired task division without any explicit communication between robots. Robots estimate the state of the environment from repeated local observations and decide what task to choose based on these observations. We model robots and observations as stochastic processes and study the dynamics of individual robots and the collective behavior. We validate our analysis with numerical simulations.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agassounon, W., Martinoli, A.: A macroscopic model of an aggregation experiment using embodied agents in groups of time-varying sizes. In: Proc. of the IEEE Conf. on System, man and Cybernetics SMC-2002, Hammamet, Tunisia. IEEE Press, Los Alamitos (2002)
Goldberg, D., Matarić, M.J.: Coordinating mobile robot group behavior using a model of interaction dynamics. In: Proceedings of the Third International Conference on Autonomous Agents (Agents 1999), Seattle,WA, USA, pp. 100–107. ACM Press, New York (1999)
Huberman, B.A., Hogg, T.: The behavior of computational ecologies. In: Huberman, B.A. (ed.) The Ecology of Computation, pp. 77–115. Elsevier, North Holland, Amsterdam (1988)
Ijspeert, A.J., Martinoli, A., Billard, A., Gambardella, L.M.: Collaboration through the exploitation of local interactions in autonomous collective robotics: The stick pulling experiment. Autonomous Robots 11(2), 149–171 (2001)
Jones, C.V., Matarić, M.J.: Adaptive task allocation in large-scale multirobot systems. In: Proceedings of the 2003 (ICRA 2003), Las Vegas, NV, IEEE, Los Alamitos (2003)
Kazadi, S., Abdul-Khaliq, A., Goodman, R.: On the convergence of puck clustering systems. Robotics and Autonomous Systems 38(2), 93–117 (2002)
Lerman, K., Galstyan, A.: Mathematical model of foraging in a group of robots: Effect of interference. Autonomous Robots 13(2), 127–141 (2002)
Lerman, K., Galstyan, A.: Macroscopic Analysis of Adaptive Task Allocation in Robots. In: Proceedings of the International Conference on Intelligent Robotics ans Systems (IROS-2003), Las Vegas, NV (October 2003)
Lerman, K., Galstyan, A., Martinoli, A., Ijspeert, A.: A macroscopic analytical model of collaboration in distributed robotic systems. Artificial Life Journal 7(4), 375–393 (2001)
Li, L., Martinoli., A., Abu-Mostafa, Y.: Emergent Specialization in Swarm Systems. In: Yin, H., Allinson, N.M., Freeman, R., Keane, J.A., Hubbard, S. (eds.) IDEAL 2002. LNCS, vol. 2412, pp. 261–266. Springer, Heidelberg (2002)
Martinoli, A., Ijspeert, A.J., Gambardella, L.M.: A probabilistic model for understanding and comparing collective aggregation mechanisms. In: Floreano, D., Nicoud, J.-D., Mondada, F. (eds.) ECAL 1999. LNCS(LNAI), vol. 1674, pp. 575–584. Springer, Heidelberg (1999)
Martinoli, A., Easton, K.: Modeling swarm robotic systems. In: Siciliano, B., Dario, P. (eds.) Proc. of the Eight Int. Symp. on Experimental Robotics ISER-2002, Sant’Angelo d’Ischia, Italy, Springer Tracts in Advanced Robotics, New York, NY, vol. 5, pp. 297–306. Springer, Heidelberg (2003)
Matarić, M.J.: Learning in behavior-based multi-robot systems: Policies, models, and other agents. Cognitive Systems Research 2(1), 81–93 (2001)
Riedmiller, M., Merke, A.: Karlsruhe brainstormers - a reinforcement learning approach to robotic soccer II. In: Birk, A., Coradeschi, S., Tadokoro, S. (eds.) RoboCup 2001. LNCS (LNAI), vol. 2377, p. 435. Springer, Heidelberg (2002)
Stone, P., Sutton, R.S.: Scaling reinforcement learning toward RoboCup soccer. In: Proc. 18th International Conf. on Machine Learning, pp. 537–544. Morgan Kaufmann, San Francisco (2001)
Sugawara, K., Sano, M.: Cooperative acceleration of task performance: Foraging behavior of interacting multi-robots system. Physica D100, 343–354 (1997)
Sugawara, K., Sano, M., Yoshihara, I., Abe, K.: Cooperative behavior of interacting robots. Artificial Life and Robotics 2, 62–67 (1998)
Van Kampen, N.G.: Stochastic Processes in Physics and Chemistry. Elsevier Science, Amsterdam (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Galstyan, A., Lerman, K. (2005). Analysis of a Stochastic Model of Adaptive Task Allocation in Robots. In: Brueckner, S.A., Di Marzo Serugendo, G., Karageorgos, A., Nagpal, R. (eds) Engineering Self-Organising Systems. ESOA 2004. Lecture Notes in Computer Science(), vol 3464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494676_11
Download citation
DOI: https://doi.org/10.1007/11494676_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26180-3
Online ISBN: 978-3-540-31901-6
eBook Packages: Computer ScienceComputer Science (R0)