Hardness measures for gridworld benchmarks and performance analysis of real-time heuristic search algorithms

Gridworlds are one of the most popular settings used in benchmark problems for real-time heuristic search algorithms. However, no comprehensive studies have been published so far on how the difference in the density of randomly positioned obstacles affects the hardness of the problems. This paper presents two measures for characterizing the hardness of gridworld problems parameterized by obstacle ratio, and relates them to the performance of the algorithms. We empirically show that the peak locations of those measures and actual performance degradation of the basic algorithms (RTA* and LRTA*) almost coincide with each other for a wide variety of problem settings. Thus the measures uncover some interesting aspects of the gridworlds.