Arc-consistency in dynamic CSPs is no more prohibitive
Author:
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10823409,p. 299-306
Abstract
Constraint satisfaction problems (CSPs) are widely used in Artificial Intelligence. The problem of the existence of a solution in a CSP being NP-complete, filtering techniques and particularly arc-consistency are essential. They remove some local inconsistencies and so make the search easier. Since many problems in AI require a dynamic environment, the model was extended to dynamic CSPs (DCSPs) and some incremental arc-consistency algorithms were proposed. However, all of them have important drawbacks. DnAC-4 has an expensive worst-case space complexity and a bad average time complexity. AC/DC has a non-optimal worst-case time complexity which prevents from taking advantage of its good space complexity. The algorithm we present in this paper has both lower space requirements and better time performances than DnAC-4 while keeping an optimal worst case time complexity.Keywords
This publication has 5 references indexed in Scilit:
- Arc-consistency and arc-consistency againArtificial Intelligence, 1994
- ChemInform Abstract: Synthia: Assisted Design of Peptide Synthesis PlansChemInform, 1991
- Arc and path consistency revisitedArtificial Intelligence, 1986
- The complexity of some polynomial network consistency algorithms for constraint satisfaction problemsArtificial Intelligence, 1985
- Consistency in networks of relationsArtificial Intelligence, 1977