Cartographie et gestion de trajectoire simultanée

  Informatique, robotique

Ces codes ont été faits pour permettre à un robot de cartographier un environnement inconnu, la difficulté étant de calculer une trajectoire sans connaitre tout l’environnement. Le code est adapté à un robot autonome contrôlé par arduino et communicant par Bluetooth avec un ordinateur. Le robot est muni d’un capteur monté sur un servo moteur capable de tourner à 250 degrés.

Le programme fonctionne de la manière suivante :

  1. Dans un premier temps il demande aux robots de scanner son environnement en bougeant le servo et en prenant des mesures avec le capteur.
  2. L’ordinateur transforme ces données en carte. La carte est une matrice de la taille de la pièce où chaque case de la matrice représente 1cm^2. La taille de ces cases peut changer en fonction de la précision voulue et de la puissance de calcul a notre disposition. Les données sont stockées sous forme de nombre dans la matrice (par exemple 0=inconue, 1=vide, 2=obstacle, 3=danger).
  3. Ensuite l’ordinateur choisit l’endroit où le robot doit se déplacer et calcule une trajectoire optimale jusqu’à ce point

1. Cartographie

Pour avoir une cartographie efficace, c’est primordial de connaitre la position précise de notre robot. C’est le rôle de la régulation et l’odométrie présente sur le robot, nous n’allons pas aborder cette partie du projet dans cet article. Il faut qu’il soit très important de minimiser les erreurs de position. De petites erreurs qui s’accumulent pendant toute l’exploration peuvent avoir beaucoup d’impacts sur la qualité de la carte finale.

La cartographie transforme les données envoyées par le robot (une liste de distance correspondant à chaque angle du scan) en une matrice-carte. Pour faire cette transformation, dans un premier temps il faut transformer les distances mesurées par le capteur en coordonnée absolue, ça se fait simplement avec un peu de trigonométrie.


On peut voir dans ce code qu’on ne s’intéresse pas uniquement aux coordonnées de l’obstacle, mais que l’on considère que l’obstacle est aussi 1cm au déçu, en dessous, à gauche et à droite. On fait ça pour plusieurs raisons: tout d’abord notre capteur a des erreurs de l’ordre du centimètre, mais aussi comme on fait une mesure par degré, à une distance allant jusqu’à un mètre, chaque mesure représente 1m*2pi/360=1.7cm alors que chaque case fait seulement 1cm de côté, pour ne pas avoir de trou dans notre obstacle il faut donc artificiellement « agrandir » chaque mesure.

Une fois les coordonnées déterminées, on peut les associer à la carte déjà existante et la faire évoluer. Mais il ne suffit pas de mettre les obstacles dans les bonnes cases, il faut aussi déterminer quelle zone est connue et quelle zone reste inconnue. Pour faire ça, le programme connaît la position du robot et son orientation, à partir de ce point, il va scanner chaque case dans un angle de 250 degrés, centrés sur l’axe du robot, et sur un mètre distance (portée maximale du capteur). Pour chaque case il va vérifier si elle correspond à des coordonnées d’obstacle calculé précédemment. si elle correspond, on transforme cette case en case obstacle sinon en case connue. Mais si une case est derrière un obstacle, il ne faut pas que le programme la considère comme connue, car notre capteur n’est pas capable de voir derrière un mur. pour régler ce problème, on fonctionne de la manière suivante:

  1. on crée une liste d’angle allant de 0 à 250
  2. Pour chaque angle dans la liste on teste la case correspondant à l’angle et a une distance n (en cm).
  3. Si cette case est vide, on la transforme en case connue.
  4. Si cette case est un obstacle, on la transforme en case obstacle et on retire l’angle de la liste.
  5. on incrémente n (n<porté du capteur) et on recommence à l’étape 2

Voilà un exemple d’un scan (en rouge les cases inconnues en noir les case obstacle et en blanc les cases connues)

