Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning

Sintesi Tecnica: Trasporto Intelligente Senza Neuroni – Espansione della Rete Metropolitana con Apprendimento per Rinforzo Tabulare

Definizione del Problema
Il documento affronta il Problema di Espansione della Rete Metropolitana (MNEP), un sottoinsieme specifico del Problema di Progettazione della Rete di Trasporto (TNDP). L'obiettivo è progettare una nuova linea metropolitana all'interno di una rete urbana esistente per massimizzare la domanda di viaggio catturata, soggetti a vincoli sul budget di costruzione ($B$) e sul numero massimo di stazioni ($T$). Tradizionalmente, l'MNEP è modellato come un problema di ottimizzazione combinatoria in cui la città è rappresentata come una griglia, e l'obiettivo è trovare una sequenza di celle adiacenti che formi una linea volta a massimizzare la somma della domanda di Origine-Destinazione (OD) soddisfatta.

Una lacuna critica identificata nella letteratura è la dipendenza dal Deep Reinforcement Learning (Deep RL) per questi problemi. Sebbene il Deep RL abbia mostrato successo nel processo decisionale sequenziale complesso, esso è computazionalmente costoso, ambientalmente oneroso e spesso funziona come una "scatola nera", priva di interpretabzionalità. Gli autori sostengono che l'MNEP sia fondamentalmente un problema di ottimizzazione statica con input di caratteristiche limitate e vincoli di scalabilità intrinseci (ad esempio, spaziatura fissa delle stazioni), suggerendo che reti neurali complesse possano non essere necessarie. Inoltre, gli approcci esistenti spesso danno priorità all'efficienza (utilitarismo) rispetto all'equità sociale, fallendo nell'affrontare adeguatamente la distribuzione equa dei benefici di trasporto tra diversi gruppi socioeconomici.

Metodologia
Gli autori propongono un nuovo framework che combina una riformulazione del problema con un approccio di Apprendimento per Rinforzo Tabulare (Tabular RL), incorporando esplicitamente criteri di equità sociale.

1. Riformulazione del Problema (NMRDP):
   L'MNEP viene riformulato come un Processo Decisionale a Ricompensa Non-Markoviana (NMRDP). A differenza dei precedenti approcci di Deep RL che trattano ogni cella della griglia come una potenziale azione (risultando in uno spazio di azioni che scala linearmente con la dimensione della griglia, $O(n \times m)$), il metodo proposto scinde il processo in due fasi:

   • Selezione dello Stato Iniziale: L'agente seleziona una cella di partenza per la linea metropolitana.
   • Navigazione Sequenziale: L'agente si muove attraverso la griglia scegliendo una delle otto direzioni discrete (N, S, E, W e quattro diagonali).
     Questo riduce lo spazio delle azioni a una dimensione costante di 8 (indipendentemente dalle dimensioni della griglia) per tutti i passi successivi alla selezione iniziale, riducendo la complessità temporale a $O(1)$ per passo. Lo stato è semplificato alla posizione attuale dell'agente. Poiché la ricompensa dipende dalla storia delle stazioni visitate (per calcolare la domanda diretta e di interscambio), il processo viola la stretta proprietà di Markov, da cui la formulazione NMRDP.

2. Algoritmo (Monte Carlo Tabular RL):
   Gli autori impiegano un algoritmo di Tabular RL basato su Monte Carlo. L'agente mantiene due tabelle:

   • $V_{start}(S_0)$: Stima il ritorno atteso per la selezione di una specifica cella come punto di partenza.
   • $Q(S, A)$: Stima il valore di compiere una specifica azione direzionale da uno stato corrente.
     L'agente utilizza una strategia $\epsilon$-greedy per l'esplorazione e lo sfruttamento. Gli aggiornamenti vengono eseguiti alla fine di ogni episodio tramite la stima Monte Carlo del ritorno totale $J$, regolando i valori $V$ e $Q in base alla differenza tra il ritorno stimato e quello effettivo.

