×

zbMATH — the first resource for mathematics

Consistency restoration and explanations in dynamic CSPs—Application to configuration. (English) Zbl 0983.68182
Summary: Most of the algorithms developed within the Constraint Satisfaction Problem (CSP) framework cannot be used as such to solve interactive decision support problems, like product configuration. Indeed, in such problems, the user is in charge of assigning values to variables. Global consistency maintaining is only one among several functionalities that should be offered by a CSP-based platform in order to help the user in her task; other important functionalities include providing explanations for some user’s choices and ways to restore consistency. This paper presents an extension of the CSP framework in this direction. The key idea consists in considering and handling the user’s choices as assumptions. From a theoretical point of view, the complexity issues of various computational tasks involved in interactive decision support problems are investigated. The results cohere with what is known when Boolean constraints are considered and show all the tasks intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, we present a new method for compiling configuration problems, that can be generalized to valued CSPs. Specifically, an automaton representing the set of solutions of the CSP is first computed off-line, then this data structure is exploited so as to ensure both consistency maintenance and computation of maximal consistent subsets of user’s choices in an efficient way.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Brace, K.S.; Rudell, R.L.; Bryant, R.E., Efficient implementation of a BDD package, (), 40-45
[2] Bryant, R.E., Graph based algorithms for Boolean function manipulation, IEEE trans. comput., 35, 8, 677-692, (1986) · Zbl 0593.94022
[3] Bennaceur, H., The satisfiability problem regarded as a constraint satisfaction problem, (), 155-159
[4] Bessière, C., Arc-consistency for dynamic constraint satisfaction problems, (), 221-227
[5] Bessière, C., Arc-consistency for non-binary dynamic csps, (), 23-27
[6] Boufkhad, Y.; Grégoire, E.; Marquis, P.; Mazure, B.; Saı̈s, L., Tractable cover compilations, (), 122-127
[7] Bouquet, F.; Jégou, P., Solving over-constrained CSP using weighted OBDDs, (), 293-308
[8] Cadoli, M.; Donini, F.M., A survey on knowledge compilation, AI comm., 10, 137-150, (1997)
[9] Castell, T., Computation of prime implicates and prime implicants by a variant of the Davis and Putnam procedure, (), 428-429
[10] Cayrol, C.; Lagasquie-Schiex, M.C.; Schiex, T., Nonmonotonic reasoning: from complexity to algorithms, Ann. math. artificial intelligence, 22, 3-4, 207-236, (1998) · Zbl 0905.68142
[11] Charniak, E.; Shimony, S.E., Probabilistic semantics for cost-based abduction, (), 106-111 · Zbl 0742.68076
[12] Coudert, O.; Madre, J.-C., A logically complete reasoning maintenance system based on a logical constraint solver, (), 294-299 · Zbl 0747.68072
[13] Darwiche, A., Compiling devices into decomposable negation normal form, (), 284-289
[14] Dechter, R.; Dechter, A., Belief maintenance in dynamic constraint networks, (), 37-42
[15] Dechter, R.; Dechter, A., Structure-driven algorithms for truth maintenance, Artificial intelligence, 82, 1-20, (1996)
[16] Dechter, R.; Pearl, J., Tree clustering schemes for constraint-processing, Artificial intelligence, 38, 3, 353-366, (1989) · Zbl 0665.68084
[17] de Kleer, J., An assumption-based TMS, Artificial intelligence, 28, 127-167, (1986)
[18] del Val, A., Tractable databases: how to make propositional unit resolution complete through compilation, (), 551-561
[19] Debruyne, R., Arc-consistency in dynamic CSPs is no more prohibitive, (), 299-306
[20] Eiter, T.; Gottlob, G., The complexity of logic-based abduction, J. ACM, 42, 3-42, (1995) · Zbl 0886.68121
[21] Falfernig, A.; Friedrich, G.; Jannach, D.; Stumptner, M., Consistency-based diagnosis of configuration knowledge bases, (), 146-150
[22] Gelle, E.; Weigel, R., Interactive configuration using constraint satisfaction techniques, (), 37-44
[23] Hobbs, J.R.; Stickel, M.E.; Appelt, D.E.; Martin, P., Interpretation as abduction, Artificial intelligence, 63, 69-142, (1993)
[24] Jussien, N.; Lhomme, O., Dynamic domain splitting for numeric CSP, (), 224-228
[25] Lobjois, L.; Verfaillie, G., Problèmes incohérents: expliquer l’incohérence, restaurer la cohérence, (), 111-120
[26] Marquis, P., Knowledge compilation using theory prime implicates, (), 837-843
[27] Mittal, S.; Frayman, F., Dynamic constraint satisfaction problems, (), 25-32
[28] Moller, G., On the technology of array based logic, ph.D. dissertation, (1995), Technical University of Denmark
[29] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[30] Poole, D., Probabilistic Horn abduction and Bayesian networks, Artificial intelligence, 64, 81-129, (1993) · Zbl 0792.68176
[31] Reiter, R.; de Kleer, J., Foundations of assumption-based truth maintenance systems: preliminary report, (), 183-188
[32] Sabin, D.; Freuder, E.C., Configuration as composite constraint satisfaction, (), 28-36
[33] Sabin, D.; Sabin, M.; Russell, R.D.; Freuder, E.C., A constraint-based approach to diagnosing software problems in computer networks, (), 463-480
[34] Sabin, D.; Weigel, R., Product configuration frameworks—A survey, IEEE intelligent systems appl., 13, 4, 42-49, (1998)
[35] Sabin, M.; Freuder, E.C., Detecting and resolving inconsistency in conditional constraint satisfaction problems, (), 90-94
[36] Schiex, T.; Fargier, H.; Verfaillie, G., Valuated constraint satisfaction problems: hard and easy problems, (), 631-637
[37] Schrag, R., Compilation for critically constrained knowledge bases, (), 510-515
[38] Selman, B.; Kautz, H.A., Knowledge compilation and theory approximation, J. ACM, 43, 193-224, (1996) · Zbl 0882.68137
[39] Soininen, T.; Gelle, E., Dynamic constraint satisfaction in configuration, (), 95-100
[40] Stumptner, M., An overview of knowledge-based configuration, AI comm., 10, 111-125, (1997)
[41] Vempaty, N.R., Solving constraint satisfaction problems using finite state automata, (), 453-458
[42] Weigel, R., Compiling constraint satisfaction problems, Artificial intelligence, 115, 257-287, (1999) · Zbl 0996.68185
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.