Offre de Thèse en Explicabilité pour des Systèmes d'Optimisation

• 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
• Environnement : Laboratoire MICS à CentraleSupélec (Université Paris-Saclay) et DataLab du ST(SI)² - Direction Générale de la Gendarmerie Nationale.
• Profil recherché : étudiant(e) en 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é.
• Candidatures : 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 21 avril 2023.
• Démarrage: Automne 2023
• Financement:  la Gendarmerie Nationale financera la thèse à hauteur de 50%.  Le/la candidat(e) retenu(e) contribuera au dépôt du dossier de demande de cofinancement de la thèse auprès de l’agence d’innovation de défense (AID) dont le résultat est attendu en juin 2023.

Détail 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.

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.

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.

• 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.

• David W. Pentico. Assignment problems: A golden anniversary survey. EJOR 176 (2007) 774–793.

• 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.

• 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.

• A. 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.