RecherchearXiv cs.RO 28 septembre 2026

MR. POP : planificateur parallèle d'optimisation multi-robots, presque sûrement asymptotiquement optimal

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Un article publié sur arXiv (arXiv:2609.30644v1) présente MR. POP (Multi-Robot Parallel Optimizing Planner), un planificateur de trajectoires pour systèmes multi-robots qui s'exécute sur GPU plutôt que sur CPU. L'algorithme combine dRRT (une variante discrète de Rapidly-exploring Random Trees) et le méta-algorithme AO-x, et exploite le parallélisme SIMT des GPU pour lancer simultanément des centaines d'itérations de construction de feuille de route et de recherche arborescente, avec des opérations de recherche de plus proches voisins et de détection de collision elles aussi parallélisées. Les auteurs rapportent que MR. POP est le seul planificateur testé à atteindre un taux de résolution de 100% tout en étant plus rapide que les meilleurs planificateurs dits "presque sûrement asymptotiquement optimaux" (a.s.a.o.) existants, sur des systèmes multi-robots allant jusqu'à 35 degrés de liberté combinés. L'algorithme améliore aussi fortement les optimiseurs de mouvement placés en aval de la chaîne de planification, en faisant grimper leur taux de succès de 4% à 72% grâce à des trajectoires de départ ("seeds") plus nombreuses et plus diverses, ce qui limite les blocages dans des minima locaux.

Ce résultat s'adresse directement aux intégrateurs manipulant plusieurs bras robotiques ou robots mobiles autonomes (AMR) dans un espace de travail partagé, un scénario courant en logistique et en usine où la coordination sans collision devient combinatoirement difficile dès que le nombre de robots et leurs degrés de liberté augmentent. Jusqu'ici, la parallélisation CPU des planificateurs a.s.a.o. permettait de conserver les garanties de convergence probabiliste sans pour autant passer à l'échelle sur des flottes multi-robots complexes. En déplaçant le calcul intensif vers le GPU, ce travail suggère qu'un goulot d'étranglement connu du secteur, à savoir la difficulté de planifier des mouvements optimaux et garantis pour de nombreux robots à haut DOF en temps raisonnable, peut être en partie levé, et que la qualité des solutions initiales fournies aux optimiseurs de mouvement compte autant que la puissance de calcul brute.

MR. POP s'inscrit dans la lignée des planificateurs a.s.a.o. de type RRT/PRM, dont dRRT est l'adaptation aux problèmes multi-robots, et du méta-algorithme AO-x conçu pour raffiner une solution de façon anytime jusqu'à l'optimalité. Le texte, publié sous forme de prépublication arXiv sans affiliation ni date de conférence précisée dans le résumé, reste à ce stade une contribution de recherche et non un produit ou un service commercialisé: aucune intégration industrielle, aucun partenariat ni calendrier de déploiement n'est mentionné. La suite logique pour ce type de travaux est généralement une intégration dans des bibliothèques de planification de mouvement existantes puis une validation sur des plateformes robotiques réelles, étapes qui restent à documenter par les auteurs.

Dans nos dossiers

arXiv cs.RO

À lire aussi

1arXiv cs.RO

AO-ARC : planification de mouvement multi-robots presque sûrement asymptotiquement optimale avec ARC

