
Recherche à horizon adaptatif basée sur les conflits pour la planification de chemins multi-agents en boucle fermée
Des chercheurs ont publié sur arXiv (arXiv:2602.12024v2) un algorithme nommé ACCBS (Adaptive-Horizon Conflict-Based Search), conçu pour résoudre en temps réel le problème de coordination de flottes de robots dans des entrepôts automatisés. Le Multi-Agent Path Finding (MAPF) consiste à calculer des trajectoires sans collision pour des dizaines à des centaines d'AGV ou AMR opérant simultanément dans un même espace. ACCBS est un planificateur en boucle fermée qui adapte dynamiquement son horizon de planification en fonction du budget computationnel disponible, et réutilise un arbre de contraintes unique pour passer fluidement d'un horizon à l'autre. L'algorithme exhibe un comportement "anytime" : il retourne une solution faisable de bonne qualité très rapidement, puis l'améliore jusqu'à l'optimalité asymptotique si le temps de calcul le permet. L'enjeu industriel est direct. Les approches actuelles se divisent en deux familles peu satisfaisantes : les planificateurs en boucle ouverte, qui génèrent des trajectoires fixes et s'effondrent dès qu'un robot tombe en panne ou qu'un opérateur traverse une allée, et les heuristiques en boucle fermée, qui réagissent aux perturbations mais sans garantie de performance formelle, ce qui les exclut des déploiements à contraintes de sécurité. ACCBS propose un compromis crédible : la robustesse aux perturbations d'un système réactif combinée aux garanties théoriques d'un solveur optimal. Pour un intégrateur ou un COO logistique, cela signifie potentiellement pouvoir dimensionner une flotte plus serrée sans sacrifier la fiabilité SLA, et certifier le comportement du système face aux auditeurs. ACCBS s'appuie sur CBS (Conflict-Based Search), un algorithme de référence académique pour le MAPF optimal, et y greffe un mécanisme d'horizon variable inspiré du Model Predictive Control (MPC) et de l'iterative deepening. Ce domaine est activement disputé : Amazon Robotics, Geek+ et Exotec (acteur français, qui déploie des flottes Skypod dans plusieurs dizaines d'entrepôts en Europe et Amérique du Nord) investissent massivement dans la coordination de flottes à grande échelle. La contribution reste à ce stade un résultat de recherche avec études de cas simulées, aucun déploiement réel n'est annoncé, et les auteurs ne précisent pas le nombre d'agents testé ni les temps de cycle obtenus, ce qui limite l'évaluation de la maturité industrielle.
UEExotec, acteur français leader des flottes Skypod déployées dans des dizaines d'entrepôts en Europe, opère précisément dans le domaine adressé par ACCBS ; si l'algorithme atteint la maturité industrielle, il pourrait renforcer la compétitivité des solutions européennes de coordination de flottes AMR face aux acteurs américains et asiatiques.

















































