Cover image for Multi-agent systems : an introduction to distributed artificial intelligence
Title:
Multi-agent systems : an introduction to distributed artificial intelligence
Author:
Ferber, Jacques.
Personal Author:
Uniform Title:
Systèmes multi-agents. English
Publication Information:
Harlow : Addison-Wesley, 1999.
Physical Description:
xviii, 509 pages : illustrations ; 24 cm
General Note:
Translation of: Les systèmes multi-agents.
Language:
English
ISBN:
9780201360486
Format :
Book

Available:*

Library
Call Number
Material Type
Home Location
Status
Item Holds
Searching...
TJ217.5 .F5313 1999 Adult Non-Fiction Non-Fiction Area
Searching...

On Order

Summary

Summary

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.


Author Notes

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.


Excerpts

Excerpts

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: 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 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'. 0201360489P04062001 Excerpted from Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence by Jacques Ferber All rights reserved by the original copyright owners. Excerpts are provided for display purposes only and may not be reproduced, reprinted or distributed without the written permission of the publisher.

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