PROJET ROBOTIQUE MOBILE

CARTOGRAPHIE ET PLANIFICATION

Thomas BRETGELD
bretgeld@ensta.fr

Guillaume GALTIER
galtier_guillaume@hotmail.com

Mercredi 22 Février 2006



OBJECTIFS DU PROJET:

Les deux objectifs principaux de ce projet étaient de:

Algorithmes utilisés: cartographie supervisée, Dijkstra, transformée en distance...



OUTILS UTILISES:

Plateforme Linux KDE Fedora Core 4.

Player/Stage et sa bibliothèque de fonctions C++ (http://playerstage.sourceforge.net), logiciel permettant la simulation de robots plongés dans un environnement fourni sous forme de dessin bitmap.

C++ avec bibliothèque d'interface graphique QT (http://www.trolltech.com/products/qt/index.html)



PRESENTATION DETAILLEE:

Notre projet a commencé par l'étude du fonctionnement du programme exemple fourni (code): celui-ci réalise une représentation locale des informations fournies par le télémètre laser d'un robot évitant les obstacles et nous a permis de nous familiariser avec l'interface graphique QT ainsi qu'avec la bibliothèque de fonctions Player/Stage utilisées.

Notre projet comporte clairement deux parties identifiées: nous avons donc naturellement segmenter notre travail suivant ces deux parties.

  1. Une partie cartographie. En temps réel, il s'agit d'afficher l'ensemble de l'environnement dans lequel évolue le robot au fur et à mesure que son télémètre laser renseigne sur la présence ou non d'obstacles. Pour simplifier, nous avons défini 3 états pour une case de l'espace (ces cases correspondant dans notre cas à des pixels). Un état EMPTY qui correspond à une zone découverte part le robot et certifiée comme ne contenant pas d'obstacle. Un état OCCUPIED qui correspond à une zone découverte par le robot et certifiée comme contenant un obstacle. Enfin, un état UNKNOWN traduisant soit une zone non encore découverte par le robot soit une zone découverte mais dont il n'est pas encore possible de dire si elle est OCCUPIED ou EMPTY. Il s'agit donc d'une grille d'occupation à 3 états (voir Figure 1). Pour certifier si une zone est EMPTY ou OCCUPIED et ainsi sortir de l'état UNKNOWN nous avons défini un seuil THRESHOLD qui correspond au nombre minimal de fois ou une zone a été vue par le télémètre dans un état donné. Il existe aussi des limites pour le compteur au delà de +THRESHOLD (resp. - THRESHOLD)  pour éviter que le compteur s'incrémente (resp. décrémente) indéfiniment.


Le choix de ce seuil permet d'avoir des contours qui sont "stables" dans le temps.

Connaissant alors a tout moment la position exacte (GPS) du robot dans l'environnement fourni au simulateur ainsi que la direction du robot par rapport à une direction de référence et ayant accès aux données télémétriques sur le demi plan frontal du robot (360 mesures sur 180 degrés soit une mesure tous les 0,5 degrés) il est alors possible de mettre à jour une variable d'état correspondant à tout moment à la grille d'occupation perçue de l'environnement. La cartographie est réalisée.

  1. Une partie plus délicate de planification qui nécessite plusieurs étapes.

    D'abord la définition et le repérage d'une cible à aller explorer. Le critère que nous avons retenu dans un premier temps est la présence, dans un masque de 5*5 pixels centré sur le pixel courant à l'état EMPTY, d'au moins 5 pixels dans l'état UNKNOWN et 5 pixels dans l'état EMPTY mais aucun dans l'état OCCUPIED. Ceci se comprend car l'intérieur des obstacles qui n'est pas accessible reste donc à l'état UNKNOWN et ne doit pas être reconnu comme une cible potentielle. Cependant le problème qui s'est rapidement posé est que les cibles ainsi désignées bien que pertinentes sont trop proches des obstacles et reste donc le plus souvent inaccessible étant donne l'encombrement du robot. Nous avons donc choisi de faire une deuxième sélection (déterminée de façon empirique) à partir de la première pour délocaliser la cible trouvée plus loin des obstacles. Nous avons par ailleurs défini deux « moyens » de trouver la cible: soit en partant de la position courante du robot et en balayant le contour d'un carré de coté croissant jusqu'à trouver une cible répondant aux critères; soit en profitant de la construction de la grille en distance par l'algorithme de Dijkstra pour repérer la cible la plus proche (cf paragraphe suivant).

    Ensuite un travail de planification à proprement parler pour amener le robot depuis sa position courante jusqu'à la cible trouvée. Pour cela nous avons utilisé l'algorithme de Dijkstra (voir Figure 2) qui permet de trouver le chemin le plus court reliant deux noeuds d'un graphe (ici le graphe étant une grille de pixels).


Nous avons pris comme poids w(u,v) mesurant la distance locale d'un pixel à son voisin le masque montré Figure 3.


 

L'inconvénient de cet algorithme est de produire des trajectoires qui longent les obstacles ce qui se révèle potentiellement dangereux pour le robot, et qui nécessite de prendre des précautions en définissant par exemple une zone interdite au robot au voisinage des obstacles (le problème demeurant de caractériser cette zone). Nous avons cherché par la suite à contourner ce problème en pondérant le poids w(u,v) par une transformée en distance (voir par exemple http://arthur.u-strasbg.fr/~ronse/TIDOC/GD/tfd.html pour l'algorithme) de la grille d'occupation ce qui permet de pénaliser les cases à proximité des obstacles lors de la recherche de chemin dans Dijkstra (cf. améliorations possibles).

Enfin, il faut que le robot se déplace en fonction de la trajectoire déterminée. Notre algorithme retient dans un vecteur la trajectoire de Dijkstra pixel par pixel ce qui ne permet pas de déplacement rapide du robot en utilisant les primitives de déplacement fournies par player/stage (c'est à dire des GoTo(x, y, theta)). Nous faisons donc une simplification du vecteur de trajectoire afin d'éliminer tous les points qui ne sont pas utiles.

Le programme peut alors planifier l'exploration entière de l'environnement.



PROGRAMME ET RESULTATS:

La structure simplifiée de programme que nous avons retenue en fonction des objectifs que nous nous étions fixés et des fonctionnalités offertes par QT est montrée Figure 4.


 

Les captures d'écran suivantes illustrent le programme en fonctionnement:










AMELIORATIONS POSSIBLES:

Parmi les améliorations possibles, ont peut citer toutes celles qui peuvent aider le robot à éviter de se retrouver trop prêt d'un obstacle:

Délimitation précise d'une zone dangereuse pour le robot qui tient compte du fait qu'une cible initialement désignée dans une zone EMPTY se retrouve après avoir été atteinte dans cette zone dangereuse ce qui emprisonne le robot...

Utilisation d'une pondération par un algorithme de transformée en distance pour éviter que les trajectoires frôles les zones à risques mais se concentrent davantage au centre des espaces. Une version bêta de notre programme propose cette amélioration (voir Figure 5 et suivantes).

Apprentissage par renforcement pour apprendre à choisir des cibles non dangereuses.

D'autres améliorations peuvent concerner par exemple la façon qu'à le robot de se déplacer (suppression des Goto), la prise en compte améliorée des obstacles mobiles (le système de seuil créant un effet d'hystérésis), la prise en compte d'une localisation imparfaite (imperfection odométrique) par des filtrages (Kalman ou particulaire), etc.





Le rectangle gris a gauche est lié à un problème de rafraîchissement lors du calcul de Djkstra.