4.8 Rule-based systems   Rule-based models consists one of the most popular paradigm for modellingcomplex systems behaviour and control, where symbolic, qualitative, relation-based, etc. representation of knowledge is necessary. Basically, any rule-based system is composed of a set of rules defining actions or conclusions in case specific conditions hold and an inference control mechanism determining the way and order of rules execution. Rule-based systems are probably the most general and most popular tool of Artificial Intelligence. In case of supervision system they can be applied for process monitoring and situation assesment, misbehaviour and fault detection and diagnosis, meta-level control, reasoning about system state and characteristics, decision support, etc. In this section basic concepts of rule-based systems are presented Elementary introduction to rule-based systems   A rule-based system is composed in principle of two main parts: a set of rules defining its rule-base (the basic part of knowledge-base) and the appropriate mechanism of rule interpreter called the inference engine. The rules define separate behaviour variants while the inference control mechanism takes care of rules selection and execution.

In many popular positions devoted to rule-based systems, the format of rules is defined as follows:

 
if <antecedent> then <consequent>
 
and is considered to be an inference, reasoning or production rule; in practice such a rule is similar tor equivalent to logical implication and is also called and if-then rule. The <antecedent> part is also named preconditions, conditional part, conditions, etc., while the <consequent> part is also called conclusion, hypothesis, action, etc., depending sometimes on the context and specific meaning. Moreover, if a rule: if <antecedent> then <consequent> is defined, then <antecedent> = LHS(rule) (Left Hand Side), while <consequent> = RHS(rule) (Right Hand Side). The basic meaning of any such rule is that if the conditions defined by the <antecedent> part are satified, then the conclusions or actions defined by the <consequent> part hold or are can be executed.

In certain works, the basic format is sometimes extended, as for

example to:
 


if <antecedent> then <consequent_1> else <consequent_2>


 


In such a case if <antecedent> is true then <consequent_1> holds or is performed (if action), but if <antecedent> is not satisfied, then <consequent_2> is confirmed or executed.

