🤖 AI

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

Cet article présente un algorithme de planification prioritaire nouveau, complet et évolutif pour le stockage et la récupération ordonnés par multi-robots dans des entrepôts à base de puzzles à capacité maximale, qui garantit une exécution sans interblocage et une amélioration quasi linéaire du makespan tout en maintenant un surcoût négligeable pour la robustesse face aux séquences de départ incertaines.

Auteurs originaux : William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

Publié 2026-08-11

📖 3 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où chaque pouce carré d'un entrepôt est rempli à ras bord, comme un plateau de Tetris qui aurait été complété jusqu'en haut sans laisser le moindre espace vide. C'est le rêve de la logistique moderne : maximiser la densité de stockage pour économiser sur le loyer, surtout dans les villes encombrées. Mais il y a un piège. Si vous remplissez une pièce si étroitement qu'il n'y a plus d'allées pour que les chariots élévateurs ou les robots puissent circuler, comment sortir quoi que ce soit ? C'est le casse-tête du « stockage basé sur des puzzles ». Pensez-y comme à un jeu de puzzle de déplacement de tuiles (comme le classique jeu du 15) où chaque article est une tuile, et le seul moyen d'en déplacer une est de faire bouger les autres autour d'elle. Maintenant, imaginez que vous n'avez pas une seule personne déplaçant des tuiles, mais toute une équipe de robots travaillant de concert. Le défi devient une danse chaotique : si les robots ne sont pas parfaitement coordonnés, ils pourraient se retrouver bloqués dans un embouteillage où plus personne ne peut bouger, une situation connue sous le nom de « deadlock » (impasse). Résoudre cela est crucial car, alors que le shopping en ligne explose, les entrepôts doivent être à la fois incroyablement pleins et incroyablement rapides.

Cet article s'attaque précisément à ce chaos. Les auteurs, une équipe de l'Université de Rutgers, proposent une nouvelle façon de coordonner un essaim de robots dans un entrepôt entièrement rempli et sans allées. Ils introduisent un système qui gère deux phases distinctes : d'abord, remplir l'entrepôt à sa capacité maximale absolue avec les marchandises entrantes, et deuxièmement, les extraire dans un ordre spécifique à mesure que les camions arrivent pour les emporter. Le cœur de leur solution est un algorithme de « planification priorisée ». Au lieu d'essayer de calculer le chemin parfait pour chaque robot simultanément (ce qui revient à essayer de résoudre un puzzle d'un million de pièces à la fois et provoque généralement le plantage de l'ordinateur), ils laissent les robots attendre leur tour. Lorsqu'un robot termine une tâche, il saisit la tâche suivante disponible et trace un chemin, tandis que les autres attendent leur tour ou s'écartent du chemin.

L'article démontre que cette approche n'est pas seulement une astuce ingénieuse, mais une solution robuste. Ils prouvent mathématiquement que leur méthode garantit que les robots ne resteront jamais bloqués dans une impasse, même lorsque l'entrepôt est rempli à 100 %. Dans leurs simulations, ils ont testé des grilles allant jusqu'à 30 par 30 cellules avec jusqu'à 30 robots. Les résultats ont montré que l'ajout de robots rendait l'exécution du travail presque linéairement plus rapide ; par exemple, utiliser 20 robots sur une grille de 20x20 rendait le processus près de 20 fois plus rapide qu'avec un seul robot. Plus surprenant encore, ils ont découvert que rendre le système « robuste » face à l'incertitude — c'est-à-dire que l'entrepôt puisse gérer si l'ordre des camions change légèrement à la dernière minute — n'entraîne presque aucune pénalité de vitesse. Les robots se déplacent tout aussi vite que le plan soit rigide ou flexible. Bien que leur méthode ne soit pas théoriquement parfaite par rapport à un planificateur central super complexe et lent, elle est suffisamment rapide pour fonctionner en temps réel et s'adapte magnifiquement à l'échelle, offrant un moyen pratique de transformer un puzzle encombré et statique en une machine mobile à haute vitesse.

Résumé Technique : Planification Prioritée Complète, Scalable et Robuste pour le Stockage et la Récupération Ordonnés Multi-Robots à Capacité Maximale

1. Définition du Problème

Le document traite du défi de la coordination de plusieurs robots dans des systèmes de stockage à haute densité basés sur des puzzles (PBS - Puzzle-Based Storage), spécifiquement pour le « problème de stockage et de récupération ordonnés à capacité maximale ».

Contexte et Défis :

