Technische Samenvatting: DISPATCH - Decentralized Informed Spatial Planning and Assignment of Tasks for Cooperative Heterogeneous Agents

Probleemstelling

Het artikel behandelt de uitdaging van ruimtelijke taakallocatie in heterogene multi-agent systemen, specifiek binnen domeinen zoals multi-robot levering, zoek- en reddingsoperaties en milieumonitoring. Het kernprobleem betreft het coördineren van $N$ heterogene agenten om $m$ ruimtelijk verdeelde taken te bedienen onder partiële observeerbaarheid.

Belangrijke beperkingen en kenmerken zijn:

• Heterogeniteit: Agenten beschikken over verschillende serviceniveaus (vaardigheidsniveaus), en taken hebben variërende werklasten, belangweights en urgentie. Compatibiliteit wordt gemodelleerd via preferentievectoren.
• Ruimtelijke Kosten: Agenten moeten navigeren door complexe 2D-omgevingen met obstakels, waarbij reis-kosten en tijdsvertragingen worden in rekening gebracht.
• Trade-off tussen Rechtvaardigheid en Efficiëntie: Greedy of puur op efficiëntie gerichte beleidsregels (bijv. het minimaliseren van de totale afstand) leiden vaak tot onrechtmatige service, waarbij sommige taken snelle, hoogwaardige service ontvangen terwijl andere te maken krijgen met lange vertragingen of slechte matches.
• Partiële Observeerbaarheid: Agenten hebben geen toegang tot globale staatinformatie; zij nemen alleen entiteiten waar binnen een lokale sensorradius.

Bestaande benaderingen gaan vaak uit van centrale coördinatie met volledige globale informatie of vertrouwen op reward shaping zonder een rigoureus evenwichtsgebaseerd rechtvaardigheidsreferentiepunt. Dit artikel tracht de kloof te overbruggen tussen de Eisenberg–Gale (EG) evenwichtstheorie (die Pareto-efficiëntie en envy-freeness garandeert) en gedecentraliseerd, partieel observeerbaar multi-agent leren.

Methodologie

De auteurs stellen twee complementaire algoritmen voor die rechtvaardigheid en efficiëntie integreren:

1. EG-MARL (Centralized Training, Decentralized Execution)

Dit framework maakt gebruik van een CTDE (Centralized Training with Decentralized Execution) architectuur.

• Trainingsfase: Een centrale critic heeft toegang tot de globale staat en lost een ruimtelijk aangepast Eisenberg–Gale (EG) convex programma op. Dit programma maximaliseert de gewogen som van logaritmische utiliteiten, waarbij de utiliteit wordt gedefinieerd als een functie van de agent-taak preferentie en een afstand-gedisconteerde factor ($uji = (\alpha d_{ij}) \cdot \text{preference}_{ji}$). De oplossing van dit programma dient als een "leraar" of supervisiesignaal.
• Executiefase: Agenten opereren onafhankelijk met behulp van alleen lokale observaties. Zij maken gebruik van een Graph Neural Network (GNN) om lokale agent-entiteit grafen te verwerken (die buren, taken en obstakels representeren) om gedecentraliseerde beleidsregels te leren.
• Reward Shaping: Het leerproces wordt gestuurd door een samengestelde reward die exploratiebonussen, workload progressie, voltooiingsbonussen en een specifieke fairness shaping term bevat, afgeleid van de EG-toewijzingsdoelen.

2. Stochastic Online Assignment

Dit is een coöperatief explore-and-assign mechanisme dat is ontworpen voor settings met centrale communicatie (als een sterke online baseline).

• Mechanisme: Agenten verkennen de omgeving coöperatief met behulp van een grid-gebaseerde samplingstrategie. Wanneer een drempelwaarde $k$ van nieuwe taken is ontdekt, voert het algoritme een subset-gebaseerde toewijzing uit.
• Proces: Het enumereert subsets van momenteel vrije agenten, lost het EG-optimalisatieprobleem voor elke subset op tegen de ontdekte taken, en selecteert de subset die het evenwichtsobjectief maximaliseert. Toegewezen agenten bedienen onmiddellijk hun doelen, terwijl anderen doorgaan met het verkennen.
• Doel: Hoewel computationeel duur vanwege de combinatorische enumeratie ($O\binom{N}{k}$), biedt het een benchmark voor hoe dicht gedecentraliseerde beleidsregels bij een online, centraal gecoördineerde EG-oplossing kunnen komen.

Belangrijkste Bijdragen

