Thiết kế môi trường mở cho hệ thống mô phỏng đa tác nhân - Renee Lynn Steiner

PREFACE This dissertation was produced in accordance with guidelines which permit the inclusion as part of the dissertation the text of an original paper or papers submitted for publication. The dissertation must still conform to all other requirements explained in the “Guide for the Preparation of Master Theses and Doctoral Dissertations at The University of Texas at Dallas.” It must include a comprehensive abstract, a full introduction and literature review and a final overall conclusion. Additional material (procedural and design data as well as descriptions of equipment) must be provided in sufficient de- tail to allow a clear and precise judgement to be made of the importance and originality of the research reported. It is acceptable for this dissertation to include as chapters authentic copies of papers already published, provided these meet type size, margin and legibility requirements.

In such cases, con- necting texts which provide logical bridges between different manuscripts are mandatory. Where the student is not the sole author of a manuscript, the student is required to make an explicit statement in the introductory mate- rial to that manuscript describing the student’s contribution to the work and acknowledging the contribution of the other author(s). The signatures of the Supervising Committee which precede all other material in the dissertation attest to the accuracy of this statement. c Copyright 2006 Renee Lynn Steiner All Rights Reserved To Michael David Steiner ENGINEERING OPEN ENVIRONMENTS FOR MULTI-AGENT SIMULATION SYSTEMS by RENEE LYNN STEINER, B.

DISSERTATION Presented to the Faculty of The University of Texas at Dallas in Partial Fulfillment of the Requirements for the Degree of DOCTOR OF PHILOSOPHY IN COMPUTER SCIENCE THE UNIVERSITY OF TEXAS AT DALLAS December 2006 UMI Number: 3238604 UMI Microform 3238604 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 ACKNOWLEDGEMENTS I would like to thank Dr. Rym Zalila Mili, my supervisor, for her many suggestions and constant support during this research. I would also like to thank Dr. Kendra Cooper, Dr.

Jing Dong and Dr. Kang Zhang for serving on my committee. I am also thankful to members of the DIVAs lab for their contributions and encouragement. I am especially thankful to my family and friends who have sacrificed much so that I might succeed in my goals.

November 2006 v ENGINEERING OPEN ENVIRONMENTS FOR MULTI-AGENT SIMULATION SYSTEMS Publication No. Renee Lynn Steiner, Ph. The University of Texas at Dallas, 2006 Supervising Professor: Dr. Rym Zalila Mili, Chair In this work, we present the idea that agents and the environment play an equally important role in MAS design and propose an architecture for Agent Environment System (AES).

We consider environments as first class entities and propose a specification, design and implementation of the DIVAs envi- ronment. DIVAs is a large scale multi-agent simulation tool in which agents represent social entities and the environment an artificial world. Our archi- tecture is based on software engineering concepts such as separation of con- cerns, modularity and information hiding. This leads to adaptable systems that can support multiple application domains.

We discuss a Specification and a Simulation Tool that illustrate the applicability of our results to various problems. vi TABLE OF CONTENTS Acknowledgements. vi Table of Contents. vii List of Tables.

x List of Figures. 1 1 State of the Art.2 Classifications of MAS Environments .1 Classification from the Literature. 18 2 Agent-Environment Systems .1 Defining Agent-Environment System .2 AES Agent Characteristics .3 AES Environment Characteristics .5 A Proposed AES Abstract Architecture .2 The AES Architecture. 33 3 Levels and Viewpoints for AES.

55 4 The DIVAs System .1 DIVAs Agent-Environment System .1 Planning and Control Module (PCM). 84 6 Environment Specification Tool .1 Mapping Design to Implementation .4 Modifying the Environment .6 Specification Tool Features. 98 7 Environment Simulation Tool .1 Simulation Tool Implementation Overview .3 Simulating the Environment .4 Simulation Tool Features. 116 Vita ix LIST OF TABLES 1.1 Assessing MAS environments .1 System Configuration for Testing.

110 x LIST OF FIGURES 1.1 MAS Environment Classification.1 Agent and Environment Commonalities .2 Interactivity illustration for AES .3 FIPA Abstract Architecture .4 FIPA Agent Management Reference Model .5 A General AES Architecture .5 Universal Level Data Model .6 World Level Data Model, Environment .7 World Level Data Model, Agent .8 Entity Level Data Model, Environment .9 Entity Level Data Model, Agent .10 Entity Level Functional Model .11 Universal Level Behavioral Model, State Chart .12 Universal Level Behavioral Model, Interaction Diagram .13 World Level Behavioral Model, State Chart .14 World Level Behavioral Model, Interaction Diagram .15 Entity Level Behavioral Model .16 Universal Level Structural Model .17 World Level Structural Model .18 Entity Level Structural Model, Environment .19 Entity Level Structural Model, Agent .20 Atomic Level Data Model, Environment .2 Geographical Simulation Environment .3 Environment partitioned into cells .4 Representation of the Environment .5 Hierarchical decomposition of the environment into cells .1 Expanding Agent and Environment Commonalities .3 Environment Class Diagram .5 MTS High Level Analysis Diagram .6 MTS CommunicationModel Class Diagram .1 Specifying the Simulation Space .2 Directly observing the DIVAs environment architecture in the Specification Tool .3 New Project Wizard .4 Environment Editor representing the environment in xml .5 Specifying the heart as the environment .6 Level 2 of heart as the environment .1 Launching the Simulation Tool .2 DIVAs Simulation Tool, Level 1 .3 DIVAs Simulation Tool with multiple levels exposed .4 Context Sensitive Menuing for Edges .5 Context Sensitive Menuing for Nodes. 105 xii INTRODUCTION The application of Multi-Agent Systems (MAS) paradigms to modeling and simulation of adaptive systems has become an important development in com- puting [20]. While traditional modeling and simulation techniques are lim- ited to static domains, MAS-based simulation brings into focus the desirable attributes of emergence, self-organization, learning, and adaptive behavior, thus enabling the modeling and understanding of more real world complex application domains. A number of agent-based simulation systems have been described in the literature including MASON [52], Swarm [66], Repast [18], Ethos [85], As- cape [74], AgentSheets [80], XRaptor [64], CORMAS [14], SimAgent [86], and SeSAm [49].

