PhD Defence: “On the Performance of Spatial Modulation and Full Duplex Radio Architectures”, Yanni Zhou, Amphitheater, CITI, 10th of December 2021 at 10:00 PM

The defense will be held in the Amphitheater, Claude Chappe, and will be streamed live here.

 

Title

On the Performance of Spatial Modulation and Full Duplex Radio Architectures

 

 

Abstract

Index modulation techniques have exhibited great potential in the scenarios foreseen in next-generation wireless networks. Applying in the spatial domain, spatial modulation (SM) as a single radio-frequency (RF) multiple-input–multiple-output (MIMO) solution has attracted wide attention. The SM system has only one transmitting antenna activated for each time slot which results in low system complexity and cost. It exploits the index of the transmitting antennas to convey additional information bits.

To analyze the SM performance, a simulated framework over the time-varying Rician fading channel is built with ADS and Matlab software and a channel state information (CSI) detector is highlighted. The simulation results are verified by the experimental implementation based on the National Instruments (NI) PXI chassis hardware and LabVIEW programming environment. In the practical analysis, two models of the propagation environments are considered, where a channel sounding method is employed in order to extract the channel coefficients.

Despite issues on system complexity and cost, a shortage of spectrum resources can also restrict the development of mobile communications technology. Full duplex (FD) communications have been developed to double the radio link data rate and spectral efficiency through simultaneous and bidirectional communication. The main challenge of FD systems is self-interference (SI), which is caused by the coupling of the transmitting antenna with the receiving one. The combination of FD and SM will not only maintain spectral efficiency but also decrease the complexity of the self-interference cancellation (SIC) because of the single RF chain.

Based on these, a full duplex spatial modulation (FDSM) system is proposed as well as the SIC method. Moreover, the impact of SIC accuracy on the system performance is studied. We focus on the FDSM system imperfections including IQ imbalance, phase noise, power amplifier (PA) nonlinearities and RF switch nonidealities. The bit error rate (BER) performance under different scenarios with these imperfections is analyzed, along with the estimation and cancellation method.

 

 

Jury

  • Marco Di Renzo, Research Director at CNRS, Reviewer
  • Matthieu Crussière, Professor at INSA-Rennes, Reviewer
  • Christelle Aupetit-Berthelemot, Professor at Université de Limoges, Examiner
  • Taneli Riihonen, Associate Professor at Tampere University, Examiner
  • Jean-Marie Gorce, Professor at INSA-Lyon, Examiner
  • Dinh-Thuy Phan-Huy, Engineer at Orange Lab, Examiner
  • Guillaume Villemaud, Associate Professeur at INSA-Lyon, Thesis director
  • Florin-Doru Hutu, Associate Professor at INSA-Lyon, Co-director

PhD Defence: “Privacy in learning systems for healthcare”, Théo Jourdan, Amphitheater, Library UCBL, 29th of October 2021 at 9:00 PM

The defense will be held in the Amphitheater, Chappe Library UCBL, and will be streamed live here.

 

Title

Privacy in learning systems for healthcare

 

 

Abstract

With the development of the Internet of Things (IoT), smartphones and sensors are now able to provide information about the user’s activity and even their physiology. This has led to a growing interest from the scientific community, particularly in the field of e-health, with applications in the monitoring of patients undergoing rehabilitation in order to offer more personalized follow-up. However, in addition to guiding the rehabilitation process, the generation and transmission of IoT data is also vulnerable to privacy breaches. Indeed, the complex processing chain of the IoT application in healthcare multiplies the risk of privacy threats throughout the life cycle of IoT data, including collection, transmission and storage, by an adversary who can retrieve the data and re-identify or reveal sensitive patient information. This thesis focuses on the following questions: Is the data collected sufficiently protected so that no one can misuse it to re-identify the owner or infer sensitive information? Is the protected data still accurate enough for healthcare applications such as rehabilitation? Achieving balance between data utility and privacy protection is an important challenge that we explore in this thesis from different angles. More specifically, the first part focuses on the problem of data anonymization through minimization, while the second part focuses on preventing the inference of sensitive attributes through a Generative Adversarial Networks (GAN) to sanitize sensor data and an approach exploiting private layers in Federated Learning (FL).

 

 

