Distributed constraint satisfaction. Foundations of cooperation in multi-agent systems

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Searching and sorting (68P10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27) Nonnumerical algorithms (68W05)

Review text

Constraint satisfaction is a well-known technique in artificial intelligence which can be applied to a large variety of problems. Many algorithms have been developed, and many implementations of these algorithms are available and have been studied. Hence, it is not surprising that the recent developments of dcstributed systems are also successfully extended to this area. Chapter 1 defines constraint satisfaction problems in general and presents the most important algorithms (e.g. backtracking, weak-commitment search, hill-climbing et al.). This introduction is used as the background for distributed constraint satisfaction problems. The given problem is assigned to agents, one agent is responsible for one variable of the problem, constraints are to be considered between different agents. One agent knows all constraints relevant to its variable.Based on these assumptions, the next chapters discuss different methods and algorithms to solve this problem: -- asynchronous backtracking (chapter 3), -- asynchronous weak-commitment search (chapter 4), -- distributed breakout (chapter 5), -- distributed consistency (chapter 6). In chapter 7, the assumption that one agent deals with one variable is deleted, multiple local variables are considered. Chapter 8 shows some over-constrained problems -- the constraints do not allow any solution -- the problem consists now in finding values for the variables so that only a ``small number of constraints remains unsatisfied. The presentation in this book is excellent. Each algorithm is presented by a sequence ``basic ideas -- details of the algorithm -- example of algorithm execution -- evaluation. This allows a very economic representation. The examples are rather small, they allow, however, the understanding of the ideas, and the reader is not overloaded with too many (unimportant) details. By means of this book, an understanding of the problems, solutions and further research fields and topics can be achieved in a rather short time. It is pleasure to read this book.

Recommendations

Cited in

(42)

Describes a project that uses

Uses Software

FASoft

This page was built for publication: Distributed constraint satisfaction. Foundations of cooperation in multi-agent systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2704802)