My quest for explanations for over-constrained problems began a long time ago, namely during the time of the second AI summer back in the 1980s. Rule-based systems have been the dominant paradigm for AI in this period, but have somehow been boring for us young students. In the AI courses, I learned about other AI techniques such as constraint propagation, intelligent backtracking, and truth maintenance systems, which I found more fascinating. Constraints permitted the formulation of problems independently of the way they are solved. Truth maintenance systems register the inferences made by a reasoning system in form of so called justifications and are thus able to compute explanations for conclusions as well as to revise conclusions in presence of new information.
A natural question was whether constraint propagation could be coupled with truth maintenance systems such that the latter could, for example, find the constraints that caused a failure. In Summer 1987, I implemented an assumption-based truth maintenance system as part of a summer stay at a computer science research center in St. Augustin, Germany. I did a quick attempt to couple it with Hans-Werner Güsgen’s constraint solver, which used domain filtering to achieve arc consistency for table constraints. Registering faithful justifications in the ATMS for all the filtering operations took an unreasonable amount of memory. I quickly abandoned this attempt and kept in mind that this was not the way to go.
I then prepared a PhD thesis on non-monotonic reasoning and went back to constraint satisfaction in Winter 1994. In the beginning of the 1990s, funding for AI research has dropped, leading to the second AI winter. Rule-based systems were out of fashion, but specialized techniques such as constraint programming (CP) and Bayesian networks have been on the rise. Constraint programming gained traction thanks to global constraints that encapsulated graph algorithms for stronger filtering. But these powerful constraint solvers lacked features such as explanations. When learning about those solvers in a training course as a new hire of a future ‘optimization company’, I was impressed by the potential of these new algorithms, but also understood that these solvers won’t be able to produce explanations of failure without an enormous penalty in computation time and memory.
When I was waiting at a bus stop, I wondered whether explanations could be computed by using the constraint solver as a blackbox and by identifying a set of failing constraints by problem decomposition. In each step, we would split the set of constraints into two halves. We first pass the first half to the solver. If a failure is obtained, we have reduced the problem in size. Then we do the same with the second half. If we were lucky and one of the halves turns out to be inconsistent and has no solution, we would be able to reduce the explanation problem in that way. However, it may also be the case that some of the conflicting constraints are in the first half and the other ones in the second half. In that case, the problem decomposition would not work. Then the bus came and I stopped my interrogation while concluding that problem decomposition does not work for explanation detection.
In 1999, interactive product configuration had become a hot topic in industry and ‘the optimization company’ decided to develop a constraint-based configuration engine. However, an interactive configurator needs an explanation module. No more excuses have been possible: it is “explain-or-vanish”!
Based on my experience, I offered my humble help in Summer 1999. The offer got accepted. I had about three months to solve this open problem (this was an informal rule in the CP RnD team: you have three months to succeed or you vanish if you don’t). I explored all possible ideas, including linear resolution for consequence-finding, justifications for value suppressions, and so on, but all lead to memory and time overhead and required significant engineering effort to be implemented.
During this period, I had to debug a constraint satisfaction problem consisting of 300 complex crew rostering constraints on a Friday afternoon in Fall 1999. Some constraints caused an unexpected failure, but which ones? I started to temporarily remove one of the constraints after the other, but I would not be able to do this for all the 300 constraints on that afternoon.
Suddenly, an idea came to my mind. I could divide the problem into subproblems of half the size by focusing the search of the culprits to one of the halves, while keeping the constraints of the other half in the solver. We first check whether we can remove all the constraints of the current half. If this leads to a failure, we know that this half does not contain any culprit. Otherwise, we find the culprits by further dividing this half in size. When we have found these culprits, we are looking for the culprits in the other half while keeping constraints from the current half in the solver. Not all constraints, but only the culprits that we have just found. That way the problem decomposition will work. We reduce the size of the explanation problem, but not the size of the overall constraint set. Nearly five years after my interrogation at the bus stop, I found out how to decompose explanation problems.
It was a sudden discovery, but perhaps I would not have made it if I had not thought of the problem before. And yes, I had kept these thought at the bus stop in my mind for five years even if I did not work at all on explanation detection during this long period. All the failed attempts of this long quest surely enabled me to find the solution when it was needed. ►
This web site expresses personal reflections about scientific topics with the purpose of contributing to discussions in scientific communities. As such, this content is not related to any organization, association, or employment.
