Learning Real-Time A* (LRTA*) Search

If a problem is to be solved repeatedly with the same goal state but different intial 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 stroring 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 efficienct than RTA* for solving a sinle problem instance, if it starts with admissible initial heuristic values over repeated trials, its heuristic values eventually coverge to their exact values. At which point the algorithm returns optimal solutions.

BACK: Interleaving Search