Soutenance de thèse de Monsieur Algassimou DIALLO

Le 16 octobre 2025 de 10:00 à 13:00

10h00 | Polytech Angers | Amphi A | 62, avenue Notre-Dame du Lac | ANGERS

Sujet : Méthode garantie de résolution de problème d’optimisation non linéaire

Directeur de thèse : Monsieur Sébastien LAHAYE

RÉSUMÉ

Cette thèse s’inscrit dans le contexte de la localisation de robots évoluant dans un environnement. Dans ce cadre, la détermination fiable de la position de chaque robot constitue un défi majeur, en particulier lorsque seules des informations partielles sont disponibles : un pavé initial contenant la position réelle de chaque robot et des mesures de distances entachées d’erreurs entre paires de robots ou par rapport à des obstacles. Ce problème est formalisé comme un problème de satisfaction de contraintes (CSP) à 2n variables, avec des contraintes définies à la fois par les encadrements initiaux et par un système d’équations de distances euclidiennes. Les approches classiques, telles que la propagation de contraintes via des contracteurs locaux ou les méthodes ensemblistes comme SIVIA, présentent des limites importantes. En effet, le contracteur global issu de l’itération des contracteurs élémentaires n’est pas nécessairement minimal, tandis que le recours au découpage des domaines, bien qu’utile pour affiner l’approximation de l’ensemble solution, entraîne une complexité exponentielle, les rendant non praticables pour ce type d’application. L’objectif principal de cette thèse est la construction de contracteurs globalement optimaux, une problématique encore non résolue dans ce contexte. Premièrement, nous proposons une caractérisation géométrique de la frontière de l’ensemble solution du CSP n-gone. Cette caractérisation consiste à la décomposer en deux sous-ensembles de dimension 1, dont les extrémités sont des polygones particuliers que nous appelons polygone limite, permettant ainsi d’encadrer précisément la frontière. Ensuite, nous proposons une méthode de construction de contracteurs optimaux pour le CSP n-gone à distances exactes. Cette méthode repose sur la génération des polygones limites, suivie de l’union ensembliste de leurs coordonnées. Elle est d’abord appliquée au cas particulier du CSP 3-gone, avant d’être généralisée au cas n-gone. Une extension de la méthode est également proposée pour le cas du CSP 3-gone à distances intervalles, permettant de prendre en compte les incertitudes sur les distances. Enfin, une application à la localisation globale d’un robot mobile est présentée, illustrant la pertinence des contracteurs proposés.

Télécharger l'avis de soutenance de thèse