Constraint relaxation techniques & knowledge base reuse

Effective reuse of KBs often entails the expensive task of identifying plausible KB-combinations. This research assists the MUSKRAT-Advisor [133] to decide whether existing KBs could be reused for solving new problems. This research assists this process, by developing an aid based on constraint satisfaction techniques which identifies incompatible KB-combinations in the scheduling domain. Incompatible KBs can be discarded, thus leaving fewer combinations for the MUSKRAT-Advisor to examine in detail. I have used a constraint solver as the Problem Solver (PS) and have represented the existing scheduling KBs as Constraint Satisfaction Problems (CSPs) which can be combined to create a composite CSP. If the composite CSP is found to be inconsistent, the KB-combination will not fulfil the PS requirements and can be discarded. Proving a CSP inconsistent can be a lengthy process, so I propose a constraint relaxation approach to more quickly identify inconsistent KB-combinations. My approach relaxes the CSP by removing constraints and if the relaxed version is unsolvable then the original CSP will not have a solution either. However, it is not certain that relaxing a CSP will produce an easier problem; previous research has shown that random binary CSP are hardest to solve around the solution transition phase [25, 96]. Moreover, part of my research has shown that when constraints are removed randomly from an inconsistent CSP (binary and non-binary), the new relaxed CSP can be up to 10 times harder to solve. To investigate these issues, I created a Prolog test suite designed to generate test-beds of CSPs and to help identify useful relaxation strategies and analyse their results. The identified relaxation strategies are based on different constraint graph properties and are in most cases easy to implement. Empirical tests show that removing constraints of low tightness as well as high arity are efficient strategies which are also simple to implement and can create relaxed CSPs that verify that the original CSP is inconsistent, using less than half the search effort of the original CSP.EThOS - Electronic Theses Online ServiceGBUnited Kingdo