JPH0774996B2 - Qualitative reasoning system - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a qualitative inference system capable of qualitatively analyzing causal relationships such as behaviors of devices and natural phenomena, and particularly to an electronic circuit including an unstable system such as positive feedback. A ambiguity reduction method for qualitative inference systems that can reduce the ambiguity of state transitions when applied to the design support of.

[0002]

2. Description of the Related Art A qualitative reasoning system captures a variable to be analyzed as a current value (or a range of values) and a state of change in the value. The state of change refers to increase, decrease, and constant 3
It is in a state. Then, the behavior of the device or the like is not analyzed in an analog manner, but only the points where the behavior changes are digitally analyzed. Taking the case of heating ice as an example, the point at which the behavior changes is when the temperature is 0 degrees and when the temperature is 100 degrees. In other words, the point where ice turns into water and water turns into steam,
This point is called a boundary mark (landmark). The state of this discretely analyzed point is called an instantaneous state, and the state between a certain instantaneous state and the next instantaneous state is called an interval state. This momentary condition occurs at one or more landmarks. The qualitative reasoning system obtains the instantaneous states, the states of the intervals, and the order of the state transitions.

Now, in the case of heating the ice, the variable having the landmark is only the temperature. Therefore, for example, if the temperature is given as an increasing state from −10 degrees as the initial state, (1) the temperature is −10.
(2) Temperature is from -10 degrees to 0
The state of the section when the temperature is 0 degree, (3) the instantaneous state when the landmark is 0 degree, (4) the state of the section when the temperature is 0 to 100 degrees, (5) the landmark is 100 degree It is required that the momentary state and the state transition at time. However, if there are multiple variables that have landmarks, it cannot be determined from the value alone which variable's landmark arrives first in time. That is, ambiguity will occur.

In the conventional qualitative inference system, this ambiguity is resolved mainly by the generation-test method. This is a method of enumerating the states of all possible variables and obtaining only those combinations whose assumptions are consistent and which satisfy the constraint condition. Possible variable states are when the variable moves from the interval to the moment, when the variable reaches the landmark and when it does not, and when moving from the moment to the interval,
There are cases of staying at landmarks and cases of transition. These are described in, for example, “Qualitative Reasoning; Knowledge Information Processing Series, Annex 1, Kyoritsu Shuppan”.

[0005]

[Problems to be Solved by the Invention]
Generally, it is used as a simulator, and when it is used for simulation, the state of change of a variable is obtained, so the state to transit to next is limited to some extent.
On the other hand, in design support using qualitative inference, the value of an element that satisfies all the constraints of each transition state is obtained by performing simulation without giving the value of the element to be designed. As described above, since the value of the element to be designed is unknown, the change state of the variable cannot be obtained in many cases. As a result, the ambiguity of time further increases, and the processing of the generation-test method for obtaining the next transition state increases. For example, the two transistors of the Schmitt trigger circuit of FIG. 4 have a base-emitter voltage of 0.7V.
Whether to turn on or off is determined by whether or not to exceed. If the state of the change in the voltage between the base and the emitter of the two transistors cannot be obtained in the previous state, both transistors are turned on in the next state or turned off.
I can't decide whether to do it. Therefore, it is necessary to generate four states when the two transistors are turned on and when the transistors are turned off, and test whether or not each state can exist. This process is called an envisioning process.

The four states obtained here are not states that can exist independently of each other, but are states having order. That is, from on / off to off / on, and vice versa through the on / on state of positive feedback.
・ State transition from on to on / off. Off-o
The state of ff cannot exist without satisfying the constraint. However, since the direction of the change in the base-emitter voltage of the transistor cannot be obtained here, the system
Processing is performed assuming the case of transition to each state.
Then, unless the transition to each state is inconsistent, there is a problem that the next state is further inferred and the above-mentioned correct state transition cannot be obtained. Even if the states of changes in the base-emitter voltage of a transistor in three states are obtained, the subsequent state transition of each state is inferred, and the result is inferior to the subsequent state transitions of other states. The ordering is determined only when it is known that the wrapping is performed. For example, it is inferred that each state branched under a certain condition makes the following state transitions.

Off-on->on-on-> on-off on-on-> on-off on-off-> on-off As a result, each state is off-on state, on-on state, on-state. It is understood for the first time that the state transitions to the off state. Therefore, there is a problem that the processing amount increases.

