Efficient production system match and constraint satisfaction problem solving
Bonghan Cho · University of Southern California Digital Library · 2015
Combinatorics has been a problem in building efficient Artificial Intelligence (AI) systems. While production systems and Constraint Satisfaction Problems (CSP) provide a useful structure for such AI systems, combinatoric production match process or CSPs are problematic in situations requiring real-time performance or scaling up. The goal of this thesis is to alleviate the combinatorics from both areas without sacrificing their functionality. We examine the causes of the combinatorics by constructing a generalized search model based on an analysis of the commonality between production match and CSP solving, revealing that a significant amount of the search space explored by conventional production match algorithms or CSP techniques is redundant. We develop domain-independent techniques which eliminate the major causes of the redundancy. ERMA and EDCON, the newly developed algorithms for production match and CSP, respectively, demonstrate orders of magnitude speedup over the existing state-of-the-art Rete match algorithm and highly optimized CSP solving algorithms, respectively. In addition to regular CSPs, EDCON efficiently solve CSPs that allow dynamic changes or need to find all solutions.