1. Field of the Invention
This invention relates generally to rule-based systems for representing knowledge, and more specifically, to a novel conflict handling and assimilator mechanism for enabling the exchange or merger of rules with different format and, resolving conflicts among the merged rules.
2. Discussion of the Prior Art
Rule based systems, a form of knowledge based systems, originate from the context of Artificial Intelligence. The simplest, most widely used form of artificial intelligence technologies is the rule-based system, also known as expert system. Rule based systems are built using rules in the form of if/then patterns. A rule-based system is a way of encoding the knowledge of a human expert in a relatively narrow area of a system. Typically, it separates the logic (represented by rules) from the data (represented by facts or assertions). The advantages of such a system is that the knowledge of the human expert becomes comprehensible to a wide variety of people other than the software engineers who encode the knowledge. Another advantage is the ease of maintenance and modification, i.e., rules may be added/deleted/modified without going through the complete cycle of compile/test.
In all rule-based systems, each “if” pattern (conventionally referred to as an antecedent) is a pattern that may match one or more of the assertions in a collection of assertions. The collection of facts/assertions is sometimes referred to as the working memory. It is understood that the working memory can further be divided into short term facts or long term facts. The “then” pattern (conventionally referred to as consequent) specify new assertions to be placed into working memory (e.g., add to the short/long term fact sets). Thus, the rule-based system may be characterized as a deduction system. Oftentimes, in rule-based systems, the “if” pattern may be mapped into a set of external objects/procedures in order to acquire information. Such a system is referred to as an “active situated” rule-based system. In addition, the “then” patterns may specify actions by attaching a conclusion with a specific object/procedure. Such a rule-based system is referred to as a “reaction” system. An active situated reaction rule-based system utilizing both the active situated and reaction designs, is the most popular rule-based system design and is the basis of most commercial rule based systems.
Many rule based systems support backward and forward chaining. Forward chaining is the process of moving from the “if” patterns to the “then” patterns, using the “if” patterns to identify appropriate situations for the deduction of a new assertion or fact or the execution of an action. In a forward chaining system, if the antecedent (i.e., if pattern) of a rule is satisfied, the rule is triggered. Whenever a triggered rule produces a new fact/assertion, and subsequently performs an action, it is “fired.” In a deduction system, all triggered rules are generally fired. However, in a reaction system, when more than one rule is triggered at the same time and many possible actions may be possible, the need for conflict resolution is obvious to identify which actions/action should be executed. Conversely, backward chaining is the process whereby a hypothesis is formed and the antecedent-consequent rules are utilized to work backward toward the assertions or facts that support the hypothesis.
The decision on which chaining method to use to solve a problem or, whether a combination of both forward and backward chaining is to be used to solve a problem, depends on the nature of the problem. Forward chaining runs more efficiently if the following conditions are satisfied: a) all the facts are available and all possible conclusions from the facts are needed; and, b) the number of ways to reach a particular desired conclusion is large, but the number of conclusions that are likely derived from the facts is small. Backward chaining is appropriate if the following conditions are satisfied: a) if facts have not be gathered, and only one of many possible conclusions (such as a query to see if a particular conclusion is true) is required; and, b) if the facts may likely lead to a large number of conclusions, but the paths to reach the required conclusion is small.
The typical rule-based system has a relatively static set of rules while the collection of facts ((knowledge base) changes continuously with time. However, in most rule-based systems and applications, the collection of facts is also relatively static from one rule operation cycle to the next. Empirically, although new facts arrive and old ones are removed continuously, the percentage of facts that change per unit time is usually relatively small. For this reason, the obvious blind search oriented approach implemented for the rules-based system shell is very inefficient in performance as it consumes a large amount of computation because the entire ruleset has to be cycled whenever a new fact is added or deleted from the knowledge base. This blind search approach implementation has a computational complexity equal to:([number of rules*number of facts in the fact base]**[average number of tests per rule antecedent])which increases exponentially with the average number of tests per rule antecedent. Since only a small amount of facts is changed, most of the tests (in the antecedents) made on each iteration will have the same results as the previous ones. This observation has become the basis of an algorithm, known as the RETE algorithm, as described in “Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem”, Charles L. Forgy, Artificial Intelligence 19 (1982), 17-37, the contents and disclosure of which is incorporated herein. This algorithm is based on the incremental matching of rule antecedents and has become the basis of a whole generation of efficient rules-based systems, e.g., OPS5, ART and CLIPS.
The main idea of the RETE algorithm is to save the state of the bindings at the end of a given iteration cycle and, in the next cycle, generating only a list of the changes to be incorporated to the binding set as a function of the changes that have affected the binding set. The computational complexity of rule based system based on the RETE algorithm now becomes linear and equal to:(number of rules*number of facts in the fact base*average number of tests per rule antecedent)and is a substantial improvement over the blind search oriented implementation.
Currently, rule based systems have been widely used in a variety of applications that range from systems that encapsulate business rules into a traditional software application at a specific point of interest, e.g., the part that consists of the business logic and data, to systems that comprise of only rules (executable rules). The main advantage of using a rule-based system in an application is the clear and clean separation of data and business logic, which allows the creation, modification, and maintenance of rules independent of the underlying implementation mechanism. Another advantage of rule-based system is the use of rules (in the form of “if-then-else” syntax) which are much closer to natural language than what the current programming languages (such as Java or C++) can offer. Typical rule-based applications include personalization, marketing, contracts, negotiation, policy specifications, product specification, etc.
A major growing requirement and trend in e-business and network-centric computing is inter-operability, including the use of rule-based systems that are part of heterogeneous applications. For example, one application is a supplier who imports the requirement of a customer, and conducts the negotiation of contract between multiple parties. The sharing and merging of rules for e-business automation involves rules with different formats and will inevitably produce conflicts among rules. An important issue in rule systems is thus conflict handling, in the following sense: Two rules within the same ruleset (e.g., program, agent, knowledge base, database) may lead to incompatible, i.e., mutually exclusive, conclusions. For example, rule 143 classifies incoming message 1014 as having a very high degree of urgency, while rule 231 classifies message 1014 as having medium degree of urgency. Therefore, a system to handle conflicts is an important part of the updating, editing of existing rules as well as rule-sharing and merging. The lack of a systematic way to resolve conflict underlies the historical difficulties in specifying large (e.g., over 100) sets of rules.
It would be highly desirable to provide for a computing system implementing a rule-base knowledge system a conflict handling mechanism, e.g., for handling conflicts during the merging of imported business rules from either updating as in a rule editor, or from a heterogeneous application, e.g., remotely over the Internet. When merging an imported ruleset into a previously present ruleset, it would be desirable to assimilate them, in the sense of forming a new integrated (merged) ruleset.
While there is extensive prior art in the area of conflict handling in rules and rule-based inferencing, and on non-monotonic reasoning involving rules or database systems whose semantics are essentially equivalent to rules, the prior art has focused on conflict handling and merging within a single rule base (a.k.a. knowledge base or data base) in a single rule-based system associated with a single application, although that application may import rules from other applications that use that same rule-based system, e.g., database systems that merge updates and views (in database systems, views and queries and facts are often semantically equivalent to special cases of rules in the sense of logic program knowledge representation) or although that application may have previously created its rule base in part or all by translating rule language formats in addition to importing rules from other applications that use other rule-based systems (e.g., cf. the approach of the DARPA Knowledge Sharing Effort using the Knowledge Interchange Format).