Further, in an unstable system such as the above-mentioned positive feedback, a correct solution cannot be obtained by mathematical formula processing. this is,
This is because it is necessary to consider the time delay in such an unstable system. For example, in a positive feedback system consisting of the following two equations, if y = x + y and y = 10 * e x = 1, then y should continue to increase infinitely,
When mathematically processed, y = -10 * x / 9. For this reason, since it is not possible to test constraints by mathematical processing, instability such as this positive feedback often has to be always established, and there is a problem that wasteful inference is performed. .

An object of the present invention is to eliminate the ambiguity of the state transition of a system including an unstable state such as positive feedback without increasing the processing amount.

[0010]

[Means for Solving the Problem] The object to be analyzed
Structure information file that describes the structure of the
To register at least various relational expressions between
Various relational expressions between the knowledge base and the variables of the above objects
Of the working notes to register the relational expressions necessary for inference
And the objects registered in the working memory.
Based on the relational expression between
The value of the variable or range of values and the change of the above object
A constraint sol that solves the constraint problem to find the state of change of numbers
Bar, above structure information file, above knowledge base, above
Using working memory and constraint solver above,
Qualitatively infer the behavior of the above objects based on the physical quantity
In a qualitative inference system equipped with
Structure of the above object described in the structure information file
And the variables of the above objects registered in the above knowledge base
Based on the given assumptions, the constraint solver
-The above assumptions are analyzed in the
Each object's variable state and each
Instantaneous state for which you want to find the current instantaneous value of an object variable
Internal analysis means, and each obtained by the instantaneous state internal analysis means
From the variable state of the object
If positive feedback is judged, if it is not positive feedback,
According to the relational expressions of the variables of the above objects registered in the
Then, each object obtained by the above-mentioned instantaneous state analysis means
From the current instantaneous value of the variable
Estimate the landmark of the object variable, and use positive feedback.
Then, the direction of change of the variable of each object at the time of positive feedback
Of the above objects registered in the above knowledge base
Calculated by the above-mentioned instantaneous state analysis means according to the relational expression of variables
The value of the variable of each
In a stable state by sequentially transitioning based on the direction of
The first layer for estimating landmarks of object variables
Calculated by the hand mark estimation means and the above-mentioned instantaneous state analysis means.
The current instant value of the variable of each object and the first
Behavior is estimated next by the landmark estimation means of
Constraint value of the landmark value of each object variable
And the above described in the above structure information file.
The structure of the object and the above-mentioned objects registered in the above-mentioned knowledge base.
Based on the relational expressions of the variables of the object,
The current variable of each object stomach in the above the constraint solver
Of each object whose behavior changes from the value at the moment of
The state of the section up to a number of landmarks is analyzed, and each object is analyzed.
In-state analysis means for finding the range of variable values
And the change of the above object registered in the above knowledge base.
The first landmark estimation means according to a numerical relational expression
Of the landmarks estimated in
Included in the range of variable values of each object obtained by analysis means
The second landmark that presumes that a landmark is a landmark
By providing the inference means with the estimation unit,
To achieve.

[0011]

[0012]

The unstable state such as positive feedback exists either alone or only between two stable and stable states. Therefore, when there are unstable and stable states such as positive feedback, it is possible to infer the useless unstable state by checking whether or not the unstable state transits to one of the stable states. All state transitions are required without performing.

Further, when two or more stable states are obtained, not only the stable state in which the unstable state transits,
All the state transitions can be obtained without performing unnecessary inference by investigating stable states that transit to unstable states.

[0014]

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to FIG. In FIG. 1, knowledge of objects and physical laws is registered in a knowledge base 1. An example of a transistor object in an electronic circuit is shown in FIG. Here, it is described that a transistor has variables such as voltage, current, resistance, and current amplification factor (beta) for each terminal of base, collector, and emitter. Further, it is defined that the transistor has two states of on and off under the condition of the base-emitter voltage (vbe @ Tr).
That is, when the base-emitter voltage exceeds 0.7 V, it is on, and when it is 0.7 V or less, it is off. Then, a relational expression between variables that holds in each state is defined. For example, in the on state, the collector current (ir @ c
!! For Tr), a relation (beta @ Tr * ir @ b! Tr) that is obtained by multiplying the base current by the current amplification factor is defined. That is, when the base-emitter voltage exceeds 0.7 V, the transistor is configured by a model of a relational expression between variables in the on state.

