Technische Samenvatting: Leren lokaal communiceren voor grootschalige multi-agent padvinding

Probleemstelling

Multi-Agent Pathfinding (MAPF) is een fundamentele abstractie voor het coördineren van meerdere homogene agenten in gedeelde omgevingen, zoals geautomatiseerde magazijnen of vlootten van autonome voertuigen. Het doel is om individuele plannen te berekenen voor $n$ agenten om van start- naar doelvertices te bewegen op een graaf zonder botsingen (vertex- of randconflicten). Hoewel er optimale MAPF-oplossers bestaan, is het probleem NP-moeilijk en verslechtert de schaalbaarheid snel naarmate het aantal agenten toeneemt.

Gedecentraliseerde benaderingen, waarbij agenten beslissingen nemen op basis van lokale waarnemingen, bieden een weg naar schaalbaarheid, maar worstelen vaak met de kwaliteit van de coördinatie. Recentere op leren gebaseerde methoden, zoals MAPF-GPT, hebben sterke resultaten geboekt met imitatielearning (IL) op grote datasets. Deze modellen missen echter doorgaans expliciete inter-agent communicatie en vertrouwen uitsluitend op lokale waarnemingen om collaboratief gedrag af te leiden. Bestaande op communicatie gebaseerde gedecentraliseerde methoden beperken interactie vaak tot een enkele ronde van uitwisseling van lokale waarnemingen, wat mogelijk onvoldoende is om complexe conflicten in dichte omgevingen op te lossen.

Methodologie: LC-MAPF

De auteurs stellen LC-MAPF (Local Communication for Multi-agent Pathfinding) voor, een gedecentraliseerd, op leren gebaseerd kader dat een leerbaar, meertraps communicatiemodule introduceert om de agentcoördinatie te verbeteren.

Architectuur

Het model is gebouwd op een Transformer-gebaseerde architectuur met ongeveer 3 miljoen parameters. De werkstroom voor elke agent $u$ op tijdstap $t$ omvat:

1. Waarnemingscodering: Agenten ontvangen een gestructureerde lokale waarneming $o^t_u$, getokeniseerd in een sequentie die kosten-naar-go-matrices, zelfkenmerken (positie, doel, greedy-actie, geschiedenis) en kenmerken van de $k$ dichtstbijzijnde buren bevat. Dit wordt ingebed in een sequentie $X_{0,u}$.
2. Latente statcompressie: Om communicatieschaalbaarheid onafhankelijk van de waarnemingsgrootte te garanderen, verwerkt een Transformer-encoder de invoer en comprimeert een "latente bottleneck" (geïnspireerd op de Perceiver-architectuur) de gecodeerde tokens tot een compacte latente staat $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$.
3. Iteratieve communicatie: Agenten voeren $R_{comm}$ rondes lokale communicatie uit (standaard $R_{comm}=4$).
   • In elke ronde $r$ ontvangt een agent berichten van zijn buren (en zichzelf).
   • Een decoder fuseert de latente staat $z_u$ van de agent met de ontvangen buurberichten $C^r_u$.
   • Een berichtkop genereert een bijgewerkt berichtvector $m^r_u$ om in de volgende ronde te worden verzonden.
   • Cruciaal: berichten worden niet gesuperviseerd. Het netwerk leert welke informatie noodzakelijk is om de uiteindelijke actieverlies te minimaliseren via backpropagation, waardoor communicatiestrategieën op natuurlijke wijze ontstaan.
4. Actievoorspelling: Na de laatste communicatieronde voert een voorspellingskop actie-logits uit, die worden omgezet in een waarschijnlijkheidsverdeling voor actiekeuze.

Training

LC-MAPF wordt getraind via Imitatielearning met behulp van expertdemonstraties. De trainingsdataset bestaat uit ongeveer 750 miljoen waarneming-actieparen afgeleid van een centrale solver (LaCAM*) over diverse kaarttypes (Labyrinten, Random, Huis). Het doel is om de cross-entropy-verlies tussen de voorspelde acties en de expertacties te minimaliseren. Er wordt geen expliciete supervisie geboden voor de communicatiemessages; het model leert uitsluitend te communiceren om de collectieve actiekwaliteit te verbeteren.