Jury

  • Fossati, Caroline Professeure des Universités, Institut Fresnel Rapporteure
  • Vincent, Emmanuel Directeur de Recherche, INRIA Nancy Rapporteur
  • Bellet, Aurélien Chargé de Recherche, INRIA Lille Examinateur
  • Ben Mokhtar, Sonia Directrice de Recherche, LIRIS Examinatrice
  • Dieterlen, Alain Professeur des Universités, IRIMAS Examinateur
  • Frindel, Carole Maître de Conférences, INSA Lyon Co-directrice de thèse
  • Boutet, Antoine Maître de Conférences, INSA Lyon Co-directeur de thèse

PhD Defence: “Expliquer et justifier les systèmes de décisions algorithmiques”, Clément Henin, Amphitheater, Chappe Building, 13th of October 2021 at 15:00 PM

The defense will be held in the Amphitheater, Chappe Building, and will be streamed live here.

 

Title

Expliquer et justifier les systèmes de décisions algorithmiques

 

 

Abstract

Les systèmes décisionnels fondés sur un traitement algorithmique sont déjà présents dans de nombreux domaines et leur utilisation devrait encore s’accroître. Pour certains types d’applications, l’opacité de ces systèmes peut être un frein, voire un obstacle rédhibitoire, à leur utilisation. Dans cette thèse, nous nous intéressons à la production d’explications et de justifications en « boîte noire », c’est-à-dire sans accès au code du système de décision. L’avantage de cette démarche est de fournir des résultats qui peuvent s’appliquer à de nombreux systèmes, indépendamment de leur mode de fonctionnement. Notre première contribution est un système d’explications interactif, permettant à l’utilisateur de contrôler les propriétés de l’explication qui lui est fournie afin d’obtenir la plus adaptée à sa situation. La deuxième contribution propose une approche novatrice pour contester et justifier les résultats d’un algorithme. Ces approches théoriques ont donné lieu au développement de deux outils : IBEX et Algocate. Ces résultats théoriques sont confrontés au terrain au travers d’études utilisateurs, dont un travail mené sur l’algorithme Score Cœur utilisé pour l’attribution des greffons cardiaques. Cette étude combine des éléments sociologiques notamment sur l’appropriation par les acteurs de ce système de décision et le développement d’un outil d’explication et de justification adapté aux spécificités de Score Coeur.

 

 

Jury

  • Solnon, Christine, Professeure, INSA Lyon,
  • Amer-Yahia, Sihem, Directrice de recherche, LIG, Rapporteure
  • Gambs, Sébastien, Professeur, UQAM, Rapporteur
  • Jacquelinet, Christian, Médecin Spécialiste, Agence de la Biomédecine, Examinateur
  • Mabi, Clément, Maître de conférence, UTC Compiègne, Examinateur
  • Le Métayer, Daniel, Directeur de recherche, Inria, Co-Directeur de thèse
  • Castelluccia, Claude, Directeur de recherche, Inria, Co-directeur de thèse

PhD Defence: “Contribution à l’analyse des systèmes de communications pour le régime paquets courts”, Dadja Anade, Amphitheater, Chappe Building, 07th of October 2021 at 14:00 PM

The defense will be held in the Amphitheater, Chappe Building, and will be streamed live here.

 

Title

Contribution à l’analyse des systèmes de communications pour le régime paquets courts

 

 

Abstract

Dans cette thèse, une fonction qui approxime la fonction de répartition d’une somme de vecteurs aléatoires indépendants et identiquement distribués est présentée. L’erreur d’approximation est majorée, et par consequent, une borne supérieure et une borne inférieure sur la fonction de répartition sont obtenues. Pour des vecteurs aléatoires absolument continues ou discrètes regulières (“lattices”), l’approximation proposée est identique à l’approximation du point de selle de la fonction de répartition. Ce résultat est ulitisé pour approcher les bornes de probabilité d’erreur de décodage pour les canaux point à point et à accès multiple. Sur le canal point à point, cette approche a permis de constater l’insuffisance de l’approximation normale, particulièrement pour des probabilité d’erreur de décodage de faibles valeurs. Concernant les canaux à accès multiple, la considération de la notion d’erreur individuel a revélé le comportement presque non interférant des transmetteurs pour des petites valeurs de la probabilité d’erreur de décodage et de la longueur des paquets.

 

 

