La coordination de flotte d'AMR multi-agents revient de plus en plus souvent dans les discussions sur l'automatisation des entrepôts ces dernières années, et la raison n'est pas compliquée : quand les AMR d'un entrepôt passent d'une poignée à des dizaines, le problème cesse d'être la façon dont une machine se déplace et devient la façon dont tout le groupe évite de se gêner lui-même.

Commençons par ce qui se passe réellement. Prenons un entrepôt de e-commerce typique de taille moyenne. Le premier lot d'AMR compte six unités, et elles fonctionnent à merveille — la productivité de préparation augmente visiblement. Encouragée, la direction élargit la flotte à vingt, puis à quarante. Mais l'année où la flotte atteint quarante, une scène étrange commence à apparaître dans l'entrepôt : au croisement de l'allée principale, plusieurs robots se retrouvent nez à nez, aucun ne bouge, jusqu'à ce que quelqu'un intervienne manuellement ; et quand une vague de préparation arrive, une douzaine de robots font la queue en attendant une allée étroite tandis que le taux de déplacement à vide grimpe au lieu de baisser. Plus de robots, à peine plus de travail accompli, et des embouteillages appris avant toute autre chose. Derrière cette scène se trouve le problème central de la coordination de flotte d'AMR multi-agents : un seul robot poursuit son propre trajet optimal, tandis qu'une flotte a besoin que tout le système ne s'emmêle pas.

Coordination de flotte d'AMR multi-agents : centralisée ou distribuée d'abord

Les universitaires appellent cette classe de problème multi-agent path finding, MAPF en abrégé, et elle est étudiée depuis des décennies sans qu'une réponse standard unique n'en soit sortie. En pratique, les architectures d'ordonnancement se répartissent en deux camps, centralisée et distribuée, et chacune a son prix.

L'ordonnancement centralisé signifie qu'un seul cerveau décide de tout : un serveur central détient la position de chaque AMR, sa tâche et l'état du réseau routier, et calcule ensemble le trajet et le timing de chaque véhicule. L'avantage est une vue globale — il peut élaborer un plan globalement optimal ou quasi optimal, et les conflits sont résolus avant qu'ils ne surviennent. Le prix est le calcul et la réactivité en temps réel : à mesure que la flotte grandit, l'espace des combinaisons explose, et calculer un seul plan globalement optimal peut prendre plus de temps que le trajet lui-même. Et si le serveur central tombe en panne, toute la flotte s'arrête avec lui. Le risque de point unique de défaillance est réel.

L'ordonnancement distribué fonctionne à l'inverse : chaque AMR décide pour lui-même, en négociant la priorité de passage et les files d'attente avec les véhicules proches par communication de machine à machine. L'avantage est la résilience aux pannes locales, l'expansion facile — ajouter un robot ne signifie pas reconstruire l'ordonnanceur — et des réponses rapides en temps réel. Le prix est que les optimums locaux ne s'additionnent pas en un optimum global. Chaque véhicule ne voit que son voisinage, et plusieurs robots peuvent se céder poliment le passage les uns aux autres jusqu'à entrer dans une boucle qui ne se résout jamais. Les universitaires appellent cela livelock. Sur le sol de l'entrepôt, on appelle cela « la danse des robots ».

Architecture Prise de décision Atout Prix
Centralisée Un serveur planifie pour tous Globalement optimale, conflits exclus à l'avance Lourde charge de calcul, risque de point unique de défaillance
Distribuée Chaque véhicule négocie localement Tolérante aux pannes, facile à mettre à l'échelle, réponse rapide Optimums locaux, livelock possible

Les entrepôts réels vont rarement à l'un ou l'autre extrême. L'approche courante est en couches : l'ordonnancement central gère l'affectation des tâches et l'itinéraire approximatif, tandis que l'évitement et la cession locaux sont laissés aux véhicules en temps réel. Central à gros grain, distribué à grain fin — chaque côté porte la moitié du coût. Ce compromis en couches est aussi ce que la plupart des fournisseurs d'AMR livrent réellement aujourd'hui.

Blocages et priorité de passage : les règles de circulation de la coordination de flotte d'AMR multi-agents

Une fois l'architecture fixée, la question suivante est celle des règles de circulation. Comment un blocage se produit-il ? La scène classique est une allée étroite qui ne laisse passer qu'un robot à la fois, avec deux AMR entrant par des extrémités opposées et se rencontrant au milieu. Aucun ne peut avancer, aucun n'a d'instruction de reculer, et sans règle prédéfinie, ils restent là jusqu'à ce qu'un humain intervienne. Plus insidieux encore, un blocage en anneau : quatre robots sur une allée en boucle, chacun occupant un segment, chacun attendant que celui devant avance, et rien sur la boucle ne peut bouger.

Prévenir les blocages ne dépend pas d'un algorithme plus malin pour un seul robot. Cela dépend d'un ensemble de règles de circulation convenues à l'avance. Premièrement, les voies à sens unique : marquer les allées principales en sens unique, n'autoriser l'entrée d'une allée étroite que dans un seul sens, et la moitié des sources de conflit disparaissent avant même de commencer. Deuxièmement, les classes de priorité : un véhicule chargé prime sur un véhicule vide, un véhicule sur une voie principale prime sur un véhicule qui s'insère depuis une voie latérale — des priorités inscrites dans les règles d'ordonnancement, et non négociées à l'intersection. Troisièmement, les réservations : avant d'entrer dans un segment critique, un véhicule réserve une fenêtre de temps auprès de l'ordonnanceur, et si les fenêtres se chevauchent, il attend quelques secondes à l'entrée plutôt que de rester figé dans l'allée pendant des minutes. Quatrièmement, le zonage : diviser l'entrepôt en zones d'ordonnancement, transmettre les tâches interzones aux points de frontière, et empêcher un véhicule de traverser tout l'entrepôt et de déclencher une chaîne de conflits.

