<u>Correction</u> to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"

Abstract

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.