Jury

  • François BACCELLI – Directeur de recherche – INRIA – Rapporteur
  • H. Vincent POOR – Professeur – Princeton University – Examinateur
  • Aline ROUMY – Directeur de Recherche – INRIA – Examinateur
  • Michèle WIGGER – Professeur – Telecom ParisTech – Rapporteur
  • Samir M. Perlaza – HDR, Chargé de recherche – INRIA, Co-directeur
  • Philippe MARY – HDR, Maitre de conférence – Université de Lyon – Co-directeur
  • Jean-Marie Gorce – Professeur – Université de Lyon – Directeur de thèse

PhD Defence: “Gestion d’Interference Topologique pour les Réseaux Sans Fils Multi-utilisateurs”, Hassan Kallam, Amphitheater, Chappe Building, 28th of September 2021 at 14:00 PM

The defense will be held in the Amphitheater, Chappe Building.

 

Title

Gestion d’Interference Topologique pour les Réseaux Sans Fils Multi-utilisateurs

 

 

Abstract

La gestion d’interference topologique (de l’Anglais: Topological Interference Management – TIM) permet l’etude des dégrées de liberté (de l’Anglais: Degrees of Freedom – DoF) de réseaux sans fils soumis à l’interference partielle et dont la connaissance de l’état du canal est limitée seulement à la topologie du réseaux, autrement dit, les liens interférents faibles et forts. Dans ce manuscrit de thèse, nous considérons l’application de TIM pour les réseaux cellulaires d’une dimension (1D) linéaires et les réseaux cellulaires de deux dimensions (2D) hexagonales. Nous considérons le cas des utilisateurs uniformément distribués dans chaque cellule, ce qui donne une distribution continue d’utilisateurs. Ceci nous permet d’étudier la performance des classes d’utilisateurs au contraire des positions des utilisateurs individuels, comme a été fait auparavant. Nous considérons aussi la construction de la topologie au travers de l’analyse des seuils de l’interférence. Contrairement aux travaux existents nous utilisons TIM au niveau des classes des utilisateurs, ce qui nous permet de trouver la performance système en DoF indépendante de la position précise de chaque utilisateur. Ensuite, après avoir proposé un schéma de coloration fractionnaire des graphes resultants, pouvant atteindre la solution optimale de DoF, un compromis entre DoF et SIR est proposé. Cette thèse propose également une nouvelle approche pour construire une topologie d’interférence pour le problème TIM unicast des réseaux sans fil multi-utilisateurs. Fondée sur notre approche de construction de topologie d’interférence, nous pouvons évaluer la limite théorique des taux atteignables, dans le régime SNR asymptotique, pour le réseau sans fil sous-jacent et pas seulement pour sa représentation topologique d’interférence. Cette nouvelle approche nous permet de traiter le régime de SNR fini et pas seulement le régime SNR asymptotique avec l’analyse DoF. Un nouveau paramètre liée au seuil d’interférence, indépendant du SNR, est proposé et nous évaluons les débits symétriques réalisables du réseau sans fil, à la fois en régime SNR fini et en régime SNR asymptotique. Ensuite, nous présentons les bornes supérieures sur ce nouveau paramètre de seuil d’interférence normalisé pour les topologies d’interférence ayant une faisabilité en demi-DoF (de l’Anglais: Half-DoF-feasible), en considérant à la fois une allocation de ressources orthogonale et l’alignement d’interference (de l’Anglais: Interference Alignment – IA). Ces limites spécifient si une topologie d’interférence donnée realisable en demi-DoF peut être, en termes de taux réalisable, la meilleure topologie ou non. En utilisant ce résultat, nous limitons l’espace de recherche dans la plage de paramètres du seuil d’interférence normalisée, pour trouver des topologies d’interférence réalisables à demi-DoF ayant la possibilité d’être les meilleures topologies en termes de taux réalisable. Enfin, cette thèse considère une étude de cas sur le TIM pour les réseaux sans fil à petite échelle, dans laquelle, nous considérons le problème TIM pour les réseaux à quatre utilisateurs en employant notre approche de construction de topologie d’interférence proposée. Ensuite, nous appliquons l’analyse des débits réalisables, proposée dans le cadre de la nouvelle approche de construction de topologie d’interférence, pour toutes les topologies d’interférence réalisables à demi-DoF, à la fois par partage orthogonal et IA, dans le problème TIM de réseaux sans fil à quatre utilisateurs.

 

 

