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

by Yokoo, Makoto; Etzioni, O.; Ishida, T.; Jennings, N.; Sycara, K.

• ISBN13: 9783540675969
• ISBN10: 3540675965
• eBook ISBN(s): 9783642595462
• Format: Hardcover
• Copyright: 2001-01-01
• Publisher: Springer Verlag

Summary

This book gives an overview of constraint satisfaction problems (CSPs), adapts related search algorithms and consistency algorithms for applications to multi-agent systems, and consolidates recent research devoted to cooperation in such systems. The techniques introduced are applied to various problems in multi-agent systems. Among the new approaches is a hybrid-type algorithm for weak-commitment search combining backtracking and iterative improvement; also, an extension of the basic CSP formalization called partial CSP is introduced in order to handle over-constrained CSPs. The book is written for advanced students and professionals interested in multi-agent systems or, more generally, in distributed artificial intelligence and constraint satisfaction. Researchers active in the area will appreciate this book as a valuable source of reference.

Table of Contents

Constraint Satisfaction Problem	1	(47)
Introduction	1	(1)
Problem Definition	2	(5)
Algorithms for Solving CSPs	7	(13)
Backtracking	8	(7)
Iterative Improvement	15	(1)
Consistency Algorithms	16	(4)
Hybrid-Type Algorithm of Backtracking and Iterative Improvement	20	(8)
Weak-Commitment Search Algorithm	20	(2)
Example of Algorithm Execution	22	(1)
Evaluations	23	(4)
Algorithm Complexity	27	(1)
Analyzing Landscape of CSPs	28	(14)
Introduction	28	(2)
Hill-Climbing Algorithm	30	(2)
Analyzing State-Space	32	(5)
Discussions	37	(5)
Partial Constraint Satisfaction Problem	42	(2)
Introduction	42	(1)
Formalization	43	(1)
Algorithms	43	(1)
Summary	44	(3)
Distributed Constraint Satisfaction Problem	47	(8)
Introduction	47	(1)
Problem Formalization	47	(2)
Application Problems	49	(5)
Recognition Problem	49	(1)
Allocation Problem	50	(3)
Multi-agent Truth Maintenance	53	(1)
Time-Tabling/Scheduling Tasks	53	(1)
Classification of Algorithms for Solving Distributed CSPs	54	(1)
Summary	54	(1)
Asynchronous Backtracking	55	(14)
Introduction	55	(1)
Assumptions	55	(1)
Simple Algorithms	56	(2)
Centralized Method	56	(1)
Synchronous Backtracking	57	(1)
Asynchronous Backtracking Algorithm	58	(8)
Overview	58	(2)
Characteristics of the Asynchronous Backtracking Algorithm	60	(3)
Example of Algorithm Execution	63	(1)
Algorithm Soundness and Completeness	64	(2)
Evaluations	66	(2)
Summary	68	(1)
Asynchronous Weak-Commitment Search	69	(12)
Introduction	69	(1)
Basic Ideas	70	(1)
Details of Algorithm	71	(2)
Example of Algorithm Execution	73	(1)
Algorithm Completeness	74	(1)
Evaluations	75	(3)
Summary	78	(3)
Distributed Breakout	81	(12)
Introduction	81	(1)
Breakout Algorithm	81	(1)
Basic Ideas	82	(2)
Details of Algorithm	84	(1)
Example of Algorithm Execution	85	(2)
Evaluations	87	(5)
Discussions	92	(1)
Summary	92	(1)
Distributed Consistency Algorithm	93	(8)
Introduction	93	(1)
Overview of Distributed ATMS	93	(1)
ATMS	93	(1)
Distributed ATMS	94	(1)
Distributed Consistency Algorithm Using Distributed ATMS	94	(2)
Example of Algorithm Execution	96	(1)
Evaluations	97	(3)
Summary	100	(1)
Handling Multiple Local Variables	101	(12)
Introduction	101	(1)
Agent-Prioritization Approach	102	(1)
Asynchronous Weak-Commitment Search with Multiple Local Variables	103	(4)
Basic Ideas	103	(1)
Details of Algorithm	104	(1)
Example of Algorithm Execution	104	(3)
Evaluations	107	(3)
Summary	110	(3)
Handling Over-Constrained Situations	113	(20)
Introduction	113	(1)
Problem Formalization	113	(1)
Distributed Maximal CSPs	114	(9)
Problem Formalization	114	(1)
Algorithms	115	(5)
Evaluations	120	(3)
Distributed Hierarchical CSPs	123	(9)
Problem Formalization	123	(1)
Asynchronous Incremental Relaxation	124	(4)
Example of Algorithm Execution	128	(1)
Algorithm Completeness	129	(1)
Evaluations	129	(3)
Summary	132	(1)
Summary and Future Issues	133