Ir al contenido

Blog


Aprendizaje por refuerzo para la logística a la carta

10 de septiembre de 2018

|

Richard Hwang

Visión general

  • Introducción
  • ¿Cuál es el problema de asignación en DoorDash?
  • ¿Qué es el aprendizaje por refuerzo?
  • Asignación aprendida por refuerzo
  • Avanzar
  • Conclusión

Introducción

DoorDash recently held our thirteenth hackathon. Hackathons are our opportunity to explore new technologies and moon-shot ideas; they help us stay up-to-date with the world and think 10x. At DoorDash, we‚Äôre constantly thinking of ways to improve the customer experience, from reducing delivery times to increasing Dasher efficiency. Algorithms and artificial intelligence help lay the foundation for delightful customer experiences, and for this hackathon, we wanted to see if more advanced techniques could further improve our product. Our team of six applied an artificial intelligence technique called reinforcement learning to the assignment problem at DoorDash, beating our production algorithm in a simulation environment with both quicker delivery speeds and higher Dasher efficiencies. In this post, we will describe what that means and how we accomplished it.

The hackathon team

¿Cuál es el problema de asignación en DoorDash?

DoorDash ofrece una plataforma en tiempo real para satisfacer la demanda de los consumidores de productos comerciales a través de una flota Dasher flexible. Dentro de DoorDash, el equipo de logística se centra en la magia que ocurre entre bastidores desde que un consumidor envía un pedido hasta que lo recibe en la puerta de su casa, incluyendo todo, desde la previsión de la oferta y la demanda hasta la supervisión automatizada de las entregas. El problema de la asignación es un área específica dentro de la logística que se ocupa de la siguiente cuestión: ¿qué Dasher debe realizar qué entrega? Nuestro objetivo es realizar asignaciones Dasher-entrega que produzcan velocidades de entrega rápidas y una eficiencia Dasher saludable, donde la eficiencia es el número de entregas realizadas por Dasher por unidad de tiempo. Para tomar estas decisiones, debemos tener en cuenta muchos factores, entre los que se incluyen:

  • Tiempos de cotización de los consumidores
  • Tiempos estimados de preparación de los pedidos
  • Previsiones de viaje
  • Enrutamiento (para asignaciones multientrega)
  • Utilización del Dasher (porcentaje de tiempo que un Dasher está trabajando activamente en una entrega durante todo el turno)
Figure 1: Assignment problem at DoorDash

The assignment algorithm at DoorDash has been crafted over the years to consider all these factors and more, in order to best serve consumers, merchants, and dashers. However, given the breadth of the assignment problem, and the fact that we don‚Äôt have ground truths for what the best assignments are, improvements to the algorithm do not always come easily. When Hackathon XIII rolled around, we wondered, ‚ÄúCould an artificially intelligent assignment algorithm learn to improve itself?‚Äù.

¿Qué es el aprendizaje por refuerzo?

Reinforcement learning is one of the most popular and powerful artificial intelligence algorithms today. Instances of reinforcement learning have reached mainstream news, such as AlphaGo, the reinforcement learned computer program that defeated the world‚Äôs top Go player. In short, the goal of reinforcement learning is to learn the best action given a state of the environment, in order to maximize the overall rewards. Here are the fundamental concepts in reinforcement learning, summarized in Figure 2.

Estado: El estado actual del entorno. Representa toda la información necesaria para elegir una acción.

Acción: El conjunto de todos los movimientos posibles en un estado.

Recompensa: La retroalimentación como resultado de la acción. Tenga en cuenta que las recompensas pueden ser inmediatas o diferidas.

Política: La estrategia utilizada para elegir una acción en cada estado.

Agente: La entidad que toma acciones e intenta aprender la mejor política.

Entorno: El mundo con el que interactúa el agente.

Figure 2: Conceptual overview of reinforcement learning

Here’s an example application to illustrate these concepts. Let’s say we are designing a delivery robot and teaching it to pick up delivery items while avoiding pedestrians. In this case the robot is an agent trying to learn the optimal policy, i.e. optimal action in each state. The states can be the area that robot is operating in, with the items and pedestrians at various locations, and the actions can be move left, right, forward, or backward. The robot receives a positive reward when it picks up an item, a negative reward when it runs into a pedestrian, and no reward otherwise. With these settings the robot can learn the optimal policy to pick up all the items in a way that maximizes the reward.

El objetivo del aprendizaje por refuerzo es encontrar la política óptima. Esto no es trivial ya que, a diferencia de los procesos de decisión de Markov, las recompensas y las probabilidades de transición entre estados son desconocidas, como se ve en la figura 3. Por este motivo, existen muchas técnicas para obtener esta información (basadas en modelos) u obtener directamente la política óptima (sin modelos), como Monte Carlo, Bootstrap y SARSA. La más utilizada es el aprendizaje Q, que es un método sin modelo y sin política que puede darnos directamente una estimación de la función Q para encontrar la política óptima.