Une équipe de recherche a publié sur arXiv (référence 2606.27495) AO-ARC, un algorithme de planification de mouvement multi-robots (MRMP) dit "anytime", c'est-à-dire capable de fournir une première solution valide immédiatement, puis de l'améliorer de façon continue sans délai fixé. L'algorithme combine le meta-algorithme AO-x, qui convertit des solveurs de faisabilité en algorithmes anytime, avec la méthode ARC (Adaptive Robot Coordination) appliquée itérativement sur des instances MRMP bornées, sous une métrique de makespan, le temps nécessaire à l'ensemble des robots pour atteindre leurs cibles. Les auteurs affirment que AO-ARC atteint des temps de première solution comparables aux solveurs de faisabilité de l'état de l'art, tout en convergeant plus rapidement et plus régulièrement que les méthodes anytime existantes à mesure que le nombre de robots augmente, avec une preuve formelle d'optimalité asymptotique. L'évaluation porte sur des scénarios 2D à différents niveaux de complexité de coordination et sur un scénario 3D avec bras manipulateurs, représentatif d'applications industrielles réelles. L'enjeu pratique est significatif : la planification multi-robots est NP-difficile en général, et le passage à l'échelle (10, 50, 100 robots) reste le talon d'Achille des méthodes existantes, notamment dans les entrepôts automatisés ou les cellules robotiques denses. La propriété anytime est particulièrement critique en déploiement réel, où un système ne peut pas attendre une solution optimale avant d'agir. La métrique makespan, en optimisant le temps de fin de la tâche collective plutôt que la somme des distances individuelles, est directement corrélée au débit industriel. Le mécanisme de couplage adaptatif d'ARC, choisir dynamiquement quand planifier des robots conjointement ou indépendamment, est préservé tout en maintenant une borne de coût cohérente sur les décompositions, ce qui est la difficulté théorique centrale que ce travail prétend résoudre. ARC, le solveur sous-jacent, avait déjà démontré des performances compétitives sur des benchmarks MRMP en exploitant ce couplage sélectif. AO-ARC s'inscrit dans une lignée de recherches visant à combiner garanties théoriques et efficacité pratique, face à des méthodes concurrentes comme CBS (Conflict-Based Search), ECBS ou les variantes de dRRT*, qui peinent à combiner rapidité de première solution et qualité asymptotique à grande échelle. Ce travail reste un preprint arXiv non encore évalué par les pairs, sans déploiement annoncé ni partenaire industriel mentionné, les benchmarks utilisés, bien que représentatifs, ne constituent pas une validation terrain.

RecherchePaper

1 source

2arXiv cs.RO

Planification multirobot des tâches et mouvements, asymptotiquement optimale

Des chercheurs publient sur arXiv (identifiant 2609.18813v1, soumission de type "new", datée de septembre 2026) un nouvel algorithme de planification conjointe tâche-mouvement pour systèmes multi-robots, appelé MR-TAMP dans le papier. Le problème visé : quand plusieurs robots interagissent, chaque transition de tâche peut mobiliser un sous-ensemble différent de robots, ce qui change la dimension des contraintes appliquées à l'espace de configuration global. Les auteurs formalisent cette structure de transitions et posent des conditions suffisantes pour garantir une optimalité asymptotique globale, à savoir une couverture persistante des transitions pertinentes combinée à une amélioration continue de la planification de mouvement dans les régions faisables connectées. Concrètement, leur planificateur combine des cartes de chemins (roadmaps) individuelles par robot, mises à jour de façon incrémentale, avec une recherche implicite en produit tensoriel, ce qui évite de devoir construire explicitement la roadmap composite de l'ensemble des robots, opération normalement coûteuse. Pour rester efficace en temps fini, le système ajoute un échantillonnage conditionnel des transitions, une vérification paresseuse des collisions, et un guidage à la fois au niveau des modes de tâche et des solutions candidates. Pour l'industrie robotique, cette contribution s'adresse directement aux intégrateurs qui déploient des flottes de bras manipulateurs ou de robots coopératifs sur une même cellule de production ou d'entrepôt, où la coordination combinatoire entre tâches discrètes (qui fait quoi, dans quel ordre) et mouvements continus sans collision reste un verrou classique. Les algorithmes à garanties d'optimalité asymptotique existaient déjà pour un seul robot ; l'étendre au multi-robot sans exploser le coût de calcul est ce qui manquait pour des applications réelles à plusieurs bras synchronisés. Il s'agit toutefois d'une contribution théorique et algorithmique publiée en prépublication arXiv, sans validation industrielle ni chiffres de déploiement, de payload ou de temps de cycle : c'est un travail de recherche fondamentale, pas un produit ni une démonstration commerciale. Ce travail s'inscrit dans la lignée des planificateurs tâche-mouvement (TAMP) à garanties asymptotiques développés pour la robotique mono-robot, en cherchant à combler l'écart avec les approches multi-robots existantes, généralement basées sur une planification découplée ou priorisée sans garantie d'optimalité globale. Les suites logiques attendues sont une validation expérimentale plus poussée, une comparaison chiffrée face aux méthodes concurrentes, puis une possible soumission à une conférence de robotique comme ICRA ou IROS, étapes non encore mentionnées dans ce dépôt initial.

RecherchePaper

1 source

3arXiv cs.RO

Modélisation par diffusion optimale pour la planification de mouvement multi-robots

