Analyzing Multi-Agent Systems Based On The Notion Of Emergence

As one effective computing pattern and designing method, multi-agent systems (MAS) has been generally recognized, accepted, and applied in many fields. MAS is composed of computing entities (i.e. Agent) with autonomy, reactivity, proactivity and sociality. The common goal of MAS is achieving some macro properties by engineering agents'activity and local mechanism. Therefore, the main activity and key topic in the analysis of MAS is the micro-macro analysis, i.e., finding out the relationships between microscopic and macroscopic MAS. However, these relationships in MAS have its specialization, differing from the traditional computing systems. Therefore, it is important to understand and analysis the specialization both in theoretical and practical aspects.By using the"emergence"as the analyzing and designing pattern of MAS, this thesis characterizes the above-mentioned particularity in MAS, and propose an emergence-based framework and several relevant methods. Furthermore, several typical MAS systems and mechanisms, including BitTorrent system, colony optimization, gossip protocol and trust/reputation system, are re-presented in the viewport of"emergence".Firstly, as emergence is so extremely complicated that it is difficult to be caught, this thesis explores the notion of emergence from various perspective. The history that the concept of emergence evolves is firstly investigated. The history reveals the ideas with which the notion of emergence ware endued. These ideas are whole, level and dynamical creation; they establish the conceptual framework of emergence, provide it with fundamental meaning, and are the basis for understanding the notion. Next, this paper identifies several core issues in the notion of emergence, which are used for catching emergence in MASs. These issues include the relations in which emergence involve, the criterions with which emergence must meet, the objects that emergence characterize, the objectivity and subjectivity in the notion of emergence, and so on. They are the key elements in the notion of emergence. Moreover,"emergence"is distinguished from several confusable notions including"resultant","synthesis"and"self-organization". The exposed differences between them give a profound insight into the notion of emergence. Lastly, emergence in MAS is exhaustively discussed based on the study upon; and the roots of emergence in MAS are indicated.Secondly, based on the notion of emergence and the viewpoints it provides, this thesis investigates and discusses the framework and approaches for analyzing MAS. At first, a general framework for is proposed, which presents the process of emergence analysis, defines several concepts involved in it, and places some general problems and possible solutions. Then, based on different means of MAS description, three categories of micro-macro analysis are identified. They are approaches respectively based on logic, mathematics and simulation. The main works of this part are: discussing the ways by which the micro-macro analysis approaches accomplish the tasks; reviewing several related works based on these approaches and following the ways; summarizing the merits and shortcomings of these micro-macro analysis approaches.Thirdly, gossip is a popular mechanism for communication in MAS. The work already existed is mainly focused on the convergence time of gossip, and seldom on its dynamic behaviors. In order to analyze the dynamic behaviors, this thesis proposes an analytical model based on mean-field method for gossip protocols. At first, the analysis steps of mean-field method and the approaches used in it are presented; and the usefulness of this method are discussed. Then, using mean-field method, an analytical model is given for a gossip-based averaging MAS. This model not only can present the convergence time of gossip, but also can characterize its dynamics and evolution under different conditions.Fourthly, from the view of computing model, peer-to-peer systems are a representative class of MAS. And as a practical peer-to-peer system, BitTorrent gets broad notice in theory and practice. The work that has been taken great efforts is providing an effective model for analyzing BitTorrent. Based on the notion of emergence, this thesis proposes an analytical model for BitTorrent. The model start from the states of microscopic BitTorrent, i.e. nodes'states, and get the parameters that represent a node, called microscopic parameters. Based on these parameters and the activities of a node, the microscopic behaviors of BitTorrent are characterized. At the same time, several macroscopic parameters are chosen to describe systematic state of BitTorrent. Based on the microscopic behaviors, by exploring the relationship between microscopic and macroscopic parameters, the macroscopic equations characterizing BitTorrent's evolvement are established. And based these equations, macro properties of BitTorrent can be obtained. Experiment results indicate that this model can effectively catch the behaviors of BitTorrent systems.Fifthly, the inspiring source of ant colony optimization (ACO) is the foraging behavior of real ants, which can regard as a simple MAS. Although this behavior is quite ordinary, it is in fact an emergent phenomenon. So, in ACO analysis, there are some obstacles on the way from micro mechanism to macro property. In order to understanding these obstacles, this thesis investigates ACO and the obstacles from the perspective of emergence. The investigation reveals the root of complexity in ACO. At first, by analyzing ACO on the micro- and macro-level and exploring the relations between these two levels, we estimate the process complexity of ACO by predictive information, and show that it is extremely large. Then, by exploring the transformation of the best-so-far solution, the convergence conditions of ACO are identified; and provide an approach for analyzing the convergence speed. Based on the perspective of emergence, we clarify that deception in ACO has its microscopic root, i.e. solution bias, and demonstrate three type of bias. Comparing with previous work, this analysis can more easily reveal the essence of ACO. Sixthly, trust management is a fundamental concern in MAS. Now, the trust models of MASs are focusing on the devising of trust mechanisms. However, the macro properties implied by these micro mechanisms are not obvious, and could not assume it as a matter of course. This thesis develops a simulation approach based on the notion of emergence for analyzing MAS trust model, and have used it to study a trust model. Starting with the relatively clear behavior of MAS micro level (i.e. agent's behavior), considering sufficient MAS macro constrains, and building up a runnable simulation system, this approach studies the macro problems and the micro-macro relations of MAS trust model. Accordingly, in this thesis, at the micro level, the design scheme of trust mechanisms is analyzed and summarized; and based on this, a framework for implementing simulation agent is proposed. At the macro level, several system issues that must be taken into account in simulation-based MAS analysis are discussed, including macro constrains, threat model, evaluating metric, and issues in simulation running. To demonstrate the effectiveness of this model, local trust model is analyzed based on it. The analysis also reveals the unpredictability and complexity of trust model.