Site Web de GILLES SIMONIN
Recherche
In the Constraints and Optimisation research group we are concerned with decision-making and problem-solving in all organisations and enterprises within the private and public sectors. We term this the study of decision analytics. In the research strand we consider both predictive and prescriptive approaches to decision analytics. The primary objective of decision analytics is to make better decisions by utilising data. In some sense, the ultimate purpose of all data analytics activity is to inform decision making. This research strand brings together a number of strands and WPs from the fundamental science level, such as scalable and robust optimisation, Bayesian methods, and machine learning. We will develop leading-edge decision analytics technology capable of supporting decision making in settings that are characterised by: independent and strategically self-interested agents; concerns about the impact of decisions on communities, societies and groups; highly stochastic and online real-time settings; and open-ness and constant change.
Le sujet de mon post-doctorat porte sur des problèmes d'ordonnancement d'expérimentations scientifiques et de transfert de données pour la sonde spatiale Rosetta/Philae. Ce travail est une collaboration entre le LAAS de Toulouse et le Centre National d'études Spatiales (CNES). Rosetta est une mission de l'agence spatiale européenne (ESA) dont le but est de réaliser le premier atterrissage sur une comète (67P / Churyumov - Gerasimenko)
Le projet consiste à développer des algorithmes permettant d'ordonnancer les différentes de l'atterrisseur (Philae) durant les trois phases. D'abord la phase de séparation, de descente et d'atterrissage (SDL), où l'atterrisseur va se séparer du module orbital et va atterrir à la surface de la comète. Puis, durant la phase des premières séquences scientifiques (FSS), les principaux instruments scientifiques vont utiliser les batteries embarquées comme source d'énergie. Cette phase devrait durer trois quatre jours, dépendant de la charge restante des batteries et de la qualité de l'ordonnancement. Finalement, durant la troisième longue phase scientifique, les activités scientifiques vont passer à un rythme beaucoup plus lent, utilisant les panneaux solaires propre à l'atterrisseur permettant de remplir partiellement les batteries.
Les expériences de la deuxième et troisième phase, et certaines de la première, nécessitent d'être ordonnancé tout en satisfaisant un certain nombre de contraintes impliquant l'utilisation simultanée de l'énergie (batteries), et de la mémoire principale ainsi que celles de chaque instrument. Une autre contrainte importante concerne les transferts de données et la notion de "visibilité", qui est la disponibilité à l'orbiteur à agir en tant que relais pour transmettre les données vers la Terre, qui dépend de son orbite et de la longueur d'un jour cométaire. Un outil développé utilisant Ilog Scheduler et Solver (MOST) est utilisé pour modéliser ce problème et de générer des planifications faisables. Chaque instrument, sous-système et expérience a été modélisé avec cette librairie, et c'est donc possible pour vérifier des solutions avec un grand degré de confiance de faisabilité. Cependant, la complexité du problème, en particulier durant la phase FSS, fait qu'il est difficile de trouver des solutions dans un délais raisonnable.
Mon travail consiste à explorer les différentes façons d'obtenir de meilleures solutions rapidement, et de développer des prototypes pour évaluer le gain. Cela pourrait être fait en améliorant le modèle, les algorithmes de propagation et les stratégies de recherche actuellement utilisés, ou en développant de nouveaux modèles dont les solutions peuvent être intégrés à MOST.
Les travaux effectués durant ma thèse portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches.
La première partie de mes travaux s'intéressait à la modélisation du problème, aux différentes tâches utilisées et aux contraintes qui leur sont appliquées. L'impact de la contrainte de compatibilité a été mis en avant, m'amenant à utiliser la théorie des graphes pour analyser les problèmes. Dans une seconde partie, j'ai donné la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Plusieurs preuves de complexité ont été données pour certains problèmes se trouvant à la limite entre la polynomialité et la NP-complétude selon les valeurs des paramètres. Pour chaque problème NP-complet, des algorithmes d'approximation en temps polynomial ont été proposés, ainsi que l'analyse des bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres dans ma thèse prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie j'ai cherchais à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème.
J'ai abordé le problème de la torpille d'un point de vue plus pratique en cherchant à réaliser une étude stochastique. Le modèle était le suivant : Les tâches d'acquisition et de traitement sont envoyées à la torpille à la volée suivant une loi de distribution. Les paquets de tâches reçus doivent être traité dans un laps de temps donné avant d'être re-exécuté de manière périodique. Lorsque un paquet de tâches n'est pas exécuté dans les temps, la torpille retire le paquet et continue à ordonnancer les autres. Le travail a été de modéliser le problème puis de proposer différentes règles de priorité à suivre pour obtenir différents ordonnancements. Des simulations ont été réalisées, et un papier a été publié à la ROADEF 2009.
J'ai également abordé l'étude en régime permanent portant sur le problème de la torpille. Le premier travail a été de modéliser le problème de la torpille, prenant en compte la structure particulière des tâches d'acquisition et la préemtivité des tâches de traitement. Ces travaux sont en collaboration avec Jean-François Pineau qui fait un postdoc au lirmm.
Enfin, certains résultats en théorie des graphes, sur le recouvrement de sommets par des chaînes disjointes de longueur inférieure à 2, ont abouti sur une collaboration avec Jean Daligault et Stéphan Thomassé sur les problèmes de star packing et les K-crowns. Un papier est en cours d'élaboration.
