Skip to main content

8 Mar, 2024

Une méthode vérifie rapidement qu’un robot évitera les collisions

Une méthode vérifie rapidement qu’un robot évitera les collisions

Les chercheurs du MIT ont développé une technique de contrôle de sécurité rapide qui peut garantir qu’un robot évitera les collisions lors de l’exécution d’une tâche.

Avant qu’un robot puisse saisir la vaisselle sur une étagère pour mettre la table, il doit s’assurer que sa pince et son bras ne s’écraseront pas sur quoi que ce soit et risquent de briser la porcelaine fine. Dans le cadre de son processus de planification de mouvement, un robot exécute généralement des algorithmes de « contrôle de sécurité » qui vérifient que sa trajectoire est sans collision.

Cependant, ces algorithmes génèrent parfois de faux positifs, affirmant qu’une trajectoire est sûre alors que le robot risque d’entrer en collision avec quelque chose. Les autres méthodes permettant d’éviter les faux positifs sont généralement trop lentes pour les robots du monde réel.

Aujourd’hui, des chercheurs du MIT ont développé une technique de contrôle de sécurité qui peut prouver avec une précision de 100 % que la trajectoire d’un robot restera sans collision (en supposant que le modèle du robot et de son environnement soit lui-même précis). Leur méthode, si précise qu’elle permet de distinguer des trajectoires qui ne diffèrent que de quelques millimètres, en apporte la preuve en quelques secondes seulement.

Mais l’utilisateur n’a pas besoin de croire les chercheurs sur parole : la preuve mathématique générée par cette technique peut être vérifiée rapidement avec des mathématiques relativement simples.

Les chercheurs y sont parvenus en utilisant une technique algorithmique spéciale, appelée programmation par somme des carrés, et l’ont adaptée pour résoudre efficacement le problème du contrôle de sécurité. L’utilisation de la programmation par somme des carrés permet à leur méthode de se généraliser à un large éventail de mouvements complexes.

Cette technique pourrait être particulièrement utile pour les robots qui doivent se déplacer rapidement pour éviter les collisions dans des espaces bondés d’objets, comme les robots de préparation des repas dans une cuisine commerciale. Il est également bien adapté aux situations dans lesquelles les collisions de robots pourraient causer des blessures, comme les robots de santé à domicile qui soignent des patients fragiles.

« Avec ce travail, nous avons montré qu’il est possible de résoudre certains problèmes complexes avec des outils conceptuellement simples. La programmation par somme des carrés est une idée algorithmique puissante, et même si elle ne résout pas tous les problèmes, si vous faites attention à la façon dont vous l’appliquez, vous pouvez résoudre des problèmes assez non triviaux », explique Alexandre Amice, spécialiste en génie électrique et informatique, étudiant diplômé en sciences (EECS) et auteur principal d’un article sur cette technique.

Peter Werner, étudiant diplômé en EECS, et Russ Tedrake, auteur principal, professeur Toyota en EECS, aéronautique et astronautique, et génie mécanique, et membre du Laboratoire d’informatique et d’intelligence artificielle (CSAIL), sont les autres auteurs de l’article. Les travaux seront présentés à la conférence internationale sur les robots et l’automatisation.

Certifier la sécurité

De nombreuses méthodes existantes permettant de vérifier si le mouvement prévu d’un robot est sans collision le font en simulant la trajectoire et en vérifiant toutes les quelques secondes si le robot heurte quelque chose. Mais ces contrôles de sécurité statiques ne permettent pas de savoir si le robot va entrer en collision avec quelque chose dans les secondes intermédiaires.

Cela ne pose peut-être pas de problème pour un robot errant dans un espace ouvert comportant peu d’obstacles, mais pour les robots effectuant des tâches complexes dans de petits espaces, quelques secondes de mouvement peuvent faire une énorme différence.

Conceptuellement, une façon de prouver qu’un robot ne se dirige pas vers une collision serait de brandir un morceau de papier qui sépare le robot de tout obstacle dans l’environnement. Mathématiquement, ce morceau de papier s’appelle un hyperplan. De nombreux algorithmes de contrôle de sécurité fonctionnent en générant cet hyperplan à un instant donné. Cependant, chaque fois que le robot se déplace, un nouvel hyperplan doit être recalculé pour effectuer le contrôle de sécurité.

