Planning Problems in a Multi-Tethered-Robot System

Doctorante : Xiao PENG

Laboratoire INSA : CITI
Ecole doctorale : ED512 : Infomaths

Multiple robot systems are widely applied in our real life. As a special type of mobile system, tethered robots play a crucial role in special contexts, particularly in challenging conditions, where cables provide stable access to power and network connectivity. However, constraints imposed by cables also introduce new challenges for motion planning in these applications. This thesis focuses on planning problems for a team of tethered robots, addressing two major problems: non-crossing Anonymous Multi-Agent Path Finding (AMAPF) and Multiple Tethered Coverage Path Planning (MTCPP).

The goal of non-crossing AMAPF is to find a set of non-crossing paths such that the makespan is minimal. The study is carried out in two cases, considering whether the robots are treated as point-sized or not. This hypothesis significantly influences the computation of makespan. The problem is abstracted to the Euclidean Bipartite Assignment problem and we show that bounds can be efficiently computed by solving linear assignment problems. We introduce a variable neighborhood search method to improve upper bounds, and a Constraint Programming model to compute optimal solutions. The approach is experimentally evaluated on three different kinds of instances.

The MTCPP problem is addressed by initially partitioning the workspace into equitable connected subregions, enabling each robot to operate independently in its assigned area. We propose an approach based on the additively weighted Voronoi diagram, ensuring an equitable partitioning that enforces relative star-convexity of each subregion to the associated anchor point, thereby avoiding cable entanglement. For the coverage path planning of each robot, the Spanning Tree Coverage method is shown to effectively solve the problem while respecting cable constraints.

Building Autonomous Agents with Hybrid Navigation Policies

Doctorant : Assem SADEK

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique Et Mathématiques de Lyon

