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

摘要

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.