Explanation and Implication for Configuration Problems
Eugene C. Freuder, Chavalit Likitvivatanavong, Richard J. Wallace · 2001
In this work we explore the problem of generating explanations for configuration problems using the constraint satisfaction (CSP) framework. In addition, we are concerned with deriving implications from user choices in order to guide selection of later choices. We show that the consistency methods used in connection with constraint processing can be used to generate inferences that support both functions. In this work we use the Ò-queens problem as a testbed. The system we have developed is interactive and allows the user to make selections and perform arc consistency on the current problem, as well as retracting selections, a typical arrangement with current configurator systems. At the same time it generates explanations for value deletions and current choices as well as implications in terms of the amount of future domain reduction that will follow certain choices and whether these choices will lead to solutions or non-solutions. Explanations take the form of trees which show the basis in terms of previous choices for current choices and deletions. Together, these methods suggest ways in which the process of solving combinatorial problems can be made more perspicuous and more interactive.