Figure 3: Markov Decision Process with Unknown Transition Matrix Pij

It is worth mentioning that to use Q-learning, we need to collect data by following an exploration policy. When we are more concerned with learning about the world than maximizing utility, we can choose a no-exploitation, all-exploration policy, which explores the action space by always choosing a random action. When we care more about utility, we need to balance exploration and exploitation, so that we can reap the benefits of what we‚Äôve learned while still not being blind to opportunities that we haven‚Äôt yet encountered. One common approach in the second case is the epsilon-greedy algorithm, which explores with probability epsilon and exploits with probability 1-epsilon.

En la práctica, cuando hay un gran número de estados, se featuriza el espacio de estados y se utiliza la aproximación de funciones para determinar la función Q. Esto hace que la función Q sea un modelo en lugar de una tabla de búsqueda. A menudo, es difícil crear características a mano, por lo que se utilizan modelos de aprendizaje profundo, como redes neuronales totalmente conectadas o convolucionales, para representar la función Q. Este enfoque se conoce como Q-N profundo. Este enfoque se conoce como Deep Q-Network (DQN) y es muy útil cuando la dimensionalidad de las características es alta y el volumen de datos también.

Asignación aprendida por refuerzo

Now we will discuss how we applied reinforcement learning to the DoorDash assignment problem. To formulate the assignment problem in a way that’s suitable for reinforcement learning, we made the following definitions.

Estado: Las entregas pendientes y los Dashers en funcionamiento, ya que representan el estado actual del mundo desde una perspectiva de asignación. Nótese que esto significa que el espacio de estados es prácticamente infinito, ya que las entregas y los Dashers individualmente pueden tener muchas características diferentes (lugar/hora de recogida, lugar/hora de entrega, etc.) y puede haber muchas combinaciones diferentes de entregas y Dashers.

Acción: La opción más natural es la asignación de Dashers a las entregas. Sin embargo, incluso con sólo 15 entregas y 15 Dashers, ¡el número total de combinaciones supera el billón! Por lo tanto, para reducir significativamente el espacio de acciones, definimos las acciones como diferentes variantes del algoritmo de asignación con diferentes parámetros. Esto puede considerarse como un ajuste inteligente de parámetros, en el que el modelo aprende qué parámetros son los mejores para un determinado estado de entregas y Dashers.

Recompensa: Combinación de velocidad de entrega y eficiencia del Dasher. Queremos que las entregas lleguen a los clientes lo más rápido posible, utilizando al mismo tiempo los Dasher de la forma más eficiente posible. Esto se traduce en maximizar la velocidad de entrega y maximizar la eficiencia del Dasher. La recompensa también incluye una penalización por entregas no entregadas, para garantizar que todas las entregas se asignan realmente a Dashers y se entregan a los consumidores.

Con estos conceptos definidos para encajar con el aprendizaje por refuerzo, ahora necesitábamos implementar los dos componentes clave para realizar realmente el aprendizaje por refuerzo, el entorno y el agente.

Entorno: Necesitamos un sistema que pueda generar estados (entregas y Dashers) y recompensas (velocidades de entrega y eficiencias de Dasher), así como recibir acciones (variantes del algoritmo de asignación) y actualizar posteriormente los estados y las recompensas. Nuestro sistema de asignación de la producción cumple los requisitos, pero corremos el riesgo de perjudicar a nuestras entregas y clientes reales, ya que el agente podría elegir malas acciones a medida que aprende mediante una política de exploración. Afortunadamente, ya disponemos de un simulador para nuestro sistema de asignación que puede tomar un algoritmo de asignación y producir asignaciones simuladas que reflejen nuestro sistema de producción. Este simulador de asignaciones se utiliza para obtener resultados offline antes de probar experimentos online para el sistema de asignaciones. Por lo tanto, utilizamos este simulador como nuestro entorno, lo que nos permite entrenar nuestro modelo de aprendizaje por refuerzo en estados/acciones/recompensas que son precisos para nuestro sistema de producción sin afectar a nuestros clientes.

Agente: Elegimos una red neuronal profunda como agente, ya que tiene sentido utilizar un modelo para la función Q y featurizar los estados en vectores de alta dimensión, dado nuestro espacio de estado infinito. Más detalles sobre esta featurización y el modelo se tratarán en la siguiente sección.

En la figura 4 se muestra un resumen de alto nivel de la formulación de nuestro problema. En resumen, el simulador de asignación genera el estado, que el agente utiliza para elegir una variante del algoritmo de asignación. El simulador de asignación ejecuta el algoritmo elegido y genera el nuevo estado y la recompensa, que se devuelven al agente. Este ciclo se repite en un intervalo de tiempo preestablecido.