Belangrijkste bijdragen

1. Nieuw communicatiekader: De introductie van LC-MAPF, een kader dat agenten in staat stelt te communiceren met uitsluitend expertactie-demonstraties, zonder dat expliciete communicatielabels of supervisie vereist zijn.
2. State-of-the-art prestaties: Een Transformer-model met 3 miljoen parameters dat een nieuwe state-of-the-art zet onder leerbare gedecentraliseerde MAPF-oplossers, en dat bestaande IL- en Reinforcement Learning (RL)-benaderingen (inclusief MAPF-GPT, SCRIMP, DCC en MAGAT-varianten) overtreft op diverse metrieken en kaarttopologieën.
3. Schaalbaarheid met communicatie: Het aantonen dat het voorgestelde meertraps communicatiemechanisme lineaire schaalbaarheid behoudt naarmate het aantal agenten groeit, waarmee een veelvoorkomende bottleneck in op communicatie gebaseerde oplossers wordt aangepakt.
4. Ablatie- en robuustheidsanalyse: Uitgebreide studies die aantonen dat:
   • Meertraps communicatie (specifiek 4 rondes) cruciaal is voor hoge succespercentages.
   • Het systeem robuust is tegen berichtfalen (tot 50% ruis) in kleinere agentpopulaties.
   • Het beperken van de communicatienabijheidsomvang de prestaties in dichte scenario's aanzienlijk verslechtert.

Experimentele resultaten

Experimenten werden uitgevoerd op de POGEMA-benchmark, die Random, Labyrinten, Magazijn en Steden kaarttypes omvat.

• Succespercentage: LC-MAPF behaalde succespercentages die gelijk waren aan of hoger waren dan alle baselines, inclusief de 85M-parameter MAPF-GPT, over alle kaarttypes en agentaantallen (tot 256 agenten in standaardtests, en tot 5.000 agenten in grootschalige evaluaties).
• Oplossingskwaliteit: In termen van Som-van-Kosten (SoC) relatief tot de centrale optimale planner (LaCAM*), behaalde LC-MAPF consequent de beste of bijna beste verhoudingen.
• Schaalbaarheid: In grootschalige tests met tot 5.000 agenten op 256x256-kaarten behield LC-MAPF lineaire schaalbaarheid, met voorspelbaar toenemende rekentijden (bijv. ~0,12s/stap voor 1.000 agenten tot ~0,65s/stap voor 5.000 agenten).
• Implementatie in de echte wereld: De auteurs hebben LC-MAPF succesvol ingezet op een fysiek multi-robotplatform (aangepaste JetBots) in een modulaire labyrintomgeving. Door discrete planning te koppelen aan continue controle (met behulp van rotatie/wacht-synchronisatie), coördineerden de agenten succesvol om doelen te bereiken zonder botsingen, waarmee de praktische toepasbaarheid van de methode werd gevalideerd.

Betekenis en claims

Het artikel beweert dat LC-MAPF een aanzienlijke vooruitgang vertegenwoordigt in gedecentraliseerde multi-agent coördinatie door aan te tonen dat effectieve, iteratieve lokale communicatie impliciet kan worden geleerd uit experttrajecten. In tegenstelling tot eerdere methoden die communicatie negeren of vertrouwen op een enkele ronde, gesuperviseerde uitwisselingen, maakt LC-MAPF gebruik van een meertraps, ongesuperviseerd communicatiemechanisme dat agenten in staat stelt dynamisch conflicten te onderhandelen en op te lossen.

De auteurs benadrukken dat deze benadering succesvol oplossingskwaliteit en schaalbaarheid in evenwicht brengt, waarbij de typische trade-off wordt overwonnen waarbij op communicatie gebaseerde methoden last hebben van computatief knelpunten. De resultaten suggereren dat LC-MAPF dient als een generaliseerbaar voorgeïnstalleerd model dat diverse, ongezichte omgevingen en grootschalige agentpopulaties aankan, en een robuuste oplossing biedt voor real-world robottoepassingen zoals logistiek en zoek- en reddingsoperaties.