Page iii
Multiagent Systems
A Modern Approach to Distributed Modern Approach to Artificial Intelligence
edited by Gerhard Weiss
The MIT Press
Cambridge, Massachusetts
London, England
©1999 Massachusetts Institute of Technology
All rights reserved. No part of the book may be reproduced in any form by any
electronic or mechanical means (including photocopying, recording, or information
storage and retrieval) without permission in writing from the publisher.
This book was set in Computer Modern by Gerhard Weiss.
Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Page iv
Multiagent systems: a modern approach to distributed artificial intelligence / edited
by Gerhard Weiss
p. cm.
Includes bibliographical references and index.
ISBN 0-262-23203-0 (hardcover: alk. paper)
1. Intelligent agents (Computer software) 2. Distributed artificial intelligence.
I. Weiss, Gerhard, 1962- .
QA76.76.I58M85 1999
006.3—dc21 98-49797
CIP
CONTENTS IN BRIEF
Contributing Authors
Preface
Prologue
Part I: Basic Themes
1
Intelligent Agents
Michael Wooldridge
2
Multiagent Systems and Societies of Agents
Michael N. Huhns and Larry M. Stephens
3
Distributed Problem Solving and Planning
Edmund H. Durfee
4
Search Algorithms for Agents
Makoto Yokoo and Toru Ishida
Page v
xix
xxi
1
27
79
121
165
5
Distributed Rational Decision Making
Thomas W. Sandholm
6
Learning in Multiagent Systems
Sandip Sen and Gerhard Weiss
7
Computational Organization Theory
Kathleen M. Carley and Les Gasser
8
Formal Methods in DAI: Logic-Based Representation and Reasoning
Munindar P. Singh, Anand S. Rao, and Michael P. Georgeff
9
Industrial and Practical Applications of DAIH.
Van Dyke Parunak
Part II: Related Themes
10
Groupware and Computer Supported Cooperative Work
Clarence Ellis and Jacques Wainer
11
Distributed Models for Decision Support
Jose Cuena and Sascha Ossowski
12
Concurrent Programming for DAI
Gul A. Agha and Nadeem Jamali
201
259
299
331
377
125
459
505
Page vi
13
Distributed Control Algorithms for AI
Geraint Tel
Glossary
Subject Index
CONTENTS IN DETAIL
Contributing Authors
Preface
Purpose, Features, Readership, How to Use This Book, One Final Word,
Acknowledgments
Prologue
Multiagent Systems and Distributed Artificial Intelligence
Intelligent Agents that Interact
Challenging Issues
Applications
Rationales for Multiagent Systems
A Guide to This Book
The Chapters
The Exercises
Page vii
539
583
609
xix
xxi
1
1
2
5
6
8
9
9
19
The Glossary
A Few Pointers to Further Readings
References
Part I: Basic Themes
1
Intelligent Agents
Michael Wooldridge
1.1 Introduction
1.2 What Are Agents?
1.2.1 Examples of Agents
1.2.2 Intelligent Agents
1.2.3 Agents and Objects
1.2.4 Agents and Expert Systems
1.3 Abstract Architectures for Intelligent Agents
1.3.1 Purely Reactive Agents
1.3.2 Perception
1.3.3 Agents with State
1.4 Concrete Architectures for Intelligent Agents
1.4.1 Logic-based Architectures
1.4.2 Reactive Architectures
19
20
21
27
27
28
31
32
34
36
36
38
38
40
42
42
48
Page viii
1.4.3 Belief-Desire-Intention Architectures
1.4.4 Layered Architectures
1.5 Agent Programming Languages
1.5.1 Agent-Oriented Programming
1.5.2 Concurrent METATEM
1.6 Conclusions
1.7 Exercises
1.8 References
2
Multiagent Systems and Societies of Agents
Michael N. Huhns and Larry M. Stephens
2.1 Introduction
2.1.1 Motivations
2.1.2 Characteristics of Multiagent Environments
2.2 Agent Communications
2.2.1 Coordination
2.2.2 Dimensions of Meaning
2.2.3 Message Types
2.2.4 Communication Levels
2.2.5 Speech Acts
2.2.6 Knowledge Query and Manipulation Language (KQML)
2.2.7 Knowledge Interchange Format (KIF)
54
61
66
67
69
70
71
73
79
79
80
81
83
83
84
85
86
87
88
92
2.2.8 Ontologies
2.2.9 Other Communication Protocols
2.3 Agent Interaction Protocols
2.3.1 Coordination Protocols
2.3.2 Cooperation Protocols
2.3.3 Contract Net
2.3.4 Blackboard Systems
2.3.5 Negotiation
2.3.6 Multiagent Belief Maintenance
2.3.7 Market Mechanisms
2.4 Societies of Agents
2.5 Conclusions
2.6 Exercises
2.7 References
3
Distributed Problem Solving and Planning
Edmund H. Durfee
3.1 Introduction
3.2 Example Problems
3.3 Task Sharing
94
95
96
97
99
100
103
104
107
109
111
114
114
118
121
121
122
124
Page ix
3.3.1 Task Sharing in the Tower of Hanoi (Toll) Problem
3.3.2 Task Sharing in Heterogeneous Systems
3.3.3 Task Sharing for Distributed Sensor Network Establishment (DSNE)
3.3.4 Task Sharing for Interdependent Tasks
3.4 Result Sharing
3.4.1 Functionally Accurate Cooperation
3.4.2 Shared Repositories and Negotiated Search
3.4.3 Distributed Constrained Heuristic Search
3.4.4 Organizational Structuring
3.4.5 Communication Strategies
3.4.6 Task Structures
3.5 Distributed Planning
3.5.1 Centralized Planning for Distributed Plans
3.5.2 Distributed Planning for Centralized Plans
3.5.3 Distributed Planning for Distributed Plans
3.6 Distributed Plan Representations
3.7 Distributed Planning and Execution
3.7.1 Post-Planning Coordination
3.7.2 Pre-Planning Coordination
3.7.3 Interleaved Planning, Coordination, and Execution
3.7.4 Runtime Plan Coordination Without Communication
125
127
129
130
131
131
133
133
135
137
138
139
139
140
141
149
151
151
152
153
156