New Results about Anytime Heuristic Search
Résumé
We describe in this paper an extension of anytime heuristic search based on the A* algorithm as proposed by Hansen, Zilberstein and Danilschenko [97]. We use the same basic idea, i.e. to make a trade off between search time and solution quality, by implementing a non admissible function : f(n)=(1-w) g(n) + w h(n), with w>= 0.5. Contrary to the quoted authors, we propose a method that at runtime tunes w continuously. A new value of w is computed each time a solution (but non optimal) is determined such that the currently available solution can be improved as fast and by as much as possible. Each value of w is computed from a linear regression rule determined during a learning phase. We illustrate our approach on randomly generated examples. Obtained results show clearly the improvement of our approach over the previous ones.