Many other extensions of the basic format are possible. For example, apart of specyfying rule name and number, it is possible to define the following additional elemnts of rule definition:
 

  • resources: these are the resources necessary to execute the action described by a rule. For example, in case of parallel rule execution - some rules may require exclusive use of certain resources (they may block the use of certain resources by other rules). The information may be necessary for the inference control mechanism in order to resolve some potential conflicts.
  • excluding conditions: this part provides the information when the rule certainly cannot be used. Note, that with regard to the fact that preconditions are specified explicitly, this addition can introduce some redundant information. However, in certain cases it may be profitable to prune (reject) some or most of the rules in a simple and efficient manner, since finding that a rule is inapplicable can be sometimes much more faster. This is the case of rarely used rules, the use of which can be excluded by a simple condition, e.g. a single fact.
  • retract - delete results: in case of systems dynamically modifying their environment it may be necessary to map these changes directly into the system memory; these part specifies which facts are no longer true after application of specific rule and as such should be retracted from the knowledge base,
  • assert- add results: as above, after application of a rule some new facts may become true; this part of the rule specifies which fact should be asserted to the knowledge base after successful application of the rule,
  • do actions: in case of control rules, these part specifies the actions or operations to be performed.
  • inform: in monitoring and supervision systems with a human supervisor it may be useful to specify an additional part containing a message for the operator. The given information, sent to the console or an archive file, can be parametrized, i.e. contain some knowledge including current process parameters.
  • next rule(s): in certain systems it may be the case, that after application of some rule it is very likely (or even sure) that the next candidate rule to be applied is determined (or a subset of the set of rules to be applied next can be given). Thus, it may be reasonable to specify this rule (these rules) explicitly, so as to enable the reasoning control mechanism to change the order of rule examination. Such a specification can significantly speed up the execution of rules, and thus improve the overall efficiency of the system.
    •


    Many further modifications and extensions are possible; however they do not change the basic concept of the if-then rules, but rather constitute some auxiliary mechanism convenient in practical applications.

     Basic rule execution mechanism   In the presented scheme of production rules the preconditions part is specified with use of a logical formula, attributive knowledge representation expression, qualitative expression or even linguistic formulaton. Disregarding the specification language, the The preconditions specify all conditions necessary for the rule to become applicable. Simultaneously, they specify all the states in which the specified production rule is applicable. Note that any of the rule components can contain parameters, i.e. variables for "adjusting" the rule to the current state and purposes. The values of the variables can be found by a rule matching mechanism, i.e. during the process of verification if the rule can be applied, or they can be given by a meta-control mechanisms, e.g. a goal defining one or by the user.

    Note that from logical point of view one can consider all variables in a rule to be universally quantified, similarly as in the case of Prolog clauses. However, the variables denote parameters to be instantiated before application of a rule. This means in fact that any rule with variables denotes a set of (or a general scheme of) applicable rules. The precise values of parameters may be selected by user and then the preconditions are proved, or - and this is more frequent approach - the values of variables for which preconditions are satisfied are found during the process of proving preconditions, as a side effect of the matching procedure.
    Assume that a given rule has the basic form, i.e. if <antecedent> then <consequent>, where the <antecedent> part is equivalent to a simple formula . Further, assume that the current state of the knowledge based is described with logical simple formula , i.e.  provides a conjunction of all the currently true facts. Let h denote the formula defining the <consequent> part (or an action to be carried out). Recall, that all the components can be parametrised with certain variables. The basic algorithm of single rule execution proceeds as follows:


      In case the rule has extended structure, the specific extensions should be interpreted in an appropriate way, hoever, the extensions to the above algorithm are quite straightforward. The only practical problem is to apply the substitution found () in a consistent way at any stage. Generation of the substitution can be performed by any pattern matching procedure; the most straightforward ones can be based on the logical unification scheme.

      Inference in rule-based systems

        Inference in rule-based systems is based on logic. Basically, the scheme of rules is similar to implication in syntax and in semantics. The application of any rule, being the basic step of any reasoning paradigm is thus analog to the modus ponens rule. The check for precondition satisfaction is a specific case of pattern matching; in fact it is also termed rule matching phase or rule precondition matching. Since the application of a single rule has already been described in a former subsection, here we concentrate on further problems concerning more advanced aspects of rule-based inference. First the problem of so-called conflict resolution will be considered.

      Consider a dynamic system composed of n rules. Conflict resolution problem can be stated as follows: given a set of n rules, select a single rule to be applied in the current state of the system under control/supervision, provided that two or more rules are potentially applicable. The conflict resolution problem does not exist in deterministic,i.e. ones for which only one rule can be applied in any state. The problem occurs if more than one rule can be applied for some state, and, in most of the systems a single rule is selected with respect to some auxiliary criteria, different from the ones consisting in preconditions satisfaction. Depending on the complexity of the structure of inference control mechanism two possible formulations, a basic one and an advanced one

      can be stated.

      The basic formulation is as follows. Consider a rule-based control systemcomposed of n rules . Assume that the rules are ordered linearly according to their indices. The conflict resolution problem consists now in selecting exactly one rule applicable in the current state. The selected rule should be applied and the process is to be repeated from the beginning.

      The basic strategies for approaching the above problem may vary depending on system specification and application. There are, however, two basic possibilities:


      In control and supervision problems mostly the second approach is applied. With respect to the organization of the rule interpreter three basic strategies for approaching the problem can be distinguished:
       


      Of course, the above approaches can be modified and extended with use of auxiliary reasoning control mechanisms, rule preselection tools, etc. For example, a modification consisting in use of a mechanism for context-dependent hierarchical switching with use of stack memory constitutes a useful mechanism.

    The advanced form of the conflict resolution problem statement includes selection of the conflict set and rule/rules selection and firing with possible passing the control to another mechanisms. Again, consider a system composed of n rules, say . The advanced formulation of the conflict resolution task is as follows: select a of rules with satisfied preconditions, and, if there are two or more such rules, select one satisfying some auxiliary criteria. Thus the approach consists of two stages: (1) initial elimination of rules which cannot be applied, and (2) selection of a rule best, appropriate or likely for performing the current control task.

    Strategies for the second stage can be constructed with use of the basic problem formulation stated as before. However, only strategies based on the third point seem reasonable; in case of linear inspection in closed loop and linear inspection with immediate going to the first rule after firing one, a large amount of time can be wasted for unnecessary testing of all the rules and selecting some of them with the ultimate goal of firing only one of them.

    For the advanced case several classifications of conflict resolution strategies can be put forward:

  • static vs. dynamic strategies; static strategies are based on criteria constant over time, while dynamic ones can take into account current context, time, number of (successful) repetitions of a rule, their recency, etc.,
  • syntactic vs. semantic strategies; the first ones base on the "shape" of the rule preconditions, while the second ones may take into account the current context, desired goal, and evaluated user-specified criteria,
  • direct vs. indirect strategies; the direct ones are based on simple comparison of rules and assigned to them ``ordering factors'', e.g. priorities, while the indirect strategies can be implemented with an auxiliary knowledge-based system, meta-rules and complex inference schemes,
  • strategies based on simple, prespecified criteria vs. modifiable, adaptable, and ones based on learning mechanisms.
    • Depending on the problem, its specification and resources available various strategies can be applied; no general criteria can be put forward. Compositions of several strategies may also be useful.
    Selected strategies for conflict resolution   In this section some selected strategies of conflict resolution are briefly outlined. A good overview of some most popular approaches for control systems is provided in the problem literature; the following strategies are listed:
     
  • rule ordering (a rule appearing earliest has the highest priority),
  • data ordering (a rule with the highest priority assigned to its conditions has the highest priority),
  • size ordering (a rule with longest list constraining conditions has the highest priority),
  • specificity ordering (arrange rules whose conditions are superset of another rule.
  • context limiting (consists in activating or deactivating groups of rules at any time to reduce the occurrence of conflict),
    •


    The two first approaches belong to direct, static ordering strategies. The third and the fourth ones constitute some specific cases of ordering possibilities with mostly syntax-based priority evaluation mechanism. Only the fifth one refers to semantics of the process but it is used to reduce the number of rules in the conflict set, and not to select a unique rule.

    For example, in OPS5 rule-based programing system [Brownston et al, 1985] two more complex strategies, LEX and MEA can be used. Roughly speaking, these strategies are implemented in four subsequent steps: refraction (deleting all instantiations fired previously), partial ordering based on recency (time tags corresponding to the working memory elements used are considered), partial ordering with respect to specificity (rules with greatest number of tests are considered first), and, finally, arbitrary selection. The MEA strategy considers the recency of the first condition of rules most important. Note that strategies as that used for rule-based programming may be unsatisfactory or even inadmissible for control of dynamic systems. For example, the refraction strategy may remove some instantiation previously executed, while repetition of exactly the same rule may be necessary to achieve certain goal via several similar moves.

      Forward vs. backward inference   Two basic direction of inference are theoretically possible: this is the so-called forward chaining, or data-driven inference and backward-chaining, or goal-directed inference. Depending on the particular problem, its characteristics and the type of rules applied the user can sometimes select the reasoning direction taking into account the current goal of inference.

    The forward chaining inference can be applied practically in any case. It is useful if there are relatively few initial facts, new facts should be produced, the goal is loosely specified or unspecified at all, etc. forward chaining normally produces well defined ground facts.

    Backward chaining is a bit more complicated; it may not be applied in any system. Note that if the rules have more variables in preconditions than in the conclusion part, than not fully specified facts are likely to be generated. Further, the strategy is a bit more complex, since all the facts necessary to prove the goal must be supported at any stage. This kind of inference is however more efficient when the goal is well defined, but there are many input facts. This strategy is also used in certain systems, e.g. Prolog.

    Further, combinations of the two modes can be applied. The most typical strategy is to combine forward checking as a general control strategy, while at some stages if detailed goals are to be inferred backward chaining is applied.

      Models for rule interpreters   Even in the case of simple interpreters selecting and executing single rule at a time, there are several possibilities for organizing the work of such systems. Assume a linear sequence of rules is specified and it is of the form $r_{1},r_{2},\ldots ,r_{n}$. The interpretation schemes can proceed as follows:
     
  • linear execution with subsequent selection of all executable rules which are executed in turn; thus after finding and executing a single rule found, the next rules are examined and executed in turn. Only after reaching the last rule the system backtracks to the beginning. In Prolog this scheme would correspond to the repeat-find-execute-fail loop format. In decision lists this mode of work corresponds to linear list organisation. Further, this type of interpretation is normally performed in decision tables.
  • hierarchical interpretation from the beginning to first executable rule (one with satisfied preconditions); then the system backtracks immediately to the beginning and repeats the cycle. In Prolog this would correspond to the run-find-execute-!-run loop scheme. This kind of interpretation is similar to the one provided in hierarchical decision lists.
  • linear interpretation with rule switching, i.e. linear interpretation from the beginning to first executable rule (one with satisfied preconditions); then the system jumps to some rule or rules indicated by the recently executed rule. This kind of scheme consists in switching among rules within one rule-base. There are also several possibilities of further interpretation: the new rules can direct the system to other rules or after executing them the system can jump back either to the place it left from or to the beginning. Further, there can be no return option and the system can follow linear interpretation after executing (or not) the rule it jumped to. This corresponds to use of the next part in rules,
  • linear examination with context switching; linear examination may be combined with context switching, i.e. after some rule is executed, the current situation of the system is evaluated, the current context (qualitative situation) is determined and a decision making mechanism switches to a different set of rules appropriate for this context.
    •


    The above types of interpreters are schematically presented on the following pictures.

    Generic applications of inference rules   Let us present three basic problems which can be approached with use of a system of inference rules as presented above. The problems refer to modelling system behaviour (in other words simulation of system behaviour), direct control of a given system (or meta-control), and plan generation (control synthesis). The problems can be roughly formulated as follows:

    Simulation: Assume we consider a dynamic relational system. There is given a finite set T of production rules defining transformations for modelling all the possible state changes. Given an initial state  find possible system behaviour for a limited number of transformation stages. In the case of simulation one can be interested in obtaining any possible behaviour (i.e. for any admissible sequence of transformation rules and parameters), or only some of the possible trajectories which are generated with some additional information concerning what rules and what parameters should be considered at any stage. This kind of approach is referred to as knowledge-based simulation and in case of application of qualitative formalism - qualitative simulation.

    Control: Assume one observes a dynamic relational system at discrete instants of time. At any instant the state formula of the system is known, as well as the goal of control (if specified explicitly). In practice, the formula defining the current goal may be a part of the state formula. The task is to build a knowledge-based control system, i.e. to design a set T of rules, to be applied to the current state one at a time, so as to assure the desired behaviour of the controlled system. The set of rules should be implemented in such a way, that for any state at least one action will be applicable (including the do-nothing action, if necessary). If more than two actions are applicable in certain state, or an action is applicable in different ways (for different parameters given by ), a reasoning control mechanism for conflict resolution should be provided as well. This kind of rule-based system can be used for direct control (direct rule-based control, reactive control) or can be applied for meta-level control, e.g. for parameter and set-point selection, control algorithm selection, model or goal adjustment, etc.The application to process monitoring, situation recognition, and supervision (including fault detection, diagnosis and decision support) can be located within this kind of applications.

    Planning: As in the case of simulation, assume that a dynamic relational system is under consideration. There is given a finite set T of production rules for modelling all the possible state transformations (these are in fact state transformation rules). Given an initial state  and a desired goal state  find a sequence of actions (together with their parameters) transforming the initial state into one satisfying the conditions of the goal state; the goal state can be defined in a more general way, i.e. only some requirements can be specified explicitly and thus there may exist more than one state satisfying the goal conditions.

    Although mainly the problems of knowledge-based proces monitoring, control, and supervision are considered here, the formalism itself and certain results applies directly to the cases of simulation and planning as well. Moreover, the presented formalism can be applied in other problems solved with knowledge engineering approach, such as automated diagnosis, decision support, computer aided design and other topics.