Pour qu'un robot autonome puisse interagir proprement avec son milieu, ce dernier doit connaitre d'une part l'environnement dans lequel il évolue et d'autre part son état dans cet environnement. En particulier, un robot doit savoir où il est pour savoir où il doit aller. Depuis l'apparition du GPS, le problème de la localisation a été pratiquement résolu pour les robots terrestres. Le GPS ne fonctionne pas sous l'eau. Toutefois, le nombre d'opérations sous-marines augmente de manière significative chaque année. Dans notre école, nous développons un robot sous-marin pour tester des systèmes de localisation sous-marins. Le capteur principal que nous utilisons est un sonar sectoriel. Un sonar est un capteur acoustique qui positionne les objets acoustiquement réfléchissant. Par exemple, le sonar peut être utilisé pour détecter les parois d'un port. Ce capteur donne souvent des mesures aberrantes. Une telle mesure peut être due à une défaillance électrique du capteur ou d'un phénomène non pris en compte lors de la modélisation de l'environnement. Le nombre de mesures aberrantes est souvent inconnu et varie avec le temps. Le but de la thèse est de résoudre le problème de localisation avec de telles données. Un problème de localisation peut être formulé en tant que problème de satisfaction de contraintes (CSP en anglais). Un CSP est en gros un système d'équations (contraintes). Ici, l'inconnu est la pose du robot. Pour chaque mesure on obtient une contrainte reliant la pose, la mesure et l'environnement. La solution classique d'un CSP est l'ensemble des points (poses) qui satisfont toutes les contraintes. Toutefois, a cause des données aberrantes de tels points peuvent ne pas exister. Le nouveau problème consiste à trouver une solution d'un CSP lorsque une partie seulement de contraintes est satisfaite. Nous appelons ce problème un CSP relaxé. Une des contributions majeures à la thèse était de trouver plusieurs représentations de la solution d'un CSP relaxé ainsi que les algorithmes qui permettent de calculer ces solutions. La première représentation est sous la forme d'un polynôme dont les coefficients sont des ensembles que nous appelons polynômes ensemblistes. Chaque coefficient correspond à l'ensemble des points qui satisfont le nombre de contraintes égal au degré du coefficient dans le polynôme. Une telle représentation permet d'utiliser l'arithmétique des polynômes pour calculer le polynôme solution. Une deuxième représentation est sous la forme d'une fonction, qu'on appelle accumulateur, qui pour chaque élément de l'espace de recherche retourne le nombre de contraintes satisfaites. Un des obstacles à surmonter pour résoudre les problèmes de localisation est la représentation de la carte. En cas d'environnements structurés, il est possible de représenter la carte par un ensemble d'objets paramétrés tels que des segments, polygones ou des courbes. En cas d'environnements non structurées où en partie structurées tels que des cartes marines ou des cartes routières, l'idée est de représenter la carte (qui est en fait un ensemble de points) sous la forme d'une image binaire où les pixels d'intérêt (noir par exemple) représentent l'ensemble des points de la carte. Une des contributions majeures de la thèse était d'incorporer une telle représentation de la carte dans le formalisme d'un CSP ou d'un CSP relaxé sous la forme d'un contracteur appelé le contracteur sur l'image. L'utilité de ces deux contributions est montrée par un exemple de localisation d'un vrai robot dans une marina abandonnée. La thèse contient plusieurs autres contributions aux méthodes ensemblistes et la théorie des contracteurs.