Next, a case where the present invention is applied to support the design of the Schmitt trigger circuit shown in FIG. 4 will be described as an example. An example of the description of the structure of the Schmitt trigger circuit is shown in FIG.
This is registered in the structure information file 2 of FIG. Here, the Schmitt trigger circuit has two transistors (T
r1, Tr2) and five resistors (RL1, etc.), and how each is connected is described (connect (...)). Further, the initial condition at the time of behavior analysis (the input voltage vr @ Inp = 0V in FIG. 5) is also registered here. Here, the value of the element (resistor RE) to be designed does not give a concrete value like the resistance @ RE> 0.0 in the figure.

The design specification shown in FIG. 6 is expressed by an IF-THEN type production rule as shown in FIG.
Register in Knowledge Base 1. That is, input voltage <7.4
When V, output voltage (collector voltage of Tr2) = 8.
4 to 8.6V, input voltage = 7.4V, output voltage = 8.4 to 12.0V, input voltage> 7.4V,
The output voltage is 12.0V. By performing a simulation while increasing the input voltage from 0 V under the above conditions, it is possible to obtain the value of the resistor RE that satisfies all the constraints of each transition state.

In the inference unit 3, first, the in-instantaneous-state analysis unit 31 is activated to perform initialization. That is, the initial conditions and the like are fetched from the structure information file 2 and registered in the working memory 4. Next, the structure described in the structure information file 2 is constructed. The structure information file 2 is shown in FIG.
As shown in, the circuit is said to consist of two transistors and five resistors, so knowledge base 1
The objects of 2 transistors and 5 resistors are copied and registered in the working memory 4. Specifically, the relational expression between the variables of the objects of FIG. 3 described in the knowledge base 1 is registered. Here, in the case of a transistor, the base-emitter voltage is often not determined until all the elements of the circuit are registered. Therefore, when registering a transistor, it is not possible to decide whether to register the relational expression between variables in the on state or the relational expression between variables in the off state. In such a case, analysis is performed based on the assumption of four combinations when the base-emitter voltage of each of the transistors Tr1 and Tr2 exceeds 0.7V and when the voltage is 0.7V or less. Assuming that the base-emitter voltage of both transistors Tr1 and Tr2 exceeds 0.7 V, the relational expression between the variables in the on state of both transistors Tr1 and Tr2 is registered in working memory 4. The constraint solver 5 calculates the expression registered in the working memory 4 and calculates the value of the variable,
Alternatively, the range of values and the state of change of variables are obtained. This constraint solver 5 can be realized by, for example, a linear programming method.

In the initial state (input voltage = 0V) of the Schmitt trigger circuit of FIG. 5, analysis can be performed without contradiction only when the transistor Tr1 is off and Tr2 is on. Otherwise, the assumptions are inconsistent and cannot exist. The base-emitter voltage Vbe of the transistor Tr1 is -6.7 V, and the transistor Tr2 is
Vbe of 0.73V is obtained. Further, the value of the resistor RE is limited to the range of 1885-2000. However, the change state of each variable cannot be obtained.

Next, the landmark estimation unit 32 first determines whether the generated circuit is positive feedback or not by the positive feedback determination unit 3 of FIG.
Look at 21. Required state (Tr1 is off, T
Since r2 is on) is not positive feedback, the landmark detection unit 323 obtains the landmark of each variable whose value is changing based on the result of the instantaneous state analysis unit 31. The landmark is obtained from the condition of the object or the condition part of the design specification described above. Here, since the only variable whose state is changing is the input voltage, the input voltage = 7.4V is obtained as the next landmark from the condition part of the design specification of FIG.

After the working memory 4 is cleared, the intra-section state analysis unit 33 sets the value of the current instant state obtained by the instant intra-state analysis unit 31 for each variable as an initial condition.
After the estimated value range of the next landmark is given as a constraint condition, the structure described in the structure information file 2 is constructed in the same manner as in the instantaneous state analysis unit 31. That is, 0.
0V <input voltage <7.4V is registered in the working memory 4 as an initial condition. When the structure is constructed based on the above, similar to the initial state when the input voltage is 0 V, the analysis can be performed without contradiction only when the transistor Tr1 is off and Tr2 is on. At this time, the base-emitter voltage Vbe of the transistor Tr1 is -6.7 V to 0.6.
Vbe of the transistor Tr2 is about 0.703 at 7V.
A range of values for V is calculated. Similarly, the change state of each variable cannot be obtained.

