Brevet FR3087922A1 — publié le 20200501

PROCÉDÉS ET SYSTÈMES D'APPRENTISSAGE DE RENFORCEMENT POUR LE CONTRÔLE D'INVENTAIRE ET L'OPTIMISATION DOMAINE DE L'INVENTION [0001) La présente invention concerne les systèmes et procédés techniques pour améliorer le contrôle d'inventaire et l'optimisation. Des modes de réalisation de l'invention emploient notamment des technologies d'apprentissage 10 automatique et spécifiquement l'apprentissage de renforcement, dans la mise en oeuvre de systèmes de gestion des recettes améliorés. CONTEXTE DE L'INVENTION [0002] Les systèmes d'inventaire sont employés dans de nombreux secteurs pour contrôler la disponibilité des ressources, par exemple via la tarification et la 15 gestion des recettes, et tout autre calcul associé. Les systèmes d'inventaire permettent à des consommateurs d'acheter ou de réserver des ressources ou des produits disponibles proposés par les fournisseurs. De plus, les systèmes d'inventaire permettent aux fournisseurs de gérer les ressources disponibles et de maximiser les recettes et le profit en fournissant ces ressources aux 20 consommateurs. [0003] Dans ce contexte, le terme « gestion des recettes » fait référence à l'application d'analyse de données pour prédire le comportement du consommateur et pour optimiser les offres de produits et la tarification afin de maximiser ia croissance des recettes. La gestion des recettes et la tarification 2 revêtent une importance particulière dans les secteurs de l'hôtellerie, du voyage et des transports qui sont tous caractérisés par un « inventaire périssable », c.-àd. des places inoccupées, telles que des chambres ou des sièges, représentent une perte de revenus irrécouvrables, une fois que l'horizon de leur utilisation est passé. La tarification et la gestion des recettes font partie des moyens les plus efficaces pour que les opérateurs de ces secteurs puissent améliorer les performances commerciales et financières. De façon significative, la tarification est un outil puissant dans la gestion de capacité et l'équilibrage de charge. Par conséquent, les dernières décennies ont vu les développements de systèmes de 10 gestion des revenus automatiques sophistiqués dans ces secteurs. [0004] Par exemple, un système de gestion des recettes (RMS) d'une compagnie aérienne est un système automatique conçu pour maximiser les recettes des vols générées à partir de tous les sièges disponibles sur une période de réservation (typiquement un an). Le RMS est utilisé pour fixer les politiques 15 concernant la disponibilité et la tarification des sièges (tarifs aériens) dans le temps pour atteindre des recettes maximums. [0005] Un RMS conventionnel est un système modélisé, c.-à-d. qu'il est basé sur un modèle de recettes et :Je réservations. Le modèle est spécifiquement conçu pour stimuler les opérations et, par conséquent, il contient nécessairement 20 de nombreuses hypothèses, estimations et heuristiques. Elles incluent la prédiction/le modelage du comportement du consommateur, la prévision de la demande (volume et modèle), l'optimisation de l'occupation des sièges sur des étapes de vol individuelles ainsi que sur tout le réseau, et la réservation. [0006] Cependant, le RMS conventionnel a de nombreux inconvénients et 25 limites. Premièrement, le RMS est dépendant des hypothèses qui peuvent être non valides. Par exemple, le RMS suppose que le futur est précisément décrit par le passé, ce qui n'est pas le cas s'il existe des changements dans l'environnement commercial (par ex., de nouveaux concurrents), des changements dans la demande et la sensibilité du consommateur aux prix, ou 3 des changements dans le comportement du consommateur. Il suppose également que ie comportement du consommateur est rationnel. De plus, les modèles de RMS conventionnels traitent le marché comme un monopole, en supposant que les actions des concurrents sont implicitement comptabilisées dans le comportement du consommateur. [0007] Un autre inconvénient de l'approche conventionnelle du RMS est qu'il existe en général une interdépendance entre le modèle et ses entrées, de sorte que tout changement des données d'entrée disponibles exige la modification ou la reconstruction du modèle pour exploiter ou tenir compte des nouvelles informations ou des informations modifiées. De plus, les systèmes modelés sans intervention humaine réagissent lentement aux changements de la demande qui sont faiblement représentés ou non représentés, dans les données historiques sur lesquelles se base le modèle. [0008] Il serait par conséquent souhaitable de développer des systèmes améliorés capables de surmonter, ou au moins d'atténuer, un ou plusieurs des inconvénients et limites du RMS conventionnel. RÉSUMÉ DE L'INVENTION [0009] Les modes de réalisation de l'invention mettent en oeuvre une approche de gestion des recettes basée sur les techniques d'apprentissage automatique (ML). Cette approche inclut avantageusement la fourniture d'un système d'apprentissage de renforcement (RL) qui utilise les observations de données historiques et de données en temps réel (par ex., les clichés d'inventaire) pour générer des sorties, telles que la tarification recommandée °t'ou les politiques de disponibilités, pour optimiser les recettes. [0010] L'apprentissage de renforcement est une technique ML qui peut être appliquée aux problèmes de décision séquentiels, tels que, dans des modes de réalisation de l'invention, la détermination des politiques devant être établies à tout moment avec pour objectif d'optimiser les recettes sur le long terme, sur la base des observations de l'état actuel du système, c.-à-d. les réservations et l'inventaire disponible sur une période de réservation prédéterminée. Avantageusement, un agent RL entreprend des actions uniquement sur la base 5 des observations de l'état du système, et reçoit une rétroaction sous la forme d'un état successeur atteint en conséquence d'actions passées, et un renforcement ou « récompense », par ex., une mesure sur l'efficacité de ces actions pour atteindre l'objectif. L'agent RE.. « apprend » ainsi avec le temps, les actions optimales à entreprendre dans tout état donné pour atteindre l'objectif, tel 10 qu'une politique de prix/tarifaire et de disponibilité devant être établie, de sorte à maximiser les recettes sur une période de réservation. ] Plus particulièrement, dans un aspect, la présente invention fournit un procédé d'apprentissage de renforcement pour un agent de gestion des ressources dans un système de gestion d'inventaire concernant des ressources 15 périssables ayant un horizon de vente, tout en cherchant à optimiser les recettes générées à partir de celui-ci, dans lequel l'inventaire dispose d'un état associé comprenant une disponibilité restante des ressources périssables et une période restante de l'horizon de vente, le procédé comprenant la génération d'une pluralité d'actions, chaque action comprenant la 20 publication de données définissant un programme de tarification des ressources sables restant dans l'inventaire ; la réception, en réponse à la pluralité d'actions, d'une pluralité correspondante d'observations, chaque observation comprenant une transition dans l'état associé à l'inventaire et une récompense associée sous la forme de 25 recettes générées par la vente des ressources périssables ; le stockage des observations reçues dans une mémoire de relecture ; l'échantillonnage périodique, à partir de la mémoire de relecture, d'un lot aléatoire d'observations selon un algorithme d'échantillonnage de relecture par ordre de priorité dans lequel, tout au long d'une période d'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement adaptée à partir d'une distribution favorisant la sélection d'observations correspondant à des transitions proches d'un état terminal vers 5 une distribution favorisant la sélection d'observations correspondant â des transitions proches d'un état initial ; et l'utilisation de chaque lot aléatoire d'observations pour mettre à jour les paramètres de pondération d'un réseau neuronal qui comprend un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources, de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du réseau neuronal se rapproche plus près d'une vraie valeur de génération de l'action d'entrée tandis qu'il est dans l'état d'inventaire d'entrée, dans lequel le réseau neuronal peut être utilisé pour sélectionner 10 chacune de la pluralité d'actions générées en fonction d'un état correspondant associé à l'inventaire. [0012] Avantageusement,des simulations d'étalonnage ont démontré qu'un agent de gestion des ressources RL mettant en oeuvre le procédé de l'invention 15 fournit des performances améliorées par rapport à des systèmes de gestion des ressources de l'état de l'art antérieur, étant donné les données d'observation permettant d'apprendre. Par ailleurs, puisque les transitions d'état observées et les récompenses changeront avec tout changement sur le marché des ressources périssables, l'agent est capable de réagir à de tels changements sans 20 intervention humaine. L'agent ne requiert aucun modèle de marché ou de comportement du consommateur pour s'adapter, c.-à-d. qu'il est exempt de modèle et de toute hypothèse correspondante. [0013] Avantageusement, afin de réduire le montant de données requises pour l'entraînement initial de l'agent RI_, des modes de réalisation de l'invention 25 emploient une approche d'apprentissage profond (DL). Le réseau neuronal peut notamment être un réseau neuronal profond (DNN). [0014] Dans des modes de réalisation de l'invention, le réseau neuronal peut être initialisé par un procédé de transfert de connaissances (c.-à-d. une forme d'apprentissage supervisé) â partir d'un système de gestion des recettes existant 6 pour fournir un « démarrage à chaud » à l'agent de gestion des ressources. Un procédé de transfert des connaissances peut comprendre les étapes de détermination d'une fonction de valeur associée au système de gestion des recettes existant, dans lequel la fonction de valeur mappe les états 5 associés à l'inventaire à des valeurs estimées correspondantes ; de transformation de la fonction de valeur en une fonction action - valeur transformée correspondante adaptée à l'agent de gestion des ressources, dans laquelle la transformation comprend la mise en correspondance d'une taille d'étape temporelle avec une étape temporelle associée à l'agent de gestion des 10 ressources et l'ajout de dimensions d'action à la valeur de fonction d'échantillonnage de la fonction action - valeur transformée pour générer un ensemble de données d'entrainernent pour le réseau neuronal ; et d'entraînement du réseau neuronal en utilisant l'ensemble de données d'entraînement. 15 [0015:1 Avantageusement, en employant un procédé de transfert des connaissances, l'agent de gestion des ressources peut exiger un volume sensiblement réduit de données supplémentaires pour apprendre des actions politiques optimales ou presque optimales. Initialement, au moins, un tel mode de réalisation de l'invention génère, de manière équivalente au système de gestion 20 des revenus existant, les mêmes actions en réponse au même état d'inventaire. Ensuite, l'agent de gestion des ressources peut apprendre à dépasser le système de gestion des revenus existant à partir duquel ses connaissances initiales ont été transférées. [0016] Dans certains modes de réalisation, l'agent de gestion des ressources 25 peut être configure pour commuter entre une approximation de fonction action - valeur en utilisant le réseau neuronal et une approche d'apprentissage Q basée sur une représentation sous forme de tableau de la fonction action - valeur. Un procédé de commutation peut notamment comprendre : pour chaque état et action, le calcul d'une valeur action 30 correspondante en utilisant le réseau neuronal, et le peuplement d'une entrée dans un tableau de consultation action - valeur avec la valeur calculée ; et la commutation vers un mode de fonctionnement d'apprentissage Q en utilisant le tableau de consultation action - valeur. [0017] Un autre procédé pour commuter vers l'approximation action - valeur 5 basée sur le réseau neuronal peut comprendre : l'échantillonnage du tableau de consultation action - valeur pour générer un ensemble de données d'entraînement pour le réseau neuronal l'entraînement du réseau neuronal en utilisant l'ensemble de données d'entraînement ; et 10 la commutation vers un modèle de fonctionnement d'approximation de fonction du réseau neuronal en utilisant le réseau neuronal entraîné. [0018] Avantageusement, l'apport d'une capacité de commutation entre une approximation de fonction basée sur le réseau neuronal et des modes de fonctionnement d'apprentissage Q sous forme de tableau permet d'obtenir les 15 avantages des deux approches, comme souhaité. Spécifiquement, dans le mode de fonctionnement du réseau neuronal, l'agent de gestion des ressources est capable d'apprendre et d'adapter les changements en utilisant des quantités beaucoup plus petites de données observées par rapport au mode d'apprentissage Q sous forme de tableau, et peut efficacement continuer à 20 explorer des stratégies alternatives en ligne en se s'entraînant et en s'adaptant continuellement en utilisant des procédés de relecture d'expérience. Cependant, sur un marché stable, le mode d'apprentissage Q sous forme de tableau peut permettre à l'agent de gestion des ressources d'exploiter plus efficacement les connaissances contenues dans le tableau action - valeur. 25 [0019] Tandis que des modes de réalisation de l'invention sont capables de fonctionner, d'apprendre et de s'adapter en ligne, en utilisant des observations en direct de l'état d'inventaire et les données du marché, il est aussi avantageusement possible d'entraîner et d'étalonner un mode de réalisation en utilisant un simulateur de marché. Un simulateur de marché peut inclure un module de génération de la demande simulé, un système de réservation simulé et un module de simulation de choix. Le simulateur de marché peut par ailleurs inclure des systèmes d'inventaire concurrents simulés. [0020] Dans un autre aspect l'invention fournit un système de gestion d'un 5 inventaire de ressources périssables ayant un horizon de vente, tout en cherchant à optimiser les recettes générées à partir de celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante des ressources périssables et une période restante d'horizon de vente, le système comprenant : 10 un module d'agent de gestion des ressources mis en oeuvre par ordinateur ; un module de réseau neuronal mis en oeuvre par ordinateur comprenant un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources ; 15 un module de mémoire de relecture ; et un module d'apprentissage mis en oeuvre par ordinateur dans lequel le module d'agent de gestion des ressources est configuré pour : générer une pluralité d'actions, chaque action é tant déterminée 20 en interrogeant le module de réseau neuronal en utilisant un état actuel associé à l'inventaire et comprenant la publication de données définissant un programme de tarification concernant les ressources périssables restant dans l'inventaire recevoir, en réponse à la pluralité d'actions, une pluralité 25 correspondante d'observations, chaque observation comprenant une dans l'état associé à l'inventaire et une récompense associée sous la forme de recettes générées par la vente de ressources périssables ; et stocker, dans le module de mémoire de relecture, les observations reçues, dans lequel le module d'apprentissage est configuré pour 30 échantillonner périodiquement, à partir de la mémoire de relecture, un lot aléatoire d'observations conformément à un algorithme d'échantillonnage de relecture par ordre de priorité dans lequel, tout au 9 long d'une période 'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement adaptée à partir d'une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état terminal vers une 5 distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état initial ; et utiliser chaque lot aléatoire d'observations pour mettre â jour les paramètres de pondération du module du réseau neuronal, de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action 10 d'entrée, une sortie du module du réseau neuronal s'approche plus étroitement d'une vraie valeur de génération de l'action d'entrée tandis qu'il est dans l'état d'inventaire d'entrée. [0021] Dans un autre aspect, l'invention fournit un système informatique pour gérer un inventaire de ressources périssables ayant un horizon de vente, tout en 15 cherchant à optimiser les recettes générées à partir de celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante des ressources périssables et une période restante de l'horizon de vente, le système comprenant : un processeur ; 20 au moins un dispositif de mémoire accessible par le processeur ; et une interface de communication accessible par le processeur, dans lequel le dispositif de mémoire contient une mémoire de relecture et un corps d'instructions de programme qui, lorsqu'il est exécuté par le processeur, amène le système informatique à mettre en oeuvre un procédé comprenant les 25 étapes : de génération d'une pluralité d'actions, chaque action comprenant la publication, via l'interface de communication, de données définissant un programme de tarification concernant les ressources périssables restant dans l'inventaire 30 de réception, via l'interface de communication et en réponse à la pluralité d'actions, une pluralité correspondante d'observations, chaque observation comprenant une transition dans l'état associé à l' 10 inventaire et une récompense associée sous la forme de recettes s par la vente de ressources périssables ; de stockage des observations reçues dans la mémoire de relecture ; 5 périodiquement d'échantillonnage, à partir de la mémoire de relecture, d'un lot aléatoire d'observations conformément à un algorithme d'échantillonnage de relecture par ordre de priorité dans lequel, tout au long d'une période d'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement 10 adaptée à partir d'une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état terminal vers une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état initial ; et d'utilisation de chaque lot aléatoire d'observations pour mettre à 15 jour des paramètres de pondération d'un réseau neuronal qui comprend un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources, de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du réseau neuronal se rapproche plus près d'une vraie valeur de génération de 20 l'action d'entrée tandis qu'il est dans l'état d'inventaire d'entrée. dans lequel le réseau neuronal peut être utilisé pour sélectionner chacune de la pluralité d'actions générées en fonction d'un état correspondant associé à l'inventaire. [0022] Dans un autre aspect, l'invention fournit un produit programme 25 d'ordinateur comprenant un support tangible lisible par ordinateur avec des instructions stockées sur celui-ci qui, lorsqu'il est exécuté par un processeur met en oeuvre un procédé d'apprentissage de renforcement pour un agent de gestion des ressources dans un système de gestion d'un inventaire des ressources périssables ayant un horizon de vente, tout en cherchant à optimiser les recettes 30 générées à partir de celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante de ressources périssables et une période restante de l'horizon de vente, le procédé comprenant 11 la génération d'une pluralité d'actions, chaque action comprenant la publication de données définissant un programme de tarification des ressources périssables restant dans l'inventaire ; la réception, en réponse à la pluralité d'actions, d'une pluralité 5 correspondante d'observations, chaque observation comprenant une transition dans l'état associé â l'inventaire et une récompense associée sous la forme de recettes générées par la vente des ressources périssables ; le stockage des observations reçues dans une mémoire de relecture ; l'échantillonnage périodique, à partir de la mémoire de relecture, d'un 10 lot aléatoire d'observations selon un algorithme d'échantillonnage de relecture par ordre de priorité dans lequel, tout au long d'une période d'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement adaptée à partir d'une distribution favorisant la sélection d'observations correspondant à des transitions proches d'un état terminal vers 15 une distribution favorisant la sélection d'observations correspondant à des transitions proches d'un état initial ; et l'utilisation de chaque lot aléatoire d'observations pour mettre à jour les paramètres de pondération d'un réseau neuronal qui comprend un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources, 20 de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du réseau neuronal se rapproche plus près d'une vraie valeur de génération de l'action d'entrée tandis qu'il est dans l'état d'inventaire d'entrée, dans lequel le réseau neuronal peut être utilisé pour sélectionner chacune de la pluralité d'actions générées en fonction d'un état correspondant 25 associé à l'inventaire. [0023] À partir de la description qui suit des divers modes de réalisation, d'autres aspects, avantages et caractéristiques des modes de réalisation de l'invention seront apparents aux hommes de métier spécialises dans les domaines pertinents. On notera cependant, que l'invention n'est pas limitée aux 30 modes de réalisation décrit qui sont fournis à titre d'illustration des principes de l'invention tels qu'ils sont définis dans les déclarations ci-dessus et pour assister les hommes de métier à mettre en pratique ces principes. BRÈVE DESCRIPTION DES DESSINS [0024] Des modes de réalisation de l'invention seront maintenant décrits en référence aux dessins accompagnant dans lesquels des numéros référentiels font référence à des caractéristiques similaires et dans lesquels : 5 La Figure 1 est un diagramme bloc illustrant un système en réseau exemplaire incluant un système d'inventaire mettant en oeuvre l'invention ; La Figure 2 est un diagramme bloc fonctionnel d'un système d'inventaire exemplaire mettant en oeuvre l'invention ' La Figure 3 est un diagramme bloc d'un simulateur de marché de 10 voyages aériens appropriés pour l'entraînement et/ou l'évaluation d'un système de gestion des recettes d'apprentissage de renforcement incitant en oeuvre l'invention ; La Figure 4 est un diagramme bloc d'un système de gestion des recettes d'apprentissage de renforcement mettant en oeuvre l'invention qui 15 emploie une approche d'apprentissage Q en tableau ; La Figure 5 illustre un tableau illustrant les performances du système de gestion des recettes d'apprentissage Q de renforcement de la Figure 4, lorsqu'il interagit avec un environnement simulé ; La Figure 6A est un diagramme bloc d'un système de gestion des 20 recettes d'apprentissage de renforcement mettant en oeuvre l'invention qui emploie une approche d'apprentissage Q profond ; La Figure 6B est un organigramme illustrant un procédé d'échantillonnage et de mise â jour, conformément à une approche de éponse par ordre de priorité mettant en oeuvre l'invention ; 25 La Figure 7 illustre un tableau illustrant les performances du système de gestion des recettes d'apprentissage Q de renforcement profond de la Figure 6, lorsqu'il interagit avec un environnement simulé ; La Figure 8A est un organigramme illustrant un procédé de transfert des connaissances pour initialiser un système de gestion des recettes 30 d'apprentissage de renforcement mettant en oeuvre l'invention ; La Figure 8B est un organigramme illustrant des informations supplémentaires sur le procédé de transfert des connaissances de la Figure 8A ; La Figure 9 est un organigramme illustrant un procédé de comma d'une opération d'apprentissage Q profond à une opération d'apprentissage tableau dans un système de gestion des recettes d'apprentissage de renforcement contenant l'invention ; 5 La Figure 10 est un tableau représentant une évaluation des performances d'algorithmes de gestion des recettes de l'état de la technique antérieur utilisant le simulateur de marché de la Figure 3 ; La Figure 11 est un tableau représentant une évaluation des performances d'un système de gestion des recettes d'apprentissage de 10 renforcement contenant l'invention qui utilise le simulateur de marché de la Figure 3 ; La Figure 12 est un tableau montrant des courbes de réservation qui correspondent à l'évaluation des performances de la Figure 10 ; La Figure 13 est un tableau représentant des courbes de réservation 15 qui correspondent à l'étalonnage des performances de la Figure 11 ; et La Figure 14 est un tableau illustrant l'effet de politiques tarifaires sélectionnées par un système de gestion des recettes de l'état de la technique antérieur et un système de gestion des recettes d'apprentissage de renforcement 20 contenant l'invention qui utilise le simulateur de marché de la Figure 3 DESCRIPTION DÉTAILLÉE DES MODES DE RÉALISATION [00251 La Figure 1 est un organigramme illustrant un système en réseau exemplaire 100 qui inclut un système d'inventaire 102 mettant en oeuvre l'invention. Le système d'inventaire 102 comprend notamment un système 25 d'apprentissage de renforcement (RO configure pour effectuer une optimisation des recettes conformément au mode de réalisation de l'invention. Concrètement, un mode de réalisation de l'invention est décrit en référence à un système d'optimisation des recettes et d'inventaire pour la vente et la réservation de sièges d'avion, dans lequel le système en réseau 100 comprend en général un 30 système de réservation de compagnies aériennes et le système d'inventaire 102 14 comprend un système d'inventaire une compagnie aérienne en particulier. Cependant, on notera qu'il s'agit d'un simple exemple pour illustrer le système et le procédé et on notera que d'autres modes de réalisation de l'invention peuvent s'appliquer aux systèmes de gestion des recettes et d'inventaire, autres que ceux liés à la vente et à la réservation de sièges d'avion. [0026] Le système d'inventaire de compagnies aériennes 102 peut comprendre un système informatique ayant une architecture conventionnelle. En particulier, le système d'inventaire de compagnies aériennes 102, tel qu'il est illustré, comprend un processeur 104. Le processeur 104 est associé de façon 10 fonctionnelle à un dispositif de stockage/mémoire non volatile 106, par ex. via un ou plusieurs bus de données/adresses 108 tel qu'illustré. Le stockage non volatile 106 peut être un disque dur et/ou peut inclure une mémoire non volatile à état défini, telle qu'une mémoire morte ROM, une mémoire flash, un disque dur électronique SSD ou autre stockage similaire. Le processeur 104 sert aussi d'interface au stockage volatile 110 tel que la mémoire à accès aléatoire RAM qui contient des instructions de programme et des données temporaires relatives au fonctionnement du système d'inventaire de compagnies aériennes 102. [0027] Dans une configuration conventionnelle, le dispositif de stockage 106 maintient un programme connu et un contenu de données pertinent avec le 20 fonctionnement normal du système d'inventaire de compagnies aériennes 102. Par exemple, le dispositif de stockage 106 peut contenir des programmes de système d'exploitation et des données ainsi que d'autres logiciels d'application exécutables nécessaires pour les fonctions voulues du système d'inventaire de compagnies aériennes 102. Le dispositif de stockage 106 contient aussi des tructions de programme qui, lorsqu'elles sont exécutées par le processeur 104, amènent le système d'inventaire de compagnies aériennes 102 à effectuer des opérations relatives à un mode de réalisation de la présente invention, lesquelles sont décrites plus en détail ci-dessous, en référence aux s 4 à 14 en particulier. Dans le fonctionnement, les instructions et les 15 données stockées sur le dispositif de stockage 106 sont transférées à la mémoire volatile 110 pour une exécution à la demande. [0028] Le processeur 104 est aussi associé ctionnellement à une interface de communications 112 d'une manière conventionnelle L'interface de communications 112 facilite l'accès à un réseau étendu de communications de données, tel que l'Internet 116. [0029] Dans la pratique, le stockage volatile 110 contient un corps d'instructions de programme correspondant 114 transféré à partir du dispositif de stockage 106 et qui est configuré pour effectuer le traitement et d'autres 10 opérations afin de mettre en oeuvre les caractéristiques de la présente invention. Les instructions de programme 114 comprennent une contribution technique à l'état de l'art, développée et configurée spécifiquement pour mettre en oeuvre un mode de réalisation de l'invention, au-delà de l'activité conventionnelle, de routine, bien comprise de l'état de l'art de systèmes d'apprentissage automatique 15 et d'optimisation des recettes, comme décrit plus amplement ci-dessous, notamment en référence aux Figures 4 à 14. [0030] Concernant l'aperçu précédent du système d'inventaire de compagnies aériennes 102 et d'autres systèmes de traitement et dispositifs décrits dans cette spécification, les ternies tels que « processeurs », 20 « ordinateur » et ainsi de suite, sauf si le contexte exige autrement, doivent être interprétés comme faisant référence à une gamme d'implémentations possibles des dispositifs, appareils et systèmes comprenant une combinaison de logiciels et de matériel. Cela inclut des dispositifs à processeur unique et à processeurs multiples et un appareil, incluant les dispositifs portables, les ordinateurs de 25 bureau et divers types de systèmes de serveur, incluant du matériel coliaboratif et des plateformes logicielles qui peuvent cohabiter ou être distribuées. Les processeurs physiques peuvent inclure des unités centrales de traitement (CPUs) à usage général, des processeurs de signaux numériques, des unités de traitement graphique (GPUs) et/ou d'autres dispositifs matériels appropriés pour 16 une exécution efficace des programmes et des algorithmes nécessaires. Comme le notent les personnes de métier, les GPU particuliers peuvent être employés pour la mise en oeuvre à haute performance des réseaux neuronaux profonds comprenant modes de réalisation de l'invention, sous le contrôle d'une ou de plusieurs CPU à usage général. [0031] Les si.stèmes informatiques peuvent inclure des architectures conventionnelles d'ordinateur personnel ou d'autres plateformes matérielles à usage générai. Les logiciels peuvent inclure des logiciels de sources libres et/ou des logiciels de systèmes d'exploitation vendus sur le marché en combinaison 10 avec diverses applications et programmes de services, Autrement, les plateformes de traitement ou de calcul peuvent comprendre du matériel et/ou des architectures de logiciel adaptés sur mesure. Pour une extensibilité améliorée, les systèmes de traitement et de calcul peuvent comprendre des plateformes d'informatique en nuage (cloud) permettant aux ressources matérielles physiques 15 d'être allouées de façon dynamique en réponse aux demandes de services. Alors que toutes ces variations sont comprises dans la portée de la présente invention, pour faciliter l'explication et la compréhension, les modes de réalisation exemplaires sont décrits dans les présentes à titre illustratif en référence aux plateformes informatiques à usage général à processeur unique, des plateformes 20 de système d'exploitation couramment disponibles et/ou des produits de consommateurs largement disponibles, tels que les ordinateurs de bureau (PCs), les ordinateurs compacts ou ordinateurs portables (PCs), les srnartphones, les tablettes informatiques et ainsi de suite. [0032] En particulier, les termes « unité de traitement » et « module » sont 25 utilisés dans cette spécification en référence à toute combinaison appropriée de matériel et de logiciels configurés pour effectuer une tâche particulière définie telle que l'accès et le traitement des données en ligne ou hors connexion, l'exécution des étapes d'entraînement d'un modèle d'apprentissage de renforcement et/ou de réseaux neuronaux profonds ou autres dispositifs 30 d'approximation de fonction dans un tel modèle, ou l'exécution des étapes de 17 tarification et d'optimisation des recettes. Une telle unité ou module de traitement peut comprendre un code exécutable qui s'exécute à un emplacement unique sur un dispositif de traitement unique ou qui peut comprendre des modules collaboratifs de code exécutable qui s'exécutent â de multiples emplacements 5 et/ou sur de multiples dispositifs de traitement. Par exemple, dans certains modes de réalisation de l'invention, les algorithmes d'apprentissage de renforcement et d'optimisation des recettes peuvent être réalisés entièrement par un code qui s'exécute sur un système unique, tel que le système d'inventaire de compagnies aériennes 102 alors que dans d'autres modes de réalisation le 10 traitement correspondant peut être effectué d'une manière distribuée sur une pluralité de systèmes. [0033} Les composants logiciels, p. ex. les instructions de programme 114, mettant en oeuvre les caractéristiques de l'invention peuvent être développés en utilisant tout langage de programmation approprié, environnement de 15 développement ou combinaison de langages et d'environnements de développement qui seront familiers aux hommes de métier spécialisés dans logicielle. Par exemple, le logiciel approprié peut être développé en utilisant le langage de programmation C. le langage de programmation Java, le langage de programmation C++, le langage de programmation Go, le langage de 20 programmation Python, le langage de programmation R etiou d'autres langages adaptés à l'implémentation des algorithmes d'apprentissage automatique. Le développement des modules logiciels mettant en oeuvre l'invention peut être supportée par l'utilisation de bibliothèques de codes d'apprentissage machine, telles que les bibliothèques TensorFlow, Torch et Keras. Les hommes de métier 25 noteront cependant, que des modes de réalisation de la mention impliquent l'implémentation de structures et de code logiciels qui ne sont pas des systèmes d'apprentissage automatiques bien compris, de routine ou conventionnels dans l'état de l'art, et que tandis que les bibliothèques préexistantes peuvent aider à l'implémentation, elles exigent une configuration spécifique et une augmentation 30 étendue (c.-à-d. le développement de code supplémentaire) afin de réaliser divers avantages de l'invention et de mettre en oeuvre les structures, le 18 traitement, les calculs et les algorithmes spécifiques décrits ci-dessous, notamment en référence aux Figures 4 à 14. [0034] Les précédents exemples de langages, d'environnements et de bibliothèques de code ne se veulent pas restrictifs et on notera que tout langage, 5 bibliothèque ou système de développement approprié peut être employé selon les exigences des systèmes. Les descriptions, diagrammes bloc, organigrammes, équations et autres qui sont présentés dans cette spécification sont fournis à titre d'exemple pour permettre aux hommes de métier spécialisés dans l'ingénierie logicielle et l'apprentissage automatique de comprendre et d'apprécier les 10 caractéristiques, la nature et la portée de l'invention, et pour mettre un ou plusieurs modes de réalisation de l'invention en pratique par l'implémentation de code logiciel adapté en utilisant tout langage, cadre, bibliothèque et système de développement approprié, conformément à cette divulgation sans avoir à y apporter une ingéniosité inventive additionnelle. 15 [0035] Le code de programme mis en oeuvre dans une/un quelconque des applications/modules décrits dans les présentes peut être distribué individuellement ou collectivement comme un produit-programme, sous une variété de formes. En particulier, le code de programme peut être distribué en utilisant un support de stockage lisible par ordinateur ayant des instructions de 20 programme lisibles par ordinateur pour amener un processeur à réaliser des aspects des modes de réalisation de l'invention. [0036] Les supports de stockage lisibles par ordinateur peuvent inclure des médias tangibles, volatiles et non volatiles, amovibles et non amovibles, implémentés dans toute méthode ou technologie de stockage d'informations, 25 telles que des instructions de programme lisibles par ordinateur, des structures de donnée, des modules de programme, ou autres données. Les supports de stockage lisibles par ordinateur peuvent aussi inclure des mémoires: une mémoire à accès aléatoire (RAM), une mémoire à lecture seule (ROM), une mémoire à lecture seule programmable et effaçable (EPROM), une mémoire à 19 lecture seule programmable et effaçable électriquement (EEPROtv ), une mémoire flash, ou autre technologie de support solide de mémoire, un disque compact portable doté d'une mémoire à lecture seule (CD-ROM), ou autre stockage optique, une bande d'enregistrement magnétique, ou tout autre support 5 pouvant être utilisé pour stocker l'information désirée et apte à être iue par un ordinateur. Tandis que le support de stockage lisible par ordinateur ne peut comprendre qu'un signal transitoire en soi (par ex., des ondes radio ou d'autres ondes de propagation électromagnétiques, les ondes électromagnétiques se propageant via un support de transmission tel qu'un guide d'ondes ou des signaux électriques transmis par un câble), les instructions de programme lisible par ordinateur peuvent être téléchargées via de tels signaux transitoires à un ordinateur, un autre type d'appareils de traitement de données programmable, ou un autre dispositif allant d'un support de stockage lisible par ordinateur ou sur un dispositif de stockage externe ou informatique externe via un réseau. 15 [0037] Les instructions de programme lisibles par ordinateur, stockées dans un support lisible par ordinateur, peuvent être utilisées pour instruire un ordinateur, d'autres types d'appareils de traitement de données programmables ou d'autres dispositifs pour fonctionner d'une façon particulière, de sorte que les instructions stockées sur un support lisible par ordinateur produisent un article de 20 fabrication comprenant les instructions qui implémentent les fonctions, les actions et/ou les opérations spécifiées dans les organigrammes, diagrammes de séquence, et/ou diagrammes blocs. Les instructions de programme informatique peuvent être fournies par un ou plusieurs processeurs sur un ordinateur à usage général, un ordinateur à usage spécial, ou un autre appareil programmable de 25 traitement de données pour produire une machine, de sorte que les instructions qui s'exécutent par l'intermédiaire d'un ou de plusieurs processeurs provoquent une série de calculs devant être effectués pour implémenter les fonctions, actions etlopérations spécifiées dans les organigrammes, diagrammes séquentiels etiou diagrammes blocs. 20 [0033] Pour en revenir à la discussion de la Figure 1, le système de réservation de compagnies aériennes 100 inclut un système de distribution globale (GDS) 118, qui inclut un système de réservation (non illustré) et qui est capable d'accéder à une base de données 120 de tarifs et de programme de 5 diverses compagnies aériennes pour lesquelles il est possible de faire des réservations. Comme illustré dans un système d'inventaire 122 d'une compagnie aérienne alternative. Alors qu'un seul système d'inventaire de compagnies aériennes alternatif 122 est représenté à la Figure 1, par voie d'illustration, on notera que le secteur des compagnies aériennes est très compétitif et en 10 pratique, le GDS 118 est capable d'accéder aux tarifs et aux programmes, d'effectuer des réservations, pour un grand nombre de compagnies aériennes, chacune d'entre elles ayant son propre système d'inventaire. Les consommateurs, qui peuvent être des particuliers, des agents de réservation ou toute autre entreprise ou entité personnelle, accède aux services de réservation 15 du GDS 118 via le réseau 116, par ex., via les terminaux des consommateurs 124 exécutant le logiciel de réservation correspondant. [0039] Conformément au cas d'usage commun, une demande entrante 126 d'un terminal consommateur 124 est reçue par le CDS 118. La demande entrante 126 inclut toutes les informations attendues pour un passager souhaitant 20 voyager vers une destination. Par exemple, les informations peuvent inclure le point de départ, le point d'arriver, la date de voyage, le nombre de passagers et ainsi de suite. Le GDS 118 accède à la base de données 120 de tarifs et de programmes pour identifier une ou plusieurs itinéraires qui peuvent satisfaire les exigences du consommateur. Le GDS 118 peut alors générer une plusieurs 25 demandes de réservation concernant un itinéraire sélectionné. Par exemple, comme représenté à la Figure 1, une demande de réservation 128 est transmise au système d'inventaire 102 qui traite la demande et génère une réponse 130, indiquant si la réservation est acceptée ou rejetée. La transmission d'une autre demande de réservation 132 au système d'inventaire de compagnies aériennes 30 alternatif 122 et une réponse d'acceptation/de rejet correspondante 134 sont également illustrés. Un message de confirmation de réservation 136 peut ensuite être transmis par le GDS 118 au terminal du consommateur 124. 21 [0040] Comme c'est bien connu dans le secteur des compagnies aériennes, en raison de l'environnement compétitif, la plupart des compagnies aériennes offrent différentes classes de voyages (par ex., économique, économique Premium, affaire et première classe) dans chaque catégorie de voyage il peut y 5 avoir un nombre de classes de tarifs ayant une tarification et des conditions différentes. Une première fonction des systèmes d'optimisation et de gestion des recettes est par conséquent le contrôle de la disponibilité et la tarification de ces différentes classes de tarifs sur une période entre l'ouverture des réservations et le départ d'un vol, dans un effort pour maximiser les recettes générées pour une 10 compagnie aérienne par le vol. Le RMS conventionnel le plus sophistiqué emploie une approche de programmation dynamique (DR) pour résoudre un modèle de processus de génération des recettes qui tient compte de la disponibilité des places, de l'heure de départ, de la valeur marginale et du coût marginal de chaque place, des modèles de comportement de consommateurs 15 (par ex., sensibilité aux prix et volonté de payer), et ainsi de suite, afin de générer, à un moment particulier, une politique comprenant un prix spécifique pour chacune d'un ensemble de classes de tarifs disponibles. Dans une implémentation commune, chaque prix peut être sélectionné à partir d'un ensemble correspondant de points de tarif, qui peut inclure « fermé », c.-à-d, une 20 indication selon laquelle la classe de tarifs n'est plus disponible à la vente. Typiquement, à mesure que la demande augmente et/ou l'approvisionnement diminue (par ex., à mesure que l'heure du départ approche) la politique générée par le RMS à partir de sa solution sur les changements de modèle, de sorte que les points de tarifs sélectionnés pour chaque classe de tarifs augmentent, et que 25 les classes les moins chères (et plus restreintes) sont « fermées ». [0041] Des modes de réalisation de la présente invention remplacent l'approche de programmation dynamique basée sur le modèle du RMS conventionnel avec une nouvelle approche basée sur l'apprentissage de renforcement (Ri.). 22 [0042] Un organigramme fonctionnel d'un système d'inventaire exemplaire 200 est illustré à la Figure 2. Le système d'inventaire 200 inclut un module de gestion des recettes 202 qui est responsable de la génération des politiques tarifaires, c.-à-d. de la tarification pour chacune d'un ensemble de 5 classes de tarifs disponible sur chaque vol qui peut être réservé â un moment donné. En général, le module de gestion des recettes 202 peut implémenter un RMS conventionnel basé sur la DP (DP-RMS) ou un autre algorithme pour déterminer les politiques. Dans des modes de réalisation de la présente invention, le module de gestion des recettes met en oeuvre un système de 10 gestion des recettes basé sur le RL (RL-RMS), comme décrit en détail ci-dessous en référence aux Figures 4 à 14. [0043] En fonctionnement, le module de gestion des recettes 202 communique avec un module de gestion d'inventaire 204 via un canal de communication 206. Le module de gestion des recettes 202 peut par conséquent 15 recevoir des informations en lien avec l'inventaire disponible (c.-à-d. les sièges invendus restant sur des vols ouverts) à partir du module de gestion d'inventaire 204, et de transmettre les mises à jour de politique tarifaire au module de gestion d'inventaire 204. Le module de gestion d'inventaire 204 et le module de gestion des recettes peuvent accéder aux données de tarif 208, en 20 incluant des informations qui définissent les points et conditions de prix fixés par la compagnie aérienne pour chaque classe de tarifs. Le module de gestion des recettes 202 est également configure pour accéder aux données historiques 210 des réservations de vols, qui mettent en oeuvre les informations sur le comportement du consommateur, la sensibilité aux prix, l'historique de la 25 demande, etc. [0044] Le module de gestion d'inventaire 204 reçoit des demandes 214 du GDS 118, par ex. pour les réservations, les changements et les annulations. Il répond 212 â ces demandes en les acceptant ou en les rejetant, sur la base des politiques actuelles fixées par le module de gestion des recettes 202 et 23 correspondant aux informations tarifaires stockées dans la base de données de tarifs 208. [0045] Afin de comparer les performances des différentes approches et algorithmes de gestion des recettes, et pour fournir un environnement 5 d'entraînement au RL-RMS, il est avantageux d'implémenter un simulateur de hé de voyage aérien. Un diagramme bloc de ce type de simulateur 300 est illustré à la Figure 3. Le simulateur 300 inclut un module de génération de demandes 302 qui est configure pour générer des demandes de consommateurs simulées. Les demandes simulées peuvent être générées pour être 10 statistiquement similaires à la demande observée sur une période historique pertinente, peuvent être synthétisées conformément à un autre modèle de demande, et/ou peuvent se baser sur un autre modèle de demande, ou combinaison de modèles. Les demandes simulées sont ajoutées à une file d'attente d'événements 304 qui est desservie par un GDS 118. Le GDS 118 peut 15 effectuer les demandes de réservation correspondantes au système d'inventaire 200 et/ou à tout nombre de systèmes d'inventaire de compagnies urrents simulés 122. Chaque système d'inventaire de compagnies aériennes concurrent 122 peut se baser sur un modèle fonctionnel similaire au système d'inventaire 200 ruais peut mettre en oeuvre une approche différente de 20 gestion des recettes, par ex., le DP-RMS, dans son équivalent du module de gestion de recettes 202. [0046] Un module de simulation de choix 306 reçoit les solutions de voyage disponibles fournies par les systèmes d'inventaire de compagnies aériennes 200, 122 provenant du GDS 118 et génère des choix de consommateurs simulés. Les 25 choix consommateurs peuvent se baser sur des observations historiques de comportement de réservation de consommateurs, la sensibilité aux prix, et ainsi de suite, et peuvent se baser sur d'autres modèles de comportement du consommateur. 24 [0047] La perspective du système d'inventaire 200, module de génération de demandes 302, la file d'attente d'événements 304, le GUS 118, le simulateur de choix 306 et les systèmes d'inventaire de compagnies aériennes concurrents 122, comprennent collectivement un environnement d'exploitation 5 simulé (c.-à-d. le marché du voyage aérien) dans lequel le système d'inventaire 200 est en compétition pour les réservations, cherche à optimiser sa génération de recettes. Aux fins de la présente invention, cet environnement stimulé est utilisé pour entraîner un RL-RMS, comme décrit plus en détail ci-dessous en référence aux Figures 4 à 7, et pour comparer les performances du 10 RL-RMS aux approches de gestion des recettes alternatives, comme décrit plus en détail ci-dessous en référence aux Figures 10 à 14. On notera cependant qu'un RL-RMS mettant en oeuvre la présente invention fonctionnera de la même manière lorsqu'il interagit avec un marché de voyages aériens réel et qu'il n'est pas limité aux interactions avec un environnement simulé. 15 [0048] La Figure 4 est un diagramme bloc d'un RL-RMS 400 mettant en oeuvre l'invention qui emploie une approche d'apprentissage O. Le RL-RMS 400 on prend un agent 402 qui est un module logiciel configuré pour interagir avec l'environnement externe 404. L'environnement 404 peut être un marché de voyages aériens réels ou un marché de voyages aériens simulés, comme décrit 20 ci-dessus en référence à la Figure 2. Conformément à un modèle bien connu de systèmes RL, l'agent 402 entreprend des actions qui influencent l'environnement 404 et observe des changements d'état de l'environnement, et reçoit des récompenses, en réponse à ces actions. En particulier, les actions 406 entreprises par l'agent RL-RMS 402 comprennent les politiques tarifaires 25 générées. L'état de l'environnement 408, pour tout vol donné, comprend la disponibilité (c.-à-d. le nombre de places invendues), et le nombre de jours restant jusqu'au départ. La récompense 410 comprend les recettes générées à partir des réservations de sièges. L'objectif RL de l'agent 402 par conséquent de déterminer les actions 406 (c.-à-d. les politiques) pour chaque état observé de 30 l'environnement qui maximise les récompenses totales 410 (par ex., les recettes par vol). 25 [0049] Le RL-RMS d'apprentissage Q 202 conserve un tableau action - valeur 412, qui comprend des estimations de valeur gs, al pour chaque état s et chaque action disponible (politique tarifaire) a. Afin de déterminer l'action à entreprendre dans l'état actuel s, l'agent 402 est configure pour demander 414 le 5 tableau action - valeur 412 pour chaque action disponible a, pour récupérer les estimations de valeur correspondantes Q[s, a], et pour sélectionner une action basée sur une politique d'action actuelle n. En fonctionnement en direct sur un marché réel, la politique d'action 7r peut être de sélectionner l'action a qui maximise (.7 dans l'état actuel s (c.-à-d. une politique d'action « avide »). 10 Cependant, au moment de l'entraînement du RL-RMS, par ex. hors ligne en utilisant une demande simulée, ou en ligne en utilisant des observations récentes de comportements de consommateurs, une politique d'action alternative peut être privilégiée, de sorte qu'un politique d'action « avide en », qui équilibre exploitation des données action-valeur actuelles avec l'exploration des actions 15 présentement considérées comme étant de faible valeur mais qui peuvent finalement conduire à des recettes plus élevées via des états inexplorés ou en raison de changements sur le marché. [0050] Après avoir entrepris une action a, agent 402 reçoit un nouvel état s' et une récompense R de l'environnement 404 et l'observation en résultant (s', a. 20 R) est passée 418 à un module logiciel de mise à jour Q 420. Le module de mise à jour Q 420 est configuré pour mettre à jour le tableau action - valeur 412 en récupérant 422 une valeur estimée actuelle Qk de la paire état-action (s, a) et en stockant 424 une estimation révisée Ctkt, basée sur le nouvel état s' et la récompense R actuellement observée en réponse à l'action a. Les détails des 25 étapes de mise à jour d'apprentissage Q appropriés sont bien connus des hommes de métier de l'apprentissage de renforcement, et sont par conséquent omis pour éviter des explications supplémentaires non nécessaires. [0051] La Figure 5 présente un tableau 500 des performances du RL-RMS d'apprentissage Q 400 interagissant avec un environnement simulé 404. L'axe 30 horizontal 502 représente le nombre d'années de données du marché simulées 26 (en milliers), alors que l'axe vertical 504 représente le pourcentage de recettes cibles 506 atteintes par le RL-RMS 400. La courbe de recette 508 illustre que le RL-RMS est en effet capable d'apprendre pour optimiser les revenus vers l'objectif 506, cependant son taux d'apprentissage est extrêmement long et ii atteint approximativement 96 % des recettes cibles uniquement après une expérience de 160 000 années de données simulées. [0052] La Figure 6A est un diagramme bloc d'un RL-RMS 600 alternatif mettant en oeuvre l'invention qui emploie une approche d'apprentissage Q profond (DQL). Les interactions de l'agent 402 avec l'environnement 404 et le 10 processus de prise de décision de l'agent 402 sont sensiblement les mêmes que dans le RL-RMS d'apprentissage Q sous forme de tableau, comme indiqué par l'utilisation des mêmes chiffres de référence et par conséquent, elles ne doivent pas être décrites à nouveau. Dans le DOL RL-RMS, le tableau action - valeur est remplacé par un dispositif d'approximation de fonction, notamment avec un 15 réseau neuronal profond (DNN) 602. Dans un mode de réalisation exemplaire, pour un avion ayant environ 200 sièges, le DNN 602 comprend quatre couches cachées, chaque couche cachée comprenant 100 noeuds, entièrement connectés. Par conséquent, l'architecture exemplaire peut être définie comme (k, 100, 100, 100, 100, n), si k est la longueur de l'état (c,-à-d. k 2 pour un état 20 consistant en la disponibilité et en jours avant le départ) et n est le nombre d'actions possibles. Dans un mode de réalisation alternatif, le DNN 602 peut comprendre une architecture de réseau d'abattage, dans laquelle le réseau de valeur est (k, 100, 100, 100, 100, 1), et le réseau d'avantage est (k, 100, 100, 100, 100, n). Dans des simulations, les inventeurs ont trouvé que l'utilisation d'une 25 architecture réseau d'abattage peut fournir un léger avantage sur un réseau action valeur unique. Cependant, on n'a pas trouvé que l'amélioration était essentielle pour les performances générales de l'invention. [0053] Dans ie DOL RL-RMS, les observations de l'environnement sont sauvegardées dans une mémoire de relecture 604. Un module logiciel DOL est 30 configuré pour échantillonner les transitions (s, a) ---> (s', R) â partir de la mémoire 27 de relecture 604 pour une utilisation pendant l'entraînement du DNN 602. Des modes de réalisation de l'invention emploient notamment une forme spécifique de relecture d'expérience classée par ordre de priorité dont on a trouvé qu'elle atteint de bons résultats tout en utilisant des nombres relativement petits de 5 transitions observées. Une approche commune dans le DOL est d'échantillonner les transitions à partir d'une mémoire de relecture complètement au hasard, pour éviter les corrélations qui peuvent empêcher la convergence de la pondération du DNN. Une approche de relecture par ordre de priorité alternative et connue échantillonne les transitions avec une probabilité qui est basée sur une estimation 10 d'erreur actuelle de la fonction de valeur pour chaque état, de sorte que les états ayant une plus grande erreur (et par conséquent si les plus grandes améliorations de l'estimation peuvent être attendues) sont plus susceptibles d'être échantillonnés. [0054] L'approche de relecture par ordre de priorité employée dans des 15 modes de réalisation de la présente invention est différente, et se base sur l'observation selon laquelle une solution intégrale du problème d'optimisation des recettes (par ex., en utilisant le DP) commence par l'état terminal, c.-à-d. au départ d'un vol, lorsque les recettes finales actuelles sont connues, et repart en via une « pyramide » extensible de champs possibles à l'état terminal pour 20 déterminer la fonction de valeur correspondante. Dans chaque état d'entraînement, des niveaux de transition sont échantillonnés à partir de la mémoire de relecture conformément à une distribution statistique qui donne initialement des priorités aux transitions proches de l'état terminal. Sur de multiples étapes d'entraînement au cours d'une période d'entraînement, les 25 paramètres de distribution sont ajustés, de sorte que la priorité change dans le temps vers des transitions qui sont plus loin de l'état terminal. La distribution statistique est néanmoins choisie, de sorte que toute transition a encore une chance d'être sélectionnée dans tout lot, de sorte que le DNN continue à apprendre la fonction action valeur sur l'ensemble de l'espace d'état d'intérêts et 30 n'« oublie » en effet pas ce qu'il a appris sur les états proches du terminal, au fur et à mesure qu'il acquiert davantage de connaissances sur les états précédents. 28 [0055] Afin de ettre à jour le DNN 602, le module DOL 606 récupère 610 les paramètres de pondération 0 du DNN 602, effectue une ou plusieurs étapes d'entraînement, par ex., en utilisant un algorithme de rétropropagation conventionnel, à l'aide des mini-lots échantillonnés et envoie 612 ensuite une 5 mise à jour Ill au DNN 602. Les détails du procédé d'échantillonnage et de mise à jour, conformément à une approche de réponse par ordre de priorité mettant en oeuvre l'invention est illustré dans l'organigramme 620 présenté à la Figure 6B. À 'étape 622, un index temporel r est initialisé pour représenter un intervalle de temps immédiatement avant le départ. Dans un mode de réalisation exemplaire, 10 la durée entre l'ouverture des réservations et le départ est divisée en 20 points de collecte de données (DCP), de sorte que l'heure de départ T correspond à t = 2 1, et par conséquent la valeur initiale de l'index temporel r dans le procédé 620 est t = 20. À l'étape 624, les paramètres de l'algorithme de mise à jour du DNN sont initialisés. Dans un mode de réalisation exemplaire, l'algorithme de mise à jour 15 Adam (c.-à-d. une forme améliorée de descente de gradient stochastique) est employé. À l'étape 626, un compteur n est initialisé. Il contrôle le nombre d'itérations (et de mini-lots) utilisés dans chaque mise à jour du DNN. Dans un mode de réalisation exemplaire, la valeur du compteur est déterminée en utilisant une valeur de base no, et une valeur proportionnelle au nombre restant d'intervalles de temps jusqu'au départ, donnée par ne- r). Concrètement; no peut-être fixé à 50 et th à 20. Cependant en simulation les inventeurs ont trouvé que ces valeurs n'étaient pas particulièrement essentielles. Le principe de base est que comme l'algorithme revient en arrière dans le temps (par ex.; vers l'ouverture des réservations), plus d'itérations sont utilisées pendant l'entraînement du DNN. [0056j À l'étape 628 a, un reins-lot échantillon est sélectionné de manière aléatoire à partir de ces échantillons dans l'ensemble de relecture 604 correspondant à la période définie par le présent index t et l'heure de départ T. Ensuite, à l'étape 630, une étape de descente de gradient est entreprise par le 30 dispositif de mise à jour en utilisant le mini-lot sélectionné. Ce processus est répété 632 à l'étape temporelle ! jusqu'à ce que toutes les itérations n ait été 29 achevées. L'index temporel t est ensuite décrémenté 634 et s'il n'a pas atteint une commande nulle, il revient à l'étape 624. [0057] Dans un mode de réalisation exemplaire, la taille de l'ensemble de relecture s'élevait à 6 000 échantillons, correspondant aux données collectées à partir de 300 vols sur 20 intervalles de temps par vol. Cependant, on a observé que ce nombre n'est pas essentiel et une gamme de valeurs peut être utilisée. Par ailleurs, la taille du mini-lot &élevait à 600, ce qui a été déterminé sur la base des paramètres de simulation particuliers utilisés, [0058] La Figure 7 représente un tableau 700 des performances du DQL RL- 10 RMS 600 interagissant avec un environnement simulé 404. L'axe horizontal 702 représente le nombre d'années de données du marché simulées, tandis que l'axe vertical 704 représente le pourcentage de recettes cibles 706 atteintes par le RLRMS 600. La courbe de recettes 700 illustre la capacité du DOL RI...-RMS 600 â apprendre pour optimiser les recettes vers la cible 706 bien plus rapidement que 15 le RL-RMS 400 d'apprentissage sous forme de tableau, atteignant environ 99 % des recettes cibles avec seulement cinq années de données simulées et proche de 100 % avec environ 15 années de données simulées. [0059] Un procédé alternatif d'initialisation d'un RL-RMS 400, 600 est illustré par l'organigramme 800 représenté à la Figure 8A. Le procédé 800 utilise un 20 RMS existant, par ex, un DP-RMS, comme source pour le « transfert de connaissances » vers un RL-RMS. L'objectif de ce procédé est que, dans un état donné s, le RL-RMS devrait initialement générer la même politique tarifaire que celle qui serait produite en utilisant le RMS source à partir duquel le RL-RMS est initialisé. Le principe générai contenu par le processus 800 consiste par 25 conséquent à obtenir une estimation de fonction action valeur équivalente correspondant au RMS source, et ensuite à utiliser cette fonction pour initialiser le RL-RMS, par ex., en fixant les valeurs correspondantes d'une représentation action - valeur sous forme de tableau dans un mode de réalisation 30 d'apprentissage Q, ou par l'entraînement supervisé du DNN dans un mode de réalisation DOL, [0060] Dans le cas d'un DP-RMS source, cependant, H existe deux difficultés â surmonter en exécutant une transformation vers une fonction action - valeur 5 équivalente. Premièrement, un DP-RMS n'emploie aucune fonction action -, valeur. En tant que processus d'optimisation basé sur un modèle, la DP produit une fonction de valeur, Ifia4sitms), basé sur l'hypothèse que des actions optimales sont toujours entreprises. Le prix de tarif correspondant peut être obtenu à partir de cette fonction de valeur, et est utilisé pour calculer la politique 10 tarifaire au moment où l'optimisation est effectuée. Il est par conséquent nécessaire de modifier la fonction de valeur obtenue à partir du DP-RMS pour inclure la dimension d'action. Deuxièmement, la DP emploie une étape temporelle dans sa procédure d'optimisation qui consiste, en pratique, à fixer une toute petite valeur de sorte qu'il y a au maximum une demande de réservation 15 attendue par étape temporelle. Tandis que de manière similaire, de petites étapes temporelles pourraient être employées dans un système RL-RMS, en pratique cela n'est pas souhaitable. Pour chaque étape temporelle dans le RL, il doit y avoir une action et une certaine rétroaction à partir de l'environnement. L'utilisation de petites étapes temporelles requiert par conséquent beaucoup plus 20 de données d'entraînement et, en pratique, la taille de l'étape temporelle. RI_ devrait être fixée en tenant compte des données disponibles et de la capacité de la cabine. En pratique, c'est acceptable parce que le marché et la politique tarifaire ne changent pas rapidement. Cependant ces résultats sont incohérents avec le nombre d'étapes temporelles dans la formule DP et le système RL. De 25 plus, un RL-RMS peut être implémenté pour tenir compte des informations d'état supplémentaires qui ne sont pas disponibles pour un DP-RMS, tel qu'un comportement des concurrents en temps réel (par ex., le prix le plus bas proposé par les concurrents). Dans de tels modes de réalisation, ces informations d'état supplémentaires doivent également être incorporées dans la fonction action - 30 valeur utilisée pour initialiser le RL-RMS. 31 [0061] Par conséquent, a l'étape 802 du processus 800, la formule DP est utilisée pour calculer la fonction de valeur itRustsRms), et à l'étape 804, elle est ensuite transformée pour réduire le nombre d'étapes temporelles et inclure un état supplémentaire et des dimensions d'action, résultant en une fonction action- transformée ORL(s.ims, a). Cette fonction peut être échantillonnée 806 pour obtenir des valeurs pour une représentation action valeur sous forme de tableau dans un RL-RMS d'apprentissage Q, et/ou pour obtenir des données pour l'entraînement supervisé du DNN dans un DOL RL-RMS pour approcher la fonction action - valeur transformée. Ainsi, à l'étape 808 !es données ntillonnées sont utilisées pour réinitialiser le RL-RMS de manière appropriée. [0062] La Figure 88 est un organigramme 2 illustrant plus en détail un procédé de transfert des connaissances mettant en oeuvre l'invention. Le procédé 820 emploie un ensemble de « points de contrôle », ((ph cp71, pour représenter les intervalles de temps plus grands utilisés dans le système RL- 15 RMS. La durée entre chacun de ces points de contrôle est divisée en une pluralité de micro-étapes in correspondant aux intervalles de temps plus courts utilisés dans le système DP-RMS. Dans la discussion suivante, l'index temps-étape RL est dénoté par r, qui varie entre 1 et T. tandis que l'index d'étapes de micro-temps est dénoté irt, qui varie entre 0 et MT, s'ils sont définis comme étant 20 des étapes de micro-temps Al du DP-RMS dans chaque temps-étape du RLRMS. En pratique, le nombre d'étapes temporelles du RL peut être, par exemple, de 20 environ. Pour le DP-RMS, les étapes de micro-temps peuvent être définies de sorte qu'il existe par exemple, une probabilité de 20 % selon laquelle une demande de réservation est reçue avec chaque intervalle, de sorte qu'il peut y 25 avoir des centaines, même des milliers d'étapes de micro-temps dans la fenêtre de réservation ouverte, [0063] L'algorithme général, conformément à l'organigramme 820 procède comme suit. Premièrement, à l'étape 822, l'ensemble de points de contrôle est établi. Un index t est initialisé à l'étape 824, correspondant au début du deuxième 30 intervalle de temps RL-RMS, c.-à-d. cp2. Une paire de boucles imbriquées est 32 ensuite exécutée. Dans la boucle externe, à l'étape 826, une valeur équivalente de la fonction action - valeur RL Q,u(s, a) est calculée correspondant à un « état virtuel » défini en une fois une micro-étape préalable au point de contrôle actuel, et la disponibilité x, i.e. s = (cpt - 1,x). Le comportement supposé du RL-RMS dans cet état virtuel se base sur la prise en compte du fait que le RL effectue une action à chaque point de contrôle et conserve la même action pour toutes les étapes de micro-temps entre deux points de contrôle consécutifs, À l'étape 828, un index de micro-étapes mr est initialisé à la micro-étape immédiatement ente, c.-à-d, (Ti - 2. La boucle interne calcule ensuite les valeurs 10 correspondantes de la fonction action - valeur RL QRT(s, a) à l'étape 830 en travaillant en arrière à partir de la valeur calculée à l'étape 826, Cette boucle continue jusqu'à ce que le précédent point de contrôle soit atteint, caà-d, lorsque rar atteint zéro 832. La boude externe continue alors jusqu'à ce que tous les intervalles de temps RL aient été calculés, c.-à-d. lorsque r= T 834. 15 (0064] Une description mathématique exemplaire des calculs dans le processus 820 sera à présent décrite. Dans le DP-RMS, la fonction de valeur DP peut être exprimée comme suit : Vicimsfrat,x) Maxall,' * Prnt(a) * (1?,' ,(a) + VRms Ont + 1, - (1 - (int * Pmt(a)) VRms Ont + xn où 20 i,,, est la probabilité d'avoir une demande à l'étape nit; P','(a.) est la probabilité de recevoir une réservation d'une demande à l'étape mt , à condition que l'action a; R't (a) constitue des recettes moyennes à partir d'une réservation à l'étape rnt, à condition que l'action o. 25 [0065] En pratique, i' et les étapes de micro-temps correspondantes sont définies en utilisant le volume prévu de demande et le modèle d'arrivée (et est traité comme étant indépendant du temps), P,,,t(a) est calculé sur la base d'une distribution de volonté de payer à la demande du consommateur (qui est dépendante du temps), Rmt(a) est calculé sur la base d'un modèle de choix du consommateur (avec des paramètres dépendant du temps), et x est fournie par le module de réservation de compagnie aérienne qui est supposé inchangé entre DP-RMS et RL-RMS. [0066] Par ailleurs : (cpT = O pour tous les x, Q],,,(cpT, x, a) 0 pour tous les x, a VRamt, 0) = 0 pour tous les mt Qgt(rnt,0, a) 0 pour tous les mt, [0067] Ensuite, pour tous les mt ept - 1 (c.-à-d. correspondant à 10 tape 826) la valeur équivalente de la -.`onction action - valeur RL peut être calculée comme suit Qfil, (nt, r, a) = /rit * Pria tri a (rat 1, x - 1)) - 1 Pm, (o.)) + 1, x) Si VRL(mt, x) = 11,1 ax'Q Ram x, a) 15 [0068] Par ailleurs, pour tous les cpt..,1 5 nit REVENDICATIONS: 1. Un procédé d'apprentissage de renforcement pour un agent de gestion des ressources (402) dans un système (200) pour gérer un inventaire des ressources périssables ayant un horizon de vente, tout en cherchant à optimiser les recettes générées à partir de celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante des ressources périssables et une période restante de l'horizon de vente, le procédé comprenant : la génération d'une pluralité d'actions (406), chaque action comprenant la publication de données qui définissent un programme de tarification concernant les ressources périssables restantes dans l'inventaire ; la réception, en réponse à la pluralité d'actions, d'une pluralité correspondante d'observations, chaque observation comprenant une transition dans l'état (408) associé à l'inventaire et une récompense associée (410) sous la forme de recettes générées par la vente des ressources périssables ; le stockage des observations reçues dans une mémoire de relecture (604) ; l'échantillonnage périodique, à partir de la mémoire de relecture (604), d'un lot aléatoire d'observations (608) conformément à un algorithme d'échantillonnage de relecture par ordre de priorité, dans lequel, tout au long d'une période d'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement adaptée à partir d'une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état terminal vers une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état initial ; et l'utilisation de chaque lot aléatoire d'observations pour mettre à jour (612) les paramètres de pondération (610) d'un réseau neuronal (602) qui comprend un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources, de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du réseau neuronal plus proche se rapproche d'une vraie valeur de génération de l'action d'entrée, tandis qu'il est dans l'état d'inventaire d'entrée, dans lequel le réseau neuronal peut être utilisé pour sélectionner chacune d'une pluralité d'actions générées selon un état correspondant associé à l'inventaire. 2 revendications modifiées, copie au propre 2. Le procédé selon la revendication 1 dans lequel le réseau neuronal (602) est un réseau neuronal profond. 3. Le procédé selon la revendication 1 ou 2 comprenant par ailleurs l'initialisation du réseau neuronal (602) en : 5 déterminant (802) une valeur de fonction associée au système de gestion des recettes existant, dans lequel la valeur de fonction mappe les états associés à l'inventaire à des valeurs estimées correspondantes ; transformant (804) la fonction de valeur dans une fonction action - valeur transformée correspondante adaptée à l'agent de gestion des ressources, dans 10 lequel la transformation comprend la mise en correspondance d'une taille d'étape temporelle avec une étape temporelle associée à l'agent de gestion des ressources et l'ajout de dimensions d'action à la fonction de valeur ; échantillonnant (806) la fonction action - valeur transformée pour générer un ensemble de données d'entraînement pour le réseau neuronal ; et 15 entraînant (820) le réseau neuronal en utilisant l'ensemble de données d'entraînement. 4. Le procédé selon l'une quelconque des revendications 1 à 3 comprenant par ailleurs la configuration de l'agent de gestion des ressources (402) pour commuter entre l'approximation de fonction action - valeur en utilisant le réseau neuronal (602) 20 et l'approche d'apprentissage Q basée sur une représentation sous forme de tableau de la fonction action - valeur, dans lequel la commutation comprend : pour chaque état et action (902), le calcul (904) d'une valeur d'action correspondante en utilisant le réseau neuronal (602) et en peuplant une entrée dans un tableau de consultation action - valeur (412) avec la valeur calculée ; et 25 la commutation (906) vers un mode de fonctionnement d'apprentissage Q en utilisant le tableau de consultation action-valeur (412). 5. Le procédé selon la revendication 4 dans lequel la commutation comprend par ailleurs : l'échantillonnage du tableau de consultation action - valeur pour générer un 30 ensemble de données d'entraînement pour le réseau neuronal ; l'entraînement du réseau neuronal en utilisant l'ensemble de données 3 revendications modifiées, copie au propre d'entraînement ; et la commutation vers un modèle de fonctionnement d'approximation de fonction du réseau neuronal en utilisant le réseau neuronal entraîné. 6. Le procédé selon l'une quelconque des revendications 1 à 4, dans lequel des s actions générées sont transmises à un simulateur de marché (300), et des observations sont reçues du simulateur de marché. 7. Le procédé selon la revendication 6, dans lequel le simulateur de marché (300) comprend un module de génération de demandes simulé (302), un système de réservations simulé (118) et un module de simulation de choix (306). 10 8. Le procédé selon la revendication 7 dans lequel le simulateur de marché (300) comprend par ailleurs un ou plusieurs systèmes d'inventaire concurrents simulés (122). 9. Un système (200) pour gérer un inventaire de ressources périssables ayant un horizon de vente, tout en cherchant à optimiser les recettes générées à partir de 15 celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante des ressources périssables et une période restante de l'horizon de vente, le système comprenant : un module d'agent de gestion des recettes mis en oeuvre par ordinateur (402) ; 20 un module de réseau neuronal mis en oeuvre par ordinateur (602) comprenant un dispositif d'approximation de fonction action - valeur de l'agent de gestion des ressources (402) ; un module de mémoire de relecture (604) ; et un module d'apprentissage mis en oeuvre par ordinateur(606), 25 dans lequel le module d'agent de gestion des recettes(402) est configuré pour : générer une pluralité d'actions (406), chaque action étant déterminée par la demande au module du réseau neuronal en utilisant un état actuel associé à l'inventaire et comprenant des données de publications définissant 4 revendications modifiées, copie au propre un programme de tarification concernant les ressources périssables restant dans l'inventaire ; recevoir, en réponse à la pluralité d'actions, une pluralité d'observations correspondante, chaque observation comprenant une s transition dans l'état (408) associé à l'inventaire et une récompense associée (410) sous la forme de recettes générées à partir de la vente des ressources périssables ; et stocker, dans le module de mémoire de relecture (604), les observations reçues, dans lequel le module d'apprentissage (606) est configuré pour : échantillonner périodiquement, à partir de la mémoire de relecture (604), un lot aléatoire d'observations (608) conformément à un algorithme d'échantillonnage de relecture par ordre de priorité dans lequel, tout au long d'une période d'entraînement, une distribution de probabilité pour la sélection 15 d'observations dans le lot aléatoire est progressivement adaptée à partir d'une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état terminal vers une distribution favorisant la sélection d'observations correspondant aux transitions proches d'un état initial ; et 20 utiliser chaque lot aléatoire d'observations pour mettre à jour (612) les paramètres de pondération (610) du module du réseau neuronal (602), de sorte que lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du module du réseau neuronal (602) se rapproche plus près d'une vraie valeur de génération de l'action d'entrée tandis qu'il est dans 25 l'état d'inventaire d'entrée. 10. Le système selon la revendication 9 dans lequel le module du réseau neuronal mis en oeuvre par ordinateur (602) comprend un réseau neuronal profond. 11. Le système selon l'une quelconque des revendications 9 ou 10 comprend un module de simulation du marché mis en oeuvre par ordinateur (300), dans lequel le 30 module d'agent de gestion des ressources (402) est configuré pour transmettre les actions générées au module de simulation du marché, et pour recevoir les observations correspondantes du module de simulation du marché. 5 revendications modifiées, copie au propre 12. Le système selon la revendication 11, dans lequel le module de simulation du marché (300) comprenant un module de génération de la demande simulé (302), un système de réservation simulé (118), et un module de simulation de choix (306). 13. Le système selon la revendication 12 dans lequel le module de simulation du s marché (300) comprend par ailleurs un ou plusieurs systèmes d'inventaire concurrents simulés (122). 14. Un système informatique (102) pour gérer un inventaire de ressources périssables ayant un horizon de vente, tout en cherchant à optimiser les revenus générés à partir de celui-ci, dans lequel l'inventaire a un état associé comprenant une disponibilité restante de ressources périssables et une période restante de l'horizon de vente, le système comprenant : un processeur (104) ; au moins un dispositif de mémoire (110) accessible par le processeur ; et une interface de communication (112) accessible par le processeur, 15 dans lequel le dispositif de mémoire (110) contient une mémoire de relecture (604) et un corps d'instructions de programme (114) qui, lorsqu'il est exécuté par le processeur, amène le système informatique à implémenter un procédé comprenant les étapes : de génération d'une pluralité d'actions (406), chaque action comprenant 20 la publication, via l'interface de communication (112), de données définissant un programme de tarification concernant les ressources périssables restant dans l'inventaire ; de réception, via l'interface de communication (112) et en réponse à la pluralité d'actions, d'une pluralité d'observations correspondante, chaque 25 observation comprenant une transition dans l'état (408) associé à l'inventaire et une récompense associée (410) sous la forme de recettes générées par la vente des ressources périssables ; de stockage des observations reçues dans la mémoire de relecture (604) ; 30 d'échantillonnage périodique, à partir de la mémoire de relecture (604), d'un lot aléatoire d'observations (608) conformément à un algorithme d'échantillonnage de relecture par ordre de priorité, dans lequel, tout au long 6 revendications modifiées, copie au propre d'une période d'entraînement, une distribution de probabilité pour la sélection d'observations dans le lot aléatoire est progressivement adaptée à partir d'une sélection favorisant la distribution d'observations correspondant aux transitions proches d'un état terminal vers une sélection favorisant la distribution d'observations correspondant aux transitions proches d'un état initial ; et d'utilisation de chaque lot aléatoire d'observation pour mettre à jour (612) les paramètres de pondération (610) d'un réseau neuronal (602) qui comprend un dispositif d'approximation de fonction action - valeur de 10 l'agent de gestion des ressources, de sorte que, lorsqu'il est fourni avec un état d'inventaire d'entrée et une action d'entrée, une sortie du réseau neuronal se rapproche plus près d'une vraie valeur de génération de l'action d'entrée tandis qu'il est dans l'état d'inventaire d'entrée, dans lequel le réseau neuronal peut être utilisé pour sélectionner 15 chacune de la pluralité d'actions générées selon un état correspondant associé à l'inventaire. 15. Un programme d'ordinateur comprenant un code de programme pour exécuter les étapes du procédé selon l'une quelconque des revendications 1 à 8 lorsque ledit programme est exécuté sur un ordinateur, 20