Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

Auteurs: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · RSS 2023

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

Traite les espaces articulaires qui bouclent sur eux-mêmes (bases mobiles, articulations continues) comme des variétés plates, de sorte que le planificateur de plus court chemin GCS donne toujours des chemins globalement optimaux et sans collision.

Pourquoi c'est important

Les manipulateurs mobiles et les bras dotés d'articulations de base sans limite peuvent désormais utiliser un planificateur qui certifie que chaque point de la trajectoire est sans collision et qui, lorsqu'il est résolu exactement, est optimal dans l'espace libre certifié. L'article prouve aussi qu'une courbure positive (par exemple les rotules SO(3) ou les corps flottants libres) brise la convexité, ce qui marque la limite de cette approche.

Problème

Le planificateur GCS de Marcucci et al. trouve des chemins sans collision et globalement optimaux grâce à une décomposition de l'espace de configuration libre en ensembles convexes, mais seulement pour des espaces de configuration euclidiens. Une base mobile capable de tourner de 360° complets, ou une articulation rotoïde continue, revient sur elle-même, de sorte que son espace de configuration n'est pas euclidien. Ajouter des butées articulaires artificielles ou traiter les angles comme des réels non bornés soit rend l'optimum inatteignable, soit exige une connaissance préalable de la solution et de nombreux ensembles dupliqués.

Solution proposée

Les auteurs modélisent l'espace de configuration comme une variété riemannienne et définissent un Graph of Geodesically-Convex Sets (GGCS), dont ils prouvent qu'il conserve les garanties du GCS ordinaire. Pour les variétés plates (à courbure nulle), qui couvrent tout robot construit à partir d'articulations à 1 DoF et d'une base SE(2), chaque ensemble est envoyé dans l'espace euclidien par une carte isométrique locale, et le problème se réduit à un problème GCS convexe standard en nombres entiers mixtes avec des contraintes de transition affines. Les régions sont construites avec IRIS et bornées articulation par articulation par le rayon de convexité, et les trajectoires de Bézier par morceaux avec contraintes de continuité se transposent telles quelles.

Idées clés

• SE(2), toute variété de dimension 1 et les produits de variétés plates sont plats, de sorte que les robots constitués d'articulations à un seul DoF et d'une base mobile entrent dans le cadre de la méthode ; les rotules à 3 DoF non
• Borner chaque région IRIS, articulation par articulation, par le rayon de convexité garantit que la région reste géodésiquement convexe une fois ramenée sur la variété
• Sur un espace plat muni de coordonnées alignées globalement, les applications de transition sont affines, si bien que les contraintes de raccordement des extrémités et de continuité des dérivées restent convexes
• Un seul point de courbure positive suffit à rendre la fonction distance riemannienne non convexe dans tout voisinage de ce point (théorème 5)

Principaux résultats

• Robot ponctuel sur un tore : chemin optimal qui fait le tour en 0,79 s ; bras plan à 5 articulations continues : planifie en 5,36 s et 4,63 s, l'un des chemins faisant tourner l'articulation centrale de plus de 360°
• Bras plan : chemins relax-and-round de longueur 7,749 et 8,448 contre des optima branch-and-bound de 7,274 et 8,008
• KUKA iiwa avec une articulation de base continue (simulation) : 14 mouvements de tri de tasses utilisant 18 régions convexes, en moyenne 25,75 s par mouvement (plage 4,63–50,30 s)
• PR2 (simulation, espace de configuration 15-D), 7 tâches d'atteinte dans des étagères : les chemins GGCS étaient sans collision dans tous les cas, par ex. 1M→4M longueur 3,875 contre 14,554 pour PRM ; Drake-Trajopt et PRM+Trajopt donnaient parfois des chemins plus courts, mais ceux-ci entraient légèrement en collision
• La planification en ligne du PR2 a pris 25,51–66,15 s pour GGCS-Planner, contre 0,49–0,54 s pour le PRM, 2,26–15,23 s pour Drake-Trajopt et 11,61–40,10 s pour PRM+Trajopt
• Préparation hors ligne du PR2 : une région IRIS prenait en moyenne 30,20 s (8,56–75,42 s), toutes les régions 156,63 s en parallèle ; la construction du PRM à 100 000 échantillons a pris 124,39 s

Limites

• Les auteurs indiquent que la méthode ne peut pas traiter les coûts et contraintes non convexes comme une dynamique non linéaire et les chaînes cinématiques fermées, ni les rotules
• Les espaces à courbure positive comme SO(3) sont exclus, car la fonction distance y est démontrablement non convexe
• L'optimalité ne vaut qu'à l'intérieur de l'espace libre 'certifié' couvert par les régions ; les performances dépendent fortement du choix des régions, et pour le PR2 certaines régions intermédiaires ont été ajoutées à la main
• Les temps de planification en ligne du PR2 (25,51–66,15 s) étaient supérieurs à ceux de toutes les méthodes de référence comparées
• Tous les résultats robotiques sont en simulation ; les auteurs citent comme travaux futurs la planification bimanuelle avec contraintes cinématiques implicites et la planification à travers le contact

Impact sur le domaine

Finaliste du RSS 2023 Best Paper Award, avec 44 citations. Les auteurs publient des enregistrements interactifs de chaque trajectoire sur un site de résultats.

Résumé

Calculer des trajectoires optimales et sans collision pour des systèmes de grande dimension est un problème difficile. Les planificateurs fondés sur l'échantillonnage peinent face à la dimensionnalité, tandis que les optimiseurs de trajectoire peuvent rester bloqués dans des minima locaux en raison des non-convexités inhérentes au paysage d'optimisation. L'utilisation de la programmation en nombres entiers mixtes pour encapsuler ces non-convexités et trouver des trajectoires globalement optimales s'est récemment montrée très prometteuse, notamment grâce à des relaxations convexes serrées et à des stratégies d'approximation efficaces qui réduisent fortement les temps de calcul. Ces approches étaient jusqu'ici limitées aux espaces de configuration euclidiens, ce qui empêchait leur utilisation avec des bases mobiles ou des articulations rotoïdes continues. Dans cet article, nous traitons de tels scénarios en modélisant les espaces de configuration comme des variétés riemanniennes, et nous décrivons une procédure de réduction du cas à courbure nulle à un problème d'optimisation convexe en nombres entiers mixtes. Nous démontrons nos résultats sur diverses plateformes robotiques, notamment en produisant des trajectoires efficaces et sans collision pour un PR2, manipulateur mobile bimanuel.

Liens

• arXiv 2305.06341: https://arxiv.org/abs/2305.06341
• DOI 10.1177/02783649241302419: https://doi.org/10.1177/02783649241302419
• PDF: https://arxiv.org/pdf/2305.06341v1
• Page du projet: https://ggcs-anonymous-submission.github.io/