RecherchearXiv cs.RO 12 mai 2026

Planification efficace du mouvement multi-robots avec des faisceaux d'arêtes invariants par translation précalculés

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Une équipe de chercheurs présente KiTE-Extend (Kinodynamic Translation-Invariant Edge Bundles), un mécanisme de sélection d'actions conçu pour améliorer la planification de mouvement multi-robot (MRMP). Publié sur arXiv (2605.09801) en mai 2026, le système repose sur une bibliothèque de segments de trajectoire calculés hors ligne, qui guident ensuite la sélection d'actions lors de la planification en ligne. L'approche est dite "planner-agnostic" : elle s'intègre aux planificateurs existants sans modifier leur propagation d'état, leur vérification de collision, ni leur évaluation de coût, et sans altérer leurs garanties théoriques. Les expériences couvrent plusieurs systèmes kinodynamiques et environnements variés, et montrent des réductions significatives du temps de planification ainsi qu'une meilleure scalabilité sur les trois paradigmes MRMP les plus utilisés : centralisé, priorisé, et basé sur la résolution de conflits (conflict-based search).

L'enjeu est concret pour les intégrateurs de cellules robotisées et les opérateurs de flottes autonomes : coordonner plusieurs robots dans des espaces contraints reste l'un des principaux goulets d'étranglement des déploiements en entrepôt, en usine ou en logistique hospitalière. Les approches d'échantillonnage cinodynamique souffrent classiquement d'une exploration inefficace dans des espaces de configuration denses, où les interactions robot-robot multiplient les contraintes spatio-temporelles. KiTE-Extend attaque ce problème en amont en précalculant des segments réutilisables invariants par translation, ce qui permet à l'algorithme de trouver plus rapidement des segments de mouvement faisables sans surcharge computationnelle en ligne. Le gain est modeste pour un agent seul, mais significatif en configuration multi-agents, là précisément où les planificateurs standards peinent le plus.

La planification cinodynamique multi-robot est un problème réputé PSPACE-difficile, et les méthodes par échantillonnage comme RRT ou SST ont longtemps dominé l'état de l'art sans résoudre complètement le passage à l'échelle au-delà de quelques agents. Des travaux comme CBS (Conflict-Based Search) ou ECBS avaient amélioré la gestion des conflits, mais laissaient entière la question de la qualité des primitives d'action sous-jacentes. KiTE-Extend s'insère en amont du planificateur plutôt qu'en remplacement, ce qui le rend compatible avec l'ensemble de l'écosystème existant. Aucun partenaire industriel ni calendrier de déploiement terrain n'est mentionné : il s'agit à ce stade d'une contribution de recherche, sans validation industrielle annoncée.

Dans nos dossiers

arXiv cs.RO

À lire aussi

1arXiv cs.RO

P-ARC : planification parallèle de mouvement multi-robot par exploitation de l'indépendance des sous-problèmes

Une équipe de chercheurs propose sur arXiv (2606.27625) P-ARC, variante parallélisée de l'algorithme ARC (Adaptive Robot Coordination) pour la planification de mouvement multi-robots (MRMP). ARC décompose le problème en trois étapes séquentielles: calcul des solutions individuelles initiales, détection des conflits entre trajectoires, puis résolution de ces conflits. P-ARC parallélise chacune de ces étapes en exploitant l'indépendance structurelle que la décomposition crée entre sous-problèmes, et les auteurs introduisent OR-P-ARC, une variante hybride ajoutant une stratégie multi-départ OR-parallèle. Les benchmarks couvrent des scénarios 2D avec jusqu'à 128 robots mobiles et manipulateurs planaires, ainsi que des équipes de manipulateurs Panda en configurations inspirées de l'industrie. Sur 16 cœurs CPU, le gain de temps de planification approche un facteur 4x par rapport à la version séquentielle d'ARC. Ce résultat intéresse directement les intégrateurs de cellules multi-bras et les opérateurs d'entrepôts automatisés, où la re-planification en temps réel reste un goulot d'étranglement opérationnel. Recalculer des trajectoires sans collision pour une dizaine de manipulateurs en réponse à une perturbation, qu'il s'agisse d'une pièce mal positionnée ou d'un ajout de robot, prend plusieurs secondes avec les approches séquentielles, ce qui bride la cadence de production. Un facteur 4x rendrait la re-planification à la volée plus viable dans des environnements dynamiques. Il convient néanmoins de nuancer: les expériences sont menées dans des scénarios qualifiés d'"inspirés du monde réel" et non sur des déploiements opérationnels réels, et l'écart simulation-terrain reste non quantifié à ce stade. Le MRMP est un problème réputé PSPACE-complet dans sa forme générale, ce qui explique l'intérêt persistant pour les approches de décomposition depuis deux décennies. ARC s'inscrit dans un paysage d'algorithmes incluant CBS (Conflict-Based Search) et ses variantes ECBS et EECBS, utilisées dans des systèmes logistiques commerciaux, ainsi que des solveurs MAPF tels que PBS ou ICTS. La parallélisation de ces algorithmes constitue un axe de recherche actif, avec des travaux récents sur PBS parallèle et des implémentations GPU pour les méthodes de champs de potentiel. P-ARC se distingue en exploitant la structure interne propre à ARC pour paralléliser chaque étape individuellement, plutôt que d'appliquer un parallélisme global à la recherche. Aucun partenariat industriel ni dépôt de code open-source n'est mentionné dans la publication: il s'agit d'une prépublication académique sans calendrier de déploiement annoncé.