Since the landmark estimating section 34 performs the same processing as the landmark estimating section 32, the input voltage = 7.4V is obtained as the landmark from the condition section of the design specification. Based on this landmark input voltage = 7.4V, the intra-instantaneous-state analysis unit 31 is activated again. Here, only when both the transistors Tr1 and Tr2 are off, the assumptions are inconsistent and cannot exist, and the other three states are consistently established.

Next, the landmark estimation unit 32 determines whether the circuit generated by the positive feedback determination unit 321 is positive feedback. Here, the transistors Tr1 and Tr2 are both o
It is determined that the state of n is positive feedback and the other two states are not positive feedback. From the result of the instantaneous in-state analysis unit 31, the state on
-On is assumed that the base-emitter voltage Vbe of both Tr1 and Tr2 exceeds 0.7V,
It can be seen that Vbe of Tr1 is increasing and Vbe of Tr2 is decreasing. That is, Vbe of Tr1>
0.7, Vbe = <0.7 of Tr2 is obtained by the landmark detection unit 323 as a landmark.

Now, in the state on / off, the V of Tr1 is
be = about 0.703 V, V2 of Tr2 = about −1.0
V, and in the state off · on, Vbe of Tr1 = about 0.67V and Vbe of Tr2 = about 0.703V. Therefore, it can be seen that the above-mentioned landmark of the state on / on can transit to the state on / off as the next state. Further, since it can be seen from the direction of change of each Vbe of the states on and on, the states off and on can be transited to the states on and on. Therefore, these three states are state off and on, and state on.・ On, state on ・ o
It can be determined that the transition is made in the order of ff. As a result, the next section intra-state analysis unit 33 needs to make inferences only for the states on / off, and the ambiguity of the state transition is reduced to 1
It can be reduced to / 3.

The positive feedback process can be realized by the following procedure, for example. In FIG. 2, the positive feedback determination unit 32
In step 1, the processing up to a in the following 1, 2, and 3 is performed, and in the positive feedback processing unit 322, the remaining processing is performed. (1) Generating a causal relationship network A network having equality and variables as nodes is generated under the following conditions. (A) Links are extended from equations to variables or from variables to equations. (B) In the equation consisting of n variables, the links from n-1 variables are the input direction and only one link is the output direction to the variable. (C) Allow multiple input links for variable nodes. (2) Detection of feedback loop (a) The expression of the branch point is detected starting from the external input variable. (B) The loop of the network is detected starting from the branch point. (C) If there is a loop, calculate its open-loop transfer function. (D) If there is no loop, move to the next node and continue the processing from (a). (3) Judgment of feedback type (a) Positive feedback is provided if the absolute value of the open loop transfer function is 1 or more and the loop is positive feedback. (B) With positive feedback, each variable in the loop is simplified as a function of the output variable of the loop starting equation. (C) Further, the change state of each variable is obtained from the obtained equation of each variable. Here, the direction of change of the output variable at the loop origin is determined only by the direction of change of the input variable of the equation at the loop origin traced from the external input variable.

The above processing will be described by taking the case where there are the following three expressions as an example.

E = x + y, y = 10 * e, x = −3 * inp First, a causal relationship network having equations and variables as nodes is generated. FIG. 7 shows one of the networks obtained by this processing. Next, a feedback loop is detected from this causal network. Specifically, first, an external input variable (variable inp of node 1) is used as a starting point, and a branch point expression is detected. The branch point equation is an equation composed of three or more variables, and the equation of the node 4 is detected. The output variable e of this node 4 is traced to see if it reaches the input of node 4. Here, node 6,
It can be seen that the input is again input to the node 4 through the line 7. That is, it can be seen that it is a loop. Once the loop is known, simplify the formula to calculate the open loop transfer function of the loop. That is, the expression is substituted, and the variable (y) at the loop end is obtained as a function of the variable (e) at the loop start point.
Here, the relational expression is simply the equation of node 6 itself.

As a result, the open loop transfer function of the loop is 1
Since 0 is 1 or more, and the variable (y) at the end of the loop is positively input with respect to the input variable (x), it is determined to be positive feedback.

