Skip to content

Blog


Apprentissage par renforcement pour la logistique à la demande

10 septembre 2018

|

Richard Hwang

Vue d'ensemble

  • Introduction
  • Quel est le problème d'affectation chez DoorDash ?
  • Qu'est-ce que l'apprentissage par renforcement ?
  • Affectation avec apprentissage par renforcement
  • Aller de l'avant
  • Conclusion

Introduction

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

Quel est le problème d'affectation chez DoorDash ?

DoorDash fournit une plateforme en temps réel pour répondre à la demande des consommateurs en biens marchands par le biais d'une flotte flexible de Dasher. Au sein de DoorDash, l'équipe logistique se concentre sur la magie qui s'opère en coulisses, depuis le moment où un consommateur soumet une commande jusqu'au moment où il reçoit cette commande à sa porte, y compris tout ce qui va de la prévision de l'offre et de la demande au suivi automatisé de la livraison. Le problème de l'affectation est un domaine spécifique de la logistique qui traite de la question suivante : quel Dasher doit effectuer quelle livraison ? Notre objectif est d'effectuer des affectations Dasher-livraison qui permettent d'obtenir des vitesses de livraison rapides et une efficacité Dasher saine, où l'efficacité est le nombre de livraisons effectuées par Dasher par unité de temps. Pour prendre ces décisions, nous devons tenir compte de nombreux facteurs, notamment mais pas exclusivement :

  • Temps de parole du consommateur
  • Estimation du temps de préparation des commandes
  • Estimations de voyage
  • Routage (pour les affectations à livraisons multiples)
  • L'utilisation de la machine à laver (pourcentage de temps pendant lequel une machine à laver travaille activement sur une livraison pendant toute la durée d'une équipe).
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'est-ce que l'apprentissage par renforcement ?

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.

État : L'état actuel de l'environnement. Il représente toutes les informations nécessaires pour choisir une action.

Action : L'ensemble de tous les mouvements possibles à un état donné.

Récompense : Le retour d'information résultant de l'action. Les récompenses peuvent être immédiates ou différées.

Politique : La stratégie utilisée pour choisir une action à chaque état.

Agent : L'entité qui prend des mesures et tente d'apprendre la meilleure politique.

Environnement : Le monde avec lequel l'agent interagit.

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.

L'objectif de l'apprentissage par renforcement est de trouver la politique optimale. Cette tâche n'est pas triviale car, contrairement aux processus décisionnels de Markov, les récompenses et les probabilités de transition entre les états sont inconnues, comme le montre la figure 3. C'est pourquoi il existe de nombreuses techniques permettant d'obtenir ces informations (basées sur un modèle) ou d'obtenir directement la politique optimale (sans modèle), telles que Monte Carlo, Bootstrap et SARSA. La plus couramment utilisée est l'apprentissage Q, qui est une méthode sans modèle, hors politique, qui peut directement nous donner une estimation de la fonction Q pour trouver la politique optimale.

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.

Dans la pratique, lorsqu'il y a un grand nombre d'états, l'espace d'état est caractérisé et l'approximation de la fonction est utilisée pour déterminer la fonction Q. Cela fait de la fonction Q un modèle au lieu d'une table de recherche. Cela fait de la fonction Q un modèle plutôt qu'une table de recherche. Souvent, il est difficile d'élaborer manuellement des caractéristiques, c'est pourquoi des modèles d'apprentissage profond tels que les réseaux neuronaux entièrement connectés ou convolutifs sont utilisés pour représenter la fonction Q. Cette approche est connue sous le nom de "Deep Q-N". Cette approche est connue sous le nom de Deep Q-Network (DQN) et est très utile lorsque la dimensionnalité des caractéristiques est élevée et que le volume de données est également important.

Affectation avec apprentissage par renforcement

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.

État : Les livraisons en cours et les Dashers en activité, puisqu'ils représentent l'état actuel du monde du point de vue de l'affectation. Il convient de noter que l'espace des états est pratiquement infini, puisque les livraisons et les coursiers peuvent présenter individuellement de nombreuses caractéristiques différentes (lieu/heure de ramassage, lieu/heure de dépôt, etc.) et qu'il peut y avoir de nombreuses combinaisons différentes de livraisons et de coursiers.

