ABSTRACT:   A demand-driven AI production system utilizing a RETE network for comparison matching in a condition/data match, rule-selection, and rule-firing execution cycle in which the RETE network is modified to maintain a list of instantiations satisfying the match conditions expressed in each node of the RETE network, passing of tokens to descendant nodes upon a comparison match, maintaining patterns to all ancestor nodes through which the tokens have passed, and traversing the patterns as a path for avoiding those RETE pattern matchings redundant between a previous match and a current match in progress.

U.S. REFERENCES:

Patent No. Patentee Issue Date 4704695 Kimura et al. Nov. 1 , 1987 4670848 Schramm Jun. 1 , 1987 4599692 Tan et al. Jul. 1 , 1986 4761746 Tano et al. Aug. 1 , 1988

Show the 22 patents that reference this one

4 CLAIMS:

• 1. A computer-implemented method for minimizing the number of data objects and pattern matchings occurring at the nodes of a flowgraph, each data object being manifest by coded indicia, said flowgraph being of the type in which the elements of a pattern are compiled into an acyclic-directed graph of entry and join nodes (FIG. 1), each pattern including coded indicia selected from a set consisting of single and compound elements, the entry nodes representing coded indicia of the single elements of the pattern, and join nodes representing coded indicia of compound elements, said entry and join nodes being connected in pattern-directed association (FIG. 1), 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 coded indicia of the data objects and the coded indicia of the node pattern elements;
• (c) maintaining a list of instantiations of objects satisfying the match conditions of pattern elements 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
• (e) traversing said pointers as a path for avoiding those flowgraph node pattern/object matchings redundant between a previously matched object and an object currently being processed.
• 2. A method for optimizing a cyclic, rule-based, data object sensitive production system, each data object being manifest by coded indicia, 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, said pattern indication part specifying logical conditions between predetermined coded indicia and a data object, said logical conditions being selected from a set consisting of single and compound terms, said action specifying part selectively including changing the state of the production system (i.e., altering stored data objects, selecting another rule) or invoking facilities external to the system (i.e., calling a print facility), 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 the action prescribed by the selected rule; wherein identification step (a) further comprises:
• (a1) compiling a data flowgraph of the logical conditions expressed in the pattern portion of the rule being matched, said flowgraph being formed from entry nodes and join nodes, the entry nodes representing those logical conditions constituting single terms and join nodes representing those logical conditions constituting compound terms arranged in a pattern-determined associative manner;
• (a2) applying those data objects created or modified in a preceding cycle to said flowgraph, and at each node (entry nodes and join nodes):
• maintaining a list of instantiations of objects satisfying the match conditions of the pattern portion of the rule 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 previously matched object and an object currently being processed.
• 3. The method according to claim 2, wherein the data flowgraph is a RETE network and wherein the pattern-directed associative manner includes the steps of conforming nodes and links of the associative graph according to the logical conditions expressed in the pattern part of the rule, and further wherein the pattern-directed associative manner for arranging the join nodes is left associative.
• 4. The method according to claim 2, wherein the indication of object change includes creation, modification, or deletion of an object occasioned during the preceding cycle as defined by the steps (a)-(c) and applied to the flowgraph during the current cycle, and further wherein the deletion of an object includes deletion of instantiations maintained at the nodes visited by any traverse of the pointers.

RELATED U.S. APPLICATIONS: none
FOREIGN REFERENCES: none
OTHER REFERENCES: none
PRIMARY/ASSISTANT EXAMINERS: Smith; Jerry; Gordon; Paul
ADDED TO DATABASE: Aug. 22, 1996