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

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.