Jury

  • Florian KALTENBERGER – Maître de Conférences HDR – EURECOM – Rapporteur
  • Iñaki ESNAOLA – Senior lecturer – University of Sheffield – Rapporteur
  • Ghaya REKAYA-BEN OTHMAN – Professeur des Universités – TELECOM PARIS – Examinatrice
  • Laurent CLAVIER – Professeur des Universités – TELECOM LILLE – Examinateur
  • Leonardo S. Cardoso – Maître de Conférence – Université de Lyon – Co-directeur
  • Jean-Marie Gorce – Professeur des Universités – Université de Lyon – Directeur

PhD Defence: “Deep learning based approaches for detection in physical layer wireless multiple access”, Cyrille Morin, Amphitheater, Chappe Building, 22th of July 2021 at 14:00 PM

The defense will be held in the Amphitheater, Chappe Building, and will be streamed live here: link

 

Title

Deep learning based approaches for detection in physical layer wireless multiple access

 

 

Abstract

Current trends point towards an accelerated augmentation of devices with a desire to access the shared radio spectrum, both due to the continued democratisation and capability augmentation of user facing radio devices, such as cellphones, computers, and especially wearables, but also to the deployment of connected objects and sensors. Technology, protocols, and legislation improvements increase the available frequency bands by opening new channels in the GHz range, but the density of devices is nevertheless expected to increase. Multiple access to a shared radio frequency resource leads to situations that are both complex to model, and to tackle with known algorithms, and it is true of detection tasks that arise in the physical layer of a wireless transmission. The class of deep learning algorithms is especially useful in this sort of situation without model, or with non tractable algorithms, as long as a large amount of labelled data is available to train the related neural networks. This thesis aims at adapting the deep learning tool to physical layer detection problems, in successive steps of a decoding chain. First with the problem of detecting the origin of a received packet, starting with hardware fingerprinting of a transmitting device, and extending it to a scenario with multiple active devices at the same time, detecting the set of active devices transmitting an explicit codeword. The next step after origin detection is bit detection, to decode transmitted messages. For that, deep learning is used to learn constellations allowing for an efficient bit detection in a multiple-access scenario, namely the two-user uplink NOMA. Data used to train the networks involved in this thesis are gathered both from simulated models, and from experimental implementations in the FIT/CorteXlab software defined radio test-bed.

 

 

Jury

  • Marco Di Renzo – Research Director – CentraleSupélec – Reviewer
    Symeon Chatzinotas – Professor – University of Luxembourg – Reviewer
    Marwa Chafii – Associate Professor – ENSEA – Examiner
    Catherine Douillard – Professor – IMT Atlantique – Examiner
    Christophe Moy – Professor – Université de Rennes 1 – President
    Leonardo S. Cardoso – Associate Professor – Université de Lyon – Co-supervisor
    Jakob Hoydis – Principal Research Scientist – Nvidia – Co-supervisor
    Jean-Marie Gorce – Professor – Université de Lyon – Supervisor

HDR Defence: “Privacy issues in wireless networks, Every frame you send, they’ll be watching you.”, Mathieu Cunche, 2nd of June 2021 at 2PM

The defense will be streamed live here: link

 

Title

Privacy issues in wireless networks, Every frame you send, they’ll be watching you.

Abstract

A growing number of devices carried by users are equipped with wireless technologies such as Bluetooth and Wi-Fi which allow the seamless exchange of information between devices and the network infrastructure. Because they routinely emit wireless messages carrying identifiers and other technical artifacts in cleartext, these technologies expose users to privacy issues. Focusing on the data included in advertising messages, we identify and analyze the leakage of personal data, and study potential and existing countermeasures. More specifically, we try to answer the following questions: what are the privacy threats associated with wireless networks? Which solutions can be deployed to protect users against these threats? How efficient are current privacy protection implementations? We start by an analysis of privacy features of the two major wireless network standards: Wi-Fi and Bluetooth-Low-Energy. We focus our study on address randomization mechanisms, a recently adopted anti-tracking measure, and identify several issues related to implementation as well as standard specifications. To illustrate the diversity and complexity of the issues affecting these technologies, we present two representative cases of personal data leakage in wireless networks. First, leveraging the reverse-engineering of Continuity, a BLE-based protocol developed by Apple, we uncover a collection of personal data leakages affecting billions of devices worldwide. Finally, we present an abuse of Android Wi-Fi permission that can be used to bypass permissions and to infer personal data such as the location of the device. When confronted with those privacy issues, it becomes necessary to increase user protection by developing privacy-preserving mechanisms but most importantly by correctly implementing existing ones. Furthermore, it appears that standard specifications are key elements of a better protection, and it is thus of utmost importance to promote the integration of privacy protection in these standards.

 

