 |
Claims  |
|
|
We claim as our invention:
1. A method of diagnosing faults in a predetermined system, comprising the
steps of: providing domain specific rules, including rules in
evidence-hypothesis form, to build a knowledge base of assertions relative
to the predetermined system,
maintaining said knowledge base free of information which makes inferences
relative to the knowledge base,
providing data relative to the predetermined system,
providing inference rules, independent and distinct from said domain
specific rules, which make belief propagating inferences in response to
the data, by selecting and applying the domain specific rules,
propagating belief in the hypotheses of selected domain specific rules, in
response to the data, by the step of interconnecting the domain specific
rules, under the control of the inference rules, into a rule network of
hypothesis nodes interconnected by evidence,
and outputting information in response to the belief propagating step.
2. The method of claim 1 including the step of dividing the inference rules
into two levels, with the first level including task control rules which
make inferences for controlling the selection and application of domain
specific rules, and with the second level including procedural rules which
make inferences for controlling the selection of the task control rules of
the first level, when there is a choice.
3. The method of claim 1 wherein the inference rules include rules for the
steps of:
determining when a belief propagating path appears unproductive,
storing the information developed for an unproductive path,
starting a new belief propagating path,
and returning to an apparently unproductive path in response to
predetermined conditions, using the information previously stored, to
start at the point of previous termination.
4. The method of claim 1 wherein the domain specific rules include
confidence factor threshold (CFT) values, and the inference rules include
rules for the steps of:
developing a confidence factor for each hypothesis node in the propagating
step, using the confidence factors of supporting nodes,
comparing the developed confidence factor for each hypothesis node with an
associated CFT value to determine when the present propagating path
appears to be unproductive,
storing the information relative to an apparently unproductive path,
and returning to an apparently unproductive path in response to
predetermined conditions, using the information previously stored to start
at the point of previous termination.
5. The method of claim 1 wherein the domain specific rules include path
factors which assign relative values to alternate paths from a node, which
path factors are utilized by the inference rules in selecting domain
specific rules.
6. The method of claim 1 wherein the domain specific rules include forward
path factors which assign relative values to alternate paths from a node
to supported rules, which path factors are utilized by the inference rules
in selecting domain specific rules.
7. The method of claim 1 wherein the domain specific rules include backward
path factors which assign relative values to alternate paths from a node
to supporting rules, which path factors are utilized by the inference
rules in selecting domain specific rules.
8. The method of claim 1 wherein the domain specific rules include
confidence factor threshold (CFT) values, and the inference rules include
rules for establishing the steps of:
developing a confidence factor for each hypothesis node in the propagating
step, utilizing the confidence factors of supporting nodes,
comparing the developed confidence factor for each hypothesis node with the
CFT values,
firing the associated rule, to continue the present propagating path, when
the comparison is within the CFT values,
noting the relative firing times of the rules in working memory elements
(WME),
terminating the present propagating path when the comparison is outside the
CFT values,
storing information relative to the terminated path,
and looking for a new belief propagating path from the hypothesis nodes of
fired rules, using the relative firing times stored in the WME's, to
select the order.
9. The method of claim 8 wherein the inference rules include rules for
establishing the step of returning to the most recent WME to continue a
terminated belief path, in response to predetermined conditions.
10. The method of claim 9 wherein the step of returning to the most recent
WME includes the step of disregarding the CFT comparison step, for at
least one rule, to advance belief propagation by firing the associated
rule.
11. The method of claim 1 wherein the domain specific rules include values
which assign relative weights to multiple pieces of evidence for a rule,
and confidence factor assumption (CFA) values, and the inference rules
include rules for propagating belief without obtaining all of the evidence
for a hypothesis by the steps of developing a confidence factor CF for
each hypothesis node, setting the weight of a missing piece of evidence to
zero, comparing the confidence factor CF with the CFA value, and
continuing without the missing evidence when CF exceeds the CFA value.
12. The method of claim 11 wherein the inference rules include rules for
establishing the step of returning to rules which were fired with missing
pieces of evidence, in response to predetermined conditions.
13. The method of claim 12 wherein the domain specific rules include rules
which have a malfunction hypothesis, with a predetermined condition which
will trigger the return to a rule fired with missing evidence is a CF of a
malfunction hypothesis being in a predetermined range.
14. The method of claim 1 wherein the step of providing data includes the
step of providing sensor data, the step of providing domain specific rules
includes providing values which enable a sufficiency factor SF to be
determined for each sensor, and the step of providing inference rules
includes the step of determining the SF for each sensor supported rule.
15. The method of claim 1 wherein the step of providing domain specific
rules includes the step of assigning values SF to the rules based upon the
confidence that the evidence, when present, supports the hypothesis, and
values NF to the rules based upon the necessity of the evidence to the
belief of the hypothesis, when substantiating evidence is not present.
16. The method of claim 1 wherein the step of providing data includes the
step of providing sensor inputs, the step of providing domain specific
rules includes the step of assigning a confidence factor CF to each
sensor, and the inference rules include the steps of developing a
sufficiency factor SF relative to the data provided by a sensor based upon
its value, and developing a measure of belief MB relative to the sensor
data equal to the product of the CF and SF.
17. The method of claim 15 wherein the step of providing inference rules
includes rules for determining a measure of belief MB in the hypothesis,
determining a measure of disbelief MD in the hypothesis, by utilizing SF
and NF, and for determining a confidence factor in the hypothesis
according to the difference between MB and MD.
18. The method of claim 1 wherein the step of providing data includes the
step of providing sensor data, and the step of providing domain specific
rules includes malfunction hypotheses, and wherein the inference rules
include rules for forward chaining from known sensor inputs, until nodes
are reached requiring unknown evidence, and rules for backward chaining to
establish additional sensor data required to provide the unknown evidence,
with the forward and backward chaining continuing until a malfunction node
is reached.
19. The method of claim 1 wherein the step of providing domain specific
rules includes the step of attaching predetermined signals and associated
conditions to predetermined hypotheses, and the inference rules include
rules for outputting such signals when the associated hypothesis node
meets the conditions for outputting the signal.
20. Apparatus for diagnosing faults in a predetermined system, comprising:
sensors for providing sensor data relative to the performance of the
predetermined system,
a domain specific knowledge base, including a plurality of rules in
evidence-hypothesis form, which make assertions relative to the
predetermined system,
said knowledge base being free of information which makes inferences
relative to the knowledge base,
domain independent inference rules, including first and second levels of
inference rules,
means interconnecting said sensors, said domain specific knowledge base,
and said domain independent inference rules,
said first level of inference rules including means for testing evidence
portions of selected rules of said domain specific knowledge base in
response to said sensor data, and means responsive to successfully tested
(fired) rules for making belief propagating inferences relative to the
hypotheses of the domain specific rules,
said second level of inference rules including means for determining which
of the first level inference rules to apply when there is a choice,
and means for outputting signals relative to at least certain of the domain
specific rules which fire when their evidence portions are tested.
21. The apparatus of claim 20 wherein the domain specific knowledge base
includes sensor information relative to each sensor, and the inference
rules include means responsive to said sensor information for determining
the confidence factor CF of the sensor data.
22. The apparatus of claim 20 wherein the domain specific knowledge base
includes values SF assigned to at least certain of the domain dependent
rules based upon the confidence that the evidence, when present, supports
the hypothesis, and values NF related to the necessity of the evidence to
the belief of the hypothesis when it is missing, and the influence rules
include means for determining a measure of belief MB and a measure of
disbelief MD in the hypotheses of selected domain dependent rules, based
upon the CF of the evidence and the SF and NF of the rules, and for
developing a confidence factor CF responsive to the difference between MB
and MD.
23. The apparatus of claim 22 wherein the domain specific knowledge base
includes confidence factor threshold values CFT, and the inference rules
include means for comparing the CF of a rule with a CFT value, firing the
rule when the CF is within the CFT, and backing up to start a different
path through the domain dependent rules when it is outside the CFT.
24. The apparatus of claim 23 wherein the inference rules include means for
returning to a non-fired rule in response to predetermined conditions, and
including means for firing the rule without regard to the CFT.
25. The apparatus of claim 20 wherein the output signals include control
signals which modify the operation of the predetermined system.
26. The apparatus of claim 22 wherein the domain specific rules include
values which assign relative weights to multiple pieces of evidence for a
rule, and confidence factor assumption (CFA) values, and the inference
rules include means for propagating belief without obtaining all of the
evidence for a hypothesis, including means for developing a confidence
factor CF for each hypothesis mode, means for setting the weight of a
missing piece of evidence to zero, means for comparing the confidence
factor CF with the CFA value, and means for continuing to propagate belief
without the missing evidence when CF exceeds the CFA value.
27. The apparatus of claim 26 wherein the inference rules include means for
returning to rules which were fired with missing pieces of evidence, in
response to predetermined conditions.
28. The apparatus of claim 20 wherein the inference rules include means
for:
determining when a belief propagating path appears unproductive,
means for storing the information developed for an unproductive path,
means for starting a new belief propagating path,
and means for returning to an apparently unproductive path in response to
predetermined conditions, using the information previously stored, to
start at the point of previous termination.
29. The apparatus of claim 20 wherein the domain specific rules include
path factors which assign relative values to alternate paths from a node,
and the inference rules include means for considering the path factors in
selecting domain specific rules.
30. The apparatus of claim 20 wherein the domain specific rules include
malfunction hypotheses, and wherein the inference rules include means for
forward chaining from known sensor inputs, until nodes are reached
requiring unknown evidence, means for backward chaining to establish
additional sensor data required to provide the unknown evidence, and means
for continuing forward and backward chaining until a malfunction node is
reached.
31. A method of diagnosing faults in a predetermined system, comprising the
steps of: providing domain specific rules having confidence threshold
(CFT) values, including rules in evidence-hypothesis form, to build a
knowledge base of assertions relative to the predetermined system,
providing data relative to the predetermined system,
providing inference rules which make belief propagating inferences in
response to the data, by selecting and applying the domain specific rules,
propagating belief in the hypothesis of selected domain specific rules, in
response to the data, by the step of interconnecting the domain specific
rules, under the control of the inference rules, into a rule network of
hypothesis nodes interconnected by evidence,
said step of propagating belief including the steps of:
(a) developing a confidence factor for each hypothesis node in the
propagating step, using the confidence factors developed for supporting
nodes,
(b) comparing the developed confidence factor for each hypothesis node with
the associated CFT value to determine when the present propagating path
appears to be unproductive,
(c) storing the information relative to an apparently unproductive path,
and (d) returning to an apparently unproductive path in response to
predetermined conditions, using the information previously stored to start
at the point of previous termination,
and outputting information in response to the belief propagating step.
32. The method of claim 31 wherein the step of returning to an apparently
unproductive path includes the step of disregarding the CFT comparison
step (b), for at least one rule, to advance belief propagation by firing
the associated rule.
33. A method of diagnosing faults in a predetermined system, comprising the
steps of: providing domain specific rules, including rules in
evidence-hypothesis form, to build a knowledge base of assertions relative
to the predetermined system, said domain specific rules including values
which assign relative weights to multiple pieces of evidence for a rule,
and confidence factor assumption (CFA) values,
providing data relative to the predetermined system,
providing inference rules which make belief propagating inferences in
response to the data, by selecting and applying the domain specific rules,
propagating belief in the hypotheses of selected domain specific rules, in
response to the data, by the step of interconnecting the domain specific
rules, under the control of the inference rules, into a rule network of
hypothesis nodes interconnected by evidence,
said belief propagating step propagating belief without obtaining all of
the evidence for a hypothesis of the steps of: (a) developing a confidence
factor CF for each hypothesis node, (b) setting the weight of a missing
piece of evidence to zero, (c) comparing the confidence factor CF with the
CFA value, and (d) continuing without the missing evidence when CF exceeds
the CFA value,
and outputting information in response to the belief propagating step.
34. The method of claim 33 wherein the domain specific rules include rules
which have a malfunction hypothesis, and including the step of returning
to a rule which was fired with missing evidence when the CF of a
malfunction hypothesis is in a predetermined range. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates in general to fault diagnosis, and more specifically
to a generic facility for the construction of knowledge based expert
systems for sensor and interactive based process diagnosis.
2. Description of the Prior Art
Expert systems have been typically characterized by a knowledge base and an
inference engine. The knowledge base usually consists of rules specific to
the task domain and the inference engine usually consists of a set of
procedures which manipulate the task specific rules. Prior art examples
are programs for medical diagnosis and mineral exploration. These prior
art systems have rigid procedural mechanisms for dealing with belief and
disbelief and hypotheses. The rules for belief propagation are, in a
sense, "hard wired" into the procedural inference engine in a manner
similar to the instruction-fetch unit in typical computers. As a result,
the structure of the domain-specific rules is also rigid. The domain
expert must formulate his knowledge into the exact structures demanded by
the form of the rules.
Another prior art expert system, which configures computer systems,
demonstrates another method by which an expert system may be constructed.
In this system, the basic inference mechanism is stripped of all
task-specific knowledge. The task specific knowledge or rule base embodies
not only knowledge about the task domain, but also knowledge about how
best to apply the rule base in order to accomplish a particular goal. The
task-specific domain knowledge and knowledge about task control are
integrated into productions or rules. Some productions are used strictly
for control, such as rules to add or remove a sub-task context, but most
rules have control information integrated into preconditions into their
left-hand sides, i.e., the antecedent of the antecedent-consequent
production rule form. Integrating the task domain knowledge with the task
control knowledge results in a system architecture which is appropriate
only to a certain set of highly structured domains. For example, this
prior art method does not deal with uncertainty in its reasoning process,
and it has no mechanism for "backing up" if it makes a poor decision. The
program assumes that it has enough knowledge to bring to bear to correctly
choose each rule to apply at every step. In complex task domains, however,
building enough control knowledge into the object-level rules is both
time-inefficient and more difficult for the "knowledge engineer" (the
builder of the rule base) to accomplish. The task of configuring computers
may be sufficiently structured that the system can effectively know all
there is to know at each step in the computer configuration process, and
consequently, it can make the right choices the first time. However, most
diagnostic domains are too complex and too ill-structured for this
approach to be feasible. While in this prior art system for determining
computer configuration, the task control knowledge has been removed from
the inference engine, which has certain advantages, it has mixed it with
the task domain knowledge, which, in complex domains, has other important
disadvantages.
There is also an issue of whether or not input to the expert system is
reliable. Many systems merely assume that input from the user is always
reliable. Some prior art systems assume that the domain is sufficiently
well structured that, with a rudimentary pre-processing package which
checks for input consistency and feasibility, any problems with user input
can be easily resolved. Other systems try to deal with unreliable input by
allowing the user to specify a measure of certainty for each input value.
This measure of certainty is then propagated along with the input value
throughout the object-level rule base. In effect, the process of reasoning
about the reliability of the input is removed from the expert system and
assigned to the user. Neither the assumption that dealing with unreliable
input is trivial, nor the practice of off-loading the responsibility of
handling unreliable input to the user, is an adequate solution for complex
systems.
Another prior art system employs techniques referred to as "retrospective
analysis" and "meta-diagnosis" to handle the problems of spurious sensor
readings and sensor degradation. Retrospective analysis refers to the
process of maintaining a history of sampled sensor inputs so that spurious
readings can be detected and processed appropriately. In most cases, this
involves some sort of averaging technique which is augmented, perhaps,
with a conversion to engineering units. Meta-diagnosis is a technique
whereby the long-term behavior of individual sensors is monitored. When an
aberration is detected, the importance of the sensor is diminished through
the use of explicit "parametric-alteration" rules.
Thus, previous expert systems have either chosen to ignore the problem of
reasoning about their inputs, or they have included some primitive,
procedurally encoded mechanisms which suffer from being difficult to
modify or extend. The result is a reasoning capability which is limited by
the rigid constraints of the design of the procedural inference engine.
SUMMARY OF THE INVENTION
Briefly, the present invention includes new and improved methods and
apparatus for developing a generic facility for the construction of any
knowledge-based expert system, as opposed to the development of any
specific system. The system is based upon a hierarchy of rules. At the
lowest level are the system's object-level rules which are specifically
directed to providing evidence for diagnosing a particular process,
system, or piece of apparatus. Above the object-level rules are the
meta-level inference rules which include means for reasoning about the
veracity of the input to the system, about the control strategy which
determines the order in which the object-level rules are applied, and
about how these object level rules were chosen for the purpose of
explaining belief in the system's conclusions. At the top of this
hierarchy of rules is a generic procedural inference mechanism with no
domain-specific knowledge which chooses meta-level rules to apply when
there is a choice, based on criteria which can be selected by the user,
e.g., depth-first, breadth-first, best-first search, etc. The meta-level
rules might logically be compared to the control structure in a typical
graph search problem. The problem is basically one of selecting the best
node (hypothesis) for expansion, from the current "open" list, such that
the optimum path to correct problem diagnosis is found in the shortest
amount of time using a minimum of user input. In this comparison, the
meta-level inference rules are analogous to the control strategy in a
graph search. The domain dependent object-level rules are analogous to the
operators used in changing states between nodes. Inputs, hypotheses, and
malfunctions are analogous to the start nodes, intermediate nodes, and
goal nodes in the search space.
In the present invention, the entire inference process, in whatever style,
is implemented entirely in a meta-level rule structure which is completely
distinct from the object-level rule base. In the meta-level, the
procedural rules which select the inference rules when there is a choice,
are completely distinct from the inference rules which select and apply
the object level rules. This architecture provides tremendous flexibility
in building an expert system to meet any specified need. It provides the
ability to easily make changes in the object-level rule base, as well as
in the dual level of the meta-level rule base, because the rules are
separate and their structures interact minimally.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention may be better understood, and further advantages and uses
thereof more readily apparent, when considered in view of the following
detailed description of exemplary embodiments, taken with the accompanying
drawings, in which:
FIG. 1 is a block diagram which sets forth an expert diagnostic system
constructed and arranged according to the teachings of the invention;
FIG. 2 is a rule network diagram which will be used as an example when
explaining different methods of propagating belief in hypotheses,
according to the teachings of the invention;
FIGS. 3A through 3F are graphs which set forth different mechanisms for
measuring belief and disbelief in hypotheses, as well as certainty factors
of the evidence and hypotheses;
FIG. 4 is a procedural flow diagram which sets forth a forward chaining
process, as conducted according to the teachings of the invention;
FIG. 5 is a diagram which illustrates the logic used in selecting the
measure of belief MB, or the measure of disbelief MD, for updating;
FIG. 6 is a procedural flow diagram which sets forth a sub-program CF which
may be called by other programs for determining the certainty factor CF of
the hypothesis of a domain dependent rule;
FIG. 7 is a procedural flow chart which sets forth a backward chaining
process, as conducted according to the teachings of the invention; and
FIGS. 8A, 8B and 8C may be assembled to provide a procedural flow chart
which sets forth mixed inference chaining, as conducted according to the
teachings of the invention.
DESCRIPTION OF PREFERRED EMBODIMENTS
Referring now to the drawings, and to FIG. 1 in particular, there is shown
a block diagram of an expert system 10 constructed according to the
teachings of the invention. The expert system 10 monitors the system, it
detects malfunctions, it provides control signals, and it aids service
personnel in diagnosing system faults. The invention does not pertain to a
specific expert system, but teaches how to improve upon the construction
of any expert system, for any system 12 which uses sensors as inputs. The
system, as well as being sensor based, is also usable in interactive modes
for aiding service personnel in diagnosing system malfunctions. While the
invention does not pertain to a specific expert system, specific examples
to be hereinafter set forth will pertain to the detection and diagnosing
of malfunctions in an elevator system, since a first application of the
invention pertains to an elevator system.
Arrangement 10 is based upon a hierarchy of rules. At the lowest level of
this meta-level architecture are domain specific object-level rules, which
include information useful in diagnosing malfunctions in system 12. Above
the object-level rules are domain independent meta-level rules which
include means for giving different weights to the sensor inputs to the
system, and they provide the control strategy for determining the order in
which the object-level rules are applied. The meta-level rules also
include means for storing information about how the object-level rules
were chosen, for the purpose of explaining belief in the system's outputs.
At the top of this hierarchy of rules is a generic inference mechanism
with no domain-specific knowledge, which chooses meta-level rules to apply
when there is a choice, based upon criteria which can be selected by the
user.
More specifically, the invention includes a plurality of sensors 14
arranged to provide input data relative to the sensor-based system 12. The
sensors 14 monitor and collect data relative to system 12, with the
sensors collecting data in analog and/or digital form, as required by the
specific system. The data from sensors 14 are applied via suitable input
ports to computer memory means 16, such as a random access memory (RAM).
The computer associated with memory 16 may be on-site or remote, as
desired. Modems may be used for remote communication. Memory means 16, in
addition to including storage space for the sensor data, includes a
memory, such as disc storage, for storing a domain dependent knowledge
base in the form of object-level rules. The object level rules contain
information provided by an expert or experts, in the field associated with
system 12, with a knowledge engineer taking the domain specific
information and placing it in the form of object level rules. The object
level rules are not coded as part of a computer program, but they are in
the form of a list, or lists, which may be easily changed, e.g., added to,
deleted from, and/or modified, and easily searched by list processing
computer languages, such as LISP or versions thereof.
Each object-level rule has an antecedent which may include one or more
pieces of evidence, and a consequent which may be an actual process
malfunction or an intermediate hypothesis. Each hypothesis or node may be
used as evidence for a higher level rule. In addition, each object-level
rule has an associated sufficiency factor SF and necessity factor NF. Each
hypothesis and malfunction has an associated measure of belief MB, measure
of disbelief MD, and an aggregate confidence factor CF. In general, the
sufficiency factor SF is used as a measure of how strongly the domain
expert feels that supporting evidence should contribute to positive belief
in the hypothesis, and the necessity factor NF is used as a measure of how
strongly contrary evidence, or lack of evidence, should increase disbelief
in the hypothesis. Thus, the object level rules have assigned values which
enable the meta-level rules to make assertions based upon the strength of
the evidence to each object-level rule. Therefore, the meta-level rules do
not merely make assertions which are assumed to be either true or false,
but rather enable "reasoning" to take place, using gradations of belief in
the assertions.
System 10 includes additional computer memory locations 18, 20 and 22.
Memory location 18 includes information about the current status of the
system 12, and other domain dependent assertions which are not in the form
of object level rules. For example, if system 12 is an elevator system,
memory 18 would include facts about the elevator system such as the number
of floors in the associated building, the locations of specific floors,
such as lobby floors, restaurant floors, garage floors, the number of cars
in the elevator system, the number of cars currently in service, the
floors each car can serve, and the like. Memory 20 includes look-up tables
which store values SF associated with the sensor readings, constants FPF
and BPF associated with the nodes (hypotheses), formable in a rule
network, and the hereinbefore-mentioned constants SF and NF associated
with each of the object level rules. Memory means 22 may store
predetermined system related constants, such as CFT and CFA values, as
will be hereinafter explained. The CFT and CFA values, instead of being
system related, may also be node related, in which event, they would be
stored in memory 20.
The description of arrangement 10 to this point describes information which
is domain dependent, i.e., specifically related to the system 12, and this
information is the information 23 located above a broken line 24 which
separates domain dependent and domain independent information 23 and 25,
respectively.
The domain independent information 25 of arrangement 10 includes meta-level
rules which contain the entire inference process, which is completely
distinct from the object level rule base. In other words, the domain
dependent information 23 includes no information on how to connect the
object level rules 16, or how to otherwise use the disparate bits of
domain dependent information to detect and diagnose system malfunctions.
On the other hand, the domain independent information 25 may operate with
any domain dependent information 23, and is the part of system 10 which
includes computer programs. This arrangement provides the ability to make
changes both to the object-level rule base and to the meta-level rule base
easily and painlessly, because the two kinds of rules are completely
separate and have minimal interaction.
More specifically, the meta-level rules of the domain independent
information 25 are divided into two levels, with a first level including
memory means 26 in which rules are stored which: (a) take into account the
veracity of the sensor inputs, (b) determine which object level rules to
apply to detect and diagnose system malfunctions in an expedient manner,
and (c) explain how system conclusions were reached. As indicated in Table
I below, these rules include chaining rules indicated in memory block 28,
such as forward chaining. Forward chaining starts at the sensor level and
works towards the malfunction hypotheses. These rules also include
backward chaining. Backward chaining starts with a user supplied
malfunction, and the program works from this malfunction node back to the
sensor level, to determine which sensor inputs are pertinent. These rules
also include mixed inference chaining, which utilizes both the principles
of forward and backward chaining in a unique manner to build from a few
pieces of evidence while directing a user as to whatever pieces of
evidence are necessary in order to continue system diagnosis. Rules for
using forward and backward path factors FPF and BPF, respectively, are
also included in memory block 28.
TABLE I
______________________________________
META LEVEL RULES
BELIEF PROPAGATING-
______________________________________
Forward Chaining Rules
Backward Chaining Rules
Mixed Chaining Rules
Rules for Forward & Backward Path Factors
Rules for Handling MB(H) & MD(H)
Rules for Determining CF(H)
Rules Re Confidence Factor Thresholds (CFT)
Rules Re Confidence Factor Assumption
Rules for Determining Sensor SF
______________________________________
The first level of meta-level rules also includes rules for determining the
measure of belief MB and the measure of disbelief MD relative to a
specific hypothesis, with these rules being indicated in memory block 30.
Rules concerning confidence factors are indicated in memory block 32.
These rules include rules for determining a confidence factor CF relative
to a hypothesis, rules relative to the use of the confidence factor
threshold values CFT, and rules for using the confidence factor assumption
value CFA.
The second level of the meta-level rules includes procedural rules
indicated in memory block 34, which determine which of the first level
metal-level rules to apply when there is a choice. The rules at the second
level may be user selected. As indicated in Table II below, these rules
include such options as the most recent working memory element (MRWME),
which rules include means for storing the time when each object level rule
is successfully applied, also hereinafter referred to as "fired". Other
procedural rules which may be used are those from graph searching
techniques, such as shallow first, depth first, breadth first, best first,
and the like.
TABLE II
______________________________________
META LEVEL RULES-
PROCEDURAL
______________________________________
Most Recent Working Memory Element (MRWME):
Shallow First;
Depth First;
Breadth First;
Best First
______________________________________
The arrangement of FIG. 1 has different operating modes, including modes
which are interactive, such as the backward chaining and mixed inference
chaining modes. A keyboard 36 enables a user to enter information for use
by the program which applies the meta-level rules. The program which
applies the meta-level rules also includes output ports 38 for
communicating and sending signals to a variety of output devices, such as
a display 40 for use in an interactive mode. The display 40 may include
voice synthesis, if desired. Non-interactive modes, such as forward
chaining entirely from sensor inputs, may include output ports for sending
signals to the system 12. For example, when predetermined malfunctions are
detected, predetermined signals associated therewith may "fire", which,
among other things, may modify the operation of system 12. For example,
when system 12 is an elevator system, a signal from output port 38 may
control a relay in the safety circuit of the elevator, shutting down
specific elevator cars, or even the entire elevator system, depending upon
the nature of the malfunction. Simultaneously, while modifying system 12,
signals from output ports may actuate local alarms 42, and/or remote
alarms 44. The latter may use auto-dial modems, for example.
In describing the procedural flow charts of FIGS. 4, 6, 7 and 8, which
teach the new and improved methods of the invention, it will be helpful to
use the rule network shown in FIG. 2. The rule network is an inference net
of logical nodes and logical rules created by the inference program for
its own use, and is transparent to the user. The references 41R, 40R, 65R,
72T, LD and LU are sensor nodes which represent inputs from sensors which
monitor the conditions of elevator system relays having the same
identifying indicia. U.S. Pat. Nos. 4,436,184; 4,042,068; and 3,902,572,
for example, may be referred to for more information regarding these
relays, if desired. Arrows (a) through (f) in FIG. 2 represent sensor
supported rules, which are supported by the sensor nodes. Table III sets
forth rules (a) through (f) in IF:THEN form, with the evidence on the
left-hand side (LHS), and the hypothesis on the right-hand side (RHS) of
each rule.
TABLE III
______________________________________
SUPPORTED RULES FOR SENSORS
RULE IF: THEN:
______________________________________
(a) Relay 41R is deenergized
Hatch door is not locked
(b) Relay 40R is deenergized
Car door is not closed
(c) Relay 65R is energized
Car is running
(d) Relay 72T is deenergized
Car is not releveling
(e) Relay LD is energized
Down leveling switch not
on cam
(f) Relay LU is energized
Up leveling switch not on
cam
______________________________________
The nodes pointed to by the arrows represent the hypotheses of the rules,
and these nodes are used as evidence for firing higher level object level
rules. Object level rules (g) through (l) are set forth in Table IV. The
intermediate hypothesis nodes may also be referred to as logical nodes,
with AND nodes having the evidence arrows interconnected by a single
curved line, OR nodes having the evidence nodes interconnected by two
spaced curved lines, and NOT nodes being indicated by the word NOT. The
associated rules are logical rules, with the hypotheses or logical nodes
being used as evidence for still higher level object rules. Malfunction
nodes are similar to any other hypothesis node, except they are not used
to support any higher rules. In other words, malfunction nodes are
associated only with supporting rules, not supported rules.
TABLE IV
______________________________________
OBJECT LEVEL RULES
RULE IF: THEN:
______________________________________
(g) (a) OR (b) Hatch door not locked or car door
not closed
(h) (e) OR (f) Car is not at floor level
(i) (h) AND (d) Car is not at floor level and not
releveling
(j) (i) AND (c) Car is not at floor level, not
releveling, and running
(k) (j) AND (g) Car is not at floor level, not
releveling, running, and car door
not closed or hatch door is not
locked
(l) (i) AND NOT (c)
Car is not at floor level, not
releveling, and not running
______________________________________
Certain information is stored in memory relative to the nodes and rules,
with Tables V, VI and VII illustrating suitable formats for sensor nodes,
hypothesis nodes, and object level rules, respectively.
TABLE V
______________________________________
SENSOR NODE
______________________________________
Name of Sensor
Value of Sensor Reading
Engineering Units of Reading
Time @ Which Reading Was Taken
MB = 1
MD = 0
______________________________________
TABLE VI
______________________________________
HYPOTHESIS NODE FORMAT
______________________________________
Description of Node
CF (H) - Confidence Factor
MB (H) - Measure of Belief
MD (H) - Measure of Disbelief
Rules Using Node as Evidence (Supported)
Rules For Which Node is Hypothesis (Supporting)
Signal Associated With Node
Update Flag - True When MB and MD Completely
Updated
______________________________________
TABLE VII
______________________________________
RULE FORMAT
______________________________________
Names of Evidence Nodes
Evidence as a Boolean Expression (IF:THEN)
Name of Hypothesis Node
CF - Confidence Factor of Evidence
SF(R) - Sufficiency Factor
NF(R) - Necessity Factor
FLAG - True When Rule Fires
Context Under Which Rule Fires
Relative Weights of Multiple Evidence Inputs
For AND Rules
______________________________________
Also, when the procedural flow diagrams are described, certain constants
and determined values will be referred to. In order to aid in quickly
determining what the values generally indicate, they are set forth in
graph form in FIGS. 3A through 3F. FIG. 3A illustrates how piece-wise
linear processing is used to develop a look-up table of sufficiency factor
values SF for each analog sensor. A graph similar to that of FIG. 3A is
determined for each analog sensor. Readings outside a predetermined range
have a sufficiency factor SF of less than one, indicating that if the
value is outside this range, the veracity of the data is suspect. In an
actual system, the graph is in the form of a look-up table in read-only
memory.
The domain expert assigns sufficiency factors SF and necessity factors NF
to each object level rule, indicated in the graphs of FIGS. 3B and 3C,
respectively. The sufficiency factor SF(R), which ranges from -1 to +1,
indicates the belief in the hypothesis of the rule when it is known that
evidence is present. The (R) indicates "rule related". A positive value
indicates belief and a negative value indicates disbelief, with the
magnitude indicating relative degrees of belief or disbelief.
The necessity factor NF, which is in the range of -1 to +1, represents the
necessity of the evidence in proving the hypothesis of the rule true. If
evidence is lacking, or it is contrary, a positive NF(R) indicates
disbelief in the rule's hypothesis, while a negative NF(R) indicates
belief.
The SF and NF values, which are constants, along with the confidence
factors of the evidence, which are program determined, are used to
determine the measure of belief MB and the measure of disbelief MD in the
hypothesis under consideration. These values, shown in FIGS. 3D and 3E,
respectively, range from 0 to 1, with values close to 1 indicating strong
belief, and strong disbelief, respectively, for MB(H) and MD(H), and
values close to zero respectively indicating weak belief and weak
disbelief for MB(H) and MD(H). The (H) indicates "hypothesis related".
Only the MB or the MD for a specific hypothesis is determined and/or
updated per rule, depending upon the update logic shown in FIG. 5, as will
be hereinafter explained.
The confidence factor CF of the hypothesis, which is the same as the
confidence factor of the evidence when the hypothesis is used as evidence
for a supported rule, is equal to the difference between MB and MD, and is
thus a number between -1 and +1. Values around 0 indicate uncertainty,
large positive values indicate strong belief, small positive values
indicate weak belief, large negative values indicate strong disbelief, and
small negative values indicate weak disbelief in the hypothesis of the
rule being considered.
FIG. 4 is a procedural flow | | |
