A Model of Adaptation in Collaborative Multi-Agent Systems

Abstract

Adaptation is an essential requirement for autonomous agent systems functioning in uncertain dynamic environments. Adaptation allows agents to change their behavior in order to improve the overall sys tem performance. We describe a general mechanism for adaptation in multi-agent systems in which agents modify their behavior in response to changes in the environment or actions of other agents. The agents estimate the global state of the system from local observations and adjust their actions accordingly. We derive a mathematical model that describes the collective behavior of such adaptive systems. The model, consisting of coupled rate equations, governs how the collective behavior changes in time. We apply the model to study collaboration in a group of mobile robots. The system we study is an adaptive version of the collaborative stick pulling in a group of robots examined in detail in earlier works (Ijspeert, Martinoli, Billard, & Gambardela, 2001; Lerman, Galstyan, Martinoli, & Ijspeert, 2001). In adaptive stick pulling, robots estimate the number of robots and sticks in the system and adjust their individual behavior so as to improve collective performance. We solve the mathematical model and show that adaptation improves collective performance for all parameter values.

Keywords

robotics mathematical models adaptation

Get full access to this article

View all access options for this article.

References

Agassounon, W. , Martinoli, A. , & Easton, K. (2004). Macroscopic modeling of aggregation experiments using embodied agents in teams of constant and time-varying sizes. Special issue on Swarm Robotics , M. Dorigo & E. Sahin (Eds.). Autonomous Robots, 17(2-3), 163-191 .

Arbib, M. A. , Kfoury, A. J. , & Moll, R. N. (1981). A basis for theoretical computer science. New York: Springer .

Arkin, R. C. (1999). Behavior-based robotics. Cambridge, MA: MIT Press .

Barabasi, A.-L. , & Stanley, H. (1995). Fractal concepts in surface growth. Cambridge, UK: Cambridge University Press .

Claus, C. , & Boutilier, C. (1998). The dynamics of reinforcement learning in cooperative multiagent systems . In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98) (pp. 746-752 ). Menlo Park, CA: AAAI Press. July 26-30 1998.

Galstyan, A. , & Lerman, K. , (2004). Analysis of a Stochastic Model of Adaptive Task Allocation in Robots . In S. Brueckner et al. (Eds.), Proceedings of workshop on Engineering of Self-Organizing Applications (ESOA2004), ACM Press, 2004, in press.

Goldberg, D. , & Mataric, M. J. (2003). Maximizing reward in a non-stationary mobile robot environment . Autonomous Agents and Multi-Agent Systems, 6(3), 281-316 .

Guestrin, C. , Koller, D. , & Parr, R. (2001). Multiagent planning with factored MDPs. In Advances in Neural Information Processing Systems (NIPS), Cambridge, MA: MIT Press .

Haberman, R. (1998). Mathematical models: Mechanical vibrations, population dynamics, and traffic flow. Philadelphia, PA: Society of Industrial and Applied Mathematics (SIAM) .

10.

Huberman, B. A. , & Hogg, T. (1988). The behavior of computational ecologies. In B. A. Huberman (Ed.), The Ecology of Computation (pp. 77-115). Amsterdam: Elsevier/North-Holland .

11.

Ijspeert, A. J. , Martinoli, A. , Billard, A. , & Gambardella L. M. (2001). Collaboration through the exploitation of local interactions in autonomous collective robotics: The stick pulling experiment . Autonomous Robots, 11(2), 149-171 .

12.

Jones, C. V. , & Mataric, M. J. (2003). Adaptive task allocation in large-scale multi-robot systems . In S. George Lee & Junku Yuh (Eds.), Proceedings of the 2003 (ICRA’03), (pp. 1969-1974 ). Piscataway, NJ: IEEE Press.

13.

Kaelbling, L. P. (1991). Learning in embedded systems. Cambridge, MA: MIT Press .

14.

Lerman, K. and Galstyan, A. (2002). Mathematical model of foraging in a group of robots: Effect of interference . Autonomous Robots, 13(2), 127-141 .

15.

Lerman, K. , & Galstyan, A. (2004). Two paradigms for the design of artificial collectives. In Kagan Tumer and David Wolpert , (Eds.), Collectives and the Design of Complex Systems (pp. 231-256). New York, NY: Springer-Verlag .

16.

Lerman, K. & Galstyan, A. (2003b). Macroscopic analysis of adaptive task allocation in robots . In C. S. George Lee & Junku Yuh (Eds.), Proceedings of the International Conference on Intelligent Robots and Systems (IROS-2003), (pp. 1951-1956 ). Piscataway, NJ: IEEE Press.

17.

Lerman, K. , Galstyan, A. , Martinoli, A. , & Ijspeert, A. (2001). A macroscopic analytical model of collaboration in distributed robotic systems . Artificial Life, 7(4), 375-393 .

18.

Lerman, K. , & Shehory, O. (2000). Coalition formation for large-scale electronic markets . In Proceedings of the International Conference on Multi-Agent Systems (ICMAS’2000). (pp. 167-174 ).

19.

Li, L. , Martinoli, A. , & Abu-Mostafa, Y. (2002). Emergent specialization in swarm systems. In H. Yin et al. (Eds.), Lecture Notes in Computer Science, Vol. 2412 (pp. 261-266). New York: Springer .

20.

Martinoli, A. , & Easton, K. (2003). Modeling swarm robotic systems . In B. Siciliano & P. Dario (Eds.), Proceedings of the Eighth International Symposium on Experimental Robotics (ISER-02) (pp. 297-306 ). New York: Springer.

21.

Martinoli, A. , Ijspeert, A. J. , & Gambardella, L. M. (1999). A probabilistic model for understanding and comparing collective aggregation mechanisms . In D. Floreano , J.-D. Nicoud , & F. Mondada (Eds.), Lecture Notes in Artificial Intelligence, Vol. 1674 (pp. 575-584 ). New York: Springer.

22.

Mataric, M. J. (1997). Reinforcement learning in the multi-robot domain . Autonomous Robots, 4(1), 73-83 .

23.

Riedmiller, M. , & Merke, A. (2001). Karlsruhe brainstormers - a reinforcement learning approach to robotic soccer II . In A. Birk , S. Coradeschi & S. Tadokoro (Eds.), RoboCup-01: Robot Soccer World Cup V (Lecture Notes in Computer Science series) (pp 435-440 ). Berlin: Springer.

24.

Sato, Y. , & Crutchfield, J. P. (2003). Coupled replicator equations for the dynamics of learning in multiagent systems . Physical Review E, 67, 015206 .

25.

Shoham, Y. , Grenager, T. , & Powers, R. (2003). Multi-agent reinforcement learning: A critical survey. unpublished manuscript available at http://robotics.stanford.edu/shoham/YoavPublications.htm

26.

Stone, P. , & Sutton, R. (2001). Scaling Reinfonement learning toward RoboCup Soccer . In Proceedings of the 18th International Conference on Machine Learning (ICML’01).

27.

Sugawara, K. , & Sano, M. (1997). Cooperative acceleration of task performance: Foraging behavior of interacting multi-robots system . Physica D, 100, 343-354 .

28.

Van Kampen, N. G. (1992). Stochastic processes in physics and chemistry. Amsterdam: Elsevier .

29.

Wolpert, D., & Tumer, K. (1999). An introduction to collective intelligence. Technical Report NASA-ARC-IC-99-63, NASA Ames Research Center.