Comment optimiser A* adaptatif - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Comment optimiser A* adaptatif

Résumé

Efficient search of (quasi-)optimal paths in graphs remains a fundamental task in Artificial Intelligence. Recent works [7, 4, 5, 8] have contributed to a new point of view on this problem whereby heuristics are learned from past solving experiences rather than derived through a static abstraction of the description of the problem. In this paper, we show how to improve this work by better exploiting information from past solving episodes. The experiments reported here confirm the significant reduction in search space achieved by our algorithm. In a second part, we show how to generalize these learning techniques to the case of changing goal states. Extensive experiments and their analysis show that the variations of the goal states must obey strict laws in order for these adaptive A* algorithms to be advantageous.
La recherche efficace d'un chemin (quasi) optimal dans un graphe reste une tâche fondamentale en Intelligence Artificielle. Des travaux récents [7, 4, 5, 8] ont contribué à renouveler l'approche de ce problème en proposant une technique de mise au point d'heuristique par apprentissage et non par une abstraction statique de la description du problème. En nous référant à ces travaux, nous montrons qu'il est possible d'exploiter beaucoup plus précisément l'information apportée par des épisodes de résolution passés. Les expériences confirment la réduction de l'espace de recherche associé. Par ailleurs, nous généralisons ces techniques d'adaptation d'heuristiques au cas de buts changeants. Les expériences et leur analyse montrent que, pour ces techniques, le changement de but doit obéir à des conditions strictes pour que le calcul adaptatif d'heuristique soit rentable.

Mots clés

Fichier principal
Vignette du fichier
Rfia08_ReverseAdaptiveA.pdf (244.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00293136 , version 1 (03-07-2008)

Identifiants

  • HAL Id : inria-00293136 , version 1
  • PRODINRA : 51293

Citer

Lou Fedon, Antoine Cornuéjols. Comment optimiser A* adaptatif. RFIA 2008: 16.Congrès Francophone AFRIF-AFIA. Reconnaissance des Formes et Intelligence Artificielle, Jan 2008, Amiens, France. 8 p. ⟨inria-00293136⟩
290 Consultations
271 Téléchargements

Partager

Gmail Facebook X LinkedIn More