RecherchearXiv cs.RO 18 août 2026

Algorithme d'enchères-consensus par groupes pour l'allocation décentralisée de tâches en systèmes multi-robots

1 source couvre ce sujet·Source originale ↗·

Résumé IASource uniqueImpact UE

Des chercheurs présentent l'algorithme GACA (Grouping Auction-Consensus Algorithm), une nouvelle méthode décentralisée pour l'allocation de tâches entre robots (MRTA, multi-robot task allocation), détaillée dans un article publié sur arXiv le 18 août 2026. GACA reprend l'architecture en deux phases enchère-consensus du CBBA (Consensus-Based Bundle Algorithm), la référence décentralisée la plus utilisée dans le domaine, mais en refond entièrement le mécanisme d'enchère : plutôt que de faire miser les robots tâche par tâche, l'algorithme regroupe d'abord les tâches spatialement proches via un prétraitement par plus proche voisin, puis les agents négocient des actions au niveau du groupe entier, partiel, ou contesté. Les auteurs comparent GACA à CBBA sur la classe de problèmes MT-SR-IA, avec un programme linéaire en nombres entiers mixtes comme référence d'optimalité absolue. Sur quatre tailles d'essaim et 4 000 mondes de test, GACA atteint une optimalité médiane d'environ 97 %, contre 81 à 84 % pour CBBA, tout en convergeant en un nombre égal ou inférieur d'itérations. Un test de passage à l'échelle supplémentaire, portant sur 3 280 instances avec des essaims de 5 à 20 agents et des lots de 10 à 50 tâches, confirme que ces gains se maintiennent.

L'enjeu dépasse la seule performance chiffrée : CBBA souffre d'un défaut structurel bien identifié dans la littérature, son critère d'enchère individuel est mal aligné avec l'objectif min-somme de minimiser la distance totale parcourue par l'équipe, ce qui produit des allocations sous-optimales dès que les tâches sont dispersées dans l'espace. En reformulant la mise aux enchères au niveau de groupes de tâches plutôt que de tâches isolées, GACA cible directement ce défaut sans sacrifier la décentralisation ni la robustesse aux pannes, des propriétés critiques pour les flottes d'AMR en entrepôt, les essaims de drones ou les opérations de recherche et sauvetage où aucune coordination centrale n'est disponible. Pour les intégrateurs et équipes robotique travaillant sur la coordination de flottes, ce résultat suggère qu'un gain d'optimalité substantiel est atteignable sans complexifier l'infrastructure de communication ni renoncer au temps de convergence.

Le travail s'inscrit dans la lignée directe des algorithmes d'enchères consensuelles initiés par CBBA, largement adopté depuis plus d'une décennie comme base de référence pour l'allocation décentralisée de tâches. L'article ne mentionne pas de déploiement matériel réel ni de partenaire industriel : il s'agit d'une contribution algorithmique validée en simulation à grande échelle, avec un MILP comme borne d'optimalité, plutôt que d'un produit ou pilote commercial. Les auteurs ne précisent pas de calendrier de mise en œuvre sur robots physiques ni d'intégration dans une plateforme existante, ce qui positionne GACA comme une avancée de recherche à surveiller pour une future adoption dans des systèmes multi-robots réels plutôt qu'une solution prête à déployer.

Dans nos dossiers

arXiv cs.RO

À lire aussi

1arXiv cs.RO

Algorithme d'enchères consensuelles à stratégie d'enchère apprise pour systèmes multi-robots

Une équipe de chercheurs a publié sur arXiv (ref. 2605.21932) une approche hybride pour l'allocation décentralisée de tâches en flotte robotique : remplacer le mécanisme d'enchères déterministe du CBBA (Consensus-Based Bundle Algorithm) par une politique d'enchères neuronale entraînée par apprentissage par renforcement. Le CBBA, algorithme de référence en coordination multi-robots, garantit une convergence prouvable mais repose sur des fonctions de score heuristiques codées à la main, souvent sous-optimales face à des scénarios complexes. Les auteurs entraînent leur politique avec PPO (Proximal Policy Optimization), en calibrant les récompenses sur la proximité aux solutions globalement optimales obtenues par programmation linéaire en nombres entiers mixtes (MILP). Trois architectures neuronales sont comparées : un Neural Additive Model (NAM), un LSTM et un Set Transformer. Les expériences couvrent plusieurs tailles de flotte et confirment que les politiques apprises améliorent systématiquement la qualité d'allocation par rapport au CBBA classique, tout en conservant une exécution entièrement décentralisée. Le résultat structurellement important est que ce cadre CTDE (Centralized Training, Decentralized Execution) permet aux robots d'enchérir sur des tâches à partir d'observations locales partielles, sans communication globale à l'exécution. Pour les intégrateurs déployant des flottes en entrepôt ou en logistique industrielle, c'est un signal concret : les heuristiques codées manuellement, longtemps standard de fait, peuvent être surpassées par des politiques apprises sans sacrifier les garanties de coordination décentralisée. La capacité à tenir à l'échelle sur différentes tailles de flotte est particulièrement notable, les approches MARL pures souffrant souvent d'une instabilité d'entraînement croissante avec le nombre d'agents. Le CBBA est issu des travaux de Choi et al. (2009) et reste une référence dans les systèmes multi-robots décentralisés, notamment pour les drones et les AMR industriels. L'hybridation RL et algorithmes de coordination classiques s'inscrit dans un axe de recherche actif, face à deux alternatives concurrentes : les approches MARL pures (scalabilité difficile) et les méthodes d'optimisation combinatoire centralisée (inadaptées au temps réel). Cette publication reste une contribution académique sans déploiement annoncé ni partenaire industriel identifié, mais elle pose une base méthodologique pour des flottes hétérogènes plus larges. Les suites naturelles seraient la validation sur robots physiques et l'extension à des contraintes temporelles explicites, comme des tâches avec fenêtres de temps ou des dépendances séquentielles.

