Multi-agent systems: An introduction to distributed artificial intelligence

Description

In this book, Jacques Ferber has brought together all the recent developments in the field of multi-agent systems - an area that has seen increasing interest and major developments over the last few years. The author draws on work carried out in various disciplines, including information technology, sociology and cognitive psychology to provide a coherent and instructive picture of the current state-of-the-art. The book introduces and defines the fundamental concepts that need to be understood, clearly describes the work that has been done, and invites readers to reflect upon the possibilities of the future.

Sample Content

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 influence

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 koïnon, 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:

1. a survey of the state of the art in relation to the subject;
2. a viewpoint on multi-agent systems, presented as a new systemics, which puts the emphasis on the issues of interaction and its consequences;
3. 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;
4. 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;
5. 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 Barthès, 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'.

Updates

Submit Errata