Welcome Guest!

Quick Find:  

Advanced Search

Languages: English Español

Valid XHTML 1.0 Transitional ¡CSS Válido! Icono de conformidad con el Nivel Doble-A, 
	de las Directrices de Accesibilidad para el 
	Contenido Web 1.0 del W3C-WAI

Distributed Constraint Satisfaction


Distributed Constraint Satisfaction
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 Table of Contents (0.18 Mb)

Preview Preview (0.21 Mb)

Bibliographic information

Physical Description : XXII, 181 p. : gráf. ; 24 cm

ISBN: 978-84-00-08572-8

Publication: Bellaterra (España) : Consejo Superior de Investigaciones Científicas, 2007

Other data: Thesis. Universidad Politécnica de Cataluña (Spain), 2007

Buy the digital edition at

This eBook is available for free download

Free Downloads

Download eBook Download eBook (1.84 Mb)

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