Riepilogo Tecnico: Scalare la Pianificazione Epistemica Multi-Agente attraverso Euristiche Derivate da GNN

Definizione del Problema

La Pianificazione Epistemica Multi-Agente (MEP) è un framework per il ragionamento su azioni fisiche e sulle credenze di più agenti. A differenza della pianificazione classica, la MEP richiede che gli stati siano rappresentati come strutture di Kripke (grafi orientati, diretti e con etichette) per catturare complessi rapporti di credenza e conoscenza di ordine superiore. Questa rappresentazione introduce due sfide primarie che ne ostacolano la scalabilità:

1. Complessità Intrinseca: Applicare transizioni e valutare formule all'interno di stati epistemici (e-state) è computazionalmente più oneroso rispetto alla pianificazione classica.
2. Mancanza di Euristiche Efficaci: I solver MEP esistenti spesso si affidano a una ricerca non informata (ad es., Breadth-First Search) poiché le euristiche efficaci sono scarse. Man mano che la lunghezza del piano aumenta, lo spazio di ricerca cresce esponenzialmente, portando all'intrattabilità. Sebbene alcuni lavori recenti (ad es., H-EFP) abbiano tentato di integrare le euristiche utilizzando costrutti di pianificazione tradizionali come i grafi di pianificazione, pochi approcci affrontano la scalabilità della MEP attraverso metodi basati sui dati.

Metodologia

Gli autori propongono un approccio basato sui dati per generare euristiche per la MEP utilizzando Reti Neurali a Grafo (GNN). L'idea centrale è quella di addestrare un regressore basato su GNN per approssimare l' "euristica perfetta" — stimando la distanza da un dato stato epistemico verso lo stato obiettivo più vicino.

1. Rappresentazione dello Stato e Embedding

Poiché gli e-state sono naturalmente strutturati come grafi (modelli di Kripke), le GNN sono state selezionate per la loro capacità di catturare strutture relazionali. Il documento investiga tre strategie per codificare i "mondi" (nodi) all'interno di una struttura di Kripke in vettori numerici adatti all'input delle GNN:

• Mappatura dell'ID Simbolico: Assegna interi sequenziali ai mondi in base all'ordine di generazione; è computazionalmente economico ma perde la similarità semantica tra i mondi e non è invariante tra le diverse esecuzioni.
• Codifica basata su Hash: Applica una funzione di hash alle interpretazioni dei mondi e agli indici di ripetizione. Ciò garantisce identificatori coerenti tra le esecuzioni e offre un equilibrio tra la preservazione delle informazioni e l'efficienza computazionale.
• Codifica Bitmask: Rappresenta i mondi come vettori binari che codificano i fluenti e gli indici di ripetizione. Preserva l'informazione logica ma comporta costi computazionali più elevati e richiede modelli più grandi per la convergenza.

Per garantire che le euristiche generalizzino attraverso diverse condizioni di obiettivo, gli autori estendono l'embedding dello stato includendo una codifica compatta dell'obiettivo. Ciò crea un grafo unificato dove "nodi di stato" e "nodi obiettivo" sono connessi, permettendo al modello di apprendere le dipendenze tra lo stato corrente e le specifiche condizioni di obiettivo.

2. Pipeline di Generazione dei Dati

I dati di addestramento vengono generati offline utilizzando una Ricerca in Profondità (DFS) modificata all'interno del planner deep (una riimplementazione del planner EFP allo stato dell'arte).

• Il planner esplora lo spazio degli stati fino a un limite di profondità.
• Raggiunto un obiettivo, l'algoritmo effettua il backtracking, assegnando a ogni e-state visitato un'etichetta corrispondente alla sua distanza dall'obiettivo più vicino.
• Per gestire l'esplosione combinatoria dello spazio di ricerca, il processo di generazione impiega la potatura probabilistica dei rami, l'ordinamento casuale delle azioni e controlli sui duplicati degli stati.
• Gli stati irraggiungibili vengono scartati per evitare etichette spurie, e la distribuzione delle classi di distanza è bilanciata per evitare bias verso piani brevi.

3. Architettura del Modello

Il regressore neurale è implementato in PyTorch utilizzando PyTorch Geometric. L'architettura consiste in:

• Embedding Bitwise: Gli identificatori dei nodi (vettori bit) e gli attributi degli archi vengono proiettati in embedding densi tramite Percettri Multistrato (MLP).
• Passaggio di Messaggi Relazionali: Due livelli di GINEConv (Graph Isomorphism Network con Edge Convolution) aggregano le informazioni dai vicini, incorporando esplicitamente gli attributi degli archi per gestire le dipendenze modali eterogenee.
• Riassunto a Livello di Grafo: Il pooling medio aggrega gli embedding dei nodi in una rappresentazione del grafo a dimensione fissa.
• Testa di Regressione Residua Profonda: Una sequenza di blocchi residui elabora l'embedding del grafo, restituendo una stima della distanza normalizzata tramite una funzione sigmoide.

