Technische Samenvatting: Schaalbare Lange-Termijn Planning met Gestaffelde Updates voor Lifelong MAPF

Probleemdefinitie

Het artikel behandelt Lifelong Multi-Agent Path Finding (LMAPF), een variant van het standaard MAPF-probleem waarbij agenten continu nieuwe doelen ontvangen zodra ze hun huidige doel hebben bereikt. De kernuitdaging is het genereren van botsingsvrije paden voor grote vloten (duizenden agenten) onder strikte realtime-beperkingen, terwijl men temporele myopie (kortzichtigheid) moet vermijden.

Bestaande benaderingen kampen met een afruil tussen schaalbaarheid en lange-termijn redeneren:

• Reactieve planners (bijv. PIBT, EPIBT): Schalen moeiteloos naar duizenden agenten door middel van regelgebaseerde, stap-voor-stap coördinatie, maar lijden aan ernstige temporele myopie, waardoor ze falen in scenario's die anticipatie op toekomstige congestie vereisen (bijv. smalle gangen of vertragingen in taakuitvoering).
• Windowed planners (bijv. RHCR): Plannen over trajecten met meerdere stappen om meer vooruitziendheid te verbeteren, maar veroorzaken aanzienlijke computationele overhead wanneer de gehele vloot simultaan opnieuw wordt gepland, wat de schaalbaarheid belemmert.
• Subset planners (bijv. Token Passing - TP): Schalen door slechts een subset van agenten opnieuw te plannen, maar zijn beperkt tot zeer gestructureerde, "welgevormde" kaarten en kunnen geen algemene topologieën aan.

Het artikel identificeert een gat: er is geen bestaand algoritme dat lange-termijn planning op schaal kan bereiken over algemene kaarten terwijl het ook congestievolle omgevingen en taakuitvoeringsvertragingen (Task Completion Time, TCT) afhandelt.

Methodologie: Padupdates over Gestaffelde Horizonten (PUSH)

De auteurs stellen PUSH voor, een planner die de sterke punten van TP, RHCR en EPIBT synthetiseert. Het bereikt schaalbaarheid door slechts een subset van agenten per tijdstap te plannen, terwijl het lange-termijn redeneren behoudt via gestaffelde vensters.

Kernmechanismen

1. Gestaffelde Subset Planning:

   • In tegenstelling tot RHCR, dat de gehele vloot simultaan opnieuw plant, plant PUSH slechts een subset van agenten ($Q$) per tijdstap opnieuw.
   • Agenten krijgen een time2Replan-teller toegewezen. Wanneer de teller van een agent nul bereikt of het huidige pad een wachten afdwingt, komt de agent in de herplanningswachtrij terecht.
   • Deze gestaffelde aanpak voorkomt de computationele explosie die gepaard gaat met simultane vlootbrede herplanning.

2. Windowed Path Planning met Fallbacks:

   • PUSH onderhoudt een globale set veilige, botsingsvrije fallback-paden ($\Pi$) voor alle agenten.
   • In plaats van volledige paden naar doelen te plannen (zoals bij TP), plannen agenten $W$-stap windowed paden.
   • Als een nieuw plan niet gevonden kan worden, valt een agent terug op zijn bestaande fallback-pad, wat de uitvoering op elk moment botsingsvrij garandeert.

3. Recursieve Prioriteitsovererving en Pushing:

   • Om congestie te beheersen en de kwaliteit van paden te verbeteren, integreert PUSH EPIBT-geïnspireerde prioriteitsovererving.
   • Agenten krijgen globale prioriteiten toegewezen. Wanneer een agent met een hogere prioriteit een pad plant dat conflicteert met een agent met een lagere prioriteit, wordt de agent met de lagere prioriteit "gepusht".
   • De verplaatste agent plant recursief zijn pad opnieuw en erft tijdelijk de hogere prioriteit. Dit gaat door totdat een botsingsvrije oplossing is gevonden of een recursielimiet ($M$) is bereikt.
   • In tegen tegenstelling tot EPIBT, dat beperkt is tot 1-stap of korte-horizon pushes, gebruikt PUSH een aangepaste windowed space-time A* om optimale $W$-stap paden te vinden die met maximaal één agent met een lagere prioriteit conflicteren.

4. Anytime Optimalisatie (LNS):

   • Na de primaire planningscyclus gebruikt PUSH de resterende tijd om een Large Neighborhood Search (LNS) uit te voeren.
   • Het selecteert willekeurig agenten, verwijdert hun paden en probeert ze opnieuw te plannen met een hogere prioriteit om het globale doel te verbeteren (minimaliseren van de afstand tot de doelen).
   • De oplossing wordt alleen geaccepteerd als deze de geaggregeerde afstand tot de doelen verbetert.

