Des robots qui dansent le Tetris dans les entrepôts géants

Des chercheurs du MIT ont développé une intelligence artificielle capable d’optimiser la gestion de centaines de robots dans d’énormes entrepôts. Cette innovation pourrait considérablement améliorer l’efficacité des opérations de logistique et de fabrication dans divers secteurs, tels que l’e-commerce et l’automobile.

Des centaines de robots sillonnent les entrepôts géants, transportant des articles et les livrant à des humains pour emballage et expédition. Ces entrepôts font partie intégrante de la chaîne d’approvisionnement de nombreuses industries, telles que l’e-commerce et la production automobile.

En revanche, coordonner efficacement 800 robots pour atteindre leurs destinations respectives tout en évitant les collisions reste un défi de taille. Les meilleurs algorithmes de planification de cheminement ont du mal à suivre le rythme effréné de l’e-commerce ou de la production automobile.

Une solution inspirée de la gestion du trafic urbain

Des chercheurs du MIT ont adapté des idées utilisées pour atténuer la congestion du trafic urbain à ce problème. Ils ont créé un modèle d’apprentissage profond qui encode des informations cruciales sur l’entrepôt, dont les robots, les trajets planifiés, les tâches et les obstacles, et les utilise pour prédire les zones de l’entrepôt offrant le meilleur potentiel de décongestion, améliorant ainsi l’efficacité globale.

Leur technique divise les robots en petits groupes, permettant de décongestionner plus rapidement ces groupes grâce à des algorithmes traditionnels utilisés pour coordonner les robots. Au final, leur méthode décongestionne les robots près de quatre fois plus rapidement qu’une méthode aléatoire forte.

Au-delà de l’optimisation des entrepôts, cette approche d’apprentissage profond pourrait être appliquée à d’autres tâches de planification complexes, telles que la conception de circuits intégrés ou la planification de la tuyauterie dans de grands bâtiments.

« Nous avons mis au point une nouvelle architecture de réseau neuronal adaptée aux opérations en temps réel à l’échelle et à la complexité de ces entrepôts. Elle peut encoder des centaines de robots en termes de trajectoires, d’origines, de destinations et de relations avec d’autres robots, et ce, de manière efficace en réutilisant les calculs entre les groupes de robots« , précise Cathy Wu, professeure assistante au Département de génie civil et environnemental (CEE) et membre du Laboratoire d’information et de systèmes de décision (LIDS) et de l’Institut pour les systèmes, les données et la société (IDSS).

Wu, auteure principale d’un article sur cette technique, est rejointe par Zhongxia Yan, étudiante diplômée en génie électrique et informatique. Le travail sera présenté à la Conférence internationale sur les représentations d’apprentissage.

Des entrepôts aux allures de Tetris

Vue du ciel, la surface d’un entrepôt robotisé d’e-commerce ressemble à une partie rapide de « Tetris ».

Lorsqu’une commande client arrive, un robot se rend à une zone de l’entrepôt, saisit l’étagère contenant l’article demandé et la livre à un opérateur humain qui le sélectionne et l’emballage. Des centaines de robots effectuent simultanément ces opérations, et si les chemins de deux robots se heurtent en traversant l’entrepôt massif, ils pourraient s’entrechoquer.

Les algorithmes de recherche traditionnels évitent les collisions potentielles en maintenant un robot sur sa trajectoire et en recalculant un trajet pour l’autre. Cependant, avec autant de robots et de conflits potentiels, le problème s’accroît de manière exponentielle.

« Comme l’entrepôt fonctionne en ligne, les robots sont repensés environ tous les 100 millisecondes. Cela signifie qu’un robot est repensé 10 fois par seconde. Par conséquent, ces opérations doivent être très rapides« , ajoute Cathy Wu.

En raison de l’importance du temps lors du repositionnement, les chercheurs du MIT utilisent l’apprentissage automatique pour se concentrer sur les zones de congestion présentant le plus grand potentiel de réduction du temps de déplacement total des robots.

Wu et Yan ont développé une architecture de réseau neuronal qui considère simultanément de plus petits groupes de robots. Par exemple, dans un entrepôt de 800 robots, le réseau peut diviser le sol de l’entrepôt en groupes contenant 40 robots chacun.

Ensuite, il prédit quel groupe offre le plus grand potentiel d’amélioration de la solution globale si un solveur de recherche basé sur des règles était utilisé pour coordonner les trajectoires des robots de ce groupe.

Un processus itératif, l’algorithme global choisit le groupe de robots le plus prometteur avec le réseau neuronal, décongestionne le groupe avec le solveur de recherche basé sur des règles, puis choisit le prochain groupe le plus prometteur avec le réseau neuronal, et ainsi de suite.

Prendre en compte les relations

Le réseau neuronal peut raisonner efficacement sur les groupes de robots car il capture les relations complexes qui existent entre les robots individuels. Par exemple, même si un robot peut être éloigné d’un autre initialement, leurs chemins peuvent toujours se croiser pendant leurs trajets.

La technique rationalise également le calcul en codant les contraintes une seule fois, plutôt que de répéter le processus pour chaque sous-problème. Par exemple, dans un entrepôt de 800 robots, la décongestion d’un groupe de 40 robots nécessite de maintenir les 760 autres robots comme contraintes. D’autres approches exigent de raisonner sur tous les 800 robots une fois par groupe dans chaque itération.

Au lieu de cela, l’approche des chercheurs ne nécessite de raisonner sur les 800 robots qu’une seule fois pour tous les groupes dans chaque itération.

« L’entrepôt est un seul grand contexte, de sorte que de nombreux groupes de robots auront des aspects partagés du problème plus vaste. Nous avons conçu notre architecture pour tirer parti de ces informations communes« , ajoute-t-elle.

Ils ont testé leur technique dans plusieurs environnements simulés, y compris ceux configurés comme des entrepôts, avec des obstacles aléatoires et des environnements en forme de labyrinthe simulant des bâtiments intérieurs.

En identifiant des groupes plus efficaces pour la décongestion, leur approche de l’apprentissage décongestionne l’entrepôt jusqu’à quatre fois plus rapidement que les approches non basées sur l’apprentissage fortes. Même lorsqu’ils ont tenu compte de tête de calcul supplémentaire du réseau neuronal, leur approche a encore résolu le problème 3,5 fois plus rapidement.

Dans l’avenir, les chercheurs souhaitent dériver des méthodes basées sur des règles simples à partir de leur modèle neuronal, car les décisions du réseau neuronal peuvent être opaques et difficiles à interpréter. Des méthodes plus simples, basées sur des règles, pourraient également être plus faciles à mettre en œuvre et à entretenir dans des environnements réels d’entrepôt

Article: « NEURAL NEIGHBORHOOD SEARCH FOR MULTI-AGENT PATH FINDING » – https://openreview.net/pdf?id=2NpAw2QJBY