Intelligence artificielle

Comment un robot planifie-t-il un chemin dans son environnement à l'aide de RRT?

Comment un robot planifie-t-il un chemin dans son environnement à l'aide de RRT?


Récemment, je travaille sur mon propre robot mobile, Citrouille, avec un étudiant de Master dans mon laboratoire de recherche. Depuis que nous essayons de remplacer certains des packages par défaut que mon robot utilise à partir de la bibliothèque ROS, nous avons appris les différents algorithmes utilisés dans une pile de robots typique. Comme quelqu'un qui travaille sur la planification et l'apprentissage par renforcement mais ne pas robotique, il y a eu une forte courbe d'apprentissage pour moi. Un robot doit savoir comment se localiser dans son environnement - ou savoir où il se trouve, construire une carte de son environnement à la volée s'il n'en a pas déjà une, éviter les obstacles qui pourraient surgir au hasard, contrôler ses moteurs pour changer sa vitesse ou sa direction, proposer un plan qui résout une tâche, etc.

Mon robot Citrouille

Comme vous vous en doutez, un vraiment une partie importante d'un robot est sa capacité à planifier un chemin d'un endroit à un autre étant donné une carte de son environnement. Pourquoi devrait-il faire cela? Peut-être doit-il traverser une pièce pour livrer un colis ou peut-être escorter une personne dans un immeuble. Dans tous les cas, chaque fois qu'un robot doit aller d'un emplacement de départ à un emplacement d'objectif pour terminer une tâche, il doit trouver un plan de trajet pour savoir comment se déplacer dans son environnement. Dans les articles sur la robotique, vous verrez souvent une carte comme celle ci-dessous avec un emplacement de départ et un emplacement d'objectif. Ceci est un joli visuel du problème classique de la robotique mobile que nous appelons habituellement Planification de trajectoire. En d'autres termes, comment un robot peut-il trouver un chemin qui le mène de l'emplacement de départ à l'emplacement de l'objectif?

Source: Un article sur la robotique par Andrew Howard, Gaurav Sukhatme et Lynne Parker

Avertissement: Dans le passé, j'ai écrit quelques articles avec des diagrammes colorés et de longues explications. Certes, parce que des articles comme celui-ci impliquent une tonne de travail, j'ai fini par ne rien poster. À l'avenir, je prévois d'écrire des messages sans fioritures qui sont un peu plus rudes et décontractés. Pourquoi? Eh bien, non seulement il est plus facile pour moi d'écrire des messages qui renforcent ma propre compréhension d'un concept, mais je suis également sûr qu'ils peuvent être tout aussi informatifs sans toutes les cloches et les sifflets que mes autres messages avaient. Et maintenant, revenons à notre programmation régulière…

Cependant, comme toujours, il y a quelques subtilités que nous devons garder à l'esprit:

  1. Le plan de trajet devrait en fait fonctionner sur un robot. Si le plan de trajectoire fait tourner le robot à des angles vifs mais que le robot ne peut pas se déplacer à des angles vifs (comme une voiture), ce plan de trajectoire ne devrait pas être autorisé.
  2. Le plan du trajet doit être aussi proche que possible de l'optimal. Bien qu'il soit agréable de trouver un plan de trajet permettant de faire passer le robot d'un emplacement de départ à un emplacement d'objectif, cela ne suffit malheureusement pas. Nous aimerions quelque chose d'un peu efficace. Non seulement cela aidera le robot à terminer sa tâche le plus rapidement possible, mais il conservera également sa précieuse autonomie.
  3. Le plan du chemin doit éviter de heurter les murs. Cela va évidemment de soi. Les robots peuvent être assez chers, et planter n'est jamais une bonne chose. Mon petit robot à moi seul m'a coûté bien plus de mille dollars.

L'un des algorithmes les plus populaires pour élaborer un plan de cheminement qui tente de satisfaire ces conditions est appelé Arbres aléatoires à exploration rapide (RRT). Puisqu'une image vaut mille mots, consultez le diagramme ci-dessous. Supposons que le robot doive partir d'un emplacement de départ (le rouge point) à un emplacement de but (le vert point) dans une carte simple sans aucun obstacle. Fondamentalement, nous allons commencer avec un arbre qui a un nœud racine représentant la position de départ du robot. Après cela, nous allons construire l'arbre progressivement. Comment? Nous allons prendre un tas d'échantillons aléatoires de la carte, créer un nouveau nœud pour chaque échantillon aléatoire et insérer chaque nouveau nœud dans l'arborescence d'une manière ou d'une autre. Une fois que l’arbre a un nœud suffisamment proche de la position de but du robot, nous avons terminé.