Les progrès récents de l'IA, et plus particulièrement de l'apprentissage automatique, permettent aux robots de s'intégrer de manière plus transparente dans nos habitudes quotidiennes. L'objectif de cette thèse est de faire un pas de plus vers le développement d'agents autonomes intelligents qui peuvent être intégrés dans notre environnement quotidien, comme les maisons, les hôpitaux, les centres commerciaux, etc. Ces agents devraient posséder la capacité de naviguer efficacement dans leur environnement pour atteindre un certain objectif, comme atteindre une certaine zone de l'environnement ou trouver un certain objet. C'est pourquoi nous examinons le large éventail de techniques existantes pour la construction d'un agent de navigation incarné. Ces techniques peuvent entièrement être apprises par des réseaux neuronaux (techniques basées sur l'apprentissage) ou elles peuvent être des techniques basées sur la géométrie qui reposent sur une modélisation explicite de l'agent et de son environnement. Dans cette thèse, nous construisons des approches hybrides qui utilisent les deux techniques afin de pouvoir fonctionner, non seulement dans une simulation, mais également dans un environnement physique réel. Il s'agit d'un objectif commun à toutes les contributions à ce travail.

Machine Learning Techniques for Electricity Price Forecasting

Doctorant : Léonard TSCHORA

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique et Mathématiques de Lyon

Electricity is essential for the energetic transition due to the diversity of greenhouse-gas free means of production and its potential to replace fossil fuels. However, it requires constant balance between generation and consumption, and can't be stored efficiently. Thus, it's necessary to use Price Fixing Algorithm (PFA) for developing competitive markets. Daily, Euphemia, determines the prices for the next day. Unlike other speculative markets, the price is algorithmically computed that renders its forcasts paramount for business applications. Electricity Price Forecasting consists in predicting the 24 hourly prices before their fixation at 12am. The literature highlights two incomplete approaches: expert models aim at replicating the PFA and computing the prices based on estimates of its inputs, but fail to produce accurate forecasts in practice. Data driven methods directly estimate prices using exogenous variables and past prices, but lack transparency. Also, the true relationship between variables and prices is only captured by Euphemia, implicitly limiting the performances of data driven approaches. The first challenge is to produce explainable EPF models using Shap Values, a model- agnostic explanability tool. Then, we represent the European network as a Graph where each country is a node labeled with its prices. We estimate the Graph edges using an optimization problem prior to training. With a Graph Neural Networks, we forecast prices for all markets simultanesously. Lastly, we combine the Euphemia algorithm with in a Neural Network (NN) that forecasts its inputs. To consider the price forecasting error in the NN's training, we compute the gradient of Euphemia's output with respect to its input, by vanishing the derivative of the dual function using a dichotomic search. We hope this thesis will be beneficial for the EPF practitioners and we also believe that our work on mixing optimization problems with machine learning models will benefit the broader Machine Learning community. 

Identification and Simulation of Physical Systems with Structured Deep Learning and Inductive Knowledge

Doctorant : Steeven JANNY

Laboratoire INSA : LIRIS
Ecole doctorale : ED512 Infomaths

Les progrès technologiques de notre époque sont soutenus par des outils numériques pour simuler, contrôler et observer les systèmes physiques. En se concentrant sur des phénomènes complexes, les méthodes conventionnelles ne parviennent plus à répondre aux attentes en termes de précision ou de temps de calcul. Les approches data-driven, en particulier les réseaux de neurones, offrent des alternatives pour résoudre ces problèmes. Ces modèles capturent des relations non-linéaires dans les systèmes physiques et déplacent la charge de modélisation vers celle de la collecte de données. Cependant, ces méthodes sacrifient les garanties offertes par les approches traditionnelles. Nous proposons de combiner les domaines de la physique, de l'apprentissage profond et de la théorie du contrôle pour proposer de nouvelles méthodes hybrides, tirant parti de la puissance des réseaux de neurones, tout en s'appuyant sur des biais inductifs issus de la physique. Ce manuscrit présente nos travaux dans ce domaine. En particulier, il décrit des outils théoriques (abordés dans la partie 1) liés à la simulation de systèmes dynamiques et les connecte à la conception de réseaux neuronaux. Dans un deuxième temps (Partie 2), nous exploitons ces connaissances pour concevoir des algorithmes de contrôle et des techniques de simulation impliquant la résolution de problèmes complexes liés aux équations aux dérivées partielles. Enfin, dans la troisième partie, nous abordons des problèmes de simulation à plus grande échelle tels que la dynamique des fluides et le raisonnement contrefactuel. Nos travaux ont été présentés lors de conférences scientifiques dans le domaine de l'intelligence artificielle et de la théorie du contrôle. En construisant un pont entre la physique et l’apprentissage automatique, nous croyons fermement que cette direction de recherche peut contribuer à une nouvelle génération de méthodologies pour la simulation et le contrôle des systèmes physiques.

Flowshop scheduling problem including learning and fatigue effects: theoretical contributions and case study

Doctorante : Yenny Alexandra PAREDES-ASTUDILLO

Laboratoire INSA : DISP

Ecole doctorale : ED512 : InfoMaths

Despite the rise of automation, hand-intensive production systems are still in use due to the need for workers to be extremely flexible and precise in completing certain tasks. Interest is generated by the impact of learning and fatigue on manual task productivity. The focus of this study is on a flowshop scheduling problem (FSSP) that considers the effects of learning and fatigue. Firstly, a literature review was conducted on the scheduling problem with learning and deterioration effect. After that, a theoretical approach was used to address the problem of FSSP with learning effect. Mathematical models that minimize the makespan were presented. Exact methods and heuristics were proposed for solving the problem in small and large instances. As fatigue is a type of deterioration, a multi-agent model was proposed to validate the integration of muscular fatigue into the FSSP by minimizing the total fatigue dose. Finally, the framework was validated by a case study application that took place in a manual picking line. The modeling of learning and fatigue effects and the computation of model parameters from real data were discussed. A bi-objective approach was proposed to minimize both makespan and total fatigue dose simultaneously. Break policies are recommended depending on the company's needs and the objective to prioritize. The aim of this work is to inspire future work that is interested in addressing operations research problems with a responsible incorporation of human factors.

Dynamique des génomes bactériens : une étude expérimentale in silico avec la plate-forme aevol

Doctorant : Marco FOLEY

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique et mathématiques de Lyon

Aevol est une plate-forme de simulation de l’évolution de populations d’organismes par variation et sélection. La conception du modèle est axée sur le réalisme de la structure du génome et des processus de mutations, permettant ainsi aux organismes simulés d'évoluer sur un fitness landscape comparable à celui d'organismes biologiques, avec des contraintes d’exploration similaires. Ces processus permettent l’émergence de comportements d’intérêt, pour l'étude de l'évolution de la structure des génomes, et pour produire des données de benchmarks pour tester les méthodes de phylogénie moléculaire. Les résultats obtenus jusqu’ici dans aevol concourent à suggérer que les éléments non-codants du génome sont soumis à sélection. Dans ce travail, nous avons utilisé Aevol pour mener une large campagne de simulation sur de très longues échelles de temps. Ces expériences nous permettent de montrer que la quantité de séquences non-codantes est finement régulée par deux forces contraires. La première est une force de sélection pour des génomes réduits car plus robustes face aux réarrangements chromosomiques. La seconde provient d'un biais mutationnel indirect favorisant les évènements de duplications neutres sur les délétions neutres menant à l'accumulation de non-codant par dérive génétique. Dans un deuxième temps, nous avons utilisé aevol comme outil de génération de benchmarks pour la phylogénie. En effet, Aevol ayant été développé indépendamment de la communauté de phylogénie moléculaire, il ne contient pas les a priori classiquement inclus dans les simulateurs de cette communauté, évitant ainsi la validation ad hoc des méthodes. Cependant, les séquences composant les génomes étant binaires dans Aevol, nous avons développé une version du simulateur utilisant des séquences génomiques quaternaire (ACTG). Cette nouvelle version a ensuite été utilisée pour générer des données de benchmarks afin de tester les reconstructions d'arbres phylogénétiques

 

Evolution beyond substitutions: Computational modeling of the impact of chromosomal rearrangements on evolutionary dynamics

Doctorant : Paul BANSE

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique et mathématiques de Lyon

L'évolution telle qu'elle a été décrite par Darwin est un processus simple qui aboutit à une extrême complexité. En effet, étudier l'évolution biologique aujourd'hui correspond à étudier un phénomène allant d'échelles nanométriques à des échelles planétaires. En plus de cela, le processus est aussi affecté par des biais dus à la méthode d'écriture et de conservation de l'information. Finalement, il faut rappeler que chaque changement évolutif a pour origine une mutation, qui est un évènement aléatoire, et que la survie des mutants est, elle aussi, un processus aléatoire. Face à une telle complexité, il est nécessaire de réduire le champ d'étude pour espérer aboutir à une compréhension. Que ce soit avec des modèles expérimentaux, comme les boites de pétri, avec des modèles formels, comme les équations différentielles, ou avec des modèles computationnels, par exemple des simulations, toutes les simplifications sont bonnes à prendre pour décortiquer l'évolution. Parmi ces simplifications, il est courant de ne considérer que mutations. En particulier, ignorer les réarrangements chromosomiques, ces mutations qui réorganisent et réassemblent l'ADN et qui est souvent létales pour l'organisme qui les porte, est souvent considéré comme une simplification logique des modèles d'évolution. D'autant plus que jusqu'à récemment, les séquençages d'ADN réalisés n'étaient pas adaptés à les repérer. Dans cette thèse, nous allons montrer qu'en incluant les réarrangements, bien que les modèles obtenus soient plus complexes, il est possible d'en tirer une connaissance. Nous utiliserons des méthodes algorithmiques pour étudier le processus evolutif pour montrer que non seulement les réarrangements chromosomiques sont nécessaires pour soutenir l'évolution à long terme, puisqu’ils permettent une amélioration et de nouvelles opportunités d'évolution. Mais en plus, les comprendre permet d'expliquer simplement certaines dynamiques d’évolution par à-coups ainsi que la maintenance de segments non codants dans les génomes.

Parameter-free analysis of digital surfaces with plane probing algorithms

Doctorante : Jui-Ting LU

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique Et Mathématiques de Lyon

Les volumes 3D discrets proviennent de diverses sources, notamment la segmentation d'images, la simulation numérique, et les éditeurs basés sur les voxels. Notre intérêt réside dans le traitement de la géométrie des surfaces discrètes entourant ces volumes, permettant la reconnaissance de structures locales telles que des segments de plans discrets. Cependant, les surfaces discrètes ont une géométrie pauvre, composée de surfels carrés parallèles aux axes. Pour analyser ces surfaces, des algorithmes de type plane-probing adaptent le voisinage autour d'un point en développant itérativement une approximation de plan, souvent sous forme de triangles, en fonction des informations locales. Notre objectif est d'analyser ces surfaces discrètes en utilisant les méthodes de type plane-probing.

Nous introduisons les algorithmes de type plane-probing existants dans un cadre général. De plus, nous proposons une nouvelle variante de l'algorithme de type plane-probing qui prend en compte un voisinage plus étendu que ceux des algorithmes existants. Nous proposons également une implémentation efficace de cette nouvelle variante.

Une découverte importante est que la suite de tétraèdres formée à partir de deux triangles consécutifs crée une triangulation de Delaunay dans une partie du plan discret. Cette propriété est vérifiée pour la nouvelle variante introduite. En conséquence, le triangle final retourné par l'algorithme a trois angles aigus ou droits. Ce résultat nous permet de déterminer l'étendue du voisinage considéré au cours des calculs.

Enfin, nous proposons quelques ajustements afin d'adapter ce type d'algorithme à des surfaces discrètes, permettant ainsi de déduire un estimateur de vecteurs normaux. Nous nous concentrons notamment sur la convergence multigrille de cet estimateur, qui a été observée expérimentalement pour des positions bien identifiées sur des surfaces discrètes convexes.

NAvigation en milieu MOdifiable (NAMO) étendue à des contraintes sociales et multi-robots

Doctorant : Benoit RENAULT

Laboratoire INSA : CITI
Ecole doctorale : ED512 : Infomaths

Alors que les robots deviennent toujours plus présents dans les environnements humains, endossant toujours plus de tâches telles que le nettoyage, la surveillance ou encore le service en salle, leurs limites actuelles n’en deviennent que plus évidentes. Une de ces limites concerne leur capacité à naviguer en présence d’obstacles: ils chercheront systématiquement à les éviter, et resteront bloqués à défaut. Ce constat a mené à la création d’algorithmes de NAvigation en milieu MOdifiable (NAMO), devant permettre aux robots de manipuler les obstacles pour faciliter leurs déplacements. Néanmoins, ces algorithmes ont été conçus sous l’hypothèse qu’un seul robot agîsse dans l’environnement, biaisant les algorithmes à n’optimiser que son seul coût de déplacement – sans considération pour les humains ou d’autres robots. S’il est souhaitable que les robots puissent bénéficier de la capacité humaine à déplacer des obstacles, ils doivent néamoins le faire dans le respect des normes et règles sociales humaines. Nous avons donc étendu le problème de NAMO pour prendre en compte ces nouveaux aspects sociaux et multi-robots. En nous basant sur le concept d’espaces d’affordance, nous avons développé un modèle de coût d’occupation sociale permettant d’évaluer l’impact des objets déplacés sur la navigabilité de l’environnement. Nous avons implémenté (et amélioré) des algorithmes NAMO de référence, dans notre outil de simulation open source, puis les avons modifiés afin qu’ils puissent trouver un compromis entre coût de déplacement et coût d’occupation des obstacles manipulés – résultant en une amélioration de la navigabilité. Nous avons également développé une stratégie de coordination permettant d’exécuter ces mêmes algorithmes tels quels, sur plusieurs robots en parallèle, en absence de communication explicite, tout en préservant la garantie d’absence de collisions; vérifiant la pertinence de notre modèle de coût social en présence effective d’autres robots. Ces travaux constituent les premiers pas d’une NAMO Sociale et Multi-Robots.

Nouvelles variantes et méthodes de résolution pour les problèmes de transport à la demande, application au transport d'enfants en situation de handicap

Doctorant : Timothée CHANE-HAÏ

Laboratoire INSA : DISP

Ecole doctorale : ED512 Infomaths

Cette thèse introduit de nouveaux modèles et méthodes de résolution pour les problèmes de transport à la demande (DARP). Ce travail s’applique au transport régulier d'enfants en situation de handicap entre leurs domiciles et leurs lieux de prise en charge. Pour des raisons de coûts et de qualité de service, il doit être effectué aussi efficacement que possible.
Aucune méthode de la littérature ne peut résoudre les problèmes réels car leur taille est trop importante (plusieurs milliers d'usagers). De plus, les recherches se concentrent sur l'organisation des tournées de véhicules. Cependant, l'intégration d'autres éléments gravitant autour du transport serait bénéfique pour les systèmes de santé dans leur ensemble.

Nous apportons des éléments de réponse à ces enjeux dans les trois chapitres principaux de cette thèse.
Premièrement, deux méthodes d'apprentissage automatique sont appliquées : une méthode offline extrait les caractéristiques des bonnes solutions et les utilise pour créer de nouvelles heuristiques ; une méthode online dénommée NRPA construit la meilleure séquence d'usagers à insérer.

Deuxièmement, nous présentons le problème journalier de transport à la demande (Com- DARP). Dans cette variante, chaque usager a un trajet aller le matin, un trajet retour le soir, et un temps de trajet maximal journalier. La dépendance entre les deux demandes de trajet est utilisée pour améliorer le transport à l'échelle de la journée. Nous résolvons le problème avec une métaheuristique de recherche à petit et grand voisinage couplée à un filtre de précédences (SLNS-PF).

Troisièmement, nous introduisons le problème d'affectation et transport à la demande (ADARP). Cette variante élargit le champ d'application du problème de tournées de véhicules en incluant l'affectation des usagers et l'allocation des ressources. Le problème est résolu par une nouvelle matheuristique nommée recherche itérative d'itinéraires (IRS).
Dans chaque chapitre, les résultats expérimentaux sont analysés pour fournir de nouvelles perspectives théoriques et pratiques.