A framework for investigating production system formulations with polynomially bounded match

Milind Tambe, Paul S. Rosenbloom

TL;DR

This paper tackles the problem of combinatorial explosion in AI production systems, specifically in Soar, by proposing a framework to systematically explore alternative "production system formulations." They demonstrate that while the "unique-attribute" formulation is optimal under certain conditions, new, more efficient formulations emerge when considering "tokenless match" algorithms, suggesting a promising direction for real-time AI.

What Problem Does This Paper Address?

Modern AI systems, particularly those aiming for real-time performance and complex reasoning, often rely on "production systems." These systems use a set of rules (productions) to process data (working memory). A critical bottleneck in these systems is the "production match" – the process of finding which rules apply to the current data. In systems like Soar, this matching process can become computationally intractable (combinatorial) due to factors like "multi-attributes" (where a single attribute can have multiple values). This combinatorial explosion prevents real-time operation, leads to inefficiently learned rules ("expensive chunks"), and hinders parallelization. The authors aim to find production system formulations that guarantee a polynomially bounded match complexity, meaning the computation time grows predictably with the problem size, not exponentially.

Methods

The core of the paper is the introduction of a framework for systematically generating and evaluating alternative production system formulations. This framework is built upon identifying independent dimensions that define how working memory elements (data) and production conditions are structured.

Key dimensions identified include:

  • Forward-attribute: Restrictions on the number of attributes for a given identifier.
  • Values-per-attribute: Restrictions on the number of values for a given attribute (this is where "multi-attributes" come in).
  • Reverse-attribute: Restrictions on the number of attributes for a given value.
  • Identifiers-per-attribute: Restrictions on the number of identifiers for a given attribute.

The authors then introduce a novel concept: tokenless match. Unlike traditional "token match" (where a token represents a specific combination of variable bindings), tokenless match focuses on finding consistent bindings for each variable independently. This is mapped to the well-understood problem of constraint satisfaction. By combining these dimensions with the tokenless match, new formulations emerge.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and a framework for evaluation, using examples from Soar's existing tasks and a hypothetical "grid task" for illustration.

Key Insights and Ideas

  • The power of a systematic framework: Instead of ad-hoc exploration, the paper provides a structured way to think about and generate production system formulations by breaking them down into independent dimensions. This significantly reduces the search space for optimal formulations.
  • Trade-off between expressiveness and efficiency: The paper highlights a fundamental trade-off: restricting the expressiveness of the production system (e.g., by disallowing multi-attributes) can lead to significant gains in match efficiency.
  • Tokenless match as a game-changer: The introduction of tokenless match, inspired by constraint satisfaction, unlocks new possibilities. It allows for polynomially bounded match even with unrestricted working memory, provided productions are "tree-structured" (i.e., no equality tests across value fields).
  • Unique-attributes are not always best: While the "unique-attribute" formulation (which disallows multi-attributes) is shown to be optimal within the traditional token-based match, the advent of tokenless match creates scenarios where other formulations, like the "unrestricted-tree formulation," can outperform it.
  • Generality of the framework: The paper demonstrates the framework's generality by showing how even a seemingly different paradigm like marker passing systems can be mapped onto one of the generated formulations, suggesting broad applicability.

Key Results

  • The "unique-attribute" formulation is identified as the best possible formulation within the investigated dimensions, assuming a traditional token-based match. This formulation achieves a linear bound on match complexity.
  • The introduction of "tokenless match" allows for new formulations, such as the "unrestricted-tree formulation," which can satisfy absolute requirements (polynomial bound, closure under chunking, correctness) even with unrestricted working memory, provided productions are tree-structured.
  • The paper suggests that the "unrestricted-tree formulation" might outperform unique-attributes in terms of chunk generality and avoid the "expensive chunk" problem, though this requires further empirical validation.

Limitations and Future Work

  • Empirical validation: While promising, the paper acknowledges that the implementation and evaluation of these new formulations on actual tasks are ongoing and represent key future work.
  • Expressive adequacy of new formulations: The paper notes that while tokenless match can improve efficiency, it might require productions to be written in a "fairly different manner," and the full extent of this impact on expressive adequacy needs further investigation.
  • Exploring other consistency algorithms: The paper hints at further possibilities by mentioning that more constraining consistency algorithms than arc-consistency could be used with tokenless match, potentially leading to formulations that perform better on expressive adequacy but require higher polynomial bounds.
  • Generalizability beyond Soar: While the framework is presented as relevant to other rule-based systems, further work is needed to demonstrate this explicitly.

Summary updated

Abstract

Real time constraints on AI systems require guaranteeing bounds on these systems' performance. However, in the presence of sources of uncontrolled combinatorics, it is extremely difficult to guarantee such bounds on their performance. In production systems, the primary source of uncontrolled combinatorics is the production match. To eliminate these combinatorics, the unique-attribute formulation was introduced in (Tambe and Rosenbloom, 1989), which achieved a linear bound on the production match. This formulation leads to several questions: is this unique-attributes formulation the best conceivable production system formulation? In fact, are there other alternative production system formulations? If there are other formulations, how should these alternatives be compared with the unique-attribute formulation? This paper attempts to address these questions in the context of Soar. It identifies independent dimensions along which alternative production system formulations can be specified. These dimensions are based on the fixed class of match algorithms currently employed in production systems. These dimensions create a framework for systematically generating alternative formulations. Using this framework we show that the unique-attribute formulation is the best one within the dimensions investigated. However, if a new class of match algorithms is admitted, by relaxing certain constraints, other competitor formulations emerge. The paper indicates which competitor formulations are promising and why. Although some of the concepts, such as unique-attributes, are introduced in the context of Soar, they should also be relevant to other rule-based systems.
BibTeX
@inproceedings{tambe1990framework,
  author = {Milind Tambe and Paul S. Rosenbloom},
  title = {{A framework for investigating production system formulations with polynomially bounded match}},
  booktitle = {National},
  year = {1990},
}
Figure