4. Integrazione nella Ricerca

La GNN addestrata è integrata nella pipeline di pianificazione per guidare una Ricerca Heuristics-First (HFS). Gli autori valutano anche una variante, HFS*, che aumenta l'euristica predetta $h(s)$ con la profondità di ricerca $d(s)$ per formare un punteggio totale $f(s) = h(s) + d(s)$, ispirato all'algoritmo A*.

Contributi Chiave

Il documento delinea quattro contributi primari:

1. Confronto degli Embedding: Una definizione formale e un confronto empirico di tre embedding di strutture di Kripke (ID Simbolico, Hash, Bitmask) per l'input delle GNN, identificando la codifica basata su hash come il compromesso più efficace.
2. Pipeline Automatizzata: Un sistema completamente automatizzato per la generazione dei dati di addestramento (coppie stato-distanza) e l'addestramento del regressore GNN specificamente per l'ambiente MEP.
3. Integrazione: L'integrazione del regressore GNN nel planner deep per valutare gli e-state e guidare il processo di ricerca.
4. Valutazione Esaustiva: Un benchmarking approfondito dell'approccio rispetto alla ricerca non informata (BFS) e ai pianificatori basati su euristiche esistenti (H-EFP) attraverso molteplici domini standard.

Risultati Sperimentali

La valutazione è stata condotta su benchmark MEP standard (ad es., Collaboration and Communication, Selective Communication, Grapevine) utilizzando un timeout di 600 secondi.

• Scalabilità vs Ricerca Non Informata: La ricerca guidata dalla GNN ha ridotto significativamente il numero di nodi espansi rispetto alla Breadth-First Search (BFS) nella maggior parte dei domini. Ad esempio, nel dominio Collaboration and Communication (CC), l'approccio GNN ha espanso circa 65 nodi in media rispetto ai 610 della BFS, risolvendo lo stesso numero di istanze.
• Strategia di Ricerca: La variante HFS* (che combina euristica e profondità) ha superato la HFS standard, risolvendo circa il 32% di istanze in più e riducendo i nodi espansi.
• Generalizzazione: I modelli addestrati su dati raccolti da più domini (CC e GR) hanno dimostrato la capacità di generalizzare a domini non visti, superando la baseline BFS in termini di espansione dei nodi.
• Confronto con H-EFP: L'approccio GNN è risultato competitivo con le migliori euristiche individuali del planner H-EFP (specificamente l'euristica $S\_PG$), risolvendo l'85,33% delle istanze di test rispetto all'intervallo 49–82% di H-EFP a seconda dell'euristica specifica utilizzata.
• Limitazioni di Runtime: Il documento nota che, sebbene la GNN riduca lo spazio di ricerca (nodi espansi), l'attuale implementazione manca di ottimizzazioni per l'inferenza batch (ad es., batching CUDA). Di conseguenza, i tempi di risoluzione grezzi non sono ancora competitivi con le euristiche tradizionali, sebbene gli autori sostengano che l'informatività dell'euristica sia la metrica primaria per la scalabilità in questo contesto.

Significato e Rivendicazioni

Gli autori posizionano questo lavoro come un passo fondamentale nell'integrazione del Machine Learning con la Pianificazione Epistemica Multi-Agente. Essi affermano che:

• Scarsità di Euristiche: La MEP soffre della mancanza di euristiche efficaci rispetto alla pianificazione classica. Questo lavoro dimostra che le GNN possono apprendere con successo l'approssimazione di euristiche perfette in questo scenario complesso basato su grafi.
• Efficienza Basata sui Dati: Trattando ogni e-state come un segnale di addestramento indipendente invece di fare affidamento su intere traiettorie, l'approccio genera grandi dataset in modo efficiente, consentendo l'apprendimento di pattern significativi dalla struttura relazionale dei modelli di Kripke.
• Complementarità: Gli autori non pretendono che le GNN sostituiscano immediatamente le euristiche esistenti. Sostengono invece che le euristiche basate su GNN fungano da potente strumento complementare per potenziare la copertura dei solver, specialmente quando integrate in approcci basati su portfolio dove diverse euristiche possono compensare le debolezze l'una dell'altra.

Il documento conclude che, sebbene siano necessarie ottimizzazioni ingegneristiche (come l'elaborazione batch) per rendere le prestazioni di runtime competitive, la riduzione della complessità dello spazio di ricerca dimostra la validità delle euristiche basate sull'apprendimento per scalare la MEP.