Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

Immaginate una flotta di veicoli che corre contro il tempo per visitare una collezione sparsa di località, ognuna delle quali offre un premio diverso. L'obiettivo è semplice: raccogliere il maggior valore possibile prima che il tempo scada. Ma il mondo non è un foglio di calcolo. Il tempo necessario per completare un compito in un dato punto è incerto; una folata di vento improvvisa potrebbe ritardare un drone, o mari agitati potrebbero rallentare una barca. Inoltre, ogni località è disponibile solo per una specifica finestra temporale. Se un veicolo arriva troppo presto, deve aspettare; se arriva troppo tardi, l'opportunità svanisce per sempre. Questa è l'essenza di una complessa sfida logistica nota come problema di orienteering di squadra con finestre temporali. Nel mondo reale, questo scenario si verifica quando i vigili del fuoco cercano di contenere un incendio boschivo, le squadre addette alle fuoriuscite di petrolio corrono per contenere una macchia prima che colpisca la costa, o i team medici devono visitare i pazienti entro intervalli di tempo critici. La difficoltà risiede nel compiere la mossa successiva istantaneamente, senza sapere esattamente quanto durerà l'attuale compito e senza il lusso di un supercomputer per ricalcolare l'intero piano ogni secondo.

Per anni, i ricercatori hanno cercato di risolvere questo problema insegnando ai computer a far evolvere semplici regole decisionali. Queste regole agiscono come un controllore del traffico, osservando la situazione attuale e decidendo immediatamente quale cliente visitare successivamente. Il metodo più efficace finora, noto come NS-GP, si basa su un insieme fisso di undici caratteristiche di base — come quanto sia lontano un cliente o quanto tempo rimanga — per compiere queste scelte. Sebbene efficace, questo approccio ha un limite. Utilizza un vocabolario limitato per descrivere il mondo, molto simile al tentativo di scrivere un romanzo usando solo cento parole. I ricercatori dietro questo nuovo studio, guidati da Augusto Mendonça e dal suo team di università brasiliane, si sono posti una domanda audace: cosa succederebbe se il computer potesse apprendere un vocabolario più ricco osservando come un pianificatore esperto risolve il problema offline? Volevano vedere se potevano estrarre la logica nascosta delle soluzioni di alta qualità e trasformare tali intuizioni in regole semplici e leggibili che funzionino in tempo reale.

Il team ha sviluppato un nuovo metodo chiamato SI-GP, che sta per Solver-Informed Genetic Programming (Programmazione Genetica Informata dal Solutore). Il processo non inizia con il computer che indovina, ma con il computer che osserva. Per prima cosa, i ricercatori hanno utilizzato potenti solutori ad alta velocità per trovare i percorsi migliori per un insieme di quaranta diversi problemi di test, assumendo che tutto procedesse perfettamente. Hanno poi preso questi percorsi perfetti e li hanno riprodotti in un mondo simulato dove i ritardi avvenivano casualmente, proprio come accade nella realtà. Confrontando i piani perfetti con ciò che è effettivamente accaduto, il team ha identificato specifiche operazioni che i piani perfetti eseguivano ma che le regole standard non coglievano. Ad esempio, hanno notato che i migliori piani spesso guardavano diversi passi avanti per vedere quali ricompense sarebbero rimaste raggiungibili, o calcolavano il rischio di perdere un'opportunità futura se si fosse impegnato in un compito attuale.

Da queste osservazioni, i ricercatori hanno costruito una nuova libreria di diciotto caratteristiche decisionali. Sedici di queste erano basate su concetti consolidati nella pianificazione, mentre due erano combinazioni completamente nuove progettate per pesare il costo di una decisione rispetto al potenziale guadagno. Questo nuovo vocabolario ha dato al computer un modo molto più sfumato di comprendere il problema. Tuttavia, avere più opzioni non significa automaticamente ottenere risultati migliori; a volte, troppe scelte possono confondere il sistema. Per risolvere questo, il team ha utilizzato un secondo livello di intelligenza per selezionare il miglior sottoinsieme di queste caratteristiche per ogni specifico problema. Hanno trattato il processo di selezione come un torneo, facendo evolvere diverse combinazioni di caratteristiche e testandole rigorosamente. Ciò è stato reso possibile da un motore personalizzato che gira su schede grafiche, permettendo loro di testare migliaia di combinazioni nel tempo in cui prima si testava una sola.

I risultati sono stati sorprendenti. Sui quaranta problemi di benchmark, il nuovo metodo non è mai stato peggiore dello standard precedente. In trentotto dei casi, il sistema ha fatto evolvere una nuova regola che ha superato la migliore precedente. In media, le nuove regole hanno migliorato il premio totale raccolto dell'1,0% in tutti i test, e dell'1,3% nei problemi in cui c'era ancora margine di miglioramento. In dieci casi specifici, il miglioramento è stato statisticamente significativo e abbastanza grande da essere considerato una grande svolta per quel particolare scenario. Forse, cosa più importante, le nuove regole sono rimaste semplici e leggibili. Non erano algoritmi a "scatola nera" che nessuno poteva comprendere; erano espressioni matematiche compatte che un essere umano poteva leggere e verificare. In molti casi, le nuove regole erano anche più stabili, producendo risultati coerenti anche quando i ritardi casuali variavano, laddove le vecchie regole a volte oscillavano selvaggiamente tra risultati buoni e cattivi.

Lo studio ha anche rivelato perché siano avvenuti i miglioramenti. Le nuove regole sono state particolarmente efficaci in situazioni in cui il sistema di base faticava a visitare tutti i possibili clienti. In questi scenari "insaturi", il nuovo vocabolario ha permesso al sistema di navigare tra complessi compromessi, come visitare un cliente lontano e di alto valore anche se ciò significava saltare un cliente vicino e di basso valore. I ricercatori hanno scoperto che le nuove caratteristiche hanno aiutato il sistema a regolarizzare la sua ricerca, il che significa che era meno probabile che rimanesse intrappolato in un minimo locale e più probabile che trovasse un percorso robusto. Il metodo ha funzionato imparando dalla struttura delle soluzioni di alta qualità senza semplicemente copiarle. Non ha cercato di imitare l'esatto percorso del pianificatore esperto; invece, ha appreso i principi che rendevano di successo quei percorsi e li ha applicati a un nuovo ambiente incerto.

Questo lavoro dimostra che è possibile colmare il divario tra l'ottimizzazione offline complessa e il decision-making online veloce. Usando le intuizioni dai solutori di alta qualità per costruire un vocabolario migliore, e selezionando con cura gli strumenti giusti per ogni specifico compito, i ricercatori hanno creato un sistema che è allo stesso tempo potente e trasparente. Il prodotto finale è un insieme di regole decisionali che possono essere incorporate direttamente in veicoli o droni, consentendo loro di prendere decisioni intelligenti in microsecondi senza la necessità di connettersi a un computer centrale o eseguire simulazioni complesse. L'approccio suggerisce una nuova strada per l'intelligenza artificiale nella logistica: una che valorizzi l'interpretabilità e l'adattabilità, assicurando che le macchine che prendono decisioni critiche possano essere comprese dagli esseri umani che fanno affidamento su di esse. I ricercatori hanno reso il loro codice, i dati e le regole specifiche scoperte disponibili al pubblico, invitando altri a costruire su questa base per future sfide in ambienti incerti.