Restricted Path Consistency Enforcement for any Constraint Network

• Item type: SIG Technical Reports(1)
• 公開日: 2004-12-04
• タイトル: Restricted Path Consistency Enforcement for any Constraint Network
• タイトル / 言語: en
• タイトル: Restricted Path Consistency Enforcement for any Constraint Network
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Knowledge Creating Methodology Laboratory Japan Advanced Institute of Science and Technology
• 著者所属: Knowledge Creating Methodology Laboratory Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Knowledge Creating Methodology Laboratory Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Knowledge Creating Methodology Laboratory Japan Advanced Institute of Science and Technology
• 著者名: AHLEMBENHASSINE; TUBAOHO
• 著者名(英): Ahlem, BenHassine; Tu, BaoHo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 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 constraint network (CN) especially for hard arc-consistent problems.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 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 constraint network (CN), especially for hard arc-consistent problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11135936
• 書誌情報: 情報処理学会研究報告知能と複雑系（ICS）; 巻 2004, 号 125(2004-ICS-138), p. 79-84, 発行日 2004-12-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会