The defense will take place on Tuesday 9th June (morning) in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Exact and anytime heuristic search for the Time Dependent Traveling Salesman Problem with Time Windows

Abstract

The Time Dependent (TD) Traveling Salesman Problem (TSP) is a generalization of the TSP which allows one to take traffic conditions into account when planning tours in an urban context: travel times between points to visit depend on departure times instead of being constant. The TD-TSPTW further generalizes this problem by adding Time Window constraints, i.e., constraints on visit times. Existing exact approaches such as Integer Linear Programming and Dynamic Programming usually do not scale well; heuristic approaches scale better but provide no guarantees on solution quality.

In this thesis, we introduce a new exact and anytime solving approach for the TD-TSPTW which aims at quickly providing approximate solutions and gradually improving them until proving optimality. We first show how to reduce the TD-TSPTW to the search for a best path in a state-transition graph. We provide an overview of existing search algorithms, with a focus on exact and anytime extensions of A*, and introduce a new one by hybridizing two of them. We show how to combine these exact and anytime search algorithms with local search – in order to faster find solutions of higher quality – and with bounding and time window constraint propagation – in order to filter the search space. Finally, we provide extensive experimental results to (i) validate our main design choices, (ii) compare our approach to state-of-the-art solving approaches on various TD benchmarks with different degrees of realism and different temporal granularities and (iii) compare TD solving approaches to recent TSPTW solvers on constant benchmarks. These experimental results show us that our approach offers a good compromise between the time needed to find good solutions and the time needed to find optimal solutions and prove their optimality for both TD and constant TSPTW instances.

Jury

• • • Cédric PRALET, Directeur de Recherche, ONERA – Rapporteur
    • Pierre SCHAUS, Professeur des Universités, UC Louvain – Rapporteur
    • Romain BILLOT, Professeur des Universités, IMT Atlantique – Examinateur
    • Christine SOLNON Professeure des Universités, INSA Lyon – Directrice de thèse
    • Jilles S. DIBANGOYE, Maître de Conférences HDR, University of Groningen – Co-directeur de thèse

The defense will take place on Friday 24th May at 10AM in the Heidi Lamarr building, Insa-Lyon, Villeurbanne.

Title

Contributions to Wireless Sensor Networks for Air Quality Monitoring

Abstract

In this talk, I will present a summary of my research, which revolves around the design and evaluation of novel solutions for Wireless Sensor Networks to efficiently monitor physical phenomena. I have addressed several scientific and technical issues by adopting a global methodology combining theoretical solutions and experimental developments. Although our solutions can be easily adapted to different applications, the focus was on air quality monitoring, a major societal challenge where new low-cost sensing technologies offer a significant advantage over traditional solutions.

This talk focuses on our main contributions in this area of low-cost sensor networks for environmental monitoring. It is structured around three axes: i) static sensor networks for air quality monitoring in cities and on industrial sites; ii) participatory sensing of air quality and Urban Heat Islands; and iii) UAV fleets for monitoring highly dynamic phenomena. The common thread running through all our solutions is that they take into account both the physical domain knowledge and the characteristics of low-cost sensors such as the limited and heterogeneous measurement accuracy. I will conclude this talk by discussing some personal feedback and setting out some future perspectives.

Jury

• • Aline CARNEIRO VIANA, Directrice de recherche, INRIA, Reviewer
  • Andrzej DUDA, Professeur, Grenoble INP – Ensimag, Reviewer
  • Nathalie MITTON, Directrice de recherche, INRIA, Reviewer
  • André-luc BEYLOT, Professeur, Toulouse INP – ENSEEIHT, Examiner
  • Abdelmadjid BOUABDALLAH, Professeur, Université de Technologie de Compiègne, Examiner
  • Isabelle GUERIN-LASSOUS, Professeur, Université de Lyon 1, Examiner
  • Hervé RIVANO, Professeur, INSA-Lyon, Examiner (« Garant »)
  • Mouloud KOUDIL, Professeur, ESI-Alger, Guest Examiner

The defense will take place on Tuesday 22th May at 10 AM in the East amphitheater of the humanities building, Insa-Lyon, Villeurbanne.

Title

Programming language abstractions for the Internet of Things era

Abstract

Jury

• • • Mme Stéphanie CHOLLET, Maître de conférences HDR – ESISAR Grenoble INP – Rapporteure
    • M. Stéphane DUCASSE, Directeur de Recherche – INRIA – Rapporteur
    • M. Philippe ROOSE, Professeur des Universités – Université de Pau et des Pays de l’Adour – Examinateur
    • M. Yannick LOISEAU, Maître de Conférences – Université Clermont Auvergne – Examinateur
    • M. Frédéric LE MOUËL, Professeur des universités – INSA Lyon – Directeur de thèse
    • M. Julien PONGE, Docteur – Red Hat – co-encadrant de thèse

The defense will take place on Tuesday 19th December at 2 PM in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Navigation Among Movable Obstacles (NAMO) Extended to Social and Multi-Robot Constraints

Abstract

As robots become ever more commonplace in human environments, taking care of ever more tasks such as cleaning, security or food service, their current limitations only become more apparent. One such limitation is of their navigation capability in the presence of obstacles: they always avoid them, and freeze in place when avoidance is impossible.

This is what brought about the creation of Navigation Among Movable Obstacles (NAMO) algorithms, expected to allow robots to manipulate obstacles as to facilitate their own movement. However, these algorithms were designed under the hypothesis of a single robot per environment, biasing NAMO algorithms into only optimizing the single robot’s displacement cost – without any consideration for humans or other robots. While it is desirable to endow robots with the human capability of moving obstacles, they must however do so while respecting social norms and rules of humans.

We have thus extended the NAMO problem as to take into account these new social and multi-robots aspects. By relying on the concept of affordance spaces, we have developed a social occupation cost model allowing the evaluation of the impact of moved objects on the environment’s navigability. We implemented (and improved) reference NAMO algorithms, in our open source simulation tool, and modified them so that they may plan compromises between robot displacement cost and social occupation cost of moved obstacles – resulting in improved navigability. We also developed an implicit coordination strategy allowing the concurrent execution of these same algorithms by multiple robots as is, without any explicit communication requirements, while preserving the no-collision guarantee; verifying the relevance of our social occupation cost model in the actual presence of other robots. As such, this work constitutes the first steps towards a Social and Multi-Robot NAMO.

Jury

• • Philippe Mathieu , Professeur des Universités, Université de Lille, CRISTAL, Rapporteur
  • Fabien Michel, Maître de Conférences HDR, Université Montpellier 2, LIRMM, Rapporteur
  • Julie Dugdale, Professeur des Universités, Université de Grenoble, LIG, Examinatrice
  • Rachid Alami, Directeur de Recherche CNRS émérite, LAAS, Toulouse, Examinateur
  • Olivier Simonin, Professeur des Universités, INSA-Lyon, CITI, Directeur de thèse
  • Jacques Saraydaryan, Enseignant Chercheur, CPE Lyon, CITI, Co-encadrant