Reason maintenance in constraint satisfaction

• Main Author: Tay, Joc Cing.
• Other Authors: School of Computer Engineering
• Format: Theses and Dissertations
• Language: English
• Published: 2008
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: http://hdl.handle.net/10356/13598
• Institution: Nanyang Technological University

Research effort in constraint satisfaction has traditionally been devoted to curbing the exponential cost of search through the methods of backtracking and problem reduction. These methods serve the overall goal of avoiding redundant computations and reduce the search space needed to derive a solution. The advent of reason maintenance systems (or RMSs) in recent years have provided the necessary machinery to dynamically determine the causes of failure, revise assumptions and avoid redundancy in backtracking. In addition, RMS-based CSP solvers promote program design clarity by separating control and inference mechanisms. However, it is well known that classical breadth-first control of the RMS incurs an exponential amount of work when only a few solutions are required. Furthermore, research effort in reason maintenance technology has neither consolidated nor clearly defined a direction for improving its performance. The deployment of such an RMS-based solver for CSPs is also a topic that has only been theoretically evaluated against classical constraint satisfaction techniques. Their derived similarities on a propositional level have promoted the inter-migration of solutions and ideas from both fields, but an evaluation of their empirical performance and comparison of respective problem solving models remains an area that has shown little growth.