Stratégie évolutionnaire pour la planification temporelle
Thématique : algorithmique/combinatoire
Laboratoires : TAO (CNRS/INRIA/LRI) et Thales Research & Technology/DCS/Platon
Lieu : Orsay (Campus Universitaire), France
Le stage se déroule dans les locaux du LRI (Orsay). Il est co-dirigé par Marc Schoenauer, responsable du projet TAO (INRIA Futurs et PCRI) et Pierre Savéant de Thales TRT.
Présentation générale du domaine
Un problème de planification consiste à trouver une séquence d'actions qui, lorsqu'elle est exécutée, permet d'atteindre un ensemble de buts à partir de la situation initiale. L'environnement est représenté par un ensemble de prédicats sur lequel un ensemble d'actions permet d'agir. La représentation la plus répandue, STRIPS, définit chaque action comme une liste de pré-conditions et une liste d'effets (ajouts ou retraits). La planification temporelle étend la planification classique en associant une durée aux actions et en permettant l'exécution de plusieurs actions en parallèle. Ces problèmes sont fortement combinatoires et de nombreux algorithmes de recherche ont été développés soit dans les espaces d'états soit dans les espaces de plans partiels. Plus récemment, de nouvelles approches ont introduit des mécanismes de propagation de contraintes en s'appuyant sur le graphe de planification. C'est le cas notamment du planificateur CPT développé par Vincent Vidal au CRIL (U. d'Artois) qui a été récompensé par un deuxième prix à la compétition IPC-2004.
Objectif du stage
Une des limites des planificateurs tels que CPT est le passage à l'échelle, tant au niveau mémoire qu'au niveau temps de calcul. Nous avons mis en place un schéma original de collaboration entre un algorithme évolutionnaire et un planificateur exact capable de résoudre de « petits » problèmes, comme CPT par exemple.
Ce schéma peut être également utilisé pour aborder des problèmes multi-objectif, hors de portée des méthodes classiques de planification.
Les approches évolutionnaires ont encore été peu explorées pour résoudre ce type de problème et l'objectif du stage est la mise en ?uvre du schéma d'implantation avec la bibliothèque EO. La maquette sera validée sur les benchmarks utilisés pour les compétitions internationales.
Les algorithmes évolutionnaires sont issus d'une métaphore avec l'évolution darwinienne caractérisée par les principes de sélection naturelle et de variation aveugle du matériel génétique.
Les solutions sont vues comme une population d'individus que l'on va tenter d'améliorer en simulant leur évolution de façon itérative. Une fonction d'évaluation simule leur adaptation à l'environnement et permet d'estimer la qualité de la solution. A chaque itération, une nouvelle génération d'individus est obtenue par l'application d'opérateurs de variation sur une partie d'entre eux : l'opération de croisement consiste à créer des individus en combinant des parties des chromosomes parents. L'opération de mutation, dont le but est de réintroduire de la diversité, consiste simplement à modifier aléatoirement un ou plusieurs des gènes d'un individu donné.
L'équilibre entre la pression sélective et le degré d'altération des opérateurs de variation aboutit à un compromis expérimental entre une exploitation locale des meilleurs individus et une exploration globale de l'espace de recherche.
Les algorithmes évolutionnaires sont des méthodes stochastiques d'optimisation globale qui ont été utilisés pour de nombreux problèmes difficiles.
La bibliothèque EO est un « framework » Open Source écrit en C++, basé sur les templates, et développé conjointement par des chercheurs de l'université de Granada, de l'université d'Amsterdam et de l'INRIA (M. Schoenauer). Elle offre des représentations standards et des opérateurs génériques de sélection/remplacement ainsi qu'un paramétrage de la ligne de commande. Disponible depuis 2000, elle a été utilisée dans de nombreux contextes académiques et industriels.