Au lieu de cela, cette nouvelle technique génère une fonction hyperplan qui se déplace avec le robot, ce qui permet de prouver qu’une trajectoire entière est sans collision plutôt que de travailler sur un hyperplan à la fois.

Les chercheurs ont utilisé la programmation par somme des carrés, une boîte à outils algorithmique capable de transformer efficacement un problème statique en fonction. Cette fonction est une équation qui décrit où l’hyperplan doit se trouver à chaque point de la trajectoire prévue pour qu’il reste sans collision.

La somme des carrés peut généraliser le programme d’optimisation pour trouver une famille d’hyperplans sans collision. Souvent, la somme des carrés est considérée comme une optimisation lourde qui ne convient qu’à une utilisation hors ligne, mais les chercheurs ont montré qu’elle est extrêmement efficace et précise pour ce problème.

« La clé ici était de trouver comment appliquer la somme des carrés à notre problème particulier. Le plus grand défi a été de parvenir à la formulation initiale. Si je ne veux pas que mon robot heurte quoi que ce soit, qu’est-ce que cela signifie mathématiquement et l’ordinateur peut-il me donner une réponse ? » précise Alexandre Amice.

En fin de compte, comme son nom l’indique, la somme des carrés produit une fonction qui est la somme de plusieurs valeurs au carré. La fonction est toujours positive, puisque le carré de n’importe quel nombre est toujours une valeur positive.

Faites confiance mais vérifiez

En revérifiant que la fonction hyperplan contient des valeurs au carré, un humain peut facilement vérifier que la fonction est positive, ce qui signifie que la trajectoire est sans collision, explique Alexandre Amice.

Bien que la méthode certifie avec une précision parfaite, cela suppose que l’utilisateur dispose d’un modèle précis du robot et de l’environnement ; le certificateur mathématique est aussi bon que le modèle.

« Ce qui est vraiment intéressant avec cette approche, c’est que les preuves sont très faciles à interpréter. Vous n’avez donc pas besoin de me croire que je l’ai bien codé, car vous pouvez le vérifier vous-même », ajoute-t-il.

Ils ont testé leur technique en simulation en certifiant que les plans de mouvements complexes de robots à un et deux bras étaient sans collision. Dans sa forme la plus lente, leur méthode ne prenait que quelques centaines de millisecondes pour générer une preuve, ce qui la rendait beaucoup plus rapide que certaines techniques alternatives.

« Ce nouveau résultat suggère une nouvelle approche pour certifier qu’une trajectoire complexe d’un robot manipulateur est sans collision, exploitant élégamment les outils d’optimisation mathématique, transformés en logiciels étonnamment rapides (et accessibles au public). Bien qu’il ne fournisse pas encore une solution complète pour la planification rapide de trajectoires dans des environnements encombrés, ce résultat ouvre la porte à plusieurs directions de recherche intrigantes », déclare Dan Halperin, professeur d’informatique à l’Université de Tel Aviv, qui n’a pas participé à cette recherche.

Bien que leur approche soit suffisamment rapide pour être utilisée comme contrôle final de sécurité dans certaines situations réelles, elle est encore trop lente pour être mise en œuvre directement dans une boucle de planification des mouvements d’un robot, où les décisions doivent être prises en quelques microsecondes, explique Alexandre Amice.

Les chercheurs prévoient d’accélérer leur processus en ignorant les situations qui ne nécessitent pas de contrôles de sécurité, comme lorsque le robot est loin de tout objet avec lequel il pourrait entrer en collision. Ils souhaitent également expérimenter des solveurs d’optimisation spécialisés qui pourraient fonctionner plus rapidement.

« Les robots ont souvent des ennuis en grattant les obstacles en raison de mauvaises approximations effectuées lors de la génération de leurs itinéraires. Alexandre Amice, Peter Werner et Russ Tedrake sont venus à la rescousse avec un nouvel algorithme puissant pour garantir rapidement que les robots ne dépassent jamais leurs limites, en exploitant soigneusement les méthodes avancées de la géométrie algébrique computationnelle », ajoute Steven LaValle, professeur à la Faculté des technologies de l’information et de l’électricité. Ingénieur à l’Université d’Oulu en Finlande, et qui n’a pas participé à ces travaux.

Ce travail a été soutenu en partie par Amazon et le laboratoire de recherche de l’US Air Force.

https://news.mit.edu/2024/method-rapidly-verifies-robot-will-avoid-collisions-0307

https://arxiv.org/pdf/2310.16603.pdf