Sintesi Tecnica: Trust-Gated Predictive Reallocation (TGPR)

Definizione del Problema

L'allocazione di compiti in sistemi multi-robot (MRTA) decentralizzati si basa tipicamente su aste basate sul mercato (ad es., Contract Net Protocol, CBBA) che assumono una consegna affidabile dei messaggi. Nelle implementazioni reali, la comunicazione wireless è soggetta a perdite dovute a attenuazione del segnale, interferenze e, criticamente, degradazione hardware persistente (ad es., antenne usurate, trasmettitori con potenza limitata) che varia da un robot all'altro.

Gli attuali metodi robusti affrontano questo problema riducendo la frequenza dei messaggi o riassegnando i compiti solo dopo che un guasto viene rilevato. Questi approcci trattano l'incertezza della comunicazione come un disturbo di pianificazione da assorbire tramite tentativi di riinvio o riconciliazione periodica, piuttosto che come una quantità apprendibile. Inoltre, i modelli di "fiducia" (trust) esistenti nella MRTA si concentrano sulla capacità di un agente di completare un compito, non sulla affidabilità del collegamento di comunicazione stesso. Ciò porta a due modalità primarie di fallimento in reti con perdita di pacchetti:

1. Starvation (Inedia): Un compito viene assegnato ma l'accuse di ricezione viene persa; il coordinatore attende indefinitamente mentre nessun altro robot interviene.
2. Duplicazione: Il coordinatore va in timeout in attesa di un'accuse di ricezione ritardata (ma non persa) e riassegna il compito, causando l'esecuzione dello stesso compito da parte di due robot.

Metodologia: Trust-Gated Predictive Reallocation (TGPR)

TGPR è un meccanismo d'asta decentralizzato che integra una stima bayesiana per robot della affidabilità del round-trip di comunicazione nel ciclo standard annuncio-offerta-assegnazione-accusa di ricezione. Modifica la logica decisionale del coordinatore senza alterare il protocollo di messaggistica sottostante.

1. Stima della Fiducia del Round-Trip Bayesiana

Il coordinatore mantiene una distribuzione posteriore Beta, $Beta(\alpha_i, \beta_i)$, per ogni robot $i$, che rappresenta la probabilità di un round-trip riuscito tra assegnazione e accusa di ricezione.

• Aggiornamenti: I parametri vengono aggiornati in base agli esiti osservati (successo al tempo $\delta$ o timeout).
• Decadimento: Un fattore di decadimento $\lambda < 1$ consente alla stima di seguire condizioni non stazionarie (ad es., guasti hardware che si sviluppano durante la missione).
• Punteggio di Fiducia (Trust Score): La affidabilità stimata è $\hat{p}_i = \alpha_i / (\alpha_i + \beta_i)$.

2. Valutazione delle Offerte con Sconto di Fiducia

A differenza delle aste standard che classificano i offerenti in base all'utilità grezza ($u_{ij}$), la TGPR classifica i candidati tramite un'utilità scontata dalla fiducia:
$$\hat{u}_{ij} = u_{ij} \cdot \hat{p}_i$$
Questo privilegia i robot che sono sia capaci che raggiungibili, distinguendo tra un robot altamente capace con un collegamento storicamente scarso e un robot leggermente meno capace con un collegamento affidabile.

3. Timeout Predittivo Adattivo

Inveve di un timeout globale fisso, la TGPR calcola un timeout per robot $\tau_i$ basato sulla distribuzione dei ritardi appresa:
$$\tau_i = \text{clip}(\mu_i + z\sigma_i, \tau_{min}, \tau_{max})$$
Questo concede pazienza ai collegamenti storicamente lenti ma affidabili, consentendo al contempo un recupero rapido per i collegamenti che non hanno mai fallito.

4. Rivendicazione Unilaterale del Bystander (Osservatore) con Gate di Confidenza

Per ridurre la latenza di recupero, i robot inattivi che intercettano un annuncio di assegnazione possono rivendicare un compito se la scadenza annunciata scade senza una trasmissione di conferma.

• Meccanismo: Se un bystander rivendica il compito, il coordinatore tenta di annullare il titolare originale.
• Finestra di Grazia (Grace Window): Una breve finestra di grazia impedisce che la rivendicazione del bystander entri in competizione con la logica di fallback del coordinatore, garantendo che la logica di riassegnazione del coordinatore non sia preclusa prematuramente.

Contributi Chiave

