Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1999-08-05
2003-03-18
Follansbee, John A. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S045000, C706S008000
Reexamination Certificate
active
06535864
ABSTRACT:
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The present invention generally relates to a method for detecting changes to a system state in a domain represented by a rules-based knowledge base.
BACKGROUND OF THE INVENTION
A knowledge-based system uses knowledge to solve problems. It is capable of distinguishing between knowledge itself and a knowledge interpreter, which is called an Inference Engine.
Knowledge itself can be represented by two distinct sets of information. The first is a set of domain-specific data about the problem and the environment, the confidence measures and the “dead ends” in the environment. The second set of information is a set of rules that express the conditions necessary to regulate the individual pieces of data in the first set, wherein the individual pieces of data represent facts about a steady state representation of the domain.
The Inference Engine is responsible for the execution process. The Inference Engine may employ some of the following principles:
Conflict resolution strategy that specifies which rule to fire first. Among commonly used strategies are the last recently used rule strategy or the most recently used rule strategy, etc.
Efficient pattern matching like the Markov Algorithm, that controls the search using a predefined order of rules to fire or the Rete Algorithm that speeds up the Markov Algorithm by looking only for changes in matches rather than for every rule every time.
Execution of the Right-Hand-Side of rules, which facilitates certain kind of prediction of the possible behavior.
Prior art in the area of this invention includes knowledge being represented by a rooted acyclic directed graph, the Rete; where the nodes, with the exception of the root, depict patterns. A pattern is a unique combination of rules that lead up to a node from the root node in the acyclic directed graph. Paths from the root to the nodes, represent the left-hand side of the rules that make up the patterns. Information is stored at each node about the facts satisfied by the patterns of the nodes in the paths from the root up to and including the current node. This information is a relation representing the possible values of the variables occurring in the patterns in the path. Such a form of knowledge representation suffers from the enormous memory requirements for storing successively larger nodes since information stored at each node in the Rete network is the cumulative information stored at all the nodes before it in the path leading up to that node from the root node.
The Rete Algorithm, adopted by most knowledge processing systems, keeps up to date the information associated with the nodes in the graph. When a fact is added or removed from the corking memory, a token representing the fact and operation is entered at the root of the graph and propagated to its leaves, modifying as appropriate, the information associated with the nodes. This requires considerable processor time and memory resources devoted to propagating the change through all the nodes in the network before the rules affected by the change are identified and queued up for firing.
A need was felt to use a model-based approach that would allow the user to define relationships between rules and data. Thus, any update to the entire knowledge base could be made by applying that update to the root objects in the knowledge base and this update would result in all objects related to the root object being updated and so on. It was felt that a model-based approach to representation of domains would make the task of manipulating data and rules very simple.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an object-oriented method of mapping alterations in system state objects to knowledge-base objects called rules, both of which are part of an object-oriented model of the domain resident in a persistent repository.
Another object of the present invention is to provide an object oriented method of evaluating only those rules that have been affected by a state change.
Still another object of the present invention is to provide an object oriented method of allowing an AgendaQueue object to retain, for further processing, only those affected rules whose all rule conditions have been satisfied.
These and other objects, features and advantages, which will become apparent as the invention is described in detail below, are provided in a computer system executing a repository program and having a storage means, a method for mapping alterations in system state to rules, both of which are part of an object-oriented model resident in a persistent repository. The method includes storing in the persistent storage means the model comprising a set of rules and a set of facts defining event states, both of which are stored as objects. The set of rules and said set of facts comprise an object-oriented representation of the model. Next, a set of commands representing an extensible inference engine are loaded as mete objects into the persistent storage. The method accepts as inputs events representing alterations in the set of facts. All of the events are retained and the events are mapped to the set of rules for deriving a list of affected rules, which are evaluated to determine if they have been qualified. Only those affected rules determined as qualified are saved for further processing.
Still other objects, features and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is shown and described only the preferred embodiment of the invention, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive, and what is intended to be protected by Letters Patent is set forth in the appended claims. The present invention will become apparent when taken in conjunction with the following description and attached drawings, wherein like characters indicate like parts, and which drawings form a part of this application.
REFERENCES:
patent: 4916625 (1990-04-01), Davidson et al.
patent: 5136523 (1992-08-01), Landers
patent: 5159662 (1992-10-01), Grady et al.
patent: 5230061 (1993-07-01), Welch
patent: 5276776 (1994-01-01), Grady et al.
patent: 5283856 (1994-02-01), Gross et al.
patent: 5644770 (1997-07-01), Burke et al.
patent: 5758031 (1998-05-01), De Silva
patent: 5761389 (1998-06-01), Maeda et al.
patent: 5802253 (1998-09-01), Gross et al.
patent: 5809238 (1998-09-01), Greenblatt et al.
patent: 5996114 (1999-11-01), Moeller
patent: 6151697 (2000-11-01), Moeller
patent: 6158043 (2000-12-01), Moeller
patent: 6321217 (2001-11-01), Maeda et al.
patent: 6356885 (2002-03-01), Ross et al.
Lee et al., A Casual Knowledge-Driven Inference Engine for Expect System, Proceedings of the 31st Hawaii International Conference on System Sciences, Jan. 1998, vol. 5, pp. 284-293.*
Vestli et al., Modeling Control in Rule-Based Systems, IEEE Software, Mar. 1994, vol. 11, Iss 2, pp. 77-81.*
Cockett et al., Prime Rule-Based Methologies Give Inadequate Control, Proceedings of the ACM SIGART International Symposium on Methologies for Intelligent Systems, 1986, pp. 441-449.*
Whitson et al., Using an Artificial Neural Network System to Determine The Knowledge Base of an Expert System, Proceedings of the 1990 ACM SIGSMALL, 1990, pp. 268-270.*
Gupta et al., High-Speed Implementations of Rule-Based Systems, ACM Transactions on Computer Systems, May 1989, Vo 7, No. 2, pp. 11
Booker Kelvin
Follansbee John A.
Hoang Phuong-Quan
Rode Lise A.
Starr Mark T.
LandOfFree
Method for mapping alterations in system state to knowledge... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for mapping alterations in system state to knowledge..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for mapping alterations in system state to knowledge... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032241