Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent Systems

by Makoto Yokoo

Overview

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem in which the goal is to find a consistent combination of actions that satisfies these inter-agent constraints. More specifically, a distributed CSP is a constraint satisfaction problem (CSP) in which multiple agents are involved. A constraint satisfaction problem is a problem in which the goal is to find a consistent assignment of values to variables. Even though the definition of a CSP is very simple, a surprisingly wide variety of artificial intelligence (AI) problems can be formalized as CSPs. Therefore, the research on CSPs has a long and distinguished history in AI (Mackworth 1992; Dechter 1992; Tsang 1993; Kumar 1992). A distributed CSP is a CSP in which variables and constraints are distributed among multiple autonomous agents. Various application problems in Multi-agent Systems (MAS) that are concerned with finding a consistent combination of agent actions can he formalized as dis­ tributed CSPs. Therefore, we can consid(~r distributed CSPs as a general framework for MAS, and algorithms for solving distributed CSPs as important infrastructures for cooperation in MAS. This book gives an overview of the research on distributed CSPs, as well as introductory material on CSPs. In Chapter 1. we show the problem defi­ nition of normal, centralized CSPs and describe algorithms for solving CSPs.

Product Details

ISBN-13:	9783642640209
Publisher:	Springer Berlin Heidelberg
Publication date:	10/02/2011
Series:	Springer Series on Agent Technology
Edition description:	Softcover reprint of the original 1st ed. 2001
Pages:	143
Product dimensions:	6.10(w) x 9.25(h) x 0.01(d)

Table of Contents

1. Constraint Satisfaction Problem.- 1.1 Introduction.- 1.2 Problem Definition.- 1.3 Algorithms for Solving CSPs.- 1.4 Hybrid-Type Algorithm of Backtracking and Iterative Improvement.- 1.5 Analyzing Landscape of CSPs.- 1.6 Partial Constraint Satisfaction Problem.- 1.7 Summary.- 2. Distributed Constraint Satisfaction Problem.- 2.1 Introduction.- 2.2 Problem Formalization.- 2.3 Application Problems.- 2.4 Classification of Algorithms for Solving Distributed CSPs.- 2.5 Summary.- 3. Asynchronous Backtracking.- 3.1 Introduction.- 3.2 Assumptions.- 3.3 Simple Algorithms.- 3.4 Asynchronous Backtracking Algorithm.- 3.5 Evaluations.- 3.6 Summary.- 4. Asynchronous Weak-Commitment Search.- 4.1 Introduction.- 4.2 Basic Ideas.- 4.3 Details of Algorithm.- 4.4 Example of Algorithm Execution.- 4.5 Algorithm Completeness.- 4.6 Evaluations.- 4.7 Summary.- 5. Distributed Breakout.- 5.1 Introduction.- 5.2 Breakout Algorithm.- 5.3 Basic Ideas.- 5.4 Details of Algorithm.- 5.5 Example of Algorithm Execution.- 5.6 Evaluations.- 5.7 Discussions.- 5.8 Summary.- 6. Distributed Consistency Algorithm.- 6.1 Introduction.- 6.2 Overview of Distributed ATMS.- 6.3 Distributed Consistency Algorithm Using Distributed ATMS..- 6.4 Example of Algorithm Execution.- 6.5 Evaluations.- 6.6 Summary.- 7. Handling Multiple Local Variables.- 7.1 Introduction.- 7.2 Agent-Prioritization Approach.- 7.3 Asynchronous Weak-Commitment Search with Multiple Local Variables.- 7.4 Evaluations.- 7.5 Summary.- 8. Handling Over-Constrained Situations.- 8.1 Introduction.- 8.2 Problem Formalization.- 8.3 Distributed Maximal CSPs.- 8.4 Distributed Hierarchical CSPs.- 8.5 Summary.- 9. Summary and Future Issues.