text: 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.
  @cite_32: Many state-of-the-art heuristic planners derive their heuristic function by relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. Looking at a collection of planning benchmarks, we measure topological properties of state spaces with respect to that relaxation. The results suggest that, given the heuristic based on the relaxation, many planning benchmarks are simple in structure. This sheds light on the recent success of heuristic planners employing local search.
  @cite_12: Many state-of-the-art heuristic planners derive their heuristic function by relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The success of such planners on many of the current benchmarks suggests that in those task's state spaces relaxed goal distances yield a heuristic function of high quality. Recent work has revealed empirical evidence confirming this intuition, stating several hypotheses about the local search topology of the current benchmarks, concerning the non-existence of dead ends and of local minima, as well as a limited maximal distance to exits on benches. Investigating a large range of planning domains, we prove that the above hypotheses do in fact hold true for the majority of the current benchmarks. This explains the recent success of heuristic planners. Specifically, it follows that FF's search algorithm, using an idealized heuristic function, is polynomial in (at least) eight commonly used benchmark domains. Our proof methods shed light on what the structural reasons are behind the topological phenomena, giving hints on how these phenomena might be automatically recognizable.
summary: More recently, Hoffman extended a similar study of heuristic topology The terms topography and topology are used interchangeably in the literature when discussing heuristic functions. to general planning @cite_32 @cite_12 . On a set of @math well-established planning benchmarks, he enumerated topological heuristic features and domain properties to sort the benchmarks into a complexity taxonomy. This is similar to our ranking of search spaces based on complexity in Sections and , although Hoffman does not compute empirical correlations to performance. Hoffman concluded that the benchmark taxonomy would shed insight on the levels of success of heuristic search planning in these benchmarks. He also claimed that it could inform subsequent improvement of heuristic functions, allow prediction of planning performance and assist in developing more challenging benchmark sets.