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.
Type de document :
Communication dans un congrès
Workshop on Monitoring & control of real-time intelligent systems - ECAI'98, 1998, Brighton, UK, 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00108029
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 15:40:15
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50

Identifiants

  • 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, 1998. 〈inria-00108029〉

Partager

Métriques

Consultations de la notice

201