Action : Le choix le plus naturel est l'attribution de Dashers aux livraisons. Cependant, même avec seulement 15 livraisons et 15 Dashers, le nombre total de combinaisons dépasse un trillion ! Par conséquent, pour réduire considérablement l'espace d'action, nous avons défini les actions comme étant différentes variantes de l'algorithme d'affectation avec différents paramètres. On peut considérer qu'il s'agit d'un réglage intelligent des paramètres, le modèle apprenant quels sont les meilleurs paramètres pour un état donné des livraisons et des Casseurs.

Récompense : Combinaison de la vitesse de livraison et de l'efficacité des Dashers. Nous voulons que les livraisons parviennent aux clients le plus rapidement possible tout en utilisant les Dashers le plus efficacement possible. Il s'agit donc de maximiser la vitesse de livraison et l'efficacité des Dasher. La récompense comprend également une pénalité pour les livraisons non livrées, afin de s'assurer que toutes les livraisons sont effectivement attribuées aux Dashers et livrées aux consommateurs.

Une fois ces concepts définis pour s'adapter à l'apprentissage par renforcement, il nous faut maintenant mettre en œuvre les deux composants clés de l'apprentissage par renforcement, à savoir l'environnement et l'agent.

Environnement : Nous avons besoin d'un système capable de produire des états (livraisons et Dashers) et des récompenses (vitesses de livraison et efficacité des Dashers), ainsi que d'accepter des actions (variantes de l'algorithme d'affectation) et d'actualiser ensuite les états et les récompenses. Notre système d'affectation de la production répond à ces critères, mais nous courons le risque de nuire à nos livraisons et à nos clients réels, car l'agent pourrait choisir de mauvaises actions au fur et à mesure qu'il apprend par le biais d'une politique d'exploration. Heureusement, nous disposons déjà d'un simulateur pour notre système d'affectation qui peut intégrer un algorithme d'affectation et produire des affectations simulées qui reflètent notre système de production. Ce simulateur d'affectation est utilisé pour obtenir des résultats hors ligne avant de tenter des expériences en ligne pour le système d'affectation. Nous avons donc utilisé ce simulateur comme environnement, ce qui nous a permis d'entraîner notre modèle d'apprentissage par renforcement sur des états/actions/récompenses qui correspondent à notre système de production sans avoir d'impact sur nos clients.

Agent : Nous avons choisi un réseau neuronal profond comme agent, car il est logique d'utiliser un modèle pour la fonction Q et d'intégrer les états dans des vecteurs à haute dimension, étant donné notre espace d'état infini. Plus de détails sur cette featurisation et ce modèle seront abordés dans la section suivante.

Un résumé de haut niveau de la formulation de notre problème est présenté à la figure 4. En résumé, le simulateur d'affectation produit l'état, que l'agent utilise pour choisir une variante de l'algorithme d'affectation. Le simulateur d'affectation exécute l'algorithme choisi et produit le nouvel état et la récompense, qui sont tous deux transmis à l'agent. Ce cycle se répète à un intervalle de temps prédéfini.

Figure 4: Reinforcement learning applied to the assignment problem

Pour l'implémentation réelle, nous avons intégré le simulateur d'affectation DoorDash dans un environnement OpenAI Gym et utilisé Keras RL pour l'agent et l'entraînement, car les deux bibliothèques sont compatibles en l'état.

Agent profond

Comme indiqué précédemment, nous avons utilisé un réseau neuronal profond comme agent. Rappelons que l'agent associe des paires d'état et d'action à des récompenses. Concrètement, le réseau prend en entrée l'état (représenté par différentes caractéristiques) et prédit la valeur Q pour chaque action, comme le montre la figure 5.

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

Pour notre problème, les caractéristiques générées à partir des états sont destinées à capturer les informations sur les livraisons et les Dashers qui sont utiles pour prédire la valeur Q, c'est-à-dire les futures vitesses de livraison et les efficacités des Dashers. Quelques exemples de ces caractéristiques sont les distances de ramassage et de dépôt, le rapport entre les livraisons et les Dashers, et les temps estimés de préparation des commandes.

