Distributed Constraint Satisfaction

Ismel Brito Rodríguez Affiliation: Consejo Superior de Investigaciones Científicas. Institut d'Investigació en Intel-ligencia Artificial (Bellaterra, España) Biography: Not available Close window

Ismel Brito Rodríguez About the authors  Publication year: 2007 Language: English Subjects: Science and Technology Collection: Monografies de l'Institut d'Investigació en Intel-ligencia Artificial Free eBook

Abstract:

Distributed constraint satisfaction (DisCSP) is a new model of constraint reasoning, where problem elements are distributed among agents and cannot be grouped into a central one for some reasons. A solution, as in the classical case, must satisfy all constraints. In a distributed setting, a solution can be achieved by message passing among agents. This book deals with algorithmic approaches for DisCSP solving. The different types of distributed algorithms, synchronous, asynchronous and hybrids, are analyzed in the DisCSP context. Taking the pioneering work of Makoto Yokoo on asynchronous backtracking as reference algorithm, a number of extensions from a common core are presented here. Among them, we emphasize the new algorithm which does not add new links among agents during the solving process. The extension to non-binary constraints and its practical implementation are also addressed. Good part of this work is devoted to privacy, one of the main motivations for distributed constraint reasoning. A new model of partially known constraints is proposed, to express those constraint problems which appear to be naturally distributed. In this model, new algorithms to preserve privacy are proposed. Looking further to protect privacy, lies are allowed among agents, providing they will tell the truth in finite time afterwards. Unsurprisingly, enforcing privacy causes eficiency in the solving process to decrease. In addition to the conventional evaluation on distributed random problems, this work considers two applications: distributed meeting scheduling and distributed stable matching. Since these problems have been widely studied in their centralized versions, when possible centralized approaches have been extended to the distributed case, and compared with generic distributed approaches, looking for the best solving strategy for these kind of problems.

Table of Contents (0.18 Mb)

Preview (0.21 Mb)

This book was added to our online catalog on Friday 24 April, 2015.