3. Integrazione dell'Equità Sociale:
   La funzione di ricompensa è estesa oltre la semplice massimizzazione della domanda per includere l'equità sociale. Gli autori definiscono i gruppi ($G$) sulla base di indicatori socioeconomici (specificamente gli indici dei prezzi delle case come proxy dello sviluppo). Vengono testate tre formulazioni di ricompensa:

   • Utilitarista (Massima Efficienza): Massimizza la domanda totale soddisfatta.
   • Condivisione Uguale (Equità Orizzontale): Utilizza l'Indice di Gini Generalizzato (GGI) per minimizzare le disparità nei benefici tra i gruppi.
   • Giustizia Rawlsiana (Equità Verticale): Massimizza il beneficio per il gruppo più svantaggiato (il quintile con i prezzi delle case più bassi).

Contributi Chiave

• Riformulazione del Problema: Il documento dimostra che riformulare l'MNEP come un NMRDP con uno spazio di azioni scisso permette l'uso di metodi tabulari semplici, riducendo drasticamente la complessità dello spazio di ricerca senza restringere lo spazio delle soluzioni.
• Efficienza Algoritmica: La proposta di un algoritmo Monte Carlo Tabular RL che raggiunge prestazioni competitive con significativamente meno episodi di addestramento rispetto al Deep RL.
• Framework Consapevole dell'Equità: L'integrazione di diversi obiettivi di bene sociale (utilitaristico, egualitario e rawlsiano) nel framework di RL, fornendo un meccanismo flessibile per bilanciare efficienza ed equità nella pianificazione dei trasporti.
• Interpretabilità: L'uso di metodi tabulari fornisce un'interpretabilità intrinseca, permettendo ai decisori di visualizzare direttamente le politiche ottimali, le distribuzioni delle ricompense e i valori Q, a differenza delle rappresentazioni latenti del Deep RL.

Risultati Sperimentali
Il metodo è stato valutato in due ambienti reali: Xi'an, Cina, e Amsterdam, Paesi Bassi.

• Performance: TabularMNEP ha raggiunto prestazioni comparabili ai metodi Deep RL allo stato dell'arte in tutte le funzioni di ricompensa (Efficienza, GGI(2), GGI(4) e Rawls). In alcuni casi, ha leggermente sottoperformato il Deep RL ma è rimasto entro gli intervalli di confidenza, superando significativamente i modelli di base Genetic Algorithms e Greedy Search.
• Efficienza: L'approccio Tabular ha richiesto solo 25.000 episodi di addestramento, una riduzione di 18 volte rispetto ai 448.000 episodi richiesti dal baseline di Deep RL.
• Impatto Ambientale: Grazie alla riduzione del tempo di addestramento e alla mancanza di dipendenza da GPU (sebbene testato su nodi GPU per equità di confronto), il metodo Tabular ha ridotto le emissioni di carbonio stimate di un fattore 12 in media.
• Esiti di Equità: Gli esperimenti hanno confermato che diverse funzioni di ricompensa hanno cambiato con successo il design della rete. La Massima Efficienza ha favorito le aree ad alta domanda (spesso più ricche), mentre le ricompense GGI e Rawlsian hanno redistribuito con successo i benefici ai gruppi a basso reddito, sebbene con costi variabili in termini di efficienza complessiva.

Significatività e Rivendicazioni
Il documento sostiene che modelli di Deep Learning complessi e "black-box" non siano sempre necessari per problemi di ottimizzazione combinatoria come l'MNEP. Riformulando attentamente il problema per ridurre lo spazio delle azioni, metodi tabulari più semplici, efficienti dal punto di vista delle risorse e interpretabili possono fornire risultati allo stato dell'arte. Gli autori sottolineano che questo approccio offre una soluzione "replicabile, modulare, interpretabile e efficiente dal punto di vista delle risorse".

Il lavoro evidenzia l'importanza di considerare l'equità sociale nella pianificazione automatizzata dei trasporti, dimostrando che il RL può essere tarato per ottimizzare l'equità senza sacrificare troppo l'efficienza. Tuttavia, gli autori mantengono una posizione modesta riguardo alla scalabilità, riconoscendo che, sebbene i metodi tabulari funzionino bene per l'MNEP grazie a spazi di stato vincolati, potrebbero non generalizzarsi a problemi con rappresentazioni di stato intrinsecamente massicce. Essi avvertono inoltre che, senza una progettazione attenta della ricompensa e la supervisione umana, il processo decisionale automatizzato nella pianificazione urbana rischia di rafforzare i pregiudizi esistenti.