View
286
Download
0
Category
Preview:
Citation preview
République Algérienne Démocratique & Populaire
Ministère de l’Enseignement Supérieur & de la Recherche Scientifique
Université Abderrahmane Mira - Bejaïa
Faculté de la Technologie
Département de Génie Electrique
Projet final pour l’obtention du grade de MASTER
En : ELECTRONIQUE
Option : AUTOMATIQUE
Sujet :
Développement et implémentation d’une
méthode de localisation basée SLAM
Par : Hachemi BOUICHE
Encadré et dirigé par : Devant le jury composé de :
Mr. Boubekeur MENDIL Mr. Hocine HADDAR
Mr. A.Oualid DJEKOUNE Mr. Kamel BOUDJELLABA
Juin 2012
À mes chers parents,
À mes frères & sœurs,
À la mémoire de nos martyrs.
i
Avant propos
Les travaux présentés dans ce projet ont été effectués au sein de l’équipe de recherche
« Vision Artificielle & ANalyse d’IMage », de la division « Productique & Robotique », du
Centre de Développement des Technologies Avancées (CDTA) à Alger, Baba Hassen.
Honneur à ceux qui sont à l'origine de ce travail, je parle bien évidemment de Mr.
A.Oualid DJEKOUNE. Sans sa confiance qu'il m'a accordée, sans son aide, sans ses conseils,
rien de cette aventure n'aurait existé.
J'exprime ma sincère reconnaissance à Mr. MENDIL Boubekeur professeur à l’université
de Bejaïa pour l'honneur qu'il m'a fait de me diriger, en acceptant ce travail et de le valider.
Mes remerciements vont également à tous ceux qui ont permis de loin ou de près, de
contribuer à l'aboutissement de ce travail et à tous les membres de la division « Productique &
Robotique » pour l'ambiance de travail.
Un remerciement particulier pour mes parents, mes sœurs, ainsi qu’à toute ma famille
pour m’avoir donné la force d’aller au bout de ce travail, pour leur patience et leur amour.
ii
Table des matières
Avant propos i
Liste des figures v
Liste des tableaux vii
Liste des abréviations viii
Présentation générale 1
I. Contexte général 1
II. Problématique traitée 2
III. Plan du mémoire 3
Chapitre I. Modélisation & perception des systèmes de robotique mobile
I.1. Introduction .......................................................................................................................... 4
I.2. Modélisation des systèmes de robotique mobile.................................................................. 4
I.2.1. Disposition des roues..................................................................................................... 4
I.2.2. Robot mobile différentiel .............................................................................................. 6
I.2.3. Robot mobile tricycle .................................................................................................... 8
I.2.4. Robot mobile de type voiture ...................................................................................... 10
I.2.5. Robot mobile omnidirectionnel ................................................................................... 12
I.2.6. Robot mobile à traction synchrone.............................................................................. 13
I.2.7. Holonomie et non holonomie ...................................................................................... 17
I.3. Perception des systèmes de robotique mobile.................................................................... 18
I.3.1. Capteurs proprioceptifs ............................................................................................... 19
I.3.1.1. Les capteurs de déplacement ................................................................................ 19
I.3.1.1.1. Les odomètres ................................................................................................. 19
I.3.1.1.2. Les accéléromètres .......................................................................................... 20
I.3.1.1.3. Le radar Doppler ............................................................................................. 21
I.3.1.2. Capteurs d’attitude ................................................................................................ 21
I.3.1.2.1. Les gyroscope, gyromètre et gyrocompas ...................................................... 22
I.3.1.2.2. Les magnétomètres ......................................................................................... 22
I.3.2. Capteurs extéroceptifs ................................................................................................. 22
iii
I.3.2.1. Les capteurs télémètriques ................................................................................... 23
I.3.2.1.1. Les capteurs ultrasons ..................................................................................... 23
I.3.2.1.2. Les capteurs infrarouges ................................................................................. 24
I.3.2.1.3. Les capteurs lasers .......................................................................................... 25
I.3.2.1.4. GPS (Global positioning system)................................................................. 26
I.3.2.1.5. Les caméras..................................................................................................... 28
I.4. Conclusion.......................................................................................................................... 29
Chapitre II. Localisation & cartographie des systèmes de robotique mobile
II.1. Introduction....................................................................................................................... 30
II.2. Localisation des systèmes de robotique mobile................................................................ 30
II.2.1. Localisation relative (à l’estime) ................................................................................ 31
II.2.2. Localisation absolue................................................................................................... 31
II.2.3. Localisation hybride................................................................................................... 32
II.3. Cartographie des systèmes de robotique mobile............................................................... 32
II.3.1. Représentations métriques ......................................................................................... 33
II.3.2. Représentation topologique........................................................................................ 34
II.4. Localisation et cartographie simultanées (SLAM) ............................................................ 35
II.5.1. L’objectif du scan matching ....................................................................................... 37
II.5.2. Les approches de scan matching ................................................................................ 38
II.6. Conclusion ........................................................................................................................ 39
Chapitre III. La technique ICP (Itérative Closest Point) basée SLAM
III.1. Introduction .................................................................................................................... 40
III.2. La plateforme utilisée : Robot mobile B21R (iRobot)..................................................... 40
III.2.1. Architecture matérielle ............................................................................................. 40
III.2.2. Architecture logicielle .............................................................................................. 43
III.3. Génération de points par le télémètre Laser .................................................................... 43
III.4. L’algorithme ICP – Iterative Closest Point .................................................................... 45
III.4.1. Projection du nouveau scan ........................................................................... 46
III.4.2. L’association de données .......................................................................................... 47
III.4.3. Estimation de la position .......................................................................................... 48
III.4.4. Résultats de validation de l’algorithme ICP ............................................................. 50
iv
III.5. L’algorithme ICP basé SLAM ......................................................................................... 52
III.5.1. Résultats de validation de SLAM-ICP ..................................................................... 53
III.5.2. L’algorithme SLAM-ICP proposé pour le rejet des mauvaises correspondances .... 55
III.5.3. Résultats de validation de SLAM-ICP proposé ........................................................ 57
III.5.3.1. Première scène de l’expérience .......................................................................... 57
III.5.3.2. Deuxième scène de l’expérience ........................................................................ 58
III.5.3.3. Troisième scène de l’expérience ........................................................................ 59
III.5.5. Discussion ................................................................................................................. 60
III.6. Conclusion ....................................................................................................................... 61
Conclusion Générale & perspectives 62
Annexes ix
Référence bibliographique xii
v
Liste des figures
Figure.I.1. Les principaux types de roues pour la robotique mobile ......................................... 5
Figure.I.2. Robot mobile différentiel ......................................................................................... .6
Figure.I.3. Robot mobile différentiel ATRV2 du CDTA ............................................................. 6
Figure.I.4. Centre instantané de rotation d’un robot mobile différentiel .................................. 7
Figure.I.5. Robot mobile tricycle ............................................................................................... 8
Figure.I.6. Robot mobile tricycle de Carnegie Mellon University ............................................. 9
Figure.I.7. Centre instantané de rotation d’un robot mobile tricycle ........................................ 9
Figure.I.8. Robot mobile de type voiture de Carnegie Mellon University DARPA ................. 11
Figure.I.9. Centre instantané de rotation d’un robot mobile type voiture ............................... 11
Figure.I.10. Robot mobile omnidirectionnel ............................................................................ 12
Figure.I.11. Robot mobile omnidirectionnel le Nomad XR4000 .............................................. 13
Figure.I.12. Robot mobile à traction synchrone B21R du CDTA ............................................ 14
Figure.I.13. Roue décentrée orientable.................................................................................... 14
Figure.I.14. Centre instantané de rotation du B21R ................................................................ 15
Figure.I.15. Disposition des quatre roues du robot mobile B21R ........................................... 16
Figure.I.16. Modèle cinématique du robot mobile B21R ......................................................... 17
Figure.I.17. Principe du capteur à effet Doppler..................................................................... 21
Figure.I.18. Capteur ultrason ME007...................................................................................... 23
Figure.I.19. La distribution de l’intensité d’un capteur ultrason [2] ...................................... 24
Figure.I.20. Capteurs Infrarouge Sharp GP2D120 ................................................................. 24
Figure.I.21. Laser SICK 180° (a) , Lidar 360° (b)................................................................... 25
Figure.I.22. Schéma de la télémétrie laser par déphasage de mesure [2] .............................. 26
Figure.I.23. Calcul de la position et le cap basé sur le GPS [2] ............................................. 27
Figure.I.24. Récepteur GPS ..................................................................................................... 28
Figure.II.1. Boucle de navigation autonome des robots mobiles ............................................. 30
Figure.II.2. Carte géométrique représentant un hall ............................................................... 33
Figure.II.3. Grille d’occupation [2] ......................................................................................... 34
Figure.II.4. (a) modèle réel, (b) Carte topologique ................................................................. 35
Figure.II.5. Architecture générale du SLAM............................................................................ 36
Figure.II.6. Localisation relative du robot utilisant deux scans consécutifs [17] ................... 38
vi
Figure.II.7. scan matching : (a) local et (b)global................................................................... 39
Figure.III.1. La structure matérielle du robot B21R ................................................................ 41
Figure.III.2. La structure matérielle de la console B21R ........................................................ 42
Figure.III.3. La position de l’obstacle P dans la référence du robot pour ..... 44
Figure.III.4. Les coordonnées cartésiennes et polaires d’un scan Laser ................................ 44
Figure.III.5. Objectif de l’ICP .................................................................................................. 45
Figure.III.6. Organigramme de l’ICP ...................................................................................... 46
Figure.III.7. La mise en correspondance ................................................................................. 48
Figure.III.8. Alignement des deux scans .................................................................................. 51
Figure.III.9. Evolution des paramètres ( ................................................................... 51
Figure.III.10. Evolution de l’erreur quadratique moyenne (MSE) de l’ICP ........................... 51
Figure.III.11. Fusion de la carte locale ................................................................................... 52
Figure.III.12. Organigramme SLAM-ICP ................................................................................ 53
Figure.III.13. Environnement réel de la première scène (indoor) ........................................... 54
Figure.III.14. La carte globale & trajectoire données par l’odométrie et par SLAM-ICP ..... 55
Figure.III.15. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP de la dernière
position ..................................................................................................................................... 55
Figure.III.16. (a) Lorsque deux scans à aligner ne chevauchent pas complètement (comme
c'est le cas pour la plupart des données réelles), ce qui donne des correspondances des
points sur les extrémités des scans qui peuvent introduire un biais systématique
dans l'alignement. (b) Interdire de telles paires en rejetant un grand nombre de ces mauvaises
correspondances [28]............................................................................................................... 55
Figure.III.17. La carte globale & trajectoire données par l’odométrie et par SLAM-ICP
proposé (première scène) ......................................................................................................... 58
Figure.III.18. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la
dernière position (première scène)........................................................................................... 58
Figure.III.19. Environnement réel de la deuxième scène (indoor) .......................................... 59
Figure.III.20. La carte globale & trajectoire donnée par l’odométrie et par SLAM-ICP
proposé (deuxième scène)......................................................................................................... 59
Figure.III.21. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la
dernière position (deuxième scène) .......................................................................................... 59
Figure.III.22. Environnement réel de la troisième scène (indoor)........................................... 60
Figure.III.23. La carte globale & trajectoire donnée par l’odométrie et par SLAM-ICP
proposé (troisième scène) ......................................................................................................... 60
Figure.III.24. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la
dernière position (troisième scène)…………………………………………………………………..60
vii
Liste des tableaux
Tableau.III.1. Pseudo-code de l’association de données ......................................................... 48
Tableau.III.2. Tableau comparatif entre les valeurs obtenues par l’odométrie et ICP ........... 52
Tableau.III.3. Pseudo-code de la méthode d’optimisation de SLAM-ICP………………………62
viii
Liste des abréviations
CDTA: Centre de développement des technologies avancées
CCD: Changed coupled device
CIR: Centre instantané de rotation
CML: Concurrent mapping and localization
CMOS: Complementary metal oxide semiconductor
EKF: Extended Kalman Filter
GPS: Global positioning system
ICP: Itérative Closest Point
IDC: Iterative dual correspondances
MSE : Mean square error
NDT: Normal Distributions Transform
NMEA: National maritime électronique association
NN: Nearest Neighbour
SLAM: Simultaneous Localization and Mapping
SVD: Décomposition en valeurs singulières
Présentation générale
1
Présentation générale
I. Contexte général
La principale ligne actuelle de recherche pour la robotique mobile est de permettre à un
système robotique mobile (système mobile ou robot mobile) de se déplacer de manière
autonome dans son environnement pour accomplir un certain nombre de tâches. Ces tâc hes
sont, par exemple, se déplacer vers une cible fixe ou mobile, éviter les obstacles, accoster,
suivre une route, explorer et intervenir dans un milieu hostile. Pour cela, les problèmes à
résoudre sont parfois assez complexes. L’un d’eux est la détermina tion d’une représentation
interne de l’environnement (carte) du système mobile au moyen de la perception pour
permettre la planification des actions et le contrôle de l’exécution. Le choix de la
représentation est essentiel. Cette représentation doit être adaptée à la tâche du système
mobile mais aussi à l’environnement dans lequel il évolue.
Le type d’environnement dans lequel devra se déplacer le système mobile détermine bien
entendu le type de capteurs à utiliser pour la perception. De très nombreux capteurs sont
utilisables : des caméras, des prosimètres, et des capteurs tactiles, etc. Mais aucun d’entre eux
ne peut à lui seul rendre compte de tout ce que le système mobile doit connaître sur le monde
qui l’entoure. La perception de chacun d’eux est partielle et entachée d’erreurs. La solution
consistera donc, à faire coopérer un grand nombre de capteurs. Cette coopération entre
capteurs est très intéressante, voire indispensable pour la réalisation des objectifs de la
perception. Elle peut se faire entre des capteurs de nature différente (vision et capteurs
acoustiques, par exemple) permettant la perception de caractéristiques totalement différentes
des objets, ou de même type, placés à différents endroits diminuant ainsi les problèmes de
résolution, de champ de vue ou dus à l’occultation [1].
Un autre problème en relation avec la perception est celui de la localisation du système
mobile dans la carte produite à partir des éléments perçus de l’environnement. Elle consiste à
calculer et à maintenir à jour la connaissance de la position et de l’orientation du système
mobile dans un repère absolu lié à son environnement. Ensuite, un itinéraire entre la position
calculée du système mobile et son but, généré grâce à des outils de planification de c hemins,
peut enfin être exécuté, ce qui amène le système mobile à évoluer dans son environnement.
Présentation générale
2
La tache la plus délicate et d’estimer le mouvement d’un robot et construire en même
temps une représentation de l’environnement (problème connu sous le nom de SLAM :
Simultaneous Localisation And Mapping) est souvent considéré comme un problème essentiel
pour développer des robots pleinement autonomes qui ne nécessitent pas de connaissances a
priori de l’environnement pour réaliser leurs taches [2].
L’évolution du SLAM est très liée aux capteurs utilisés. Les sonars avec l’odométrie sont
souvent présentés comme les premiers capteurs ayant fourni des résultats convaincants.
Depuis, les lasers 2D ont souvent remplacées ces capteurs pour des raisons de précision et de
rapport signal/bruit. Néanmoins les lasers 2D permettent d’estimer des mouvements
planaires.
C’est dans ce contexte que se situent les travaux de notre projet. Le but est de développer
une méthode de localisation basée SLAM. En particulier, il sera nécessaire de modéliser et de
construire la carte de l’environnement à partir de données issues des capteurs de perception du
robot (Scanner Laser 2D) dans le but de se localiser dans son milieu de navigation.
II. Problématique traitée
Pour un système mobile se déplaçant dans un environnement inconnu, l’autonomie de
déplacement devient un problème encore plus difficile à résoudre que dans le cas où le
système mobile évolue dans un environnement parfaitement connu. La localisation autonome
doit pouvoir répondre aux deux questions que nous nous posons tous inconsciemment lorsque
nous utilisons nos véhicules :
Où suis-je ?
Où dois-je aller ?
La méthode SLAM est la solution parfaite de nos jours pour remédier à ce problème en
robotique mobile, et pour effectuer cette tache autonome, le robot mobile doit :
Posséder un (ou des) capteurs(s) proprioceptif(s) et extéroceptif(s).
Etre capable de se localiser et construire la carte dans cet environnement.
Présentation générale
3
III. Plan du mémoire
Ce mémoire se divise en trois chapitres :
Le premier chapitre est un état de l'art concernant tous les points pour l’intégration de la
modélisation et systèmes de perception des robots mobile. Les différents types de robots
mobiles existants de nos jours, ainsi les capteurs disponibles sur le marché.
Le deuxième chapitre passe en revue les principales méthodes de localisation et de la
représentation de l’environnement, et aborder le principe de SLAM, nous trouvons aussi, les
différentes approches du scan matching (appariement).
Le troisième chapitre traite la technique SLAM développée basée sur la méthode ICP, et
l’ensemble des résultats obtenus, Nous évoquons ensuite quelques perspectives que nous
trouvons les plus intéressantes pour la suite de ces travaux.
Chapitre I
Modélisation & perception des systèmes de
robotique mobile
Chapitre I Modélisation & perception des systèmes de robotique mobile
4
I.1. Introduction
De manière générale, on regroupe sous l’appellation robots mobiles l’ensemble des robots
à base mobile, par opposition notamment aux robots manipulateurs. L’usage veut néanmoins
que l’on désigne le plus souvent par ce terme les robots mobiles à roues. Les autres robots
mobiles sont en effet le plus souvent désignés par leur type de locomotion, qu’ils soient
marcheurs, sous-marins ou aériens.
On peut estimer que les robots mobiles à roues constituent la grande partie des robots
mobiles. Historiquement, leur étude est venue assez tôt, suivant celle des robots
manipulateurs. Leur faible complexité en a fait de bons premiers sujets d’étude pour les
roboticiens intéressés par les systèmes autonomes. Cependant, malgré leur simplic ité
apparente, ces systèmes ont soulevés un grand nombre de problèmes difficiles, nombreux de
ceux-ci ne sont d’ailleurs toujours pas résolus. Néanmoins, l’intérêt indéniable de la robotique
mobile est d’avoir permis d’augmenter considérablement nos connaissances sur la localisation
et la navigation de systèmes autonomes.
Néanmoins, l’intérêt indéniable de la robotique mobile est d’avoir permis d’augmenter
considérablement nos connaissances sur la localisation et la navigation de systèmes
autonomes à l’aide de ses capteurs embarqués. La gamme des problèmes potentiellement
soulevés par le plus simple des robots mobiles à roues en fait un sujet d’étude à part entière et
forme une excellente base pour l’étude de systèmes mobiles plus complexes.
Ce chapitre a pour objectif de définir la modélisation des différents types de robots
mobiles à roues à savoir les plus utilisés en robotique mobile, ainsi que leurs caractéristiques
cinématiques. Comme cas particulier, l’étude cinématique de notre plateforme le robot mobile
B21R est accomplie. Enfin, ce chapitre introduit aussi la notion de l’holonomie et la non
holonomie. Nous présentons aussi les différents types de capteurs utilisés dans les systèmes
de robotique mobile disponibles sur le marché.
I.2. Modélisation des systèmes de robotique mobile
I.2.1. Disposition des roues
C’est la combinaison du choix des roues et de leur disposition qui confère à un robot son
mode de locomotion. On rencontre principalement quatre types de roues (Figure.I.1) :
Chapitre I Modélisation & perception des systèmes de robotique mobile
5
les roues fixes dont l’axe de rotation passe par le centre de la roue, tandis que l’axe
d’orientation est constant (Figure.I.1 (a)).
les roues centrées orientables dont l’axe d’orientation passe par le centre de la roue.
(Figure.I.1 (b)).
les roues décentrées orientables souvent appelées roues folles, pour lesquelles l’axe
d’orientation ne passe pas par le centre de la roue (Figure.I.1 (c)).
Les roues suédoises dont la bande de roulement a été remplacée par des galets inclinés
par rapport à la normale au plan de la roue. C’est la combinaison de la rotation de la
roue avec la rotation libre du galet en contact avec le sol qui permet un déplacement
sans glissement dans toutes les directions (Figure.I.1 (d)).
(a) Roue fixe (b) Roue centrée orientable
(d) Roue suédoise (c) Roue décentrée orientable
Figure 1.2 : Les principaux types de roues pour robots mobiles
Axe d’orientation
P
r
P
r
Axe de rotation
P r
Axe d’orientation
P
r
d
Figure.I.1. Les principaux types de roues pour la robotique mobile [1]
Ces quatre types de roues sont les plus utilisés en robotique mobile et n’empêche qu’il en
existe d’autres tels que les roues sphériques connues pour leur propriété omnidirectionnelle.
Bien évidemment, pour un ensemble de roues données, toute disposition ne conduit pas à une
solution viable. Un mauvais choix peut limiter la mobilité du robot ou occasionner
d’éventuels blocages.
Chapitre I Modélisation & perception des systèmes de robotique mobile
6
I.2.2. Robot mobile différentiel
Une des configurations les plus utilisées pour les robots mobiles est la configuration
différentielle (differential drive) qui comporte deux roues fixes non orientables commandées
indépendamment Une ou plusieurs roues folles sont ajoutées à l’avant ou à l’arrière du robot
pour assurer sa stabilité, n’empêche qu’il existe certains robots différentiels avec quatre roues
commandées indépendamment sauf qu’ils sont modélisés en deux roues. Le schéma du robot
différentiel est présenté à la (Figure.I.2). On y a omis les roues folles, parce qu’ils
n’interviennent pas dans la cinématique, mais ils assurent juste l’équilibre.
Figure.I.2. Robot mobile différentiel
Ce type de robot est très répandu en raison de sa simplicité de construction et de ses
propriétés cinématiques intéressantes, comme sa capacité à tourner sur lui même. La
(Figure.I.3) présente un exemple d’un robot mobile différentiel.
Figure.I.3. Robot mobile différentiel ATRV2 du CDTA
Les roues motrices ayant même axe de rotation, le CIR (centre instantané de rotation) du
robot est un point de cet axe. Soit R le rayon de courbure de la trajectoire du robot, c’est-à-
dire la distance du CIR au point O (Figure.I.4). Soit 2L la distance qui sépare les deux roues,
Chapitre I Modélisation & perception des systèmes de robotique mobile
7
et la vitesse angulaire du robot par rapport au CIR. Alors les vitesses des roues droite et
gauche, respectivement notées dv et gv vérifient :
)( LRdv (I.1)
)( LRgv (I.2)
Ce qui permet de déterminer R et à partir des vitesses des roues :
L
gd vv
2 (I.3)
gd
gd
vv
vvLR (I.4)
La vitesse linéaire v du robot au point O est :
2
gd vvv (I.5)
La vitesse de rotation du robot est égale à la vitesse de rotation autour du CIR :
L
gd vv
2
.
(I.6)
L’équation (I.4) permet de situer le CIR sur l’axe des roues. Par ailleurs ces équations
expliquent deux propriétés particulières du mouvement des robots différentiels : si gd vv , la
vitesse angulaire sera nulle et le rayon de courbure R est infinie et le robot se déplace en
ligne droite ; si gd vv , 0 et R est nulle alors le robot effectue une rotation sur lui-
même. Cependant dans le cas où gd vv le déplacement du robot est un virage à gauche ou à
droite selon que dv soit supérieur ou inférieur à gv (dans une direction qui correspond à la
vitesse inférieur).
L’utilisation de ce mode de locomotion, fournie une solution simple pour amener le robot
d’une position à l’autre. C’est sans doute là une des raisons du succès de ce type de robots.
Figure.I.4. Centre instantané de rotation d’un robot mobile différentiel
Chapitre I Modélisation & perception des systèmes de robotique mobile
8
Le modèle cinématique du robot différentiel est donné par les équations suivantes :
cos.
vx (I.7)
sin.
vy (I.8)
.
(I.9)
Ces équations relient la dérivée de la position ),,( yx du robot à la commande Tvu ),( ,
avec rotation instantanée du robot par rapport au repère (O, X, Y). De ce fait, la position du
robot est donnée par :
t
dtx v0
))(cos()()( (I.10)
t
dty v0
))(sin()()( (I.11)
t
dt0
)()( (I.12)
I.2.3. Robot mobile tricycle
L’architecture d‘un robot mobile tricycle est représentée dans la (Figure.I.5). Ce robot est
constitué de deux roues fixes (passives) de même axe et d’une roue centrée orientable placée
sur l’axe longitudinal du robot. Le mouvement est conféré au robot par deux actions: la
vitesse longitudinale et l’orientation de la roue orientable.
Figure.I.5. Robot mobile tricycle
Un exemple de robots tricycles est représenté dans la (Figure.I.6). Ce type de robot
possède les mêmes propriétés cinématiques que le robot de type bicycle, sauf que celui-ci est
constitué d’une seule roue fixe passive et une roue centrée orientable.
Chapitre I Modélisation & perception des systèmes de robotique mobile
9
Figure.I.6. Robot mobile tricycle de Carnegie Mellon University
Le CIR du robot se situe à l’intersection des axes des roues fixes et de la roue orientable.
Figure.I.7. Centre instantané de rotation d’un robot mobile tricycle
On peut déterminer R de manière géométrique à partir de l’angle d’orientation de la roue
avant et à partir de la vitesse linéaire v du robot (vitesse enO ) et de R :
tan
DR (I.13)
tan
D
v (I.14)
La vitesse linéaire v est une fonction de la vitesse linéaire de la roue orientable Sv :
cosSvv (I.15)
Ce type de robot peut se diriger en ligne droite pour 0 et théoriquement tourner autour du
point O (sur lui-même) pour2
. Néanmoins, le rayon de braquage de la roue orientable,
Chapitre I Modélisation & perception des systèmes de robotique mobile
10
généralement limité, impose le plus souvent des valeurs de telles que22
,
interdisant cette rotation du robot sur lui-même.
L’écriture des contraintes sur chacune des roues est un raisonnement similaire à celui
suivi dans le cas du robot différentiel permettant de déterminer les modèles cinématiques des
robots de type tricycle. Toutefois, par un simple raisonnement géométrique, on établit les
équations suivantes représentant la dérivée de la position du robot:
cos.
vx (I.16)
sin.
vy (I.17)
tan.
D
v (I.18)
S
.
(I.19)
Où TSvu ),( est le vecteur de commande cinématique, la rotation instantanée du robot
par rapport au repère (O, X, Y), et S la vitesse d’orientation imposée à la roue orientable.
Ces équations sont celles du modèle cinématique. La position du robot est donnée par :
t
dtx v0
))(cos()()( (I.20)
t
dty v0
))(sin()()( (I.21)
t
dt0
)()( (I.22)
I.2.4. Robot mobile de type voiture
Le cas du robot de type voiture est très similaire à celui du tricycle. La différence se situe
au niveau du train avant, qui comporte deux roues au lieu d’une. Cela va de soit, on rencontre
beaucoup plus souvent ce type de système.
Chapitre I Modélisation & perception des systèmes de robotique mobile
11
Figure.I.8. Robot mobile de type voiture de Carnegie Mellon University DARPA
Comme on l’a vu précédemment, l’existence d’un CIR unique impose que les axes des
roues du robot soient concourants (qui se coupent en un point). Dans le cas du robot de type
voiture, cela impose aux roues du train avant d’avoir une orientation différente, comme
illustré à la (Figure.I.9). Le roulement idéal, assurant que le CIR est bien unique, est réalisé
sur une voiture par un système de braquage différentiel. Par ailleurs, les trajectoires des roues
n’ayant pas le même rayon de courbure, leurs vitesses sont également différentes.
Figure.I.9. Centre instantané de rotation d’un robot mobile type voiture
L’équivalence entre tricycle et voiture réside dans le fait de figurer une roue virtuelle qui
transformerait un robot de type voiture en tricycle en plaçant la roue orientable du tricycle au
centre de l’axe des roues avant de la voiture, orientée de sorte que le CIR reste inchangé,
conformément à la (Figure.I.9).
De ce fait, le modèle cinématique reste inchangé et les équations de la position du robot
seront celles exprimées pour le robot tricycle.
Chapitre I Modélisation & perception des systèmes de robotique mobile
12
I.2.5. Robot mobile omnidirectionnel
Un robot mobile est dit omnidirectionnel si l’on peut agir indépendamment sur les vitesses
de translation selon les axes x
et y
, et la vitesse de rotation autour de z
.
D’un point de vue cinématique cela n’est pas possible avec des roues fixes ou des roues
centrées orientables [2]. On peut en revanche réaliser un robot omnidirectionnel ayant recours
à un ensemble de trois roues décentrées orientables ou de trois roues suédoises disposées a ux
sommets d’un triangle équilatéral (Figure.I.10).
Trois roues sont suffisantes. Mais, dans certains cas, une quatrième offre des possibilités
d'optimisation et permet de rendre le système plus robuste en évitant le glissement dans le cas
d'un sol qui ne serait pas parfaitement plat par exemple.
Notons qu’en se qui concerne les roues suédoises (Figure.I.1), la rotation des galets
inclinés permet au roues du robot de rouler dans une direction perpendiculaire à celle dans
laquelle elles roulent normalement. C’est ce qui permet au robot de se déplacer dans diverses
directions sans qu’il ait à tourner. Donc le corps du robot lui-même n’effectue pas de rotation
mais uniquement des translations.
Figure.I.10. Robot mobile omnidirectionnel
Dans ce cas on peut considérer qu’il est possible d’appliquer directement la commande
sur le modèle cinématique qui sera défini par les équations suivantes :
1
.
ux (I.23)
2
.
uy (I.24)
3
.
u (I.25)
Chapitre I Modélisation & perception des systèmes de robotique mobile
13
Où Tuuuu ),,( 321représente le vecteur de commande. On choisit ainsi généralement ce type
de robot pour se dispenser des problèmes de planification et de commande liés à la non
holonomie. L’avantage d’une cinématique extrêmement simple est, cependant, à mettre en
balance avec les inconvénients liés à une localisation odométrique déficiente et à une grande
complexité mécanique, en plus qu’ils sont limités en capacité de franchissement et requièrent
un sol très plat. La (Figure.I.11) représente un exemple de ce type de robots.
Figure.I.11. Robot mobile omnidirectionnel le Nomad XR4000
I.2.6. Robot mobile à traction synchrone
La traction synchrone (synchronous drive) est une technique utilisée pour minimiser
l’effet de glissement et augmenter la force de traction.
On rencontre ce type de robot dans l’industrie automobile et dans les robots tous terrains.
La configuration du robot à traction synchrone est similaire à un robot à trois ou quatre roues
couplées de façon quelles soient actionnées en même temps, en ayant la même vitesse et la
même orientation. Ce système est réalisé grâce à deux moteurs : un pour la traction et l’autre
pour l’orientation. L’ensemble est relié par une chaîne (ou une ceinture) pour assurer que
toutes les roues tournent de façon synchrone. La (Figure.I.12) montre le robot à quatre roues
couplées avec des chaînes nommée B21R utilisée dans notre travail.
Chapitre I Modélisation & perception des systèmes de robotique mobile
14
Figure.I.12. Robot mobile à traction synchrone Figure.I.13. Roue décentrée orientable
B21R du CDTA
On a vu qu’à chaque modèle de robot, correspond un type de roues selon son architecture
et ses tâches à accomplir. Le B21R dispose de quatre roues décentrées orientables tournant
selon deux axes, une rotation selon l’axe y permettant le roulement des roues pour avoir la
translation et une rotation selon l’axe K permettant de changer leurs orientations (Figure.I.13).
D’où on en déduit que le nombre de degré de liberté du robot B21R est :
M= m + t = 1+1=2.
m : degré de mobilité (degree of mobility).
t : degré d’orientation (degree of steerability).
Quand le robot se déplace suivant un arc (un virage), les rayons liés au centre du robot et
perpendiculaire à l’axe virtuel défini par son orientation pour chaque position, convergent
vers un point de l’espace, qui est le centre instantané de rotation (CIR) (Figure.I.14).
Ayant une vitesse linéaire v et une vitesse angulaire , le robot peut se déplacer de façon
rectiligne ( v ≠0, =0), le CIR se trouve à l’infinie. Alors que lors d’une rotation pure du
B21R ( ≠0, v =0), le CIR se trouve sur son centre (O’). Et enfin dans le cas où le
déplacement est un virage, c'est-à-dire qu’il se déplace sur un arc de cercle de longueur s , de
rayon R et avec un angle , le déplacement s du robot mobile est :
Rs (I.26)
R et φ peuvent être positifs ou négatifs selon le sens de déplacement du robot (sens du virage).
Les paramètres de la roue orientée sont :
r = rayon de la roue.
v = vitesse linéaire de la roue.
= vitesse angulaire de la roue.
=vitesse d’orientation R
Chapitre I Modélisation & perception des systèmes de robotique mobile
15
Comme le robot tourne autour du CIR avec une vitesse linéaire v et une vitesse angulaire ,
on peut écrire :
Rv (I.27)
Sachant que cette vitesse angulaire du robot mobile B21R est : , donc nous pouvons
exprimer la valeur du rayon du centre instantané de rotation CIR par l’équation :
vR (I.28)
La position du CIR du B21R dans le repère RU (O, X, Y) est donnée par les coordonnées
cartésiennes suivantes :
)sin(RxCIR
x (I.29)
)cos(RyCIR
y
Figure.I.14. Centre instantané de rotation du B21R
Afin de trouver les équations de déplacement du robot B21R, on introduit la vitesse de
roulement de la roue .
rv et sa vitesse de rotation autour de l’axe K (Figure.I.13). On
forme le modèle cinématique suivant :
cos.
vrex (I.30)
sin.
vrey (I.31)
.
(I.32)
Chapitre I Modélisation & perception des systèmes de robotique mobile
16
Puisque les vitesses connues sont celles des roues motrices (Av ,
Bv ,Dv ,
Ev ) qui sont égales,
nous pouvons calculer la vitesse Cv du centre C du robot mobile B21R, tel que :
ACAvCv (I.33)
BCBCv (I.34)
DCDvCv (I.35)
ECEvCv (I.36)
La somme des quatre équations, sachant que vEvDvBvAv , est donnée par :
)(44 ECDCBCACvCv (I.37)
Figure.I.15. Disposition des quatre roues du robot mobile B21R
A partir de la (Figure.I.15), nous pouvons en déduire que les vecteurs AC et DC ainsi que EC
et BC sont des vecteurs égaux et opposés, donc :
vCv 44 et vEvDvBvAvCv (I.38)
On en déduit que la vitesse du robot est égale à la vitesse des roues et à la même direction que
ces dernières, et donc cette vitesse sera parallèle au plan (O, X, Y).
La vitesse linéaire du robot peut être exprimée en fonction de la variation de ses coordonnées
dans le repère univers tel que :
v yx22 (I.39)
Le changement d’orientation du robot, c'est-à-dire sa vitesse de rotation , est exprimé par :
t
.
(I.40)
Chapitre I Modélisation & perception des systèmes de robotique mobile
17
Où est l’orientation instantanée du robot dans le repère Ru (l’angle est représenté par
rapport à l’axe horizontal X, mais dans notre travail il sera représenté par rapport à l’axe
vertical Y, ce qui nous à était imposé par le constructeur iRobot).
Pour le cas de changement de position dans la direction de l’axe X et Y du repère univers Ru,
on aura :
cos.
vx (I.41)
sin.
vy (I.42)
Les équations (I.40, I.41, I.42) constituent l’ensemble d’équations cinématiques du robot
mobile B21R, correspondant à notre modèle cinématique (Figure.I.16).
Figure.I.16. Modèle cinématique du robot mobile B21R
D’où la position du robot mobile dans le repère absolu est donnée par :
t
dttx v0
))(cos()()( (I.43)
t
dtty v0
))(sin()()( (I.44)
t
dt0
)()( (I.45)
I.2.7. Holonomie et non holonomie
La capacité d’un mobile à pouvoir se déplacer à partir d’une situation dans n’importe
quelle direction est appelée "holonomie". En effet, le mécanisme holonomique permet au
robot de manœuvrer dans n’importe quelle direction arbitraire à partir de n’importe quelle
configuration. Ce qui est très rare à trouver dans notre vie quotidienne. Il n’y a pas de
Chapitre I Modélisation & perception des systèmes de robotique mobile
18
contrainte sur les commandes. Cela signifie donc une très grande simplification des problèmes
de contrôle. Un robot holonome omnidirectionnel est donc un robot pour lequel les trois
mouvements planaires indépendants, deux de translation et un de rotation, sont admissibles à
une vitesse non nulle à partir d’une configuration quelconque.
Par contre, de nombreux robots mobiles sont des systèmes non holonomes tels que les
robots différentiels, tricycles, voitures. Ces plates- formes sont toutefois plus difficiles à
commander. Car, elles ne peuvent pas tourner sur place et doivent manœuvrer. Ce qui peut
être difficile dans des environnements encombrés. Pour ce type de robots, bien que l’espace
de configuration sur le plan est de trois dimensions, le mouvement est produit par deux
déplacements indépendants seulement. Donc, le robot ne possède que deux degrés de liberté.
I.3. Perception des systèmes de robotique mobile
Pour réaliser un système de robotique mobile intelligent, il est nécessaire d'utiliser des
capteurs qui fourniront la perception requise de l'environnement pour une prise de décision
intelligente. A ce jour, il n'existe pas de capteur qui se démarque des autres par une efficacité
vraiment supérieure. Ils ont tous des avantages et des inconvénients avec lesquels il faut
pouvoir composer. Par contre, leur importance peut être passablement influencée par
l'environnement dans lequel le système est amené à évoluer. Le défi est donc de réaliser des
systèmes qui utilisent le mieux possible les capteurs ou une combinaison de capteurs en tenant
compte de leurs conditions d'utilisation. Ce qui requiert une bonne connaissance de leurs
caractéristiques.
Nous pouvons définir deux catégories de capteurs couramment utilisés en robotique
mobile : ceux qui délivrent une information caractérisant l’environnement et ceux qui
interviennent dans le fonctionnement du système robotique. Les premiers sont appelés
« capteurs extéroceptifs » qui fournissent des informations sur le monde extérieur au système
mobile, et les seconds sont les « capteurs proprioceptif s » qui fournissent des informations
propres au comportement interne du système mobile, c’est-à-dire sur son état à un instant
donné.
Chapitre I Modélisation & perception des systèmes de robotique mobile
19
I.3.1. Capteurs proprioceptifs
Les capteurs proprioceptifs fournissent par intégration des informations élémentaires sur
les paramètres cinématiques du système mobile. Les informations sensorielles gérées dans ce
cadre sont généralement des vitesses, des accélérations, des angles de giration, des angles
d’altitude. Cependant, ils ne peuvent pas procurer de renseignements lors de l'arrêt du système
mobile. On peut regrouper les capteurs proprioceptifs en deux familles:
Les capteurs de déplacement qui comprennent les odomètres, les accéléromètres et les
radars Doppler. Cette catégorie permet de mesurer des déplacements élémentaires, des
variations de vitesse ou d’accélération sur des trajectoires rectilignes ou curvilignes.
Les capteurs d’attitude, qui mesurent deux types de données : les angles de cap et les
angles de roulis et de tangage. Ils sont principalement constitués par les gyroscopes,
les gyromètres, les gyrocompas, les capteurs inertiels composites, les inclinomètres et
les magnétomètres. Ces capteurs sont en majorité de type inertiel.
I.3.1.1. Les capteurs de déplacement
I.3.1.1.1. Les odomètres
Les systèmes odométriques fournissent la position du système mobile pendant son
mouvement, par intégration des rotations élémentaires de ses roues. Pour les applications de
robotique mobile, les mesures de rotation des roues sont effectuées dans la p lupart des cas par
des codeurs optiques incrémentaux. Il existe néanmoins d'autres codeurs (magnétiques,
inductifs, capacitifs, etc.).
L’information sur l’angle est discrétisée et le nombre de tours est compté, normalement la
résolution est haute. Cependant, la discrétisation devient un problème quand on mesure des
rotations lentes.
Comme tout capteur, le modèle d’odométrie à bien des limitations, du moment que l’idée
fondamentale de celui-ci est l’intégration d’information incrémentale du mouvement à travers
le temps. Ce qui mène inévitablement à l’accumulation d’erreurs, en particulier, celles
d’orientation qui causera une grande incertitude sur la position [3]. Cette erreur croît
proportionnellement avec la distance traversée par le robot.
Quand on cherche à mesurer ou à réduire les erreurs de l’odométrie, il est important de
faire la différence entre l’erreur systématique et non systématique de l’odométrie. Les erreurs
systématiques sont ceux qui sont une partie inhérente à la cinématique du robot ou à ces
Chapitre I Modélisation & perception des systèmes de robotique mobile
20
paramètres de contrôle indépendamment de l’environnement. Les erreurs non systématiques
sont celles qui dépendent de l’environnement du robot et diffèrent d’un environnement à un
autre.
La distinction entre ces deux groupes est importante. Car, chaque groupe influe
différemment sur la plateforme mobile. Leurs remèdes sont différents et nécessitent
techniques de mesure différentes. Borenstein et ses collaborateurs [4],[5], étudient les
différentes sources des deux types d’erreurs et catégorisent ces erreurs d’odométrie comme
tel :
Les erreurs systématiques :
- Diamètres des roues différents.
- Roues male positionnées.
- Une résolution limitée des encodeurs.
- vitesse d‘échantillonnage des encodeurs limitée.
Les erreurs non systématiques
- Se déplacer sur un sol raboteux.
- Se déplacer à travers des objets imprévus sur le sol.
- Glissement des roues (sol lisse, excès d’accélération, patiner dans un tournant
rapide, etc.).
- Forces externes (interaction avec des corps externes).
- Forces internes (roue folle).
- Pas de contact avec le sol.
Tout modèle odométrique aussi bon qu’il soit n’est qu’une approximation du vrai modèle
cinématique. Quand l’odométrie est utilisée pour la prédiction de la position, la partie la plus
critiquée de l’estimation est la capacité à estimer l’orientation du robot. Car, même une petite
erreur dans l’orientation du robot (ce qu’on appelle par drift) induit à une grande erreur
dans la position. Mais, par une modélisation soigneuse cette erreur systématique pourra être
limitée (Borenstein & Feng 1996b) [5], (Borenshtein 1998) [7].
I.3.1.1.2. Les accéléromètres
L’accéléromètre est un capteur qui mesure l’accélération linéaire en un point donné. En
pratique, la mesure de l’accélération est effectuée à l’aide d’une masse d’épreuve M, de masse
m, reliée à un boîtier du capteur. Le principe de ce capteur est de mesurer l’effort massique
non gravitationnel qu’on doit appliquer à M pour le maintenir en place dans le boîtier
Chapitre I Modélisation & perception des systèmes de robotique mobile
21
lorsqu’une accélération est appliquée au boîtier. Le calcul du déplacement élémentaire du
système mobile est obtenu par double intégration de ces informations. Cette double
intégration conduit généralement à des accumulations importantes d’erreurs. Ce capteur est
plus coûteux que les odomètres.
I.3.1.1.3. Le radar Doppler
Le radar Doppler fournit une estimation instantanée de la vitesse linéaire d’une
plateforme mobile par rapport à un objet de la scène en se basant sur l’effet Doppler-Fizeau.
Le principe est de diriger un faisceau électromagnétique de fréquence F vers le sol. Le
faisceau reçu après rediffusion sur le sol présente un décalage de fréquence F proportionnel
à la vitesse V du déplacement relatif du véhicule par rapport au sol (Figure.I.17).
L’intégration de la mesure de vitesse fournira une estimation du déplacement du mobile.
Figure.I.17. Principe du capteur à effet Doppler
L’expression de la vitesse est donnée par :
(I.46)
Avec :
v : la vitesse de déplacement de l'émetteur.
c : la vitesse de propagation de l'onde.
ΔF : la différence de fréquence.
F : la fréquence d'émission.
α : l’angle d'inclinaison entre le capteur et le sol.
I.3.1.2. Capteurs d’attitude
Les capteurs d’attitude permettent d’estimer les paramètres intrinsèques du système
mobile qui sont les angles de cap, de roulis et de tangage. Ces capteurs sont principalement de
type inertiel. Ces capteurs ont pour point commun d’être généralement coûteux et sensibles au
bruit, d’où une intégration moins fréquente dans les systèmes embarqués que les odomètres.
Chapitre I Modélisation & perception des systèmes de robotique mobile
22
I.3.1.2.1. Les gyroscope, gyromètre et gyrocompas
Les gyroscopes permettent la mesure de l'angle de rotation de la trajectoire du système
mobile. Ces mesures sont intégrées pour fournir la position du système mobile. Ces capteurs
sont particulièrement répandus en positionnement de systèmes mobiles. Car, ils aident à
compenser pour la plupart, l'imprécision sur l'orientation fournie par l'odomètre [6],[7]. Une
erreur d'orientation odométrique peut entraîner une erreur de position cumulative qui peut être
diminuée voire compensée par l’utilisation conjointe de gyroscopes [7]. Les gyroscopes très
précis sont trop onéreux pour être utilisés en robotique mobile. Cependant, les gyroscopes à
fibre optique, connus pour leur grande précision, ont vu leur prix chuter et sont donc devenus
une solution attractive pour la navigation en robotique mobile.
Le gyromètre est un capteur qui permet de mesurer une vitesse angulaire. Il existe
plusieurs types de gyromètres : les premiers à avoir fait leur apparition furent mécaniques,
aujourd’hui, on utilise surtout des gyromètres laser ou des gyromètres optiques [8].
Le gyrocompas est un capteur qui permet de mesurer le cap. Il est composé d’un
gyroscope et d’un compas magnétique. Le gyrocompas conserve le nord magnétique durant
tout le déplacement du véhicule, après l’avoir initialement déterminé de façon autonome.
I.3.1.2.2. Les magnétomètres
Les capteurs magnétiques sont des instruments qui mesurent la direction du champ
magnétique terrestre. Ils sont utilisés pour déduire l’orientation du système mobile. Ces
derniers étant perturbés par les masses métalliques, l'utilisation du compas magnétique n'est
possible que pour des systèmes mobiles évoluant dans la nature, moyennant une procédure
d'initialisation pour compenser l'influence magnétique de l'engin porteur. Comme les capteurs
inertiels, les magnétomètres sont utilisés pour indiquer l'orientation du système mobile [9].
I.3.2. Capteurs extéroceptifs
Les capteurs extéroceptifs sont employés en robotique mobile pour collecter des
informations sur l'environnement d'évolution du système mobile. Ils sont le complément
indispensable aux capteurs proprioceptifs présentés précédemment. Des méthodes de fusion
de données sont alors utilisées pour conditionner et traiter les informations sensorielles de
natures différentes.
Chapitre I Modélisation & perception des systèmes de robotique mobile
23
Ils sont notamment utilisés dans les domaines d'application tels que l'évitement d'obstacle,
la localisation, la navigation et la modélisation d'environnements. Les principaux capteurs
utilisés en robotique mobile sont : les capteurs télémétriques (les ultrasons, les lasers et les
infrarouges), le GPS et les caméras.
I.3.2.1. Les capteurs télémètriques
On appelle télémétrie toute technique de mesure de distance par des procédés acoustiques,
optiques ou radioélectriques. L’appareil permettant de mesurer les distances est appelé
« télémètre ». Il existe différentes technologies pour réaliser un télémètre. Nous présentons
dans ce qui suit les télémètres les plus utilisés dans les systèmes de robotique mobile, en
donnant une idée de leur gamme de mesure et d’application.
I.3.2.1.1. Les capteurs ultrasons
Les capteurs ultrasonores utilisent des ondes sonores dont les fréquences ne sont pas
perceptibles par l’oreille humaine. Les fréquences couramment utilisées dans ce type de
technologie vont de 20khz à 200khz. Les capteurs à ultrasons mesurent le temps de vol d’une
onde ultrasonore entre son émission et sa réception après réflexion. A partir de ce temps et
connaissant la vitesse de propagation de l’onde, la distance séparant le capteur de l’obstacle
qu’il perçoit est directement disponible sans analyses complémentaires. Les acquisitions des
mesures sont rapides, ils peuvent donc être utilisés pour le processus qui commande un
traitement en temps réel comme l’évitement d’obstacle.
Figure.I.18. Capteur ultrason ME007
Comme chaque capteur, il existe néanmoins des erreurs potentielles comme la variation de
la vitesse de propagation de l'onde qui peut être influencée par les changements de
température, par les courants d'air et dans une moindre mesure par l'humidité. Une autre
caractéristique de ces capteurs est leur cône d'émission assez large (de 20° à 30°) qui ne
Chapitre I Modélisation & perception des systèmes de robotique mobile
24
permet pas de connaître précisément la position de l'obstacle dans le cône d'émission du
capteur.
Figure.I.19. La distribution de l’intensité d’un capteur ultrason [2]
I.3.2.1.2. Les capteurs infrarouges
Les capteurs à infrarouges fonctionnent suivant le même principe que les capteurs à
ultrasons. Ils se composent d'un couple émetteur-récepteur (Figure I.20). L'émission s'effectue
par une diode électroluminescente infrarouge. Le récepteur est une photodiode ou un
phototransistor, sensible au flux lumineux rétrodiffusé par la cible [10].
Les capteurs à infrarouges sont d'un faible encombrement mais sens ibles aux
perturbations lumineuses ainsi qu'à la nature des surfaces réfléchissantes. Leurs portées n'étant
que de quelques mètres, ils sont utilisés essentiellement pour détec ter les obstacles proches
[11].
Figure.I.20. Capteurs Infrarouge Sharp GP2D120
Obstacle
IR
Chapitre I Modélisation & perception des systèmes de robotique mobile
25
I.3.2.1.3. Les capteurs lasers
Il existe deux manières de mesurer une distance grâce à un système laser. Soit il émet en
mode continu et la distance est déterminée à partir du déphasage entre l’onde émise et l’onde
réfléchie par l’obstacle, soit il émet en mode pulsé et la distance est proportionnelle au
« temps de vol » de l’onde entre son émission et sa réception.
Le faisceau d’onde émis est très concentré, ce qui permet d’avoir un cône d’émission très
étroit et donc une bonne précision de mesure. Pour obtenir un balayage de l’environnement en
deux, voir en trois dimensions, différents systèmes de miroir tournants peuvent être associés
au laser [12].
Les lasers existants diffèrent par leurs caractéristiques et leurs domaines d’applications.
En effet, la distance maximale mesurable des lasers peut aller d’une dizaine de mètres jusqu’à
quelques centaines de mètres.
Les télémètres les plus utilisés à l’heure actuelle pour des applications de cartographie et
de localisation sont les télémètres laser à balayage. Ils utilisent un faisceau laser mis en
rotation afin de balayer un plan, en général horizontal.
Figure.I.21. Laser SICK 180° (a) , Lidar 360° (b)
Les télémètres laser les plus courant ont une bonne résolution angulaire car ils permettent
d’obtenir une mesure de distance tout les demi ou un degré, sur une zone de 180 à 360 degrés
selon les modèles (Figure.I.21). Ces télémètres sont plus utilisés en environnement d’intérieur
que l’extérieur car ils fournissent des données abondantes et précises sur la position des objets
caractéristiques de l’environnement tels que les murs…etc.
Chapitre I Modélisation & perception des systèmes de robotique mobile
26
Figure.I.22. Schéma de la télémétrie laser par déphasage de mesure [2]
L’expression de la distance de mesure est donnée par l’équation :
(I.47)
Avec :
(I.48)
I.3.2.1.4. GPS (Global positioning system)
Un des systèmes les plus connus de ces dernières années est le Système de Positionnement
Global (GPS), du département de la défense des Etats-Unis, qui exploite une constellation de
vingt-quatre satellites en orbite à haute altitude. Chaque satellite détecte les récepteurs
terrestres fixes ou mobiles qui se trouvent dans sa zone de visibilité et transmet à chacun, à
période fixe, un signal contenant des informations telles que son identification, l'heure
d'émission du signal et les paramètres définissant son orbite donc sa position. Théoriquement,
un récepteur doit être visible d’au moins trois satellites, pour pouvoir calculer sa position dans
un repère centré sur la terre, en calculant l’intersection de trois sphères (trois cercles pour un
système mobile au sol) ; de fait, pour tenir compte des décalages temporels entre les mesures
fournies par les satellites, quatre mesures de distance entre le satellite et le récepteur sont
requises pour disposer d’une précision satisfaisante [13].
Chapitre I Modélisation & perception des systèmes de robotique mobile
27
Figure.I.23. Calcul de la position et le cap basé sur le GPS [2]
En termes de précision, la localisation ainsi obtenue est entachée d’une erreur de l’ordre
de la quinzaine de mètres. Ce qui n’est pas suffisant pour permettre à un robot de naviguer de
manière robuste. Ainsi, on a systématiquement recours à une méthode différentielle pour
obtenir des résultats plus satisfaisants (Figure.I.23). La localisation se fait à l’aide de deux
récepteurs, dont l’un est statique et positionné avec précision dans l’environnement. On peut
alors obtenir une précision de l’ordre du centimètre.
Ce système est cependant loin de résoudre tous les problèmes de localisation des systèmes
mobiles. Il fonctionne en effet difficilement dans des environnements urbains, et n’est pas
utilisable à l’intérieur des bâtiments, car les ondes employées sont fortement atténuées en
traversant les murs. Sa précision est de plus souvent trop faible pour qu’un système mobile
terrestre puisse utiliser ces informations seules. En pratique, il est souvent couplé à un
système inertiel qui permet de pallier aux pertes du signal GPS et il ne remplace, de toute
façon, pas les capteurs du système mobile qui lui permettent de percevoir son environnement
immédiat [14].
Mis à part son utilisation pour la localisation, ce système est aussi utilisé pour l’aide à la
navigation d’avions et de bateaux lors de l’approche d’aéroports ou de ports, ainsi que dans la
surveillance de camionnettes de livraison et de véhicules d’urgence, en vue de choisir au
mieux leurs itinéraires.
Chapitre I Modélisation & perception des systèmes de robotique mobile
28
Figure.I.24. Récepteur GPS
Il existe une variété de trames GPS d’une fréquence entre 5Hz à 15Hz, qui donnent non
seulement la position, mais aussi l’altitude, vitesse, heures, nombre de satellites…etc. Parmi
les plus utilisés dans la robotique terrestre, aérienne et maritime du standard NMEA on
trouve : GGA – RMC…etc.
I.3.2.1.5. Les caméras
La vision par ordinateur est une imitation de la vision humaine. Pour ce faire, il faut
d’abord créer des dispositifs de vision ayant les mêmes capacités de capture que celles de
l’être humain. Deux technologies sont utilisées: CCD (charged coupled device) et CMOS
(complementary metal oxide semiconductor).
Technologie CCD : Un composant CCD est une matrice d’éléments (Pixels) sensibles
à la lumière (400-1000nm). Chaque pixel peut être vu comme un condensateur de
taille d’environ 5-25μm. Au début, les condensateurs sont chargés. Durant le temps
d’exposition (temps d’intégration), les photons libèrent des électrons qui seront
retenus par les pixels (jusqu’à 40000 e /pixel). Après l’exposition, les charges doivent
être maintenues constantes et lues. Ce qui exige une circuiterie de commande bien
spécialisée.
Technologie CMOS : Cette technologie démarre à partir de CCD. Elle associe à
chaque pixel une circuiterie de plusieurs transistors qui mesure et amplifie le signal.
Ce qui facilite énormément le transfert de l’information et réduit la consommation
énergétique. Néanmoins, cette technologie est récente et la résolution est encore faible
en la comparant à celle de CCD.
Une caméra peut être utilisée de différentes manières pour la navigation d’un robot
mobile. Elle peut être utilisée pour détecter des amers visuels (des points particuliers qui
servent de repère, tels que des portes ou des affiches) à partir desquels il se ra possible de
calculer la position du robot. Si ces amers sont simplement ponctuels, ou de petite taille, il
sera en général simplement possible d’estimer leur direction. Dans le cas ou les amers sont
Chapitre I Modélisation & perception des systèmes de robotique mobile
29
des objets connus en 2D ou 3D, il sera en général possible d’estimer complètement la position
du robot par rapport à la leur. Elle peut également être utilisée pour détecter des « guides » de
navigation pour le robot, tels que des routes ou des couloirs.
I.4. Conclusion
Au cours de ce chapitre, nous avons présenté les différents types de robots mobiles à roues
les plus utilisés. Cette variété réside dans leur mode de locomotion qui dépend du type et de la
disposition des roues employées. Une étude cinématique spécifique est donc nécessaire pour
chaque type de robot avant son utilisation. Nous avons aussi introduit la distinction entre
systèmes holonomes et systèmes non holonomes. On a vu que la majorité des robots mobiles
à roues sont des systèmes non holonomes, sauf dans le cas des robots mobiles
omnidirectionnels. Dans notre cas, le robot mobile B21R est non holonome, de type à traction
synchrone.
Ces robots mobiles sont dédiés à divers applications où ils auront à se déplacer dans des
environnements d’intérieur ou d’extérieur. Pour cela, ils doivent être munis d’un système de
perception qui est généralement composé de deux catégories de capteurs. Ces catégories sont
plus complémentaires que concurrentes. C’est pour cette raison qu’un système de navigation
sera généralement basé sur l’exploitation des informations sensorielles émanant de ces deux
catégories de capteurs. Nous pouvons étendre cette remarque à la problématique spécifique
qu’est la perception du milieu d’évolution d’un robot mobile : l’emploi d’un seul capteur pour
une tâche donnée est généralement insuffisant. Ainsi, l’association de plusieurs capteurs,
qu’ils soient complémentaires ou redondants, permettra d’obtenir un modèle sensoriel robuste
et hautement descriptif.
Chapitre II
Localisation & cartographie des systèmes
de robotique mobile
Chapitre II Localisation & cartographie des systèmes de robotique mobile
30
II.1. Introduction
La navigation est l'une des compétences les plus difficiles requises d'un robot mobile. Le
succès de la navigation nécessite la réussite dans les cinq blocs constructifs du système de
navigation:
La perception : Le robot doit interpréter les données de ses capteurs pour extraire des
informations significatives.
Localisation : Le robot doit déterminer sa position dans l'environnement.
La cartographie : Le robot doit construire la carte de l’environnement qui l’entoure
vu par ses systèmes embarqués.
La navigation : Le robot doit planifier son chemin pour atteindre ses objectifs.
Le contrôle du mouvement : Le robot doit moduler ses sorties des moteurs pour
obtenir la trajectoire désirée.
Figure.II.1. Boucle de navigation autonome des robots mobiles
Parmi ces cinq composantes (Figure.II.1), la localisation et la cartographie ont reçu la plus
grande attention durant cette dernière décennie et des progrès significatifs ont été réalisés sur
ce front qui y a un grand lien avec la navigation.
II.2. Localisation des systèmes de robotique mobile
La localisation est la détermination de la situation (i.e., position et orientation) du système
mobile par rapport à un repère de référence. Elle est absolue, si le repère est fixé à son
environnement. Elle est relative, lorsque le repère est lié à une position précédente du
système mobile. Nous pouvons aussi parler de localisation statique lorsque le calcul de la
position s’effectue à l’arrêt ou de localisation dynamique lorsque celle-ci est évaluée durant
le mouvement.
Capteurs Perception Localisation Cartogra
phie
Navigation Contrôle Actionneurs
Chapitre II Localisation & cartographie des systèmes de robotique mobile
31
Nous pouvons considérer trois grands systèmes de localisation [15]:
La localisation relative ou à l’estime (Dead Reckoning en anglais), basée sur
l’utilisation des capteurs proprioceptifs,
La localisation absolue, basée sur l’utilisation des capteurs extéroceptifs,
La localisation dite hybride, basée sur l’utilisation conjointe des capteurs
proprioceptifs et extéroceptifs.
II.2.1. Localisation relative (à l’estime)
Elle consiste à déterminer la position, l’orientation, et éventuellement la vitesse du
système mobile par intégration des informations fournies par divers capteurs proprioceptifs
depuis un point de départ. Ces données peuvent être des informations de déplacement
(odomètre), de vitesse (vélocimètre) ou d’accélération (capteurs inertiels) [15].
Ce type de localisation présente l’immense avantage d’être indépendant de
l’environnement. Les seules erreurs qu’il peut générer sont celles dues à son mode de
fonctionnement interne. Par contre, l’inconvénient majeur est l’accumulation des erreurs due
aux différentes intégrations.
II.2.2. Localisation absolue
La localisation absolue est une technique qui permet à un système mobile de se repérer
directement dans son milieu d’évolution, que ce soit en environnement extérieur (mer, espace,
terre), ou en environnement intérieur (ateliers, immeubles, centrales nucléaires) [16]. Elle est
basée sur l’utilisation de capteurs extéroceptifs et nécessite toujours une représentation de
l’environnement.
Le système mobile possède donc une banque de données regroupant les éléments
caractéristiques de son milieu d’évolution (balises, GPS…). Pour sa localisation absolue, il
doit déduire de la perception de ces éléments caractéristiques, sa position dans son
environnement.
II.2.3. Localisation hybride
Les deux approches de localisation présentées précédemment (localisation à l’estime et
localisation absolue) s’appuient soit sur des mesures de déplacement relatif, soit sur des
mesures de position absolue. Elles possèdent des caractéristiques complémentaires.
Chapitre II Localisation & cartographie des systèmes de robotique mobile
32
En développant des méthodes de localisation qui fusionnent les données proprioceptives et
extéroceptives, il est possible d’allier les avantages des deux approches, tout en limitant leurs
inconvénients. Le principe de ces méthodes consiste à corriger les positions estimées à
cadence rapide au moyen des capteurs proprioceptifs par des mesures fournies à cadence
beaucoup plus lente par les capteurs extéroceptifs. On parle alors de recalage dynamique,
c'est-à-dire, les positions estimées par les capteurs proprioceptifs seront utilisées pour faciliter
l’appariement des mesures fournies par les capteurs extéroceptifs [16].
II.3. Cartographie des systèmes de robotique mobile
Même en présence d’une bonne localisation, un robot qui ne possède a priori aucune
information sur l’environnement, dans lequel il doit se déplacer et agir, doit être capable de
modéliser son environnement grâce à l’ensemble de ses capteurs. Ce modèle est indispensable
pour la navigation. Dans certaines applications robotiques, une carte de l’environnement peut
être fournie par un opérateur humain ou par des sources extérieures comme les images
aériennes ou satellites. Mais, dans la plupart des cas, ces données sont insuffisantes pour les
applications qui ont besoin de perception précise dans une zone d’activité locale du robot. Un
robot autonome doit être capable de réagir à des modifications inattendues dans son
environnement. La construction d’une telle carte devra être incrémentale, en fusionnant les
perceptions successives acquises par les capteurs du robot au cours de son déplacement.
Deux grandes familles de représentation d’un espace de navigation se distinguent :
Les représentations métriques : Elles décrivent explicitement la position
"géométrique" des éléments de l'environnement.
les représentations topologiques : Elles sont basées sur des graphes représentant des
informations de plus haut niveau comme certaines places caractéristiques de
l'environnement (coins, croisement de deux couloirs, jonctions en T, etc.).
II.3.1. Représentations métriques
Dans cette représentation, l’environnement est représenté par un ensemble d’objets
auxquels sont associées des positions dans un espace métrique, généralement en deux
dimensions. Elle peut être subdivisée en deux sous familles:
Représentation purement géométrique qui utilise explicitement les positions
"cartésiennes" des primitives cartographiques.
Chapitre II Localisation & cartographie des systèmes de robotique mobile
33
Représentation par grille d’occupation, qui décrit les propriétés métriques par
discrétisation de l’environnement en y ajoutant des informations d'incertitude.
A- Représentation géométrique
C’est une représentation cartésienne de l’environnement où les coordonnées x, y voire z
des amers (caractéristiques de l’environnement) sont décrites explicitement. Ces
caractéristiques sont des points, des segments de droite, des rectangles, des polygones…etc,
obtenues à partir des mesures et constituant une représentation des différents éléments de
l'environnement.
Ces représentations sont obtenues soit à partir des mesures de capteurs télémétriques qui
donnent la limite des obstacles, soit à partir des modèles établis à partir d'une image d'un
capteur de vision qui donne une autre perception de l'environnement.
Figure.II.2. Carte géométrique représentant un hall
B- Grille d’occupation
Dans une grille d’occupation, les mesures sont représentées sous forme d'un ensemble de
cellules. Chaque cellule possède plusieurs attributs exprimant chacun une propriété de la zone
correspondante, notamment son occupation. Pour des scènes d'intérieur, où le sol est plat, la
plupart des chercheurs décrivent l'état de chaque cellule par un attribut unique qui est la
probabilité d'occupation. On parle alors de grille d'occupation. Une cellule est dite « libre » si
sa probabilité d'occupation est inférieure à un seuil choisi et occupée dans le cas inverse.
La grille d’occupation représente un modèle capable de faire la mise à jour de
l’environnement à une fréquence élevée et permettant de réviser facilement les probabilités
Chapitre II Localisation & cartographie des systèmes de robotique mobile
34
d’occupation, donc de suivre l’évolution de l’environnement autour du robot. Ce qui est
indispensable pour une meilleure réactivité. De plus, une grille d’occupation est capable de
modéliser des environnements de forme quelconque et ne cherche pas à estimer les données
par des primitives qui peuvent être inadéquates. Elle est en général préférée pour les
applications qui reposent sur la détection de l’espace navigable (espace libre) ou pour
l’évitement d’obstacles. En revanche, elle souffre de la discrétisation par une grille qui induit
des déformations et exige un espace de stockage important pour une grande résolution.
Figure.II.3. Grille d’occupation [2]
II.3.2. Représentation topologique
Les cartes topologiques permettent de représenter l’environnement du robot sous forme de
graphe. Les nœuds du graphe correspondent à des lieux, c’est-à-dire des positions que le robot
peut atteindre. Les arêtes liant les nœuds marquent la possibilité pour le robot de passer
directement d’un lieu à un autre et mémorisent en général la manière de réaliser ce passage.
La détection et la mémorisation des lieux reposent en général sur deux procédures qui
utilisent les perceptions. La première permet simplement de comparer deux perceptions et
donc de reconnaître un lieu de la carte ou de détecter un lieu nouveau. La seconde procédure
permet de mémoriser un nouveau lieu ou d’adapter la définition d’un lieu lors des passages
successifs du robot en ce lieu. Comme nous l’avons déjà mentionné, la reconnaissance d’un
lieu est soumise aux problèmes de la variabilité perceptuelle. En conséquence, la première
procédure peut donner des résultats erronés. Par exemple, un lieu déjà visité peut ne pas être
reconnu ou un lieu nouveau peut être confondu avec un lieu déjà mémorisé. Pour résoudre ces
problèmes, la reconnaissance des lieux fera donc appel aux données proprioceptives en plus
des perceptions. Pour ce faire, de nombreuses méthodes ont été mises en œuvre. Les données
mémorisées dans les arêtes du graphe sur les relations de voisinage entre lieux proviennent
des données proprioceptives. Cela est caractéristique des cartes topologiques, dans lesquelles
Chapitre II Localisation & cartographie des systèmes de robotique mobile
35
les perceptions ne sont en général pas utilisées pour estimer les positions relatives des lieux
visités, mais seulement pour reconnaître un lieu. Ces données peuvent être des informations
sur les positions relatives des nœuds ou des informations sur les actions à effectuer pour
parcourir cette arête.
Figure.II.4. (a) modèle réel, (b) Carte topologique
II.4. Localisation et cartographie simultanées (SLAM)
Lorsque la carte de l’environnement du système mobile n’est pas connue a priori, un
module de génération de carte doit obligatoirement être intégré au système de navigation. Il
s’agit là d’une étape supplémentaire qui consiste à mettre à jour, au fur et à mesure des
acquisitions, une représentation du milieu d’évolution du système mobile. Ce processus se
décline comme une fusion successive des différents modèles sensoriels générés lors du
déplacement du système. Il paraît clair à ce niveau que la fusion incrémentale de modèles
sensoriels nécessite obligatoirement leurs recalages systématiques avec les primitives déjà
insérées dans la carte. Cette étape de recalage est, ni plus ni moins, qu’une localisation du
système mobile par rapport à une connaissance acquise au cours du déplacement. L’étape de
localisation devient alors indissociable de celle de modélisation et on parle alors d’un système
de localisation et modélisation simultanée (en anglais, Simultaneous Localization and
Mapping ou SLAM), voire plus rarement CML (Concurrent Mapping and Localization) [16].
L’implémentation d’un algorithme SLAM repose sur les étapes suivantes :
Perception : les algorithmes de perception fournissent, à partir des données issues des
capteurs extéroceptifs, un ensemble d’observations des éléments de l’environnement
(amers), dont la position relative au système mobile peut être déterminée. Ce
(a) (b)
Chapitre II Localisation & cartographie des systèmes de robotique mobile
36
processus de perception dépend bien entendu du type d’environnement dans lequel le
système mobile évolue et des capteurs utilisés. Les données proprioceptives sont des
mesures internes au système et renseignent sur l’évolution de son état. Pour le SLAM,
on s’intéresse à la position du système mobile dont l’évolution est typiquement fournie
par des capteurs odométriques ou une centrale inertielle.
Figure.II.5. Architecture générale du SLAM
Association de données : les amers ne sont utiles, pour estimer la position du système
mobile, que s’ils sont observés de différentes positions. Le système mobile doit
décider si l’amer observé est déjà présent dans la carte et de quel amer il s’agit ou bien
alors si c’est un nouvel amer à ajouter à la carte.
Estimation : L’algorithme d’estimation doit intégrer les données issues de la
perception ainsi que de la proprioception afin de fournir une estimée de la position du
système mobile et des positions des amers, ainsi que les incertitudes associées à ces
estimées.
Perception Mouvement
Carte Locale
Mise en
correspondance
Correction de la
position du
robot et de la
carte
Carte
globale
Fusion de la
carte
Chapitre II Localisation & cartographie des systèmes de robotique mobile
37
Gestion de la carte : Il s’agit d’intégrer ou bien fusionner toutes les données issues de
la perception afin de fournir une carte globale cohérente de l’environnement.
Autrement dit, lorsqu’un système mobile se déplace dans un environnement, les amers
détectés sont positionnés avec une imprécision due aux capteurs embarqués. Le
système mobile mesure son déplacement par une technique de localisation à l’estime
avec une certaine erreur. Les amers qui sont à nouveau observés, après une mise en
correspondance, sont associés aux amers préalablement perçus. Une technique de
fusion de données permet alors de réduire les erreurs sur la position courante du
système mobile et les positions des amers. Ce processus est itéré à chaque nouvelle
perception de l’environnement effectuée par le système mobile.
II.5. La technique SLAM scan matching
Dans les applications de modélisation de l’environnement, on dispose généralement de
plusieurs données 2D de la même scène prises de points de vue différents. L’alignement de
ces vues peut être défini comme étant le processus d'estimation des transformations rigides
(rotations et translations) qui permettent de ramener ces différentes vues dans un référentiel
commun. Le scan matching (ou mise en correspondance des scannes) de deux vues est
souvent considéré comme un problème d'optimisation, dont la fonction de coût est basée sur
la mesure d’une distance entre les parties communes de ces deux vues. Les différentes
méthodes proposées pour résoudre ce problème diffèrent essentiellement selo n la métrique
utilisée pour formuler cette distance et selon la technique de minimisation mise en œuvre.
II.5.1. L’objectif du scan matching
La reconstruction de modèles 2D complets (création de modèles d'objets, reconstruction
de l'environnement en robotique mobile, imagerie, etc.) nécessite l'acquisition de plusieurs
données de l'objet sous des points de vue différents. Cette contrainte résulte tout d’abord des
limitations du champ de capteur utilisé. Ainsi, plus la résolution du capteur est importante,
plus son champ est petit. Dans ce cas, il faut acquérir un nombre important de données pour
numériser l’ensemble de l’objet. Il en résulte des données 2D qui doivent être transformées
dans le même système de coordonnées. Cette opération est appelée "appariement (matching)".
Pour que l’appariement soit possible, les points de vue choisis pour la numérisation doivent
être tels que deux nuages de point voisins se recouvrent partiellement.
Chapitre II Localisation & cartographie des systèmes de robotique mobile
38
Le scan matching vise à fournir un ensemble de données exploitables pour la
reconstruction du modèle numérique d’un objet ou d’un environnement de telle sorte que l'on
puisse, d'une part, le visualiser sur un écran et, d'autre part, traiter ces données pour obtenir
une représentation adaptée à l’application envisagée. Mais ce n’est pas le seul domaine
d’application du scan matching. Il peut également servir pour la reconnaissance de formes 2D
& 3D ou pour résoudre des problèmes de localisation en robotique mobile en maximisant la
superposition de deux configurations consécutives comme le montre la (Figure II.6).
Figure.II.6. Localisation relative du robot utilisant deux scans consécutifs [17]
II.5.2. Les approches de scan matching
La construction du modèle 2D d'un objet nécessite l’appariement de plusieurs vues. Pour
recaler l’ensemble de ces vues dans un référentiel unique, on peut utiliser soit une approche
locale soit une approche globale, comme il est illustré dans la (Figure II.6).
Le scan matching local [18],[19] consiste à recaler les différentes vues deux par deux.
Ainsi, pour un modèle composé de N vues, il faut recaler successivement N-1 paires de
données. Cette approche a l'inconvénient de ne pas prendre en compte toutes les interactions
entre les divers recouvrements mutuels des différentes données. En effet, chaque vue
chevauche généralement plusieurs autres vues. Un autre inconvénient de cette approche est
que les erreurs d’appariement par paires se propagent de donnée en donnée [20].
Le scan matching global, contrairement au scan matching local, prend en considération
toutes les vues disponibles à la fois. Il prend en compte tous les recouvrements possibles entre
les différentes vues. Il permet une meilleure distribution des erreurs résid uelles entre les
différents recouvrements.
Points à recaler
Chapitre II Localisation & cartographie des systèmes de robotique mobile
39
Figure.II.7. scan matching : (a) local et (b) global.
Pour les méthodes du scan matching, il existe plusieurs algorithmes pour résoudre ce
problème, parmi les plus connus et utilisés, on y trouve les algorithmes:
Itérative closest point ICP [19].
Itérative dual correspondances IDC [21].
Point-based probabilistic registration [22].
Branch-and-bound registration [23].
Normal distributions transform NDT [24].
Gaussian fields registration [25].
II.6. Conclusion
Dans ce chapitre, nous avons présenté les différentes méthodes de localisation, ainsi les
différentes représentations de l’environnement existantes. Nous avons abordé aussi le principe
de SLAM et l’objectif du scan matching et ses différentes approches. On a terminé par les
algorithmes les plus utilisés du scan matching qui sont, de nos jours, appliqués pour la
localisation et cartographie simultanées (SLAM) en robotique mobile.
Le prochain chapitre aborde le fond de notre travail qui concerne la technique étudiée et
implémentée du scan matching utilisée pour le SLAM, à savoir l’algorithme ICP, ainsi les
résultats obtenus pour divers environnements.
Carte globale
Carte locale
Carte locale (k)
Carte locale (k+1)
Repère (k)
Repère (k+1)
Repère globale
(a)
(b)
Chapitre III
La technique ICP (Itérative Closest Point)
basée SLAM
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
40
III.1. Introduction
Plusieurs techniques ont été développées pour assurer la connaissance, de façon autonome,
la position d’un robot mobile dans son environnement. Parmi elles, les méthodes SLAM
(Simultaneous Localization and Mapping) qui fournissent simultanément la position du robot
mobile et une carte fiable et précise de l’environnement d’évolution. Car une carte précise et
détaillée représente une source d’information indispensable pour réaliser une bonne localisation
du robot mobile. Mais, pour élaborer une carte correcte, une localisation du robot mobile dans
son environnement et aussi importante. La localisation et cartographie
simultanées, SLAM, permet au robot de mettre en place une base de connaissances, grâce à la
construction progressive de la carte, en utilisant les données de ses capteurs, tout en estimant sa
localisation sur la carte.
Comme nous l’avons mentionné dans le chapitre précédent, il existe plusieurs techniques
pour l’estimation des postures du robot. Dans notre projet, l’approche utilisée est la technique
ICP (Iterative Closest Point) qui recherche pour chaque point du premier scan le meilleur
correspondant parmi les points du second scan. Ces informations d'association de données
permettent de corriger la position du robot due à l’erreur cumulative engendrée par les capteurs
odométriques. Puis, le processus se répète de manière itérative pour raffiner progressivement
cette estimation. Ceci fait l’objet de ce chapitre. Mais, on commence d’abord par la
présentation plateforme utilisée, à savoir le robot mobile B21R (iRobot).
III.2. La plateforme utilisée : Robot mobile B21R (iRobot)
Le robot mobile B21R que nous avions utilisé est une plateforme expérimentale
construite par la société iRobot pouvant se déplacer dans un milieu intérieur (Indoor). Conçu
spécialement pour diverses applications telles que: la localisation, navigation, cartographie,
surveillance, IHM…etc.
III.2.1. Architecture matérielle
Le robot synchro drive B21R se déplace grâce à ses quatre roues disposées en forme de
carré. Il a une forme cylindrique de dimension de (52.5x106cm), pèse environ 122.5kg et peut
supporter une charge supplémentaire de 90kg, et se déplace à une vitesse max de 90cm/s.
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
41
Figure.III.1. La structure matérielle du robot B21R
Il est constitué de trois parties : la base, l’enclosure et la console. L’enclosure et la console
sont mécaniquement attachées, alors que l’enclosure et la base sont reliées par une articulation
se qui permet une rotation libre de l’enclosure indépendamment de la base. L’enclosure
comporte deux ceintures de capteurs, une ceinture de capteurs à ultrasons de type polaroid et
une ceinture de capteurs infrarouges de type GP2D02. La base quant à elle comporte une autre
ceinture de capteurs à ultrasons polaroïd. La console supporte la caméra CCD et l’interface
rFLEX. Un télémètre laser est aussi embarqué sur le robot mobile, celui-ci est placé dans la
partie inférieure de l’enclosure, donc l’orientation du laser suivra celle du robot.
Le robot mobile B21R est aussi muni d’odomètres qui servent à mesurer le déplacement et
l’orientation effectués par le robot. Les données provenant de ces capteurs sont présentées de
façon à donner la position du robot mobile en X et Y ainsi que son orientation. De ce fait la
position du robot peut être directement lue.
Dans ce type de robots, toutes les roues tournent en même temps et roulent de la même
façon. C’est ce qui mène à un comportement non holonome. Les quatre roues pointent dans la
Roue
Console
Enclosure
Base
Ceinture Ultrasons
Infrarouges
Laser
Caméra CCD
Vue de l’extérieur Vue de l’intérieur
Laser
Moteur de déplacement Moteur d’orientation
Chaine de déplacement Chaine d’orientation
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
42
même direction et roulent à la même vitesse. Ceci est typiquement réalisé par l'utilisation d'une
collection complexe de ceintures qui lie physiquement les roues ensembles et synchronise leur
mouvement. Pour la locomotion, le robot possède deux moteurs indépendants : un pour la
translation et l’autre pour l’orientation. L’ensemble du mécanisme : moteurs, roues et la
collection de ceintures se situent dans la base, qui ne tourne pas lors de la rotation des roues.
Contrairement, l’enclosure tourne d’une façon synchrone avec l’orientation des roues [1].
Les vitesses (rotation et translation) du robot à traction synchrone (synchro drive) peuvent
être positives ou négatives. Cela signifie qu’il peut se déplacer en avant ou en arrière, tourner
sur lui-même ou en suivant un virage.
Tous les capteurs et les actionneurs sont connectés au bus FARnet du robot et contrôlés par
un ordinateur embarqué. Ce dernier est un Pentium PC avec dual 800Mhz processeurs avec un
système d’exploitation Linux (Redhat v6.2). Le système communique avec un autre ordinateur
extérieur par l’intermédiaire des ports illustrés par Figure.III.2.
Deux antennes BreezeCom pour une communication Ethernet sans fils.
Un port série pour une communication série avec un autre ordinateur.
Un port Ethernet (RJ45) pour une connexion directe à un réseau local.
Figure.III.2. La structure matérielle de la console B21R
Ecran rFLEX
Port série de la console
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
43
III.2.2. Architecture logicielle
Le robot B21R est contrôlé par le système rFlex de la société iRobot, fournissant des
contrôles standardisés et une interface utilisateur facile à utiliser et conviviale permettant
l’interaction avec l’utilisateur à travers un ensemble de menus permettant la gestion des
capteurs ultrasonores, les moteurs et autres systèmes embarqués. Ce système est considéré
comme le système nerveux central du robot mobile B21R où les câbles, nœuds et Hubs sont
faciles à configurer et son réseau est très optimisé pour lier les capteurs embarqués et les
actionneurs à son ordinateur du traitement central.
Le contrôle software se fait par MobilityTM, logiciel distribué, toolkit orienté objet pour la
construction de programmes de contrôle d’un seul ou plusieurs robots de la famille iRobot. Le
logiciel Mobility utilisé est basé sur CORBA. Il collecte les données en provenance des capteurs
embarqués, les interprète et les exécute. En utilisant CORBA, tous les capteurs et les
actionneurs peuvent être vus comme des ressources Internet. C’est une librairie composée de
programmes écrits en C & C++ contrôlant le hardware du robot mobile B21R.
La connexion avec les différents capteurs embarqués se fait en exécutant le programme
serveur qui réagit réciproquement avec le capteur. Ce dernier se connectera à son tour au name
server. Chaque capteur peut être donc connecté et contrôlé par un simple programme écrit en C
incluant les fonctions et procédures fournies avec Mobility.
III.3. Génération de points par le télémètre Laser
Le dispositif de balayage laser, monté sur le robot B21R, est un SICK de type PLS-101-312
(Proximity Laser scanner) situé au centre du robot (Figure.III.3) qui génère un faisceau
lumineux qui tourne dans un plan horizontal parallèle au sol. Ainsi, une plage de balayage, à
l'instant k discret, peut être définie comme un ensemble de points représentés en
coordonnées polaires, sous forme de liste couplé de distances et d'angles ,
correspondant à des intersections successives du rayon laser avec les plus proches objets de
l’environnement [26].
Les angles de balayage sont disposés consécutivement et sont espacés régulièrement avec
une certaine résolution angulaire . La séquence de balayage est indexée par j, qui représente
un nombre entier compris entre 0 et une valeur maximale N.
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
44
Nous avons un système de coordonnées du télémètre au temps discret k. En supposant que
l'axe des X est aligné avec le faisceau laser à , Alors:
(III.1)
Les coordonnées cartésiennes des points scannés sont données par :
(III.2)
Figure.III.3. La position de l’obstacle P dans la référence du robot pour
Figure.III.4. Les coordonnées cartésiennes et polaires d’un scan Laser
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
45
III.4. L’algorithme ICP – Iterative Closest Point
L’algorithme itérative closest point (ICP) est largement utilisé de nos jours pour
l’appariement de deux nuage de points 2D & 3D. Il a été introduit en 1992 par Besl & McKay
[19].
En dépit de sa popularité, particulièrement pour l'appariement de surface 3D (Chan
et Medioni, 1991) [18], (Besl etMcKay, 1992) [19], (Zhang, 1992) [29], y compris en
3D SLAM (Surmann et al. 2004), seules quelques applications de l'ICP ont été signalés pour
l'estimation 2D du mouvement de robot mobile. Depuis notre objectif est d'utiliser la méthode
de la mise en correspondance 2D, ce qui suit est une description d'un pur deux dimensions
point par point (point-to-point) de l'algorithme ICP (c'est-à-dire sans calculs de la tangente)
ainsi son application pour le SLAM [26].
Pour cela, nous supposons que le robot est dans une position de référence notée . Il
prend un premier scan noté . Maintenant, le robot se déplace dans l’environnement vers
une nouvelle posture , par rapport au repère de référence, il prend un nouveau scan .
La différence approximative de la position à partir de la position (translation et
rotation) est habituellement connue par odométrie. Cependant, cette information est souvent
imparfaite et cela est dû au patinage, glissement des roues et aux erreurs des capteurs. Notre
première tâche consiste à déterminer la vraie position en alignant les deux scans
( , ) [21].
Figure.III.5. Objectif de l’ICP
PRef
PNew
PCorrigé SRef SNew
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
46
L’algorithme ICP comporte en général trois étapes essentielles. On peut les représenter sous la
forme de la (Figure.III.6).
Figure.III.6. Organigramme de l’ICP
III.4.1. Projection du nouveau scan
Pour faire une comparaison entre deux points ou bien deux nuages de points (donnés par le
capteur télémétrique), représentés dans deux repères différents, il faut d’abord les mettre dans
le même système de coordonnées (repère).
Le nouveau scan acquis par le robot est défini dans le repère local du robot dont la
position, , est donnée par l’odométrie et est exprimée dans le repère . Nous voudrions
projeter le nouveau scan ( : la projection de ). Ceci est fait facilement par un
Début
Initialisation des paramètres
par odométrie
Projection de dans le repère de
Association de avec
Estimation des paramètres
(
Critère
d’arrêt
Arrêt
Oui Non
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
47
changement de système de coordonnées pour les points du scan en utilisant la matrice de
transformation homogène entre les deux repères [21].
L’objectif de l’alignement est d’estimer la matrice de rotation de dimension (2x2) et le
vecteur de translation t de dimension (2x1) tels que :
(III.3)
Avec :
,
Donc,
(III.4)
(III.5)
III.4.2. L’association de données
Dans cette étape, nous devons déterminer, pour chaque point du scan , son
correspondant dans le scan de référence . Pour cela, nous calculons d’abord la distance
entre chaque point du scan et tous les points de , ensuite la distance minimale
correspond à l’associe des points de . Il existe plusieurs méthodes pour trouver le plus
proche voisin connu sous le nom de NN (Nearest-Neighbour), telles que la méthode « k-d tree »
[27]. Notre travail est basé sur la distance Euclidienne. La (Figure.III.7) montre la mise en
correspondance entre le scan et . Le pseudo-code est donné par le (Tableau.III.1).
: la taille de
: abscisses du scan de
: ordonnés du scan de
: abscisses du scan de
: ordonnés du scan de
Tableau.III.1. Pseudo-code de l’association de données
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
48
Figure.III.7. La mise en correspondance
III.4.3. Estimation de la position
Il y a plusieurs méthodes dans la littérature qui abordent ce problème. Il y a des solutions
itératives basées sur le problème des moindres carrées non linéaires, quaternions, récursive,
décomposition en valeurs singulières…etc. Mais, le principe de l’ICP reste le même et consiste
à minimiser l’erreur quadratique moyenne (MSE).
a. Critère à minimiser pour aligner les scans
La bonne convergence de la position du robot par la méthode ICP est basée sur la
minimisation de l’erreur quadratique moyenne de la distance définie entre les points associés.
Cette erreur est une fonction de la matrice de rotation et la matrice de translation . Le critère
à minimiser s’écrit comme suit :
(III.6)
Avec :
I=c(i) : est le point de qui correspond au point de .
On a :
Donc,
(III.7)
(III.8)
C’est la fonction (III.8) qui sera utilisée comme critère de convergence. Car, l’idéal est d’avoir
(valeur optimale).
Association
SRef
SNew
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
49
b. Estimation des paramètres de transformation
L’une des méthodes utilisée pour l’estimation des paramètres , est une méthode
récursive. Le principe est de minimiser l’erreur quadratique moyenne (MSE) de la distance
entre les deux scans associés en dérivant l’équation (III.8) par rapport aux trois
paramètres . Alors, on trouve le système d’équations suivant :
Avec :
,
,
Les termes sont définis comme suit :
Le critère est optimal lorsque , alors on trouve les équations suivantes :
Cette méthode ne nécessite aucun calcul complexe. Elle n’utilise que les équations de (III.10).
Son principe est défini comme suit :
- La condition initiale est toujours donnée par l’odométrie.
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
50
- On fixe la valeur de et on détermine la nouvelle estimation de à partir des
deux premières équations de (III.10).
- En connaissant , on détermine la nouvelle valeur estimée de à partir de la
troisième équation.
Les étapes 2 et 3 sont répétées jusqu’à ce que les paramètres estimés ( convergent vers
une valeur fixe.
La méthode n’est valable que si la condition initiale est proche de la solution réelle. Par
ailleurs, l’odométrie nous donne en général une première estimation acceptable.
III.4.4. Résultats de validation de l’algorithme ICP
Afin de valider l’algorithme ICP présenté dans le paragraphe précédent, nous avons
effectué des simulations avec des données réelles. Les deux scans à aligner sont générés à partir
des nuages de points, la position de référence, la position perturbée donnée par
l’odométrie et est la position corrigée par l’algorithme ICP. Les résultats illustrés
dans la (Figure.III.8) montrent qu’après 25 itérations les deux scans sont parfaitement alignés
et par conséquent la position perturbée est corrigée.
Figure.III.8. Alignement des deux scans
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
51
Figure.III.9. Evolution des paramètres (
Figure.III.10. Evolution de l’erreur quadratique moyenne (MSE) de l’ICP
X [mm] Y [mm] [rad] MSE
Odométrie 1274 -248.6 -0.6245 86
ICP 1128 -115.6 -0.6408 6.032
Tableau.III.2. Tableau comparatif entre les valeurs obtenues par l’odométrie et ICP.
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
52
III.5. L’algorithme ICP basé SLAM
Dans ce qui a précédé, nous avons expliqué le principe de l’ICP qui a pour objectif
l’alignement des mesures et donc d’estimer la position du robot. Pour pouvoir utiliser le SLAM-
ICP dans un environnement réel, une étape est indispensable : la gestion de la carte.
La construction d’une carte exige, d’une part, le choix de la nature des représentations qui
vont la composer. Dans notre travail, nous avons choisi la représentation métrique basée sur les
points. D’autre part, elle devra être incrémentale, en fusionnant les données successives
acquises par le capteur télémètre à balayage laser du robot au cours de son déplacement.
Figure.III.11. Fusion de la carte locale
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
53
Figure.III.12. Organigramme SLAM-ICP
III.5.1. Résultats de validation de SLAM-ICP
Pour l’application au SLAM, on a fait déplacer le robot sur une trajectoire connue et dans
un environnement inconnu au niveau du CDTA. La figure suivante nous montre le chemin
parcouru par le robot sans correction (sans SLAM-ICP) et avec correction (avec SLAM-ICP),
avec un nombre d’itérations fixé à 25.
Le résultat obtenu nous montre bien la différence entre le résultat odométrique et le résultat
du SLAM-ICP, avec un alignement des scans corrigé qui implique une correction au niveau de
la posture du robot. Mais, si on parle de la bonne position, on ne peut rien dire, vu les scans qui
ne sont pas bien alignés (Figure.III.14) et l’erreur quadratique moyenne n’a pas été minimisée
efficacement. Ceci peut engendrer un biais au niveau de la position corrigée. Ce phénomène est
dû aux mauvaises correspondances qui est très connu dans les algorithmes de localisation.
Non Oui
Position corrigée
Destination
Atteinte
Arrêt du
Robot
Début
Initialisation des paramètres
par odométrie
Nouveau déplacement
Acquisition Odométrique
& Laser
ICP
Gestion de la carte globale
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
54
Figure.III.13. Environnement réel de la première scène (indoor)
Figure.III.14. La carte globale & trajectoire données par l’odométrie et par SLAM-ICP
Figure.III.15. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP de la dernière position
Odométrie Position estimée
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
55
III.5.2. L’algorithme SLAM-ICP proposé pour le re jet des mauvaises correspondances
L’algorithme ICP est très sensible aux mauvaises correspondances, d’où il est nécessaire de
rejeter entièrement certaines paires (valeurs aberrantes) qui peuvent avoir un biais sur
l’alignement des scans lors de l’estimation des positions [28].
Figure.III.16. (a) Lorsque deux scans à aligner ne chevauchent pas complètement (comme c'est le
cas pour la plupart des données réelles), ce qui donne des correspondances des points sur les
extrémités des scans qui peuvent introduire un biais systématique dans l'alignement. (b) Interdire de
telles paires en rejetant un grand nombre de ces mauvaises correspondances [28].
Pour cette raison, nous avons élaboré une méthode pour rejeter ces mauvaises correspondances,
en se basant sur une technique développée par [26].
Les pairs incompatibles peuvent être écartés par la définition d'une fonction booléenne pour la
détection des valeurs aberrantes:
Etant donné un seuil de correspondance E, par conséquent le nombre de correspondances
valide est donné par :
Le rapport qui indique le degré de chevauchement de toute transformation possible est donné
par:
La mise en correspondance exacte des points à partir des différents scans est impossible, en
raison d'un certain nombre de faits: la déformation causée par le déplacement du véhicule, les
gammes parasites, le bruit aléatoire, les inégalités du terrain, les zones occluses, des objets en
mouvement…etc. Alors, la mise en correspondance peut être considérée comme un problème
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
56
d'optimisation pour déterminer une transformation 2D qui minimise le critère de la bonne
correspondance .
L’indice de correspondance général pour une transformation donnée peut être
formulé par l'accumulation des erreurs d'appariement en divisant cette somme par pour
normaliser et par pour pénaliser les taux de faibles correspondances:
Finalement, les paramètres du mouvement sont mis à jour en minimisant l’équation (III.14),
avec la définition de l’équation d’erreur (III.8). Cette optimisation peut être résolue
analytiquement comme suit :
Où les termes S représentent les sommes suivantes :
Cette technique garantit la convergence vers un minimum local qui est proche de
l'estimation de l’odométrie [19], qui n'est pas nécessairement la solution optimale [29]. Notons
que le calcul le plus couteux de l'ICP est de trouver les points les plus proches de chaque
itération [26].
Le seuil E est un paramètre critique pour l’algorithme ICP. Certaines implémentations 3D
ont proposé un seuil adaptatif statistique [29]. Pour configurer ce paramètre correctement pour
l’estimation du mouvement 2D, la valeur de E peut être caractérisée à partir de calibration
expérimentale de l’incertitude odométrique [26]. Une limite supérieure des erreurs attendues
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
57
odométriques, pour chaque paramètre de la transformation, peut être exprimée en
, qui dépend de la durée t de navigation écoulée entre deux balayages consécutifs.
Puis, E est calculé comme une distance au carré :
III.5.3. Résultats de validation de SLAM-ICP proposé
Dans toutes ces expériences, nous avons fixé le nombre d’itérations à 25 pour l’algorithme
ICP, qui est utilisé comme critère d’arrêt.
La première scène (Figure.III.17) est la même scène utilisée pour la première méthode SLAM-
ICP (Figure.III.14), rien pour comparer les résultats obtenus.
III.5.3.1. Première scène de l’expérience
Figure.III.17. La carte globale & trajectoire données par l’odométrie et par SLAM-ICP proposé
(première scène)
Odométrie Position estimée
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
58
Figure.III.18. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la dernière
position (première scène)
III.5.3.2. Deuxième scène de l’expérience
Figure.III.19. Environnement réel de la deuxième scène (indoor)
Figure.III.20. La carte globale & trajectoire donnée par l’odométrie et par SLAM-ICP proposé
(deuxième scène)
Position estimée Odométrie
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
59
Figure.III.21. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la dernière
position (deuxième scène)
III.5.3.3. Troisième scène de l’expérience
Figure.III.22. Environnement réel de la troisième scène (indoor)
Figure.III.23. La carte globale & trajectoire donnée par l’odométrie et par SLAM-ICP proposé
(troisième scène)
Position estimée Odométrie
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
60
Figure.III.24. Evolution de l’erreur quadratique moyenne (MSE) de SLAM-ICP proposé de la dernière
position (troisième scène)
III.5.5. Discussion
A. La méthode donne de bons résultats, dans le cas où le seuil E (équation III.16) est
calculé correctement. L’auteur dans [26] a bien mentionné que celle-ci est définie à
partir d’une calibration expérimentale de l’incertitude odométrique. Evidement, le seuil
E diffère pour chaque robot mobile.
B. Concernant le critère d’arrêt de l’ICP, dans le cas ou l’environnement est considéré
connu, il suffit de fixer un seuil de l’erreur J (MSE) ou un nombre fixe d’itérations. Si
les valeurs atteignent ce seuil ou toutes les itérations fixées sont terminées, l’algorithme
ICP sort de la boucle pour traiter une nouvelle posture du robot. Dans le cas contraire
ou l’environnement est inconnu (comme notre cas), utiliser le nombre d’itérations
comme critère suffirait. Pour une convergence acceptable, on utilise souvent entre 20 –
25 itérations. Car, si on inclut l’erreur J, ceci pourrait ne pas converger rapidement, dû à
la complexité de l’environnement et au temps de calcul.
C. L’optimisation du temps de calcul du robot est primordiale. Comme nous l’avons
mentionné, le SLAM-ICP est très couteux en calcul dans l’étape de l’association de
données, et cela s’effectue en quelques millisecondes seulement pour traiter toutes les
données.
C’est pour cette raison, nous avons eu le reflexe de proposer une solution à ce problème
ou tous les chercheurs se concentrent dessus. L’idée est simple. A partir de la première
itération, on peut savoir si l’algorithme procède au calcul de l’ICP ou pas, en prenant
juste en considération la valeur de l’erreur J. Car durant la navigation du robot, on peut
bien tomber sur une position très proche de la position exacte, ou l’erreur entre les deux
Chapitre III La technique ICP (Itérative Closest Point) basée SLAM
61
scans peut être négligée. Cette proposition n’a pas été testée, mais c’est un projet qui
sera achevé dans l’avenir. Le pseudo-code est donné comme suit :
Tableau.III.3. Pseudo-code de la méthode d’optimisation de SLAM-ICP
III.6. Conclusion
Dans notre travail, nous avons passé en revue les approches proposées dans la littérature
afin de résoudre le problème SLAM. Parmi ces approches, nous avons opté pour une technique
de scan matching qui est l’algorithme ICP. L’algorithme a été validé dans un environnement
statique, qui nous a donné une amélioration par rapport aux valeurs odométriques.
Par la suite, nous avons présenté une amélioration de l’ICP en rejetant les mauvaises
correspondances dans divers environnements, afin d’assurer l’efficacité de la méthode. Les
résultats obtenus sont très satisfaisants. L’erreur quadratique moyenne (selon la définition de la
technique) est minimisée. Contrairement à certaines méthodes basées sur le filtre de Kalman
étendu (EKF) [1], on constate aussi que la méthode est très robuste même pour une longue
trajectoire (Figure.III.23).
Notons que certains auteurs utilisent les données GPS afin d’assurer la convergence de la
méthode élaborée [30], sachant qu’il possède un écart type de quelques centimètres, et parfois
même de quelques millimètres. Dans ce cas là, on peut dire que la méthode peut être applicable
à n’importe quel robot mobile doté d’un télémètre laser 2D, dans un environnement statique
(Indoor).
62
Conclusion Générale & perspectives
Le travail présenté dans ce mémoire s’inscrit dans le cadre de la navigation en robotique
mobile, il traite le problème de la localisation et la cartographie simultanées dans un
environnement d’intérieur statique. L’idée principale est de réaliser une carte la plus réelle
possible décrivant l’environnement d'évolution.
En premier lieu, nous avons présenté une modélisation cinématique des robots mobiles,
avec une étude détaillée du robot mobile B21R utilisé dans ce travail, ainsi qu'une
présentation des différents capteurs, disponibles sur le marché, utilisés dans la perception pour
les systèmes de robotique mobile.
En seconde, nous avons introduit les concepts de localisation et cartographie qui sont les
fonctions de base composant le problème SLAM. Trois types de cartes ont été discutés
(géométrique, grille d’occupation et topologique). Nous avons opté pour la carte géométrique
pour sa simplicité de calcul. Puis, le problème SLAM a été mis en évidence ainsi l’objectif de
la mise en correspondance des scannes (scan matching).
En suite, nous avons introduit la technique d’alignement des mesures télémétriques
utilisées pour résoudre le problème SLAM. Notre choix s’est focalisé sur l’algorithme ICP qui
fait partie des algorithmes les plus employés dans ce domaine. Les différentes étapes de
l’algorithme ont été illustrées ainsi qu’une simulation mettant en évidence la convergence de
cet algorithme.
Après cela, nous avons appliqué l’algorithme ICP pour le SLAM. Les résultats, à partir des
données réelles, obtenus démontrent bien l’efficacité de l’algorithme avec une grande
amélioration des scannes. Mais à un certain moment, nous constatons que les scannes sont pas
suffisamment alignés qui peuvent gravement influencer sur la position corrigée et ceci est dû
aux mauvaises correspondances des scannes.
En outre, afin de remédier à ce phénomène, nous avons proposé une méthode pour le rejet
des mauvaises correspondances. L’idée consiste à les effacer complètement avant chaque
estimation de la position, et ceci ce répète pour chaque itération de l’algorithme. Ceci a pour
63
résultat l’amélioration parfaite de la carte qui implique la correction de la position du robot,
qui prouve l’efficacité de l’algorithme
L’implémentation de la méthode sur le robot est partagée en deux parties, l’acquisition des
données et le traitement par la méthode SLAM-ICP. Dans notre travail, nous avons écrit un
programme en langage C++ afin d’acquérir les données laser et odométriques qui sont
ensuite stockés dans des fichiers pour d’éventuelles exploitations (utilisation offline). La
méthode SLAM-ICP a été implémentée en langage C++ aussi.
Comme perspectives, nous proposons :
Implémentation en temps réels de l’algorithme SLAM-ICP.
Adaptation de la méthode dans un environnement dynamique.
Implémentation de l’algorithme dans une boucle de navigation.
Application de l’algorithme dans un environnement extérieur (Outdoor).
ix
Annexes
Laser SICK PLS 101-312 « Proximity Laser Scanner »
Le PLS mesure son environnement dans un plan semi-circulaire - (angle de balayage est de
180°).
Le champ de protection (protective field), à la zone dangereuse d'une machine ou un
véhicule peut avoir un rayon
maximum de 4 mètres. Les PLS
arrête la machine ou arrête le
véhicule dans le cas d'intrusion
dans le domaine de protection.
Le champ d'alarme (warning
field) peut atteindre un rayon de 50
mètres. Il faut noter, cependant, que
le capteur est seulement capable de
détecter des objets avec une
réflectance d'env. 20 - 30% d'une
distance de 15 mètres.
x
La distance de mesure (measuring
range) du PLS s'étend à un rayon de
50 mètres. Jusqu'à ce que la distance
du PLS est capable de détecter le
contour de son environnement (par
exemple le contour spatial). Il peut
alors attribuer les données pour le
champ de protection et le champ
d'avertissement, à condition que la
réflectance de l'objet soit suffisante
pour être détectée.
Dimensions en (mm) du PLS
xi
Robot mobile B21R
xii
Références bibliographiques
[1] Bouraine Sara. Contribution à la localisation dynamique du robot mobile d’intérieur
B21r en utilisant la plateforme multi sensorielle. Thèse de magistère de l’université de
Blida, 2007.
[2] R.Siegwart, I.R.Nourbakhsh. Introduction to autonomous mobile robot. The MIT
press, ISBN 0-262-19502-X, 2004.
[3] J. Borenstein, « Internal Correction of Dead-reckoning Errors With the Compliant
Linkage Vehicle», Journal of Robotic Systems, Vol. 12, No. 4, pp. 257-273,
University of Michigan, Ann Arbor, USA, April 1995.
[4] J. Borenstein, « Internal Correction of Dead-reckoning Errors with the Smart Encoder
Trailer », International Conference on Intelligent Robots and Systems, vol1, pp. 127–
134, Munich, Germany, 1994.
[5] J. Borenstein, « Experimental results from internal odometry error correction with the
OmniMate mobile robot», IEEE Transactions on Robotics and Automation, vol. 14,
pp. 963– 969, University of Michigan, Ann Arbor, USA, 1998.
[6] A.Ferrand. Conception et mise en œuvre d'un système de capteurs proprioceptifs
destiné à la localisation relative des robots mobiles. Thèse de l'université de Toulouse,
LAAS, 1991.
[7] J. Borenstein, L. Feng. Gyrodometry : a new method for combining data from gyros
and odometry in mobile robots. Proceedings of the IEEE International Conférence on
Robotics and Automation, pp. 423- 428, 1996.
[8] J. Vaganay. Conception d’un système multisensoriel de localisation dynamique 3D
pour robot mobile. Thèse de doctorat, LIRMM, Montpellier, juillet 1993.
[9] José Armando Segovia de Los Rios. Etude des déplacements d’un robot mobile dans
un environnement peu contraint. thèse de doctorat, Université de Technologie de
Compiègne, France, Septembre 1993.
[10] Alain COURCELLE. Localisation d’un robot mobile : Application à l’aide à la
mobilité des personnes handicapées moteur. Doctorat de l’Université de Metz, France,
janvier 2000.
[11] C. Gourley, M. Trivedi, “Sensor Based Obstacle Avoidance and Mapping for Fast
Mobile Robots”, Proceedings of the IEEE International Conference on Robotics and
Automation, 1994, pp. 1306-1311.
xiii
[12] Y. D. Kwon, J.S. Lee, « A stochastic Environment Modelling Method for Mobile
Robot by using 2-D Laser scanner », Proceedings of International Conference
IROS’97, pp. 1688-1693, Albuquerque, USA.
[13] J. P. Laumond. La robotique mobile. Hermès Sience Publications, 2001, Paris, ISBN
2-7462-0246-8.
[14] David FILLIAT. Robotique Mobile. Cours C10-2, ENSTA, France, Octobre 2004.
[15] Vincent Ricquebourg. Identification, Localisation et Suivi de personnes au sein d’un
habitat intelligent. Diplôme d’études approfondies, université de Rouen et université
de Picardie Jules Verne, septembre 2004.
[16] Cyril Drocourt. Localisation et modélisation de l'environnement d'un robot mobile par
coopération de deux capteurs omnidirectionnels. Thèse doctorat, université de
technologie de Compiègne, février 2002.
[17] J.Minguez, F.Lamiraux, L.Montesano. Metric-bases scan matching algorithm for
mobile robot displacement estimation. ICRA, 2005.
[18] Y.Chan, G.Medioni. Object modeling by registration of multiple range images. IEEE
ICRA, April 1991.
[19] Besl.P.J, McKay.N.D. A method for registration of 3D shapes. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 14:239–256, 1992.
[20] Ben-Jemaa.R, Schmitt.F. Recalage 3D. Traité IC2 "Information, Commande,
Communication", Volume "Images de Profondeur", 2002.
[21] Lu.F, Milios.E. Robot pose estimation in unknown environments by matching 2D
range scans. Journal of Intelligent and Robotic Systems, 18:249–275, 1997.
[22] D.Hahnel and W.Burgard. Probabilistic matching for 3D scan registration. In Proc of
the VDI-Conference Robotik (Robotik), 2002.
[23] C.F. Olson, D. P. Huttenlocher. Automatic target recognition by matching oriented
edge pixels. IEEE Transactions on Image Processing, 6(1):103–113, January 1997.
[24] P.Biber and W.Straber. The normal distributions transform: A new approach to
laser scan matching. In IEEE/RSJ International Conference on Intelligent
Robots and Systems, pages 2743–2748, 2003.
[25] F.Boughorbel, A.Koschan, B.Abidi, and M.Abidi. Gaussian fields: a new criterion for
3D rigid registration. Pattern Recognition, pp 1567–1571, 2004.
[26] J.Martínez. L.González, J.Morales, J.A.Mandow and A.J.García-Cerezo. (2006),
Mobile robot motion estimation by 2D scan matching with genetic and iterative
closest point algorithms. Journal of Field Robotics, 23: 21–34. doi:
10.1002/rob.20104.
xiv
[27] A.Nüchter, K.Lingemann, J.Hertzberg. Cached k-d tree for ICP algorithms. IEEE
ICRA, 2007.
[28] S.Rusinkiewicz, M.Levoy. Efficient variants of the ICP algorithm. In Proc. 3th Int.
Conf. on 3D Digital Imaging and Modeling, pages 145–152, Canada, 2001.
[29] Zhang, Z. (1992). Iterative point matching for registration of free-form curves.
Technical Report 1658, INRIA, France.
[30] Juan Nieto, Tim Bailey, Eduardo Nebot. Recursive scan-matching SLAM. Robotics
and Autonomous Systems, 55: 39–49, 2006.
Résumé
Les robots mobiles autonomes peuvent être appliqués pour effectuer des activités qui ne
devraient pas, ou ne peuvent pas être dispensés par des humains en raison des conditions
inhospitalières ou le niveau élevé de danger. Un robot mobile autonome doit être capable de
naviguer en toute sécurité dans des environnements inconnus, en reconstruisant des
informations de ses capteurs afin de planifier et d'exécuter les routes. La localisation et
cartographie simultanées (SLAM), est une méthode utilisée pour remédier à ce problème, la
technique permet la création progressive d'une carte en utilisant les données obtenues à partir
des capteurs tout en estimant la localisation du robot mobile. L’algorithme du scan matching
Iterative Closest Point (ICP) est l'une des approches adoptées pour le SLAM, basée sur la
correspondance des points à partir des données laser 2D. Ce travail propose un algorithme
ICP basé SLAM. Notre algorithme a été simulé et implémenté sur le robot mobile B21R dans
un environnement d’intérieur. Les résultats montrent que la méthode présentée dans ce travail
(basé sur le rejet des mauvaises correspondances des points) a une meilleure performance que
celle obtenue par l'algorithme ICP original.
Mots clés : SLAM, ICP, scan matching, localisation, cartographie, robot mobile
Abstract Autonomous mobile robots can be applied to perform activities that should not, or cannot,
be performed by humans due to inhospitable conditions or high level of danger. An
autonomous mobile robot must be able to navigate safely in unfamiliar environments by
reconstructing information from its sensors so as to plan and execute routes. Simultaneous
Localization And Mapping (SLAM), is a technique used to remedy to this problem, the
technique allows the gradual creation of a map using data obtained from sensors while
estimating the mobile robot localization. The Iterative Closest Point (ICP) scan matching
algorithm is one of the approaches adopted for SLAM, based on matching points from 2D
laser data. This work proposes an ICP algorithm based SLAM. Our algorithm has been
simulated and implemented on the mobile robot B21R in indoor environment. The results show
that the method presented in this work (based on rejecting unmatchable points) has a better
performance than the one obtained by the original ICP algorithm.
Keywords: SLAM, ICP, scan matching, localization, mapping, mobile robot
Recommended