Adaptive mechanisms for execution of sequential decisions

• US 4,752,890 A
• Filed: 07/14/1986
• Issued: 06/21/1988
• Est. Priority Date: 07/14/1986
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Natarajan, Kadathur S., Stone, Harold S.
• Primary Examiner(s): Ruggiero, Joseph
• Application Number:
  US06/885,101
• Time in Patent Office: 708 Days
• Field of Search: 364/513, 364/148, 364/149-151, 364/152, 364/156, 364/200 MS File, 364/300, 364/900 MS File, 364/140, 364/141, 382/14, 382/15, 382/27, 382/1, 382/36-39, 382/48, 382/50, 307/201
• US Class Current: 706/58
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: Y10S 706/908 Electronic or computer, internal or network, circuit
• CPC Class Codes: Y10S 706/922 Computer program preparation

Abstract

An adaptive mechanism is presented in the context of optimization of expert system applications. Both single and multiple processor implementations are disclosed. The mechanism is used to maintain a near-optimal sequence for scanning rule lists in expert systems. For a program containing a sequential-decision chain with many independent or mutually exclusive outcomes with each decision having associated with it some fixed cost and probability, the adaptive mechanism tends to produce the optimal ordering automatically from repeated observations of the execution of the decision chain.

Claims

1. An adaptive mechanism for the optimization of sequential decision making in an artificial intelligence system having N rules in a list to be scanned comprising the steps of:

storing the observed frequencies of firing of different rules in a one-dimensional array FREQ, with FREQ(i), i=l, . . . ,N, containing the number of times each rule has fired;

setting the FREQ values to zero the first time said system is used;

generating a one-dimensional array COST(i), i=1, . . . ,N, containing the accumulated cost of testing if a given rule is applicable;

generating a one-dimensional array ATTMEPTS(i), i=1, . . . ,N, containing the number of times a rule has been tested for firing;

generating a one-dimensional array RATIO(i), i=1, . . . ,N, containing the value ##EQU2## which is the estimate of the ratio of probability of firing to cost per test for each rule;

maintaining a SCANLIST of rules in a sequence ordered by nonincreasing RATIO values;

selecting a rule for firing in order from SCANLIST so that Rule i is tested before Rule j if RATIO(i) >

RATIO(j);

incrementing ATTEMPTS(i) and increasing COST(i) by the cost of testing when RULE(i) is tested for firing; and

increasing FREQ(i) by one when a test for RULE(i) is successful indicating that a rule will fire and updating RATIO(i).

2. The adaptive mechanism as recited in claim 1 further including the step of reordering SCANLIST to maintain the ordering to be in nonincreasing RATIO values.

3. The adaptive mechanism as recited in claim 2 further including the step of saving SCANLIST, FREQ, COST, ATTEMPTS and RATIO for future use by the system.

4. In an artificial intelligence system, a method of optimization of sequential decision making process comprising the steps of:

monitoring quantifiable performance parameters including probability or equivalent relative frequency of occurrence of different outcomes of a search;

developing a prior history of the monitored quantifiable performance parameters including the cost of the search, where cost is any dominant performance measure of the system such as the number of instructions executed, the number of memory references, the number of machine cycles completed, or elapsed time; and

automatically adapting and converging to an optimum average cost of search based on the prior history developed of the monitored quantifiable performance performance parameters.

5. The method of optimization recited in claim 4 wherein the step of automatically adapting and converging to an optimum average cost of search comprises the steps of:

computing ratios of probability or equivalent relative frequency of occurrence to cost for search rules in said sequential decision making process; and

ordering a search list of rules in a nonincreasing order of ratios computed for the rules.

6. The method of reducing the overhead of an adaptive algorithm of a sequential decision making process for an artificial intelligence system wherein quantifiable performance parameters are monitored and measured, the sequential decision making process is automatically adapted and converged to an optimum average search cost comprising the steps of:

varying the frequency of the adaptation process to be relatively more frequent initially and less frequent or not at all after the search process reaches near optimal or optimal behavior; and

controlling the measurement of the quantifiable performance parameters to be very accurate initially during the adaptation process and less accurate or not at all as the adaptation operations are done less frequently or discontinued.