Recent real-time heuristic search algorithms have demonstrated outstanding performance in video-game pathfinding. However, their applications have been thus far limited to that domain. We proceed with the aim of facilitating wider applications of real-time search by fostering a greater understanding of the performance of recent algorithms. We first introduce eight algorithm-independent complexity measures for search spaces and correlate their values with algorithm performance. The complexity measures are statistically shown to be significant predictors of algorithm performance across a set of commercial video-game maps. We then extend this analysis to a wider variety of search spaces in the first application of database-driven real-time search to domains outside of video-game pathfinding. In doing so, we gain insight into algorithm performance and possible enhancement as well as into search space complexity.
Another of the complexity measures we use to characterize search spaces is taken from the research of Mizusawa and Kurihara @cite_24 . They successfully demonstrated a link between search performance in gridworld pathfinding domains and two hardness measures'': initial heuristic error and probability of solution existence. They define initial heuristic error for a search problem as @math where @math is the set of all states on some path connecting the start and goal states. The search spaces used by Mizusawa and Kurihara are generated randomly by making random cells in the gridworld untraversable. The percentage of untraversable cells is called the , @math . Since the obstacles are placed randomly, solutions are not guaranteed to exist for search problems. The entropy @math is used as their measure of likeliness of solution existence. Mizusawa and Kurihara demonstrated that @math , @math , and LRTA* and RTA* solution cost are all maximized at a similar obstacle ratio of approximately $41
@cite_24
2014438206
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.