La version de base de l’algorithme Tangent BUG

Télécharger le fichier pdf d’un mémoire de fin d’études

Définition du robot

Il existe plusieurs définitions d’un robot :
• Robot n.m. (du tchèque robota, travail forcé, corvée). Définition 1 : Dans les œuvres de science-fiction, machine à l’aspect humain, capable de se mouvoir, d’exécuter des opérations, de parler. Définition 2 : (Technique). Appareil automatique qui, capable de manipuler des objets ou d’exécuter des opérations selon un programme fixe ou modifiable, voir par apprentissage. [56].
• Un appareil automatique qui peut effectuer des fonctions normalement effectués par des humains. Traduit du dictionnaire Webster’s [60]
• [Dans des œuvres de fiction sc]. Machine, automate à l’aspect humain capable d’agir et de parler comme un être humain… [61].
• [Domaine technique]. Appareil effectuant, grâce à un système de commande automatique à base de micro-processeur, une tâche précise pour laquelle il a été conçu dans le domaine industriel, scientifique ou domestique. [61].
• Machine automatique dotée d’une mémoire et d’un programme, capable de se substituer à l’homme pour effectuer certains travaux. [62].

La robotique

Ensemble des techniques permettant la conception et la réalisation de machines automatiques et de robots. Ce terme a été utilisé pour la première fois par le romancier Isaac Asimov dans son récit de science-fiction «Menteur !», publié en 1941 [55].

Evolution de la robotique

Le défi de DARPA (Defense Advanced Research Projects Agency) donne un bon aperçu de la vitesse de progression de la robotique. En 2004, l’objectif de ce défi était de réaliser une navigation autonome de 96 km, en ville, tout en respectant le Code de la route et en prenant en compte la circulation extérieure : piétons et autres voitures non automatiques. En 2004, aucune voiture n’a pu réaliser plus de 11.78 km. En 2005, cinq véhicules ont terminées cette couse dont l’équipe la plus rapide était celle de Stanford avec un temps total de 6 heures et 54 minutes.
En 2012, un autre défi a été réalisé par Google c’est de conduire un aveugle de son domicile à un commerce local par une voiture automatique.
Le rapport PIPAME sur Le développement industriel futur de la robotique personnelle et de service en France (Erdyn Consultants, 2012) estime qu’en 2015, au niveau mondial, le marché de la robotique de service personnelle représentera 8 milliards de dollars tandis que le marché de la robotique de service industrielle représentera, quant à elle, 18 milliards de dollars [45] (Figure 3).

Domaines d’applications

Le domaine de la robotique est en plein essor depuis quelques années. Les évolutions technologiques, dépassant sans cesse nos espérances, elles permettent de réaliser des solutions technologiques s’adaptant au moindre problème.
La robotique est utilisée dans beaucoup de domaines qui sont extrêmement rigoureux et exigeants. Nous allons explorer quelques domaines.

Exploration

NASA utilise les robots dans l’exploration d’autres planètes (exemple de Sojourner en 1997 (Figure 4), et Spirit en 2003) ; pour beaucoup de raison l’un est l’économie. Les robots sont utilisés aussi dans l’exploration sous-marine.

Industriel

Les robots sont utilisés très largement dans le domaine de l’industrie, l’assemblage des voitures et des cartes électroniques, la peinture, le transport, le nettoyage,…

Agriculture

L’agriculture est l’un des nouveaux domaines où la robotique est introduite, il existe maintenant des robots pour faire la majorité des travaux agricoles, allant de la plantation jusqu’à la récolte.

Militaire

Les robots sont de plus en plus utilisés dans le domaine militaire. Les armés modernes se convergent vers l’utilisation des robots à la place des soldats, les robots sont utilisés dans les missiles intelligentes, les missions de reconnaissance et d’espionnage (guerre de golf 2000 et 2003, guerre de Lebanon 2006),…

Civile

Dans ces jours, il n’est pas étonnant de trouver un robot qui fait le ménage, le nettoyage ou même la cuisine.

Médical

Le domaine médical n’est pas une exception, des nouveaux techniques sont découvertes, les robots interviennent dans la chirurgie, ainsi que la télé-chirurgie.
Le robot « Da Vinci » est un robot médical qui peut opérer et diagnostiquer les patients. 1242 exemplaires étaient utilisés dans le monde en juin 2009 [63].

