Un nouveau cadre d’optimisation pour la planification des mouvements des robots

Il n’est pas facile pour un robot de sortir d’un labyrinthe. Imaginez ces machines essayant de traverser la salle de jeux d’un enfant pour atteindre la cuisine, avec divers jouets éparpillés sur le sol et des meubles bloquant certains chemins potentiels. Ce labyrinthe désordonné oblige le robot à calculer le trajet le plus optimal jusqu’à sa destination, sans se heurter à aucun obstacle. Quel est le bot à faire ?

L’algorithme d’optimisation de trajectoire Graphiques d’ensembles convexes (GCS) des chercheurs du MIT CSAIL présente un système de planification de mouvement évolutif et sans collision pour ces besoins de navigation robotique.

L’approche allie la recherche de graphes (une méthode pour trouver des chemins discrets dans un réseau) et l’optimisation convexe (une méthode efficace pour optimiser des variables continues afin de minimiser un coût donné), et peut trouver rapidement des chemins à travers des environnements de type labyrinthe tout en optimisant simultanément le trajectoire du robot.

GCS peut tracer des trajectoires sans collision dans jusqu’à 14 dimensions (et potentiellement plus), dans le but d’améliorer la façon dont les machines fonctionnent en tandem dans les entrepôts, les bibliothèques et les ménages.

Le projet dirigé par CSAIL trouve systématiquement des chemins plus courts en moins de temps que des planificateurs comparables, démontrant la capacité de GCS à planifier efficacement dans des environnements complexes.

Dans les démonstrations, le système a habilement guidé deux bras robotiques tenant une tasse autour d’une étagère tout en optimisant le temps et le chemin les plus courts. Le mouvement synchronisé du duo ressemblait à une routine de danse en couple, se balançant sur les bords de la bibliothèque sans laisser tomber d’objets.

Dans les configurations ultérieures, les chercheurs ont retiré les étagères et les robots ont échangé les positions des peintures en aérosol et se sont remis une boîte à sucre.

Le succès de ces tests réels montre le potentiel de l’algorithme dans des domaines tels que la fabrication, où deux bras robotiques travaillant en tandem pourraient faire tomber un article d’une étagère. De même, ce duo pourrait aider à ranger des livres dans une maison ou une bibliothèque, en évitant les autres objets à proximité.

Alors que les problèmes de cette nature étaient auparavant résolus avec des algorithmes basés sur l’échantillonnage, qui peuvent poser problème dans des espaces de grande dimension, GCS utilise une optimisation convexe rapide et peut coordonner efficacement le travail de plusieurs robots.

« Les robots excellent dans les mouvements répétitifs et pré-planifiés dans des applications telles que la construction automobile ou l’assemblage électronique, mais ont du mal à générer des mouvements en temps réel dans des environnements ou des tâches nouveaux.

Les précédentes méthodes de planification de mouvement de pointe utilisent une approche « en étoile », utilisant des graphiques précalculés d’un nombre fini de configurations fixes, connues pour être sûres. Pendant le fonctionnement, le robot doit respecter strictement cette feuille de route, ce qui conduit souvent à des mouvements inefficaces du robot.

La planification des mouvements à l’aide de Graph-of-Convex-Sets (GCS) permet aux robots de s’adapter facilement à différentes configurations au sein de régions convexes précalculées, ce qui permet au robot de « contourner le coin » lorsqu’il établit ses plans de mouvement. Ce faisant, GCS permet au robot de calculer rapidement et très efficacement des plans dans des régions sûres en utilisant une optimisation convexe.

« Cet article présente une nouvelle approche susceptible d’améliorer considérablement la vitesse et l’efficacité des mouvements des robots ainsi que leur capacité à s’adapter à de nouveaux environnements », déclare David MS Johnson, cofondateur et PDG de Dexai Robotics.

GCS a également prospéré dans les démonstrations de simulation, où l’équipe a étudié comment un quadrirotor pouvait voler à travers un bâtiment sans s’écraser sur des arbres ni échouer à entrer dans les portes et les fenêtres selon le bon angle. L’algorithme a optimisé le contournement des obstacles tout en tenant compte de la riche dynamique du quadrirotor.

Un mariage optimal

La recette du succès de l’équipe du MIT repose sur le mariage de deux ingrédients clés : la recherche graphique et l’optimisation convexe. Le premier élément de GCS recherche les graphiques en explorant leurs nœuds, en calculant différentes propriétés à chacun pour trouver des modèles cachés et identifier le chemin le plus court pour atteindre la cible. Tout comme les algorithmes de recherche graphique utilisés pour le calcul de distance dans Google Maps, GCS crée différentes trajectoires pour atteindre chaque point de son parcours vers sa destination.

En combinant recherche graphique et optimisation convexe, GCS peut trouver des chemins à travers des environnements complexes et optimiser simultanément la trajectoire du robot.

GCS atteint cet objectif en traçant graphiquement différents points dans sa zone environnante, puis en calculant comment atteindre chacun d’entre eux sur le chemin de sa destination finale. Cette trajectoire prend en compte différents angles pour garantir que le robot évite d’entrer en collision avec les bords de ses obstacles. Le plan de mouvement qui en résulte permet aux machines de franchir des obstacles potentiels, en manœuvrant avec précision à chaque virage de la même manière qu’un conducteur évite les accidents dans une rue étroite.

GCS a été initialement proposé dans un article de 2021 comme cadre mathématique pour trouver les chemins les plus courts dans les graphiques où le franchissement d’une arête nécessitait de résoudre un problème d’optimisation convexe.

Se déplaçant avec précision sur chaque sommet dans de grands graphiques et des espaces de grande dimension, GCS avait un potentiel évident dans la planification de mouvements robotiques. Dans un article ultérieur, Marcucci et son équipe ont développé un algorithme appliquant leur cadre à des problèmes de planification complexes pour des robots se déplaçant dans des espaces de grande dimension.

L’article de 2023 a fait la couverture de Robotique scientifiquealors que les premiers travaux du groupe sont désormais publiés dans le Journal sur l’optimisation de la Société de mathématiques industrielles et appliquées (SIAM).

Bien que l’algorithme excelle dans la navigation dans des espaces restreints sans collisions, il reste encore de la place pour se développer. L’équipe CSAIL note que GCS pourrait éventuellement aider à résoudre des problèmes plus complexes où les robots doivent entrer en contact avec leur environnement, comme pousser ou faire glisser des objets hors d’un espace restreint. le chemin. L’équipe explore également les applications de l’optimisation de trajectoire GCS à la planification des tâches et des mouvements des robots.

« Je suis très enthousiasmé par cette application de GCS à la planification de mouvements. Mais ce n’est que le début. Ce cadre est profondément lié à de nombreux résultats fondamentaux en matière d’optimisation, de contrôle et d’apprentissage automatique, nous donnant un nouvel effet de levier sur des problèmes qui sont simultanément continus. et combinatoire », déclare Russ Tedrake, professeur au MIT, chercheur principal du CSAIL et co-auteur d’un nouvel article sur le travail. « Il y a encore beaucoup de travail à faire. »