1. Design del Testbed: Un simulatore a eventi discreti con un modello di canale che presenta perdita dipendente dalla distanza, jamming transitorio e un fattore di affidabilità hardware persistente e apprendibile ($h_i$) per ogni robot. Gli autori dimostrano che senza questo differenziale persistente, i meccanismi basati sulla fiducia non offrono vantaggi rispetto alle euristiche basate sulla distanza.
2. Algoritmo TGPR: Un nuovo meccanismo d'asta che combina offerte scontate dalla fiducia, timeout adattivi per robot e rivendicazione del bystander.
3. Valutazione Controllata: Un confronto sistematico contro tre baseline (Timeout fisso ingenuo, Backoff esponenziale e Riconciliazione periodica) attraverso cinque regimi di qualità del canale, due dimensioni di team e un'ablazione dell'eterogeneità dell'hardware.

Risultati Sperimentali

Lo studio ha valutato 4.800 prove di sweep principale e 2.000 prove di ablazione.

Efficienza e Riduzione degli Sprechi

La TGPR dimostra miglioramenti statisticamente significativi nell'efficienza della comunicazione e nella riduzione degli sprechi:

• Esecuzione Duplicata: Ridotta del 23,9% rispetto alla baseline ingenua (10,65% vs 13,99%).
• Overhead di Messaggistica: Ridotto del 13,6% (167,2 vs 193,6 messaggi per compito completato).
• Trend: Questi vantaggi crescono man mano che la qualità del canale peggiora e aumenta la frazione di robot con hardware degradato.

Tasso di Completamento dei Compiti

Contrariamente all'ipotesi che un'allocazione consapevole della affidabilità migliorerebbe la produttività complessiva, la TGPR non migliora il tasso di completamento dei compiti complessivo.

• Performance: In condizioni di canale scarse e severe, la TGPR completa significativamente meno compiti rispetto alla baseline con timeout fisso (ad es., 0,434 vs 0,466 in condizioni severe con $N=25$).
• Risultato dell'Ablazione: Il divario nel tasso di completamento si amplia (da 1,1% a 1,9%) all'aumentare della frazione di hardware degradato, contraddicendo l'aspettativa che il meccanismo di fiducia possa "recuperare" il proprio costo evitando l'hardware difettoso.

Causa Radice del Costo del Tasso di Completamento

Gli autori attribuiscono il deficit del tasso di completamento a due meccanismi specifici:

1. Inflazione della Varianza Illimitata: Sotto tassi di fallimento sostenuti, la regola di aggiornamento del timeout adattivo gonfia la stima della varianza del ritardo ($\sigma_i$) senza un decadimento sufficiente. Ciò causa un innalzamento dei timeout appresi verso il limite massimo, perdendo potere discriminante tra robot sani e degradati.
2. Tassa di Latenza Fissa: La finestra di grazia della rivendicazione del bystander introduce un ritardo fisso su ogni ciclo di recupero, accumulando costi sotto fallimenti frequenti.

L'analisi della sensibilità dei parametri conferma che riducendo il moltiplicatore del timeout ($z$) è possibile recuperare il tasso di completamento a scapito di un aumento di duplicati e messaggistica, indicando un trade-off controllabile piuttosto che un difetto fondamentale della stima della fiducia.

Significato e Rivendicazioni

Il documento posiziona la TGPR non come un miglioramento universale rispetto alle aste più semplici, ma come una soluzione specializzata per specifici vincoli operativi.

• Confine Operativo: La TGPR è un vantaggio sostanziale per le implementazioni dove la larghezza di banda della comunicazione è scarsa o l'esecuzione fisica duplicata (ad es., consumo di batteria, usura degli attuatori) è il vincolo determinante. In questi scenari, la riduzione dello spreco e dell'overhead di messaggistica è la metrica primaria di successo.
• Limitazione: Quando l'unica metrica è la produttività pura del completamento dei compiti in ambienti ostili, la TGPR non è un miglioramento rigoroso rispetto alle baseline più semplici a timeout fisso e può performare peggio.
• Insight Scientifico: Lo studio fornisce un controesempio critico all'assunto che la "fiducia" aiuti sempre. Dimostra che i meccanismi basati sulla fiducia richiedono un segnale persistente e apprendibile (degradazione dell'hardware) per essere efficaci; in flotte in cui l'inaffidabilità è puramente posizionale e transitoria, i meccanismi di fiducia non offrono alcun beneficio misurabile.
• Reporting Onesto: Gli autori riportano esplicitamente il trade-off, notando che il costo del meccanismo (ridotto tasso di completamento) cresce con l'eterogeneità dell'hardware, contrariamente alle aspettative iniziali, e lo attribuiscono a specifici comportamenti algoritmici (inflazione della varianza) piuttosto che a fattori esterni.

Il lavoro conclude che la TGPR offre un trade-off quantificabile e prezioso: sacrificare parte della produttività di completamento per ridurre significativamente l'overhead di comunicazione e l'esecuzione duplicata, a condizione che l'ambiente di implementazione presenti differenziali di affidabilità hardware persistenti e apprendibili.