fr.wedoany.com Rapport : Une équipe de recherche chinoise a proposé un nouveau paradigme nommé DPCN (Decentralized-Planning-Centralized-Negotiation) pour résoudre le problème de planification de trajectoire multi-agents (MAPF). Ce paradigme, tout en conservant l’extensibilité des méthodes décentralisées, traite efficacement les conflits dynamiques grâce à un mécanisme de négociation centralisé, obtenant des performances supérieures aux méthodes d’apprentissage par renforcement existantes sur des benchmarks standards.
La planification de trajectoire multi-agents vise à planifier des trajectoires sans conflit pour plusieurs agents dans un environnement partagé, et est largement utilisée dans des domaines tels que l’entreposage automatisé, la gestion des robots de service et la logistique aéroportuaire. Les stratégies de planification centralisées traditionnelles excellent sur les problèmes à petite échelle, mais la complexité de calcul augmente considérablement face à des équipes d’agents à grande échelle. Les méthodes décentralisées basées sur l’apprentissage par renforcement, bien qu’extensibles et adaptables à l’environnement, sont limitées par leur champ de vision local, ce qui peut entraîner des blocages, des collisions, voire des interblocages.
Le DPCN divise chaque pas de temps en deux phases : dans la phase de planification, chaque agent génère indépendamment une intention d’action basée sur les informations d’observation locale o_i^t (champ de vision de 3×3) ; dans la phase de négociation, le système détecte tous les conflits potentiels (y compris les conflits de sommet et les conflits d’échange) et regroupe dynamiquement les agents impliqués dans des conflits en « super-agents ». Grâce au réseau PNSE (Pointer Network Special Edition) apprenable, un « gagnant » est sélectionné parmi l’ensemble des conflits en fonction de l’état de l’environnement pour exécuter son intention originale, tandis que les autres agents restent immobiles ou rééchantillonnent une nouvelle action.
Face aux difficultés liées à l’incohérence des ensembles d’actions des super-agents et à l’entraînement dynamique, le réseau PNSE, inspiré des réseaux de pointeurs, peut traiter des entrées de longueur variable et des espaces d’actions incohérents. L’équipe de recherche a proposé un mécanisme d’entraînement par apprentissage par renforcement avec gradient de politique personnalisé, utilisant une approximation de champ moyen pour une répartition équitable des récompenses globales, permettant un entraînement efficace des super-agents dynamiques.
Les expériences ont été menées sur des benchmarks MAPF standards et des cartes aléatoires, en comparant deux types de planificateurs centralisés (ODrM*, BALANCE) et trois méthodes RL de pointe (SCRIMP, DCC, PICO). Les expériences sur cartes aléatoires ont utilisé des cartes de taille 30×30 à 100×100, une densité d’obstacles de 0 % à 30 %, et un nombre d’agents de 32 à 256. Chaque configuration a été répétée 200 fois, en rapportant le taux de réussite et le nombre de pas pour accomplir la tâche. Les résultats montrent que le DPCN maintient constamment un taux de réussite élevé et un faible temps de tâche dans les scénarios à haute densité d’obstacles (30 %) et à grande échelle, surpassant non seulement les autres méthodes RL, mais aussi les planificateurs centralisés.
Lors de l’évaluation de la capacité de généralisation sur des cartes structurées, les expériences ont utilisé trois types de cartes typiques : un environnement multi-pièces de taille 32×32 (taille de pièce 3×3), un environnement d’auditorium de 162×141, et un environnement d’entrepôt de 170×84 (largeur des allées de rayonnage de seulement 2 cases), chaque carte contenant 25 instances de problèmes. Le DPCN maintient sa capacité à coordonner efficacement des équipes à grande échelle dans ces structures complexes.
L’équipe de recherche souligne que le DPCN, grâce à son architecture innovante de planification décentralisée et de négociation centralisée, résout efficacement les problèmes de coordination de conflits sous un champ de vision local tout en conservant l’extensibilité. À l’avenir, elle explorera les applications sur des obstacles dynamiques, des agents hétérogènes et des plateformes robotiques réelles.
