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

Quand les automates rencontrent les flux : compilation de logique temporelle pour la planification tâche-mouvement en robotique

Une équipe de recherche en robotique présente SAM-TD (Synchronous Action Monitoring with Token Destruction), une méthode de compilation permettant d'imposer des contraintes de logique temporelle linéaire sur traces finies (LTLf) dans la planification tâche-mouvement (TAMP) basée sur les flux, ou "streams". Publiée sur arXiv en aout 2026, l'approche traduit des spécifications LTLf arbitraires en automates, puis intègre des gardes d'automates régressées directement dans les schémas d'action, définis avant le début de la planification. Pendant la recherche de plan, SAM-TD met à jour de façon synchrone l'état de chaque automate et s'appuie sur un jeton de validité partagé entre tous les automates pour élaguer les branches qui violent les contraintes. Les auteurs rapportent ce qu'ils présentent comme la première démonstration de TAMP basée sur des streams sous contraintes LTL_f, testée dans trois environnements robotiques PDDLStream, et affirment que SAM-TD reste compétitif face aux méthodes de référence de compilation de contraintes temporelles sur des benchmarks PDDL discrets classiques. Le TAMP basé sur les streams combine planification symbolique discrète et génération continue de paramètres géométriques (poses, prises, trajectoires) produits à la volée pendant la recherche de solution. Jusqu'ici, ces planificateurs ne vérifiaient que l'atteignabilité d'un objectif, sans garantir de contraintes temporelles comme l'ordre d'exécution critique pour la sécurité, l'invariance ou la liveness, pourtant indispensables sur des tâches à long horizon. Le verrou technique tenait au fait que les streams génèrent un ensemble d'objets géométriques en expansion continue au fil des boucles de raffinement, incompatible avec les techniques existantes de compilation de logique temporelle conçues pour un ensemble d'objets fixe et énumérable. En levant ce verrou sans modifier le planificateur sous-jacent ni exiger d'énumération préalable des objets, SAM-TD ouvre la voie à des architectures capables de respecter des règles de sécurité formelles tout en conservant la flexibilité des générateurs continus, un enjeu direct pour les intégrateurs qui déploient des manipulateurs en environnement partagé avec des humains ou soumis à des contraintes réglementaires strictes. Le cadre PDDLStream, sur lequel s'appuie ce travail, sert de référence académique pour coupler planification classique PDDL et générateurs de paramètres continus en robotique ; les techniques antérieures de compilation de logique temporelle avaient été conçues pour ce contexte discret et supposaient un monde d'objets clos, d'où leur incompatibilité avec les streams. SAM-TD se positionne comme une extension du cadre existant plutôt que comme un nouveau planificateur, ce qui pourrait faciliter son adoption par les équipes déjà équipées d'outils PDDLStream. L'article ne mentionne ni pilote industriel ni calendrier de déploiement sur robot réel : les résultats se limitent à des environnements simulés et à des benchmarks PDDL standards, laissant ouverte la question du passage à l'échelle en conditions réelles.

RecherchePaper

1 source

2arXiv cs.RO

Utiliser le raisonnement des VLM pour contraindre la planification tâche-mouvement

Des chercheurs proposent une méthode baptisée VIZ-COAST, décrite dans une nouvelle version (v3) d'un article déposé sur arXiv (2510.25548), qui exploite des modèles vision-langage (VLM) pré-entraînés à grande échelle pour améliorer la planification de tâches et de mouvements (TAMP, Task and Motion Planning) en robotique. Le principe repose sur le raisonnement spatial de bon sens de ces VLM pour repérer, avant même de lancer la recherche de plan, les endroits où un plan de haut niveau risque de ne pas se traduire en trajectoire de mouvement continue exécutable. Les auteurs ont testé leur approche sur trois domaines TAMP jugés complexes, en extrayant des contraintes plausibles directement à partir d'images et de descriptions de domaine. Résultat annoncé : une réduction drastique des temps de planification, et dans certains cas une élimination complète des échecs de raffinement (downward refinement), avec une généralisation à un ensemble varié d'instances au sein d'un même domaine plus large. Il s'agit à ce stade d'un travail de recherche publié en prépublication, sans déploiement industriel ni produit commercialisé associé. L'enjeu touche un goulot d'étranglement classique de la planification robotique à long horizon : les plans de tâches sont construits sur une abstraction du monde pour rendre la recherche efficace, mais cette abstraction ne garantit pas qu'un plan valide au niveau symbolique puisse réellement être exécuté par un planificateur de mouvement continu. Quand ce lien (le raffinement descendant) est mauvais, des plans en apparence corrects échouent en cours d'exécution, forçant un replanification coûteuse en temps. Les méthodes existantes ne corrigent ce problème qu'après coup, une fois l'échec constaté, en gaspillant du temps de calcul sur des branches de recherche infaisables. L'apport de VIZ-COAST est de déplacer cette détection en amont, en utilisant le sens commun spatial des VLM comme filtre a priori plutôt que comme diagnostic a posteriori, ce qui rejoint une tendance plus large consistant à injecter les capacités des modèles de fondation vision-langage dans les piles de planification classiques utilisées par l'industrie robotique, notamment pour les systèmes de manipulation et de navigation à long horizon. Le contexte scientifique est celui des limites bien connues du TAMP, où l'écart entre plan symbolique et exécution physique reste un frein à l'autonomie des robots sur des tâches longues et complexes. Les travaux antérieurs cités par les auteurs se contentaient d'encoder les échecs de raffinement en contraintes correctives une fois détectés pendant la planification. VIZ-COAST s'inscrit dans la lignée des approches combinant VLM et robotique symbolique, sans toutefois préciser d'implémentation matérielle, de partenaire industriel ni de calendrier de déploiement : il s'agit pour l'instant d'une validation expérimentale sur des domaines de test, dont la prochaine étape logique serait une évaluation sur des plateformes robotiques réelles.

RecherchePaper

1 source

3arXiv 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

4arXiv 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