Distributed Forward Checking
Publication Type:Journal Article
Source:Principles and Practice of Constraint Programming, Volume LNCS 2833, p.801-806 (2003)
A reason to distribute constraint satisfaction is privacy: agents may not want to share their values, and they may wish to keep contraints as private as possible. In this paper, we present the Distributed Forward Checking algorithm, a natural successor of Asynchronous Backtracking, where some privacy is achieved on agent values. Regarding constraints, we introduce the Partially Known Constraints model, which allow a constraint between two agents to be not completely know by any of them. With these elements, we obtain new solving algorithms that enforce privacy and maintain completeness. Empirical results are provided.