If the feedback is positive, the positive feedback processor 32
In step 2, the direction of change of each variable in the loop is calculated. The variable is y
Only. Here, since the external input variable (Inp) is increasing, the variable (x) is also increasing. Also, node 4
In the equation, the variable (x) and the output variable (e) have the same sign, so the variable (e) also increases. As a result, the variable (y) is also required to increase.

By the above processing, it is possible to determine the positive feedback and obtain the direction of change of each variable during the positive feedback.

[0030]

According to the present invention, the ambiguity of state transitions in an unstable state such as positive feedback can be reduced, so that the amount of inference processing can be reduced and high-speed inference can be realized.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention.

FIG. 2 is a block diagram of an embodiment of a landmark estimation unit of the present invention.

FIG. 3 is a diagram showing a knowledge representation of an object of the present invention by taking a transistor as an example.

FIG. 4 is a circuit diagram of a Schmitt trigger circuit.

FIG. 5 is a diagram showing a description example of a circuit structure, initial values, and the like when the present invention is applied to design support of a Schmitt trigger circuit.

FIG. 6 is a diagram showing design specifications of the Schmitt trigger circuit, with the vertical axis representing an output voltage and the horizontal axis representing an input voltage.

FIG. 7 is a diagram showing a description example of design specifications of a Schmitt trigger circuit.

FIG. 8 is a diagram showing a causal relationship network.

[Explanation of symbols]

1 ... Knowledge base, 2 ... Structural information file, 3 ... Inference section,
4 ... Working memory, 5 ... Constraint solver, 31 ... In-state analysis unit, 32 ... Landmark estimation unit, 33 ... Section analysis unit, 34 ... Landmark estimation unit, 321, ... Positive feedback determination unit, 322 ... Positive feedback processing unit 323 ... Landmark detection unit.

 ─────────────────────────────────────────────────── ─── Continued Front Page (56) References ICOT TECHNICAL REP ORT TR-738 (1992-2)

Claims (1)

[Claims] 1. A structure of an object to be analyzed is described.
Structure information file and various relational expressions between the variables of the above objects.
Inference among the relational expressions between the knowledge base to be registered and the variables of the above objects
A working memory for registering a relation required, the object registered in the working memory
Based on the relational expression between variables,
The value or range of values, and the variable
Constraint solver that solves constraint problems to find the state of optimization
And the structure information file, the knowledge base, and the workin
Based on the physical quantity using the memory and the constraint solver above.
Based on the reasoning method to qualitatively infer the behavior of the above objects
In a qualitative inference system with a stage, the object of the above described in the above structure information file
Structure and of the above objects registered in the above knowledge base
According to the relational expression of variables, the above constraint
Analyze the above assumptions with the louver and contradict each object
State of each object variable so that there is no state
And the moment to find the current moment value of the variable for each object
The in-state analysis means and each of the objects obtained by the instantaneous in-state analysis means
Whether the above object as a whole has positive feedback from the state of variables
If it is judged and it is not positive feedback, it will be registered in the above knowledge base.
The above moment according to the relational expression of the variables of the above objects
The current variable of each object obtained by the in-state analysis means
From the value of the moment, the change of each object whose behavior changes next
Number of landmarks is estimated, and if positive feedback, then positive feedback
The direction of the change of the variable of each object of
In the relational expression of the variable of the above object registered in the base
Therefore, each object obtained by the above-mentioned instantaneous state analysis means
Based on the direction of the above change from the current instantaneous value of the variable
Of each object in a stable state
First landmark estimation for estimating landmarks of variables
Means and variables of each object obtained by the above-mentioned instantaneous state analysis means
Value of the present moment and the first landmark estimating means
Variable of each object whose behavior changes next estimated by
The landmark values of
Structure of the above object described in the report file and the above
Relationship of the variables of the above objects registered in the knowledge base
According to the formula, based on the above constraint conditions,
And then behaves from the current instant value of each object variable
Until the variable landmark of each object that changes
The range of the value of the variable of each object is analyzed by analyzing the state of the interval
Interval state analysis means for obtaining, and the variable of the object registered in the knowledge base
In accordance with the relational expression, the first landmark estimating means
Of the estimated landmarks, the analysis method in the above section state
It is included in the range of the value of the variable of each object calculated in the column
Second landmark estimation that estimates things as landmarks
Reasoning, characterized in that the inference means is provided with
system.