Search-Space Characterization for Real-time Heuristic Search
This work addresses the challenge of facilitating wider applications of real-time search algorithms beyond video-game pathfinding, though it is incremental in extending existing methods to new data.
The paper tackled the problem of understanding and predicting the performance of real-time heuristic search algorithms across different domains by introducing eight algorithm-independent complexity measures, which were statistically shown to be significant predictors of performance on video-game maps and extended to non-gaming domains.
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.