Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

Sintesi Tecnica: Stabilità della Policy per la Misurazione delle Prestazioni Operative nell'Assegnazione di Task con Finestre Temporali sotto Influenza Avversaria Interna

Enunciato del Problema
Il documento affronta la vulnerabilità dei sistemi autonomi di raccolta e consegna (pickup-and-delivery) rispetto ad agenti avversari interni. In questi sistemi, uno scheduler centralizzato accoppia gli agenti disponibili alle richieste di servizio. Tuttavia, agenti compromessi o strategici all'interno della flotta possono falsificare la segnalazione della propria posizione per catturare l'assegnazione dei task e intenzionalmente lasciare tali richieste non servite. Questo comportamento interrompe lo scheduler, causando ritardi, cancellazioni di richieste e un'inefficiente utilizzazione delle risorse.

Una sfida centrale identificata è la definizione di "stabilità della policy" in tali ambienti avversari. Le definizioni tradizionali di stabilità si basano su:

1. Carichi di lavoro basati sulla teoria delle code: Questi richiedono l'analisi dell'esecuzione delle rotte specifiche degli agenti, il che è impraticabile quando gli agenti deviano arbitrariamente o non servono le richieste.
2. Costi di Reinforcement Learning (RL) scontati: Questi dipendono da un fattore di sconto che può sottopesare il degrado a lungo termine e mascherare gli effetti avversari cumulativi.
3. Metriche basate solo sul backlog: Queste non riescono a distinguere tra le richieste che vengono infine servite dopo un ritardo eccessivo e quelle che non vengono mai servite entro una finestra temporale operativamente accettabile.

Gli autori sostengono che i criteri esistenti siano inadatti per contesti avversari in cui agenti non cooperativi deviano arbitrariamente dalle rotte assegnate.

Metodologia
Gli autori propongono un nuovo framework per l'analisi della stabilità basato su segnali osservabili a livello di sistema piuttosto che su azioni inferite a livello di agente.

• Nuova Formulazione della Stabilità: Il documento introduce un criterio di stabilità a costo medio definito da due quantità osservabili:

  1. Il numero di richieste in sospeso ($O_t$).
  2. Il numero cumulativo di richieste cancellate ($C_t$).
     Il costo per stadio è definito come $g = O_t + C_t$. Una policy è stabile se il costo medio atteso su un orizzonte infinito è finito.

• Analisi Teorica:

  • Assunzioni: L'analisi assume arrivi di richieste limitati e finestre temporali di richiesta finite (le richieste scadono se non servite entro una durata specifica).
  • Teorema Chiave: Sotto queste assunzioni, il numero di richieste in sospeso è uniformemente limitato nel tempo (Nota 1). Di conseguenza, il documento dimostra (Teorema 1) che la stabilità sotto il proposto criterio di costo medio è equivalente al mantenere uniformemente limitato nel tempo il numero atteso di richieste cancellate.
  • Stabilità Degenerata: Gli autori caratterizzano un regime patologico chiamato "stabilità degenerata". Senza finestre temporali finite, un sistema potrebbe soddisfare i classici criteri di stabilità basati sul backlog pur mantenendo un backlog elevato e operativamente inaccettabile di richieste ritardate. Le finestre temporali finite convertono l'attesa eccessiva in cancellazioni osservabili, eliminando così questo regime degenerato.

