Le 05/05/2023 par gicquel :
Bonjour à tous,
Nous proposons une thèse financée à l'Université Paris Saclay.
Sujet : Conception et Génération d’explications pour des solutions issues de systèmes d’optimisation : application à la planification annuelle d'escadrons de gendarmerie mobile
Date limite de candidature : 20 mai 2023
Bien cordialement,
C. Gicquel
----------------------------------
Description du sujet
Cette thèse, réalisée en collaboration avec le Service des Technologies et des Systèmes d’Informations de la Sécurité Intérieure (ST(SI)², Direction générale de la Gendarmerie, ministère de l’intérieur), s’intéresse à une problématique rencontrée par les états-majors. En effet, une des responsabilités du Centre National des Opérations (CNO ) est de réaliser la planification annuelle des 109 escadrons de Gendarmerie Mobile. Concrètement, l’année à venir est découpée en semaines. Pour chacune de ces semaines, on dispose d’une liste d’environ cinquante missions à assurer (par exemple des missions de sécurisation de sites sensibles ou de renfort de gendarmerie départementale) en métropole, en outre-mer ou à l’étranger. Le problème de planification consiste à affecter, pour chaque semaine de l’horizon, un escadron à chaque mission. Les contraintes à prendre en compte sont multiples : respect des périodes de repos (permissions, indisponibilités) à accorder à chaque escadron, nombre maximal d'occurrences de certains types de mission dans le planning d’un escadron, intervalle de temps minimal à respecter entre certaines missions successives, coordination des relèves entre escadrons, etc. Le planning construit doit permettre d’optimiser simultanément plusieurs objectifs, notamment : maximiser la satisfaction des besoins opérationnels, maximiser l’équité entre la charge de travail des différents escadrons et maximiser la diversité des missions affectées à chaque escadron.
Un outil d’aide à la planification a été mis en place par le ST(SI)². Toutefois, le nombre élevé de décisions d’affectation à considérer (environ 280000) et la multiplication des contraintes à respecter peut rendre difficile la compréhension de l’affectation finale fournie par l’outil. En effet, face à la solution, le décideur du CNO peut s'interroger sur le fonctionnement de l'algorithme de planification et se poser des questions du type : ‘Pourquoi cet escadron a-t-il été affecté à cette mission ?’, ‘Pourquoi cette mission commence à cette date ?’, ‘N’est-il pas possible d’insérer une mission supplémentaire à telle date ?’, ... Cette thèse a pour objectif de mettre en place une méthodologie et des mécanismes d’explication permettant de répondre à ces questions, de justifier (soutenir) l’affectation fournie par l’outil, et ce faisant d’augmenter la confiance du décideur dans celle-ci.
Ce sujet s’inscrit dans le domaine de l’IA explicable [Gunning et Aha, 2019] qui a pour mission d'éclairer les utilisateurs finaux sur le fonctionnement des systèmes d’IA et de rendre leur fonctionnement plus transparent. Même si on a assisté ces dernières années à une explosion des travaux s'intéressant à cette question d'explicabilité, notamment dans le domaine du Machine Learning, e.g. [Barredo Arrieta et al., 2020], à notre connaissance, très peu de travaux sont dédiés à la construction d'explications pour des problèmes d’optimisation (e.g. [Korokov and Beck, 2021, Posanco, 2022]). En outre, ces travaux reposent sur des hypothèses qui limitent fortement leur champ d'application et qui rendent difficile l'utilisation des méthodes proposées pour fournir des explications sur le problème étudié dans cette thèse. A titre d’exception, un travail récent [Lerouge et al, 2023] s’est intéressé à la génération d’explications pour un problème de planification d’employés mobiles. Cependant, ce problème ne mobilise pas les mêmes contraintes et objectifs que le problème de planification d’escadrons de gendarmerie mobile si bien que les méthodes développées par [Lerouge et al, 2023] ne sont pas directement transposables au problème étudié ici. Un travail de recherche conséquent est donc nécessaire pour développer un outil d’explication adapté au cas pratique rencontré par la Gendarmerie Nationale.
D’un point de vue de la littérature, le problème d’escadrons mobiles appartient à une classe de problèmes d’optimisation combinatoire très étudiés dans la littérature : les problèmes d’affectation de personnel. Plus précisément, selon la classification de [Pineto et al, 2007], il s’agit d’un problème d’affectation multi-périodique multi-objectif incluant des contraintes supplémentaires. Ce problème trouve des applications dans des secteurs très variés tels que la planification annuelle des stages de formation d’étudiants internes en médecine [Franz and Miller, 1993], la gestion du personnel dans des centres ‘objets trouvés’ d’une zone touristique [Pour et al, 2017] ou l’affectation journalière de tâches à des ouvriers dans une usine [Ayough et al, 2012]. Notons en particulier que certaines caractéristiques de notre problème telles que la présence de nombreuses contraintes d’exclusion entre deux ou plusieurs décisions d’affectation [Franz and Miller, 1993 ; Pour et al, 2017], la nécessité de faire varier les tâches affectées à une personne pour éviter l’ennui [Ayough et al, 2012 ; Pour et al, 2017] ou la présence de plusieurs objectifs à optimiser simultanément [Zolfaghari et al., 2004] ont déjà été largement étudiées dans la littérature. Ceci signifie que les méthodes et techniques développées dans cette thèse pour développer des explications pour le problème de la Gendarmerie Mobile pourraient s'appliquer sur un large spectre de problèmes d'affectation de personnel.
Objectifs
Cette thèse s’intéresse au problème d’explicabilité de décisions algorithmiques pour le problème de planification annuelle d'escadrons de gendarmerie mobiles. L’objectif est de proposer une méthodologie et des outils formels pour la construction d’explications pour justifier les solutions (les plans d’affectation) de ce problème. Ces outils auront pour but d’augmenter la confiance des opérateurs dans l’outil d’aide à la planification.
Environnement
Le/la doctorant(e) sera accueilli(e) au LISN, Université Paris Saclay ainsi qu’au Datalab de la Direction Générale de la Gendarmerie Nationale (Issy-les-Moulineaux). Il/elle sera encadré(e) par Wassila Ouerdane (MICS, CentraleSupélec), Vincent Mousseau (MICS, CentraleSupélec) et Céline Gicquel (LISN, Université Paris-Sacaly). Cette thèse s’inscrit dans le cadre d’une collaboration avec Gaël de Léséleuc de Kérouara et Jean-Baptiste Delfau (ST(SI)², Gendarmerie Nationale).
Candidat et Financement
Nous recherchons des candidat(e)s intéressé(e)s ayant un Master2 (ou un diplôme d'ingénieur) (niveau Bac+5) en informatique ou en mathématiques appliquées. Plus particulièrement, de solides compétences en recherche opérationnelle sont requises. Un goût pour l’intelligence artificielle sera apprécié.
Date limite de candidature : 20 mai 2023
Cette thèse fait l’objet une allocation doctorale spécifiquement attribuée à ce projet. Cette allocation est co-financée par les ‘graduate schools’ ‘Informatique et sciences du numérique’ et ‘Sciences de l’ingéniérie et des systèmes’ de l’Université Paris Saclay.
Le ou la candidat(e) devra cependant passer une audition auprès de l’Ecole Doctorale ‘Sciences et Techniques de l’Information et de la Communication’ de l’Université Paris Saclay. Il ou elle pourra disposer de ce financement à condition que sa candidature soit retenue par l’école doctorale.
Comment candidater ?
Contacter Wassila Ouerdane (wassila.ouerdane@centralesupelec.fr) et Céline Giquel (gicquel@lri.fr) en envoyant un CV, une lettre de motivation ainsi que les notes disponibles de l'année passée et en cours, avant le 20 mai 2023.
Références
Alejandro Barredo Arrieta, et al., . Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai. Information Fusion, 58:82–115, 2020.
Ashkan Ayough & M. Zandieh & H. Farsijani. GA and ICA approaches to job rotation scheduling problem: considering employee’s boredom. International Journal of Advanced Manufacturing Technology (2012) 60:651–666.
L.S. Franz, J.L. Miller, Scheduling medical residents to rotations: Solving the large-scale multiperiod staff assignment problem, Operations Research 41 (2) (1993) 269–279.
Ghorbani Pour, Z. Naji-Azimi, M. Salari. Sample average approximation method for a new stochastic personnel assignment problem. Computers & Industrial Engineering 113 (2017) 135–143
Gunning, D., Aha, D., 2019. DARPA’s Explainable Artificial Intelligence (XAI) program. AI Magazine 40, 44–58.
Anton Korikov and J. Christopher Beck. Counterfactual explanations via inverse constraint programming. 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, pages 35:1–35:16.
Mathieu Lerouge; Céline Gicquel, Vincent Mousseau, Wassila Ouerdane. Counterfactual Explanations for Workforce Scheduling and Routing Problems. In Proceedings of the 12th International Conference on Operations Research and Enterprise Systems - ICORES, pages 50-61, 2023
David W. Pentico. Assignment problems: A golden anniversary survey. European Journal of Operational Research 176 (2007) 774–793
Alberto Pozanco, Francesca Mosca, Parisa Zehtabi, Daniele Magazzeni, Sarit Kraus: Explaining Preference-Driven Schedules: The EXPRES Framework. ICAPS 2022: 710-718
S. Zolfaghari, M.Y. Jaber & H. Hamoudi. A goal programming approach for a multi-period task assignment problem. INFOR: Information Systems and Operational Research (2004), 42:4, 299-309.
