RecherchearXiv cs.RO 1 septembre 2026

Planification certifiée par échantillonnage à l'aide de graphes d'ensembles convexes

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Des chercheurs publient sur arXiv (référence 2608.29770v1) la première mesure chiffrée d'un écart resté largement ignoré dans la planification de trajectoire par graphes d'ensembles convexes (GCS), une famille de planificateurs réputés produire des trajectoires sans collision "par construction". Le problème: le générateur de régions convexes sous-jacent ne garantit cette absence de collision que de façon probabiliste, et aucun planificateur GCS existant ne vérifie réellement cette propriété avant de livrer sa réponse. Sur une bibliothèque bimanuelle à 14 degrés de liberté (DOF) mise à l'échelle, les auteurs mesurent que 3,2 % des échantillons d'interface entre régions sont en réalité en collision. Le planificateur de référence testé, GCS* (approche par recherche), transforme cette erreur de volume en 62 % d'erreur de réponse: 18 des 29 requêtes de pick-and-place évaluées retournent des trajectoires faisant pénétrer les bras jusqu'à 91 mm dans les étagères, tout en étant rapportées comme des succès.

Ce résultat met en défaut une hypothèse de confort répandue dans la planification de mouvement robotique, celle voulant que les garanties théoriques "correct par construction" des GCS se traduisent automatiquement en fiabilité opérationnelle. Pour des intégrateurs déployant des bras robotiques en environnement encombré (entrepôt, cellule industrielle, picking bimanuel), cela signale un risque concret de collisions silencieuses, d'autant plus critique que l'espace de configuration est dense avec deux bras. Les correctifs évidents échouent: durcir dix fois le contrat d'acceptation des régions, générer des régions certifiées par sommes de carrés, ou imposer des marges uniformes, détruisent tous la connectivité nécessaire à la planification avant même d'obtenir une garantie de solidité, révélant une tension structurelle entre sécurité et faisabilité dans cette famille d'algorithmes.

Face à ce constat, les auteurs proposent un planificateur qui certifie chaque réponse plutôt que de faire confiance à la génération de régions en amont: il échantillonne les recouvrements et faces partagées de la décomposition convexe, élague la recherche via une borne informée admissible, vérifie en continu le candidat proposé à chaque tour par une chaîne de certificats de dégagement sans paramètre de résolution arbitraire, répare les échecs par des détours locaux internes aux régions, puis revérifie le polissage convexe final. Sur les mêmes 29 requêtes, ce planificateur ne produit aucune réponse invalide, contre 21 pour la référence, atteint sa première réponse certifiée en 0,11 seconde contre 1,59 seconde pour la version non vérifiée, et reproduit exactement l'optimum de référence chaque fois que celui-ci est physiquement valide. L'article, un pré-print de recherche sans affiliation industrielle précisée, ne mentionne ni calendrier de déploiement ni partenaire commercial.

Dans nos dossiers

arXiv cs.RO

À lire aussi

1arXiv cs.RO

Planification de mouvements par logique temporelle de signaux via des graphes d'ensembles convexes

Une équipe de chercheurs a publié sur arXiv (arXiv:2605.23240) un cadre de planification de trajectoires en temps continu combinant la logique temporelle de signaux (STL, Signal Temporal Logic) et les graphes d'ensembles convexes (GCS, Graphs of Convex Sets). L'objectif est de générer des trajectoires lisses satisfaisant à la fois des contraintes logico-temporelles de haut niveau, par exemple "atteindre la zone A entre t=2 s et t=5 s tout en évitant B", et des limites cinématiques de bas niveau comme les bornes de vitesse. La méthode encode d'abord la spécification STL sous forme d'automate temporisé, le couple à une décomposition convexe de l'espace de configuration, puis reformule l'ensemble comme un problème de plus court chemin sur un GCS. La solution produit des trajectoires en B-splines de Bézier, validées expérimentalement sur un quadrirotor 3D, un humanoïde à 30 degrés de liberté (DoF) et un bras industriel UR-3 testé en conditions matérielles réelles. La contribution principale est de rendre tractable un problème historiquement difficile. Les approches classiques de planification sous STL s'appuient sur la programmation mixte entière (MILP), dont la complexité est exponentielle avec la dimension de l'espace ou la longueur de l'horizon temporel. Ce travail démontre qu'une fois l'automate temporisé et la décomposition convexe fixés, la relaxation convexe évolue polynomialement avec la dimension de l'espace de configuration et le degré des splines de Bézier, ce qui constitue une garantie de passage à l'échelle concrète. Le test sur un humanoïde à 30 DoF est significatif : c'est précisément la gamme de systèmes où les planificateurs STL classiques échouent. La validation hardware sur UR-3 confirme que les trajectoires produites sont directement exécutables, sans post-traitement supplémentaire. Le cadre GCS a été introduit vers 2022 par Marcucci, Tedrake et leurs collaborateurs au MIT comme outil d'optimisation de trajectoires dans des espaces fragmentés en régions convexes. Ce papier étend l'approche aux spécifications temporelles contraintes, une jonction entre vérification formelle et robotique opérationnelle. Les approches concurrentes incluent la MPC non linéaire sous STL et les planificateurs par échantillonnage avec satisfaction de contraintes temporelles. L'article reste un preprint non relu par les pairs ; les benchmarks présentés couvrent essentiellement des espaces de basse à moyenne dimension, et l'extension aux environnements dynamiques ou à la replanification en temps réel n'est pas encore abordée.

