Technische Samenvatting: Primitive-Guided Tree Search in Multi-Agent Pursuit-Evasion Games

1. Probleemformulering

Het artikel behandelt de uitdaging van het berekenen van Nash-evenwichtspolicies in multi-agent Pursuit-Evasion Games (PEGs) op grafen. In deze spellen probeert een team van Pursuers (Rood) een team van Evaders (Blauw) te vangen voordat de Evaders de aangewezen exit-nodes bereiken. De kern van de moeilijkheid ligt in de exponentiële groei van de gezamenlijke toestands- en actieruimtes naarmate het aantal agenten toeneemt.

Bestaande benaderingen kampen met een trade-off:

• Offline methoden (bijv. PSRO, MAPPO) trainen policies offline, maar missen vaak de aanpassingsvermogen aan adversariële gedragingen die niet tijdens de training zijn gezien en lijden onder een hoge trainingscomplexiteit.
• Online planning methoden (bijv. MCTS) passen zich aan de huidige toestanden aan, maar worstelen met de enorme vertakkingsfactoren (branching factors) die inherent zijn aan simultane multi-agent spellen, waardoor diepe zoekopdrachten computationeel onhaalbaar worden.
• Hybride methoden (bijv. AlphaZero-varianten) vertrouwen vaak op het leren van nauwkeurige waarde/policy-approximaties die uitgebreide data vereisen, of zijn beperkt tot twee-speler settings.

Het doel is om een schaalbaar, robuust framework te ontwikkelen dat de strategische diepte van offline evenwichtsberekening combineert met de aanpasbaarheid van online zoekopdrachten.

2. Methodologie: Primitive-Guided Tree Search (PGTS)

De auteurs stellen Primitive-Guided Tree Search (PGTS) voor, een hybride framework dat het complexe multi-agent spel deelt in behapbare sub-spellen offline en deze oplossingen integreert in een online Simultaneous-Move Monte Carlo Tree Search (SM-MCTS).

2.1 Offline Fase: Primitive Sub-Team Games

In plaats van het volledige spel direct op te lossen, berekent PGTS vooraf de exacte Nash-evenwichten voor kleine, representatieve "primitive" sub-spellen waarbij subsets van agenten betrokken zijn:

• 1v1: Eén Pursuer tegen één Evader.
• 2v1: Twee Pursuers tegen één Evader.
  Deze worden opgelost met Shapley value iteratie op de beperkte toestandsruimtes ($V \times V$ en $V^2 \times V$). De output bevat optimale mixed policies ($\pi^*$) en functies voor de waarde ($V^*$) voor deze primitives, die worden gecached voor gebruik tijdens runtime.

2.2 Online Fase: Tree Search

Op elk tijdstip voert PGTS een tree search uit vanaf de huidige gezamenlijke toestand. Het algoritme wijzigt standaard SM-MCTS op twee cruciale manieren:

1. Primitive-Guided Expansion:
   Om de exponentiële vertakkingsfactor te beperken, breidt het algoritme niet alle mogelijke gezamenlijke acties uit. In plaats daarvan gebruikt het de offline primitive policies om de zoekopdracht te sturen:

• Voor elke Evader identificeert het algoritme de $k_r$ dichtstbijzijnde Pursuers.
• Het samplet gezamenlijke acties voor lokale interacties (1v1 en 2v1 groepen) op basis van de vooraf berekende Nash-policies ($\pi^*_{1v1}, \pi^*_{2v1}$).
• Deze samples vormen een beperkte kandidaat-actieset, aangevuld met heuristische kortste-pad-acties en random exploratie om overmatige focus op priors te voorkomen.

2. Leaf Value Estimation via Sub-team Surrogates:
   In plaats van dure Monte Carlo rollouts naar de horizon uit te voeren, schat het algoritme de waarde van leaf nodes in met behulp van de offline primitive waarde-functies.

• Het algoritme benadert de waarde van het volledige spel door de huidige toestand te ontleden in een set van primitive sub-teams.
• Het hanteert een sequentiële matching strategie: Eerst koppelt het algoritme agenten greedily om 2v1 interacties te vormen (wat hogere-orde coördinatie zoals gezamenlijke trapping vangt) met behulp van het Hongaarse algoritme op de 2v1 waarde-matrix.
• Overgebleven agenten worden gekoppeld in 1v1 interacties.
• De leaf waarde is de geaggregeerde som van deze primitive waarden, waardoor de zoekopdracht kan eindigen op ondiepere dieptes terwijl nauwkeurige resultaat-schattingen behouden blijven.

