La perception des robots améliorée grâce à l'algorithme GNC - MATLAB & Simulink

Naviguer dans de nouveaux espaces grâce aux robots

Un nouvel algorithme renforce la robustesse de la perception des robots


Lorsque Vasileios Tzoumas, chercheur scientifique au Massachusetts Institute of Technology (MIT), visite une nouvelle ville, il aime l’explorer en allant courir. Et parfois, il se perd. Il y a quelques années, lors d'un long jogging alors qu’il était à Osaka pour une conférence, l'inévitable s'est produit. Tzoumas a alors repéré un 7-Eleven par lequel il se souvenait être passé peu de temps après avoir quitté son hôtel. Cette reconnaissance lui a permis de « boucler la boucle » mentalement, de relier l’extrémité libre de sa trajectoire à un endroit qu’il connaissait et dont il était sûr, solidifiant ainsi sa carte mentale et lui permettant de retourner à l’hôtel.

L’algorithme de non-convexité graduée (GNC) pourrait aider les machines à traverser la terre, l’eau, le ciel et l’espace, et à revenir raconter leur histoire.

La fermeture de la boucle est en fait un terme technique pour quelque chose que les robots doivent fréquemment faire lorsqu'ils naviguent dans de nouveaux environnements. Cela fait partie d'un processus appelé localisation et cartographie simultanées (SLAM). Le SLAM n’est pas nouveau. Il est utilisé pour les aspirateurs robotisés, les voitures autonomes, les drones aériens de recherche et de sauvetage ainsi que pour les robots dans les usines, les entrepôts et les mines. Alors que les appareils et véhicules autonomes naviguent dans de nouveaux espaces, allant du salon jusqu’au ciel, ils construisent une carte au fur et à mesure de leur déplacement. Ils doivent également déterminer où ils se trouvent sur la carte à l’aide de capteurs tels que des caméras, un GPS et un lidar.

Le SLAM ayant de de plus en plus d’applications, il est plus important que jamais de garantir que les algorithmes SLAM produisent des résultats corrects dans des conditions réelles difficiles. Les algorithmes SLAM fonctionnent souvent bien avec des capteurs parfaits ou dans des conditions de laboratoire contrôlées, mais ils se perdent facilement lorsqu'ils sont exploités avec des capteurs imparfaits dans le monde réel. Sans surprise, les clients industriels se demandent souvent s’ils peuvent faire confiance à ces algorithmes.

Des chercheurs du MIT ont développé plusieurs algorithmes SLAM robustes, ainsi que des méthodes pour prouver mathématiquement à quel point nous pouvons leur faire confiance. Le laboratoire de Luca Carlone, Leonardo Career Development assistant professor au MIT, a publié un article à propos de leur algorithme de non-convexité graduée (GNC), qui réduit les erreurs aléatoires et les incertitudes dans les résultats SLAM. Plus important encore, l’algorithme produit des résultats corrects là où les méthodes existantes « se perdent ». L'article, rédigé par Carlone, Tzoumas et les étudiants de Carlone, Heng Yang et Pasquale Antonante, a reçu le prix du meilleur article sur la vision robotique lors de la Conférence internationale sur la robotique et l'automatisation (ICRA). Cet algorithme GNC aidera les machines à traverser la terre, l’eau, le ciel et l’espace, et à revenir raconter leur histoire.

Tout est aligné

La perception des robots repose sur des capteurs qui fournissent souvent des entrées bruitées ou trompeuses. L'algorithme GNC du MIT permet au robot de décider à quels points de données faire confiance et lesquels rejeter. Une application de l'algorithme GNC est appelée alignement de formes. Un robot estime l’emplacement et l’orientation 3D d’une voiture à l’aide d’images de caméra 2D. Le robot reçoit une image de caméra avec de nombreux points étiquetés par un algorithme de détection de caractéristiques : phares, roues, rétroviseurs. Il dispose également d'un modèle 3D d'une voiture dans sa mémoire. L’objectif est de mettre à l’échelle, de faire pivoter et de placer le modèle 3D afin que ses caractéristiques s’alignent avec celles de l’image. « C'est facile si l'algorithme de détection de caractéristiques a parfaitement fait son travail, mais c'est rarement le cas », explique Carlone. Dans les applications réelles, le robot est confronté à de nombreuses valeurs aberrantes (des caractéristiques mal étiquetées) qui peuvent représenter plus de 90 % de toutes les observations. C'est là qu'intervient l'algorithme GNC et qu’il surpasse tous les concurrents.

Les robots résolvent ce problème à l’aide d’une fonction mathématique qui prend en compte la distance entre chaque paire de caractéristiques, par exemple, le phare droit sur l’image et le phare droit sur le modèle. Ils tentent « d’optimiser » cette fonction, c’est-à-dire d’orienter le modèle de manière à minimiser toutes ces distances. Plus il y a de caractéristiques, plus le problème est difficile.

