Sat, 27 Jul 2024

A PRINCIPLED APPROACH FOR QUICKXPLAIN

In Fall 2003, a prominent CP researcher asked me for progress on QuickXplain. This motivated me to give this work a second thought, but from a scientific point of view and not from a product development standpoint. Interestingly, this happened at a time when ‘the optimization company’ stopped all further development of configuration technology as part of a major refocusing effort. Work on QuickXplain thus became my personal affair.

Two research questions came into my mind. The first research question concerns the problem formulation. We have a first problem, namely a constraint satisfaction problem. If this first problem has no solution, we obtain a second problem, namely that of finding explanations for this over-constrained problem. Which is a general formulation of this explanation problem? Which assumptions are needed? Can we distinguish background and foreground constraints? Can we take importance preferences between constraints into account? I took inspiration from Gerhard Brewka’s notion of preferred sub-theories of inconsistent logical theories. Instead of finding maximal consistent subsets, I was interested in minimal inconsistent subsets. Therefore, definitions had to be turned around in a suitable way.

The second research question concerned solving the explanation problem. It was necessary to do multiple solver calls to test the inconsistency of different subsets of constraints. A basic method removes one constraint after the other on a trial basis. If the resulting set of constraints is inconsistent, the removal becomes definitive. Otherwise, the removed constraint is put back. This sequential method needs a linear number of solver calls. Can we compute explanations with less than a linear number of solver calls? Framed in this way, the whole approach got more sense and I could figure out a principled approach. I decided to use an a-priori recursive decomposition as this was easy to explain and analyze. Indeed, the clear and explicit formulation of the explanation problem unlocked all the other steps and gave coherence to the new paper. It has thus been key for the success of QuickXplain.

This new approach now fitted into my personal research program of studying preferences for problem solving. As already indicated, this work was no longer important at that time for ‘the optimization company’ as they endured a Kafkaesque transformation from an optimization company to a company building and selling a rule management system. Due to this transformation, I was called on working on methods for finding conflicts between rules. This was a different conflict detection problem and it did not immediately ask for QuickXplain-like algorithms.

As my attention was taken 200% by this new RnD project, I could write the QuickXplain paper only in my spare private time on weekends and when traveling. However, I had quite a lot of discussions with a colleague who supported this pet project and it was him who convinced me to keep things simple and to skip those variants that are too complicated to explain. The main purpose of the new QuickXplain paper was to convince the AI community of this approach. Therefore, the algorithm needed to be as simple as possible. I followed the idea that less is more.

I wrote this second QuickXplain paper very quickly and it could certainly have benefited from more time and polishing. The paper has nevertheless been accepted at AAAI 2004 and I was quite happy that it passed this threshold. This showed that the principled approach worked and convinced the reviewers. Moreover, the AAAI presentation of the QuickXplain article went very well. At that time, the AAAI conference has been much smaller, but there have only been a few parallel sessions. Therefore, my talk has been very well attended. At the same conference, I gave a tutorial with Jon Doyle about preference handling and this was an extreme honor for me. This tutorial was my main focus at AAAI 2004 and I considered QuickXplain more like a little cute idea that I was going to present in addition to research on preferences. ►