Comme on peut le voir ici, le programme a bien détecté l’obstacle et il n’a pas vu ce qui est caché derrière, mais il y a un problème : il reste beaucoup de cases rouges (inconnue) au milieu de la zone qui devrait être scannée. C’est dû aux faits qu’on a que vérifié 250 cases par arc de cercle (une par angle), et non toutes les cases, pour régler ce problème, on peut soit vérifier manuellement chaque case sur l’arc de cercle. Mais ayant des cases carrées, c’est compliqué à retranscrire concrètement. En effet la position relative aux robots des cases ainsi que leur nombre par arc de cercle changera en fonction de son orientation et de sa position. À la place j’ai opté pour la solution suivante : étant donné qu’on sait qu’un obstacle a très peu de chance de faire 1,2,3 ou 4cm^2. On peut donc retirer toutes les cases rouges seules qui sont entourées de blanc. On peut aussi enlever les groupes de 2,3 ou 4 cases. En fonction de la précision voulue et la portée du capteur, on peut décider d’enlever de plus grands groupes de cases .

Ce changement nous donne un bien meilleur résultat, comme on peut le voir sur la deuxième image. Même si à longue portée le problème n’est pas complètement réglé. Mais étant donné que notre robot ne va pas se déplacer en un mouvement jusqu’à l’extrémité de son champ de vision. et qu’il fasse de multiples scans, ça n’impacte que peu ses capacités d’exploration

Une fois cette carte faite, on doit encore rajouter un type de case: les cases danger. Ces cases sont là pour une simple raison: dans tout notre programme on considère que notre robot est un point, mais en réalité il a un volume. Il faut donc l’empêcher d’approcher trop près des obstacles sinon il les heurterait. C’est la qu’intervienne les cases danger: se sont simplement l’ensemble des cases a moins d’une certaine distance d’un obstacle dans lequel le robot (le point le représentant) ne peut pas rentrer sinon il toucherait l’obstacle. Dans notre cas cette distance est de 20 cm, mais elle peut être adaptée en fonction de la taille du robot. Cette approche permet de grandement simplifier le programme de gestion de trajectoire, même si ça peut poser problème dans le cas de passage très étroit.

On a donc un programme capable de cartographier une zone et de transformer des données brutes d’un capteur en donnée utilisable et compréhensible. Mais ce programme a quelque défaut: tout d’abord on travaille avec une carte/matrice de taille donnée. Si cette matrice est plus grande que la zone a exploré, ça ne pose pas de problème, mais ça empêche notre robot d’explorer des zones complètement inconnues. On pourrait régler ce problème en faisant une matrice beaucoup plus grande pour limiter ces risques, mais alors on perd beaucoup de performance et de fluidité. La solution serait de faire une matrice qui s’agrandit au cours de l’exploration, mais ceci ajoute beaucoup de complexité entre autres pour gérer les coordonnées. Un autre point pouvant être amélioré est qu’au lieu de travailler avec des types de cases absolues on peut assigner un degré de certitude. Par exemple plus une case a été scanner un grand nombre de fois, mieux elle est connue. Mais c’est une approche complètement différente que nous n’aborderons pas ici.

On peut voir que le programme est capable de créer une carte utilisable à partir d’une succession de scan à différent endroit.

2. Gestion de trajectoire

Une fois qu’on est capable de faire une carte, il faut pouvoir calculer des trajectoires pour explorer dans la pièce. Pour ça, la première étape c’est de choisir un point inconnu qu’on va rejoindre. On a utilisé deux méthodes, dans un premier temps s’il y a un point inconnu directement accessible (en ligne droite) dans le champ de vision, c’est celui-là qu’on choisit. Dans la majorité des cas c’est ce qu’il va se passer. Mais s’il n’y a pas de point directement visible, il nous faut un moyen de choisir un point inconnu derrière un obstacle, mais dont on est sûr qu’il est accessible. Pour ça, on a un algorithme, qui teste les cases de proche en proche (en partant du robot), en contournant les obstacles un peu comme une vague.

on peut voir ici les case tester a differente etape de la recherche avec en rouge notre robot et en vert la zone explorer

Une fois le point inconnus choisis il faut trouver comment le rejoindre, quand il est directement en ligne de vu c’est assez simple il suffit de faire une ligne droite et ensuite de scanner la zone avec notre capteur (on peu soit rejoindre directement le point ou le faire par petit mouvement de maximum 50 cm par exemple par sécurité).

Mais quand il est pas dans notre champs de vision c’est la qu’on dois avoir un algorithme efficace: en voici certain et les raison pour lesquel on les a pas choisis:

WORK IN PROGRESS

Laisser un commentaire