Contraintes de Haute Densité : Contrairement aux systèmes de stockage et de récupération automatisés (AS/RS) traditionnels qui reposent sur des allées dédiées (ex: style Kiva), les architectures PBS éliminent les allères internes pour maximiser la densité de stockage. La grille de stockage fonctionne comme un puzzle de type glissement de tuiles où les charges sont réorganisées à l'aide de cellules vides limitées.
Phases Opérationnelles : Le système fonctionne en deux phases distinctes :
1. Stockage : Les charges arrivent via un convoyeur dans une séquence spécifique et doivent être stockées jusqu'à 100 % de la capacité de la grille.
2. Récupération : Les charges doivent être récupérées selon une séquence de départ pré-planifiée.
Le Conflit Central : Bien que des travaux antérieurs (StoRMR et R-StoRMR) aient établi que les arrangements sans déplacement (relocation-free) séquentiels (mono-robot) sont géométriquement réalisables, l'exécution de ces arrangements à l'aide de plusieurs robots en parallèle reste inexplorée. Coordonner plusieurs robots dans des environnements aussi denses et sans allées est numériquement difficile en raison du risque élevé d'impasses (deadlocks) et de la malédiction de la dimensionnalité pour les planificateurs centralisés.
Incertitude : Le système doit également gérer l'incertitude de la séquence de départ, où l'ordre réel de récupération peut dévier légèrement du plan (modélisé par des perturbations bornées par $k$ ).

2. Méthodologie

Les auteurs proposent un algorithme de recherche de chemin multi-agents (MAPF) priorisé et en ligne qui exploite les invariants géométriques spécifiques des arrangements de stockage sans déplacement pour garantir la complétude et prévenir les blocages.

Modèle de Système

Environnement : Une grille rectangulaire ( $R \times C$ ) avec une rangée d'E/S (Entrée/Sortie) et un convoyeur en dessous.
Agents : $m$ robots ( $m \le C$ ) capables de se déplacer, de pivoter, de ramasser et de déposer des charges.
Modèle de Hauteur à Deux Niveaux : Les robots naviguent sous les charges stationnaires (style AMR), ce qui leur permet de passer sous les objets stockés sans collision, à condition de ne pas occuper la même cellule simultanément.
Contraintes : Le système évite les collisions positionnelles (deux entités dans une même cellule) et les collisions directionnelles (échanges ou conflits orthogonaux), bien que le mouvement en « train » (suivre dans la même direction) soit autorisé.

L'Algorithme : Planification Prioritée Asynchrone

L'approche découple le processus de planification, en assignant les tâches dynamiquement aux robots inactifs plutôt qu'en résolvant pour tous les agents simultanément.

Assignation de Tâches :
- Stockage : Lorsqu'un robot devient inactif, il se voit assigner la prochaine charge non réclamée dans la séquence d'arrivée. Le robot le plus proche du point de ramassage est sélectionné de manière gloutonne (greedy).
- Récupération : Les robots réclament la prochaine charge non réclamée dans la séquence de départ. Un robot ne réclame une charge qu'une fois qu'un chemin valide a été calculé avec succès.
Planification de Trajectoire :
- Le planificateur utilise une recherche A* spatio-temporelle pour générer des trajectoires minimales en temps depuis la position actuelle du robot vers les points de ramassage/dépose.
- Table de Réservation Globale : Pour éviter les collisions, le système maintient une table de réservation suivant les contraintes espace-temps $(p, t, d)$ , où $p$ est la position, $t$ l'étape temporelle et $d$ la direction d'entrée prohibée. Cela empêche explicitement les conflits de suivi directionnel.
- Gestion des Obstacles : Les charges stockées sont traitées comme des obstacles statiques. Leur statut est mis à jour dynamiquement : une charge est retirée de la table des obstacles lorsqu'un robot prévoit de la ramasser et y est réajoutée lorsqu'elle est déposée.
Gestion de la Complexité de Récupération :
- Un défi critique lors de la récupération est de déterminer où le robot doit attendre après avoir déposé une charge.
- Stratégie : L'algorithme tente de positionner le robot sous la prochaine charge non réclamée de la séquence. Si cela est inaccessible, il retombe sur l'attente sous la charge non réclamée la plus proche et accessible. Si aucune charge n'est accessible, le robot se déplace vers une cellule garantie sans obstruction dans la rangée arrière.
- Respect de la Séquence : Pour garantir le respect de la séquence de départ, un robot ne planifie un chemin pour la charge $j$ qu'une fois que le chemin pour la charge $j-1$ vers la rangée d'E/S est mis en file d'attente.

Garanties Théoriques

