One of the most widely used search formalisms is the constraint satisfaction problem (CSP), which represents a problem as a set of variables, a set of finite discrete domains for each of the variables, and a set of constraints. The constraints are Boolean predicates over the Cartesian product of the domains, specifying whether a particular set of assignments to the variables is acceptable (True) or not (False). The binary nature of constraints reflects a hard constraint in a problem, one that cannot be violated. A solution to the problem is an assignment to each variable from its domain, such that all the constraints evaluate to “True.” This approach enjoys a large community of practice with a high degree of cohesiveness and interaction, a rich and interesting toolbox of techniques, and a significant track record of successful applications.

Classical CSP algorithms assume that a single program has access to all of the variables and constraints, and specify how that program should try different assignments to satisfy all the constraints. In some application domains, this assumption is not justified. For example, in many commercial applications, variables or constraints may represent proprietary information. A company may be willing to tell its associates whether or not various external values are consistent with its constraints, but be unwilling to divulge a complete account of its reasoning so that a centralized CSP program can be constructed.

For the past decade, Yokoo has explored ways of distributing the reasoning about CSPs over multiple agents. This volume draws together the results of his research into a coherent and accessible account. His basic approach is to start with a recognized algorithm from the centralized CSP literature, and develop ways to distribute it over multiple agents.

Chapter 1 introduces the terminology and fundamental algorithms of classical CSP. It includes a helpful discussion of the landscape of CSPs, which uses the language of phase transitions to study how problem difficulty is related to the ratio of unsolvable problems. Chapter 2 is a general introduction to distributed CSPs, including a survey of applications. Subsequent chapters develop specific techniques, including asynchronous backtracking (chapter 3), asynchronous weak commitment (chapter 4), distributed breakout (chapter 5), and distributed consistency algorithms (chapter 6).

These algorithms, and the formalism of the distributed CSP on which they are based, assume that each agent is responsible for a single variable, that and constraints are shared among the agents whose variables are referenced by that constraint. Chapter 7 moves from single-variable agents to multiple-variable agents, but still assumes that variables map to agents and that constraints are shared. Readers should be aware of two alternative ways of mapping a CSP onto multiple agents, which may be more natural in some applications. One may assign each constraint to a different agent and share variables among agents (Liu and Sycara [1]). Alternatively, one may have two interacting species of agents, one species with variable agents and another with constraint agents (Parunak, Ward and Sauter [2]).

Chapter 8 introduces the problem of over-constrained situations; those in which no assignment to variables exists that can satisfy all the constraints. The broader CSP community addresses such problems by selecting some subset of the constraints to relax. A typical approach is to prioritize the constraints and drop low-priority constraints until the problem has a solution. Yokoo shows how to extend this partial satisfaction approach to distributed setting. While interesting from a theoretical perspective, this approach seems unnatural. Real-world applications often have “soft” constraints that can be relaxed without being abandoned entirely. Formally, a soft constraint is real-valued rather than binary. A typical approach maps hard constraints onto {0,1} and soft constraints onto [0,1], where 1 represents complete satisfaction and 0 represents complete violation. The success criterion shifts from the satisfaction of all constraints to the maximization of the sum of the constraint values achieved. This formalism describes the constraint optimization problem (COP), which also enjoys both centralized and distributed practitioners, but which Yokoo does not discuss. If all constraints cannot be satisfied and one still seeks a solution, the violated constraints are perforce soft, not hard, and COP is more appropriate than CSP. It is not at all obvious that the solution reached by optimizing the sum of utilities achieved over a complete set of constraints is the same as the one that will be reached by a CSP that ignores low-priority constraints entirely. CSP researchers will value chapter 8 for showing how their specialty can be extended to new situations. A user with a real problem will be more interested in a comparison of alternative tools.

The book’s bibliography extends only through 1998, and thus excludes some of Yokoo’s more recent results. The index is brief, but the excellent organization of the chapters will make it possible for readers to find the material they need quickly. Overall, this volume is an essential addition to the literature of both distributed AI and constraint satisfaction.