• Modelli Avversari e Policy di Assegnazione:

  • Conoscenza Avversaria: Sono definiti tre modelli basati sulla disponibilità di informazioni: Solo Richiesta (informazioni limitate), Informazione di Squadra (coordinamento tra avversari) e Onnipotente (piena consapevolezza del sistema e conoscenza dell'algoritmo dello scheduler).
  • Policy di Assegnazione: Vengono studiati tre policy: Greedy (vicino più prossimo locale), Assegnazione Istantanea (IA) (matching ottimale globale con impegno) e Assegnazione Istantanea con Riassegnazione (IA-RA) (matching globale che consente la riassegnazione prima del ritiro).
  • Allocazione Consapevole della Fattibilità: Gli autori introducono meccanismi di assegnazione che limitano i match a coppie agente-richiesta capaci di rispettare i vincoli della finestra temporale prima della scadenza.

Contributi Chiave

1. Stabilità a Costo Medio Osservabile: Una formulazione della stabilità basata su segnali a livello di sistema (richieste in sospeso e cancellazioni) che non richiede la ricostruzione dell'esecuzione della rotta a livello di agente, rendendola applicabile sia ad ambienti cooperativi che avversari.
2. Teorema di Equivalenza: Una dimostrazione che, sotto arrivi limitati e finestre temporali finite, la stabilità è equivalente al limitare il numero atteso di richieste cancellate nel tempo.
3. Identificazione della Stabilità Degenerata: La caratterizzazione di un regime in cui i criteri basati sul backlog certificano falsamente la stabilità nonostante una scarsa qualità del servizio, motivando la necessità di finestre temporali finite e penalità per le cancellazioni.
4. Framework Avversario: Sviluppo di procedure di assegnazione consapevoli della fattibilità e modelli di conoscenza avversaria che catturano diversi livelli di consapevolezza strategica e coordinamento.
5. Valutazione Empirica: Uno studio di caso utilizzando dati reali di mobilità on-demand (taxi) di San Francisco per valutare il framework proposto.

Risultati
Lo studio empirico, condotto su una rete stradale simulata di San Francisco con dati reali di domanda, ha prodotto i seguenti risultati:

• Calibrazione della Flotta: Le dimensioni della flotta cooperativa derivate dai baselines esistenti della teoria delle code sono state verificate come produttrici di un comportamento stabile sotto finestre temporali finite.
• Validazione della Stabilità Degenerata: In contesti senza scadenza della richiesta, il numero di richieste in sospeso si è stabilizzato, portando le metriche classiche del backlog a classificare il sistema come stabile nonostante i ritardi significativi. Ciò ha confermato l'esistenza della stabilità degenerata.
• Impatto Avversario: Sotto finestre temporali finite, la proposta metrica di costo medio ha identificato correttamente l'instabilità attraverso una crescita sostenuta del costo della policy guidata dalle cancellazioni delle richieste.
  • L'instabilità aumentava con la proporzione di agenti avversari.
  • Gli avversari Onnipotenti hanno causato la degradazione più severa, seguiti dai modelli Informazione di Squadra e Solo Richiesta.
  • La policy IA-RA è risultata essere più vulnerabile rispetto a IA o Greedy perché i meccanismi di riassegnazione permettono agli avversari di reindirizzare ripetutamente gli agenti cooperativi, amplificando la perturbazione.
• Confronto tra Metriche: La metrica proposta (backlog + cancellazioni) ha identificato regimi instabili che una metrica basata solo sul backlog aveva mancato, dimostrando che il solo backlog limitato è insufficiente per valutare la qualità del servizio in sistemi sensibili al tempo e soggetti ad avversari.

Significatività
L'articolo sostiene che la sua principale significatività risieda nel fornire una definizione di stabilità che è direttamente legata ai fallimenti operativi del servizio (cancellazioni) piuttosto che ai carichi di lavoro teorici. Collegando la stabilità alla limitatezza delle richieste cancellate, la formulazione offre una metrica significativa per sistemi di routing sensibili al tempo dove i ritardi sono inaccettabili.

Gli autori sottolineano che le finestre temporali finite delle richieste non sono un semplice dettaglio di modellazione, ma sono essenziali per distinguere tra un'operazione accettabile e un regime di "stabilità degenerata" in cui i sistemi appaiono stabili ma falliscono nel servire le richieste entro tempi accettabili. Questo lavoro colma il divario tra l'analisi della stabilità del routing, la sicurezza contro lo spoofing interno e i vincoli pratici del servizio con finestre temporali, offrendo un framework che rimane robusto anche quando gli agenti deviano dai comportamenti prescritti.