Source: l'article original de RRT par Steven LaValle

Comme je sais que cela semble assez vague, ajoutons quelques détails à cette idée approximative. Pour commencer, examinons chaque paramètre que nous enverrons à RRT.

  • Carte: la carte de l'environnement partitionné en un région d'obstacles Et un région sans obstacle. Cela ressemblera à la carte que j'ai publiée ci-dessus, où la région d'obstacles est tout ce qui est gris et la région sans obstacles est tout ce qui est blanc.
  • La position de départ: la position de départ du robot dans son environnement. Ceci est juste le point rouge sur cette carte.
  • Région d'objectif: la région cible du robot dans son environnement. Et ce n'est que le point vert sur cette carte.
  • Nombre d'itérations: le nombre d'itérations effectuées par RRT.

Passons en revue chaque étape de RRT. Tout d'abord, nous allons initialiser un arbre vide. Ensuite, nous allons insérer le nœud racine qui représente la position de départ dans l'arborescence. À ce stade, nous aurons juste un arbre avec un seul nœud qui représente la position de départ. Enfin, nous répéterons ces étapes jusqu'à ce que nous atteignions le nombre d'itérations ou atteignions l'objectif, selon la première éventualité.

  1. Échantillon une position aléatoire de la région sans obstacle de la carte.
  2. Créer un nœud associé à la position aléatoire.
  3. Trouver un nœud déjà dans l’arbre le plus proche de la position aléatoire.
  4. Calculer un chemin de la position aléatoire à la position du nœud qui fonctionnerait réellement possible sur le robot.
  5. Continuer à l'itération suivante si le chemin entre en collision avec quelque chose.
  6. Insérer le nœud associé à la position aléatoire dans l'arborescence avec le nœud (le nœud le plus proche) comme nœud parent.
  7. Revenir l'arbre une fois que la position aléatoire est à une certaine distance de la position du but.

Attention, si l'arbre ne se rapproche pas de la région cible au moment où nous atteignons le nombre d'itérations, nous reviendrons simplement sur l'arbre que nous avons construit jusqu'à présent.

Source: mjkaufer via Reddit

Mais comment obtenir le chemin de l'emplacement de départ à l'emplacement de l'objectif une fois que nous avons construit l'arborescence? Tout ce que nous avons à faire est de commencer au nœud qui représente l'emplacement de l'objectif et de remonter dans l'arborescence jusqu'à ce que nous arrivions au nœud qui représente l'emplacement de départ. Cela nous donnera le chemin qui amène le robot de l'emplacement de départ à l'emplacement de l'objectif. Facile.

Et est-il possible de réutiliser l'arbre pour de nouveaux emplacements d'objectifs sur la même carte? Bien sûr! S'il y a déjà un nœud dans l'arbre près du nouvel emplacement de l'objectif, nous sommes prêts à partir. Cependant, s'il n'y a encore rien à proximité de ce nouvel emplacement d'objectif, nous pouvons simplement continuer à échantillonner jusqu'à ce que nous atteignions un nœud qui se trouve à proximité. Tant que l'environnement ne change pas, vous pouvez simplement continuer à construire sur la même arborescence pour tout nouvel emplacement d'objectif.

Source: Robotique en temps réel

Sans plus tarder, voici une version approximative de l'algorithme pour RRT!

une fonction RRT (carte, la position de départ, goalRegion, numIterations):
arbre = initializeEmptyTree ()

insertRootNode (arbre, la position de départ)

pour je = 1 à numIterations:
randomPosition = échantillon (carte)
randomNode = createNode (arbre, randomPosition)
le plus proche = findNearestNode (arbre, randomPosition)
chemin = CalculatePath (le plus proche, randomNode) si (hasCollision (carte, chemin)):
continuerinsertNewNode (arbre, node, randomNode)
si (randomPosition est à l'intérieur goalRegion):
revenir arbre
revenir arbre

Il y a encore une chose importante à couvrir! Plus tôt, j'ai mentionné que nous recherchons un chemin qui fonctionne sur un robot réel, est optimal et évite les obstacles. Bien que ce chemin fonctionne sur un robot réel et évite les obstacles, est-il optimal? Il s'avère que RRT n'est malheureusement pas garanti pour produire des chemins optimaux. Dans un prochain article de blog, je parlerai de RRT *, une meilleure version de RRT, qui génère un chemin optimal finalement. Mais c'est pour la prochaine fois.

Afficher plus

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Articles similaires

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer