Research Of Generating Interactive Explanation Algorithms Based On Constraint Programming

The research of generating explanation algorithms under the architecture of constraint program in the interactive configuration domain has been a hot issue of AI scholars. Any progress in this research branch isn't only the breakthrough of computer science theory, but also the key of industrial application in configuration. CP, as a kind of general modeling way, has been applied in quite many domains in AI because of its strong consistent propagation techniques. The interactive process with users of configuration requires that it provide the function of generating explanations. The purpose of this research is to blend the powerful CP propagation capability into the interactive generating explanation algorithm, and then achieve the configuration effectively.In the past few years, many scholars have been made plenty of outstanding contributions in the configuration. Such as Ulrich Junker, who is from France, is usually credited as the person most responsible for generating explanations algorithm, he presented a method for computing minimal and preferred conflicts which is called QUICKXPLAIN. It provides a casual explanation of the current configuration state. The algorithm recursively divides the explanation problem into sub problems of the same size and solves the explanation problem by propagation techniques. And lots of scholars, who are from the famous institute called "4C"(Cork Constraint Computation Centre) in Cork, Ireland's leading research university, especially Freuder and Barry O'sullivan, they presented a method for computing minimal corrective explanation which is called CORRECTIVEEXP. It provides a maximal set of the current user requirements and lead the users getting theirs entire configuration. It also is the combination of consistency propagation techniques and recursively dividing and conquer technique.After consulting many correlative materials information and analyzing the correlative techniques relates modeling, preprocessing, solving and generating explanations, the contributions of this paper are listed as following:1. We improve the current popular kernel algorithm for computing the interactive corrective explanation. Firstly we indicate the lack of CORRECTIVEEXP-it propagates many times unnecessarily in some case. Secondly we present an improved algorithm CorectiveExp-1 for solving the problem. The algorithm adds another input parameter called the set of constraints M and updates it while dividing the set of constraints A. In this way CORRECTIVEEXP-1 can effectively reduce the amount of consistency propagation comparing with CORRECTIVEEXP. This algorithm has been achieved under the platform of Eclipse in java language. The experimental results show that CORRECTIVEEXP-1 performs well on both real-world configuration Benchmarks and randomly generated problems.2. on the basis of research on the relation between the explanations and the user's requirements, we find the interactive explanation is different with the order of the user's preferences. Hence we provide the idea generating the multiple explanations in parallel way. This function could avoid the effect of the default order of the user preference in the configuration system, transfer the decision-making power to the user, and display the user-centric principle. This algorithm has been achieved under the platform of Eclipse in java language, and has been tested through the both random problems and the real-world configuration Benchmarks. The experimental results show that the time cost in computing explanations increases while the number of the explanations increases. However, the growth rate of time cost is very little with respect to the growth rate of the number of explanations. So the results present the parallel capability.