Perception de l’environnement

Pour qu’un robot avance vers une destination quelconque, ou même faire n’importe quoi il doit avoir une connaissance de son environnement local (au minimum une partie de cet environnement). Pour cela les robots sont alimentés avec des capteurs de différents types voici les deux types de capteurs utilisés dans la perception :

Les différents types de capteurs

Il existe deux types de capteurs :
• Proprioceptifs : mesurent l’état du robot lui-même (capteur de position (GPS), capteur de vitesse, capteur de charge de batteries, …).
• Extéroceptifs : renseignent sur l’état de l’environnement (capteur de température, télémètre (RADAR, LIDAR), boussole, détecteur de chaleur/lumière, …) [55].

Capteurs proprioceptifs

Quelques exemples très utilisés dans l’actualité :
1. Capteurs ultrason
Les capteurs ultrason sont les premiers capteurs utilisés dans les robots. Le principe de ces capteurs est la mesure du temps de retour d’une onde sonore réfléchie par les obstacles pour estimer la distance des obstacles.
Les capteurs ultrason utilisent des ondes sonores non audibles par l’oreille humaine. La fréquence ultrason est trop élevée (le son est très aigu) supérieure à 20000Hz [63].
La Figure 13 présente un capteur de Parallax, ce capteur est adaptable à la fois sur les Boe-Bot et les Sumobot. Les caractéristiques techniques de ce produit sont :
– Mesure de distance : entre 2 centimètres et 3,3 mètres.
– Erreur moyenne inférieure à 0,5 centimètres.
– Fréquence d’émission : 40 Hz.

Capteurs extéroceptifs

Ces types de capteurs renseignent sur l’état de l’environnement et non pas du robot, l’utilisation des caméras et la vision sont des éléments centraux. Les caméras produisent une quantité très importante d’informations pour les traiter il faut une puissance de calcul et une quantité importante de mémoire, ce qui rend leur utilisation dans les robots mobiles très limitée. Toutefois, les caméras sont utilisées de plus en plus [45] [71] [72].
D’autres types de capteurs très variés sont utilisés, par exemple les capteurs de chaleurs dans la recherche des feux à titre d’exemple [67] (ce projet est sponsorisé par le bureau de recherche naval américain), aussi les détecteurs de champs magnétiques ou autres types de champs [26]. On voit en outre l’utilisation des sonars dans les robots sous-marins [41] [44].

Localisation

Pour que le robot puisse naviguer dans son environnement, il doit se localiser dans l’environnement. La localisation est l’estimation de la position du robot par rapport à un repère fixe de l’environnement. La localisation est un facteur très important dans la conception des robots. Sans avoir la possibilité de se localiser un robot ne peut pas se déplacer.
Une des définitions de la localisation c’est l’ensemble des capteurs et des techniques permettant au véhicule de naviguer de manière autonome ou semi-autonome dans son environnement [46].

Navigation

La localisation relative : permet au véhicule de naviguer à l’estime (dead reckoning) en utilisant uniquement les mesures de ses mouvements propres fournies par ses capteurs proprioceptifs.
La localisation absolue : utilise les mesures des capteurs extéroceptifs pour estimer la position du véhicule dans un repère lié à l’environnement. Les capteurs extéroceptifs permettent de recaler périodiquement la localisation obtenue par la mesure des mouvements [53].

Méthodes de recherche de trajectoire

