Rapid Random Restarts for Real-Time Heuristic Search

In constraint satisfaction, researchers have recently begun to study "rapid random restarts" systematically. "Rapid random restart" just means that a randomized search procedure is interrupted when it has run a given short amount of time, and started from scratch, see:

Randomization in Backtrack Search: Exploiting Heavy-Tailed Profiles for Solving Hard Scheduling Problems. Carla P. Gomes, Bart Selman, Ken McAloon, and Carol Tret. Proc. AIPS-98, Pittsburgh, PA, June 1998.

In this project, you will explore whether the same is true for real-time heuristic search. Get an implementation of Learning-Real Time A* or a planner that uses Learning-Real Time A*. Here is a paper that describes a planner and how to get the code:

A fast and robust action selection mechanism for planning B. Bonet, G. Loerincs, H. Geffner. Proceedings AAAI-97. Provide, RI, 7/97.

Alternatively, I can provide you with a quick-and-dirty implementation of Learning-Real Time A*.

Choose a search problem and test whether you can use rapid random restarts to improve the performance of the algorithm. (Note that you cannot restart the algorithm in a randomly chosen start state since you want to find a path from the given start state to the goal. However, you can break ties randomly to randomize the algorithm.) Test whether you can improve its performance further if the decision whether to restart is not just based on the run-time of the algorithm but also on other features.