Cover image for Multiagent systems : a modern approach to distributed artificial intelligence
Title:
Multiagent systems : a modern approach to distributed artificial intelligence
Publication Information:
Cambridge, Mass. : The MIT Press, 1999
ISBN:
9780262232036
Subject Term:
Intelligent agents (Computer software)

Distributed artificial intelligence
Added Author:
Weiss, Gerhard

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
 30000004209346 QA76.76.I58 M84 1999 Open Access Book Book
Searching...

On Order

Summary

Summary

This is the first comprehensive introduction to multiagent systems and contemporary distributed artificial intelligence that is suitable as a textbook.


Author Notes

Gerhard Weiss is a Research Scientist in the Computer Science Department at the Technical University of Munich.


Table of Contents

Contributing Authors
Preface
Prologue
Part I Basic Themes
1 Intelligent Agents
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
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
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)
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
3.1 Introduction
3.2 Example Problems
3.3 Task Sharing
3.3.1 Task Sharing in the Toll Problem
3.3.2 Task Sharing in Heterogeneous Systems
3.3.3 Task Sharing for 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
3.8 Conclusions
3.9 Exercises
3.10 References
4 Search Algorithms for Agents
4.1 Introduction
4.2 Constraint Satisfaction
4.2.1 Definition of a Constraint Satisfaction Problem
4.2.2 Filtering Algorithm
4.2.3 Hyper-Resolution-Based Consistency Algorithm
4.2.4 Asynchronous Backtracking
4.2.5 Asynchronous Weak-Commitment Search
4.3 Path-Finding Problem
4.3.1 Definition of a Path-Finding Problem
4.3.2 Asynchronous Dynamic Programming
4.3.3 Learning Real-Time A*
4.3.4 Real-Time A*
4.3.5 Moving Target Search
4.3.6 Real-Time Bidirectional Search
4.3.7 Real-Time Multiagent Search
4.4 Two-Player Games
4.4.1 Formalization of Two-Player Games
4.4.2 Minimax Procedure
4.4.3 Alpha-Beta Pruning
4.5 Conclusions
4.6 Exercises
4.7 References
5 Distributed Rational Decision Making
5.1 Introduction
5.2 Evaluation Criteria
5.2.1 Social Welfare
5.2.2 Pareto Efficiency
5.2.3 Individual Rationality
5.2.4 Stability
5.2.5 Computational Efficiency
5.2.6 Distribution and Communication Efficiency
5.3 Voting
5.3.1 Truthful Voters
5.3.2 Strategic (Insincere) Voters
5.4 Auctions
5.4.1 Auction Settings
5.4.2 Auction Protocols
5.4.3 Efficiency of the Resulting Allocation
5.4.4 Revenue Equivalence and Non-Equivalence
5.4.5 Bidder Collusion
5.4.6 Lying Auctioneer
5.4.7 Bidders Lying in Non-Private-Value Auctions
5.4.8 Undesirable Private Information Revelation
5.4.9 Roles of Computation in Auctions
5.5 Bargaining
5.5.1 Axiomatic Bargaining Theory
5.5.2 Strategic Bargaining Theory
5.5.3 Computation in Bargaining
5.6 General Equilibrium Market Mechanisms
5.6.1 Properties of General Equilibrium
5.6.2 Distributed Search for a General Equilibrium
5.6.3 Speculative Strategies in Equilibrium Markets
5.7.1 Task Allocation Negotiation
5.7.2 Contingency Contracts and Leveled Commitment Contracts
5.8 Coalition Formation
5.8.1 Coalition Formation Activity 1: Coalition Structure Generation
5.8.2 Coalition Formation Activity 2: Optimization within a Coalition
5.8.3 Coalition Formation Activity 3: Payoff Division
5.9 Conclusions
5.10 Exercises
5.11 References
6 Learning in Multiagent Systems
6.1 Introduction
6.2 A General Characterization
6.2.1 Principal Categories
6.2.2 Differencing Features
6.2.3 The Credit-Assignment Problem
6.3 Learning and Activity Coordination
6.3.1 Reinforcement Learning
6.3.2 Isolated, Concurrent Reinforcement Learners
6.3.3 Interactive Reinforcement Learning of Coordination
6.4 Learning about and from Other Agents
6.4.1 Learning Organizational Roles
6.4.2 Learning in Market Environments
6.4.3 Learning to Exploit an Opponent
6.5 Learning and Communication
6.5.1 Reducing Communication by Learning
6.5.2 Improving Learning by Communication
6.6 Conclusions
6.7 Exercises
6.8 References
7 Computational Organization Theory
7.1 Introduction
7.1.1 What Is an Organization?
7.1.2 What Is Computational Organization Theory?
7.1.3 Why Take a Computational Approach?
7.2 Organizational Concepts Useful in Modeling Organizations
7.2.1 Agent and Agency
7.2.2 Organizational Design
7.2.3 Task
7.2.4 Technology
7.3 Dynamics
7.4 Methodological Issues
7.4.1 Virtual Experiments and Data Collection
7.4.2 Validation and Verification
7.4.3 Computational Frameworks
7.5 Conclusions
7.6 Exercises
7.7 References
8 Formal Methods in DAI: Logic-Based Representation and Reasoning
8.1 Introduction
8.2 Logical Background
8.2.1 Basic Concepts
8.2.2 Propositional and Predicate Logic
8.2.3 Modal Logic
8.2.4 Deontic Logic
8.2.5 Dynamic Logic
8.2.6 Temporal Logic
8.3 Cognitive Primitives
8.3.1 Knowledge and Beliefs
8.3.2 Desires and Goals
8.3.3 Intentions
8.3.4 Commitments
8.3.5 Know-How
8.3.6 Sentential and Hybrid Approaches
8.3.7 Reasoning with Cognitive Concepts
8.4 BDI Implementations
8.4.1 Abstract Architecture
8.4.2 Practical System
8.5 Coordination
8.5.1 Architecture
8.5.2 Specification Language
8.5.3 Common Coordination Relationships
8.6 Communications
8.6.1 Semantics
8.6.2 Ontologies
8.7 Social Primitives
8.7.1 Teams and Organizational Structure
8.7.2 Mutual Beliefs and Joint Intentions
8.7.3 Social Commitments
8.7.4 Group Know-How and Intentions
8.8 Tools and Systems
8.8.1 Direct Implementations
8.8.2 Partial Implementations
8.8.3 Traditional Approaches
8.9 Conclusions
8.10 Exercises
References
9 Industrial and Practical Applications of DAI
9.1 Introduction
9.2 Why Use DAI in Industry?
9.3 Overview of the Industrial Life-Cycle
9.4 Where in the Life Cycle Are Agents Used?
9.4.1 Questions that Matter
9.4.2 Agents in Product Design
9.4.3 Agents in Planning and Scheduling
9.4.4 Agents in Real-Time Control
9.5 How Does Industry Constrain the Life Cycle of an Agent-Based System?
9.5.1 Requirements, Positioning, and Specification
9.5.2 Design: the Conceptual Context
9.5.3 Design: the Process
9.5.4 System Implementation
9.5.5 System Operation
9.6 Development Tools
9.7 Conclusions
9.8 Exercises
9.9 References
Part II Related Themes
10 Groupware and Computer Supported Cooperative Work
10.1 Introduction
10.1.1 Well-Known Groupware Examples
10.2 Basic Definitions
10.2.1 Groupware
10.2.2 Computer Supported Cooperative Work (CSCW)
10.3 Aspects of Groupware
10.3.1 Keepers
10.3.2 Coordinators
10.3.3 Communicators
10.3.4 Team-Agents
10.3.5 Agent Models
10.3.6 An Example of Aspect Analysis of a Groupware
10.4 Multi-Aspect Groupware
10.4.1 Chautauqua -- A Multi-Aspect System
10.5 Social and Group Issues in Designing Groupware Systems
10.6 Supporting Technologies and Theories
10.6.1 Keepers
10.6.2 Coordinators
10.6.3 Communicators
10.6.4 Team-Agents
10.7 Other Taxonomies of Groupware
10.7.1 Space/Time Matrix
10.7.2 Application Area
10.8 Groupware and Internet
10.8.1 Internet as Infrastructure
10.8.2 Internet as Presumed Software
10.9 Conclusions
10.9.1 Incorporating Communicators into Keepers
10.9.2 Incorporating Keepers and Communicators into Coordinators
10.9.3 Future Research on Agents
10.9.4 Future Research on Keepers
10.10 Exercises
10.11 References
11 Distributed Models for Decision Support
11.1 Introduction
11.2 Decision Support Systems
11.2.1 The Decision Support Problem
11.2.2 Knowledge-Based Decision Support
11.2.3 Distributed Decision Support Models
11.3 An Agent Architecture for Distributed DSSs
11.3.1 Information Model
11.3.2 Knowledge Model
11.3.3 Control Model
11.4 Application Case Studies
11.4.1 Environmental Emergency Management
11.4.2 Energy Management
11.4.3 Road Traffic Management
11.5 Conclusions
11.6 Exercises
11.7 References
12 Concurrent Programming for DAI
12.1 Introduction
12.2 Defining Multiagent Systems
12.3 Actors
12.3.1 Semantics of Actors
12.3.2 Equivalence of Actor Systems
12.3.3 Actors and Concurrent Programming
12.4 Representing Agents as Actors
12.4.1 Mobility of Actors
12.4.2 Resource Model
12.5 Agent Ensembles
12.5.1 Customizing Execution Contexts
12.5.2 Interaction Protocols
12.5.3 Coordination
12.5.4 Naming and Groups
12.6 Related Work
12.7 Conclusions
12.8 Exercises
12.9 References
13 Distributed Control Algorithms for AI
13.1 Introduction
13.1.1 Model of Computation
13.1.2 Complexity Measures
13.1.3 Examples of Distributed Architectures in AI
13.2 Graph Exploration
13.2.1 Depth-First Search
13.2.2 Pseudo-Fast Exploration: the Echo Algorithm
13.2.3 Searching for Connectivity Certificates
13.3 Termination Detection
13.3.1 Problem Definition
13.3.2 Tracing Algorithms
13.3.3 Probe Algorithms
13.4 Distributed Arc Consistency and CSP
13.4.1 Constraint Satisfaction and Arc Consistency
13.4.2 The AC4 Algorithm
13.4.3 The Distributed AC4 Algorithm
13.4.4 Termination Detection
l3.4.5 Partitioning for Multiprocessor Computers
13.4.6 Distributed Constraint Satisfaction Algorithm
13.5 Distributed Graph Processing
13.5.1 The Problem: Loop Cutset
13.5.2 Distributed Execution of the Algorithm
13.5.3 Complexity and Conclusions
13.6 Conclusions
13.7 Exercises
13.8 References
Glossary
Subject Index