Cuando algunos trenes de cercanías llegan al final de la línea, deben viajar a una plataforma de conmutación para ser giradas para que puedan salir de la estación más tarde, a menudo desde una plataforma diferente a la que llegaron.
Los ingenieros usan programas de software llamados solucionadores algorítmicos para planificar estos movimientos, pero en una estación con miles de llegadas y salidas semanales, el problema se vuelve demasiado complejo para que un solucionador tradicional se desentraques de una vez.
Usando el aprendizaje automático, los investigadores del MIT han desarrollado un sistema de planificación mejorado que reduce el tiempo de resolución hasta en un 50 por ciento y produce una solución que cumpla mejor con el objetivo de un usuario, como las salidas de trenes a tiempo. El nuevo método también podría usarse para resolver eficientemente otros problemas logísticos complejos, como programar el personal del hospital, asignar equipos de aerolíneas o asignar tareas a máquinas de fábrica.
Los ingenieros a menudo dividen este tipo de problemas en una secuencia de subproblemas superpuestos que se pueden resolver en una cantidad factible de tiempo. Pero las superposiciones hacen que muchas decisiones sean recomputadas innecesariamente, por lo que se necesita el solucionador mucho más tiempo para alcanzar una solución óptima.
El nuevo enfoque de inteligencia artificial mejorado aprende qué partes de cada subproblema deben permanecer sin cambios, congelando esas variables para evitar cálculos redundantes. Luego, un solucionador algorítmico tradicional aborda las variables restantes.
«A menudo, un equipo dedicado podría pasar meses o incluso años diseñando un algoritmo para resolver solo uno de estos problemas combinatorios. El aprendizaje profundo moderno nos brinda la oportunidad de usar nuevos avances para ayudar a optimizar el diseño de estos algoritmos. Podemos tomar lo que sabemos bien y usar AI para acelerarlo», dice Cathy Wu, el Tomas D. y Virginia W. Cabot Development Associating en el profesor civil en el desarrollo de la carrera. Datos, sistemas y sociedad (IDS) en el MIT, y miembro del Laboratorio para Sistemas de Información y Decisión (LIDS).
Se une al periódico por el autor principal Sirui Li, un estudiante graduado de IDSS; Wenbin Ouyang, un estudiante graduado de CEE; y Yining MA, A Postdocs Postdocs. La investigación se presentará en la Conferencia Internacional sobre Representaciones de Aprendizaje.
Eliminando la redundancia
Una motivación para esta investigación es un problema práctico identificado por el estudiante de maestría Devin Camille Wilkins en el curso de transporte de nivel de entrada de Wu. El estudiante quería aplicar el aprendizaje de refuerzo a un verdadero problema de disputa de tren en la estación Norte de Boston. La organización de tránsito debe asignar muchos trenes a un número limitado de plataformas donde se pueden dar una vuelta antes de su llegada a la estación.
Este resulta ser un problema de programación combinatoria muy complejo: el tipo exacto de problema en el que el laboratorio de Wu ha pasado en los últimos años trabajando.
Cuando se enfrenta a un problema a largo plazo que implica asignar un conjunto limitado de recursos, como tareas de fábrica, a un grupo de máquinas, los planificadores a menudo enmarcan el problema como una programación flexible de la tienda de empleo.
En la programación flexible de la tienda de empleo, cada tarea necesita una cantidad diferente de tiempo para completar, pero las tareas se pueden asignar a cualquier máquina. Al mismo tiempo, cada tarea se compone de operaciones que deben realizarse en el orden correcto.
Tales problemas se vuelven demasiado grandes y difíciles de manejar para los solucionadores tradicionales, por lo que los usuarios pueden emplear optimización de horizonte rodante (Rho) para dividir el problema en fragmentos manejables que se pueden resolver más rápido.
Con Rho, un usuario asigna algunas tareas iniciales a las máquinas en un horizonte de planificación fijo, tal vez una ventana de tiempo de cuatro horas. Luego, ejecutan la primera tarea en esa secuencia y cambian el horizonte de planificación de cuatro horas hacia adelante para agregar la siguiente tarea, repitiendo el proceso hasta que se resuelva todo el problema y se cree el cronograma final de tareas de las tareas.
Un horizonte de planificación debe ser más largo que la duración de cualquier tarea, ya que la solución será mejor si el algoritmo también considera tareas que surgirán.
Pero cuando el horizonte de planificación avanza, esto crea cierta superposición con las operaciones en el horizonte de planificación anterior. El algoritmo ya se le ocurrió soluciones preliminares a estas operaciones superpuestas.
«Tal vez estas soluciones preliminares son buenas y no necesitan calcularse nuevamente, pero tal vez no son buenas. Aquí es donde entra el aprendizaje automático», explica Wu.
Para su técnica, que llaman optimización de horizonte de rodillo guiado por el aprendizaje (L-RHO), los investigadores enseñan un modelo de aprendizaje automático para predecir qué operaciones o variables deben ser recomputadas cuando el horizonte de planificación se lanza hacia adelante.
L-RHO requiere datos para capacitar al modelo, por lo que los investigadores resuelven un conjunto de subproblemas utilizando un solucionador algorítmico clásico. Tomaron las mejores soluciones, las que tienen la mayor cantidad de operaciones que no necesitan ser recomputadas, y las usaron como datos de capacitación.
Una vez entrenado, el modelo de aprendizaje automático recibe un nuevo subproblema que no ha visto antes y predice qué operaciones no deben ser recomputadas. Las operaciones restantes se devuelven al solucionador algorítmico, que ejecuta la tarea, recomputa estas operaciones y mueve el horizonte de planificación hacia adelante. Entonces el bucle comienza de nuevo.
«Si, en retrospectiva, no necesitábamos reoptimizarlas, entonces podemos eliminar esas variables del problema. Debido a que estos problemas crecen exponencialmente en tamaño, puede ser bastante ventajoso si podemos eliminar algunas de esas variables», agrega.
Un enfoque adaptable y escalable
Para probar su enfoque, los investigadores compararon L-RHO con varios solucionadores algorítmicos base, solucionadores especializados y enfoques que solo usan el aprendizaje automático. Los superó a todos, reduciendo el tiempo de resolución en un 54 por ciento y mejorando la calidad de la solución hasta en un 21 por ciento.
Además, su método continuó superando a todas las líneas de base cuando lo probaron en variantes más complejas del problema, como cuando las máquinas de fábrica se descomponen o cuando hay una congestión adicional del tren. Incluso superó a las líneas de base adicionales que los investigadores crearon para desafiar su solucionador.
«Nuestro enfoque se puede aplicar sin modificar a todas estas diferentes variantes, que es realmente lo que nos propusimos hacer con esta línea de investigación», dice ella.
L-Rho también puede adaptarse si los objetivos cambian, generando automáticamente un nuevo algoritmo para resolver el problema: todo lo que necesita es un nuevo conjunto de datos de capacitación.
En el futuro, los investigadores quieren comprender mejor la lógica detrás de la decisión de su modelo de congelar algunas variables, pero no otras. También quieren integrar su enfoque en otros tipos de problemas de optimización complejos como la gestión de inventario o el enrutamiento de vehículos.
Este trabajo fue apoyado, en parte, por la National Science Foundation, el Comité de Apoyo a la Investigación del MIT, una beca de doctorado de Robotics de Amazon y MathWorks.
