×

zbMATH — the first resource for mathematics

Using constraint metaknowledge to reduce arc consistency computation. (English) Zbl 0911.68192
Summary: Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values for problem variables subject to constraints that specify which combinations of values are consistent. Knowledge about properties of the constraints can permit inferences that reduce the cost of consistency checking. In particular, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a fundamental constraint-based reasoning technique. A general AC-Inference algorithm schema is presented and various forms of inference discussed. A specific algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform. The effectiveness of this approach is demonstrated analytically, and experimentally.

MSC:
68T30 Knowledge representation
68W10 Parallel algorithms in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bessière, C.; Cordier, M.O., Arc-consistency and arc-consistency again, (), 108-113
[2] Bessière, C., Arc-consistency and arc-consistency again, Artificial intelligence, 65, 179-190, (1994)
[3] Bessière, C.; Freuder, E.C.; Régin, J.C., Using inference to reduce arc consistency computation, (), 592-598
[4] Bessière, C.; Régin, J.C., Using bidirectionality to speed up arc-consistency processing, (), 157-169
[5] Bessière, C.; Régin, J.C., MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems, (), 61-75
[6] Bessière, C.; Régin, J.C., Arc consistency for general constraint networks: preliminary results, (), 398-404
[7] Deville, Y.; Van Hentenryck, P., An efficient arc consistency algorithm for a class of CSP problems, (), 325-330 · Zbl 0747.68066
[8] Frost, D.; Bessière, C.; Dechter, R.; Regin, J.C., Random uniform CSP generators, (1996)
[9] Freuder, E.C., Synthesizing constraint expressions, Comm. ACM, 21, 11, 958-966, (1978) · Zbl 0386.68065
[10] Freuder, E.C., Using metalevel constraint knowledge to reduce constraint checking, (), 171-184
[11] Gaschnig, J., Experimental case studies of backtrack vs. waltz-type vs. new algorithms for satisficing assignment problems, (), 268-277
[12] Gent, I.P.; MacIntyre, E.; Prosser, P.; Shaw, P.; Walsh, T., The constrainedness of arc consistency, (), 327-340
[13] Grant, S.A.; Smith, B.M., The arc and path consistency phase transitions, (), 541-542
[14] Grant, S.A.; Smith, B.M., The phase transition behavior of maintaining arc consistency, (), 175-179
[15] Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[16] Mackworth, A.K.; Freuder, E.C., The complexity of constraint satisfaction revisited, Artificial intelligence, 59, 57-62, (1993)
[17] Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artificial intelligence, 28, 225-233, (1986)
[18] Perlin, M., Arc consistency for factorable relations, Artificial intelligence, 53, 329-342, (1992) · Zbl 1193.68140
[19] Régin, J.C., Développement d’outils algorithmiques pour l’intelligence artificielle, application à la chimie organique, ()
[20] Sabin, D.; Freuder, E.C., Contradicting conventional wisdom in constraint satisfaction, ()
[21] Van Hentenryck, P.; Deville, Y.; Teng, C.M., A generic arc-consistency algorithm and its specializations, Artificial intelligence, 57, 291-321, (1992) · Zbl 0763.68059
[22] Wallace, R.J., Why AC-3 is almost always better than AC-4 for establishing arc consistency in CSPS, ()
[23] Wallace, R.J.; Freuder, E.C., Ordering heuristics for arc consistency algorithms, (), 163-169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.