Logic programming with stable models for constraint satisfaction

Logic Programming with the stable model semantics, called stable logic programming (SLP), has been suggested as a new paradigm for solving a number of computationally hard problems in artificial intelligence, including constraint satisfaction problems (CSPs), planning problems and scheduling problems. The expressiveness of SLP as a general knowledge representation language is in sharp contrast with the conventional problem solvers that work only for special domains. The promise of this new paradigm has recently been demonstrated by efficient implementations of SLP systems, among which the smodels system developed by Niemela et al. is the most competitive. Niemela demonstrated that smodels successfully competes with special-purpose solvers for a class of planning problems. But to date, very few studies have been carried out for smodels in context of CSPs which form the basis of some of the most successful practical industrial-scale systems in artificial intelligence. Further, the promise of SLP can be strengthened by the development of strong and more powerful pruning techniques for stable model computation. One is unlikely to succeed in this direction without an understanding of the techniques employed by the efficient existing implementations, and how they relate to the pruning techniques we understand for other domains. Though the efficiency of smodels is apparently attributed to some of well-known techniques in solving CSPs (and SAT problems) so far no comprehensive studies of such implementations has been performed.; In this thesis, we study the important techniques incorporated in the implementation of smodels. We show that the three main techniques used in smodels, namely, constraint propagation, lookahead, and backjumping, are mappings from well-known efficient techniques in CSPs. It turns out that smodels with lookahead can compete successfully with the best CSP algorithms.; An interesting yet challenging question in constraint satisfaction is what if a CSP is inconsistent, i.e., it does not have a solution in which all the given constraints are satisfied. These problems are called over-constrained problems. Our study extends to these problems. Research in the direction of representation and solving of over-constrained problems necessitated a clear understanding of their semantics and complexity. However the inadequate treatment of the semantic notion of solution in over-constrained problems in the literature prompted us to first explore their semantics. In the latter part of the thesis we studied the semantical problems with the notion of solution in over-constrained problems. We find that the existing notions of solutions in over-constrained problems suffer from the following semantic problems: (1) ad-hoc semantics; (2) higher computational complexity; (3) semantics not preserved in translation from non-binary to binary representations; and (4) techniques used in solving finite CSPs cannot be used directly.