A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Peter E. Hart, Nils J. Nilsson, 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.
- Compared the A* algorithm to Temporal Difference learning. TD Lambda and the Heuristic function in A* can both be used to change the behaviour of the algorithm.
- Relying on the triangle inequality reduces the number of situations where A* is useful. However, it is very flexible in its ability to solve many common problems, making it an important algorithm regardless of limitations.
- The discussion of the existing and competing algorithms did not feel very complete. There was no runtime or complexity analysis since the heuristic function would change it. It would have been nice to see the performance benefits over other algorithms, but it would have made the paper very long.
- The reasoning and proofs were exceptionally clear until it got bogged down with some not so clear set theory.