A generalization for heuristically-ordered search: algorithms ρ, results about termination and admissibility

We propose a formal generalization for various works dealing with heuristically-ordered search in state graphs. The formalization and the generalization focus on the notion of path length, on the characteristics of the state graphs, on the procedures that control the choices of the states to be expanded, on the rules that govern the update operations, on the properties of the evaluation functions. Consequently, we present the family of algorithms ρ and the sub-family of algorithms A˜, which includes Nilsson´s A or A* algorithms and many of their descendants such as HPA, B, Aε*, A _ε, C, BF*, B´, IDA*, D, A**, and SDW. We present general theorems, about the termination at a goal and the admissibility or sub-admissibility, that widely extend the corresponding results previously published concerning all the above-mentioned algorithms