Aplicaciones Industriales de la IA, parte 3 (Aprendiendo a decidir)

Muchos problemas industriales son problemas en los que se requiere encontrar una buena solución entre millones de posibles soluciones. Un ejemplo de ello puede ser un problema de planificación de un taller o scheduling. En estos problemas, es necesario decidir en qué orden procesar unos trabajos en un conjunto de máquinas. Cada uno de los trabajos se compone de distintas operaciones que se realizan en distintas maquinas. El ordenamiento buscado debe conseguir que se cumplan uno o varios objetivos (por ejemplo, que ningún trabajo se entregue tarde). En el Gantt de la Figura-1 se muestra una planificación de un taller con 15 máquinas, si se quiere mejorar esta planificación (ej. hay un trabajo que no cumple su fecha de entrega), se debe modificar el orden de algunos trabajos en algunas máquinas, pero si lo hacemos automáticamente se “moverán” el resto de los trabajos. En definitiva, encontrar la mejor solución a este “sudoku”, con millones de combinaciones es muy complejo.

Otro ejemplo, son los problemas de reparto de paquetería (ver Figura-2), donde hay que realizar distintas entregas en distintos puntos y es necesario determinar cuál es la mejor ruta sujeta a ciertas restricciones (ej. hay entregas que se deben realizar en determinadas ventanas de tiempo) y de forma que se optimice un objetivo (ej. menor tiempo del camión de reparto en completar la ruta). Aquí también el número de posibles soluciones o rutas puede ser altísimo, por lo que no es fácil determinar entre todas ellas cual es la más conveniente.

Los ejemplos anteriores son ejemplos de problemas combinatorios complejos donde se busca una solución óptima, o cercana a la óptima, y donde el reto principal está en conseguirlo en tiempos muy cortos.

La situación ideal sería conseguir un algoritmo que fuese capaz de aprender a resolver este tipo de problemas en un entorno simulado, para después poder aplicar lo aprendido a un entorno de producción y conseguir buenas soluciones en tiempos muy cortos. Recientemente tanto desde el mundo académico como desde la industria ^[1], comienzan a obtenerse resultados interesantes, siendo dos las aproximaciones más prometedoras, unas basadas en Deep Learning y otras en Deep Reinforcement Learning, a continuación, se describen.

Deep Learning

La idea es abordar el problema de optimización como un problema de machine learning^[2], suministrándole, al algoritmo, ejemplos de problemas con sus soluciones optimas. Con el objetivo de que el algoritmo aprenda a partir de los ejemplos, para después poder aplicar dicho algoritmo entrenado en producción. Lo que debe permitir obtener buenas soluciones en tiempos muy cortos.

Para entender esto, supongamos el problema del reparto, también conocido como problema del viajante o travel salesman problem, que se mostraba en la Figura-2. El objetivo es encontrar la ruta con la menor distancia que conecte los puntos de entrega. Una aproximación a este problema es entrena una red neuronal (ej. Graph Convolutional Network), a partir de ejemplos de problemas de los que se dispone de la solución óptima. La red aprende que

conexiones son las que tienen mayor probabilidad de pertenecer a la solución óptima. Una forma de visualizar las probabilidades obtenidas es pintar las conexiones entre puntos con una intensidad mayor si su probabilidad es alta, a esto le llamaremos “heat map” (ver Figura-3).

Una vez entrenada la red neuronal es posible aplicarla a nuevos problemas, obteniéndose para el nuevo problema su “heat map”. A partir de dicho “heat map” es posible, utilizando técnicas heurísticas de optimización (ej. beam search), conseguir buenas soluciones en tiempos muy corto, ya que gracias al “heat map” solo es necesario explorar aquellas conexiones identificadas como más prometedoras.

Para ilustrar esta técnica en la Figura-3 se muestra una aplicación a un pequeño problema con 20 puntos de entrega, la intensidad de las conexiones en el “heat map” indican la probabilidad de pertenecer a la solución óptima, por lo que la optimización heurística sólo considerará aquellas conexiones con alta probabilidad, reduciendo así su tiempo de procesamiento.

Una segunda forma de abordar estos problemas es mediante Reinforcement Learning o mejor dicho Deep Reinforcement Learning (DRL), ya que el problema se representa utilizando un modelo de Deep Learning (ej. GCN, LSTM, RNN). La ventaja de utilizar Deep Reinforcement Learning es que no se necesita un conjunto de ejemplos o problemas con soluciones optimas, ya que es el propio algoritmo quien va generando, por simulación, problemas y soluciones y va aprendiendo en este proceso.

Para entenderlo mejor, si se aplicase Deep Reinforcement Learning al problema de las entregas o problema del viajante visto anteriormente (ver Figura-4), el algoritmo iría generando problemas nuevos mediante simulación y para cada problema construiría una solución, recibiendo una recompensa o refuerzo si la solución es buena y aprendiendo de dichas recompensas. Una vez que el algoritmo ha sido entrenado, es posible pasarle un nuevo problema y el algoritmo construye una solución cercana a la óptima en tiempos muy cortos.

En la industria muchos problemas de decisión se estructuran como problemas de optimización combinatoria. Las nuevas técnicas de Deep Learning aplicadas a problemas de optimización combinatoria, comienzan a demostrar que pueden ser una alternativa válida a las técnicas de optimización tradicionales con tiempos de respuesta más reducidos. Si esta tendencia se consolida, sin duda, representará una importante oportunidad para el mundo industrial.