[inria-00293136, v1] Comment optimiser A* adaptatif

Manuscrit auteur, publié dans "Reconnaissance des Formes et Intelligence Artificielle, Amiens : France (2008)"∗CommentoptimiserA adaptatif∗AdaptiveA :howtobestexploitpastproblem solvingepisodes1 2 2LouFedon , AntoineCornuéjols1 ÉquipeInférenceetApprentissage,LaboratoiredeRechercheenInformatique(LRI)Bâtiment490,UniversitéParis Sud,91405-OrsayCedex(France)lou.fedon@lri.fr2 UMRAgroParisTech/INRA51816,rueClaudeBernard,F 75231ParisCedex05(France)antoine.cornuejols@agroparistech.frhttp ://www.lri.fr/∼antoineRésumé in search space achieved by our algorithm.In a second part, we show how to generalize these lear-La recherche efficace d’un chemin (quasi) optimal dans unning techniques to the case of changing goal states. Ex graphe reste une tâche fondamentale en Intelligence Ar-tensiveexperimentsandtheiranalysisshowthatthevaria tificielle. Des travaux récents [7, 4, 5, 8] ont contribué àtions of the goal states must obey strict laws in order forrenouveler l’approche de ce problème en proposant une∗these adaptive A algorithms to be advantageous.techniquedemiseaupointd’heuristiqueparapprentissageet non par une abstraction statique de la description du Keywordsproblème. En nous référant à ces travaux, nous montrons ∗Heuristicsearch,Graphs,AdaptiveA ,Learning.qu’il est possible d’exploiter beaucoup plus précisémentl’informationapportéepardesépisodesderésolutionpas 1 Introductionsés.Lesexpériencesconfirmentlaréductiondel’espacederecherche associé. ...