Présentation
 
Expérimentations
 
Téléchargements
 
Sujet de master recherche présenté par:
Antoine Durand

Implémentation d'un algorithme de localisation globale par calculs ensemblistes

Tuteur:

R. Guyonneau

Titre:
Implémentation d'un algorithme de localisation globale par calculs ensemblistes
Mots clés:
Analyse par intervalles, kidnapping, localisation globale, développement C++, Robot mobile autonome
Résumé:
La localisation est un problème majeur en robotique mobile. Dans le but d'accomplir un nombre de tàąches (par exemple : l'exploration, la cartographie, ...), un robot autonome doit-être capable de se localiser lui même dans son environnement et de résoudre une situation de kidnapping. Les GPS ne fonctionnant pas dans un milieu intérieur, il devient nécessaire de développer d'autres moyens de localisation. Un algorithme original a été développé : IAL (Interval Analysis Localization), mais cet algorithme fonctionne seulement sur simulateur. Les travaux décrits ci-après montrent l'implémentation de cet algorithme sur un robot, le MiniRex. Nous verrons également différentes expérimentations dans des environnements réels, montrant ainsi la capacité de cet algorithme à  fonctionner dans des conditions d'opérations réelles.

Présentation:

La localisation est un problème majeur en robotique mobile. Afin de pouvoir accomplir un certain nombre de tàąches (exploration, cartographie, ...) un robot autonome doit être capable de se localiser dans son environnement. Disposant d'une carte, la localisation consiste à  trouver la posture (position et orientation) d'un robot. Le GPS n'étant pas exploitable en milieu intérieur il devient alors nécessaire de mettre en place d'autres moyens de localisation.
Ce problème peut être divisé en trois sous-problèmes :

La localisation globale : On n'a aucune idée de la position ni de l'orientation initiale du robot dans l'environnement.
Le suivi de position : On connaît maintenant la posture initiale du robot, le but est de la suivre au cours du temps, en prenant en compte les mesures et le déplacement du robot.
Le kidnapping : Le robot est déplacé sans en avoir conscience (déplacement non-planifié). Il doit alors être capable de détecter cette situation.

On représente la posture (ou configuration) du robot de la façon suivante :


avec
s, la posture du robot (x,y,θ)
u, le vecteur des relevés odométriques
z, le vecteur des mesures
On commence par estimer la posture du robot en fonction de la dernière posture connue et des relevés odométriques, c'est ce qu'on appelle l'étape de prédiction. Puis on ajuste cette posture en fonction des mesures obtenues, c'est l'étape de correction.

Les principales méthodes de localisations mises en place sont basées sur une approche probabiliste (voir rapport de Mars 2013), mais ces méthodes ne permettent pas de garantir une solutions. C'est pourquoi un algorithme original a été developpé au sein du LISA, basé sur une approche ensembliste. Cette approche qui contraste avec l'approche probabiliste est basé sur l'analyse et le calcul par intervalle.

Algorithme étudié:

IAL (Interval Analysis Algorythm)

Cet algorithme recherche une boîte contenant la posture du robot (position + orientation), pour cela, il utilise les outils de l'analyse par intervalles ainsi que la résolution d'un problème de satisfaction de contraintes.

La satisfaction de contraintes permet de réduire l'ensemble des solutions en utilisant la propagation et la rétro-propagation de contraintes, comme le montre l'animation ci-dessous.
Etape 1 : On récupère une mesure et on la positionne dans le repère du robot.
Etape 2 : On propage l'incertitude sur la posture du robot à  la mesure.
Etape 3 : On applique une série de contracteurs qui permettent de gagner en précision sur la position de la mesure.
Etape 4 : On rétro-propage les informations gagnées afin d'affiner la posture du robot.

Implémentation

Cet algorithme a été développé sur un simulateur, mais n'a jamais été implémenté sur une plateforme robotique. L'objectif de ce stage consistait à  implémenter et optimiser cet algorithme sur un robot : le robot MiniRex, afin de pouvoir le tester en conditions réelles. Le robot MiniRex fait partie d'une flotille de 6 robots conçu par l'équipe Cart-O-Matic dans le cadre du challenge CAROTTE. Il est équipé pour les mesures d'un télémètre laser permettant d'acquérir des mesures avec une précision de plus ou moins 30mm et d'un PC embarqué doté d'un processeur cadencé à  1.6GHz pour les calculs.