RecherchearXiv cs.RO 28 août 2026

Réservation à emplacement fixe pour la collecte et livraison multi-agents en ligne dans des entrepôts denses

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Un article publié sur arXiv (2608.26759v1) présente SHARP (Safe-Haven Retreat Planner), une méthode garantissant l'achèvement de toutes les tâches de ramassage-livraison confiées à des flottes de robots mobiles dans des entrepôts denses, où allées à sens unique, impasses et guidages arborescents empêchent un robot inactif d'attendre sans bloquer les autres. Chaque agent reçoit un "Havre" fixe, en général sa cellule de départ, que lui seul peut occuper et que les autres traitent comme un obstacle. Les auteurs démontrent formellement que ce contrat garantit la complétion de tout nombre fini de tâches libérées, sous des conditions d'accessibilité et de planification explicites. Face à trois algorithmes de référence, Token Passing (TP), Priority Inheritance with Backtracking (PIBT) et sa variante PIBTTP-TA, SHARP est le seul à atteindre 100% de réussite sur l'ensemble d'un test de robustesse, au prix d'un coût de calcul centralisé nettement plus élevé sur les layouts arborescents. Une variante sans réaffectation en cours de repli dégrade le temps de service de 1,89 fois et le makespan de 1,53 fois en condition de forte charge.

Ce travail comble un angle mort documenté du MAPD (Multi-Agent Pickup and Delivery): les garanties théoriques existantes supposent généralement des points d'attente supplémentaires évitables par les chemins planifiés, ou une topologie biconnexe du réseau de guidage, deux hypothèses qui s'effondrent dans les entrepôts réels à forte densité de stockage. Pour les intégrateurs de flottes de robots mobiles autonomes et les exploitants d'entrepôts, le résultat est concret: un mécanisme de retour systématique vers une position réservée fixe peut restaurer la robustesse là où les algorithmes classiques échouent, sans repenser le layout physique pour ajouter des zones tampons. Le compromis entre robustesse garantie et coût de planification centralisée reste néanmoins le principal frein pratique à un déploiement à grande échelle.

La méthode s'inscrit dans la continuité des algorithmes de coordination Token Passing et de la famille PIBT, références classiques du MAPF (Multi-Agent Path Finding) appliqué à la logistique automatisée. Les auteurs testent aussi une variante Token Passing à retour systématique vers le point de départ avec validation complète de trajectoire, qui retrouve une robustesse comparable sur les layouts arborescents testés, suggérant que le retour fixe est un mécanisme de robustesse indépendant de l'algorithme sous-jacent. L'étude reste à ce stade une contribution de simulation académique, sans déploiement industriel ni partenariat annoncé avec un opérateur d'entrepôt ou un fabricant d'AMR; une validation en conditions réelles constituerait la suite logique de ces travaux.

Dans nos dossiers

arXiv cs.RO

À lire aussi

1arXiv cs.RO

Sélection dynamique de zones refuges pour la livraison multi-agents en entrepôt contraint

Publié sur arXiv fin août 2026 sous la référence 2608.26939, A-sharp (Adaptive SHARP) est un algorithme de planification multi-agents de ramassage-livraison (MAPD) pour entrepôts exigus, couloirs à largeur d'un seul robot et postes en cul-de-sac. Il corrige SHARP (Safe HAven Retreat Planner), qui assignait à chaque robot un Haven fixe, zone d'attente protégée, obligeant parfois un repli éloigné après livraison. A-sharp réassigne ce Haven à chaque nouvelle tâche grâce à un test de disponibilité et une règle de libération différée empêchant deux robots de viser le même emplacement. Sous hypothèses de structure des Havens et de planification SIPP, les auteurs prouvent une complétude garantissant la livraison en temps fini, validée sur 72 000 exécutions couvrant 14 400 combinaisons carte/agents/taux/graine sur quatre cartes: sur 138 configurations à Havens excédentaires, A-sharp bat significativement SHARP dans 107 cas, jamais l'inverse, avec une réduction médiane du makespan de 16,7% sur la carte en arbre testée. Pour les intégrateurs de flottes AMR, cette contribution s'attaque à un point de blocage très concret des entrepôts à forte densité: dans une allée où un seul robot passe à la fois, une zone d'attente mal choisie ou saturée peut paralyser tout le flux logistique. En rendant les Havens dynamiques plutôt que figés par agent, A-sharp promet de réduire trajets et temps de cycle sans sacrifier les garanties formelles de non-blocage, un argument de poids pour des acheteurs B2B qui exigent des preuves avant tout déploiement en production. L'étude reste toutefois une validation en simulation sur des cartes synthétiques et non un test en entrepôt réel, et le gain de 16,7% ne concerne qu'une seule topologie parmi les 138 configurations testées. Le travail prolonge directement SHARP, dont A-sharp corrige la principale faiblesse: des affectations de Havens figées à l'initialisation. Il s'inscrit dans le champ actif du MAPD et du MAPF (Multi-Agent Path Finding), où coexistent des approches comme CBS ou PIBT, et où des acteurs industriels comme le français Exotec développent déjà des systèmes de stockage à très haute densité. Les auteurs ne mentionnent aucun calendrier de déploiement ni partenariat industriel: la contribution reste, à ce stade, un résultat algorithmique et théorique, dont l'étape naturelle suivante serait une validation sur des flottes robotiques réelles ou des layouts d'entrepôt propriétaires.