Jury

    • Monsieur Noubir Guevara, Professeur, Northeastern University (Rapporteur)
    • Madame Fischer-Hübner Simone, Professeure, Karlstad University (Rapporteur)
    • Madame Guérin-Lassous Isabelle, Professeure, Université Claude Bernard Lyon 1
    • Monsieur Gorce Jean-Marie, Professeur, INSA-Lyon
    • Monsieur Zuniga Juan-Carlos, SigFox
    • Monsieur Anciaux Nicolas, Directeur de recherche, Inria, Université de Versailles/St-Quentin (Rapporteur)

PhD Defence: “De l’évaluation des performances Wi-Fi à la mobilité contrôlée pour les réseaux de drones”, Remy Grünblatt, 8th of January 2021 at 14:00 PM

The defense will be streamed live here: link

 

Title

De l’évaluation des performances Wi-Fi à la mobilité contrôlée pour les réseaux de drones

 

Abstract

La mobilité dans les réseaux de télécommunications est souvent considérée comme un problème qu’il faut résoudre : un appareil mobile sans fil doit adapter ses paramètres de transmission afin de rester connecté à son ou ses homologues, car le canal évolue avec les mouvements de l’appareil. Les drones, qui sont des véhicules aériens sans pilote, ne font pas exception. En raison de leur grande liberté de mouvements, de leur mobilité tridimensionnelle, et ce dans des environnements aussi nombreux que variés, de leur charge utile limitée et de leurs contraintes énergétiques, et en raison du large éventail de leurs applications dans le monde réel, les drones représentent de nouveaux objets d’étude passionnants dont la mobilité est un défi. Pourtant, la mobilité peut aussi être une chance pour les réseaux de drones, surtout lorsque nous pouvons la contrôler. Dans cette thèse, nous explorons comment la mobilité contrôlée peut être utilisée pour augmenter les performances d’un réseau de drones, en mettant l’accent sur les réseaux IEEE 802.11 et les petits drones multi-rotor. Nous décrivons d’abord comment la mobilité est traitée dans les réseaux 802.11, c’est-à-dire en utilisant des mécanismes d’adaptation de débit, puis nous effectuons l’ingénierie inverse de l’algorithme d’adaptation de débit utilisé dans le chipset Wi-Fi du drone Intel Aero. L’étude de cet algorithme d’adaptation de débit, de manière à la fois expérimentale et par simulation, grâce à son implémentation dans le simulateur de réseau NS-3, permet de le comparer à d’autres algorithmes bien connus. Cette étude met en évidence l’importance de ces algorithmes pour les réseaux de drones, en lien avec leur mobilité, et la différence de comportement de chaque nœud en résultant. Par conséquent, une solution de mobilité contrôlée visant à améliorer les performances du réseau ne peut pas supposer beaucoup du comportement des algorithmes d’adaptation de débits. En outre, les applications des réseaux de drones sont diverses, et il est difficile d’imposer des contraintes de mobilité sans devenir incompatible avec un pan complet d’applications. Nous proposons donc une solution de mobilité contrôlée qui exploite le diagramme de rayonnement de l’antenne des drones. Cet algorithme est évalué grâce à outil de simulation développé pour l’occasion, permettant la simulation d’antennes et de drones, basé sur NS-3. Cette solution, qui fonctionne avec n’importe quel algorithme d’adaptation de débit, est distribuée, et ne nécessite aucune coordination globale ou communication spécifique qui pourrait s’avérer coûteuses. Elle ne nécessite pas non plus un contrôle complet de la mobilité du drone comme le requièrent les solutions de mobilité contrôlée existantes, ce qui rend cette solution compatible avec diverses applications.

 

 

