Scarica L'Aggiornamento sui Vortici Browniani e Sull'Intelligenza Cognitiva dopo "Un Modo Veloce per risolvere Problemi di Pianificazione Complessi."

MIT NEWS fro Massachusetts Institute of Technology di Boston 

Eliminando i calcoli ridondanti, un nuovo metodo basato sui dati può semplificare processi come la programmazione dei treni, l'instradamento degli autisti per le consegne o l'assegnazione degli equipaggi delle compagnie aeree.Adam Zewe | Notizie dal MIT

Quando alcuni treni pendolari giungono al capolinea, devono recarsi su un binario di scambio per essere invertiti e poter ripartire dalla stazione più tardi, spesso da un binario diverso da quello di arrivo.
Per pianificare questi movimenti, gli ingegneri utilizzano programmi software chiamati risolutori algoritmici, ma in una stazione con migliaia di arrivi e partenze settimanali, il problema diventa troppo complesso perché un risolutore tradizionale possa risolverlo tutto in una volta.
Utilizzando l'apprendimento automatico, i ricercatori del MIT hanno sviluppato un sistema di pianificazione migliorato che riduce i tempi di risoluzione fino al 50% e produce una soluzione che soddisfa meglio gli obiettivi dell'utente, come la puntualità delle partenze dei treni. Il nuovo metodo potrebbe essere utilizzato anche per risolvere in modo efficiente altri problemi logistici complessi, come la programmazione del personale ospedaliero, l'assegnazione degli equipaggi delle compagnie aeree o l'assegnazione di compiti ai macchinari industriali.
Gli ingegneri spesso scompongono questo tipo di problemi in una sequenza di sottoproblemi sovrapposti, ciascuno dei quali può essere risolto in un lasso di tempo ragionevole. Tuttavia, le sovrapposizioni comportano il ricalcolo inutile di molte decisioni, quindi il risolutore impiega molto più tempo per raggiungere una soluzione ottimale.Il nuovo approccio, potenziato dall'intelligenza artificiale, apprende quali parti di ciascun sottoproblema devono rimanere invariate, congelando tali variabili per evitare calcoli ridondanti. Successivamente, un risolutore algoritmico tradizionale affronta le variabili rimanenti.
"Spesso, un team dedicato potrebbe impiegare mesi o addirittura anni a progettare un algoritmo per risolvere anche solo uno di questi problemi combinatori. Il moderno apprendimento profondo ci offre l'opportunità di utilizzare nuovi progressi per semplificare la progettazione di questi algoritmi. Possiamo prendere ciò che sappiamo funzionare bene e usare l'intelligenza artificiale per accelerarlo", afferma Cathy Wu, Professoressa Associata Thomas D. e Virginia W. Cabot Career Development in Ingegneria Civile e Ambientale (CEE) e presso l'Institute for Data, Systems, and Society (IDSS) del MIT, e membro del Laboratory for Information and Decision Systems (LIDS).
Insieme a lei, l' autore principale Sirui Li, studentessa laureata presso l'IDSS; Wenbin Ouyang, studentessa laureata presso il CEE; e Yining Ma, postdoc presso il LIDS. La ricerca sarà presentata alla Conferenza Internazionale sulle Rappresentazioni dell'Apprendimento.
Eliminare la ridondanza
Una delle motivazioni di questa ricerca è un problema pratico individuato da uno studente magistrale, Devin Camille Wilkins, nel corso di introduzione ai trasporti di Wu. Lo studente desiderava applicare l'apprendimento per rinforzo a un problema reale di gestione dei treni alla North Station di Boston. L'azienda di trasporto pubblico deve assegnare numerosi treni a un numero limitato di binari, dove possano essere invertiti con largo anticipo rispetto al loro arrivo in stazione.Si è rivelato un problema di pianificazione combinatoria molto complesso, esattamente lo stesso tipo di problema su cui il laboratorio di Wu ha lavorato negli ultimi anni.
Quando si trovano ad affrontare un problema a lungo termine che comporta l'assegnazione di un insieme limitato di risorse, come attività di fabbrica, a un gruppo di macchine, i pianificatori spesso inquadrano il problema come una pianificazione flessibile del lavoro in officina.
Nella pianificazione flessibile del job shop, ogni attività richiede un tempo di completamento diverso, ma è possibile assegnarle a qualsiasi macchina. Allo stesso tempo, ogni attività è composta da operazioni che devono essere eseguite nell'ordine corretto.
Tali problemi diventano rapidamente troppo grandi e difficili da gestire per i risolutori tradizionali, quindi gli utenti possono ricorrere all'ottimizzazione rolling horizon (RHO) per suddividere il problema in parti gestibili che possono essere risolte più rapidamente.
Con RHO, un utente assegna inizialmente alcune attività alle macchine in un orizzonte temporale di pianificazione fisso, ad esempio una finestra temporale di quattro ore. Quindi, esegue la prima attività in quella sequenza e sposta in avanti l'orizzonte di pianificazione di quattro ore per aggiungere l'attività successiva, ripetendo il processo fino alla risoluzione dell'intero problema e alla creazione della pianificazione finale delle assegnazioni attività-macchina.
Un orizzonte di pianificazione dovrebbe essere più lungo della durata di una qualsiasi attività, poiché la soluzione sarà migliore se l'algoritmo considera anche le attività che verranno svolte in futuro.
Tuttavia, quando l'orizzonte di pianificazione avanza, si crea una sovrapposizione con le operazioni dell'orizzonte di pianificazione precedente. L'algoritmo ha già elaborato soluzioni preliminari per queste operazioni sovrapposte.
"Forse queste soluzioni preliminari sono valide e non necessitano di essere rielaborate, ma forse non lo sono. È qui che entra in gioco il machine learning", spiega Wu.
Per la loro tecnica, che chiamano learning-guided rolling horizon optimization (L-RHO), i ricercatori insegnano a un modello di apprendimento automatico a prevedere quali operazioni, o variabili, debbano essere ricalcolate quando l'orizzonte di pianificazione avanza.
L-RHO necessita di dati per addestrare il modello, quindi i ricercatori hanno risolto una serie di sottoproblemi utilizzando un risolutore algoritmico classico. Hanno scelto le soluzioni migliori – quelle con il maggior numero di operazioni che non necessitano di essere ricalcolate – e le hanno utilizzate come dati di addestramento.
Una volta addestrato, il modello di apprendimento automatico riceve un nuovo sottoproblema mai visto prima e prevede quali operazioni non devono essere ricalcolate. Le operazioni rimanenti vengono reimmesse nel risolutore algoritmico, che esegue il task, ricalcola queste operazioni e sposta in avanti l'orizzonte di pianificazione. Quindi il ciclo ricomincia da capo.
"Se, a posteriori, non abbiamo avuto bisogno di riottimizzarli, allora possiamo eliminare quelle variabili dal problema. Dato che questi problemi crescono esponenzialmente in termini di dimensioni, può essere molto vantaggioso eliminare alcune di queste variabili", aggiunge.
Un approccio adattabile e scalabile
Per testare il loro approccio, i ricercatori hanno confrontato L-RHO con diversi risolutori algoritmici di base, risolutori specializzati e approcci che utilizzano esclusivamente l'apprendimento automatico. Li ha superati tutti, riducendo i tempi di risoluzione del 54% e migliorando la qualità della soluzione fino al 21%.
Inoltre, il loro metodo ha continuato a superare tutte le basi di partenza quando lo hanno testato su varianti più complesse del problema, come in caso di guasti ai macchinari di fabbrica o di congestione ferroviaria. Ha superato persino le basi di partenza aggiuntive create dai ricercatori per mettere alla prova il loro risolutore.
"Il nostro approccio può essere applicato senza modifiche a tutte queste diverse varianti, che è in realtà ciò che ci prefiggiamo di fare con questa linea di ricerca", afferma.
L-RHO può anche adattarsi se gli obiettivi cambiano, generando automaticamente un nuovo algoritmo per risolvere il problema: tutto ciò di cui ha bisogno è un nuovo set di dati di addestramento.
In futuro, i ricercatori vorranno comprendere meglio la logica alla base della decisione del loro modello di congelare alcune variabili, ma non altre. Intendono inoltre integrare il loro approccio in altri tipi di problemi di ottimizzazione complessi, come la gestione dell'inventario o il routing dei veicoli.
Questo lavoro è stato sostenuto, in parte, dalla National Science Foundation, dal Research Support Committee del MIT, da una borsa di dottorato di ricerca di Amazon Robotics e da MathWorks.