ARA* - Anytime A* with Provable Bounds on Sub-Optimality

Optimal search is often infeasible for real world problems as time limitations are abundant, alternatively we may choose to find the optimal solution within a given time frame. This paper proposes ARA* (Anytime repairing A*) which runs A* with inflated heuristics (actual heuristic values which are multiplied by an inflation factor 𝜀 > 1) in succession with decreasing inflation to guarantee sub optimal solution.

Original paper (2003)