US6144953A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Time-constrained inference strategy for real-time expert systems
Assignee: Hanger Solutions LLC
•
Filing: 1986-05-20
•
Granted: 2000-11-07
•
Expires: 2006-05-20
Abstract
Abstract Expert systems often must be operated under constraints of time or other computer resources. In the past, this has created significant problems since conventional "depth-first" systems will often not be able to arrive at a satisfactory response, or even any response at all, within the limitations of the constraint. Accordingly, an expert system control process and an associated inference network are provided which assign merit values to each inference node (i.e. each proposition) of the inference network. These merit values reflect the processing cost of expanding a node to calculate a likelihood value for the proposition that the node represents. The merit values are then used in the control process to determine which of the nodes will be processed first to calculate likelihood values. In this way, a "best-first" control process is provided which takes account of the actual processing cost of each node in the inference network to establishing which nodes are, in fact, "best" to evaluate first. The processing cost can reflect real-time, processor time or other resources of the computer system which will be consumed in processing respective nodes.
Inventors
- 👤 Mark E. Sorrells
- 👤 John M. Dixon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 02:27
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/04; G06N5/01
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
153 words
A control process for an expert system implemented with a computer system, wherein said expert system includes an inference network comprising a plurality of inference nodes each representing a predetermined proposition, said inference nodes being respectively coupled to one another in accordance with a plurality of predetermined inference rules to form said inference network, wherein each of said inference nodes is assigned a merit value based on a processing cost for calculating with said computer system a likelihood value of the likelihood of the proposition which said inference node represents, said control process comprising: selecting nodes of said inference network for processing to determine said likelihood values for said nodes in accordance with the respective merit values of said nodes so that those nodes having greater merit values will be processed before nodes having smaller merit values; and limiting the total number of nodes selected for processing in accordance with a predetermined constraint.
Claim 2
Dependent Claim
153 words
A control process for an expert system implemented with a computer system, wherein said expert system includes an inference network comprising a plurality of inference nodes each representing a predetermined proposition, said inference nodes being respectively coupled to one another in accordance with a plurality of predetermined inference rules to form said inference network, wherein each of said inference nodes is assigned a merit value based on a processing cost for calculating with said computer system a likelihood value of the likelihood of the proposition which said inference node represents, said control process comprising: selecting nodes of said inference network for processing to determine said likelihood values for said nodes in accordance with the respective merit values of said nodes so that those nodes having greater merit values will be processed before nodes having smaller merit values; and limiting the total number of nodes selected for processing in accordance with a predetermined constraint.
Claim 3
Dependent Claim
42 words
A control process according to claim 1, wherein said predetermined constraint is a real time constraint so that the total number of nodes selected for processing will be limited to the number of nodes which can be processed within a predetermined real-time.
Claim 4
Dependent Claim
25 words
A control process according to claim 2, wherein said processing cost represents a real-time value required for said computer system to calculate said likelihood value.
Claim 5
Dependent Claim
41 words
A control process according to claim 1, wherein said predetermined constraint is a processor time constraint so that the total number of nodes selected will be limited to the number of nodes which can be processed within a predetermined processor time.
Claim 6
Dependent Claim
25 words
A control process according to claim 4, wherein said processing cost represents a processor time required by said computer system to calculate said likelihood value.
Claim 7
Dependent Claim
25 words
A control process according to claim 1, wherein said predetermined constraint is a predetermined limit on the total number of nodes which can be processed.
Claim 8
Dependent Claim
81 words
A control process according to claim 1, further comprising the steps of assigning each of said nodes an initial estimate default likelihood value to be used in determining initial merit values for each node and recalculating merit values for a predetermined node and all nodes whose likelihood values will be effected by changes in the likelihood value of the predetermined node whenever an updated likelihood value is calculated for said predetermined node based on input data provided to the computer system.
Claim 9
Dependent Claim
262 words
A control process for an expert system implemented with a computer system, wherein said expert system includes an inference network having a plurality of inference nodes each representing a predetermined proposition, said inference nodes being respectively coupled to one another in accordance with a plurality of predetermined inference rules to form a network having predetermined top nodes representing basic propositions and antecedent nodes which will affect the calculation of a likelihood value of the likelihood of the basic proposition of the top nodes to which they are connected, wherein each of said antecedent inference nodes is assigned a merit value which represents a ratio between (1) the amount of an effect which a change of a likelihood value representing a likelihood of said antecedent inference node will have on the likelihood value of a top node which it is connected to and (2) a processing cost for calculating said likelihood value for said antecedent node with said computer system, and wherein each of said top nodes is assigned a merit value based on a processing cost for calculating the likelihood value for said top node with said computer system, said control process comprising: selecting antecedent nodes and top nodes of said inference network for processing to determine said likelihood values for said antecedent and top nodes in accordance with the respective merit values of said nodes so that those nodes having greater merit values will be processed before nodes having smaller merit values; and limiting the total number of antecedent and top nodes selected for processing in accordance with a predetermined constraint.
Claim 10
Dependent Claim
262 words
A control process for an expert system implemented with a computer system, wherein said expert system includes an inference network having a plurality of inference nodes each representing a predetermined proposition, said inference nodes being respectively coupled to one another in accordance with a plurality of predetermined inference rules to form a network having predetermined top nodes representing basic propositions and antecedent nodes which will affect the calculation of a likelihood value of the likelihood of the basic proposition of the top nodes to which they are connected, wherein each of said antecedent inference nodes is assigned a merit value which represents a ratio between (1) the amount of an effect which a change of a likelihood value representing a likelihood of said antecedent inference node will have on the likelihood value of a top node which it is connected to and (2) a processing cost for calculating said likelihood value for said antecedent node with said computer system, and wherein each of said top nodes is assigned a merit value based on a processing cost for calculating the likelihood value for said top node with said computer system, said control process comprising: selecting antecedent nodes and top nodes of said inference network for processing to determine said likelihood values for said antecedent and top nodes in accordance with the respective merit values of said nodes so that those nodes having greater merit values will be processed before nodes having smaller merit values; and limiting the total number of antecedent and top nodes selected for processing in accordance with a predetermined constraint.
Claim 11
Dependent Claim
42 words
A control process according to claim 8, wherein said predetermined constraint is a real time constraint so that the total number of nodes selected for processing will be limited to the number of nodes which can be processed within a predetermined real-time.
Claim 12
Dependent Claim
25 words
A control process according to claim 9, wherein said processing cost represents a real-time value required for said computer system to calculate said likelihood value.
Claim 13
Dependent Claim
80 words
A control process according to 10, further comprising the steps of assigning each of said nodes an initial estimate default likelihood value to be used in determining initial merit values for each node and recalculating merit values for a predetermined node and all nodes whose likelihood values will be effected by changes in the likelihood value of the predetermined node whenever an updated likelihood value is calculated for said predetermined node based on input data provided to the computer system.
Claim 14
Dependent Claim
80 words
A control process according to 10, further comprising the steps of assigning each of said nodes an initial estimate default likelihood value to be used in determining initial merit values for each node and recalculating merit values for a predetermined node and all nodes whose likelihood values will be effected by changes in the likelihood value of the predetermined node whenever an updated likelihood value is calculated for said predetermined node based on input data provided to the computer system.
Claim 15
Dependent Claim
41 words
A control process according to claim 8, wherein said predetermined constraint is a processor time constraint so that the total number of nodes selected will be limited to the number of nodes which can be processed within a predetermined processor time.
Claim 16
Dependent Claim
25 words
A control process according to claim 12, wherein said processing cost represents a processor time required by said computer system to calculate said likelihood value.
Claim 17
Dependent Claim
25 words
A control process according to claim 8, wherein said predetermined constraint is a predetermined limit on the total number of nodes which can be processed.
Claim 18
Dependent Claim
81 words
A control process according to claim 8, further comprising the steps of assigning each of said nodes an initial estimate default likelihood value to be used in determining initial merit values for each node and recalculating merit values for a predetermined node and all nodes whose likelihood values will be effected by changes in the likelihood value of the predetermined node whenever an updated likelihood value is calculated for said predetermined node based on input data provided to the computer system.
References Cited (Backward Citations)
US4543630A
Cited
US4591983A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-07 | 2004-05-08 | 2004-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-07 | 2008-05-08 | 2008-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-07 | 2012-05-08 | 2012-11-07 | $7700.00 | Window Closed / Lapsed |