Planification évolutionnaire – DESCARWIN

DESCARWIN, le mariage de Descartes (pour la stratégie Divide-and-Conquer – diviser pour mieux régner) et Darwin (pour l'Evolution Artificielle), appartient à l'axe “Design et Optimisation” dans la catégorie recherche fondamentale. Cette combinaison constitue une avancée prometteuse pour la résolution de problèmes de planification difficiles et possède un fort potentiel économique sur le long terme. La planification, en tant que recherche d'une séquence optimale d'actions pour atteindre un ensemble de buts, est omniprésente dans les domaines impliquant des systèmes critiques : sécurité (gestion de crise, surveillance), gestion du trafic aérien, missions spatiales, industrie (gestion de chaînes de production, logistique), transport (optimisation du trafic). Ce type de problèmes est généralement difficile à modéliser et résoudre à cause d'une part de la complexité et de l'interdépendance des contraintes, et d'autre part de la difficulté à trouver les meilleures solutions quand de multiples objectifs entrent en conflits. Depuis plus de 20 ans, la recherche en Planification et Ordonnancement automatiques a produit des modèles mathématiques, des langages de représentation ainsi que des algorithmes pour les résoudre. Néanmoins, l’accent est généralement porté plus sur la rapidité de l’algorithme plutôt que sur la qualité de la solution qui, de surcroît, est mono-objectif. Le point de départ du projet DESCARWIN est une méthode stochastique pour la décomposition en sous-problèmes d'un problème de planification,appelée Divide-and-Evolve, qui a été introduite récemment et se concentre sur la qualité des plans produits. Le principe de base est de décomposer l'espace des états du problème à résoudre au moyen de l'évolution artificielle : les solutions candidates sont des séquences de buts intermédiaires qui définissent des sous-problèmes que l'on espère plus faciles à résoudre que le problème global. Le champ d'application de Divide-and-Evolve est une restriction de la planification temporelle telle que définie dans PDDL2.1 (langage standardisé de représentation des problèmes de planification, largement adopté par la communauté), où les actions ont une durée, peuvent s'exécuter de manière concurrente, et où la qualité du plan s'exprime parrapport à la durée totale d'exécution du plan. Les objectifs de DESCARWIN sont : 1. améliorer et valider la méthode Divide-and-Evolve par rapport aux planificateurs les plus performants de l'état de l'art, 2. étendre le champ d'application de Divide-and-Evolve par des éléments requis par les problèmes de planification issus du monde réel. Le premier objectif soulève plusieurs points fondamentaux comme (1) la stratégie de décomposition, (2) le réglage des paramètres de l'algorithme et (3) l'indépendance par rapport au planificateur interne. L'extension du champ d'application porte sur : (a) l'aspect multi-objectifs : dans beaucoup de problèmes de planification issus du monde réel, la qualité du plan s'exprime avec plusieurs objectifs conflictuels pour lesquels il n'existe pas d'agrégation naturelle, (b) la concurrence obligatoire: la concurrence peut être obligatoire soit à cause des interactions fonctionnelles entre les activités du domaine d'application, soit à cause d'une échéance imposée forçant la compression temporelle des activités, (c) les caractéristiques introduites par PDDL3: elles expriment des préférences sur la structure du plan ou sur les buts à atteindre, ce qui est bienvenu lorsque l’ensemble des solutions est trop important. Il est souhaitable, par ailleurs, lorsque tous les buts ne peuvent être atteints, de pouvoir négliger une partie d’entre eux. La validation sera conduite d’une part en se confrontant aux meilleurs planificateurs sur les benchmarks utilisés par la compétition internationale de planification, et d’autre part, sur une étude de cas issue de la gestion de crise qui exploitera les nouvelles capacités.