RecherchearXiv cs.RO 13 août 2026

Vers une relaxation convexe plus fine des programmes mixtes en nombres entiers : le flux de réseau logique pour la planification tâche-mouvement

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Des chercheurs en robotique ont mis à jour sur arXiv (2509.24235) "Logic Network Flow", un framework de planification de tâches et de mouvements (task and motion planning, TAMP) fondé sur l'optimisation, qui intègre la logique temporelle dans des programmes en nombres mixtes. Inspirée de la formulation Graph-of-Convex-Sets, la méthode encode les contraintes temporelles comme des contraintes polyédriques sur les arêtes d'un modèle de flux réseau, plutôt qu'entre les nœuds comme dans les formulations classiques dites Logic Tree, et ajoute une élimination de Fourier-Motzkin qui supprime les variables continues sans perdre en finesse de relaxation convexe. Sur des tests de routage de véhicules, de coordination multi-robots et de contrôle de systèmes dynamiques (modèles point-mass et pendule inversé linéaire), elle affiche des accélérations de calcul allant jusqu'à plusieurs ordres de grandeur et une consommation mémoire réduite. Une démonstration matérielle sur robots quadrupèdes valide une capacité de replanification en temps réel face à des conditions environnementales changeantes, avec code et détails disponibles sur logicnetworkflow.github.io.

Ce travail cible un goulot d'étranglement connu du secteur robotique: la planification combinée tâches-mouvements sous contraintes temporelles devient vite trop lente pour du temps réel dès que le nombre de variables entières croît, ce qui limite le déploiement de robots mobiles ou à pattes dans des environnements changeants. Des relaxations convexes plus serrées et moins de contraintes réduisent directement le coût de résolution des solveurs en nombres mixtes, un frein majeur à la mise à l'échelle des méthodes de planification formelle face aux approches data-driven de type VLA. Les gains annoncés, jusqu'à plusieurs ordres de grandeur en vitesse, restent toutefois issus de benchmarks contrôlés, avec une validation matérielle limitée à des quadrupèdes en conditions de laboratoire plutôt qu'à un déploiement industriel à grande échelle.

La méthode prolonge les travaux sur Graph-of-Convex-Sets, une formulation d'optimisation convexe pour la planification de trajectoires devenue courante en robotique ces dernières années, en l'étendant à la logique temporelle. Elle se positionne face aux formulations Logic Tree traditionnelles du TAMP et aux méthodes de synthèse de contrôleurs par logique temporelle signal (STL), couramment employées en robotique formelle. Publiée en version 2 sur arXiv sans partenariat industriel ni feuille de route commerciale annoncée, cette contribution reste académique, avec code et démonstrations mis à disposition sur le site du projet pour en faciliter la reproductibilité.

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

Relaxations semi-définies pour la planification de mouvement sans collision

Une équipe de chercheurs a soumis sur arXiv (identifiant 2606.14063) une analyse théorique des relaxations semi-définies (SDP) appliquées à la planification de trajectoires sans collision. Le problème étudié est volontairement élémentaire : un robot ponctuel doit rejoindre une cible en évitant des obstacles sphériques dans R^n, sous contraintes de continuité de trajectoire et avec un coût sur les dérivées au carré. Ce problème est d'abord formulé exactement comme un problème non-convexe sur des courbes polynomiales, puis une relaxation semi-définie naturelle est construite. Les benchmarks montrent un gain de vitesse de 10 à 100 fois par rapport aux solveurs de programmation non-linéaire directs SNOPT et IPOPT, avec une variance des temps de résolution nettement plus faible. La méthode est validée comme fonction de pilotage convexe dans un planificateur RRT pour des trajectoires quadrirotor à snap minimal avec continuité C^4 (jusqu'à la 4e dérivée). Les deux contributions théoriques constituent, selon les auteurs, la première analyse formelle des SDP pour ce problème. La première établit que résoudre la relaxation convexe revient à résoudre globalement un problème de planification connexe dans un espace de dimension potentiellement supérieure, ce qui donne des conditions nécessaires et suffisantes de tightness ainsi qu'une intuition géométrique claire des cas où la relaxation est lâche. La seconde identifie une réduction de symétrie décisive : les tailles des cônes semi-définis positifs (PSD) évoluent linéairement avec le degré polynomial et sont indépendantes de la dimension ambiante, évitant ainsi l'explosion combinatoire typique des méthodes NLP en haute dimension. La planification sans collision reste un verrou fondamental de la robotique, où les solveurs NLP classiques souffrent de sensibilité aux initialisations et de convergence vers des minima locaux sous-optimaux. Des frameworks comme Drake (groupe Tedrake, MIT CSAIL) utilisent déjà des relaxations convexes de type GCS ou DSOS, mais sans les garanties théoriques que ce travail commence à formaliser. L'extension aux obstacles non-sphériques et aux robots articulés à degrés de liberté multiples reste entière, deux généralisations indispensables avant tout déploiement industriel. Des applications en navigation de drones en intérieur ou en planification de mouvement pour bras manipulateurs constituent les prochaines étapes logiques.

RecherchePaper

1 source

3arXiv cs.RO

