Bertram Raphael

Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.

Our paper on the use of heuristic information in graph searching defined a path-finding algorithm, A*, and proved that it had two important properties. In the notation of the paper, we proved that if the heuristic function ñ (n) is a lower bound on the true minimal cost from node n to a goal node, then A* is <u>admissible;</u> i.e., it would find a minimal cost path if any path to a goal node existed. Further, we proved that if the heuristic function also satisfied something called the <u>consistency assumption,</u> then A* was <u>optimal;</u> i.e., it expanded no more nodes than any other admissible algorithm A no more informed than A*. These results were summarized in a book by one of us.

New directions in Artificial Intelligence research have led to the need for certain novel features to be embedded in programming languages. This paper gives an overview of the nature of these features, and their implementation in four principal families of AI languages: SAIL; PLANNER/CONNIVER; QLISP/INTERLISP; and POPLER/POP-2. The programming featurcs described include: new data types and accessing mechanisms for stored expressions; more flexible control structures, including multiple processes and backtracking; pattern matching to allow comparison of data item with a template, and extraction of labeled subexpressions; and deductive mechanisms which allow the programming system to carry o u t certain activities including modifying the data base and deciding which subroutines to run next using only constraints and guidelines set up by the programmer.

For the purpose of this paper, a question-answering system is a computer program that has at least the following three characteristics: (1) The ability to accept statements of fact and store them in its memory (2) The ability to search stored information efficiently and to recognize items that are relevant to a particular query (3) The ability to respond appropriately to a question by identifying and presenting the answer if it is present in memory, and by deducing a reasonable logical response from relevant knowledge if the complete answer is not explictly available.