Name
Abstract | ||
|---|---|---|
Arc consistency filtering is widely used in the framework of binary constraint satisfaction problems: with a low complex- ity, inconsistency may be detected and domains are filtered. In this paper, we show that when detecting inconsistency is the objective, a systematic domain filtering is useless and a lazy approach is more adequate. Whereas usual arc consis- tency algorithms produce the maximum arc consistent sub- domain, when it exists, we propose a method, called , which only looks for any arc consistent sub-domain. The algorithm is then extended to provide the additional service of locating one variable with a minimum domain car- dinality in the maximum arc consistent sub-domain, without necessarily computing all domain sizes. Finally, we compare traditional AC enforcing and lazy AC enforcing using several benchmark problems, both randomly generated CSP and real life problems. The Constraint Satisfaction Problem(CSP) framework is increasingly used to represent and solve numerous OR and AI problems. When constraints are binary, arc consis- tency filtering is one of the most prominent filtering tech- niques, applied either before any search, or incrementally during backtrack search: (1) it has a limited space and time worst-case complexity, (2) if a domain becomes empty while filtering, the inconsistency of the problem is proven, (3) otherwise, variable domains are filtered and the search for a solution can start on a reduced space. On some problems, systematic domain filtering may be- come unproductive and costly. This observation has already been made about forward-checking in (ZE89) and largely clarified in (DM94): the only possible cause for backtrack being a wipe-out, it suffices to prove that at least one value remains in each filtered domain. Obviously the worst-case complexity is the same as for usual forward-checking and the average-case behavior is far better, especially when the domains are large. This paper is devoted to a similar approach applied to arc consistency filtering. Traditional AC filtering try to produce, when it exists, the maximum arc consistent sub- domain. If this maximum arc consistent sub-domain does not exist (a domain wipe-out occurred), inconsistency is proven. If it exists, it can be used as a basis for a fur- ther search, since removed values cannot take part in any solution. When considering wipe-out detection only, the computation of the maximum arc consistent sub-domain is useless and one arc consistent sub-domain is sufficient since it proves the absence of wipe-out. In some cases, wipe-out detection alone is not enough: backtrack tree-search algorithms such as Really Full Look- Aheador MACalso use domain sizes as a heuristic to choose the next variable to instanciate. Lazy arc consistency can then be extended to provide the additional service of locating one variable with a minimum domain size in the maximum arc consistent domain, without exhaustive filtering. After a short introduction to constraint satisfaction prob- lems and arc consistency, lazy arc consistency filtering is introduced and the corresponding algorithm, called , is described. We prove its correctness and study its space and time complexity. We then extend the algorithm in order to locate a variable with a minimum domain size and we experiment and compare these algorithms with traditional AC enforcing algorithms. |
Year | Venue | Keywords |
|---|---|---|
1996 | National Conference on Artificial Intelligence | maximum arc consistent sub-domain,arc consistency,arc consistent sub-domain,usual arc consistency algorithm,lazy arc consistency,lazy ac,systematic domain,lazy approach,maximum arc consistent subdomain,minimum domain cardinality,domain size,artificial intelligence,constraint satisfaction,constraint satisfaction problem,time complexity,algorithms,search algorithm,forward checking,reliability |
Field | DocType | ISBN |
Local consistency,Mathematical optimization,Arc (geometry),Computer science,Cardinality,Filter (signal processing),Algorithm,Theoretical computer science,Artificial intelligence,Machine learning,Binary constraint | Conference | 0-262-51091-X |
Citations | PageRank | References |
14 | 1.63 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Schiex | 1 | 1509 | 123.12 |
| Jean-charles Régin | 2 | 1312 | 96.59 |
| Christine Gaspin | 3 | 54 | 7.68 |
| Gérard Verfaillie | 4 | 578 | 61.44 |