Une façon de résoudre le problème serait d’essayer toutes les solutions possibles à la fonction et de voir laquelle fonctionne le mieux, mais il y en a trop à essayer. Une méthode plus courante, expliquent Yang et Antonante, « consiste à essayer une solution et à continuer à la modifier (en alignant, par exemple, les phares du modèle avec ceux de l'image 2D) jusqu'à ce que vous ne puissiez plus l’améliorer ». Étant donné les données bruitées, ce ne sera pas parfait (peut-être que les phares s'alignent mais pas les roues) ; vous pouvez donc recommencer avec une autre solution et affiner celle-ci autant que possible, en répétant le processus plusieurs fois pour trouver le meilleur résultat. Cependant, les chances de trouver la meilleure solution possible sont minces.

Dans les applications réelles, le robot est confronté à de nombreuses valeurs aberrantes, qui peuvent représenter plus de 90 % de toutes les observations. C'est là qu'intervient l'algorithme GNC et qu’il surpasse tous les concurrents.

Maillage et nuage de points avec correspondances (70% de contours)
Alignement réussi par GNC-TLS
Alignement incorrect par les algorithmes SLAM courants

L'algorithme GNC trouve l'alignement optimal malgré des mesures bruitées avec jusqu'à 70 à 90 % de valeurs aberrantes. Crédit : MIT.

L’idée derrière GNC est de d’abord simplifier le problème. Ils réduisent la fonction qu'ils tentent d'optimiser (celle qui décrit les différences entre le modèle 3D et l'image 2D) à une fonction ayant une seule meilleure solution. Maintenant, lorsqu'ils choisissent une solution et la poussent, ils finiront par trouver la meilleure solution. Ils réintroduisent ensuite un peu de complexité de la fonction originale et affinent la solution qu'ils viennent de trouver. Ils continuent ainsi jusqu’à ce qu’ils aient la fonction originale et sa solution optimale. Les phares sont bien alignés, tout comme les roues et les pare-chocs.

Tourner en rond

L'article applique l'algorithme GNC à l’alignement de formes et au SLAM, entre autres problèmes. Dans le cas du SLAM, le robot utilise des données de capteur pour déterminer sa trajectoire passée et construire une carte. Par exemple, un robot se déplaçant sur un campus universitaire recueille des données d'odométrie évaluant la distance et la direction de son déplacement entre 8h00 et 8h15, entre 8h15 et 8h30, et ainsi de suite. Il recueille aussi des données lidar et de caméra à 8h00, 8h15, et ainsi de suite. Occasionnellement, il fera des boucles complètes, et verra ainsi la même chose à deux moments différents, comme Tzoumas lorsqu’il a couru et est passé devant le 7-Eleven.

Les chercheurs ont découvert que l’algorithme GNC était plus précis que les techniques de pointe et pouvait gérer un pourcentage plus élevé de valeurs aberrantes.

Tout comme dans l’alignement de formes, il y a un problème d’optimisation à résoudre. Yang, qui est le premier auteur de l’article, explique : « Pour SLAM, au lieu d'aligner les entités pour qu'elles correspondent à un modèle 3D, le système courbe la trajectoire qu'il pense avoir parcourue afin d'aligner les objets sur la carte. » Tout d’abord, le système s’efforce de minimiser les différences entre les trajets perçus par différents capteurs, puisque chaque capteur est susceptible d’avoir des erreurs de mesure. Par exemple, si l'odomètre du robot indique qu'il a parcouru 100 mètres entre 8h00 et 8h15, la trajectoire mise à jour en fonction des mesures du lidar et de la caméra doit refléter cette distance, ou quelque chose de proche. Le système minimise également les distances entre les emplacements qui semblent être le même endroit. Si le robot a vu le même 7-Eleven à 8h00 et 10h00, l’algorithme tentera de courber la trajectoire rappelée – en ajustant chaque segment – de sorte que ses positions rappelées à 8h00 et 10h00 s’alignent, fermant ainsi la boucle.

Un robot cartographie l'intérieur d'un bâtiment. GNC organise progressivement les données désordonnées. En relativement peu d’étapes, l’algorithme parvient à une carte précise de l’intérieur d’un bâtiment. Crédit : MIT.

Pendant ce temps, l'algorithme identifie et élimine les valeurs aberrantes (les mauvais points de données, là où il pensait revenir sur ses pas, mais ce n'était pas le cas), tout comme les entités mal étiquetées dans l'alignement de formes. Vous ne voulez pas fermer une boucle à tort. Tzoumas se souvient d'un moment, alors qu'il courait dans les bois du Maine, où il est passé devant un amas de troncs d'arbres au sol, qui lui semblaient familiers. Il pensait avoir bouclé la boucle et, profitant de ce prétendu point de repère, il a pris un virage. Ce n'est qu'après ne plus avoir rien vu de familier pendant 20 minutes qu'il a soupçonné son erreur et a fait demi-tour.

Une trajectoire rappelée avant optimisation pourrait ressembler à une boule de ficelle emmêlée. Une fois démêlée, elle ressemble à un ensemble de lignes à angle droit reflétant la forme des sentiers et des couloirs du campus que le robot a parcouru. Le terme technique pour ce processus SLAM est Optimisation du graphe de pose.

Dans l’article, les chercheurs ont comparé leur algorithme GNC avec d’autres algorithmes sur plusieurs applications, notamment l’alignement de formes et l’optimisation du graphe de pose. Ils ont découvert que leur méthode était plus précise que les techniques de pointe et pouvait gérer un pourcentage plus élevé de valeurs aberrantes. Pour SLAM, cela a fonctionné même si trois fermetures de boucle sur quatre étaient erronées, ce qui représente beaucoup plus de valeurs aberrantes que ce que l'on rencontrerait dans une application réelle. De plus, leur méthode est souvent plus efficace que d’autres algorithmes, nécessitant moins d’étapes de calcul. Tzoumas explique : « L’une des difficultés était de trouver un algorithme polyvalent qui fonctionne bien dans de nombreuses applications. » Yang explique qu'ils l'ont essayé sur plus de 10 personnes. Au final, dit Tzoumas, ils ont trouvé « le juste milieu ».

L'algorithme GNC reconstruit correctement une carte de l'intérieur du Grand Dôme du MIT.

MATLAB a généré des cartes créées à partir de données dérivées d'un robot tondant une pelouse. Gauche : Carte originale de la pelouse. Milieu : Carte optimisée avec des algorithmes SLAM courants, qui incluent des données mal étiquetées provenant de fermetures de boucles aberrantes inconnues. Droite : Carte optimisée avec l'algorithme GNC.

Passer de la recherche à la production est une étape importante pour que les résultats de la recherche fassent une différence à grande échelle, déclare Roberto G. Valenti, chercheur en robotique chez MathWorks. MathWorks a travaillé avec le laboratoire de Carlone pour intégrer les algorithmes GNC dans MATLAB dans le cadre de Navigation Toolbox™, outil que les entreprises utilisent pour implémenter SLAM sur des systèmes autonomes commerciaux et industriels.

Se sortir de situation délicates

Le laboratoire de Carlone travaille sur des moyens d’étendre les capacités de leur algorithme GNC. Par exemple, Yang a pour but de concevoir des algorithmes de perception dont l’exactitude peut être certifiée. Et Antonante trouve des moyens de gérer les incohérences entre différents algorithmes : Si le module SLAM d’un véhicule autonome indique que la route va tout droit, mais que le module de détection de voie indique qu’elle tourne à droite, vous avez un problème.

L'algorithme GNC est la nouvelle référence permettant aux robots de détecter leurs propres erreurs.

Tzoumas étudie comment développer non seulement l'interaction entre plusieurs algorithmes dans un robot, mais également la collaboration entre plusieurs robots. Dans ses travaux antérieurs, il a programmé des drones volants pour suivre des cibles, comme des criminels essayant de s'échapper à pied ou en voiture. À l’avenir, plusieurs dispositifs pourraient peut-être exécuter l’algorithme GNC collectivement. Chacun apporterait des informations partielles à ses voisins et, ensemble, ils construiraient une carte mondiale – des emplacements sur Terre ou ailleurs. Cette année, il rejoint le département d'ingénierie aérospatiale de l'Université du Michigan pour travailler sur l'autonomie fiable pour la planification et l'auto-navigation multirobots, même dans des environnements difficiles, tels que les champs de bataille et d'autres planètes.

« Ne pas savoir comment l’IA et les algorithmes de perception se comporteront est un obstacle majeur à leur utilisation », explique Antonante. Il note que les guides robotisés des musées ne seront pas dignes de confiance s'il y a un risque qu'ils entrent en collision avec les visiteurs ou avec la Joconde : « Vous voulez que votre système ait une compréhension approfondie de son environnement et de lui-même, afin qu’il puisse détecter ses propres erreurs. » L’algorithme GNC est la nouvelle référence qui permet aux robots de détecter leurs propres erreurs et, plus important encore, comme le dit Tzoumas, « il vous aide à vous sortir d’affaire ».

Autres articles sur la robotique

ETH Zurich

Une équipe de neuf étudiants de premier cycle développe un robot sauteur innovant pour son projet final

Robot Weston

Un course folle de 10 jours pour développer des robots qui luttent contre la COVID-19

Corindus

Les nouvelles frontières de la télémédecine

Université Drexel

Essayez ceci pour voir : Designer Clothing donne aux robots le sens du toucher


Lire d'autres articles

Navigation dans l'interface

Académie / IA

L’IA dévoile les secrets d’artefacts anciens

Utilisation du Deep Learning et du traitement d'images pour restaurer et préserver les œuvres d'art

Navigation dans l'interface

Technologies vertes/Systèmes de contrôle

Éliminer des millions de tonnes d’émissions de CO2 dans les ports maritimes chaque année

Électrifier les véhicules utilitaires avec des piles à combustible à hydrogène

Navigation dans l'interface

STEM / Communauté académique

Construire un avenir dans les STEM

Un lycéen découvre que le codage ne se limite pas à un écran d’ordinateur