Des chercheurs du MIT ont mis au point une technique de vérification de sécurité capable de démontrer avec une précision absolue que la trajectoire d'un robot restera exempte de collisions (à condition que les modèles du robot et de son environnement soient précis). Leur méthode, d'une précision telle qu'elle peut distinguer des trajectoires différant de quelques millimètres seulement, fournit cette preuve en quelques secondes.

Mais l'utilisateur n'a pas à se fier aux dires des chercheurs : la preuve mathématique générée par cette technique peut être rapidement vérifiée au moyen d'opérations mathématiques relativement simples.

Les chercheurs ont obtenu ce résultat grâce à une technique algorithmique particulière appelée programmation par somme de carrés, qu'ils ont adaptée pour résoudre efficacement le problème de vérification de sécurité. La programmation par somme de carrés permet de généraliser la méthode à une large gamme de mouvements complexes.

Cette technique pourrait s'avérer particulièrement utile pour les robots devant se déplacer rapidement tout en évitant les collisions dans des espaces encombrés, comme les robots préparant des aliments dans une cuisine professionnelle. Elle convient également aux situations où les collisions entre robots pourraient entraîner des blessures, comme celles rencontrées par les robots médicaux soignant des patients vulnérables.

« Grâce à ces travaux, nous avons démontré que certains problèmes complexes peuvent être résolus à l’aide d’outils conceptuellement simples. La programmation par sommes de carrés est une idée algorithmique puissante et, bien qu’elle ne résolve pas tous les problèmes, appliquée avec soin, elle peut en résoudre certains non triviaux », explique Alexandre Amice, doctorant en génie électrique et informatique et auteur principal d’un article sur cette technique.

Amice a collaboré à cet article avec Peter Werner, également étudiant en génie électrique et informatique, et avec Russ Tedrake, professeur titulaire de la chaire Toyota d'aéronautique, d'astronautique et de génie mécanique au sein de ce même département, et membre du Laboratoire d'informatique et d'intelligence artificielle (CSAIL). Ces travaux seront présentés à la Conférence internationale sur la robotique et l'automatisation.

Certifier la sécurité

De nombreuses méthodes actuelles de vérification de l'absence de collision lors du déplacement planifié d'un robot consistent à simuler sa trajectoire et à vérifier toutes les quelques secondes si le robot entre en collision avec un obstacle. Cependant, ces contrôles de sécurité statiques ne permettent pas de prédire si le robot entrera en collision avec un obstacle dans les secondes qui suivent.

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

Conceptuellement, une façon de démontrer qu'un robot ne se dirige pas vers une collision consiste à brandir une feuille de papier séparant le robot de tout obstacle dans son environnement. Mathématiquement, cette feuille de papier est appelée hyperplan. De nombreux algorithmes de contrôle de sécurité ne génèrent cet hyperplan qu'une seule fois. Cependant, à chaque déplacement du robot, un nouvel hyperplan doit être recalculé pour effectuer le contrôle de sécurité.

À l'inverse, cette nouvelle technique génère une fonction hyperplan qui se déplace avec le robot, ce qui lui permet de démontrer qu'une trajectoire entière est exempte de collisions au lieu de travailler avec un hyperplan à chaque fois.

Les chercheurs ont utilisé la programmation par somme de carrés, un outil algorithmique permettant de transformer un problème statique en une fonction. Cette fonction est une équation qui décrit la position que doit occuper l'hyperplan en chaque point du chemin planifié afin d'éviter toute collision.

La somme des carrés peut être généralisée au programme d'optimisation pour trouver une famille d'hyperplans sans collision. Souvent considérée comme une méthode d'optimisation lourde, adaptée uniquement à une utilisation hors ligne, elle s'est révélée extrêmement efficace et précise pour ce problème.

« La clé résidait dans la manière d'appliquer la somme des carrés à notre problème spécifique. Le plus grand défi a été de trouver 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 ? » explique Amice.

Comme son nom l'indique, la somme des carrés est une fonction qui représente la somme de plusieurs carrés. Cette fonction est toujours positive, puisque le carré d'un nombre est toujours positif.

Faites confiance, mais vérifiez

En vérifiant que la fonction hyperplan contient des valeurs au carré, on peut facilement vérifier que la fonction est positive, ce qui signifie que le chemin est sans collision, explique Amice.

Bien que la méthode garantisse une précision parfaite, cela suppose que l'utilisateur dispose d'un modèle exact du robot et de son environnement ; le certificateur mathématique n'est performant que dans la mesure où le modèle l'est également.

« Ce qui est formidable avec cette méthode, c'est que les tests sont très faciles à interpréter ; vous n'avez donc pas à vous fier à mon code, car vous pouvez le vérifier vous-même», ajoute-t-il.

Ils ont testé leur technique en simulation, certifiant que les plans de mouvement complexes de robots à un et deux bras étaient exempts de collisions. Dans sa version la plus lente, la méthode ne nécessitait que quelques centaines de millisecondes pour générer un test, ce qui la rend beaucoup plus rapide que les autres techniques alternatives.

Bien que leur méthode soit suffisamment rapide pour être utilisée comme contrôle de sécurité final dans certaines situations réelles, elle est encore trop lente pour être appliquée directement dans la boucle de planification des mouvements d'un robot, où les décisions doivent être prises en microsecondes, explique Amice.

Les chercheurs prévoient d'accélérer le processus en ignorant les situations ne nécessitant pas de contrôles de sécurité, par exemple lorsque le robot est éloigné des objets avec lesquels il pourrait entrer en collision. Ils souhaitent également expérimenter des solveurs d'optimisation spécialisés, capables de fonctionner plus rapidement.

Ce travail a été financé, en partie, par Amazon et le Laboratoire de recherche de l'armée de l'air des États-Unis.