Skip to Main content Skip to Navigation
Conference papers

New Results about Anytime Heuristic Search

Nicolas Ray 1 Anne Boyer 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Thursday, October 19, 2006 - 3:40:15 PM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM


  • HAL Id : inria-00108029, version 1



Nicolas Ray, Anne Boyer, François Charpillet. New Results about Anytime Heuristic Search. Workshop on Monitoring & control of real-time intelligent systems - ECAI'98, 1998, Brighton, UK. ⟨inria-00108029⟩



Record views