ABSTRACT:   A technique for collecting changes to working memory objects made by rule execution in an artificial intelligence production system avoids frequent use of a matching algorithm by delaying the match processing of the collected changes to a memory object until completion of an executing rule. A change to an object wrought by execution of a rule is signified in a control block for that object. Once a first change has occurred, subsequent changes caused before execution of the rule is complete will be made to the object and indicated by the change block. When execution of the rule is complete, the changes coalesced in the object itself are registered in the system by introduction of the changed object into the matching algorithm. This avoids match processing the object each time it is changed during execution of the rule.

U.S. REFERENCES: none

8 CLAIMS:

• A method for coalescing changes to objects in a working memory, the method being invoked prior to processing said changes through a matching structure used in conflict set resolution, said resolution occurring during the recognize-act cycle of a rule-based, artificial intelligence production system,
• said system including a rule set and an inference engine cooperating with said rule set and working memory for executing a succession of recognize-act cycles, each rule having pattern indication and action specifying parts thereof, the action specifying part of a rule including procedures for effecting changes to said objects,
• said method comprising the steps of:
• responsive to a first change to an object resulting from execution of a first rule, creating a control block (CB) internal to the inference engine and recording said first change in the created CB;
• enqueueing said CB in a queue;
• in the event of a second change to said object subsequent to said first change and prior to the selection of the next rule following said first rule, maintaining said CB unaltered in said queue, without passing either said first or said second changes through said matching mechanism; and
• upon completing said execution of said first rule, passing the change recorded in said CB through said matching mechanism.
• 2. The method of claim 1, wherein said first change is a creation of said object, said enqueueing step including enqueueing said CB in a make queue.
• 3. The method of claim 1, wherein said first change is an update of said object, said enqueueing step including enqueueing said CB in an update queue.
• 4. The method of claim 1 wherein said enqueueing step includes enqueueing said CB in either a make or an update queue.
• 5. The method of claim 4, further including the steps of:
• responsive to said passing step, enqueueing said CB in a changed queue; and, then,
• upon selection of a second rule following said first rule, recording a third change to said object occurring before selection of the next rule following said second rule by moving said CB from said changed queue to said update queue.
• 6. The method of claim 5 further including the step of:
• in the event of a fourth change to said object subsequent to said third change and prior to the selection of the next rule following said second rule, maintaining said CB unaltered in said update queue, without passing either said first or said second changes through said matching mechanism; and
• upon completing said execution of said second rule, passing the change recorded in said CB through said matching mechanism.
• 7. A method for coalescing changes to objects in a working memory, the method being invoked prior to processing said changes through a matching structure used in conflict set resolution, said resolution occuring during the recognize-act cycle of a rule-based, artificial intelligence, production system,
• said system including a rule set and an inference engine cooperating with said rule set and working memory for executing a succession of recognize-act cycles, each rule having a pattern indication and an action specifying part, the action specifying part of the rule including procedures for making changes to said objects,
• said method including the steps of:
• creating a first queue for a production system calling routine, and selecting and executing a first rule during said calling routine;
• in an action-specifiying part of said first rule, calling and executing a rule-driven, production system subroutine including a subroutine rule set, a subroutine working memory with working memory objects which said subroutine cares about, and a subroutine matching structure used in subroutine conflict set resolution;
• creating a second queue for said subroutine;
• responsive to a first change to an object in said subroutine working memory resulting from execution of a rule in said subroutine working set, creating a first control block (CB) for said object and recording said first change in said CB;
• enqueueing said first CB in said second queue;
• in the event of a second change to said object occurring during the execution of said rule of said subroutine working set, maintaining said first CB unaltered in said second queue, without passing either said first or said second change through said subroutine matching structure;
• upon completing said execution of said rule in said subroutine rule set, passing said first and second changes through said subroutine matching mechanism in response to said CB; and
• after return to said calling routine:
• if said calling routine cares about said object, moving said first CB to said first queue if said first queue contains no second CB for said object, and passing said first and second changes through said matching structure;
• otherwise, dequeueing and destroying said first CB.
• 8. The method of claim 7, further including the step of creating a third queue for said calling routine, and if said first queue includes a second CB for said object, moving said second CB from said first to said third queue and passing said first and second changes through said matching structure in response to the inclusion of said second CB in said third queue.

RELATED U.S. APPLICATIONS: none
FOREIGN REFERENCES: none

OTHER REFERENCES:

• Programming Expert Systems in OPS5, An Introduction to Rule-Based Programming, Lee Brownston, et al, 1985.
• A New and Efficient Match Algorithm for AI Productions Systems, by Daniel Paul Miranker, Jan., 1987.
• OPS 5 User's Manual, Jul. 1981, Charles L. Forgy, Department of Computer Science, Carnegie-Mellon University.
• Artificial Intelligence RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, Charles L. Forgy, 1982.
• Chapter from Distributed Computing, Academic Press, 1984, pp. 10-19, Chambers et al.
• Aho et al., "Compilers: Principles, Techniques, and Tools", Addison-Wesley Publishing Co., copyright 1986, pp. 608-632.
• Chapter from Introduction to Expert Systems, Additons-Wesley, 1986, pp. 29-51, 126-141, Peter Jackson.
• Advances in RETE Pattern Matching, Marshall I. Schor et al, pp. 226-232, Proceedings of AAAI, 1986.