RoboCup 2015 - Pyro Team : Différence entre versions

De Wiki de Projets IMA
(Jour 1 :)
(Avancement du Projet)
Ligne 95 : Ligne 95 :
 
*L'algorithme A-Star (Basé sur Dijkstra, cet algo s'oriente directement vers le point d'arrivée en minimisant la distance avec celui-ci)<br>
 
*L'algorithme A-Star (Basé sur Dijkstra, cet algo s'oriente directement vers le point d'arrivée en minimisant la distance avec celui-ci)<br>
 
*L'algorithme D-Star Lite (Amélioration du A-Star avec bufferisation des précédents calculs pour éviter les calculs inutiles en cas d'arrivée d'un obstacle mobile sur la trajectoire)<br>
 
*L'algorithme D-Star Lite (Amélioration du A-Star avec bufferisation des précédents calculs pour éviter les calculs inutiles en cas d'arrivée d'un obstacle mobile sur la trajectoire)<br>
 +
 +
Nous avons visualisé les différents algorithmes sur [http://qiao.github.io/PathFinding.js/visual/ PathFinding]
  
 
Fonctionnement de l'algorithme A-Star :<br>
 
Fonctionnement de l'algorithme A-Star :<br>

Version du 14 février 2015 à 12:44


Cahier des charges

LogoPyro icone.png

Présentation générale du projet

Avec plusieurs IMAs, nous avons créer une équipe pour participer à la Logistic League de la RoboCup. Lors de la compétition de l'Open German, version européenne de la RoboCup, il faudra mettre en place un système autonome de production à l'aide de Robotinos (robots mobiles de Festo ayant un système d'exploitation Linux) afin de réaliser des produits en fonction des demandes de l'arbitre du jeu : la Referee Box. Nous traiterons dans ce projet de l'aspect navigation des robots, composé d'une partie localisation et d'une partie déplacement.

Contexte

La compétition de l'Open German se déroule en quatre phases spécifiques : phase de début-de-jeu, phase d'exploration, phase de production, phase de fin-de-jeu. La navigation sera utilisée dans la phase d'exploration afin de réaliser une carte de la zone de jeu permettant de définir des zones de passage entre les machines. Dans la phase de production, la navigation permettra de se déplacer à partir de la carte créée au préalable (avec les obstacles fixes) et des robots (obstacles mobiles) se déplaçant en même temps.

Objectif du projet

Fournir aux Robotinos un système capable de se localiser et de parcourir des trajectoires calculées à partir de coordonnées envoyées par le Manager.

Description du projet

ProjetS8.png
  • Localiser correctement le robot (à 5 cm près)
  • Localiser les éléments fixes :
    • Murs
    • Machines
  • Générer une trajectoire selon :
    • les demandes du "Manager"
    • la détection d'obstacles dynamiques (robots)
  • Assurer le suivi de la trajectoire

Choix techniques : matériel et logiciel

  • Utilisation de 3 Robotinos équipés chacun de :
    • 1 détecteur laser pouvant réaliser des mesures à 240°
    • 1 gyroscope
    • 9 capteurs SHARP (télémètres infrarouges)
    • 3 codeurs incrémentaux présents en sortie de chaque moteur du Robotino
  • Utilisation de ROS Hydro
  • Utilisation de différents langages : C++ ou Python
  • Utilisation de Linux Ubuntu 12.04

Etapes du projet

  • Conception du schéma global des différentes parties :
    • Localisation avec le SLAM
    • Création de la carte avec le SLAM
    • Génération de trajectoire avec A-Star
    • Execution de trajectoire avec le noeud ROS pour Robotino robotino_local_move
  • Codage des différents noeuds ROS
  • Tests de précision et de robustesse sur robot
  • Validation du modèle
  • Améliorations possibles :
    • Fusionner les maps des 3 robots
    • D-Star Lite au lieu de A-Star
    • Filtrage des données laser

Vocabulaire

Nos comptes rendus peuvent contenir des expressions que nous employons régulièrement mais qui ne sont parfois pas évidentes. Nous proposons alors cette partie vocabulaire afin d'aider le lecteur à comprendre ces expressions.

  • Noeud : C'est un programme qui tourne de manière indépendante et qui réalise une tâche spécifique.
  • Type : C'est un format spécifique de message. Il définit les valeurs que peut prendre une donnée, ainsi que les opérateurs qui peuvent lui être appliqués.
  • Odométrie : L’odométrie est une technique permettant d'estimer la position d'un véhicule en mouvement. Cette mesure de bas niveau est présente sur quasiment tous les robots mobiles, grâce à des capteurs embarqués permettant de mesurer le déplacement du robot (de ses roues).

Avancement du Projet

Semaine 1

  • Participation aux Finales Nationales des Olympiades des Métiers en robotique mobile (4ème)

Semaine 2

Jour 1 :

Etablissement du cahier des charges :

  • Prise de connaissance des contraintes d'environnement
  • Dialogue avec l'équipe responsable de la partie Manager

Familiarisation avec l'environnement logiciel ROS Recherches de solutions pour la localisation (SLAM) et la génération de trajectoire (algorithme A-star)

Jour 2 :

Génération de trajectoire :

Nous avons fait nos recherches en nous orientant sur le déplacement du Robotino afin de trouver un algorithme de trajectoire, capable de trouver le chemin le plus court, puisqu'un des buts de la compétition étant la rapidité.
Plusieurs algorithmes sont donc ressortis :

  • L'algorithme Dijkstra (On part du point de départ et on cherche le chemin le plus court vers le point d'arrivée en cherchant dans TOUTES les directions)
  • L'algorithme A-Star (Basé sur Dijkstra, cet algo s'oriente directement vers le point d'arrivée en minimisant la distance avec celui-ci)
  • L'algorithme D-Star Lite (Amélioration du A-Star avec bufferisation des précédents calculs pour éviter les calculs inutiles en cas d'arrivée d'un obstacle mobile sur la trajectoire)

Nous avons visualisé les différents algorithmes sur PathFinding

Fonctionnement de l'algorithme A-Star :

  • Tout d'abord, on calcule la distance qui sépare le robot du point d'arrivée, et on définit les points interdits par les obstacles. (la zone bleue correspond

à l'obstacle et la zone verte est une zone ou le robot touche l'obstacle. Ces deux zones constituent la zone interdite).

Projet S8 A STAR 1.PNG
Projet S8 A STAR 2.PNG
  • Ensuite le Robot trouve un premier noeud sur la grille qu'on lui a attribué. Si le noeud n'est pas dans une zone interdite, il sauvegarde ce noeud.
Projet S8 A STAR 3.PNG
Projet S8 A STAR 4.PNG
  • Il répète l'opération jusqu'à trouver le chemin qui le mènera à l'arrivée
Projet S8 A STAR 5.PNG
  • Attention : c'est seulement lorsqu'il aura trouvé le chemin complet que le robot va se déplacer !

Localisation :

Pour la localisation nous allons utilisé un algorithme de Localisation et Cartographie Simultanée (SLAM en anglais):

SLAM.png

Explicitation des différentes parties :

  • Odometry change  : changement de position
  • Odometry update  : mise à jour de l'odométrie
  • Re-observation  : vérification des changements à partir de toutes les données disponibles
  • New observations  : mise à jours de la matrice d'état
  • Laser scan  : scan laser brut
  • Landmark Extraction : extraction des objets caractéristiques
  • Data Association  : association entre objets scannés et objets en mémoire

Ce schéma sera explicité à la séance prochaine.

Semaine 3

Jour 1 :

Nous avons découper le travail de génération de map et de la correction de position de la manière suivante :

SchémaProjetS8-1.png

( Nous recommandons au lecteur de se référer à la partie vocabulaire pour comprendre les termes techniques )

Chaque case du diagramme précédent correspond à un noeud ROS.

Décrivons précisément le rôle de chaque noeud :

  • Laser récupère les données brutes du laser.
  • Filtrage permet, comme son nom l'indique, d'enlever les éventuels bruits qui affectent les données du laser.
  • Reconnaissance des droites traite les données laser filtrées pour détecter les droites présentes (Transformée de Hough ou Ransac)
  • Reconnaissance des formes extrapole les objets (machines) à partir des droites.
  • Corrélation emplacements machines lie la position des machines détectées au laser et les positions envoyées par RefBoxCom pour éviter les incohérences.
  • Odométrie récupère la position du robot par rapport au point de départ. Il renvoie une position corrigée grâce au gyroscope(Pose) et une position non corrigée par le gyroscope (Twist)
  • Traitement de position corrige l'erreur sur le Twist avec les données du gyroscope (par dérivation).
  • Fusion de Kalman est un algorithme qui va coupler les données de position et les données du laser afin de fournir un modèle et une position précise. C'est le noeud central du SLAM.
  • Stockage machines + robot transforme les positions des machines et du robot en grille. Il sera couplé aux détections d'obstacles.
  • Grid Map renvoit une map utilisée ensuite pour les déplacements et les calculs de trajectoires (A_Star)
  • RefBoxCom stocke et renvoie la position des machines.
  • Position robot renvoie la position exacte du robot sur la grille.
  • Manager Noeud qui envoie la position à atteindre.
  • Pathfinder recherche le chemin demandé par le Manager sur une grille
  • Parcoureur exécute le chemin trouvé en fournissant les vitesses au noeud Déplacement.
  • Déplacement (noeud robotino_local_move_server), qui donne les commandes aux moteurs à partir de la vitesse linéaire et angulaire envoyée par le Parcoureur.

Jour 2 :

Nous avons cherchés toutes les documentations techniques nécessaires pour la programmation de chaque noeud : Wiki_ROS et API_Robotino, nous permettant de mettre à jour le schéma global (semaine 2 jour 2), notamment au niveau des types.

Nous nous sommes ensuite concentrés sur le noeud GridMap qui contient Map.cpp :

Dans le code de l'an dernier, ce noeud générait une grille en dur. Cependant, cette solution n'est pas possible cette année car nous ne connaissons pas toutes les informations sur la piste (on connaît à peu près la position mais pas l'orientation). Il va donc falloir générer une grille en fonction du noeud précédent qui nous renverra un type OccupancyGrid.

Etant donné que ce noeud tournera en permanence, si des informations changent pendant que le robot est sur la piste (détection des nouvelles machines par exemple), le noeud Map.cpp modifiera la grille en temps réel.

La grille est décomposée en case pour le A-Star :

Si c'est une case interdite (obstacle) ont associe a la case la valeur 1, si elle est autorisée, on associe la valeur 0. On illustre le principe précédent par un exemple :

Projet S8 Creation Map.PNG

Cependant, le noeud "Grid Map" va nous délivrer un vecteur et non une matrice par le biais de OccupancyGrid.Data.Dans notre exemple précédent, on récupère le vecteur suivant :

Projet S8 Creation Map 2.PNG

On choisit donc de transformer ce vecteur en matrice, car l'algorithme A-Star fonctionne sur un graphe, pas un vecteur. On connait la largeur (en case) de la grille grâce au type OccupancyGrid.info.width.

Le pseudo-code pour générer la matrice à partir de ce vecteur sera le suivant :

fonction create_grid (OccupancyGrid.Data vecteur[size]) : matrice[height].[width]
{
  matrice[height].[width] ;		
     int t <- size;
         Pour (i de 0 à height)
         faire:
               {
                   Pour (j de 0 à width)
                   faire :
                           {
                              matrice[i].[j] <- vecteur[t] ;
                              t++;
                           }
               }
  return matrice;
}

Fichiers Rendus