TREAT: a better match algorithm for AI production systems

TLDR

The paper introduces the TREAT match algorithm for AI production systems and reports an empirical comparison with the RETE match. TREAT employs a conflict‑set support state‑saving method in production‑system interpreters and is evaluated against RETE. On five OPS5 programs, TREAT outperformed RETE by over fifty percent, supporting the view that RETE’s condition‑element state saving may be unnecessary.

Abstract

This paper presents the TREAT match algorithm for AI production systems. The TREAT algorithm introduces a new method of state saving in production system interpreters called conflict-set support. Also presented are the results of an empirical study comparing the performance of the TREAT match with the commonly assumed best algorithm for this problem, the RETE match. On five different OPS5 production system programs TREAT outperformed RETE, often by more than fifty percent. This supports an unsubstantiated conjecture made by McDermott, Newell and Moore, that the state saving mechanism employed in the RETE match, condition-element support, may not be worthwhile.