We seek here to determine the exact quantitative dependence of performance of best-first search (i.e., A* algorithm) on the amount of error in the heuristic function's estimates of distance to the goal. Comparative performance measurements for three families of heuristics for the 8-puzzle suggest general conjectures that may also hold for more complex best-first search systems. As an example, the conjectures are applied to the coding pnase of the PSI program synthesis system. A new worst case cost analysis of uniform trees reveals an exceedingly simple general formula relating cost to relative error. The analytic model is realistic enough to permit reasonably accurate performance predictions for an 8-puzzle heuristic. The analytic results also sharpen the distinction between "Knowledge itself" and the "Knowledge engine itself". One has the sense that the men who conceived these high buildings [Gothic cathedrals] were intoxicated by their newfound command of the force in the stone. How else could they have proposed to build vaults of 125 feet and 150 feet at a time when they could not calculate any of the stresses?

By placing various restrictions on the heuristic estimator it is possible to constrain the heuristic search process to fit specific needs. This paper introduces a new restriction upon the heuristic, called the “bandwidth” condition, that enables the ordered search to better cope with time and space difficulties. In particular, the effect of error within the heuristic is considered in detail. Beyond this, the bandwidth condition quite naturally allows for the extension of the heuristic search to MIN/MAX trees. The resulting game playing algorithm affords many desirable practical features not found in minimax based techniques, as well as maintaining the theoretical framework of ordered searches.

An analysis of the efficiency of the alpha-beta algorithm is carried out based on a probabilistic model in which terminal node scores depend on random branch values. Explicit expressions are derived for the expected number of terminal nodes scored for the cases of uniform trees of fanout N and of depths 2 and 3. For trees of depth 2, the expected number is of order O(NHN); for trees of depth 3, the expected number is of order O(N2). An upper bound on the expected number of terminal nodes scored for trees of depth 4 is shown to be no greater than O(N2HN2) and no less than O(N2).

There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortest paths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortest paths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience.

This paper analyzes the complexity of heuristic search algorithms, i.e. algorithms which find the shortest path in a graph by using an estimate to guide the search. In particular, algorithm A∗, due to Hart, Nilsson and Raphael, is shown to require O(2N) steps, in the worst case, for searching a graph with N nodes, if the so called “consistency assumption” does not hold for the estimate. Furthermore, a new search algorithm is presented which runs in O(N2) steps in the worst case and which never requires more steps than A∗.

The alpha-beta technique for searching game trees is analyzed, in an attempt to provide some insight into its behavior. The first portion of this paper is an expository presentation of the method together with a proof of its correctness and a historical discussion. The alpha-beta procedure is shown to be optimal in a certain sense, and bounds are obtained for its running time with various kinds of random data.

A computer program has been written that successfully discovers syntheses for complex organic chemical moleculeB. The definition of the search space and strategies for heuristic search are described in this paper. It is not growing like a tree... ...In small proportions we just beauties see; - Ben Jonson. Introduction The design of application of artificial intelligence to a scientific task such as Organic Chemical Synthesis was the topic of a Doctoral Thesis completed in the summer of 197I. Chemical synthesis in practice involves i) the choice of molecule to be synthesized; ii) the formulation and specification of a plan for synthesis (involving a valid reaction pathway leading from commercial or readily available compounds to the target compounds with consideration of feasibility regarding the purposes of synthesis); iii) the selection of specific individual steps of reaction and their temporal ordering for execution; iv) the experimental execution of the synthesis and v) the redesign of syntheses, if necessary, depending upon the experimental results. In contrast to the physical synthesis of the molecule, the activity in ii) above can be termed the'formal synthesis'. This development of the specification of syntheses involves no laboratory technique and is carried out mainly on paper and in the minds of chemists (and now within a computer's memory!). Importance and Difficulty of Chemical Synthesis The importance of chemical synthesis is undeniable and there is emphatic testimony to the high regard held by scientists for synthesis chemists.

This framework is in large part due to various res trictions imposed upon the heuristic that guides the search and the resulting effect on the search algorithm itself. In order to discuss some of these restrictions it is necessary to introduce the following notation. For a node n of a tree or graph, the following functions are defined as part of the problem.

Unfortunately, by using such heuristics, it is not possible to solve any reasonably complex set of problems in a reasonably complex domain. Regardless of how good such heuristics are at directing search, attempts to traverse a complex problem space can be caught in a combinatorial quagmire. This paper presents an approach to augmenting the power of the heuristic search process. The essence of this approach is to utilize a means for discriminating between important information and details in the problem space. By planning in a hierarchy of abstraction spaces in which successive levels of detail are introduced, significant increases in problem-solving power have been achieved. Section II sketches the hierarchical planning approach and gives motivation for its use. Sections III and IV describe the definition and use of abstraction spaces by ABSTRIPS (Abstraction-Based STRIPS), a modification of the STRIPS problem-solving system that incorporates this approach. Section V describes the performance of the system.

Additive AND/OR graphs are defined as AND/ /ORgraphs without circuits, which can be considered as folded AND/OR trees; i.e. the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once. Additive AND/OR graphs are naturally obtained by reinterpreting the dynamic programming method in the light of the problem-reduction approach. An example of this reduction is given. A top-down and a bottom-up method are proposed for searching additive AND/OR graphs. These methods are, respectively, extensions of the "arrow" method proposed by Nilsson for searching AND/OR trees and Dijkstra's algorithm for finding the shortest path. A proof is given that the two methods find an optimal solution whenever a solution exists. 1) introduction In the literature on artificial intelligence, AND/OR trees have proved to be a good formalism for representing the problem-reduction approach to problem solving. Usually, the search is for any solution tree, but in a paper by Nilsson the problem is presented of finding the best solution tree, where arcs have a given cost, and the cost of a tree is simply the sum of the costs of the arcs. Nilsson gives there an algorithm which assumes available, for each node, an estimate of the cost of the "optimal solution tree rooted at that node.