Cette thèse traite de la localisation de véhicule. Plusieurs méthodes sont utilisées pour résoudre ce type de problème. Elles peuvent être classées en deux grandes catégories d’approches : les approches probabilistes et les approches déterministes.Ce travail aborde les approches déterministes et plus précisément l'approche ensembliste basée sur l'analyse par intervalles. Les travaux ont été conduits sur des jeux de données réelles collectées en environnements d'extérieur comprenant des capteurs proprioceptifs et extéroceptifs.Lorsque l'on met en jeu plusieurs capteurs fournissant des informations complémentaires ou redondantes, il est important de fusionner les données afin d'améliorer la pose estimée. L'approche détaillée dans ce document utilise les méthodes intervalles et présente le problème de la localisation sous la forme d'un problème de satisfaction de contraintes.La résolution se fait à l'aide d’un solveur à intervalles. Plusieurs algorithmes ont été comparés. Un constat s'est dégagé : les algorithmes de consistance locale ne corrigent pas l'incertitude sur l’orientation. Cette thèse propose une méthode de localisation utilisable dans des applications temps réel et qui corrige l'incertitude sur le cap du véhicule. Nous avons comparé nos résultats à ceux du filtre de Kalman étendu (méthode probabiliste de référence) et mis en avant un des intérêts de notre méthode : l'assurance d'une consistance de la pose (position et orientation du mobile).Cette thèse propose deux contributions. La première est d'ordre méthodologique. Dans l'état de l'art tous les travaux affirment la nécessité (voire l'obligation) d'une décomposition préalable des contraintes du problème avant l'étape de résolution. Nos travaux permettent de prouver le contraire. La deuxième contribution concerne la réduction du domaine de l'incertitude en orientation en couplant la propagation de contraintes et une approche de bissection. / This thesis deals with the vehicle locationand addresses the problem of SLAM (simultaneous localization and mapping). Several methods are used to solve this kind of problem. They can be classified into two broad categories of approaches: probabilistic approach and deterministic approaches. This work addresses the deterministic approaches and more precisely the approach based on interval analysis. The work has been conducted on real data sets collected in outdoor environments with proprioceptive and exteroceptive sensors.When multiple sensors providing complementary or redundant information are put into play, it is important to merge the data to improve the estimated pose. The approach detailed in this document uses the intervals methods and presents the localization problem as a constraint satisfaction problem.The resolution is done using a solver interval. Several solvers were compared. One thing is clear: local consistency algorithms do not address the uncertainty of the orientation. This thesis proposes a method of locating usable in real time applications and corrects the uncertainty in the heading of the vehicle. We compared our results with those of the extended Kalman filter (probabilistic reference method) and highlighted one of the interests of our method: the assurance of consistency of the pose (position and orientation of the mobile).This thesis proposes two contributions. The first is methodological. In the state of the art all works affirm the need (or obligation) to pre-decompose the constraints of the problem before the resolution step. Our work allows to prove otherwise. The second contribution relates to the reduction of the orientation uncertainty by combining constraint propagation and a bisection approach.

Nos travaux portent sur la modelisation et la resolution de problemes d'optimisation combinatoire emergeant dans le cadre de la planification de missions spatiales. Ces problemes de grande taille presentent des caracteristiques communes en termes de types de donnees, de contraintes et de criteres a optimiser. Nous nous focalisons sur l'apport de la programmation lineaire pour ces problemes, associee a des methodes de simplification de l'espace de recherche, par decomposition ou grace a des techniques de propagation de contraintes. Nous avons plus particulierement etudie deux problemes. Le premier concerne la planification de communications sonde/satellite et d'experiences dans un projet d'exploration martienne. Une decomposition de ce probleme permet de le formuler comme deux problemes independants : un probleme de planification des communications que nous modelisons et resolvons par programmation lineaire en nombres entiers, et un probleme d'aide a la decision pour la planification des experiences, pour lequel nous etablissons des courbes d'evaluation de la charge des ressources deduites de l'application de techniques de propagation de contraintes basees sur un raisonnement energetique. Le second probleme etudie est celui de la planification de prises de vue d'un satellite d'observation de la Terre. Nous proposons un modele lineaire en variables mixtes et nous developpons une approche de resolution par generation de colonnes, qui est une adaptation de la programmation lineaire au traitement de problemes de grande taille, faisant appel a certaines techniques de decomposition des modeles.

Στη διπλωματική λύνουμε το πρόβλημα του sudoku με χρήση του εκπαιδευτικού ρομπότ της Lego, το LEGO Mindstorm NXT. Το εκπαιδευτικό ρομπότ αυτό δεν έχει συγκεκριμένη μορφή αλλά αποτελείται από αλληλοσυνδεόμενα μεταξύ τους πλαστικά μέρη. Με χρήση αυτών κατασκευάσαμε ένα όχημα που αποτελεί παραλλαγή οχήματος από άλλη εργασία. Το όχημα αυτό μπορεί να κινείται μόνο μπροστά και πίσω. Διαθέτει έναν βραχίονα που μπορεί να κινεί δεξιά-αριστερά και στον οποίο εφαρμόζεται ένας αισθητήρας φωτεινότητας. Τέλος, στον βραχίονα υπάρχει θέση για στυλό. Το πρόβλημα του sudoku που δίνεται στο ρομπότ είναι εκτυπωμένο σε ένα χαρτί Α4. Το ρομπότ αναλαμβάνει να το αναγνωρίσει με τον αισθητήρα, να το επιλύσει και να το αποτυπώσει με τη χρήση του στυλό. Για την επίτευξη αυτού του στόχου επιστρατεύονται αλγόριθμοι ρομποτικής και αλγόριθμοι τεχνητής νοημοσύνης. Συγκεκριμένα για την πλοήγηση του οχήματος εφαρμόζεται μετρική και τοπολογική πλοήγησης, στη συνέχεια για την αναγνώριση του προβλήματος και την ταυτοποίηση κάθε εικόνας που λαμβάνεται υλοποιήσαμε αλγόριθμους μορφολογικής επεξεργασία και τέλος για την επίλυση του προβλήματος sudoku υλοποιήσαμε και συγκρίναμε δύο αλγόριθμους, την αναζήτησης κατά βάθος και την αναζήτηση κατά βάθος με διάδοση περιορισμών. Οι τελικοί αλγόριθμοι που αναπτύχθηκαν διαπιστώσαμε ότι πετυχαίνουν το σκοπό τους αφού το όχημα αναγνωρίζει τους αριθμούς του δοσμένου προβλήματος με ποσοστό επιτυχίας 95%, λύνει τα περισσότερα προβλήματα σε λιγότερο από ένα δευτερόλεπτο και συμπληρώνει επιτυχώς τα κελιά του sudoku με τους σωστούς αριθμούς. Πέρα από αυτές τη σύγκριση των αλγορίθμων θεωρούμε ότι η μελέτη ενός τέτοιου συστήματος είναι ιδανική για εισαγωγή σε θέματα ρομποτικής και μπορεί να χρησιμοποιηθεί ως εκπαιδευτικό εργαλείο πειραματισμού. Μάλιστα ο κώδικας μας σχολιάζεται επαρκώς σε αυτή την εργασία για να είναι ευκολότερη η κατανόηση του. Εκτός αυτού έχουμε αναπτύξει και πρόγραμμα αλληλεπίδρασης χρήστη-ρομπότ μέσω κονσόλας. / We solve the problem of sudoku using the educational robot LEGO Mindstorm NXT, made by LEGO. This educational robot doesn't have specific form but consists of interlinked plastics. We constructed a vehicle that is a variant from another work. This vehicle can move only forward and back. It has an arm that can move side to side and is equipped with a light sensor and a marker. The problem of sudoku is given to the robot in printed form on a A4 paper. The robot at first recognize the problem with the sensor, then it resolves it and finally writes the solution down by using the pen. To achieve this goal we implemented various algorithms. Specifically, we studied robotic algorithms such as metric and topological navigation. Moreover, to identify the printed problem we processed every captured image morphologically and finally to solve the sudoku instance we implemented and compared two methods, first-depth search and first-depth search with constraint propagation. We should mention that our code is written in Java for the lejOS firmware. The final code is capable of recognizing the numbers of the given problem with a success rate of 95%, solving most problems in less than a second and completing the cells on the paper with the correct numbers. Finally, we have developed an accompanying program that is usable for debugging purposes and for calibrating the robot. Even more, it can be used as education tool.