RecherchePaper

1 source

2arXiv cs.RO

Agir face à l'invisible : filtrage collaboratif sans communication pour l'allocation décentralisée de tâches multi-robots

Des chercheurs ont présenté sur arXiv (2605.25584) un cadre théorique et algorithmique baptisé Zero-Knowledge MRTA (ZK-MRTA), conçu pour l'allocation de tâches dans des équipes de robots sans aucune communication inter-agent, sans modèle de tâche préalable et sans coordinateur central. Dans ce régime, chaque robot ne dispose que d'une vue partielle et bruitée du flux public des résultats de ses coéquipiers. L'algorithme proposé, SwarmCF, exploite une structure cachée de faible rang (low-rank) qui gouverne l'adéquation entre chaque robot et chaque type de tâche, en appliquant du filtrage collaboratif en ligne, le même principe mathématique que les systèmes de recommandation Netflix ou Spotify. Les expériences montrent que SwarmCF récupère environ 80 % des performances d'un système centralisé avec communication complète, et maintient cet avantage même sous contention de capacité 1 (chaque tâche assignée à un seul robot à la fois). L'enjeu théorique est substantiel: les auteurs prouvent formellement que tout algorithme sans structure est coincé au plancher d'erreur de la moyenne a priori sur les paires (robot, tâche) jamais tentées, tandis que SwarmCF atteint une complexité d'échantillonnage par robot en Theta(d) au lieu de Theta(n), où d est le rang de la structure latente et n le nombre total de tâches, typiquement d est très inférieur à n. Cette séparation est catégorielle, pas un simple facteur constant. Pour les intégrateurs de flottes robotiques (entrepôts AMR, inspection industrielle, agriculture), cela signifie qu'une flotte hétérogène peut s'auto-organiser sur des tâches inédites sans infrastructure de communication, ce qui réduit la complexité système et améliore la résilience aux pannes réseau. Le scaling est positif: la compétence par robot sur les tâches non vues augmente avec la taille de l'équipe. Le problème d'allocation multi-robots (MRTA) est étudié depuis les années 2000, avec des approches classiques comme les enchères distribuées (CBBA), les méthodes à base de marché ou les algorithmes de consensus qui supposent toutes un canal de communication fiable. ZK-MRTA s'attaque au cas extrême opposé, commun dans les déploiements industriels réels (réseaux dégradés, robots hétérogènes sans protocole commun) mais largement ignoré en théorie. Côté concurrence, des travaux récents sur le multi-armed bandit collaboratif ou le federated reinforcement learning adressent des problèmes voisins mais supposent soit une communication périodique, soit un modèle de récompense partagé. La prochaine étape naturelle serait de valider SwarmCF sur des flottes physiques, notamment dans des contextes entrepôts ou de manipulation, où le sim-to-real gap reste la principale inconnue pour les méthodes fondées sur l'observation passive de coéquipiers.

RecherchePaper

1 source

3arXiv cs.RO

Évaluation embarquée de la fusion d'admissions de tâches dans les systèmes multi-robots décentralisés