RecherchePaper

1 source

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

3arXiv cs.RO

Planification de mouvement multi-robots décentralisée par diffusion informée par simulation

Des chercheurs présentent SID (Simulation-Informed Diffusion), un cadre décentralisé de planification de mouvement pour flottes multi-robots, publié sur arXiv (2605.27697) en mai 2026. Le problème ciblé est fondamental en robotique mobile collaborative : chaque robot doit générer des trajectoires sans collision à partir de ses seules observations locales, sans capteur global ni communication fiable. L'approche repose sur des modèles de diffusion sensibles aux contraintes (CADM, Constraint-Aware Diffusion Models) : dans une première passe, CADM simule les trajectoires futures des robots voisins à partir de leurs états observés ; dans une seconde passe, le même modèle planifie la trajectoire propre de chaque robot sous contraintes de sécurité issues de ces simulations. Un mécanisme de communication minimaliste complète le dispositif, ne déclenchant la coordination qu'en zones de forte congestion. Les expériences montrent que SID surpasse les méthodes de référence en termes d'efficacité de planification et de respect des contraintes, et passe à l'échelle jusqu'à 108 robots simultanés évoluant parmi 160 obstacles. La limite adressée est bien documentée dans les systèmes AMR industriels : planificateurs classiques (RVO, ORCA) et approches d'apprentissage raisonnent tous sur un instantané statique de l'environnement, ce qui devient un goulot d'étranglement au-delà d'une vingtaine d'agents en densité élevée. L'apport de SID est de traiter prédiction des voisins et planification propre comme un problème unifié, résolu par le même modèle de diffusion, évitant ainsi la propagation d'erreurs entre modules séparés. La communication conditionnelle représente également un avantage pratique pour les déploiements sur réseaux contraints, un point d'intérêt direct pour les intégrateurs logistiques opérant des flottes AMR à grande échelle. Les modèles de diffusion appliqués à la robotique connaissent un essor marqué depuis 2024, avec des travaux comme Pi-0 (Physical Intelligence) ou GR00T N2 (NVIDIA) ayant démontré leur efficacité pour la manipulation. SID s'inscrit dans cette tendance mais cible la coordination décentralisée, angle moins couvert que la manipulation. La compétition directe inclut les approches MARL (multi-agent reinforcement learning) et les planificateurs hybrides comme PRIMAL ou DHC. À ce stade, SID reste une preuve de concept en simulation ; aucun déploiement sur hardware physique n'est annoncé. La prochaine étape naturelle serait une validation sur AMR réels en conditions d'entrepôt, qui constituerait le vrai test du sim-to-real gap encore ouvert pour ce type d'approche générative.

RecherchePaper

1 source

4arXiv cs.RO

Planification de mouvement multi-robots à grande échelle par décomposition hiérarchique de l'espace de travail

Une équipe de chercheurs a déposé en mai 2026 sur arXiv (réf. 2605.20395) une méthode de planification de mouvement pour flottes de robots mobiles qui revendique un gain de temps de calcul allant jusqu'à un ordre de grandeur par rapport aux solveurs existants. Le goulot central du domaine, l'explosion combinatoire de l'espace de configuration joint dont la dimension croît exponentiellement avec le nombre de robots N, est contourné par une recherche discrète dans une décomposition de l'espace de travail (workspace decomposition). Contrairement aux approches antérieures qui fusionnent les robots dans cet espace joint dès la détection d'un conflit, la méthode affine itérativement cette décomposition pour ne résoudre que des sous-problèmes à espaces de configuration découplés et de taille réduite, d'où le terme de hierarchical subproblem expansion dans l'intitulé. Pour les intégrateurs de systèmes multi-robots en entrepôt ou en usine, une latence de planification divisée par 10 ouvre concrètement la porte à une replanification quasi-temps-réel sur des flottes de plusieurs dizaines de robots, un seuil difficile à franchir aujourd'hui avec les solveurs MAPF (multi-agent pathfinding) classiques tels que CBS (Conflict-Based Search) et ses variantes ECBS ou BCBS. L'approche par décomposition itérative de l'espace de travail suggère également une meilleure adaptabilité aux environnements dynamiques, où obstacles ou priorités de mission changent en cours d'exécution. Prudence cependant : il s'agit d'un preprint non encore évalué par les pairs, et l'abstract disponible ne détaille pas les conditions expérimentales précises, notamment la densité de robots testée, la topologie des environnements ou les horizons de planification retenus. La planification multi-robots est un champ structuré depuis deux décennies autour de deux familles antagonistes : méthodes couplées, qui garantissent l'optimalité mais à coût prohibitif, et méthodes découplées, rapides mais sous-optimales. CBS et ses dérivés constituent aujourd'hui la référence académique dominante. Dans l'industrie, des acteurs comme Exotec (Croix, Nord, déployé dans plus de 10 pays avec plus de 600 clients) ou Locus Robotics ont intégré des planificateurs propriétaires à leurs flottes AMR. Ce travail ne mentionne ni partenariat industriel ni calendrier de transfert technologique ; la prochaine étape naturelle serait une validation sur plateforme réelle ou dans un simulateur de référence tel qu'Isaac Sim ou MoveIt 2.

UEDes acteurs français comme Exotec, dont les flottes AMR sont déployées dans plus de 10 pays, pourraient bénéficier d'une replanification quasi-temps-réel si cette méthode est validée et transférée en production.

RecherchePaper

1 source