RecherchePaper

1 source

2arXiv cs.RO

Livraison et collecte dynamiques multi-agents dans les systèmes d'entrepôt robotisé cellulaire

Une équipe de chercheurs publie sur arXiv (réf. 2606.05669, juin 2026) la première formalisation du problème de collecte et livraison multi-agents (MAPD) intégrant l'évolution dynamique des commandes dans les entrepôts robotisés à cellules (RCWS). Le constat de départ est un angle mort opérationnel connu: les algorithmes MAPD classiques supposent des tâches figées, alors que dans la réalité industrielle, de nouvelles références (SKU) s'ajoutent à une commande pendant son exécution. Pour y répondre, les auteurs proposent deux algorithmes de replanification en ligne déclenchés par événements, construits sur le paradigme du token passing. Le premier, Dynamic Token Passing (DTP), effectue une replanification localisée à chaque mise à jour via une décomposition add-order et un ordonnancement prioritaire des accès, tout en garantissant l'absence de collisions entre robots. Le second, Cooperative Token Passing (CTP), mobilise en plus les robots inactifs pour absorber opportunément les nouveaux pickups ajoutés en cours d'exécution. Des simulations en environnement RCWS montrent une réduction significative du flowtime de commandes par rapport aux baselines statiques et non coopératives, sans que les auteurs ne publient de chiffres précis à ce stade. L'enjeu pour les intégrateurs d'entrepôts automatisés est direct: toute modification de commande en cours force aujourd'hui soit une replanification globale coûteuse en temps de calcul, soit une dégradation de la qualité de service. Ce travail comble pour la première fois l'écart entre la littérature académique sur le MAPD et les contraintes opérationnelles réelles des ERP industriels. Le mécanisme coopératif du CTP est particulièrement notable: il exploite la capacité oisive des flottes denses plutôt que de relancer un planning complet, remettant en question l'hypothèse selon laquelle la planification statique par vagues suffit aux RCWS commerciaux actuels. Le token passing est un paradigme bien établi dans la recherche en planification multi-agents (MAPF), notamment autour des travaux de Sven Koenig. Son application aux RCWS cible des architectures déployées par AutoStore (Norvège), Ocado Technology et Hai Robotics, ainsi que par l'acteur français Exotec (Villeneuve-d'Ascq) avec son système Skypod, dont les configurations à grille dense concentrent des centaines de robots sur un volume compact. Ces environnements sont précisément ceux où la coordination dynamique devient critique à mesure que les densités de flotte augmentent. Ce travail reste à ce stade une contribution académique sans déploiement ni partenariat industriel annoncé; la prochaine étape logique serait une validation sur environnement physique et une intégration avec des WMS industriels existants.

UEExotec (Villeneuve-d'Ascq), dont le système Skypod est explicitement cité comme architecture cible, pourrait bénéficier de ces algorithmes si intégrés dans un WMS industriel, renforçant sa compétitivité face à AutoStore et Ocado dans les entrepôts à haute densité de flotte.

RecherchePaper

1 source

3arXiv cs.RO

Coordination par relais pour la collecte et livraison multi-robots économe en énergie

Une équipe de chercheurs a publié sur arXiv (identifiant 2509.14127, version 2, septembre 2025) un cadre de planification baptisé VCST-RCP (Voronoi-Constrained Steiner Tree Relay Coordination Planning), conçu pour coordonner des flottes homogènes de robots mobiles dans des missions de livraison multi-colis depuis un dépôt unique vers des destinations dispersées. L'algorithme opère en deux phases: la construction d'un réseau de relais sparse combinant des interfaces d'échange dérivées de diagrammes de Voronoï à une optimisation par arbre de Steiner, puis la génération des plannings de collecte, relais et livraison sous contraintes de capacité de charge et de temps de service. Sur des expériences menées à plusieurs échelles, VCST-RCP réduit la distance totale parcourue par la flotte de 31% en moyenne, avec des pics proches de 50%, par rapport à l'algorithme d'affectation Hungarian assignment, et surpasse significativement OR-Tools CVRP, le solveur de référence de Google. La significativité statistique est établie à p inférieur à 10^-3, et le gain d'efficacité de livraison, mesuré en colis par kilomètre parcouru, dépasse 50%. Ces résultats intéressent directement les opérateurs de flottes AMR (robots mobiles autonomes) en intralogistique et en livraison de dernier kilomètre, où la distance parcourue est directement corrélée au coût énergétique et à l'usure matérielle. L'étude d'ablation incluse dans les travaux est particulièrement instructive: elle démontre que l'optimisation du placement des points de relais génère des gains substantiellement supérieurs à ceux obtenus par simple repartitionnement spatial, établissant le design des relais comme levier dominant de la performance système. Cela remet en question l'hypothèse implicite répandue chez les intégrateurs, selon laquelle le transport direct source-destination constitue la référence optimale par défaut. La scalabilité démontrée à différentes tailles de flotte est un argument supplémentaire pour une adoption industrielle. Le problème MRPD (Multi-Robot Pickup and Delivery) est un classique de l'optimisation combinatoire en robotique, mais les architectures relay-based à grande échelle restent peu explorées. Hungarian assignment et OR-Tools CVRP, les deux références battues dans cette étude, sont précisément les solveurs utilisés par les éditeurs de WMS et les intégrateurs de flottes dans des environnements comme ceux d'Exotec (Roubaix), 6 River Systems ou Locus Robotics. Ce travail reste cependant un preprint arXiv, sans validation sur plateforme réelle annoncée: les gains en simulation sont solides, mais la transition sim-to-real, notamment face à la congestion dynamique et aux pannes robot en cours de mission, reste à prouver. Les extensions naturelles incluent des flottes hétérogènes et des dépôts multiples.

UEL'algorithme VCST-RCP, s'il est validé en environnement réel, pourrait réduire de ~30% les coûts énergétiques des flottes AMR d'acteurs européens comme Exotec (Roubaix) qui utilisent actuellement Hungarian assignment ou OR-Tools CVRP comme solveurs de référence.

RecherchePaper

1 source

4arXiv cs.RO

Planification de placement sensible à la sémantique et à la densité pour préserver l'accessibilité multi-objets

Des chercheurs présentent, dans un article publié sur arXiv le 18 août 2026 (référence arXiv:2608.16741v1), une méthode baptisée SDPP (Semantic-Dense Placement Planning), conçue pour permettre à un robot de service domestique de ranger des objets sur une étagère partiellement occupée sans connaître à l'avance les futurs objets à placer. Le système classe les positions candidates à partir d'un score combinant similarité sémantique entre objets (par exemple regrouper les produits de même catégorie) et proximité spatiale, afin de densifier le rangement tout en gardant une organisation cohérente. Une seconde brique, l'Accessibility Map (AM), filtre en amont les poses de placement peu susceptibles d'être atteignables par le bras manipulateur avant même de lancer la planification de mouvement, et pénalise les choix qui réduiraient l'espace de travail accessible pour les placements suivants. Les auteurs rapportent, en simulation, une amélioration significative de la qualité de l'organisation sémantique par rapport aux méthodes de référence actuelles, ainsi que la densité moyenne d'étagère la plus élevée obtenue parmi les approches comparées ; l'AM réduit par ailleurs sensiblement le temps nécessaire pour identifier une pose de placement faisable. Une expérience qualitative en conditions réelles, sur un scénario domestique de stockage en étagère, complète ces résultats. L'enjeu dépasse le simple rangement de courses : la plupart des travaux existants sur la planification de placement traitent séparément l'organisation sémantique, la densité d'occupation de l'espace et l'accessibilité du bras robotique, alors que ces trois contraintes entrent souvent en conflit dans un contexte réel de remplissage séquentiel où les futurs objets sont inconnus. En traitant ces dimensions conjointement, SDPP s'adresse directement aux intégrateurs travaillant sur la logistique en entrepôt, le service à domicile ou le retail automatisé, où un robot doit continuer à opérer efficacement sur une étagère qui se remplit au fil du temps sans bloquer ses propres accès futurs. Le travail s'inscrit dans la littérature de planification de manipulation à long terme pour robots de service, un domaine où la validation reste majoritairement limitée à la simulation. Les auteurs précisent eux-mêmes que leur test en environnement réel n'a qu'une portée qualitative, ce qui distingue cette contribution d'un système prêt pour un déploiement commercial et la situe encore au stade de la recherche exploratoire, avant tout passage à une validation à plus grande échelle.

RecherchePaper

1 source