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∗.

Also found at aminer.orgProc. IJCAI 77 VOL 1 MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MASSACHUSETTS, USA AUGUST 22 - 25 , 1977, pp.434-441.

Proc. IJCAI 77 VOL 1 MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MASSACHUSETTS, USA AUGUST 22 - 25 , 1977, pp.933-939

"We define the concept of meta-level Knowledge, and illustrate it by briefly reviewing four examples that have been described in detail elsewhere. The examples include applications of the idea to tasks such as transfer of expertise from a domain expert to a program, and the maintenance and use of large Knowledge bases. We explore common themes that arise from these examples, and examine broader implications of the idea, in particular its impact on the design and construction of large programs."IJCAI 5, 920-927

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.

Artificial Intelligence 6:361-371

IJCAI S, 23-29.

A problem domain can be represented as a hierarchy of abstraction spaces in which successively finer levels of detail are introduced. The problem solver ABSTRIPS, a modification of STRIPS, can define an abstraction space hierarchy from the STRIPS representation of a problem domain, and it can utilize the hierarchy in solving problems. Examples of the system's performance are presented that demonstrate the significant increases in problem-solving power that this approach provides. Then some further Implications of the hierarchical planning approach are explored.Later journal article in Artificial Intelligence 5:115-135 (1974). Available for a fee. In IJCAI-73: THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 20-23 August 1973, Stanford University Stanford, California.

The design of application of artificia l intelli­gence 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; i i) 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 exper­imental execution of the synthesis and v) the redesign of syntheses, if necessary, depending upon the exper­imental results. In IJCAI-73: THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 20-23 August 1973, Stanford University Stanford, California.