Graph of Convex Sets

Aussi appelé: GCS, graphs of convex sets
Catégorie: Planning & manipulation › Trajectory optimisation
Mots-clés: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

Formulation de planification de mouvement qui relie dans un graphe des régions convexes de l'espace libre et trouve, par optimisation convexe, un chemin lisse et sans collision à travers elles.

Définition

Un graphe d'ensembles convexes (graph of convex sets, GCS) est un graphe dont chaque sommet est un ensemble convexe et dont le point choisi dans chaque ensemble est une variable de décision continue. Les arêtes relient des ensembles entre lesquels on peut passer, et les coûts et contraintes des arêtes sont des fonctions convexes des points à chaque extrémité. Trouver l'itinéraire le moins coûteux à travers un tel graphe combine un choix discret, quels ensembles traverser, et un choix continu, où aller dans chaque ensemble. Tobia Marcucci, Russ Tedrake et leurs collègues ont formulé ce problème de plus court chemin et montré que, bien qu'il s'agisse en général d'un problème en nombres entiers mixtes, il possède une relaxation convexe forte qui est souvent exacte ou presque exacte.

Pour la planification de mouvement, la partie sans collision de l'espace des configurations est d'abord couverte par une collection de régions convexes, par exemple avec l'algorithme IRIS, qui fait croître de grands polytopes sans obstacle à partir de points d'amorçage. Chaque région devient un sommet, les régions qui se chevauchent sont reliées par des arêtes, et dans chaque région la trajectoire est représentée par une courbe lisse, typiquement une courbe de Bézier, qui reste dans la région parce que ses points de contrôle y restent. Les coûts comme la longueur du chemin, la durée ou l'énergie, ainsi que les limites de vitesse et d'accélération, s'écrivent comme des contraintes convexes. Résoudre la relaxation puis l'arrondir donne une trajectoire lisse et sans collision, sans recherche par échantillonnage ni post-traitement.

L'approche suppose une géométrie euclidienne ordinaire au sein de chaque ensemble. Les robots dont l'espace des configurations se referme sur lui-même, comme des articulations rotoïdes continues sans butées ou le cap d'une base mobile, ne correspondent pas directement à cette hypothèse. Des extensions remplacent les ensembles convexes par des ensembles géodésiquement convexes sur une variété : des ensembles dans lesquels deux points quelconques sont reliés par un unique plus court chemin, ou géodésique, qui reste dans l'ensemble. Avec ce changement, la même formulation en graphe peut planifier sur de tels espaces non euclidiens. GCS est disponible dans la boîte à outils Drake.

Pourquoi c'est important

Les planificateurs par échantillonnage trouvent des chemins faisables mais ont généralement besoin d'un lissage et ne donnent aucune mesure de la qualité du chemin. GCS produit des trajectoires lisses et respectant les contraintes en une seule optimisation, souvent avec un certificat de la distance à l'optimum, ce qui est précieux pour des bras qui travaillent de manière répétée dans des cellules fixes comme des étagères et des postes de travail.

Applications principales

Planification de trajectoires sans collision pour manipulateurs dans des cellules de travail fixes
Planification pour des robots à articulations continues ou à espaces des configurations qui se referment
Planification des appuis et des contacts sur des régions convexes du terrain
Trajectoires en temps minimal pour drones dans des environnements encombrés
Planification bimanuelle et multi-bras dans des espaces de travail partagés

En pratique

Une équipe qui déploie un bras pour prélever dans un ensemble fixe de bacs d'étagère génère d'abord hors ligne des régions convexes de l'espace des configurations sans collision, en amorçant IRIS à des configurations devant et dans chaque bac. Cela prend du temps mais n'est à refaire que lorsque la cellule change. À l'exécution, chaque demande de prélèvement devient une requête GCS de la configuration actuelle vers un but situé dans un bac. Le solveur renvoie une trajectoire lisse respectant les limites de vitesse, et le temps de résolution croît avec le nombre de régions ; l'équipe garde donc l'ensemble de régions pas plus grand que ce que la cellule exige. Si un but se trouve hors de toutes les régions, la requête échoue ; l'équipe ajoute alors des points d'amorçage là où la couverture manque. Une vérification de collision à court horizon protège toujours contre les objets qui n'étaient pas dans le modèle.

Idées reçues

GCS exige que l'espace libre soit convexe — il exige que l'espace libre soit couvert par une union de régions convexes, qui peut approcher des formes complexes
GCS renvoie toujours l'optimum global par optimisation convexe — la relaxation est souvent exacte mais pas toujours ; un arrondi ou une résolution en nombres entiers mixtes peut être nécessaire
GCS remplace entièrement la vérification de collision — il ne garantit l'absence de collision que par rapport aux régions utilisées, qui doivent donc refléter l'environnement réel

Qui devrait le savoir

Ingénieurs en planification de mouvement pour manipulateurs et drones
Chercheurs en planification fondée sur l'optimisation
Intégrateurs de systèmes de prélèvement et d'assemblage en cellule fixe
Étudiants en robotique qui étudient la planification et l'optimisation convexe

Technologies associées

Drake
Génération de régions IRIS (IRIS Region Generation)
Courbes de Bézier (Bézier Curves)
Optimisation convexe (Convex Optimization)
Programmation convexe en nombres entiers mixtes (Mixed-Integer Convex Programming)

Termes associés

Projets associés

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OpenArm: 7DOF humanoid arm for physical AI research in contact-rich environments

Vidéos

MIT Robotics - Russ Tedrake - Planning with Graphs of Convex Sets (in the age of foundation models): MIT Robotics