|
Jacques Ferber is Professor of Computer Science and Artificial Intelligence at the University of Montpellier, France and head of one of the foremost research groups in Europe investigating the applications of distributed artificial intelligence and multi-agent systems. Translated and updated from the original French, this book was winner of the French Association of Engineering and Information Systems award to the most outstanding technical book of the year.
Back Cover Copy
--Mike Wooldridge, Queen Mary and Westfield College, UK
"This author guides his readers responsibly and engagingly through the best of classical Al-based agent research while opening eyes to a powerful new version Of Swarm-based intelligence. I know of no other book on agents ... that matches its comprehensive treatment and clear, enjoyable exposition." --Dr. H. Van Dyke Parunak Centre for Electronic Commerce, Industrial Technology Institute, Michigan
What are multi-agent systems? How do they work? What do they do?
If you are looking for the answers to these questions, read on; for Jacques Ferber's authoritative book is the first to provide a single, coherent overview of multi-agent systems.
no prior knowledge required
- introduces and defines key concepts throughout the text
- provides numerous examples to illustrate Core principles
- clear, accessible writing style transcends traditional subject area boundaries to make this complex subject understandable to all
the whole picture
- draws on contributions from different disciplines to present a holistic, comprehensive picture of state-of-the art agent technology.
future trends
- describes all the latest developments in the field and encourages the reader to reflect on possibilities for the future
Preface
Over the past few years, multi-agent systems have become more and more important in many aspects of computer science (artificial intelligence, distributed systems, robotics, artificial life ... ) by introducing the issue of collective intelligence and of the emergence of structures through interactions. In focusing on the autonomy of individuals, called 'agents', and on the interactions that link them together, multi-agent systems have raised several questions. What really are the concepts on which this area of study is based? How does it differ from other disciplines, and in particular from the fields of artificial intelligence, distributed systems and robotics? What contributions can it make to the cognitive sciences and to philosophical thought in general?
Research into multi-agent systems demands integrational rather than analytical science, and prompts us to ask a certain number of questions. What is an agent that interacts with other agents? How can they cooperate? What methods of communication are required for them to distribute tasks and coordinate their actions? What architecture can they be given so that they can achieve their goals? These questions are of special importance, since the aim is to create systems possessing particularly interesting characteristics: flexibility, the capacity to adapt to change, the capacity to integrate heterogeneous programs, the capacity to obtain rapid results and so on.
Two major objectives are being pursued by research in the area of multi-agent systems. The first important area is the theoretical and experimental analysis of the self-organization mechanisms which come into play when several autonomous entities interact. The second is the creation of distributed artefacts capable of accomplishing complex tasks through cooperation and interaction. So these researches have a dual aspect: on the one hand, they are centered in the cognitive and social sciences (psychology, ethology, sociology, philosophy and so on) and the natural sciences (ecology, biology and so on), since they simultaneously model, explain and simulate natural phenomena and provide models for self-organization. On the other hand, they can be seen as a practical method, a technique, aimed at creating complex computing systems based on the concepts of agents, communication, cooperation and coordination of actions.
This book came out of several years of experience while I was lecturing on multi-agent systems (MASs) in the DEA IARFA at the Pierre and Marie Curie University (Paris 6). As far as I know, no textbooks dealing with MASs exist. The only works available are published theses, work on specific projects or compilations of articles written by specialists for other specialists in this field, which offer no opportunity for a student or a non-specialist to obtain an integrated overall view of the topic. The research carried out into multi-agent systems, stretching back over nearly 20 years, is extremely wide-ranging, and there are (as yet) no foundations for this discipline which are sufficiently simple and precise to make it easy to give a chronological and structured picture of work in this area. So the first step was to bring all the positions together and establish a conceptual framework for the development of theories in future. That is the purpose behind this book - to bring together the main strands of knowledge relating to this area and to begin to lay down the foundations for a science of interaction, which I have called kenetics (from the Greek term koinon, that which is common).
For the present, this remains a somewhat timid and tentative approach, essentially based on the definition of conceptual frameworks, on certain classifications and formalisations, and on the presentation of a modular method for constructing multi-agent systems. There is a twofold interest in bringing all these areas together. It means that we can eventually escape from the problems caused by differences in notation and by the legitimate meanderings of researchers exploring their field of study, and jointly arrive at a clear view of the issues which can be expressed precisely and simply. We are not there yet, but I hope that the unified language offered in this book will help the non-specialist reader to understand the results achieved by multi-agent systems and the issues involved therein; and that at the same time the book will provide some solid bases which may enable the student or researcher in pursuit of new knowledge to contribute a stone of his or her own to the foundations of this discipline.
Contents of the book
This book contains:
- a survey of the state of the art in relation to the subject;
- a viewpoint on multi-agent systems, presented as a new systemics, which puts the emphasis on the issues of interaction and its consequences;
- a conceptual analysis of the field, based on a classification of the main problems and results and, above all, a functional and structural analysis of the organizations within which all the work being done in this field is carried out;
- a formal system, BRIC, making possible the modular and incremental conception of MASs through the modelling of behaviors, communication structures and the main forms of interaction, which are the allocation of tasks and the coordination of actions;
- an attempt to formalize MASs and interaction, using an action model based on an influence/reaction pairing.
To whom is it addressed?
This book is addressed, first of all, to computer professionals not specializing in this field, who are interested in obtaining an integrated view of it. It is also intended for readers who are not computer scientists, but who specialize in social sciences or natural sciences and want to use multi-agent systems to model natural behaviors and study the emergence of complex phenomena. It is also addressed to readers who are not computer specialists, but who want to obtain some knowledge of the essential concepts which will allow them to understand what is meant by a 'collective intelligence' and to obtain a general view of the issues raised by multi-agent systems. And finally, it is intended as a study resource for second- or third- year computer science students who would like to specialize in this area.
How this book is organized
This book has deliberately been constructed in such a way that the full picture emerges gradually. After a brief introduction to the field and an outline of a general analysis framework for multi-agent systems, the concepts and mechanisms brought into play in multi-agent systems are progressively studied and analyzed. The first part of the book deals with the basic concepts. Chapter I contains a general outline of the field, the most important aspects and their relationship to other disciplines. Chapter 2 introduces the concept of interaction situation, and puts forward a general framework to help readers to appreciate the various elements involved in cooperation. Chapter 3 offers a functional and structural analysis of organizations, together with the various architectures generally used to form conceptions of them. Chapter 4 is intended to act as a bridge between the generalities of the preceding sections and the more detailed descriptions which follow. It tackles the issues of the normalization of action and behavior and of modelling multi-agent systems, and it introduces most of the concepts used in the remainder of the book. It is shown here that the classic concepts of action are not sufficient to provide a clear understanding of interactions. A theory of action is then developed which considers an action as the result of a set of influences generated by agents. This chapter also formalizes a system for modelling agents and multi-agent systems, BRIC, which associates Petri nets with a modular structure. Chapter 5 gives an update on the concept of the mental state of an agent (beliefs, intentions, obligations and so on) and suggests a way of representing the agent's mental dynamics, which takes the form of a modular architecture described in terms of BRIC elements. The final section is devoted to the various conceptual methods and tools which are used to construct cooperative organizations. Chapter 6 relates to communications and describes the modelling of the principal communications structures, with the help of Petri nets. Chapter 7 deals with the study of collaborative organizations in which work is dynamically distributed among the agents. Finally, Chapter 8 presents the main models for coordination of action which manage dynamic articulation of planning and of the carrying out of tasks and which attempt to avoid conflicts. It is further explained here that problems can be resolved by interaction between single agents.
Only two research topics have not been tackled in this book. The first is the application of games theory and economic theories to multi-agent systems. An excellent reference work on this subject is that by Rosenschein and Zlotkin (1994). The second area concerns learning how to use multi-agent systems. A very good survey of the state of the art can be found in Weiss and Sen (1996).
Acknowledgments
This book could not have been written without the help of a great many people who assisted me with their comments, their criticisms and above all their support. I am particularly grateful to Jacqueline Zizi both for her friendship and for reading and rereading my book in its entirety. Her strict and exacting standards were a great help to me, and her tact and encouragement assisted me in maintaining my confidence in this project. I am happy to express my gratitude here. My thanks also go to Philippe Laublet, Alexis Drogoul and Anne Collinot for providing me with constructive comments and criticisms when the book existed only in embryonic form. I found their views very helpful.
I am also grateful to the members of the MIRIAD team - Stephane Bura, Thierry Bouron, Patrice Carle, Christophe Cambier, Eric Jacopin, Karim Zeghal and all I the others. They brought their skills and their dynamic energy to the creation of this research group - a perfect example of a multi-agent system. They provided continual stimulation while this book was in preparation.
I must also thank the students at the DEA IARFA for putting up with my explanations - which I'm sure were sometimes rather confused - of why MASs are so interesting. They helped me to crystallize certain theories and syntheses which have found their way into this book.
Yves Demazeau, Jean Erceau, Les Gasser, Charles Lenay, Jean-Pierre Müller and Jean-François Perrot gave me their friendship, their help and their encouragement, for which I am profoundly grateful.
I must also pay tribute to Pierre Azema, Jean-Paul Barthes, Paul Bourgine, Jean-Pierre Briot, Christian Brassac, Christiano Castelfranchi, Brahim Chaib-Braa, Bruno Corbara, Pascal Estraillier, Dominique Fresneau, France Guérin, Alain Pavé, Joël Quinqueton, Mario Tokoro, Dominique Lestel, Christian Mullon, Gérard Sabah, Lena Sanders, Luc Steels, Jean-Pierre Treuil and many others too numerous to mention here. Their kindness, and the particularly fruitful scientific discussions we had together, were a great help to me.
And finally, I would like to thank all my companions, my family and friends, for their understanding, their unconditional support and their affection over the past few years, during which they must have become all too familiar with the words 'I'm just about to finish my book'.
Table of Contents
1. Principles of Multi-Agent Systems.
In favor of a collective intelligence. From the thinking machine .... ... to artificial organization. Agent and society. Some definitions. Levels of organization. Social or biological? Architecture and behavior. Languages, communications and representations. A little history. The early years. The classical age. The influence of artificial life. Modern times. Areas of application. Problem solving. Multi-agent simulation. The construction of synthetic worlds. Collective robotics. Kenetic program design. Principal aspects of kenetics. The issues of action. The individual and its relationship with the world. Interaction. Adaptation. The creation and implementation of MASs. Areas related to multi-agent systems. Artificial intelligence. Systemics. Distributed systems. Robotics. What is not covered by kenetics. 2. Interactions and Cooperation. Interaction situations. Components of interactions. Compatible and incompatible goals. Relation to resources. Capacities of agents in relation to tasks. Types of interaction. Independence. Simple collaboration. Obstruction. Coordinated collaboration. Pure individual competition. Pure collective competition. Individual conflicts over resources. Collective conflicts over resources. Level of analysis of interaction situations. Forms of cooperation. Cooperation as an intentional posture. Cooperation from the observer's point of view. Increasing survival capacity. Improving performances. Conflict resolution. Methods of cooperation. Grouping and multiplication. Communication. Specialization. Collaborating by sharing tasks and resources. Coordination of actions. Conflict resolution by arbitration and negotiation. Organizations and cooperation. The cooperation activities system. Advantages. Social constraints and emergence of structures. 3. Multi-agent Organizations. What is an organization? Organizational structures and concrete organizations. Levels of organization. How should an organization be studied? Functional analysis. The functions of an organization. Dimensions of analysis. Dimensional analysis of an organization. Grid for functional analysis of organizations. Structural analysis. Agents and tasks. Abstract relationships. Coupling modes. Subordination and decision-making structures. Ways of setting up organizational structures. Concretisation parameters. Analysis of a concrete organization. The example of explorer robots. Organizations with a fixed, hierarchical, predefined structure. Organizations with a variable, egalitarian, emergent structure. Organizations with a variable, egalitarian, predefined structure. Organizations with an evolutionary structure. Other work on organizations. Individual organizations. Table of main types of architecture. Modular horizontal architecture. Blackboard-based architecture. Subsumption architecture. Competitive tasks. Production systems. Classifier-based systems. Connectionist architectures. Architectures based on dynamic systems. Multi-agent based architectures and actors. 4. Action and Behavior. Modelling. The models... ...and how MASs benefit from them. What should be modelled? Agents and actions: deceptively elementary concepts. Modelling action. Actions as transformation of a global state. A functional representation of action. STRIPS-like operators. Planning with STRIPS-like operators. Some plan categories. Limits Of STRIPS-like planners. Limits of classic representations of action. Action as response to influences. General presentation. States. Actions and reactions. Interest of the influences/reactions model for MASs. Action as processes in computer science. Representation of processes by finite-state automata. Register automata. Representation of processes by Petri nets. Other factual models. Action as physical displacement. Displacements in a potential field. Appeal of this conception of action. Action as local modification. Cellular automata. Representation of a cellular automaton. Cellular automata and multi-agent systems. Action as command. Tropistic and hysteretic agents. Tropistic agents. Formal approach. A tropistic multi-agent system. Tropistic agents and situated actions. Flexibility of situated actions. The goals are in the environment. Hysteretic agents. Formal approach. A hysteretic multi-agent system. Modelling of hysteretic agents by automata. Modelling of MASs in BRIC. Describing MASs with the help of components. Modelling of purely communicating MASs. Modelling of environments. Modelling of a situated MAS. Modelling of a complete MAS. An example: transporter agents. 5. States of (Artificial) Minds. Mental states and intentionality. Introduction. The cogniton concept. Types of cogniton. The interactional system. The representational system. What is knowledge? Representing knowledge and beliefs. Logics of learning and beliefs. Adequacy and revision of beliefs. What to believe? Contents of representations. Environmental beliefs. Social beliefs (a). Relational beliefs (a). Personal beliefs (o). The conative system. Rationality and survival. A model of the conative system. Motivations: sources of actions. Personal motivations: pleasure and constraints. Environmental motivations desire for an object. Social motivations: the weight of society. Relational motivations: reason is other people. Commitments: relational and social motivations and constraints. Reactive undertaking of an action. Consumatory acts and appetitive behaviors. Action selection and control modes. Action selection or dynamic combination. Intentional transitions to an action. Logical theories of intentions. Cohen and Levesque's theory of rational action. 6. Communications. Aspects of communication. Signs, indicators and signals. Definition and models of communication. Communication categories. What is communication for? Speech acts. To say is to do. Locutory, illocutory and perlocutory acts. Success and satisfaction. Components of illocutory acts. Conversations. Conversations and finite-state automata. Conversations and Petri nets. A classification of speech acts for multi-agent conversational structures. KQML. 7. Collaboration and Distribution of Tasks. Modes of task allocation. Criteria for breaking down tasks. Roles. Forms of allocation. Centralized allocation of tasks by trader. Distributed allocation of tasks. Acquaintance network allocation. Allocation by the contract net. Variations and hybrid allocations. Contracts and commitments. Integrating tasks and mental states. The SAM system. The hierarchy of architectures. The results. The implementation of architectures. Level 1. Level 2. Level 3. Emergent allocation. An example: the Manta system. General description. The system architecture. Experimentation. From ants to robot ants. 8. Coordination of Actions. What is coordination of actions? Definitions.
Coordination as problem solving. Characteristics of coordination systems. Forms of coordination of actions. Synchronization of actions. Synchronization of movements. Synchronization of access to a resource. Coordination of actions by planning. Multi-agent planning. Centralized planning for multiple agents. Centralized coordination for partial plans. Distributed coordination for partial plans. Reactive coordination. Coordination by situated actions. On pack behavior in anti-collision systems. Marking the environment. Coordination actions. Solving by coordination: eco-problem solving. Principles of eco-problem solving. Eco-agents. Simple examples of eco-problems. Evolutionary universes. Formalisation. Solving constraints by eco-problem solving. 9. Conclusion. Appendix A. The components. Composite components. Constitution of elementary components. Communication links. Notation conventions and equivalents. Translation in the form of Petri nets. Example. Further reading and information on multi-agent systems. Bibliographical references. Index.
|