Learning Real-Time A* (LRTA*) Search

If a problem is to be solved repeatedly with the same goal state but different initial state then one would like an algorithm that improves its performance over time. Learning Real-Time A* (LRTA*) is such an algorithm. It behaves almost identically to RTA*, except that instead of storing the second-best f value of a node as its new heuristic value, it stores the best value instead. Once one problem instance is solved, the stored heuristic values are saved and become the minimal value for the next problem instance.

While LRTA* is less efficient than RTA* search for solving a single problem instance, if it starts with admissible initial heuristic values over repeated trials, its heuristic values eventually coverage to their exact values. At which point the algorithm returns optimal solutions.