Une équipe de chercheurs a évalué l'« admission par coalescence » des tâches dans les systèmes multi-robots décentralisés, c'est-à-dire le fait de regrouper les nouvelles tâches avant de relancer l'allocateur, au lieu de lancer une allocation à chaque arrivée. L'étude s'appuie sur quatre algorithmes d'allocation (CBAA, ACBBA, PI et HIPC) et sur trois volets expérimentaux. Une campagne de 3 000 missions tourne sur un NVIDIA Jetson AGX Orin avec délai de calcul mesuré, complétée par 3 000 missions appariées sans coût de calcul. Une campagne de 96 missions en hardware-in-the-loop utilise un microcontrôleur RP2040 sur robot Pololu 3pi+. L'admission immédiate (Eager) est comparée à des seuils de 2, 4 et 8 tâches, et à une politique à 4 tâches assortie d'un délai d'attente maximal de 10 s, sous trois cadences d'arrivée. Sur l'AGX, la coalescence réduit à la fois le nombre d'appels à l'allocateur et la charge processeur dans 31 des 48 conditions évaluées, avec une ampleur variable selon l'algorithme. Le regroupement par lots de 4 tâches fait grimper la latence moyenne des cibles en ligne de 20,08 à 23,57 s en arrivées clairsemées, surtout à cause de l'attente avant admission. La variante bornée dans le temps réduit le travail moyen dans dix des douze combinaisons allocateur-charge. Pour HIPC en arrivées denses, elle le baisse de 19,35 % pour 1,40 s de latence moyenne en plus. Le résultat le plus parlant concerne le matériel contraint. Sur quatre scénarios HIPC à cadence moyenne appariés, le seuil de 4 tâches (Count b=4) réduit le travail moyen sur RP2040 de 59,85 % et la latence de service de 39,47 %. Les cas équivalents sur AGX voient au contraire la latence augmenter de 27,69 %. Le regroupement n'est donc pas une optimisation universelle. Son intérêt dépend de l'intensité des arrivées, du comportement propre à chaque allocateur et du coût relatif du calcul sur la plateforme d'exécution. Pour les intégrateurs de flottes hétérogènes, la conséquence est directe : la politique d'admission doit être réglée selon le calculateur embarqué, et non figée dans l'algorithme. Quand le processeur est le goulot, calculer moins souvent peut même raccourcir le service. Sur une machine puissante comme l'Orin, attendre coûte davantage que ce que l'on économise. Un bémol : il s'agit d'une évaluation de laboratoire, avec peu de scénarios matériels (96 missions) et des benchmarks d'allocateurs académiques, sans flotte industrielle réelle. Ce travail s'inscrit dans la littérature de l'allocation de tâches multi-robots (MRTA). CBAA et ACBBA relèvent de la famille des algorithmes à consensus basés sur les enchères, et PI (Performance Impact) et HIPC servent de références de comparaison. Cette littérature mesure souvent la qualité de l'affectation en négligeant le coût de calcul sur le robot, alors que les flottes réelles mêlent des calculateurs très inégaux, de la carte GPU embarquée au microcontrôleur à quelques euros. L'étude répond à cet écart en quantifiant l'arbitrage entre travail de l'allocateur et latence de service. Les suites logiques seraient des politiques d'admission adaptatives, ajustant seuil et délai à la charge et aux ressources disponibles, ainsi que des validations sur des flottes plus grandes et des missions en conditions réelles. L'article, publié sur arXiv (2610.09187), ne mentionne aucun pilote industriel ni calendrier de déploiement.

UEPas d\'impact direct sur la France/UE

RecherchePaper

1 source

4arXiv cs.RO

Optimisation bicouche par colonies de fourmis pour l'allocation et le routage de tâches multi-robots en livraison

Une équipe de recherche propose dans un article publié sur arXiv (référence 2608.17416v1, soumis le 19 août 2026) un nouvel algorithme pour résoudre le problème d'allocation de tâches multi-robots (MRTA), central pour la logistique et la livraison. La méthode repose sur une fonction de coût inédite qui unifie en un seul problème d'optimisation l'attribution des tâches et le calcul des trajectoires, jusqu'ici souvent traités séparément. Les auteurs y adossent un algorithme d'optimisation par colonies de fourmis à double couche (bi-layer ACO), où deux niveaux de décision interdépendants, l'un pour l'affectation des tâches, l'autre pour le routage, sont résolus simultanément au sein d'un même processus de colonie. Comparé à deux méthodes de référence, la programmation linéaire en nombres entiers mixtes (MILP) et l'optimisation par essaims particulaires (PSO), ce bi-layer ACO réduit la distance totale parcourue jusqu'à 17,7% et le temps total de complétion des tâches de près de 20%, et ce sur toutes les tailles de scénarios testées. Ces gains, bien que mesurés en simulation et non en déploiement réel, ciblent un point de friction concret pour les opérateurs de flottes de robots de livraison et d'AMR en entrepôt: la plupart des solveurs actuels séparent la phase d'allocation des tâches de celle du routage, ce qui génère des trajectoires sous-optimales une fois les tâches figées. En traitant les deux dimensions comme un seul problème d'optimisation, l'approche s'attaque directement à ce goulot d'étranglement algorithmique, avec un intérêt direct pour les intégrateurs qui cherchent à réduire les coûts opérationnels et les délais de cycle sur des flottes de robots partagant un même espace de travail. Le MRTA est un problème NP-difficile étudié depuis des années en robotique et recherche opérationnelle, où le MILP garantit l'optimalité mais passe mal à l'échelle, tandis que les métaheuristiques comme le PSO ou les colonies de fourmis offrent un compromis vitesse/qualité pour de grandes flottes. L'article positionne son architecture à double couche comme une alternative plus scalable que ces deux familles de méthodes. Aucun déploiement industriel ni partenariat n'est mentionné à ce stade: il s'agit d'un travail de recherche algorithmique, dont la prochaine étape logique serait une validation sur des scénarios réels avec des contraintes physiques et de communication supplémentaires.

RecherchePaper

1 source