×

zbMATH — the first resource for mathematics

Reasoning from last conflict(s) in constraint programming. (English) Zbl 1185.68645
Summary: Constraint programming is a popular paradigm to deal with combinatorial problems in artificial intelligence. Backtracking algorithms, applied to constraint networks, are commonly used but suffer from thrashing, i.e., the fact of repeatedly exploring similar subtrees during search. An extensive literature has been devoted to prevent thrashing, often classified into look-ahead (constraint propagation and search heuristics) and look-back (intelligent backtracking and learning) approaches. In this paper, we present an original look-ahead approach that allows to guide backtrack search toward sources of conflicts and, as a side effect, to obtain a behavior similar to a backjumping technique.
The principle is the following: after each conflict, the last assigned variable is selected in priority, so long as the constraint network cannot be made consistent. This allows us to find, following the current partial instantiation from the leaf to the root of the search tree, the culprit decision that prevents the last variable from being assigned. This way of reasoning can easily be grafted to many variations of backtracking algorithms and represents an original mechanism to reduce thrashing. Moreover, we show that this approach can be generalized so as to collect a (small) set of incompatible variables that are together responsible for the last conflict. Experiments over a wide range of benchmarks demonstrate the effectiveness of this approach in both constraint satisfaction and automated artificial intelligence planning.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
PDDL; QUICKXPLAIN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Bacchus, Extending forward checking, in: Proceedings of CP’00, 2000, pp. 35-51 · Zbl 1044.68735
[2] R.J. Bayardo, R.C. Shrag, Using CSP look-back techniques to solve real-world SAT instances, in: Proceedings of AAAI’97, 1997, pp. 203-208
[3] Bessiere, C., Constraint propagation, (), (Chapter 3)
[4] C. Bessiere, J. Régin, MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems, in: Proceedings of CP’96, 1996, pp. 61-75
[5] Bessiere, C.; Régin, J.C.; Yap, R.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artificial intelligence, 165, 2, 165-185, (2005) · Zbl 1132.68691
[6] F. Boussemart, F. Hemery, C. Lecoutre, L. Sais, Boosting systematic search by weighting constraints, in: Proceedings of ECAI’04, 2004, pp. 146-150
[7] Brelaz, D., New methods to color the vertices of a graph, Communications of the ACM, 22, 251-256, (1979) · Zbl 0394.05022
[8] Cabon, B.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J.P., Radio link frequency assignment, Constraints, 4, 1, 79-89, (1999) · Zbl 1020.94500
[9] Chen, X.; van Beek, P., Conflict-directed backjumping revisited, Journal of artificial intelligence research, 14, 53-81, (2001) · Zbl 0970.68192
[10] R. Debruyne, C. Bessiere, Some practical filtering techniques for the constraint satisfaction problem, in: Proceedings of IJCAI’97, 1997, pp. 412-417
[11] Debruyne, R.; Bessiere, C., Domain filtering consistencies, Journal of artificial intelligence research, 14, 205-230, (2001) · Zbl 0970.68125
[12] Dechter, R., Constraint processing, (2003), Morgan Kaufmann
[13] Fikes, R.; Nilsson, N., STRIPS: A new approach to the application of theorem proving to problem solving, Artificial intelligence, 2, 189-208, (1971) · Zbl 0234.68036
[14] F. Focacci, M. Milano, Global cut framework for removing symmetries, in: Proceedings of CP’01, 2001, pp. 77-92 · Zbl 1067.68633
[15] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research (JAIR), 20, 61-124, (2003) · Zbl 1036.68093
[16] Gent, I.P.; MacIntyre, E.; Prosser, P.; Smith, B.M.; Walsh, T., Random constraint satisfaction: flaws and structure, Constraints, 6, 4, 345-372, (2001) · Zbl 0992.68193
[17] Ghallab, M.; Nau, D.; Traverso, P., Automated planning, theory and practice, (2004), Morgan Kaufmann · Zbl 1074.68613
[18] Ginsberg, M.L., Dynamic backtracking, Journal of artificial intelligence research, 1, 25-46, (1993) · Zbl 0900.68179
[19] Haralick, R.M.; Elliott, G.L., Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, 14, 263-313, (1980)
[20] T. Hulubei, B. O’Sullivan, Search heuristics and heavy-tailed behaviour, in: Proceedings of CP’05, 2005, pp. 328-342 · Zbl 1153.68464
[21] J. Hwang, D.G. Mitchell, 2-way vs d-way branching for CSP, in: Proceedings of CP’05, 2005, pp. 343-357 · Zbl 1153.68465
[22] U. Junker, QuickXplain: Preferred explanations and relaxations for over-constrained problems, in: Proceedings of AAAI’04, 2004, pp. 167-172
[23] N. Jussien, R. Debruyne, P. Boizumault, Maintaining arc-consistency within dynamic backtracking, in: Proceedings of CP’00, 2000, pp. 249-261 · Zbl 1044.68772
[24] G. Katsirelos, F. Bacchus, Generalized nogoods in CSPs, in: Proceedings of AAAI’05, 2005, pp. 390-396
[25] Lecoutre, C., Constraint networks: techniques and algorithms, (2009), ISTE/Wiley
[26] C. Lecoutre, F. Boussemart, F. Hemery, Backjump-based techniques versus conflict-directed heuristics, in: Proceedings of ICTAI’04, 2004, pp. 549-557
[27] C. Lecoutre, L. Sais, S. Tabary, V. Vidal, Last conflict-based reasoning, in: Proceedings of ECAI’06, 2006, pp. 133-137 · Zbl 1185.68645
[28] C. Lecoutre, S. Tabary, Abscon 109: A generic CSP solver, in: Proceedings of the 2006 CSP Solver Competition, 2007, pp. 55-63
[29] O. Lhomme, Quick shaving, in: Proceedings of AAAI’05, 2005, pp. 411-415
[30] D.G. Mitchell, Resolution and constraint satisfaction, in: Proceedings of CP’03, 2003, pp. 555-569 · Zbl 1273.68356
[31] S. Ouis, N. Jussien, P. Boizumault, k-relevant explanations for constraint programming, in: Proceedings of the Workshop on User-Interaction in Constraint Satisfaction (UICS’02) Held with CP’02, 2002, pp. 109-123
[32] Prosser, P., Hybrid algorithms for the constraint satisfaction problems, Computational intelligence, 9, 3, 268-299, (1993)
[33] P. Prosser, MAC-CBJ: Maintaining arc consistency with conflict-directed backjumping, Technical report, Department of Computer Science, University of Strathclyde, 1995
[34] D. Sabin, E.C. Freuder, Contradicting conventional wisdom in constraint satisfaction, in: Proceedings of CP’94, 1994, pp. 10-20
[35] T. Schiex, G. Verfaillie, Stubborness: A possible enhancement for backjumping and nogood recording, in: Proceedings of ECAI’94, 1994, pp. 165-172
[36] Smith, B.M.; Dyer, M.E., Locating the phase transition in binary constraint satisfaction problems, Artificial intelligence, 81, 155-181, (1996)
[37] Vidal, V.; Geffner, H., Branching and pruning: an optimal temporal POCL planner based on constraint programming, Artificial intelligence, 170, 3, 298-335, (2006) · Zbl 1131.68528
[38] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artificial intelligence, 171, 8-9, 514-534, (2007) · Zbl 1168.68554
[39] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, Journal of artificial intelligence research, 12, 93-103, (2000) · Zbl 0940.68099
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.