Most of these systems are often restricted to specific ap- plications, and are difficult to adapt to other domains. In addition, these systems do not clearly separate between agents and environment responsibil- ities. Researchers agree that this is a substantial weakness in MAS and have recently organized workshops dedicated to the exploration of environments as first class entities [92, 91, 94]. 1 2 Our work is based on the idea that, by separating the agent from its en- vironmental responsibilities, both the environment and the agent are more robust and adaptable.

Such a clear separation of duties and responsibilities leads to a reduction in unnecessary coupling and a more understandable, ex- tensible, reusable architecture. New Multi-Agent Simulation tools make use of this principle [18, 52]. Moreover, we subscribe to the idea that agents and environment play an equally important role, and propose a definition for Agent-Environment Sys- tems (AES). The AES concept is particularly useful when a) the environment is dynamic and distributed, b) the environment includes entities that are not agents, and c) agents cannot have a complete view of the environment at any point in time.

As such, AES are subsets of MAS and supersets of agent simulation tools. We illustrate our concepts through the DIVAs environment. DIVAs (or Dynamic I nformation V isualization of Agent systems) is a social simulation tool in which the environment is a geographical map consisting of a graph whose nodes indicate places and whose edges represent pathways between places. In Chapter 1, we define key terms and examine the state of the art of Multi Agent Simulation Systems and the environments they provide.

In Chapter 2, we present the concept of the Agent Environment Architecture. In Chapter 3, 3 we discuss the environment and agent from various levels of abstraction and propose models for data, functional, behavioral and structural viewpoints. In Chapter 4, we discuss the DIVAs system architecture. In Chapter 5, we examine the DIVAs environment architecture.

In Chapter 6, we introduce our Specification Tool implementation, and in Chapter 7, we inspect our Simulation Tool implementation. In Chapter 8, we discuss the experimental results achieved. We finish by suggesting directions for future work for Multi- Agent Simulation System environments. CHAPTER 1 STATE OF THE ART In this Chapter, we discuss terms found in the MAS field and proceed with discussing the state of the art with respect to environments for Multi-Agent Systems, focusing on simulation systems.1 Definitions In our work, we subscribe to the following definitions: Agent.

An agent is a computer system that is situated in some environ- ment, and that is capable of autonomous action in this environment in order to meet its design objectives [6]. In situated MAS, the environment is an active entity with its own processes that can change its own state, independent of the ac- tivity of the embedded agents [91]. Multi-agent System (MAS). A MAS is a system that consists of a num- ber of agents, which interact with one-another.

Agents interact on behalf of users with different goals and motivations. To successfully interact, 4 5 they require the ability to cooperate, coordinate, and negotiate with each other [97]. Multi-agent Simulation System (MASS). A computer simulation is the discipline of designing a model of an actual or theoretical physical system, executing the model on a digital computer and analyzing the execution output.

A MASS is a computer simulation specifically for a MAS [37, 22]. In the past few years, interest in environments for MAS has greatly in- creased. A new workshop, Environments for Multiagent Systems (E4MAS), began in 2004 as part of the Autonomous Agents for Multi-agent Systems (AAMAS) conference [5]. The workshop in 2004 resulted in the survey by Weyns et al.

This survey describes various MAS from the perspective of the environment [91]. By focusing on the environment, the authors stress the importance that the environment plays in MAS as well as emphasizes the relative newness of accepting the environment as a primary abstraction. Like- wise, more and more researchers agree that the environment should be treated as a first-class entity. We define a first-class entity as “a program building block, an independent piece of software which.

provides an abstraction or information hiding mechanism so that a module’s implementation can be changed without requiring any change to other module” [1, 91]. Hence, since 6 the environment only recently has been proposed as such, the amount of en- gineering, and therefore, the amount of architectures focusing on this topic is limited. Therefore, in order to discuss the state of the art, we first discuss existing classifications of MAS environments.2 Classifications of MAS Environments In this section, we discuss the classification proposed by the mentioned survey and continue with a proposed a classification for environments for MAS.1 Classification from the Literature The referenced survey classifies environments into four categories: general models, inter-agent facilities, agent-environment interaction, and environ- ments in agent oriented methodologies. These are models which define general agent environ- ment relationships (e., how the agent perceives the environment, how the environment perceives the agent).

Examples of such models are the influence/reaction model proposed by Ferber [27], the percept/effector model proposed by Russell and Norvig [82], and a model proposed by Odell et al. which differentiates between the physical environment and 7 the communication environment [68]. Another discussed model deals with environments for mobile agents in which the agent possesses the ability to migrate from one system to another in the course of complet- ing their goals. These models are also referred to as Distributed Agent Environments (DAE) and commonly adhere to the OMG MASIF stan- dard [41] or the FIPA standard [36].

• Inter-agent facilities.