Jury

  • Mme. Nathalie MITTON, Directrice de recherche à INRIA Lille Nord – Europe, Rapportrice
  • Mr. Enrico NATALIZIO, Professeur des universités au Technology Innovation Institute – Abu Dhabi, Rapporteur
  • Mme. Laure GONNORD, Maître de conférences à l’université Lyon 1 Claude Bernard – Lyon, Examinatrice
  • Mr. André-Luc BEYLOT, Professeur des universités à l’ENSEEIHT – Toulouse, Examinateur
  • Mr. Franck ROUSSEAU, Maître de conférences à Grenoble INP-Ensimag – Grenoble, Examinateur
  • Mme. Isabelle GUÉRIN-LASSOUS, Professeure des universités à l’université Lyon 1 Claude Bernard – Lyon, Directrice de thèse
  • Mr. Olivier SIMONIN, Professeur des universités à l’INSA de Lyon, Codirecteur de thèse

PhD Defence: “Étalonnage in situ de l’instrumentation bas coût pour la mesure de grandeurs ambiantes : méthode d’évaluation des algorithmes et diagnostic des dérives”, Florentin Delaine, 4th of December 2020 at 10:30AM

The defense will be streamed live here: link

 

Title

Étalonnage in situ de l’instrumentation bas coût pour la mesure de grandeurs ambiantes : méthode d’évaluation des algorithmes et diagnostic des dérives

Abstract

In various fields going from agriculture to public health, ambient quantities have to be monitored in indoors or outdoors areas. For example, temperature, air pollutants, water pollutants, noise and so on have to be tracked. To better understand these various phenomena, an increase of the density of measuring instruments is currently necessary. For instance, this would help to analyse the effective exposure of people to nuisances such as air pollutants. The massive deployment of sensors in the environment is made possible by the decreasing costs of measuring systems, mainly using sensitive elements based on micro or nano technologies. The drawback of this type of instrumentation is a low quality of measurement, consequently lowering the confidence in produced data and/or a drastic increase of the instrumentation costs due to necessary recalibration procedures or periodical replacement of sensors. There are multiple algorithms in the literature offering the possibility to perform the calibration of measuring instruments while leaving them deployed in the field, called in situ calibration techniques.

The objective of this thesis is to contribute to the research effort on the improvement of data quality for low-cost measuring instruments through their in situ calibration. In particular, we aim at 1) facilitating the identification of existing in situ calibration strategies applicable to a sensor network depending on its properties and the characteristics of its instruments; 2) helping to choose the most suitable algorithm depending on the sensor network and its context of deployment; 3) improving the efficiency of in situ calibration strategies through the diagnosis of instruments that have drifted in a sensor network. Three main contributions are made in this work. First, a unified terminology is proposed to classify the existing works on in situ calibration. The review carried out based on this taxonomy showed there are numerous contributions on the subject, covering a wide variety of cases. Nevertheless, the classification of the existing works in terms of performances was difficult as there is no reference case study for the evaluation of these algorithms. Therefore in a second step, a framework for the simulation of sensors networks is introduced. It is aimed at evaluating in situ calibration algorithms. A detailed case study is provided across the evaluation of in situ calibration algorithms for blind static sensor networks. An analysis of the influence of the parameters and of the metrics used to derive the results is also carried out. As the results are case specific, and as most of the algorithms recalibrate instruments without evaluating first if they actually need it, an identification tool enabling to determine the instruments that are actually faulty in terms of drift would be valuable. Consequently, the third contribution of this thesis is a diagnosis algorithm targeting drift faults in sensor networks without making any assumption on the kind of sensor network at stake. Based on the concept of rendez-vous, the algorithm allows to identify faulty instruments as long as one instrument at least can be assumed as non-faulty in the sensor network. Across the investigation of the results of a case study, we propose several means to reduce false results and guidelines to adjust the parameters of the algorithm. Finally, we show that the proposed diagnosis approach, combined with a simple calibration technique, enables to improve the quality of the measurement results. Thus, the diagnosis algorithm opens new perspectives on in situ calibration.

 