1. Spatial-Aware Eisenberg–Gale Framework: De auteurs breiden het klassieke EG-framework uit door ruimtelijke reiskosten in de utiliteitsformulering op te nemen, waardoor de evenwichtstheorie effectief wordt verbonden met belichaamde multi-agent taakallocatie.
2. EG-MARL Algoritme: Een nieuw CTDE-framework dat graph-gebaseerde beleidsregels integreert met ruimtelijk bewuste EG-toewijzingen. Dit stelt agenten in staat om gedecentraliseerde beleidsregels te leren die gezamenlijk rechtvaardigheid en reis-efficiëntie optimaliseren onder partiële observeerbaarheid, geleid door het EG-evenwicht.
3. Stochastic Online Assignment: Een coöperatief mechanisme dat geleide exploratie en subset-gebaseerde eerlijke toewijzing uitvoert in realtime terwijl taken worden ontdekt, wat een centrale baseline vormt voor online fairness-efficiency trade-offs.
4. Empirische Validatie: De aanpak wordt gevalideerd in Multi-Agent Particle Environment (MPE) simulaties over variërende teamgroottes (3 tot 15 agenten) en een Webots-gebaseerde magazijn proof-of-concept met heterogene robots (bijv. Summit-XL, TurtleBot3, Pioneer).

Experimentele Resultaten

De evaluatie vergelijkt EG-MARL en de Stochastic Online methode met centrale baselines: Centralized EG, Hungarian Algorithm (utilitair optimum) en Min-Max Distance (equity-focused).

• Regret: EG-MARL bereikt een lage regret (het gat tussen gedecentraliseerde en centrale EG-objectieven), met name voor kleinere teams. Naarmate de teamgrootte toeneemt, groeit de regret, maar blijft het competitief.
• Fairness: Zowel EG-MARL als de Online methode presteren consistent beter dan de Hungarian en Min-Max baselines in fairness-metrieken (Coefficient of Variation en de Jain's Fairness Index). De EG-gebaseerde methoden bereiken meer gebalanceerde taakuitkomsten, geclusterd in de "upper-left" regio van de fairness-efficiency trade-off curve (hoge rechtvaardigheid, lage voltooiingstijd).
• Efficiëntie: EG-MARL bereikt de snelste voltooiingstijden in de meeste configuraties (N=7, 10), en presteert vaak beter dan de centrale EG-oplossing qua snelheid, hoewel dit soms ten koste gaat van een iets hogere totale reisafstand.
• Ablatie-studies: Het verwijderen van de EG fairness-shaping reward of de exploratie-reward leidt tot een verslechterde rechtvaardigheid en langere voltooiingstijden, wat de noodzaak van de evenwichtsgestuurde rewardstructuur bevestigt.
• Webots Validatie: In een realistische magazijnscenario met heterogene robots demonstreerde de centrale EG-toewijzing de sterkste algemene balans, waarbij de hoogste rechtvaardigheidsscores behaalde terwijl competitieve voltooiingstijden werden behouden in vergelijking met de Hungarian en Min-Max methoden.

Betekenis en Claims

Het artikel claimt dat ruimtelijk bewuste EG-formuleringen effectief de gedecentraliseerde coördinatie kunnen sturen van agenten met heterogene capaciteiten.

• Theoretische Brug: Het werk legt een verbinding tussen het EG evenwicht convex programma en gedecentraliseerd, partieel observeerbaar multi-agent leren, en toont aan dat evenwichtsconcepten effectieve supervisie-signalen kunnen dienen voor leren.
• Praktische Balans: De resultaten suggereren dat gedecentraliseerde agenten Pareto-efficiënte en rechtvaardigheidsbewuste uitkomsten kunnen benaderen zonder afhankelijk te zijn van globale staatinformatie.
• Beperkingen: De auteurs merken bescheiden op dat de Stochastic Online Assignment computationeel intensief is voor grote teams vanwege de combinatorische enumeratie en bedoeld is primair als een baseline in plaats van een schaalbare deployment oplossing. Ze erkennen ook dat het EG-MARL framework een empirisch geleide leerbenadering is in plaats van een theoretisch benaderingsalgoritme voor de onderliggende Dec-POMDP.

De studie concludeert dat hoewel pure efficiëntie vaak ongelijkheid creëert, het integreren van evenwichtsgebaseerde rechtvaardigheid in gedecentraliseerd leren multi-agent systemen in staat stelt een robuust evenwicht te bereiken tussen servicekwaliteit en operationele efficiëntie in dynamische, ruimtelijke omgevingen.