Completeness and admissibility for general heuristics search algorithms – A theoretical study: Basic concepts and proofs

We propose a formal generalization for various work 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 ρ> and the sub-family (Ã), which includes Nilsson's A or A* and many of their successors such as HPA, B, A(ε)*, A(ε), 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, especially when the state graphs and the evaluation functions are less constrained than ordinarily.