Efficient Production Match Algorithm and Its Implication for Dynamic Constraint Satisfaction Problems

Bonghan Cho, Paul Rosenbloom, Milind Tambe

Production systems have been a successful paradigm in Artificial Intelligence (AI) programming and have been extensively used in building AI systems including problem-solving systems, cognitive models, expert systems and real-time systems. Despite this extensive use, there remains a key performance bottleneck that limits the applicability of production systems - the combinatoric match process. Algorithms that handle the match combinatorics efficiently are increasingly needed as (1) knowledge bases grow in size and (2) real time performance becomes more important. There has in fact been much progress in production match since Rete (Forgy 1982) was developed, resulting in orders of magnitude of improvements in production system performance. However, despite the current match technology, programmers of production systems experience that they spend substantial amounts of time in rewriting productions just in order to improve production system efficiency. The goal of our research is to develop an efficient match algorithm for large data sets in working memory in real time environments. The match algorithm we have developed, called ERMA, attempts to eliminate match combinatorics. Due to the elimination of such combinatorics (though not fully eliminated yet), ERMA is able to scale well with large data sets in working memory.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.