Completeness and admissibility for general heuristic search algorithms - A theoretical study: Basic concepts and proofs
We propose a formal generalization for various works dealing with Heuristic Search in State Graphs. This generalization focuses on the properties of the evaluation functions, on the characteristics of the state graphs, on the notion of path length, on the procedures that control the node expansions, on the rules that govern the update operations. Consequently, we present the algorithm family rho and the sub-family (A) over tilde, which include Nilsson's A or A* and many of their successors such as HPA, B, A(epsilon)*, A(epsilon), C, BF*, B', IDA*, D, A**, SDW. We prove general theorems about the completeness and the sub-admissibility that widely extend the previous results and provide a theoretical support for using diverse kinds of Heuristic Search algorithms in enlarged contexts, specially when the state graphs and the evaluation functions are less constrained than ordinarily.
admissibility heuristic search ordered search algorithms a and a*