A Reformulation-Based Approach to Explanation in Constraint Satisfaction

摘要

Many approaches to explanation generation have been reported in the literature [1—5]. The dominant approach to explanation is based on computing minimal conflicting sets of constraints. An explanation can be considered concise if it involves few constraints of low arity. However, in many practical domains constraints are specified extensionally as table constraints. From an explanation point of view, table constraints can prevent us from finding concise explanations since the constraint may be specified over all the variables in the problem. However, it is often possible to reformulate a large arity table constraint into a set of low arity constraints whose join is logically equivalent to the original table constraint. In this research we are concerned with finding reformulations of large arity table constraints into low arity constraints in order to help find more concise explanations in interactive applications such as product configuration or online electronic commerce.