HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal.inria.fr/inria-00108029
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 3:40:15 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:17 PM

Identifiers

  • HAL Id : inria-00108029, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

85