Theoretische Garanties

• Volledigheid: PUSH garandeert het teruggeven van botsingsvrije paden voor alle agenten binnen een eindige tijd.
• Deadlock-vrijheid: Onder specifieke condities (biconnected grafen, nul TCT, en "langere verstreken tijd" prioritering), garandeert PUSH dat elke agent zijn doel binnen een eindig aantal tijdstappen bereikt, overeenkomend met de garanties van EPIBT.

Belangrijkste Bijdragen

1. Eerste General-Map Subset Planner: PUSH is het eerste algoritme dat subset planning (voor schaalbaarheid) combineert met lange-termijn windowed planning, toepasbaar op algemene kaartstructuren zonder de topologische restricties van Token Passing.
2. Schaalbare Lange-Termijn Redenering: Het coördineert succesvol vloten van wel 10.000 agenten met multi-step planninghorizonten ($W=10$), een capaciteit die voorheen onbereikbaar was voor algemene kaarten.
3. Robuustheid tegen Congestie en Vertragingen: Door recursieve prioriteitsverplaatsing en gestaffelde updates te integreren, handelt PUSH effectief smalle gangen, diepe doodlopende wegen en stochastische Task Completion Times (TCT) af, waar reactieve planners falen.

Experimentele Resultaten

De auteurs evalueerden PUSH tegenover baselines (RHCR-PBS, EPIBT-LNS, PIBT en een ablatie PUSH-lite) in twee soorten scenario's:

1. TCT Kaarten (Taakvertragingen):

   • Setup: Agenten wachten bij doelen voor $T=20$ tijdstappen.
   • Resultaten: PUSH en PUSH-LNS behaalden de hoogste throughput over alle kaartgroottes (tot 10.000 agenten).
   • Vergelijking: Terwijl EPIBT-LNS een vloeiende schaling behield in open kaarten, verslechterde het aanzienlijk in smalle gangen en dichte obstakels. RHCR verbruikte zijn planningbudget naarmate de congestie toenam. PUSH-LNS vertoonde een throughput-verbetering van 25% ten opzichte van EPIBT-LNS in warehouse-large en 300% in random-32-32-20.

2. Complexe Kaarten (Structurele Beperkingen):

   • Setup: Lange gangen en doodlopende wegen (Symbotic, Delivery kaarten) met $T=0$.
   • Resultaten: PUSH-LNS behaalde de hoogste throughput (bijv. 3.8 in Symbotic).
   • Foutmodi: EPIBT-LNS had moeite met hoge dichtheden in diepe gangen; RHCR liep frequent vast (timeout). De PUSH-lite ablatie (zonder recursieve pushing) leed aan een catastrofale prestatie-instorting bij grote vloten, wat het belang van recursieve prioriteitsverplaatsing onderstreept.

3. Ablatie-studies:

   • TCT Sensitiviteit: PUSH-LNS behield een hoge throughput, zelfs met niet-nul TCT's, terwijl myope planners (EPIBT-LNS) significant verslechterden.
   • Window Grootte ($W$): Het vergroten van $W$ verbeterde de prestaties van PUSH-LNS, waardoor het lange-termijn planning kon benutten zonder computationele instorting. In contrast hiermee stortte de prestatie van EPIBT-LNS in bij $W=7$ door de exponentiële explosie van mogelijke operaties, terwijl RHCR overging op myope planning bij grotere vensters.

Betekenis en Claims

Het artikel claimt dat PUSH de cruciale kloof overbrugt tussen de extreme schaalbaarheid van reactieve planners en de vooruitziendheid van lange-termijn planners. Het wordt gepresenteerd als het eerste LMAPF-algoritme dat in staat is tot:

• Coördinatie van 10.000 agenten met lange-termijn planning.
• Werken op algemene kaartstructuren zonder restrictieve topologische aannames.
• Effectief beheren van congestievolle scenario's en taakuitvoeringsvertragingen die reactieve planners doen falen.

De auteurs positioneren PUSH als een fundamentele stap naar het oplossen van echte industriële uitdagingen (bijv. robotische sorteercentra) die gelijktijdige coördinatie van grote vloten en lange-termijn anticipatie vereisen, een combinatie die voorheen als onhandelbaar werd beschouwd voor algemene kaarten. Voorgestelde toekomstige richtingen omvatten het uitbreiden van het framework naar kinodynamische beperkingen en dynamische venstergrootte.