Sintesi Tecnica: Tensor-Coord

Definizione del Problema

I Large Language Models (LLM) mostrano limitazioni fondamentali nella pianificazione multi-agente, principalmente a causa di un divario tra la fluidità generativa e il ragionamento strutturato. Sebbene gli LLM possano generare piani individuali plausibili, essi mancano del tracciamento deterministico dello stato e delle capacità di ricerca sistematica necessarie per l'azione coordinata. Quando più agenti pianificano indipendentemente, i loro piani spesso risultano in inconsistenze collettive, come collisioni spaziali, contesa delle risorse e deadlock temporali.

Gli approcci di coordinamento esistenti non affrontano questo problema efficacemente:

• Joint Prompting: La concatenazione di tutti i contesti degli agenti eccede le finestre di contesto pratiche man mano che lo spazio delle azioni congiunte cresce esponenzialmente ($|A|^N$).
• Pianificazione Sequenziale: Introduce un bias di ordinamento e non può risolvere dipendenze circolari.
• Algoritmi Classici (es. Conflict-Based Search): Richiedono specifiche di dominio formali (PDDL) che negano la flessibilità del linguaggio naturale degli LLM.

La sfida centrale è rilevare e risolvere i fallimenti di coordinamento nei piani congiunti generati da LLM senza fare affidamento su regole specifiche del dominio o modelli di spazio di stato formali.

Metodologia: Framework Tensor-Coord

Il documento introduce Tensor-Coord, un framework che codifica il piano congiunto di $N$ agenti come un tensore di terzo ordine $\mathbf{T} \in \mathbb{R}^{N \times T \times A}$ (Agenti $\times$ Timesteps $\times$ Azioni) e applica l'algebra multilineare per scoprire strutture di coordinamento latenti.

1. Rappresentazione Tensoriale Soft

Per garantire la stabilità numerica e il rango multilineare completo, il framework evita la codifica binaria rigida. Utilizza invece un 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]$$
dove $\gamma$ è un parametro di confidenza (es. 0.8). Questo assegna un'alta probabilità all'azione scelta e distribuisce il resto tra le altre azioni, preservando la struttura dominante pur evitando la deficienza di rango.

2. Decomposizione Canonica (CP) e Metrica di Complessità

Il framework applica la decomposizione CP per fattorizzare il tensore in una somma di componenti di rango uno:
$$\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r \cdot \mathbf{u}_r \otimes \mathbf{v}_r \otimes \mathbf{w}_r$$

• Intuizione Teorica: Se gli agenti sono indipendenti, il rango del tensore $R^*$ è uguale al numero di agenti $N$. Se $R^* > N$, l'eccedenza di rango rappresenta le dipendenze inter-agente (accoppiamento).
• Metrica di Complessità di Coordinamento ($CC$): Definita come $CC(\Pi) = \frac{R^* - N}{N}$.
  • $CC(\Pi) = 0$ implica mutua indipendenza (nessun conflitto possibile).
  • $CC(\Pi) > 0$ implica dipendenza statistica e la necessità di coordinamento.

3. Rilevamento dei Conflitti basato sui Residui

Il residuo della decomposizione $\mathbf{E} = \mathcal{T} - \mathcal{T}_{R^*}$ cattura il comportamento non spiegato dai thread indipendenti.

• Punteggio di Conflitto: $CS(i, j, t) = \rho(i, t) \cdot \rho(j, t)$, dove $\rho(i, t) = \|\mathbf{E}(i, t, :)\|_2$.
• Meccanismo: Alti residui in entrambi gli agenti $i$ e $j$ allo stesso istante temporale $t$ indicano un fallimento di coordinamento (es. una collisione) che il modello indipendente non può spiegare. Questo localizza i conflitti algebricamente senza regole specifiche del dominio.

4. Decomposizione Tucker per l'Interpretabilità

Per guidare la ri-pianificazione, il framework utilizza la decomposizione Tucker ($\mathcal{T} \approx \mathcal{G} \times_1 \mathbf{U} \times_2 \mathbf{V} \times_3 \mathbf{W}$) per estrarre fattori interpretabili:

• $\mathbf{U}$ (Ruoli degli Agenti): Raggruppa gli agenti con ruoli di coordinamento simili.
• $\mathbf{V}$ (Fasi Temporali): Identifica finestre critiche di coordinamento.
• $\mathbf{W}$ (Tipi di Azione): Raggruppa azioni funzionalmente equivalenti.
  Questi fattori vengono tradotti in Vincoli in Linguaggio Naturale (es. "EVITA posizione (x,y) al timestep t" o "SINCRONIZZA alla fase di confine") per guidare la ri-pianificazione iterativa dell'LLM.

5. Algoritmo Iterativo

Il sistema opera in un ciclo:

1. Gli LLM generano i piani iniziali.
2. I piani vengono codificati in un tensore soft.
3. La decomposizione CP calcola $R^*$ e il residuo $\mathbf{E}$.
4. I conflitti vengono localizzati tramite il punteggio del residuo.
5. I fattori Tucker generano vincoli specifici in linguaggio naturale.
6. I vincoli vengono reimmessi negli LLM per la ri-pianificazione.
7. Il ciclo si ripete fino alla convergenza o al massimo numero di iterazioni.

Contributi Chiave

1. Formulazione Tensoriale: Una codifica soft di piani congiunti che consente una decomposizione multilineare stabile.
2. Metrica di Complessità Algebrica: La prima misura computabile e fondata algebricamente della complessità di coordinamento ($CC$), provando che $R^*=N$ è necessario e sufficiente per l'indipendenza del piano.
3. Rilevamento dei Conflitti Domain-Agnostic: Un metodo basato sui residui che localizza algebricamente i conflitti nello spazio agente $\times$ istante temporale $\times$ azione senza richiedere esplicite regole di collisione.
4. Estrazione di Strutture Interpretabili: Utilizzo della decomposizione Tucker per derivare ruoli degli agenti, fasi temporali e cluster di azioni per generare vincoli azionabili.
5. Algoritmo di Raffinamento Iterativo: Un framework che raggiunge alti tassi di convergenza in compiti di consegna multi-robot.

Risultati Sperimentali

Gli esperimenti sono stati condotti su compiti di consegna multi-robot in mondi a griglia (5x5 e 6x6) con 2 a 5 agenti.

• Tassi di Convergenza:
  • Facile (2 agenti): 100% di convergenza (media 1.4 iterazioni).
  • Medio (3 agenti): 80% di convergenza (media 3.2 iterazioni).
  • Difficile (4 agenti): 60% di convergenza (media 4.0 iterazioni).
  • Molto Difficile (5 agenti): 20% di convergenza (l'alta congestione limita la risoluzione).
• Legge di Scalabilità: Il rango CP minimo scala linearmente con il numero di agenti: $R^*(N) \approx 3.9 \cdot N + 0.5$ ($R^2 = 0.94$), confermando l'affidabilità della metrica come predittore di complessità.
• Confronto con i Baseline: Tensor-Coord ha superato significativamente la Pianificazione Indipendente, la Pianificazione Sequenziale Round-Robin e il Joint Prompting con Singolo-LLM. È stato l'unico metodo capace di raggiungere lo zero conflitti attraverso il raffinamento iterativo, in particolare in scenari di media complessità.

Significato e Assertions

Il documento afferma che Tensor-Coord colma il divario tra la flessibilità del linguaggio naturale degli LLM e i requisiti rigorosi del coordinamento multi-agente. Trattando il coordinamento come un problema algebrico di rango tensoriale, il framework:

• Fornisce una misura quantificabile della difficoltà di pianificazione ($CC$) precedentemente assente nei sistemi multi-agente basati su LLM.
• Offre un meccanismo principato per il rilevamento dei conflitti che non dipende da regole di dominio predefinite, rendendolo applicabile a diversi ambienti.
• Dimostra che la decomposizione algebrica può guidare efficacemente gli LLM a risolvere complessi fallimenti di coordinamento che le strategie di prompting standard non riescono a gestire.

Gli autori osservano che, sebbene l'approccio raggiunga alti tassi di successo su problemi trattabili, affronta sfide in ambienti altamente congestionati (es. 5 agenti su una griglia 6x6) dove le interazioni tra i vincoli possono portare a una convergenza non monotona. Il lavoro futuro proposto mira ad affrontare la decomposizione gerarchica per un numero maggiore di agenti e l'individuazione di set di vincoli minimi per la risoluzione dei conflitti.