Ces règles ne ressemblent pas à de la haute technologie, et c'est exactement pour cela qu'elles constituent la partie la plus précieuse de l'ordonnancement de flotte. Voici le jugement contre-intuitif : dans une flotte d'AMR, ce qui compte le plus souvent pour le débit, ce n'est pas la vitesse à laquelle un robot roule, mais la clarté avec laquelle les règles de cession sont écrites. Augmentez la vitesse d'un seul véhicule de dix pour cent et le temps gagné peut être entièrement perdu à attendre aux intersections. Mettez les règles de priorité de passage au clair, et le débit global de la flotte augmente. La vitesse est une métrique de véhicule unique. Le flux est une métrique de flotte. Les deux s'opposent souvent, et l'ordonnancement existe pour les empêcher de s'opposer.

Affectation des tâches : qui prend cette commande, c'est l'algorithme qui décide

Au-delà des trajets, l'ordonnancement doit répondre à une autre question : une nouvelle tâche arrive — quel véhicule l'obtient ? La réponse la plus simple est l'affectation au plus proche : le véhicule libre le plus proche prend le travail. La logique est intuitive et facile à mettre en œuvre. Le défaut est que les véhicules proches de la zone animée sont toujours les plus occupés, tandis que ceux qui sont loin restent inactifs. Les charges de travail et l'usure des batteries deviennent inégales, les états des véhicules divergent avec le temps, et les coûts de maintenance suivent.

Une approche plus soignée est l'affectation par enchères : l'ordonnanceur diffuse la tâche, et chaque véhicule propose un « coût » en fonction de sa position, de son niveau de batterie et de son travail en cours. L'offre la plus basse gagne. L'idée vient de la théorie des enchères, et la littérature universitaire en discute abondamment ; il existe aussi des déploiements en production. L'avantage est que la distance, la batterie et le type de tâche se combinent en un seul chiffre, de sorte que la charge de la flotte s'équilibre d'elle-même. Le coût est la surcharge de communication et de calcul — avec un flux de tâches intense, l'enchère elle-même devient un fardeau — si bien que de nombreux systèmes ne font des enchères qu'entre les vagues ou quand les tâches s'accumulent, et utilisent une règle simplifiée du plus proche pondéré le reste du temps.

Prenons un exemple illustratif. Supposons une flotte de vingt véhicules confrontée à 120 tâches de transport par heure en pointe. Avec l'affectation au plus proche, les six véhicules les plus proches de la zone de stockage populaire pourraient prendre la moitié des tâches, vider leurs batteries rapidement et devoir partir se recharger en milieu de poste, réduisant la flotte effective à quinze ou seize. Avec l'affectation pondérée par la batterie, les tâches se répartissent sur les vingt, la charge par véhicule baisse, et les rotations de recharge peuvent être échelonnées dans les intervalles entre les vagues, de sorte que les mêmes vingt véhicules assurent une présence effective plus élevée. Ces chiffres sont un exemple illustratif calculé, destiné à montrer comment les règles d'affectation influent sur la taille effective de la flotte — pour tout entrepôt réel, le calcul doit être refait en fonction de sa propre distribution des tâches et de son réseau routier.

Vers où se dirige la coordination de flotte d'AMR multi-agents

En rassemblant les fils, la direction est assez claire. Premièrement, les architectures hybrides seront la norme : contrôle centralisé pour les tâches et la vue d'ensemble, contrôle distribué pour l'évitement et le détail, avec une interface nette divisant les deux couches plutôt qu'un côté qui domine. Deuxièmement, les algorithmes d'ordonnancement s'appuieront davantage sur la simulation : avant qu'une nouvelle règle ne passe en production, exécuter des milliers de vagues dans un jumeau numérique, exposer à l'avance les scénarios de blocage et de congestion, et seulement ensuite la déployer dans l'entrepôt réel. Troisièmement, l'affectation des tâches passera de « qui est le plus proche » à « qui est le plus adapté », avec le niveau de batterie, le type de tâche et les cycles de maintenance qui alimentent tous la fonction de coût.

Mais un rappel appartient à la fin : quelle que soit la sophistication de l'algorithme d'ordonnancement, il ne peut pas se substituer à l'agencement de l'entrepôt lui-même. Largeurs d'allées, emplacement des zones de stockage, rythme des vagues — si la conception physique est fausse dès le départ, même le meilleur algorithme ne fait que colmater un mauvais réseau routier. Les algorithmes peuvent empêcher un groupe de robots de se battre. Ils ne peuvent pas élargir une route mal conçue. Faites d'abord les routes correctement, puis parlez de la façon dont la flotte doit fonctionner. Il est peu probable que cet ordre change avant longtemps.

Par Dr. Chen, Chercheur en chaîne logistique Traduit de l'anglais. En cas de divergence, la version anglaise fait foi.