Comment optimiser A∗ adaptatif / Adaptive A∗ : how to best exploit past problem-solving episodes

Lou Fedon (1, 2) , Antoine Cornuéjols (1, 3)

1 LRI - Laboratoire de Recherche en Informatique
2 TAO - Machine Learning and Optimisation
3 MIA-Paris - Mathématiques et Informatique Appliquées

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: Transfer Learning; A

Domaines: Apprentissage [cs.LG]

Lou Fedon, Antoine Cornuéjols. Comment optimiser A∗ adaptatif / Adaptive A∗ : how to best exploit past problem-solving episodes. Reconnaissance des Formes et Intelligence Artificielle, Jan 2008, Amiens, France. ⟨hal-00265006⟩