Technische Samenvatting: Tensor-Coord

Probleemstelling

Large Language Models (LLM's) vertonen fundamentele beperkingen in multi-agent planning, primair door een kloof tussen generatieve vloeiendheid en gestructureerd redeneren. Hoewel LLM's plausibele individuele plannen kunnen genereren, ontbreekt het hen aan de deterministische status-tracking en systematische zoekcapaciteiten die vereist zijn voor gecoördineerde actie. Wanneer meerdere agenten onafhankelijk plannen, resulteren hun plannen vaak in collectieve inconsistenties, zoals ruimtelijke botsingen, resource-concurrentie en temporele deadlocks.

Bestaande coördinatiebenaderingen slagen er niet effectief in dit aan te pakken:

• Joint Prompting: Het concateneren van alle agent-contexten overschrijdt praktische contextvensters naarmate de gezamenlijke actieruimte exponentieel groeit ($|A|^N$).
• Sequential Planning: Introduceert ordeningsbias en kan circulaire afhankelijkheden niet oplossen.
• Klassieke Algoritmen (bijv. Conflict-Based Search): Vereisen formele domeinspecificaties (PDDL) die de natuurlijke taalflexibiliteit van LLM's tenietdoen.

De kernuitdaging is het detecteren en oplossen van coördinatiefouten in door LLM's gegenereerde gezamenlijke plannen zonder te vertrouven op domeinspecifieke regels of formele state-space modellen.

Methodologie: Tensor-Coord Framework

Het paper introduceert Tensor-Coord, een framework dat het gezamenlijke plan van $N$ agenten codeert als een derde-orde tensor $\mathbf{T} \in \mathbb{R}^{N \times T \times A}$ (Agents $\times$ Tijdstappen $\times$ Acties) en multilineaire algebra toepast om latente coördinatiestructuren te ontdekken.

1. Soft Tensor Representatie

Om numerieke stabiliteit en volledige multilineaire rang te garanderen, vermijdt het framework harde binaire codering. In plaats daarvan gebruikt het een Soft Plan Tensor:
$$\mathcal{T}(i, t, k) = \gamma \cdot \mathbb{1}[a_i^t = a_k] + \frac{1-\gamma}{K-1} \cdot \mathbb{1}[a_i^t \neq a_k]$$
waarbij $\gamma$ een betrouwbaarheidsparameter is (bijv. 0.8). Dit wijst een hoge waarschijnlijkheid toe aan de gekozen actie en verdeelt de rest over andere acties, waardoor de dominante structuur behouden blijft terwijl rank-deficiëntie wordt voorkomen.

2. Canonical Polyadic (CP) Decompositie & Complexiteitsmetriek

Het framework past CP-decompositie toe om de tensor te factoriseren in een som van rank-één componenten:
$$\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r \cdot \mathbf{u}_r \otimes \mathbf{v}_r \otimes \mathbf{w}_r$$

• Theoretisch Inzicht: Als agenten onafhankelijk zijn, is de tensor-rang $R^*$ gelijk aan het aantal agenten $N$. Als $R^* > N$, vertegenwoordigt de overtollige rang de interacties tussen agenten (koppeling).
• Coördinatie Complexiteitsmetriek ($CC$): Gedefinieerd als $CC(\Pi) = \frac{R^* - N}{N}$.
  • $CC(\Pi) = 0$ impliceert wederzijdse onafhankelijkheid (geen conflicten mogelijk).
  • $CC(\Pi) > 0$ impliceert statistische afhankelijkheid en de noodzaak van coördinatie.

3. Residual-Based Conflict Detectie

De decompositie-residue $\mathbf{E} = \mathcal{T} - \mathcal{T}_{R^*}$ vangt gedrag op dat niet verklaard wordt door onafhankelijke threads.

• Conflict Score: $CS(i, j, t) = \rho(i, t) \cdot \rho(j, t)$, waarbij $\rho(i, t) = \|\mathbf{E}(i, t, :)\|_2$.
• Mechanisme: Hoge residuen bij zowel agent $i$ als $j$ op hetzelfde tijdstip $t$ duiden op een coördinatiefout (bijv. een botsing) die het onafhankelijke model niet kan verklaren. Dit lokaliseert conflicten algebraïsch zonder domeinspecifieke regels.

4. Tucker Decompositie voor Interpreteerbaarheid

Om herplanning te sturen, gebruikt het framework Tucker-decompositie ($\mathcal{T} \approx \mathcal{G} \times_1 \mathbf{U} \times_2 \mathbf{V} \times_3 \mathbf{W}$) om interpreteerbare factoren te extraheren:

• $\mathbf{U}$ (Agent Rollen): Clustert agenten met vergelijkbare coördinatierollen.
• $\mathbf{V}$ (Temporele Fasen): Identificeert kritieke coördinatievensters.
• $\mathbf{W}$ (Actie Types): Groepeert functioneel equivalente acties.
  Deze factoren worden vertaald naar Natural Language Constraints (bijv. "VERMIJD positie (x,y) op tijdstip t" of "SYNCHRONISEER bij fasegrens") om iteratieve LLM-herplanning te sturen.

5. Iteratief Algoritme

Het systeem werkt in een lus:

1. LLM's genereren initiële plannen.
2. Plannen worden gecodeerd in een soft tensor.
3. CP-decompositie berekent $R^*$ en de residue $\mathbf{E}$.
4. Conflicten worden gelokaliseerd via de residue score.
5. Tucker-factoren genereren specifieke natuurlijke taalbeperkingen.
6. Beperkingen worden teruggevoerd naar de LLM's voor herplanning.
7. De lus herhaalt zich tot convergentie of maximale iteraties.

Belangrijkste Bijdragen

1. Tensor Formulering: Een soft encoding van gezamenlijke plannen die stabiele multilineaire decompositie mogelijk maakt.
2. Algebraïsche Complexiteitsmetriek: De eerste berekenbare, algebraïsch onderbouwde maatstaf voor coördinatiecomplexiteit ($CC$), die bewijst dat $R^*=N$ noodzakelijk en voldoende is voor plan-onafhankelijkheid.
3. Domein-Agnostische Conflict Detectie: Een op residuen gebaseerde methode die conflicten algebraïsch lokaliseert in de agent $\times$ tijdstip $\times$ actie ruimte zonder expliciete botsingsregels te vereisen.
4. Interpreteerbare Structuur Extractie: Het gebruik van Tucker-decompositie om agent-rollen, temporele fasen en actieclusters af te leiden voor het genereren van actiegerichte beperkingen.
5. Iteratief Verfijningsalgoritme: Een framework dat hoge convergentiesnelheden bereikt bij multi-robot leveringstaken.

Experimentele Resultaten

Experimenten werden uitgevoerd op multi-robot leveringstaken in grid-werelden (5x5 en 6x6) met 2 tot 5 agenten.

• Convergentiesnelheden:
  • Easy (2 agenten): 100% convergentie (gem. 1.4 iteraties).
  • Medium (3 agenten): 80% convergentie (gem. 3.2 iteraties).
  • Hard (4 agenten): 60% convergentie (gem. 4.0 iteraties).
  • Very Hard (5 agenten): 20% convergentie (hoge congestie beperkt de resolutie).
• Scaling Law: De minimale CP-rang schaalt lineair met het aantal agenten: $R^*(N) \approx 3.9 \cdot N + 0.5$ ($R^2 = 0.94$), wat de betrouwbaarheid van de metriek als complexiteitsvoorspeller bevestigt.
• Baseline Vergelijking: Tensor-Coord presteerde significant beter dan Independent Planning, Round-Robin sequentiële planning en Single-LLM Joint prompting. Het was de enige methode die in staat was om door iteratieve verfijning tot nul conflicten te komen, met name in scenario's met gemiddelde complexiteit.

Betekenis en Claims

Het paper claimt dat Tensor-Coord de kloof overbrugt tussen de natuurlijke taalflexibiliteit van LLM's en de rigoureuze vereisten van multi-agent coördinatie. Door coördinatie te behandelen als een algebraïsch probleem van tensor-rang, biedt het framework:

• Een kwantificeerbare maatstaf voor de moeilijkheidsgraad van planning ($CC$) die voorheen ontbrak in LLM multi-agent systemen.
• Een geprincieerd mechanisme voor conflictdetectie dat niet afhankelijk is van handmatig ontworpen domeinregels, waardoor het toepasbaar is in diverse omgevingen.
• Een demonstratie dat algebraïsche decompositie effectief kan sturen om complexe coördinatiefouten op te lossen die standaard prompting-strategieën niet kunnen oplossen.

De auteurs merken op dat hoewel de aanpak hoge succespercentages bereikt op behapbare problemen, het uitdagingen ondervindt in zeer gecongesteerde omgevingen (bijv. 5 agenten op een 6x6 grid) waar interacties tussen beperkingen kunnen leiden tot niet-monotone convergentie. Toekomstig werk wordt voorgesteld om hiërarchische decompositie voor grotere aantallen agenten en minimale conflict-oplossende beperkingssets aan te pakken.