Figure 4: Reinforcement learning applied to the assignment problem

Para la implementación real, envolvimos el simulador de asignación de DoorDash en un entorno OpenAI Gym y utilizamos Keras RL para el agente y el entrenamiento, ya que las dos bibliotecas son compatibles fuera de la caja.

Agente profundo

Como ya hemos mencionado, utilizamos una red neuronal profunda como agente. Recordemos que el agente asigna pares de estado y acción a recompensas. Concretamente, la red toma como entrada el estado (representado como diferentes características) y predice el valor Q para cada acción, como se ve en la Figura 5.

Figure 5: Neural network as Q(s, a) approximators

Para nuestro problema, las características generadas a partir de los estados pretenden capturar la información sobre las entregas y los Dashers que son útiles para predecir el valor Q, que son las velocidades de entrega futuras y las eficiencias de los Dasher. Algunos ejemplos de estas características son las distancias de recogida y entrega, la relación entre entregas y Dasher y los tiempos estimados de preparación de los pedidos.

El modelo en sí es una red multicapa densa y totalmente conectada. Se probaron algunos parámetros diferentes del modelo, pero en futuros trabajos se llevará a cabo un ajuste más exhaustivo de los hiperparámetros y una exploración de la arquitectura.

Este modelo se entrena utilizando el algoritmo de aprendizaje Q profundo presentado por Mnih et al. en su artículo Deep Reinforcement Learning. Los detalles se pueden encontrar en el artículo, pero la idea general es que el entorno y el agente se utilizan para generar estados, acciones y recompensas que se almacenan como experiencias. A partir de estas experiencias se crean muestras de entrenamiento que el modelo utiliza para optimizar hacia el valor Q máximo.

Resultados

La evaluación se realizó realizando asignaciones para un día de datos en una región. Primero obtuvimos resultados de referencia ejecutando el simulador de asignaciones con el algoritmo de asignación de producción por defecto y obteniendo las velocidades medias de entrega y las eficiencias Dasher.

A continuación, para evaluar si nuestro modelo lo hacía mejor, hicimos que nuestro modelo eligiera el mejor algoritmo de asignación para cada estado durante ese mismo día y obtuvimos las nuevas velocidades medias de entrega y las eficiencias de Dasher. Estos resultados muestran que el modelo aprendido por refuerzo logró una mejora media de 6 segundos en la velocidad de entrega y de 1,5 segundos en la eficiencia de Dasher en todas las entregas. No parece mucho, pero cuando se trata de millones de entregas, estos segundos se acumulan rápidamente. Estos resultados demuestran que el aprendizaje por refuerzo puede ayudar con el problema de la asignación.

Avanzar

Hemos hecho algunos progresos durante el hackathon, pero siempre hay algo más que hacer. Estas son algunas formas en las que nos gustaría mejorar el agente:

  • Más ajuste de hiperparámetros, como la velocidad de aprendizaje o el tamaño de las capas ocultas.
  • Añadir más características, es decir, generar más características a partir de los estados.
  • Estructurar las características en forma de cuadrícula tridimensional colocando en la cuadrícula entregas/destinos en función de la latitud y la longitud. La analogía es una imagen, que tiene altura, anchura y profundidad. Podemos probar con redes neuronales convolucionales, muy populares para tareas basadas en imágenes, como agente.

Conclusión

Hemos visto cómo la aplicación del aprendizaje por refuerzo al problema de asignación en DoorDash ha dado lugar a un algoritmo de asignación mejorado. Creemos que el aprendizaje por refuerzo es una poderosa herramienta que podemos utilizar para mejorar nuestra plataforma de logística a la carta, y estamos entusiasmados con la oportunidad de seguir deleitando a nuestros clientes utilizando inteligencia artificial avanzada".

Nos encantaría conocer sus aplicaciones de aprendizaje por refuerzo. Si te apasiona resolver este tipo de problemas, ¡únete al equipo!

Agradecimientos

Gracias a todo el equipo del hackathon por trabajar en este proyecto: Anne Zhou, Gary Ren, Ivy Wang, Richard Hwang, Sifeng Lin, Yixin Tang. Y gracias al comité del hackathon por organizar otro divertido hackathon.

About the Author

Trabajos relacionados

Job ID: 2915998
Ubicación
Sao Paulo, Brazil
Departamento
Ingeniería
Ubicación
Sunnyvale, CA
Departamento
Ingeniería
Ubicación
Pune, India
Departamento
Ingeniería
Ubicación
São Paulo, Brasil
Departamento
Ingeniería
Job ID: 2739485
Ubicación
San Francisco, CA; Tempe, AZ
Departamento
Ingeniería