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

Calcul simultané avec plusieurs priorisations en planification de mouvement multi-agents

Une équipe de recherche, rattachée au Cyber-Physical Mobility Lab, propose une méthode permettant à des agents de calculer simultanément avec plusieurs priorisations dans un problème de planification de mouvement multi-agents. Le travail, publié sur arXiv en version 2 (2501.10781v2), s'inscrit dans le cadre de la planification de mouvement multi-agents (MAMP) à horizon glissant, soumise à des contraintes de temps de calcul. Les auteurs affirment atteindre une priorisation quasi optimale et surpasser les méthodes de l'état de l'art, pour une augmentation du temps de calcul qualifiée de mineure. La validation combine des expériences numériques et un essai en temps réel sur un réseau routier avec dix véhicules. Le résumé ne donne ni gain chiffré, ni taille des réseaux simulés, ni temps de cycle précis. La planification prioritaire (prioritized planning, PP) est une approche classique du problème de recherche de chemins multi-agents (MAPF) dans les grands réseaux. Les agents planifient l'un après l'autre selon un ordre de priorité, chacun devant éviter les trajectoires déjà fixées par les agents plus prioritaires. Cette méthode est peu coûteuse en calcul, mais la qualité de la solution dépend fortement de l'ordre choisi. Les priorisations actuelles reposent soit sur des heuristiques qui généralisent mal, soit sur des itérations successives qui consomment du temps de calcul. L'approche présentée évite ce compromis en évaluant plusieurs ordres de priorité en parallèle au sein du même cycle de planification. Elle ne s'appuie sur aucune connaissance propre à un domaine, ce qui la rend applicable à d'autres contextes que la mobilité routière. Le MAMP modélise la dynamique des systèmes de façon plus détaillée que le MAPF, ce qui rapproche les résultats des conditions d'exploitation réelles. Pour les intégrateurs et les responsables de flottes de robots mobiles autonomes (AMR), la coordination de dizaines de véhicules sur un même réseau reste un point dur. Une méthode qui conserve la rapidité de la planification prioritaire tout en limitant sa sensibilité à l'ordre des agents répondrait à un besoin réel, notamment en logistique d'entrepôt. Les réserves sont toutefois nettes. Dix véhicules représentent une échelle modeste face aux flottes industrielles, et l'absence de métriques dans le résumé empêche d'évaluer le gain réel. Le test a lieu dans un laboratoire de mobilité cyber-physique, donc dans un environnement contrôlé. Il s'agit d'un résultat de recherche, sans produit ni déploiement commercial. Le passage à l'échelle, la comparaison avec des solveurs MAPF optimaux ou bornés et le comportement sous contraintes de communication restent à démontrer.

RecherchePaper

1 source