Extraire et utiliser la structure des domaines en planification de tâches
Résumé
Dans la course actuelle au planiicateur de tâches le plus efficace, nous proposons dans cet article une nouvelle approche qui permet de traiter efficacement des probl emes de taille importante. L'algorithme se decompose en deux parties distinctes. Dans un premier temps ShaPer construit, hors-ligne, le graphe d'accessibilit e, compact gr^ ace e a la notion de forme, d'un domaine donné. La capacité e ShaPer à "résister" à l'explosion combinatoire réside en effet dans une gestion efficace des symetries des domaines. Le graphe des formes est ensuite utilisé en-ligne pour repondre à n'importe quel probleme de planiication sur le domaine developpe. Apres avoir decrit en detail cette methode originale, nous la completons par l'utilisation et la synthese automatique de hi erarchies d'abstractions, etendant ainsi les possibilit es de ShaPer. Une premiere implementation a permis d'obtenir des resultats prometteurs sur la majorite des benchmarks, rivalisant avec les meilleurs planiicateurs de la competition AIPS-2000.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...