UELa validation matérielle sur bras UR-3 (Universal Robots, Danemark/UE) offre une pertinence indirecte pour les équipes R&D européennes en planification de trajectoires, mais la recherche est conduite au MIT sans implication directe d'acteurs français ou européens.

RecherchePaper

1 source

2arXiv cs.RO

GCS-Bridging : restaurer la connectivité des ensembles convexes déconnectés pour la planification de mouvement par graphe d'ensembles convexes

Les chercheurs derrière GCS-Bridging (arXiv:2608.22326v1, preprint récent) proposent une méthode qui corrige une faille pratique des planificateurs de trajectoire bases sur les Graph-of-Convex-Sets (GCS). L'approche GCS découpe l'espace de configuration libre de collision d'un robot en un ensemble fini de régions convexes, puis calcule directement une trajectoire a travers ce graphe, ce qui simplifie nettement le calcul par rapport aux planificateurs par échantillonnage classiques. Le problème: les méthodes GCS existantes supposent une connectivité suffisante entre régions et échouent purement et simplement quand la zone de départ et la zone d'arrivée appartiennent a deux composantes distinctes de la carte initiale. GCS-Bridging relie ces ilots disjoints en traçant d'abord un chemin de points libres de collision entre eux, puis en "gonflant" ce chemin pour créer de nouvelles régions convexes qui comblent la discontinuité. Teste sur plusieurs algorithmes de la famille IRIS et de multiples scenarios simules, le procédé restaure la connectivité départ-arrivée manquante avec un taux de succès de 99,8%. Une validation matérielle a également été réalisée sur un bras robotique Franka a un seul bras, dans un scenario réel présentant initialement des régions de départ et d'arrivée déconnectées. Pour les intégrateurs qui déploient des bras manipulateurs en environnement encombre (entrepôts, lignes d'assemblage, cellules robotisées), ce correctif s'attaque a une limite concrète: la génération automatique de régions convexes via des outils comme IRIS laisse parfois des "trous" entre zones franchissables, ce qui bloquait jusqu'ici la planification des qu'un objectif tombait dans un ilot sépare du point de départ, obligeant a réinitialiser la carte ou a basculer vers un planificateur par échantillonnage plus lent. Un taux de succès de 99,8% en simulation, appuyé par une démonstration matérielle même limitée, indique que ce problème de connectivité peut être traite comme une étape de prétraitement automatisable plutôt que comme un échec a gérer au cas par cas, ce qui renforce la viabilité des méthodes GCS face aux planificateurs traditionnels pour des usages industriels ou fiabilité et temps de calcul comptent autant que l'optimalité de la trajectoire. Les méthodes GCS s'appuient généralement sur des algorithmes de décomposition convexe comme IRIS (Iterative Regional Inflation by Semidefinite programming) pour construire automatiquement la carte de régions a partir de l'espace de configuration d'un robot, une famille d'outils que les auteurs utilisent justement comme référence dans leurs tests. Le travail s'inscrit dans un effort plus large pour rendre l'optimisation de trajectoire par ensembles convexes exploitable en conditions réelles, au-delà des démonstrations en environnement simple et entièrement connecte. Un site de projet dédié (zhouxk1997.github.io/GCS_Bridging) présente les résultats. La suite logique, non détaillée dans le résume, consisterait a étendre la validation matérielle a des bras multiples ou des scenarios avec davantage d'obstacles dynamiques, pour vérifier que le taux de succès observe en simulation se maintient quand la complexité de l'environnement augmente.

UEImpact indirect: le bras robotique Franka utilise pour la validation matérielle est produit par une entreprise allemande, mais aucun acteur français ou européen n'est directement implique dans cette recherche.

RecherchePaper

1 source

3arXiv cs.RO

Planification cinodynamique par échantillonnage avec des modèles du monde

Des chercheurs proposent d'abandonner les optimiseurs habituels (CEM, MPPI) au profit d'une planification de mouvement par échantillonnage cinématique et dynamique appliquée aux modèles du monde visuels. Leur méthode utilise le modèle appris comme propagateur d'un arbre de recherche dans l'espace latent. Deux stratégies d'exploration y sont déclinées : un RRT guidé par plus proches voisins et un KPIECE fondé sur des projections. L'expansion de l'arbre est calculée par lots, nativement sur GPU, pour bien exploiter le matériel. L'évaluation s'appuie sur un DINO-WM standard, sans réentraînement spécifique, testé sur quatre domaines simulés et sur une tâche réelle de poussée de bloc avec un robot. En simulation, les deux approches égalent ou dépassent le taux de succès de CEM et MPPI, avec un temps de planification jusqu'à 13,8 fois inférieur. Sur le robot réel, le taux de succès gagne 20 %. Le papier ne détaille pas, dans son résumé, l'ampleur absolue des taux de succès ni la taille des échantillons de test. L'enjeu dépasse l'optimisation de vitesse. Les modèles du monde visuels prédisent les conséquences d'actions à partir d'images, mais les optimiseurs qui les pilotent sont myopes : ils échouent dès que la progression exige un mouvement que la fonction objectif ne récompense pas, comme contourner un bloc avant de le pousser. Les auteurs montrent que les stratégies d'échantillonnage conçues pour la recherche en haute dimension dans l'espace de configuration se transposent directement à l'espace latent. L'arbre traverse ainsi des états intermédiaires que CEM et MPPI ne tirent jamais. Pour les intégrateurs et les équipes qui visent des tâches de manipulation à horizon long, le message est que le goulot d'étranglement tient autant à l'algorithme de planification qu'à la qualité du modèle du monde. Il faut toutefois rester prudent : quatre environnements simulés et une seule tâche réelle, très proche de la simulation, ne disent rien de la robustesse sur des scènes industrielles encombrées, déformables ou à contacts riches. Le gain de 20 % sur robot réel reste modeste et son intervalle de confiance n'est pas indiqué. Ce travail s'inscrit dans la montée des modèles du monde latents, dont DINO-WM, qui s'appuie sur des représentations visuelles DINO pré-entraînées pour prédire l'évolution des scènes sans reconstruction de pixels. La planification par échantillonnage de trajectoires (CEM, MPPI) est devenue la norme dans ce cadre, au prix des limites décrites plus haut. Les auteurs ramènent à ce domaine un héritage de la robotique classique : RRT et KPIECE, utilisés de longue date dans les planificateurs de mouvement de type OMPL. Il s'agit d'une publication académique (arXiv, version 1, octobre 2026), sans produit ni déploiement annoncé. Les suites naturelles sont des tests sur des tâches plus longues et plus variées, sur d'autres modèles du monde, et une comparaison avec les approches de politiques VLA apprises de bout en bout, qui évitent la planification explicite.

UEPas d\'impact direct sur la France/UE

RecherchePaper

1 source

4arXiv cs.RO

Accélérer la planification de mouvement discrète-continue via des graphes neuronaux d'ensembles convexes

Des chercheurs ont publié en août 2026 sur arXiv (2608.15440) une méthode qui accélère la planification de mouvement combinant décisions discrètes et trajectoires continues, un problème central en navigation sans collision et en manipulation avec contacts. Le travail s'appuie sur le cadre Graphs of Convex Sets (GCS), où les décisions discrètes forment les nœuds d'un graphe et les trajectoires continues ses arêtes, mais remplace la coûteuse relaxation convexe du GCS classique par un passage unique dans un Graph Attention Network qui propose des chemins candidats, triés ensuite par un réseau léger jusqu'à un plan quasi optimal. Testée sur un quadrirotor 3D, un bras à 7 degrés de liberté et une tâche de poussée planaire avec contacts, elle atteint jusqu'à 100 fois la vitesse du GCS classique avec 100% de réussite, au prix d'une légère perte d'optimalité. Code et vidéos sont disponibles sur neural-gcs.github.io. Pour l'industrie robotique, ce résultat s'attaque à un verrou concret : les planificateurs GCS approchent l'optimum global même sur des problèmes non convexes, mais leur coût de calcul limitait leur usage à la planification hors ligne ou à des scènes simples. Diviser ce temps par un facteur proche de 100 rend envisageable le replanning embarqué, utile pour les bras en usine, les drones en environnement encombré et la manipulation avec contact comme le poussage d'objets en logistique. Cela illustre une tendance du secteur : coupler apprentissage et solveurs d'optimisation classiques plutôt que de tout confier à un modèle appris de bout en bout comme les architectures vision-langage-action. Le compromis vitesse contre optimalité de ce travail académique, validé seulement en simulation, reste à confirmer sur du matériel réel. Le cadre GCS n'est pas nouveau : introduit par des chercheurs du MIT et de Toyota Research Institute, il unifie planification discrète et continue en alternative aux méthodes d'échantillonnage type RRT et aux solveurs de programmation en nombres entiers mixtes. Son coût de calcul a motivé plusieurs travaux d'accélération, dont celui-ci, aux côtés d'approches qui utilisent l'apprentissage pour guider des planificateurs par échantillonnage. Aucune entreprise n'est associée à cette publication : code et vidéos sont ouverts pour reproduction indépendante, et les prochaines étapes attendues portent sur une validation sur matériel réel et une intégration dans des piles logicielles utilisées par des intégrateurs industriels.

RecherchePaper

1 source