Method for rolling back an expert system

• US 5,170,464 A
• Filed: 11/15/1991
• Issued: 12/08/1992
• Est. Priority Date: 01/26/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hayes, Raymond R., Hsieh, Lo
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/794,617
• Time in Patent Office: 389 Days
• Field of Search: 395/76
• US Class Current: 706/60
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A system and method suitable for use with a rule-based expert system maintains a history of execution states through which the expert system progresses during execution. A user can select a previous execution state for roll back, and later states maintained in the history are undone in reverse order until the selected state is reached. If desired, a user can define a breakpoint to which the system is to be rolled back. The corresponding executable state is determined from a retained history of all potential breakpoints, and the system is then rolled back to such corresponding executable state.

Claims

1. A method for rolling back the state of a rule-based expert system on an inference engine, comprising the steps of:

providing an inference stack of state records;

providing an execution stack of execution state records, each of which identifies a state for the inference engine;

responsive to user selection of at least a first breakpoint condition definition, establishing at least a first breakpoint for the inference engine;

operating the inference engine to generate a chain through a rule/variable network by removing inference state records and execution state records from the inference stack and the execution stack, respectively;

advancing an execution state number with each execution state record removed from the execution stack;

for each inference state record removed from the inference stack, copying the inference state record with a current execution state number to an inference history queue;

for each execution state record removed from the execution stack, copying the execution state record with a current execution state number to an execution history queue;

upon the inference engine encountering a breakpoint during operation, adding an entry to a breakpoint history queue;

accepting a breakpoint condition definition for rollback of the execution state from a user;

comparing the accepted breakpoint condition definition and the entries in the breakpoint history queue to determine a desired execution state and its state number;

resetting the inference and execution stacks by moving state records and copied execution state records from the inference history queue and execution history queue to the inference stack and execution stack, respectively;

for each copied execution state record replaced from the execution history queue to the execution stack, reducing the execution state number and retracing the chain through the rule/variable network; and

discontinuing resetting of the inference and execution stacks when the execution state number equals the state number for the desired execution state.

2. The method of claim 1, wherein said step of comparing comprises the steps of:

scanning the breakpoint history queue from the most recent entry;

for each entry in the breakpoint history queue, determining whether such entry matches the breakpoint condition definition accepted from the user; and

when an entry matches the accepted breakpoint condition definition, selecting the execution state corresponding to such matching breakpoint entry as the desired execution state.

3. The method of claim 2, further comprising the step of:

when the desired roll back execution state is determined, deleting the matching entry, and all later entries, from the breakpoint history queue.

4. A method for rolling back the state of a rule-based expert system as set forth in claim 1, and further comprising:

generating version queues for variables in the expert system, wherein a version record is added for a variable in connection with occurrence of an execution state wherein the variable was used or assigned a value and wherein each version record in each version queue provides a variable value and the execution state number for a point when the variable was used in the inference engine; and

in the step of resetting the inference and execution stacks, deleting all version records from the version queues having execution state numbers after the number for the desired execution state.

5. A method of rolling back the state of a rule-based expert system as set forth in claim 4, and further comprising:

generating an inference history queue, wherein a record in the inference history queue includes an execution state number.

6. The method of claim 1, and further comprising:

before operating the inference engine, providing a resettable inference queue and an inference history queue;

with operation of the inference engine updating the resettable inference queue; and

with operation of the inference engine adding a record to the set history queue with each update of the resettable inference queue;

the step of resetting further including retracting changes made to the resettable inference queue using records from the inference history queue.

7. A system for rolling back the execution state of a rule-based expert system to a previous state, comprising:

an inference stack comprising a plurality of inference state records;

an execution stack comprising a plurality of execution state records;

a breakpoint history stack comprising a plurality of breakpoint occurrence records;

inference engine means operating on the inference state records and execution state records for moving through a sequence of execution states;

means for generating history queues associated with said inference and execution stacks, respectively, said history queues each containing entries corresponding to entries popped from said stack during execution;

means responsive to user specification of a breakpoint condition definition for determining a desired roll back execution state from the breakpoint occurrence records; and

means operating on said inference and history stacks and said associated history queues for reversing the inference engine means until the desired roll back execution state is reached, wherein stack entries which were pushed onto said history queues during execution are popped therefrom, delivered to the inference engine and pushed onto said inference and execution queues to obtain the desired roll back execution state in the rule/variable network.

8. The system of claim 7, wherein said

execution stack records corresponde to execution states of said inference engine;

and

said inferencing stack records corresponde to inferencing states of said inference engine.

9. The system of claim 7, further comprising:

a version queue for variables in the expert system, wherein said reversing means includes means for deleting versions of variables occurring after the desired roll back execution state.

10. The system of claim 7, further comprising:

a plurality of inferencing sets;

a set history queue for each inferencing set, wherein said reversing means further includes means for reversing operations on each inferencing set using entries in the corresponding set history queue.

11. The system of claim 7,

wherein the breakpoint history queue contains an entry for each possible breakpoint reached during execution of said inference engine and wherein each entry corresponds to an execution state.

12. The system of claim 12, wherein said determining means comprises:

means for scanning said breakpoint history queue in reverse order to locate an entry matching the desired breakpoint, wherein the desired roll back execution state is set equal to the execution state corresponding to such matching entry.