Browse Prior Art Database

Predictive Method of Controlling Artificial Intelligence Search by Exploration and Ordering

IP.com Disclosure Number: IPCOM000037378D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR [+2]

Abstract

A technique is described whereby a predictive method provides a means of controlling artificial intelligence searching by utilizing exploration and ordering strategies.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 44% of the total text.

Page 1 of 3

Predictive Method of Controlling Artificial Intelligence Search by Exploration and Ordering

A technique is described whereby a predictive method provides a means of controlling artificial intelligence searching by utilizing exploration and ordering strategies.

In prior art, an adaptive search would control the order of search choices based on a history of executions of that search on a variety of data. The concept described herein extends the prior-art approach by providing a means of searching a tree that has never been visited. Predictive methods are used to guess the structure of the search tree and to search the most productive areas.

A search problem that typically arises in artificial intelligence applications and in various other applications, such as engineering design and mathematical optimization, involves the exploration of a tree-structured set of choices called a "search tree". At the highest level of the tree, there is a set of available choices. For each possible choice, there are additional choices, etc. Each subtree of a search tree typically contains some number of candidate solutions. A certain amount of time is required to fully explore the subtree before all candidate solutions contained in it can be discovered. Each candidate solution is subjected to additional testing before it is accepted or rejected as a desired solution.

As a sequence of choices is made, the search will either find an acceptable solution and stop, or it will discover that no such solution exists for this set of choices. In the latter case, the search backtracks and explores a different sequence of choices. If there are no more choices to explore, the search tree is exhausted and the search ends in failure.

Given an instance of a search problem, it is often the case that no a priori information is available regarding: a) the number of candidate solutions that can be

obtained by exploring different subtrees that

correspond to the various search alternatives, and

b) the search effort expended in exploring the

alternatives.

However, these parameters affect the optimal ordering of the alternatives of the search tree. For a degenerate case of a search tree in which the tree is a decision chain (all internal nodes produce either a solution, or one additional choice, and there is no branching of choices), a minimum expected cost policy is known [*]. For each choice in the chain, the policy computes the probability of success, pi, the cost of computation for that choice, ci, and the ratio of these quantities, pi/ci . The optimum search chain orders the choices in non-increasing order according to this ratio. When the cost function is equal to the computation time, the policy produces a search that has the minimum expected time.

In prior art, information has been described as to how to estimate the ratios through repeated execution of a search. By conducting a search a sufficiently large number of times, an adaptive mechanism can order and reorder...