Planification par réseau de neurones en graphe et contrôle prédictif pour la planification de mouvement multi-robots sans étiquettes sous contraintes de communication

Une équipe de chercheurs propose, dans un preprint déposé sur arXiv le 25 mai 2026 (arXiv:2605.19209), un framework hiérarchique pour résoudre le problème de planification de mouvement multi-robots sans étiquetage, c'est-à-dire l'assignation simultanée de robots à des objectifs et la génération de trajectoires sûres dans des environnements partagés. Le système combine deux composants : un Graph ATtention Planner (GATP), fondé sur des réseaux de neurones à graphes avec mécanisme d'attention, qui génère des sous-objectifs intermédiaires par coopération entre agents, et un contrôleur NMPC (Nonlinear Model Predictive Controller) décentralisé, exécuté en embarqué sur chaque robot, qui garantit la faisabilité des trajectoires sous dynamiques non-linéaires et contraintes d'actuation réelles. Le framework a été évalué à la fois en simulation et sur des quadrotors physiques. Les auteurs rapportent une tolérance aux délais de communication allant jusqu'à 200 ms, une inférence entièrement décentralisée à bord, et une meilleure généralisation à des équipes de taille croissante. Ce travail s'attaque directement au gouffre sim-to-real qui mine la plupart des approches GNN appliquées à la robotique multi-agents : les méthodes existantes supposent des dynamiques simplifiées et un environnement de simulation idéalisé, ce qui les rend fragiles en conditions réelles. En couplant un planificateur neuronal décentralisé à un contrôleur à modèle prédictif, le framework maintient les propriétés de scalabilité des GNN tout en imposant des garanties de sécurité physiques que les approches purement apprises ne fournissent pas. La robustesse aux délais de communication est particulièrement significative pour les déploiements en entrepôts ou en milieu industriel, où les réseaux sans fil ne sont jamais idéaux. Cette contribution s'inscrit dans un corpus actif de recherche sur les GNN pour la coordination multi-robots, aux côtés de travaux comme MAGAT ou DAN, qui visent à remplacer les solveurs centralisés classiques (MILP, CBS) par des approches distribuées passant à l'échelle. Le preprint n'est pas encore soumis à une revue avec comité de lecture, et aucun déploiement industriel ni partenariat n'est annoncé : il s'agit d'une validation expérimentale académique sur quadrotors, prometteuse mais à consolider. Les prochaines étapes naturelles seraient des expériences sur flottes plus larges et des robots à dynamiques plus complexes, comme des manipulateurs mobiles ou des AMR en environnement entrepôt.

RecherchePaper

1 source

4arXiv cs.RO

Arbres de fibration : une approche unifiée pour la planification de mouvement multi-robots

Une équipe de chercheurs a publié le 11 juin 2026 sur arXiv (2606.12070) un framework mathématique baptisé "fibration trees" visant à unifier les méthodes de planification de mouvement pour des équipes de robots multiples. Le système repose sur une structure en arbre où chaque noeud représente un espace d'états et chaque arête une fibration, c'est-à-dire une projection d'un espace de haute dimension vers un espace simplifié de dimension inférieure. Sur cette base formelle, les chercheurs ont développé un planificateur d'échantillonnage appelé Fibration-RRT (Rapidly-Exploring Random Fibration Trees), validé sur 32 scénarios impliquant des équipes de robots atteignant jusqu'à 96 degrés de liberté (DOF). L'implémentation est publiée en open source, et le planificateur est prouvé probabilistiquement complet. L'enjeu est la fameuse "malédiction de la dimensionnalité" : dès que l'on coordonne plusieurs robots, l'espace de configuration combiné explose exponentiellement, rendant la planification classique intractable. Les approches existantes répondaient à ce problème soit par la priorisation séquentielle (planifier les robots un par un), soit par la décomposition parallèle (sous-espaces indépendants), soit par des projections dans l'espace des tâches, mais sans framework commun capable de combiner ces stratégies. Fibration-RRT généralise à la fois le quotient-space RRT et le discrete RRT sous un formalisme unique, ce qui permet en théorie à un intégrateur de définir sa propre structure d'arbre selon la topologie du problème plutôt que de choisir entre des outils incompatibles. La robustesse sur 96 DOF est un signal technique solide, même si l'article ne fournit pas de comparaison de temps de cycle sur des benchmarks standardisés industrie. La planification de mouvement multi-robot est un domaine mature sur le plan académique, porté depuis la fin des années 1990 par les algorithmes RRT de Steven LaValle et leurs variantes (RRT*, BiRRT, quotient-space RRT de Orthey et al.). Le besoin d'unification se fait sentir à mesure que les déploiements AMR (autonomous mobile robots) et les cellules robotisées industrielles complexifient les interdépendances entre agents. Aucun acteur industriel n'est mentionné dans ce préprint, qui reste pour l'instant une contribution théorique. Les prochaines étapes naturelles seraient une validation sur des plateformes physiques et une intégration dans des middlewares standards comme ROS 2 MoveIt, qui constitue aujourd'hui la référence dans les projets d'intégration multi-bras.

RecherchePaper

1 source