Motion planning for hundreds of floating robots

Résumé Technique : Planification de Mouvement pour des Centaines de Robots Flottants

Énoncé du Problème
L'article traite du défi que représente la planification de trajectoires exemptes de collisions et dynamiquement réalisables pour de grandes flottes de robots flottants omnidirectionnels (robots de surface) opérant sur une variété plane. Contrairement aux drones aériens, qui peuvent utiliser des manœuvres verticales pour déconflicter les transitions denses, les robots de surface sont contraints à la 2D, ce qui rend la coordination et l'évitement de collisions intrinsèquement plus difficiles. Le contexte de planification est celui de la conception de spectacles interactifs, où un designer spécifie des images clés (keyframes) éparses (configurations de départ et d'arrivée) et nécessite un retour quasi immédiat (quelques secondes) pour générer des trajectoires pouvant s'étendre sur plusieurs minutes et des milliers de pas de temps.

La difficulté principale réside dans la scalabilité de l'évitement de collisions. À mesure que la taille de la flotte ($N$) augmente, le couplage entre agents croît rapidement (souvent de manière quadratique), entraînant un nombre de contraintes de collision par paires de l'ordre de $\binom{N}{2}K$ (où $K$ est le nombre de pas de temps). Pour des $N$ élevés (ex. 500) et des $K$ élevés (ex. 1000), les formulations standards de Programmation Convexe Séquentielle (SCP) résultent en des Programmes Quadratiques (QP) possédant des centaines de millions d'entrées non nulles, ce qui les rendrait informatiquement intraitables pour des boucles de conception itératives.

Méthodologie
Les auteurs proposent un pipeline de planification hiérarchique et scalable qui décompose le problème globalement couplé en sous-problèmes plus petits et indépendants. Le pipeline se compose de quatre étapes principales :

1. Initialisation et Allocation :

   • Le processus commence par un problème d'assignation à coût minimum pour faire correspondre les robots aux positions cibles. Pour les robots « étiquetés » (ceux ayant des cibles définies par l'utilisateur), le coût est de zéro ou infini pour imposer des correspondances spécifiques. Pour les robots « non étiquetés », le coût est la distance euclidienne, minimisant le déplacement total pour réduire les échanges inutiles.
   • Une trajectoire initiale est générée via une interpolation linéaire entre les positions de départ et d'arrivée. Cette initialisation n'est généralement pas exempte de collisions.

2. Construction du Graphe de Collisions :

   • Un graphe spatio-temporel est construit où les nœuds représentent des paires robot-temps.
   • Les arêtes spatiales connectent les robots au même pas de temps s'ils se trouvent dans un rayon de sécurité $R$.
   • Les arêtes temporelles connectent un robot à lui-même à travers des pas de temps consécutifs si une collision se produit dans l'un ou l'autre.
   • Les composantes connexes de ce graphe définissent des « clusters de collision ». Les auteurs utilisent une structure de données KD-tree pour détecter efficacement les violations par paires, atteignant une accélération de près de 2000× par rapport à une vérification naïve par paires.

3. Clustering et Décomposition :

   • Pour donner au l'optimiseur la liberté de planifier des détours, la fenêtre temporelle de chaque cluster est étendue (tamponnée) par un hyperparamètre $B$ (fixé à 3 secondes).
   • Les clusters tamponnés qui se chevauchent sont fusionnés à l'aide d'une procédure d'union-find. Pour éviter la création de sous-problèmes trop importants (ce qui annulerait les bénéfices de la parallélisation), une limite de complexité est imposée. Si la fusion dépasse un seuil d'entrées non nulles dans les matrices QP, le groupe est divisé à l'aide d'un mécanisme de score qui minimise la complexité maximale des sous-problèmes résultants.

4. Résolution de Sous-problèmes et Fusion :

   • Chaque cluster est résolu indépendamment et en parallèle à l'aide d'un cadre SCP.
   • Amélioration de la Formulation : L'article introduit une formulation de « transcription directe » où le vecteur de décision inclut à la fois les positions et les vitesses ($\chi = [p, v]$). Cela convertit la dynamique en contraintes d'égalité locales et améliore considérablement la parcimonie de la matrice de contrainte (réduisant la complexité de $O(N^2K^2)$ à $O(N^2K)$) par rapport à la formulation de « tir direct » (direct shooting) utilisée dans les travaux précédents.
   • Robustesse : Les mécanismes incluent la perturbation de l'initialisation pour les configurations symétriques, l'élagage adaptatif de la discrétisation si une résolution est infaisable, et une étape de polissage légère.
   • Détection de Cycles : Le pipeline détecte les dépendances cycliques où la fusion de clusters mène à des motifs de collision oscillants. En cas de détection, les sous-problèmes conflictuels sont verrouillés dans un seul sous-problème conjoint pour les itérations suivantes.
   • Enfin, les solutions locales sont fusionnées en une trajectoire globale, et la boucle se répète jusqu'à ce qu'une solution exempte de collisions soit trouvée.

Contributions Clés

• Pipeline Hiérarchique Scalable : Une méthode qui construit un graphe de collision, décompose le problème en clusters d'interaction et résout ces derniers en parallèle, permettant la planification de centaines de robots en quelques secondes.
• Mécanismes de Décomposition Robustes : Des techniques pour gérer les pathologies courantes, notamment des mises à jour rapides de graphes, des stratégies de tamponnage, des limites de complexité pour empêcher l'explosion des sous-problèmes, et la détection de cycles pour éviter l'oscillation.
• Reformulation de l'Optimisation : Un passage à une formulation de transcription directe pour l'optimisation de trajectoire au niveau des clusters, ce qui améliore la parcimonie du QP et la robustesse du solveur, particulièrement pour les configurations avec une forte proportion de robots étiquetés.

Résultats et Validation
Le système a été validé par des simulations et deux déploiements en conditions réelles :

• Simulation : Le pipeline a généré avec succès des trajectoires sans collision pour des flottes allant jusqu'à 500 robots sur 1000 pas de temps. Dans une étude de cas avec 500 robots, le solveur a atteint un taux de convergence de 100 % pour jusqu'à 30 % de robots étiquetés et de 99 % pour des pourcentages plus élevés, avec des temps de calcul typiquement inférieurs à quelques secondes.
• Déploiement Réel 1 (Lac de Zurich) : Une flotte de 24 robots a été chorégraphiée pour des transitions s'étendant sur 1 à 2 minutes (400+ pas de temps). Les designers pouvaient ajuster de manière itérative les images clés et régénérer les trajectoires en quelques secondes.
• Déploiement Réel 2 (Venise Biennale 2025) : Une flotte de 8 robots a effectué des transitions s'étendant sur plus de 2000 pas de temps. Une trajectoire de 2491 étapes a été calculée en 1,23 seconde.

Signification
L'article affirme que ce pipeline axé sur l'ingénierie répond au goulot d'étranglement principal de la scalabilité de la planification de mouvement multi-robots sur des surfaces. En décomposant le problème et en optimisant la formulation du solveur, l'approche est de plusieurs ordres de grandeur plus rapide que les pipelines SCP monolithiques traditionnels. Cette vitesse permet une expérience utilisateur fluide et interactive pour la conception de la chorégraphie, permettant aux designers d'ajuster itérativement des images clés éparses et de recevoir un retour immédiat sur des trajectoires exemptes de collisions et dynamiquement réalisables, une capacité auparavant limitée par les contraintes de calcul dans les environnements de surface en 2D.