2.3 Actie Selectie

Het framework ondersteunt twee selectie-operators voor het doorlopen van de boom:

• Regret Matching (RM): Past regret matching toe op de geschatte matrix game bij elke node om mixed policies te berekenen.
• Decoupled UCT (DUCT): Past Upper Confidence Bounds onafhankelijk toe op de marginale actiewaarden van elk team.

3. Belangrijkste Bijdragen

• Hybride Framework: De introductie van PGTS, dat uniek de exacte offline Nash-oplossingen van kleine sub-games integreert in een online tree search voor multi-agent coördinatie.
• Gestructureerde Expansie: Een mechanisme om vertakkingsfactoren te verminderen door acties te samplen op basis van strategische priors afgeleid van offline evenwichtsberekeningen, in plaats van willekeurige of puur heuristische sampling.
• Schaalbare Leaf Evaluatie: Een surrogaat waarde-schattingsmethode die gebruikmaakt van offline primitive waarde-functies en een sequentiële matching algoritme (waarbij 2v1 prioriteit krijgt boven 1v1) om leaf nodes te evalueren zonder diepe rollouts.
• Behoud van Coördinatie: In tegenstelling tot eenvoudige decompositie-methoden die sub-teams onafhankelijk behandelen, behoudt PGTS coördinatie op teamniveau door gezamenlijke actie-rollouts uit te voeren in de volledige actieruimte, gestuurd door de primitives.

4. Experimentele Resultaten

De auteurs evalueerden PGTS op vier topologieën: twee 7x7 grids (Easy/Hard), een 200-node Scotland Yard graaf, en een 151-node real-world Atlanta graaf. Het Pursuer-team werd getest tegen diverse Evader gedragingen.

Baselines:

• MT-PSRO: Multi-Task Policy Space Response Oracles (learning-based).
• NSGZero: Neural-guided MCTS voor netwerkbeveiliging.
• Decomposition: Een baseline die enkel de sub-team decompositie gebruikt zonder tree search.
• Intercepting: Een heuristische kortste-pad baseline.

Bevindingen:

• Robuustheid: PGTS (zowel RM als DUCT varianten) behaalde consistent de hoogste Worst-Case Utility (WCU) over alle topologieën, waarbij het significant beter presteerde dan de learning-based baselines (MT-PSRO, NSGZero) die tekenen van overfitting vertoonden op shortest-path Evaders.
• Coördinatie: PGTS presteerde beter dan de pure "Decomposition" baseline, wat aantoont dat de tree search component effectief de team-level coördinatie vangt die statische decompositie mist.
• Ablatie: Het verwijderen van de primitive-guided expansie of de 2v1 primitives resulteerde in significante prestatieverliezen, vooral op grotere, complexe grafen (Scotland Yard, Atlanta), wat de noodzaak van beide componenten voor effectieve exploratie en waarde-estimatie bevestigt.

5. Betekenis en Claims

Het artikel claimt dat PGTS een schaalbare oplossing biedt voor de "curse of dimensionality" in multi-agent PEGs. Door gebruik te maken van exacte oplossingen voor kleine, terugkerende lokale interacties (primitives) om een globale zoekopdracht te sturen, bereikt de methode:

1. Computationele Tractabiliteit: Het beheert de vertakkingsfactor en de zoekdiepte effectief.
2. Aanpasbaarheid: Het behoudt het vermogen om over gecoördineerde policies te redeneren in de volledige gezamenlijke actieruimte, in tegen tegenover statische decompositie.
3. Robuustheid: Het presteert goed tegen diverse adversariële strategieën, inclusief strategieën die niet tijdens een trainingsfase zijn gezien, omdat het steunt op speltheoretische principes in plaats van geleerde distributies.

De auteurs concluderen dat deze aanpak de kloof overbrugt tussen de theoretische optimaliteit van offline evenwichtsberekening en de praktische aanpasbaarheid van online planning, en daarmee een robuust framework biedt voor multi-agent besluitvorming in adversariële omgevingen. Toekomstig werk wordt gesuggereerd om dit uit te breiden naar partial observability en bredere multi-agent spelklassen.