Des chercheurs présentent MDOC (Model-Based Diffusion Optimal Control), un planificateur de trajectoires pour flottes multi-robots fondé sur la diffusion, décrit dans un preprint publié sur arXiv (2607.12423). Contrairement aux approches récentes qui traitent la planification de trajectoires comme un problème d'inférence probabiliste et apprennent leurs fonctions de score à partir de larges jeux de données de démonstration, MDOC s'appuie directement sur des modèles de dynamique connus, sans données d'entraînement. Sa mécanique de sécurité combine ces modèles avec des projections contraintes par des Control Barrier Functions (CBF), et le système passe à l'échelle multi-robots grâce à la méthode de Conflict-Based Search (CBS), qui résout les conflits de trajectoires entre agents de façon hiérarchique. Les auteurs rapportent, en simulation, de meilleures performances que des planificateurs de référence en termes d'efficacité d'échantillonnage, de fluidité géométrique des trajectoires et de taux de réussite, tout en réduisant le temps de calcul et en garantissant des trajectoires sans collision. L'enjeu dépasse l'exercice académique : la planification de mouvement multi-robots en environnement continu se heurte à une explosion combinatoire de l'espace des trajectoires conjointes, et les méthodes par diffusion existantes peinent à garantir rigoureusement la faisabilité dynamique et les contraintes de sécurité strictes lors de l'échantillonnage. En s'affranchissant de la dépendance aux données de démonstration tout en conservant des garanties formelles de sécurité, MDOC répond à un frein réel à l'adoption industrielle de ces techniques pour des flottes d'AMR ou de robots collaboratifs, où l'absence de collision n'est pas négociable. Le travail s'inscrit dans la lignée des approches récentes qui recadrent la planification de trajectoires comme un problème d'inférence par diffusion, en s'en distinguant par son caractère "model-based" plutôt que piloté par les données. Il se positionne aussi comme une alternative aux méthodes classiques d'optimisation de trajectoire et de recherche multi-agents. À ce stade, les résultats restent limités à des expériences en simulation ; aucun déploiement sur robots physiques n'est mentionné, ce qui en fait une contribution méthodologique à confirmer avant tout usage en conditions réelles.

RecherchePaper

1 source

4arXiv cs.RO

Kino-PAX+ : un planificateur de mouvement kinodynamique massivement parallèle quasi optimal

Une équipe de chercheurs en robotique a publié la version 2 d'un article sur arXiv (2602.02846) décrivant Kino-PAX+, un planificateur de mouvement par échantillonnage (SBMP, sampling-based motion planner) pour robots soumis à des contraintes kinodynamiques dans des espaces de haute dimension, comme des bras manipulateurs ou véhicules dont la trajectoire doit respecter vitesse et accélération. L'algorithme découpe les opérations habituellement séquentielles en trois sous-routines massivement parallèles, construit un arbre épars de trajectoires dynamiquement réalisables et concentre le calcul sur les nœuds les plus prometteurs de chaque voisinage pour améliorer rapidement le coût de la solution. Les auteurs rapportent des résolutions jusqu'à trois ordres de grandeur, soit environ mille fois plus rapides que les méthodes sérielles existantes, avec des coûts de trajectoire plus faibles, et apportent une preuve formelle de quasi-optimalité asymptotique dite delta-robuste. L'apport tient moins à la vitesse brute qu'à la garantie qui l'accompagne : les précédentes tentatives de parallélisation des SBMP accéléraient la recherche d'une solution faisable mais sans assurance sur sa qualité, forçant les intégrateurs à arbitrer entre rapidité et optimalité. Pour les fabricants de bras robotiques, de robots mobiles ou de plateformes humanoïdes évoluant en environnement dynamique, disposer d'un planificateur à la fois rapide et quasi optimal réduit ce compromis et rapproche la replanification kinodynamique temps réel d'un usage industriel. Le résultat confirme aussi une tendance de fond du secteur : déporter le calcul de planification vers des architectures massivement parallèles plutôt que d'optimiser des algorithmes purement séquentiels, dans la lignée d'efforts comme cuRobo de Nvidia. Kino-PAX+ prolonge une lignée de recherche en planification par échantillonnage remontant aux familles RRT et RRT*, dont les variantes kinodynamiques peinaient historiquement à passer à l'échelle sur des systèmes à nombreux degrés de liberté ; son nom suggère qu'il s'appuie sur un planificateur antérieur, Kino-PAX, focalisé sur la seule faisabilité. Il s'agit à ce stade d'un travail académique déposé sur arXiv, non encore validé par relecture par les pairs ni intégré dans un produit commercial : aucun déploiement sur robot physique ni partenariat industriel n'est mentionné. Les suites attendues sont une publication en conférence ou en revue et des essais comparatifs sur des plateformes robotiques réelles.

RecherchePaper

1 source