Restricted Path Consistency Enforcement for any Constraint Network(Artificial Intelligence I)

概要

論文の詳細を見る
Local consistency techniques (LC) are in the core of the constraint programming paradigm due to their preminent role in its success. The main objective of these techniques is to prune the search space and consequently to enhance the efficiency of the constraints solver. Several levels were proposed among which arc consistency (AC) is the most used one due to its low time and space complexities. However, 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 more powerful levels. For some hard CNs 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 DRAG approach (Distributed.Reinforcement of Arc-Consistency) to achieve higher level of local consistency, the restricted path consistency (RFC) 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 constraint network (CN), especially for hard arc-consistent problems.
一般社団法人情報処理学会の論文
2004-12-04