Le problème de recherche de trajectoire a tiré l’attention des chercheurs depuis les années 70 et jusqu’à nos jours, beaucoup de travaux de recherches ont été effectués dans ce domaine qui englobent trois autres problèmes : localisation, planification et contrôle de mouvement.
Les années 80, c’est la naissance des algorithmes Bug pour recherche de trajectoire (Bug). Le premier algorithme est Bug1 créé en 1984 par Lamelsky [1] [2] [3].
Dans les années 1990-1999, beaucoup de méthodes classiques ont vu le jour :
Bug3 hybridation de Bug1 et Bug2 1996 [24], Tangent Bug par Ishay Kamon en 1997 [49] la version finale en 1998 [12], ainsi que l’arrivée des méthodes du champ de potentielle Hussien en [48]. On voit aussi la naissance des méthodes heuristiques D* ou Dynamique A* inventé en 1994 par Anthony Stentz [20].
Dans ces dernières années (2000-2013), beaucoup de recherches s’attachent à l’extension de l’algorithme A* : A* modifié (connu Physical A*) [48], Focussed Dynamique A* par Stenz [20] [37], Extended A* par Matous Pokorny [19], ARA ARA+ [15], Improved D* par Jianming GUO en 2009 [17], Improved A* par Dongmei Zhang en 2010 [18].
Néanmoins l’arrivée de nouvelles approches de recherche de trajectoire, on voit toujours l’apparition de certains algorithmes de type Bugs des fois plus optimales tel que : HD1 Hiroshi Noborio en 2000 [27], Ave par Hiroshi Noborio en 2004 [21], K-Bug par Ricardo A. en 2007 [13], Point Bug par Buniyamin N. en 2011 [14], Dynamic Point Bug par B. Margaret Devi en 2013 [16]. Dans le présent chapitre on va exposer les différentes méthodes de recherche de trajectoire leurs principes, avantages et inconvénients.
Il existe deux classes principales de méthodes de recherche de trajectoire pour les robots mobiles [63]:
1- Les méthodes déterministes : Elles trouvent toujours le même résultat (le même chemin) si on applique les mêmes conditions initiales. Les algorithmes classiques (Bug), Heuristiques (Compositions cellulaire), Champ de potentiel, Diagramme de Voronoï,…). Elles sont déterministes parce qu’elles garantissent de trouver une solution s’il existe une au moins.
2- Les méthodes probabilistes : Elles ne trouvent pas forcement le même chemin même en appliquant les mêmes conditions initiales. On trouve deux sous-catégories :
a. Les méthodes d’échantillonnage : on prend un échantillon puis on lui applique des traitements jusqu’à l’arrivée à une solution.
b. Les méthodes de diffusion : Effectuent une recherche aléatoire jusqu’à trouver une solution.
La plupart des méthodes exposées dans ce chapitre appartiennent à la première classe.

Méthodes Bug

Les méthodes Bug sont les premières méthodes de recherche de trajectoire, elles sont des méthodes basées sur deux comportements du robot (Figure 21) : (1) l’avancement en ligne droite vers la destination, (2) et l’évitement des obstacles. La grande différence entre ces méthodes se réside dans la condition de basculement entre ces deux comportements.
Autre caractéristique de cette famille d’algorithmes est leurs simplicités dans leurs principes et implémentations (plus ou moins) ce qui les rend plus adéquats pour être implémentées sur des robots à cartes électroniques de moyenne et faible gamme.

Avantages

– Les méthodes Bugs sont intéressantes parce qu’on peut les appliquer dans un environnement inconnus (elles sont indépendantes de la géométrie de l’environnement).
– La plupart d’entre elles sont convergentes qui veut dire elles trouvent un résultat.
– N’utilisent pas de fonctions mathématiques complexes (racine, sinus,..), et ne demandent pas d’espace mémoire énorme d’ailleurs certaines algorithmes de cette famille n’utilisent même pas une mémoire.
– Simple à implémenter sur des robots réels.
– Les résultats donnés par les tests réels prouvent l’efficacité de ces algorithmes.

Inconvénients

– Certains algorithmes de cette famille ne sont pas convergents.
– Dans la plus part des algorithmes la longueur du chemin peut-être soit meilleure ou très mauvaise mais pas moyenne.
– Le résultat de l’algorithme dépond de l’environnement, et la convergence de certains algorithmes ne peut pas être prouvée théoriquement.
– Certains algorithmes restent théoriques parce qu’ils supposent l’utilisation d’un matériel idéal ou des capteurs à distance illimités.

Méthodes heuristiques

