Search-Space Characterization for Real-time Heuristic Search
  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.
