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_15: Fast-forward (FF) was the most successful automatic planner in the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS '00) planning systems competition. Like the well-known hsp system, FF relies on forward search in the state space, guided by a heuristic that estimates goal distances by ignoring delete lists. It differs from HSP in a number of important details. This article describes the algorithmic techniques used in FF in comparison to hsp and evaluates their benefits in terms of run-time and solution-length behavior.
  @cite_14: In the AIPS98 Planning Contest, the HSP planner showed that heuristic search planners can be competitive with state-of-the-art Graphplan and SAT planners. Heuristic search planners like HSP transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24-Puzzle and Rubik’s Cube in that they use a general declarative language for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are based on a simple and general heuristic that assumes that action preconditions are independent. The heuristic is then used in the context of best-first and hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers.  2001 Elsevier Science B.V. All rights reserved.
  @cite_33: The purpose of this paper is twofold: on one hand, modelling the hill-climbing heuristic search algorithm as a stochastic process serves for deriving interesting properties about its expected performance; on the other hand, the probability that a hill-climbing search algorithm ever fails when approaching the target node (i.e., it does not find a descendant with a heuristic value strictly lower than the current one) can be considered as a pesimistic measure of the accuracy of the heuristic function guiding it. Thus, in this work, it is suggested to model heuristic hill-climbing search algorithms with Markov chains in order to fulfill these goals. Empirical results obtained in various sizes of the (n,m)-Puzzle domain prove that this model leads to very accurate predictions.
summary: Previous work has been conducted to predict the performance of simpler real-time heuristic search algorithms. Citing important applications in planning (e.g., as part of the Heuristic Search Planner @cite_14 and the Fast-Forward Planner @cite_15 ), L o pez sought to model the efficiency of heuristic hill-climbing by modelling the algorithm as a Markov process @cite_33 . Using several sizes of the sliding tile puzzle, the model could reasonably predict the likelihood that a hill-climbing agent reaches a target state in a number of moves equal to the initial heuristic value. L o pez stated that this model is useful not only as a predictor of simple real-time search performance, but as a gauge of heuristic accuracy.