Method for optimized rete pattern matching in pattern-directed, rule-based artificial intelligence production systems

Claim 1

A computer-implemented method for minimizing the number of data objects and pattern matchings occurring at the nodes of a flowgraph of the type in which the elements of a pattern are compiled into an acyclic-directed graph of entry and join nodes, the entry nodes representing the single elements of the pattern, and join nodes representing compound elements, said entry and join nodes being connec­ted in pattern-directed association, comprising the steps of: (a) applying the data objects to the entry nodes of said flowgraph, at each node (entry nodes and join nodes): (b) performing a comparison match between the attributes of the data objects and the node pattern elements; (c) maintaining a list of instantiations satis­fying the match conditions expressed at that node and passing tokens to descendant nodes; (d) maintaining pointers to all ancestor nodes through which the token for each object passed; and (f) traversing said pointers as a path for avoiding those flowgraph node pattern/object match­ings redundant between a previously matched object and an object currently being processed.

Claim 3

A method for optimizing a cyclic, rule-based, data object sensitive production system, said system including means for storing data objects and rules, and means cooperating with the storage means for executing a control cycle, each rule having pattern indication and action specifying parts thereof, comprising the cyclic steps of: (a) identifying an executable subset of rules by matching the pattern parts of the rules to those data objects in the storage means modified or created during a preceding cycle; (b) selecting a rule from the identified rules; and (c) executing th. action prescribed by the selected rule; wherein identification step (a) further comprises: (a1) compiling a data flowgraph of the condition elements of the pattern portion of the rule being matched, said flowgraph being formed from entry nodes and join nodes, the entry nodes representing counterpart individual condition elements and join nodes representing compound condition elements arranged in a pattern-determined associative manner; (a2) applying those data objects created or modified in a preceding cycle to said flow­graph, and at each node (entry nodes and join nodes): maintaining a list of instantiations satisfying the match conditions expressed at that node, passing tokens to descendant nodes, maintaining pointers to all ancestor nodes through which the token for each object passed, and responsive to indication of object change, traversing said pointers as a path for avoiding those flowgraph node pattern/­object matchings redundant between a previ­ously matched object and an object currently being processed.

Claim 4

A method for optimizing a cyclic, rule-based, data object sensitive production system, said system including means for storing data objects and rules, and means cooperating with the storage means for executing a control cycle, each rule having pattern indication and action specifying parts thereof, comprising the cyclic steps of: (a) identifying an executable subset of rules by matching the pattern parts of the rules to those data objects in the storage means modified or created during a preceding cycle; (b) selecting a rule from the identified rules; and (c) executing th. action prescribed by the selected rule; wherein identification step (a) further comprises: (a1) compiling a data flowgraph of the condition elements of the pattern portion of the rule being matched, said flowgraph being formed from entry nodes and join nodes, the entry nodes representing counterpart individual condition elements and join nodes representing compound condition elements arranged in a pattern-determined associative manner; (a2) applying those data objects created or modified in a preceding cycle to said flow­graph, and at each node (entry nodes and join nodes): maintaining a list of instantiations satisfying the match conditions expressed at that node, passing tokens to descendant nodes, maintaining pointers to all ancestor nodes through which the token for each object passed, and responsive to indication of object change, traversing said pointers as a path for avoiding those flowgraph node pattern/­object matchings redundant between a previ­ously matched object and an object currently being processed.