Reference: Smith, D. E. Controlling Backward Inference. March, 1987.
Abstract: Effective control of inference is a critical problem in Aritificial Intelligence. Expert systems make use of powerful domain-dependent control information to eat the combinatorics of inference. However, it is not always feasible or convenient to provide all of the domain-dependent control that may be needed, especially for systems that must handle a wide variety of inference problems, or must function in a changing environment. In this paper, a powerful domain-independent means of controlling inference is developed. The basic appproach is to compute expected cost and probability of success for different backward inference strategies. This information is used to select between inference steps, and to compute the best oreder for processing conjunts. The necessary expected cost and probability calculations rely on simple information about the contents of the problem solver's database, such as the number of facts of a given form, and the domain sizes for the predicates and relations involved.
Notes: 67 pages.