Le modèle lui-même est un réseau multicouche dense/pleinement connecté. Quelques paramètres de modèle différents ont été essayés, mais un réglage plus approfondi des hyperparamètres et une exploration de l'architecture seront effectués dans le cadre de travaux futurs.

Ce modèle est formé à l'aide de l'algorithme d'apprentissage Q profond présenté par Mnih et al. dans leur article sur l'apprentissage par renforcement profond. Les détails peuvent être trouvés dans l'article, mais l'idée générale est que l'environnement et l'agent sont utilisés pour générer des états, des actions et des récompenses qui sont stockés en tant qu'expériences. Ces expériences sont ensuite utilisées pour créer des échantillons d'entraînement, que le modèle utilise pour optimiser la valeur Q maximale.

Résultats

L'évaluation a été réalisée en effectuant des affectations pour une journée de données dans une région. Nous avons d'abord obtenu des résultats de base en exécutant le simulateur d'affectation avec l'algorithme d'affectation de la production par défaut et en obtenant les vitesses de livraison moyennes et l'efficacité des laveurs.

Ensuite, pour évaluer si notre modèle a fait mieux, nous avons demandé à notre modèle de choisir le meilleur algorithme d'affectation à utiliser pour chaque état au cours de la même journée et nous avons obtenu les nouvelles vitesses de livraison moyennes et les efficacités du Dasher. Ces résultats montrent que le modèle d'apprentissage par renforcement a permis d'améliorer en moyenne de 6 secondes la vitesse de livraison et de 1,5 seconde l'efficacité du Dasher pour l'ensemble des livraisons. Cela semble peu, mais lorsque des millions de livraisons sont concernées, ces secondes s'additionnent rapidement. Ces résultats prouvent que l'apprentissage par renforcement peut aider à résoudre le problème de l'affectation.

Aller de l'avant

Nous avons fait quelques progrès pendant le hackathon, mais il y a toujours plus à faire. Voici quelques pistes d'amélioration de l'agent :

  • Plus de réglages d'hyperparamètres, par exemple le taux d'apprentissage, la taille des couches cachées.
  • Ajouter des fonctionnalités, c'est-à-dire générer des fonctionnalités supplémentaires à partir des états.
  • Structurer les caractéristiques sous la forme d'une grille en 3D en plaçant les livraisons/dashers dans la grille en fonction de la latitude et de la longitude. L'analogie est une image, qui a une hauteur, une largeur et une profondeur. Nous pouvons alors essayer les réseaux neuronaux convolutifs, qui sont populaires pour les tâches basées sur l'image, en tant qu'agent.

Conclusion

Nous avons vu comment l'application de l'apprentissage par renforcement au problème d'affectation chez DoorDash a permis d'améliorer l'algorithme d'affectation. Nous pensons que l'apprentissage par renforcement est un outil puissant que nous pouvons utiliser pour améliorer notre plateforme de logistique à la demande, et nous sommes enthousiastes à l'idée de pouvoir satisfaire davantage nos clients en utilisant une intelligence artificielle avancée.

Nous serions ravis de connaître vos applications de production de l'apprentissage par renforcement. Si la résolution de ce type de problèmes vous passionne, rejoignez l'équipe!

Remerciements

Merci à toute l'équipe du hackathon pour avoir travaillé sur ce projet : Anne Zhou, Gary Ren, Ivy Wang, Richard Hwang, Sifeng Lin, Yixin Tang. Et merci au comité du hackathon pour l'organisation d'un autre hackathon amusant !

About the Author

Emplois connexes

Job ID: 2915998
Localisation
Sao Paulo, Brazil
Département
Ingénierie
Localisation
Sunnyvale, CA
Département
Ingénierie
Localisation
Pune, Inde
Département
Ingénierie
Localisation
São Paulo, Brésil
Département
Ingénierie
Localisation
San Francisco, CA; Tempe, AZ
Département
Ingénierie