Performing more than AC for Hard Distributed Constraint Satisfaction Problems

Constraint satisfaction problem (CSP) framework is essentially characterized by the ubiquitous use of local consistency properties and enforcing techniques. The main objective of these techniques is to prune the search space and consequently to enhance the efficiency of the constraint solver. Several levels of local consistency were proposed in the literature among which arc consistency (AC) is the most used one due to its low time and space complexities. However, with the omnipresence of natural distributed real world applications, recently few efforts were directed to enforce local consistency in an entirely distributed manner. Nevertheless, most of these works are limited only to AC property due to the effective-cost of the other existing stronger forms. For some hard constraint network (CN) applying only AC enforcement may be fruitless, case of problems initially arc-consistent. In an attempt to overcome these limitations, the main contribution of this paper is to propose a refinement of the DRAC approach (distributed reinforcement of arc-consistency) to achieve higher level of local consistency, the restricted path consistency (RPC) in a distributed manner with the minimal amount of additional constraint checks, a comprehensive empirical study was performed to highlight the benefit of using the collected knowledge for enforcing arc-consistency on any binary CN, especially for hard arc-consistent problems. The inferred knowledge is used to prune some path inconsistent values (not all of them). The new approach DRAC/sup ++/ is discussed in terms of termination and complexity.