Le papier prouve la complétude (l'algorithme trouvera toujours une solution si elle existe) pour les phases de stockage et de récupération.

Base : La preuve repose sur les propriétés des arrangements sans déplacement (établis dans les travaux précédents StoRMR/R-StoRMR). Ces arrangements garantissent que pour toute charge de la séquence, un chemin sans collision existe vers/depuis la rangée d'E/S, à condition que les autres charges ne soient pas déplacées.
Induction : Les auteurs utilisent l'induction pour montrer que si les $k-1$ premières charges sont stockées/récupérées avec succès, les propriétés géométriques de l'arrangement garantissent que la $k$ -ième charge peut également être accessible par au moins un robot inactif, empêchant ainsi les blocages même à 100 % de densité.

3. Contributions Clés

Formulation Multi-Robots : Introduit une nouvelle formulation pour le stockage et la récupération ordonnés à capacité maximale, comblant le fossé entre la faisabilité géométrique (séquentielle) et l'efficacité d'exécution (parallèle).
Algorithme de Planification Prioritée : Propose un algorithme asynchrone et en ligne qui utilise les invariants des arrangements sans déplacement pour garantir la complétude et la prévention des blocages dans des environnements denses, un accomplissement rare pour les méthodes de MAPF prioritées.
Scalabilité et Efficacité : Démontre que l'approche atteint une amélioration quasi linéaire du makespan (temps total de réalisation) à mesure que le nombre de robots augmente, jusqu'à $m = C$ (largeur de la grille).
Robustesse avec un Surcoût Négligeable : Montre que l'utilisation d'arrangements de stockage robustes (R-StoRMR) pour gérer l'incertitude de la séquence de départ n'entraîne aucun pénalité significative sur la vitesse d'exécution par rapport aux bases non robustes.
Faible Sous-optimalité : L'algorithme présente une faible sous-optimalité du makespan (ratio de 1,09 à 1,21) par rapport à un planificateur couplé centralisé théoriquement optimal mais non scalable.

4. Résultats Expérimentaux

Des expériences ont été menées sur des grilles allant jusqu'à $30 \times 30$ avec un nombre variable de robots (de 1 à $C$ ).

Scalabilité : Le système atteint une accélération quasi linéaire de la réduction du makespan à mesure que le nombre de robots augmente. Pour une grille de $20 \times 20$ , le ratio d'amélioration suit étroitement la référence linéaire idéale jusqu'à 20 robots.
Temps d'Exécution : Le temps de planification par charge reste dans la plage de la sous-seconde même lorsque la taille de la grille et le nombre de robots augmentent, rendant le système adapté à une opération en ligne en temps réel.
Pénalité de Robustesse : En comparant les arrangements standards ( $k=0$ ) avec les arrangements robustes ( $k=0,4C$ ), la pénalité d'exécution s'est avérée négligeable. Le makespan et la distance totale parcourue étaient presque identiques.
Surcoût de Coordination : Bien que la distance totale parcourue augmente légèrement avec plus de robots en raison des manœuvres d'évitement de collision, l'augmentation est faible (moins de 5 % pour 20 robots par rapport à un seul robot).
Optimalité : Comparé à un solveur A* couplé (limité à de petits lots en raison de la complexité computationnelle), le planificateur priorisé montre un ratio de sous-optimalité compris entre 1,09 et 1,21. Les auteurs attribuent une partie de cet écart à la capacité du planificateur couplé à exploiter le modèle de convoyeur pour un léger réordonnancement, ce que l'approche priorisée évite pour maintenir des garanties de séquence strictes.

5. Signification et Revendications

Le papier prétend résoudre un compromis fondamental dans la logistique automatisée : maximiser la densité de stockage tout en maintenant un débit de récupération élevé. En prouvant que la planification priorisée peut être complète et exempte de blocages dans des environnements à 100 % de densité lorsqu'elle est guidée par des invariants géométriques spécifiques, ce travail permet le déploiement pratique de systèmes multi-robots dans le stockage basé sur des puzzles.

Les auteurs soulignent que leur approche ne nécessite pas la « malédiction de la dimensionnalité » associée aux planificateurs centralisés. Au lieu de cela, elle exploite les propriétés structurelles de la disposition de stockage pour permettre une exécution parallèle et scalable. Crucialement, le travail démontre que la robustesse face à l'incertitude (gestion de séquences de départ variables) peut être intégrée sans sacrifier la vitesse ou l'efficacité du système, ce qui en fait une solution viable pour la logistique réelle où les temps d'arrivée et de départ peuvent varier.

Le papier conclut que, bien qu'il existe un léger écart d'optimalité par rapport à la recherche couplée, la scalabilité et la robustesse de la méthode proposée la rendent supérieure pour les applications à grande échelle et en temps réel. Des travaux futurs sont suggérés pour explorer d'autres techniques de MAPF (comme PIBT) afin de réduire l'écart d'optimalité et pour étudier des arrangements spécifiquement adaptés à la coordination multi-robots.