Ces méthodes se basent sur des estimations du coût de trajectoire. L’algorithme utilisé essaye de minimiser la fonction du coût choisi (le tableau dans Figure 22 présente quelques fonctions de coût utilisées).
Dans les méthodes heuristiques l’environnement du robot (la carte géographique) est divisé en plusieurs cellules ou cases (Grid). Si une case contient un pourcentage d’obstacle que soit petit ou grand elle est déclarée comme obstacle sinon elle sera déclarée comme libre (pas d’obstacle) et le robot peut passer par elle.
Pour trouver son chemin le robot utilise une fonction de coût qui sera calculée à chaque case, l’objectif du calcul est de minimiser cette fonction.
La différence entre les algorithmes heuristiques réside dans cette fonction (et rien d’autre).
A chaque position du robot les coûts de toutes les cases voisines sont recalculés et la case ayant le coût minimal sera la prochaine position du robot [73].

Avantages

– S’il existe un chemin l’algorithme finira par le trouver (selon certaines conditions).
– Pas de boucles ou oscillations infinies, un chemin ne peut être parcouru qu’une seule fois.
– Peut-être adapter facilement pour qu’elles prennent en considération l’état et la nature du terrain [39].

Désavantages et problèmes

Les méthodes heuristiques comportent pas mal de problèmes. Beaucoup de recherches ont essayées de les éliminer ou du moins les minimiser, on va exposer quelques-uns de ces problèmes.

Chemin très proche ou très loin des obstacles

Ce problème fait qu’on est obligé d’appliquer des modification à la carte de l’environnement (filtre Blur de Gauss : Gaussian Blur) afin que le chemin soit un peu plus loin des obstacles, c’est pour ça que la formule de base est modifiée d’un algorithme à un autre, quelques formules les plus utilisées sont présentées dans la Figure 22.

Table des matières

1. INTRODUCTION
1.1. DEFINITION DU ROBOT
1.2. LA ROBOTIQUE
1.3. EVOLUTION DE LA ROBOTIQUE
1.4. DOMAINES D’APPLICATIONS
1.1.1. Exploration
1.1.2. Industriel
1.1.3. Agriculture
1.1.4. Militaire
1.1.5. Civile
1.1.6. Médical
1.1.7. Musique
1.5. TYPES DE ROBOTS
1.5.1. Robot manipulateur
1.5.2. Robot mobile
2. NAVIGATION
2.1. PERCEPTION DE L’ENVIRONNEMENT
2.2. LES DIFFERENTS TYPES DE CAPTEURS
2.2.1. Capteurs proprioceptifs
2.2.2. Capteurs extéroceptifs
2.3. LOCALISATION
3. METHODES DE RECHERCHE DE TRAJECTOIRE
3.1. METHODES BUG
3.1.1. Avantages
3.1.2. Inconvénients
3.2.1. Avantages
3.2.2. Désavantages et problèmes
3.3. CHAMPS DE POTENTIEL
3.3.1. Avantages
3.3.2. Inconvénients
3.4. ALGORITHMES GENETIQUES
3.4.1. Avantages
3.4.2. Inconvénients
3.5. AUTRES METHODES
4. METHODES BUG D’EVITEMENT D’OBSTACLES
4.1. L’ALGORITHME BUG1
4.2. L’ALGORITHME BUG2
4.3. L’ALGORITHME ALG1
4.4. L’ALGORITHME ALG2
4.5. AUTRES VARIATIONS DES ALGORITHMES BUG1 ET BUG2
4.5.1. L’algorithme BUGM
4.5.2. L’algorithme BUG3
4.6. L’ALGORITHME AVE
4.7. L’ALGORITHME DISTBUG
4.8. ALGORITHME TANGENTBUG
4.8.1. La version de base de l’algorithme Tangent BUG
4.8.2. La version finale de Tangent BUG
4.9. K-BUG
4.10. POINT BUG
4.11. L’ALGORITHME DYNAMIC POINT BUG
5. APPROCHES PROPOSEES
5.1. AVANTAGES DE L’ALGORITHME POINT BUG
5.2. PROBLÈMES DE L’ALGORITHME POINT BUG
5.2.1. Tours infinis
5.2.2. Omission des chemins
5.2.3. Tests d’arrêts
5.3. SOLUTION PROPOSÉE
5.4. SIMULATION
6.1. CONCLUSION GENERALE
6.2. PERSPECTIVES
7. REFERENCES

Télécharger le rapport complet