Jury

  • M. Jean-Luc Bertrand-Krajewski, Professeur des Universités, Université de Lyon, INSA Lyon, DEEP (Rapporteur)
  • M. Romain Rouvoy, Professeur des Universités, Université de Lille, Spirals (Rapporteur)
  • Mme Nathalie Redon, Maître de conférences, IMT Lille Douai, SAGE (Examinatrice)
  • M. Gilles Roussel, Professeur des Universités, Université du Littoral Côte d’Opale, LISIC (Examinateur)
  • Mme Bérengère Lebental, Directrice de recherche, Institut Polytechnique de Paris, École Polytechnique, LPICM (Directrice de thèse)
  • M. Hervé Rivano, Univeristé de Lyon, INSA Lyon, CITI Lab (Co-directeur de thèse)
  • M. Éric Peirano, Directeur général adjoint en charge de la R&D, Efficacity (Invité)
  • M. Matthieu Puigt, Maître de conférences, Université du Littoral Côte d’Opale, LISIC (Invité)

PhD Defence: “Deep Multi-Agent Reinforcement Learning for Dynamic and Stochastic Vehicle Routing Problems”, Guillaume Bono, 28th of October 2020 at 2PM

The defense will take place in amphitheater Chappe and you are all welcome to attend as long as there are enough place (35 persons max).
It will be also streamed live on youtube at: https://youtu.be/fvCz5ZXYN_I

 

Title

Deep Multi-Agent Reinforcement Learning for Dynamic and Stochastic Vehicle Routing Problems

Abstract

Routing delivery vehicles in dynamic and uncertain environments like dense city centers is a challenging task, which requires robustness and flexibility. Such logistic problems are usually formalized as Dynamic and Stochastic Vehicle Routing Problems (DS-VRPs) with a variety of additional operational constraints, such as Capacitated vehicles or Time Windows (DS-CVRPTWs). Main heuristic approaches to dynamic and stochastic problems simply consist in restarting the optimization process on a frozen (static and deterministic) version of the problem given the new information. Instead, Reinforcement Learning (RL) offers models such as Markov Decision Processes (MDPs) which naturally describe the evolution of stochastic and dynamic systems. Their application to more complex problems has been facilitated by recent progresses in Deep Neural Networks, which can learn to represent a large class of functions in high dimensional spaces to approximate solutions with high performances. Finding a compact and sufficiently expressive state representation is the key challenge in applying RL to VRPs. Recent work exploring this novel approach demonstrated the capabilities of Attention Mechanisms to represent sets of customers and learn policies generalizing to different configurations of customers. However, all existing work using DNNs reframe the VRP as a single-vehicle problem and cannot provide online decision rules for a fleet of vehicles.
In this thesis, we study how to apply Deep RL methods to rich DS-VRPs as multi-agent systems. We first explore the class of policy-based approaches in Multi-Agent RL and Actor-Critic methods for Decentralized, Partially Observable MDPs in the Centralized Training for Decentralized Control (CTDC) paradigm. To address DS-VRPs, we then introduce a new sequential multi-agent model we call sMMDP. This fully observable model is designed to capture the fact that consequences of decisions can be predicted in isolation. Afterwards, we use it to model a rich DS-VRP and propose a new modular policy network to represent the state of the customers and the vehicles in this new model, called MARDAM. It provides online decision rules adapted to the information contained in the state and takes advantage of the structural properties of the model. Finally, we develop a set of artificial benchmarks to evaluate the flexibility, the robustness and the generalization capabilities of MARDAM. We report promising results in the dynamic and stochastic case, which demonstrate the capacity of MARDAM to address varying scenarios with no re-optimization, adapting to new customers and unexpected delays caused by stochastic travel times. We also implement an additional benchmark based on micro-traffic simulation to better capture the dynamics of a real city and its road infrastructures. We report preliminary results as a proof of concept that MARDAM can learn to represent different scenarios, handle varying traffic conditions, and customers configurations.

 

Jury

  • François Charpillet, Research Director at INRIA Nancy Grand Est, Reviewer
  • Romain Billot, Professor at IMT Atlantique, Reviewer
  • René Mandiau, Professor at Université Polytechnique des Hauts de France, Examiner
  • Aurélie Beynier, Associate Professor at Sorbonne Université, Examiner
  • Christian Wolf, Associate Professor at INSA de Lyon, Examiner
  • Olivier Simonin, Professeur à l’INSA de Lyon, Thesis director
  • Jilles Dibangoye, Associate Professor at INSA de Lyon, Co-supervisor
  • Laëtitia Matignon, Associate Professor at Université Lyon 1, Co-supervisor
  • Florian Pereyron, Research Engineer at Volvo Group, Co-supervisor