Chargement...
 

Stage planification évolutionnaire multi-objectif 2011

Contexte

Un problème de planification est la donnée
  • d'un espace d'états, ensemble d'objets et de prédicats sur ces objets ;
  • d'un ensemble d'actions, avec, pour chaque action, les prérequis pour son déclenchement (prédicats qui doivent être vrais dans l'état pourant pour que l'action puisse être déclenchée) et les résultats sur l'état courant de son application ;
  • d'un état initial I;
  • d'un but B, constitué d'un ensemble de prédicats.
La résolution d'un tel problème consiste à trouver une séquence d’actions qui, lorsqu’elle est exécutée sur l'état initial, rend vrais l'ensemble des prédicats du but, et minimise un critère donné (nombre d'action dans le cas le plus simple - ou parle alors de problème STRIPS, coût total lorsque chaque action a un coût, ou durée totale, ou makespan lorsque chaque action a une durée, et que des actions peuvent éventuellement être utilisées an parallèle - ou parle alors de planification temporelle).

PDDL est un langage de description de problèmes de planification très répandu, mis au point en vue des compétitions biennales (IPC - International Planning Competition) et permettant de représenter divers types de problèmes de planification. Il existe de nombreux planificateurs dans la communauté AI Planning, mais le problème générique est PSPACE et les planificateurs existant se heurtent sous à l'explosion combinatoire inhérente au problème.

Divide And Evolve (DAE) est une approche évolutionnaire de la résolution de problèmes de planification, qui consiste à proposer une suite de buts intermédiaires B(1), ..., B(n) et à utiliser un planificateur classique pour résoudre successivement les sous-problèmes d'état initial B(i) et de but B(i+1) (avec la convention B(0) = I et B(n+1) = B). La concaténation des plans partiels obtenus pour chaque sous-problème est alors une solution du problème global inital.
L'idée sous-jacente est qu'il doit être possible de trouver une séquence d'états telle que chaque sous-problème soit plus simple que le problème global, et telle que la concaténation des plans partiels soit néanmoins optimale (quel que soit le critère).
La preuve de principe de DAE a été acquise en 2006 [1], et l'algorithme a muri pour devenir compétitif avec les meilleurs planificateurs du domaine en 2010 [2]. Un projet ANR appelé DESCARWIN a démarré en 2010 sur le sujet, coordonné par Pierre Savéant (Thalès), partenaire du projet DAE dés le premier jour, et auquel participe aussi Vincent Vidal (Onera Toulouse), auteur des planificateurs 'classiques' CPT et YAHSP, fortement couplés aux versions existantes de DAE.

But du stage

Dés le papier séminal de 2006 [1], il était apparu que l'approche évolutionnaire DAE permettait l'optimisation multi-objectif. Or de nombreux problèmes réels sont de fait multi-objectif (minimiser la durée totale d'un plan et son coût), et il n'existe aujourd'hui aucun algorithme prenant en compte plusieurs objectifs dans la communauté AI Planning. Le but du stage est donc d'approfondir l'approche proposée dans [1] sur la base de la plate-forme DAE actuelle, et de montrer non plus la faisabilité de l'approche, mais son intérêt et sa généralité. Un des buts intermédiaire sera de choisir (ou de construire) des problèmes de planification multi-objectif de complexité croissante, qui serviront ensuite de base à tout le domaine.


Références

[1] Schoenauer, M. , Savéant, P. and Vidal, V.. Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning. In J. Gottlieb and G. Raidl, eds.: "8th European Conf. on Evolutionary Computation in Combinatorial Optimization (EvoCOP'06)", Springer Verlag, LNCS(3906) : p. 247-260. 2006. http://hal.inria.fr/docs/00/05/41/84/PDF/TGV-paradigm.pdf

[2] Bibai, J. , Savéant, P. , Schoenauer, M. and Vidal, V.. An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning. In Ronen Brafman, Héctor Geffner, Jorg Hoffmann and Henry Kautz, eds.: "ICAPS 2010", AAAI Press : p. 15-25. May 2010. http://hal.archives-ouvertes.fr/docs/00/45/62/92/PDF/icaps10.pdf


Déroulement du stage

  • Le stage aura lieu au sein de l'équipe TAO au LRI, sous la supervision de Marc Schoenauer et de Matthias Brendel (post-doc dans le projet DESCARWIN), en lien étroit avec les équipes de DESCARWIN (Thalès et Onera).
  • Une connaissance préalable de l'évolution artificielle et/ou de la planification sont recommandées, sans être absolument nécessaires.
  • La version actuelle de DAE est écrite en C++, basée sur les versions C de CPT et YAHSP pour la partie planification, et sur la plate-forme EO pour la partie évolutionnaire.
  • Un goût certain pour la programmation en C++ est indispensable (cf EO par exemple). Une connaissance de la programmation parallèle est un plus, vus les coûts-calcul de ce genre d'approche.


Collaborateur(s) de cette page: evomarc .
Page dernièrement modifiée le Lundi 07 février 2011 10:10:14 CET par evomarc.