Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO

Panoramica del Problema

L'esplorazione robotica extraterrestre richiede sempre più spesso l'uso di squadre robotiche eterogenee (ad esempio, rover, droni, robot a zampe) dotate di capacità diverse (strumenti scientifici, locomozione specifica). La sfida principale risiede nel coordinare efficientemente questi agenti per massimizzare l'utilizzo delle risorse e il valore scientifico estratto.
I problemi chiave includono:

1. Assegnazione dei compiti e pianificazione del percorso: Determinare quale robot esegue quale compito e in quale ordine, considerando le abilità specifiche di ciascun robot (alcuni compiti richiedono abilità multiple, tipo "AND", altri una sola, tipo "OR").
2. Scalabilità: Gli algoritmi di pianificazione classici (es. ricerca esaustiva, programmazione intera) soffrono di una crescita combinatoria esponenziale al crescere del numero di robot e target, rendendo i tempi di calcolo troppo lunghi per l'uso in tempo reale, specialmente su hardware con risorse limitate come i rover spaziali.
3. Ambienti dinamici: Le missioni spaziali comportano incertezze (nuovi target, guasti, cambiamenti del terreno) che richiedono un replanning (ripianificazione) online rapido senza ritardi nelle comunicazioni.

Metodologia

Gli autori propongono un approccio basato sull'apprendimento per rinforzo multi-agente (MARL) utilizzando l'algoritmo MAPPO (Multi-Agent Proximal Policy Optimization).

• Ambiente di Addestramento:
  • Simulato come una griglia 2D discreta.
  • Gli agenti (robot) possono muoversi in 4 direzioni o restare fermi.
  • I target richiedono insiemi specifici di abilità. Un target è risolto se un agente con l'abilità necessaria (tipo OR) o tutti gli agenti con le abilità necessarie (tipo AND) si trovano nella stessa cella del target.
• Osservazioni:
  • Ogni agente riceve un vettore di osservazione che include: posizioni relative di tutti gli agenti e target, insiemi di abilità degli agenti e dei target, e il tipo di target (AND/OR).
  • La struttura dell'osservazione è fissa per numero di agenti e target, semplificando l'input per la rete neurale.
• Architettura della Rete:
  • Utilizza una struttura Actor-Critic.
  • Critic: Centralizzato, riceve le osservazioni concatenate di tutti gli agenti per apprendere una funzione di valore congiunta.
  • Actor: Decentralizzato, ogni agente ha la propria politica che decide le azioni basandosi sulle sue osservazioni locali.
  • Le reti includono unità ricorrenti (GRU) per gestire la dipendenza temporale.
• Funzione di Ricompensa:
  • È composta da diversi termini ponderati:
    • Attraction Reward (AR): Guida gli agenti verso i target non risolti.
    • Target Reward (TR): Ricompensa fissa per ogni target risolto.
    • Wrong Target Cost (WC): Penalità se un agente si muove su un target senza le abilità necessarie.
    • Step Cost (SC) & Solve Time Cost (TC): Penalità per i movimenti e per il tempo impiegato, per incentivare l'efficienza.
    • Terminal Bonus (TB): Ricompensa finale per la risoluzione completa dell'ambiente.
• Strategia di Addestramento:
  • Divisa in due fasi: Bootstrap (gli agenti imparano a navigare verso i target) e Refinement (imparano a risolvere i target in modo efficiente minimizzando i costi).
  • L'addestramento avviene su un ambiente virtuale, mentre l'inferenza è eseguita in tempo reale.

Contributi Chiave

1. Framework Unificato: Sviluppo di una strategia di pianificazione collaborativa basata su MAPPO che unifica in un unico solver l'allocazione dei compiti, la pianificazione del percorso e la schedulazione per squadre eterogenee.
2. Scalabilità e Prestazioni: Dimostrazione che il metodo basato su apprendimento supera le limitazioni di scala degli algoritmi esatti, spostando il carico computazionale dal tempo di esecuzione (runtime) al tempo di addestramento.
3. Capacità di Replanning Online: Validazione della capacità del sistema di adattarsi dinamicamente a nuovi target scoperti durante la missione, sostituendo i target risolti con nuovi nell'buffer di osservazione.
4. Open Source: Rilascio del framework di apprendimento per la comunità scientifica.

Risultati Sperimentali

Gli esperimenti sono stati condotti su mappe 32x32 con 3 agenti e un numero variabile di target (da 5 a 7).

• Confronto con Soluzioni Ottimali:
  • Il metodo RL è stato confrontato con soluzioni ottimali ottenute tramite ricerca esaustiva (Exhaustive Search - ES).
  • Success Rate: Oltre il 90% di successo nella risoluzione degli ambienti.
  • Qualità della Soluzione: Le politiche apprese raggiungono fino all'86% dell'ottimalità rispetto al tempo di risoluzione e fino al 92% rispetto allo sforzo totale del team (movimenti complessivi) rispetto alla soluzione ottima.
  • Si nota che la politica tende a privilegiare la minimizzazione dello sforzo collettivo rispetto alla velocità assoluta, a causa dei pesi delle ricompense scelti.
• Tempi di Inferenza:
  • Il tempo di inferenza della politica RL è costante (O(1)) e indipendente dal numero di target o agenti, rendendolo ideale per sistemi embedded con risorse limitate.
  • Al contrario, il tempo di inferenza della ricerca esaustiva cresce esponenzialmente.
  • Il tempo di addestramento RL è significativamente più alto, ma è un costo "una tantum" che non influenza l'esecuzione in tempo reale.
• Replanning:
  • Il sistema è stato testato con l'aggiunta dinamica di nuovi target durante l'esecuzione. I risultati mostrano che la politica mantiene prestazioni simili anche senza un addestramento specifico su scenari di replanning, dimostrando robustezza.

Significato e Limitazioni

Significato:
Questo lavoro rappresenta un passo critico verso la pianificazione robotica in tempo reale per missioni spaziali autonome. Spostando la complessità computazionale nella fase di addestramento, permette a robot con hardware limitato di prendere decisioni collaborative complesse in millisecondi, gestendo scenari dinamici che gli algoritmi classici non potrebbero risolvere in tempo utile.

Limitazioni e Futuro:

• Dimensione Fissa delle Osservazioni: L'architettura attuale richiede un numero fisso di agenti e target durante l'addestramento, limitando la scalabilità a scenari con dimensioni variabili.
• Sensibilità ai Parametri: La sintonizzazione delle ricompense diventa più difficile all'aumentare della complessità del problema.
• Direzioni Future: Gli autori suggeriscono l'uso di Graph Neural Networks (GNN) o modelli del mondo (come in DreamerV3) per creare rappresentazioni delle osservazioni indipendenti dal numero di entità, permettendo a una singola politica di generalizzare su squadre di dimensioni diverse.