Modeling and Analysis of the Collective Dynamics of Large-Scale Multi-Agent Systems

Tosic, Predrag T.

Permalink

https://hdl.handle.net/2142/11259 Copy

Description

Title

Modeling and Analysis of the Collective Dynamics of Large-Scale Multi-Agent Systems

Author(s)

Tosic, Predrag T.

Issue Date

2006-12

Keyword(s)

• multi-agent systems
• computer science

Abstract

This technical report addresses modeling and analysis of the behavior of large-scale multiagent systems. A broad variety of multi-agent systems (MAS) are modeled as appropriate variants of cellular and network automata. Several fundamental properties of the collective dynamics of those cellular and network automata are then formally analyzed. The focus of this work is placed on the following three important aspects of large-scale distributed information systems that are viewed as MAS made of a large number of autonomous agents that locally interact with each other. First, the temporal and causal nature of inter-agent interaction is addressed, together with its consequences. In that context, a comparison and contrast of cellular automata with different communication models is undertaken. Second, the implications of homogeneity vs. heterogeneity of the individual agent behaviors in a large-scale MAS are analyzed. Third, in conjunction with the models of individual agent behaviors, the impact of the communication network topology on the collective behavior of large agent ensembles is studied. In particular, it is formally established that a number of fundamental problems about the collective dynamics of multi-agent systems are demonstrably computationally intractable. Moreover, that intractability is shown to hold even when the instances of the network automata abstractions of the large-scale multi-agent systems under scrutiny are severely constrained. The research summarized in this report strengthens and/or generalizes much of the previous work on the global behavior of various discrete dynamical system models studied in the literature, such as the classical cellular automata and discrete Hopfield networks. Among several far-reaching implications of the results presented in this report, perhaps the most prominent is the general conclusion that a highly complex and unpredictable collective dynamics in multi-agent systems can arise from a synergy of very simple individual agent behaviors and their loosely coupled local interactions.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11259

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections