Brevet FR3095042A1 — publié le 20201016

Description Titre de l'invention : PROCEDE DE DEFINITION D'UN CHEMIN Domaine technique [0001] L'invention concerne un procédé de définition d'un chemin à suivre par un véhicule dans un environnement représenté par un graphe de noeuds reliés par des arêtes, chaque noeud dudit graphe représentant une position pouvant être prise par ledit véhicule, chaque arête entre deux noeuds étant associée à un coût de transition entre les deux noeuds, un dispositif et un système mettant en oeuvre le procédé. Technique antérieure [0002] Ces dernières années ont vu apparaître des véhicules dits autonomes, capables de se déplacer dans un environnement dc manière autonome, c'est-à-dire sans intervention humaine ou de manière serni-autonome, c'est-à-dire avec une intervention humaine limitée. Ces véhicules autonomes regroupent des véhicules automobiles capables dc circuler sur des routes en compagnie d'autres véhicules et des drones volants, roulants ou naviguant sous ou sur l'eau. [0003] On demande en général à ces véhicules autonomes d'atteindre un point, appelé aussi noeud, d'arrivée à partir d'un point de départ sans lui préciser le chemin à suivre pour atteindre le point d'arrivée. Dans certains cas, le chemin peut être contraint, le véhicule autonome devant passer par une ou plusieurs positions obligatoires entre le point de départ et le point d'arrivée. [0004] Généralement, le nombre de positions que peut adopter le véhicule autonome dans son environnement n'est pas infini, ce qui permet de représenter ledit environnement sous forme d'un graphe de noeuds reliés par des arêtes. Dans cc graphe, chaque arête reliant deux noeuds peut être associée à un poids représentatif d'un coût dc transition entre les deux noeuds. [0005] La Fig. 1 illustre un graphe G représentatif d'un environnement dans lequel peut évoluer un véhicule. [0006] Le graphe G comprend « 8» noeuds reliés par des arêtes. Chaque arête est associée à un poids. Par exemple, l'arête entre le noeud 1 et le noeud 2 est associée à un poids de valeur « 2 ». Dans un exemple, un véhicule V doit circuler dans le graphe G depuis un noeud 1 vers un noeud 6 en passant obligatoirement au moins une fois par un noeud 3. On appelle par la suite un triplet constitué d'un noeud de départ, d'un noeud d'arrivée et d'un ensemble de noeuds obligatoires, une instance du graphe G, notée I(S, D, M), S étant le noeud de départ, D étant le noeud d'arrivée et M étant l'ensemble des noeuds obligatoires. Par ailleurs, nous appelons résolution de l'instance I(S, D, M) une procédure permettant de rechercher un meilleur chemin dans un graphe G pour une 2 instance l(S, D, M) dudit graphe. Une résolution d'instance consiste à rechercher le chemin minimisant un coût de transition global, le coût de transition global étant une somme de coûts de transition entre chaque paire de noeuds successifs composant ledit chemin. Dans l'exemple de la Fie. 1, l'instance à résoudre est donc! (noeud 1, noeud 6, (noeud 3)). La résolution de cette instance donne un ordre de parcours d'un ensemble de noeuds, du noeud 1 au noeud 6. L'ordre de parcours suivant est ainsi obtenu : [0007] {noeud 1, noeud 2, noeud 5, noeud 3. noeud 5, noeud 6}. [0008] Dans l'exemple de la Fig. 1, le graphe G comprend peu de noeuds. Pour un nombre de noeuds de cet ordre, la résolution d'une instance est relativement simple, même si cette instance comprend des noeuds obligatoires. Il est en effet possible de tester exhaustivement dans un temps raisonnable chaque combinaison possible des suites de noeuds pour trouver celle qui résout l'instance avec un coût minimal. Une telle méthode d'optimisation serait inapplicable pour des graphes comprenant un grand nombre de noeuds, a fortiori avec des instances à résoudre comprenant un grand nombre de noeuds obligatoires. [0009] Des méthodes connues existent pour résoudre des instances dans un graphe comprenant un grand nombre de noeuds telles que les méthodes 2-opt, 3-opt, l'heuristique de Lin-Kernighan, etc. Ces méthodes ont toutefois des temps de résolution très importants, où, lorsque le temps de résolution est contraint, génèrent des solutions très sous-optimales. [0010] 11 est souhaitable de pallier ces inconvénients de l'état de la technique. Il est notamment souhaitable de proposer une méthode qui permette de résoudre une instance comprenant un ensemble de noeuds obligatoires important dans un graphe comprenant un grand nombre de noeuds de manière optimale ou quasi optimale dans un temps raisonnable. Exposé de l'invention [0011] Selon un premier aspect de la présente invention, la présente invention concerne un procédé de définition d'un chemin à suivre par un véhicule dans un environnement représenté par un graphe de noeuds reliés par des arêtes, chaque noeud dudit graphe représentant une position pouvant être prise par ledit véhicule, chaque arête entre deux noeuds étant associée à un coût de transition entre les deux noeuds. Le procédé comprend : obtenir une instance dudit graphe, dite instance à résoudre, chaque instance étant représentée par un noeud de départ, un noeud d'arrivée et un ensemble de noeuds obligatoires par lesquels le véhicule doit passer, lesdits noeuds de départ, d'arrivée et obligatoires formant les noeuds de l'instance à résoudre ; obtenir une information représentative d'un ordre initial de parcours desdits noeuds obligatoires en appliquant une procédure utilisant un réseau de neurones convolutif de graphe, dit RNCG, adapté 3 audit graphe à ladite instance à résoudre; exécuter une procédure d'optimisation locale de l'ordre des noeuds obligatoires afin d'obtenir un ordre des noeuds obligatoires optimisé, ladite procédure étant initialisée avec ladite information représentative de l'ordre initial; définir un chemin pour ladite instance à résoudre à partir de l'ordre des noeuds obligatoires optimisé et pour chaque paire de noeuds de ladite instance à résoudre, d'un plus court chemin entre les noeuds de ladite paire. [0012] Selon un mode de réalisation, la procédure utilisant le RNCG est une procédure itérative prenant une instance du graphe en entrée, dite instance d'entrée et générant une information représentative d'un ordre initial de parcours des noeuds obligatoires de l'instance d'entrée en sortie, dite information de sortie, et comprenant à chaque itération : appliquer le RNCG à ladite instance d'entrée afin d'obtenir pour chaque noeud du graphe une valeur représentative d'une probabilité d'être le prochain noeud obligatoire à traverser à la suite du noeud de départ de l'instance d'entrée ; identifier le noeud obligatoire de l'ensemble de noeuds obligatoires de l'instance d'entrée possédant la probabilité la plus élevée ; insérer le noeud obligatoire identifié dans une liste ordonnée de noeuds obligatoires; remplacer le noeud de départ de l'instance d'entrée par le noeud obligatoire identifié et retirer le noeud obligatoire identifié de l'ensemble de noeuds obligatoires de l'instance d'entrée ; les itérations prenant fin lorsqu'un nombre de noeuds dans l'ensemble de noeuds obligatoires de l'instance d'entrée est égal à un, le noeud obligatoire restant dans l'ensemble de noeuds obligatoires de l'instance d'entrée étant inséré dans ladite liste ordonnée et ladite liste ordonnée formant l'information de sortie. [0013] Selon un mode de réalisation, la procédure d'optimisation locale de l'ordre des noeuds obligatoires est une procédure itérative prenant une instance, dite instance initiale, et une information représentative d'un ordre de noeuds obligatoires, dit ordre initial, en entrée et générant une information représentative d'un ordre de noeuds obligatoires optimisé en sortie, dit ordre optimisé, chaque information représentative d'un ordre de noeuds obligatoires étant une liste de noeuds obligatoires ordonnés, et comprend à chaque itération: déterminer une paire de noeuds obligatoires, dits noeuds pivots, parmi les noeuds obligatoires de la liste de noeuds obligatoires ordonnée de l'ordre initial, dite liste initiale, et obtenir une liste de noeuds obligatoires ordonnée modifiée, dite liste modifiée, dans laquelle les noeuds obligatoires de la liste initiale situés entre les deux noeuds pivots ont été intervertis symétriquement, la paire de noeuds pivots déterminée étant différente de toutes paires de noeuds pivots déjà utilisées pour modifier l'ordre des noeuds obligatoires dans la liste initiale ; définir une information représentative de l'ordre des noeuds obligatoires dans la liste modifiée comme étant un ordre optimisé temporaire lorsqu'un coût de transition global d'un chemin entre les noeuds de départ et d'arrivée de l'instance initiale en suivant l'ordre des noeuds obligatoires dans la liste modifiée est inférieur à un coût de transition global dudit chemin en suivant l'ordre des noeuds obligatoires dans la liste initiale; et définir l'ordre optimisé temporaire comme étant l'ordre initial ; mettre fin aux itérations de la procédure d'optimisation locale lorsqu'une condition d'arrêt est remplie, l'ordre optimisé étant le dernier ordre optimisé temporaire obtenu par la procédure d'optimisation locale. [0014] Selon un mode de réalisation, le RNCG a été adapté audit graphe lors d'une phase préalable d'adaptation, la phase préalable d'adaptation comprenant une procédure d'apprentissage permettant d'adapter des paramètres d'une phase de convolution et d'une phase de combinaison linéaire dudit RNCG, dits paramètres du RNCG, la procédure d'apprentissage étant une procédure itérative comprenant à chaque itération : générer une instance aléatoire du graphe ; appliquer la procédure utilisant le RNCG à l'instance aléatoire afin d'obtenir une première information représentative d'un ordre des noeuds obligatoires de l'instance aléatoire, dite première information ; générer une deuxième information représentative d'un ordre des noeuds obligatoires de l'instance aléatoire définie aléatoirement, dite deuxième information ; obtenir une première et une deuxième informations représentatives d'un ordre des noeuds obligatoires optimisées, dites première et deuxième informations optimisées, en appliquant la procédure d'optimisation locale respectivement à l'ordre des noeuds obligatoires correspondant à la première et à la deuxième informations; sélectionner l'ordre représenté par ladite première ou par ladite deuxième information optimisée permettant de minimiser un coût de transition global d'un chemin entre les noeuds de départ et d'arrivée de l'instance aléatoire ; former une nouvelle instance à partir de chaque noeud obligatoire de l'instance aléatoire, chaque nouvelle instance ayant pour noeud de départ le noeud obligatoire correspondant à la nouvelle instance, pour noeud d'arrivée le noeud d'arrivée de l'instance aléatoire et pour un ensemble de noeuds obligatoires, les noeuds suivant le noeud obligatoire utilisé comme noeud de départ de la nouvelle instance dans l'ordre sélectionné ; et pour l'instance aléatoire et chaque nouvelle instance, former un couple en associant ladite instance à un prochain noeud obligatoire à traverser pour ladite instance, ledit prochain noeud obligatoire à traverser étant le noeud obligatoire suivant le noeud de départ de ladite instance dans l'ordre sélectionné ; mettre à jour une fenêtre d'apprentissage avec les couples ainsi formés; faire évoluer les paramètres du RNCG pour minimiser une erreur de prédiction par le RNCG d'un prochain noeud obligatoire à traverser en utilisant le prochain noeud obligatoire de couples de la fenêtre d'apprentissage comme référence de prochains noeuds obligatoires à traverser à obtenir par le RNCG. [0015] Selon un deuxième aspect de l'invention, l'invention concerne un dispositif pour définir un chemin à suivre par un véhicule dans un environnement représenté par un graphe de noeuds reliés par des arêtes, chaque noeud dudit graphe représentant. une position pouvant être prise par ledit véhicule, chaque arête entre deux noeuds étant associée à un coût de transition entre les deux noeuds. Le dispositif comprend : des moyens d'obtention pour obtenir une instance dudit graphe, dite instance à résoudre, chaque instance étant représentée par un noeud de départ, un noeud d'arrivée et un ensemble de noeuds obligatoires par lesquels le véhicule doit passer, lesdits noeuds de départ, d'arrivée et obligatoires formant les noeuds de l'instance à résoudre ; des moyens d'obtention pour obtenir une information représentative d'un ordre initial de parcours desdits noeuds obligatoires en appliquant une procédure utilisant un réseau de neurones convolutif de graphe, dit RNCG, adapté audit graphe à ladite instance à résoudre; des moyens d'exécution pour exécuter une procédure d'optimisation locale de l'ordre des noeuds obligatoires afin d'obtenir un ordre des noeuds obligatoires optimisé, ladite procédure étant initialisée avec ladite information représentative de l'ordre initial; des moyens de définition pour définir un chemin pour ladite instance à résoudre à partir de l'ordre des noeuds obligatoires optimisé et pour chaque paire de noeuds de ladite instance à résoudre, d'un plus court chemin entre les noeuds de ladite paire. [0016] Selon un troisième aspect de l'invention, l'invention concerne un véhicule comprenant un dispositif selon le deuxième aspect. [0017] Selon un quatrième aspect de l'invention, l'invention concerne un programme d'ordinateur, comprenant des instructions pour mettre en oeuvre, par un dispositif, le procédé selon le premier aspect, lorsque ledit programme est exécuté par un processeur dudit dispositif. [0018] Selon un cinquième aspect de l'invention, l'invention concerne des moyens de stockage, caractérisés en ce qu'ils stockent un programme d'ordinateur comprenant des instructions pour exécuter, par un dispositif, le procédé selon le premier aspect, lorsque ledit programme est exécuté par un processeur dudit dispositif. Brève description des dessins [0019] Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, appa- raîtront plus clairement à la lecture de la description suivante d'un exemple dc réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels : [0020] [fig.1] illustre un graphe représentatif d'un environnement dans lequel peut évoluer un véhicule ; [0021] [fig.2] illustre schématiquement une architecture matérielle d'un module de traitement apte à mettre en oeuvre l'invention ; [0022] [fig.3] illustre schématiquement un procédé de définition d'un chemin d'un véhicule selon l'invention ; 6 [0023] [fig.4] illustre schématiquement une procédure d'application d'un réseau de neurones convolutif de graphe à une instance d'un graphe ; [0024] [fig.5] illustre schématiquement une procédure d'apprentissage de paramètres d'un réseau de neurones convolutif de graphe ; [0025] [fig.6] illustre schématiquement une procédure itérative de détermination d'un ordre de parcours de noeuds obligatoires pour une instance d'un graphe basée sur le réseau de neurones convolutif de graphe ; et, [0026] [fig.7] illustre schématiquement une procédure d'optimisation locale d'un ordre des noeuds obligatoires. [0027] EXPOSE DETAILLE DE MODES DE REALISATION [0028] L'invention est décrite par la suite dans un contexte de véhicule autonome roulant circulant dans un environnement représenté par un graphe tel que le véhicule V dans le graphe G décrit en relation avec la Fig. 1, le graphe G n'étant pas orienté. Un graphe est dit orienté lorsqu'au moins un coût de transition entre deux noeuds du graphe dépend du sens de la transition entre les deux noeuds. L'invention est toutefois adaptée à d'autres types de véhicules autonomes ou semi-autonomes, tels qu'un dronc volant ou naviguant sur ou sous l'eau, et évoluant dans un environnement pouvant être représenté par un graphe orienté ou pas. [0029] Le procédé de définition d'un chemin à suivre par un véhicule dans son envi- ronnement se traduit par un procédé de résolution d'une instance d'un graphe. Comme décrit par la suite, ce procédé peut fonctionner en temps réel, ce procédé étant capable de résoudre une instance très rapidement et de fournir un chemin quasi-optimal au véhicule V en s'appuyant sur un réseau de neurones convolutif de graphe, dit RNCG. Le RNCG comprend des paramètres obtenus en utilisant une procédure d'apprentissage itérative pouvant être mise en oeuvre pendant une phase non temps réelle, préalablement à tout déplacement du véhicule V. [0030] Dans un mode de réalisation, le véhicule V comprend un module de traitement 10 exécutant le procédé de définition d'un chemin selon l'invention. Dans ce mode de réalisation, le module de traitement 10 exécute aussi la procédure d'apprentissage itérative permettant de déterminer les paramètres du réseau de neurones. [0031] Dans d'autres modes de réalisation, le module de traitement 10 est un module externe au véhicule V qui reçoit une instance à résoudre et communique au véhicule V un résultat du procédé de définition d'un chemin pour ladite instance, c'est-à-dire un chemin à suivre par le véhicule V. [0032] La Fig. 2 illustre schématiquement un exemple d'une architecture matérielle du module de traitement 10. [0033] Selon l'exemple d'architecture matérielle représenté à la Fig. 2, le module de traitement 10 comprend alors, reliés par un bus de communication 100 : un processeur 7 ou CPU (« Central Processing Unit » en anglais) 101 ; une mémoire vive RAM (« Random Access Memory » en anglais) 102 ; une mémoire morte ROM (« Read Only Memory » en anglais) 103; une unité de stockage telle qu'un disque dur ou un lecteur de support de stockage, tel qu'un lecteur de cartes SD (« Secure Digital » en anglais) 104; au moins une interface de communication 105 permettant par exemple au module de traitement 10 de communiquer des caractéristiques d'un chemin à suivre par le véhicule V à un module contrôlant les déplacements du véhicule V. [0034] Le processeur 101 est capable d'exécuter des instructions chargées dans la RAM 102 à partir de la ROM 103, d'une mémoire externe (non représentée), d'un support de stockage (tel qu'une carte SD), ou d'un réseau de communication. Lorsque le module de traitement 10 est mis sous tension, le processeur 101 est capable de lire de la RAM 102 des instructions et de les exécuter. Ces instructions forment un programme d'ordinateur causant l'exécution complète ou partielle, par le processeur 101, du procédé décrit ci-après en relation avec la Fig. 3 et du procédé décrit en relation avec la Fig. 6. [0035] Le procédé décrit en relation avec la Fig. 3 et le procédé décrit en relation avec la Fig. 6 peuvent être implémentés sous forme logicielle par exécution d'un ensemble d'instructions par une machine programmable, par exemple un DSP (« Digital Signal Processor » en anglais) ou un tnicrocontrôleur, ou être implémentés sous forme matérielle par une machine ou un composant dédié, par exemple un FPGA (« Field-Programmable Gate Array » en anglais) ou un ASIC (« Application-Specific Integrated Circuit » en anglais). [0036] La Fig. 3 illustre schématiquement un procédé de définition d'un chemin d'un véhicule selon l'invention. [0037] Dans une étape 30, le module de traitement 10 obtient une instance à résoudre IR ( SR, DR,MR) d'un graphe G. L'instance IR(SR,DR,MR) est donc représentée par un noeud de départ SR, un noeud d'arrivée D R et un ensemble de noeuds obligatoires M. L'ensemble de noeuds obligatoires MR peut être vide ou comprendre un ou plusieurs noeuds obligatoires. Le noeud de départ SR, le noeud d'arrivée DR et l'ensemble de noeuds obligatoires MR forment les noeuds de l'instance I R (SR, DR, M R) - [0038] Dans une étape 31, le module de traitement 10 obtient une information représentative d'un ordre initial de parcours des noeuds obligatoires de l'ensemble de noeuds obligatoires M u entre le noeud de départ SR et le noeud d'arrivée D R en appliquant une procédure déctite en relation avec la Fig. 6 àl'instance IR(SR,DR,MR). La procédure de la Fig. 6 utilise un RNCG adapté au graphe G. Une application dudit RNCG à une instance d'un graphe est décrite en relation avec la Fig. 4. L'adaptation 8 du RNCG au graphe G passe par une phase préliminaire d'adaptation. Cette phase préliminaire d'adaptation s'appuie sur une procédure d'apprentissage itérative décrite en relation avec la Fig. 5 durant laquelle des paramètres du RNCG sont déterminés. L'information représentative d'un ordre initial de parcours des noeuds obligatoires de l'ensemble de noeuds obligatoires MR est une liste ordonnée de noeuds obligatoires. [0039] Dans une étape 32, le module de traitement 10 exécute une procédure d'optimisation locale de l'ordre des noeuds obligatoires afin d'obtenir un ordre des noeuds obligatoires optimisé, ladite procédure étant initialisée avec l'information représentative de l'ordre initial obtenue lors de l'étape 31. La procédure d'optimisation locale de l'ordre des noeuds obligatoires est décrite en relation avec la Fig. 7. [0040] Dans une étape 33, le module de traitement 10 définit un chemin pour l'instance IR(SR,DR,MR) à partir de l'ordre des noeuds obligatoires optimisé et, pour chaque paire de noeuds de l'instance Tr? ( SR, DR,MR), d'un plus court chemin entre les noeuds de ladite paire. 100411 La Fig. 4 illustre schématiquement une procédure d'application d'un RNCG à une instance I(S, D, M) du graphe G. 100421 Dans une étape 401, le module de traitement 10 encode une instance l(S, D, M) du graphe G sous forme d'un vecteur Xi à une dimension. Dans un mode de réalisation, lors de cet encodage, chaque noeud du graphe G est encodé suivant un nombre NB4 = 3 d'attributs (AI, A2, A3) : 100431 - A1=1 si le noeud est un noeud de départ pour l'instance I(S, D, M), A1=0 sinon ; 100441 - A2=1 si le noeud est un noeud d'arrivée pour l'instance l(S, D, M), A2=0 sinon ; 100451 - A3=1 si le noeud est un noeud obligatoire pour l'instance l(S, D, M), A3=0 sinon. 100461 On suppose ici que les noeuds du graphe G sont ordonnés. A la fin de l'encodage, les noeuds du graphe G apparaissent dans le vecteur X1 dans cet ordre sous forme de triplets d'attributs (Al, A2, A3). [0047] Dans une étape 402, le module de traitement 10 met le vecteur Xi sous forme d'une matrice MA T1 ayant un nombre de lignes égal au nombre de noeuds NB G: dans le graphe G et un nombre de colonnes égal au nombre NB d'attributs utilisés. On passe donc d'un vecteur à une dimension (Xi) à un vecteur à deux dimensions ( MA Ti). [0048] Dans une étape 403, le module de traitement 10 applique le RNCG à la matrice MA Ti. [0049] Une application d'un réseau de neurones convolutif comprend en général une pluralité de phases dont les phases suivantes : [0050] - Une phase de convolution ou plusieurs phases de convolution consécutives ; [0051] - Une phase de vectorisation (mise sous forme de vecteur) des données de sortie de la 9 ou des phases de convolution ; [0052] - Une phase de combinaison linéaire, dite « fully connected ». [0053] Chaque phase de convolution se décompose généralement en trois sous-phases : [0054] - une sous-phase de convolution par un noyau de convolution de données d'entrée permettant d'obtenir un ensemble de caractéristiques représentatives desdites données d'entrées. Les caractéristiques obtenues ne sont pas prédéfinics niais apprises par le réseau de neurones lors d'une phase d'entraînement. Pendant la phase d'entraînement, le noyau de convolution évolue de manière à « apprendre » à extraire des caractéristiques pertinentes pour un problème donné. [0055] - une sous-phase de « mise en commun » (« pooling » en terminologie anglo- saxonne) ayant pour but de réduire la taille des données qu'elle reçoit en entrée (issue de la convolution), tout en préservant les caractéristiques importantes de ces données d'entrées. La phase de « mise en commun » permet de réduire le nombre de calculs dans le réseau de neurones convolutif. [0056] - une sous-phase d'application d'une fonction d'activation consistant à appliquer une fonction mathématique, dite fonction d'activation, aux données obtenues en sortie de chaque convolution (ou de la phase de mise en commun s'il y en aune). Le terme de fonction d'activation vient d'un équivalent biologique potentiel d'activation, qui représente un seuil de stimulation qui, une fois atteint, entraîne une réponse d'un neurone. [0057] Lorsqu'un réseau de neurones est utilisé dans une méthode de classification ou de prédiction de valeurs, la phase de combinaison linéaire constitue toujours la dernière phase d'un réseau de neurones, qu'il soit convolutif ou non. Cette phase reçoit un vecteur en entrée, dit vecteur d'entrée, et produit un nouveau vecteur en sortie, dit vecteur de sortie. Pour cela, elle applique une combinaison linéaire aux composantes du vecteur d'entrée. La phase de combinaison linéaire permet de classifier les données d'entrées du réseau de neurones suivant un nombre de classes prédéfinies N. Elle renvoie donc un vecteur de sortie de taille N. Chaque composante du vecteur de sortie est associée à une classe et est représentative d'une probabilité pour les données d'entrées du réseau de neurones d'appartenir à ladite classe. Chaque composante du vecteur d'entrée peut contribuer différemment au vecteur de sortie. Pour ce faire, lors de l'application de la combinaison linéaire, un poids différent est appliqué à chaque composante en fonction d'une importance qu'on souhaite donner à la caractéristique que cette composante représente. La combinaison linéaire de la phase de combinaison linéaire est généralement suivie d'une phase de transformation du vecteur de sortie en distribution de probabilité. Le réseau de neurones convolutif apprend les valeurs des poids de la phase de combinaison linéaire de la même manière qu'il apprend à faire évoluer le noyau de convolution de chaque phase de convolution. [0058] Comme nous le décrivons par la suite, le RNCG utilisé dans l'invention applique une pluralité de phases de convolution à un graphe. Lesdites phases de convolution ne comprennent pas dc sous-phase dc « mise en commun » et comprennent une sous-phase d'application d'une fonction d'activation mise en oeuvre par la fonction ReLUO telle que ReLU(x)=max (0, x). [0059] Dans un mode de réalisation, le noyau dc convolution utilisé dans l'invention est tiré de l'article Thomas N Kipf and Max Welling. Setni-supervised classification with graph con volutional networks. KIR 2017. Cet article propose une relation combinant convolution et application d'une fonction d'activation. iT le0W(E>) [0060] H(1+1) représente des données de sortie issues d'une application d'une convolution par un noyau de convolution et d'une fonction d'activation à des données d'entrées fi . = A -Ft J, A étant une matrice d'adjacence du graphe G et I étant une matrice d'identité. D est une matrice de degrés de À c'est-à-dire une matrice diaconale telle que D ii TAT(1) est une matrice de poids spécifique à une U Yr phase de convolution I. Ces poids évoluent pendant la phase d'entraînement de manière à apprendre au réseau de neurones à extraire des caractéristiques pertinentes de chaque instance du graphe G. La phase préliminaire d'adaptation au graphe G utilisant la procédure d'apprentissage itérative décrite en relation avec la Fig. 5 a pour but de déterminer les poids (ou paramètres) de chaque matrice w(I).G est une fonction d'activation. Dans un mode de réalisation, la fonction d'activation G utilisée est la fonction RcLU() telle que ReLU(x)=max (0, x). [0061] Dans un mode de réalisation, le RNCG appliqué lors de l'étape 403 est multicouches, c'est-à-dire qu'il comprend plusieurs phases de convolution. Par exemple, le RNCG utilise « 4 » phases de convolution. [0062] Chaque phase de convolution du RNCG reçoit en entrée une matrice, dite matrice d'entrée, de NBC _IN colonnes et de NBL_IN lignes et génère en sortie une matrice, dite matrice de sortie, de NBL_OUT lignes et NBC_OUT colonnes. La matrice d'entrée H (0) de la première phase de convolution du RNCG est la matrice MA T1. Lorsque deux phases dc convolution de RNCG se suivent, la matrice de sortie de la première phase de convolution devient la matrice d'entrée de la phase de convolution suivante. Chaque composante d'une matrice de sortie est représentative dc caractéristiques des composantes de la matrice d'entrée (et donc dc la matrice MA T Chaque matrice d'entrée (respectivement chaque matrice de sortie) comprend NEL 1N=fe lignes (respectivement NEL OUT=N B o lignes). Chaque matrice 11 de sortie (et donc respectivement chaque matrice d'entrée à partir de la deuxième phase de convolution du RNCG) peut comprendre un nombre de colonnes NBC OUT (respectivement NBC IN) fixe ou variable d'une phase de convolution à l'autre. Dans un mode de réalisation NBC OUT=10. [0063] On considère ici que chaque phase de convolution classifie les données d'entrée en un nombre de classes égal au nombre de composantes de la matrice de sortie (c'est-à-dire en un nombre de classes égal à NBI._OUT X NBC _OUT). [0064] Dans une étape 404, le module de traitement 10 met la matrice de sortie issue de la dernière phase de convolution du RNCG sous forme d'un vecteur Yi de N.B.L. _OUT X NE C_O UT composantes en mettant bout à bout chaque ligne de ladite matrice de sortie. [0065] Dans une étape 405, le module de traitement 10 applique une phase de combinaison linéaire (« fully connected » en terminologie anglo-saxonne) au vecteur Yi. La phase de combinaison linéaire génère un vecteur 0 i de composantes 0 ij (j allant de « 1 » à NB G) à partir du vecteur Yi. Chaque composante 0ii est calculée de la manière suivante : [0066] où W est un poids d'un vecteur W1 et b. est un biais d'un vecteur de biais b i et Y1. Wil est un produit scalaire. Chaque noeud du graphe G est associé à une composante du vecteur 0 chaque composante étant un nombre réel représentatif d'une probabilité que le noeud correspondant soit le prochain noeud obligatoire de l'ensemble de noeuds obligatoires M de l'instance 1(5, D, M) devant être traversé par le véhicule V après avoir quitté le noeud de départ s de l'instance 1(5, D, M). 100671 Dans une étape 406, le module de traitement 10 transforme le vecteur 0 en un vecteur de probabilité P. Pour cc faire, dans un mode de réalisation, une fonction exponentielle normalisée (« Softmax function » en terminologie anglo-saxonne) est appliquée à chaque composante du vecteur 0 i. Une fonction exponentielle normalisée prend en entrée un vecteur z de K nombres réels 2" et génère en sortie un vecteur z ) de K nombres réels strictement positifs et de somme « 1 » tel que : [0068] En sortie du RNCG (i.e. en sortie de l'étape 406), le module de traitement 10 obtient pour chaque noeud du graphe G, une probabilité que ledit noeud soit le prochain noeud obligatoire de l'ensemble de noeuds obligatoires M de l'instance 1(5, D, M) devant être 12 traversé par le véhicule V après avoir quitté le noeud de départ S de l'instance I(S, D, M). [0069] Dans un mode de réalisation, l'instance 1(5, D, M) est encodée différemment, par exemple, avec un nombre NB_.4 d'attributs différent, ou avec un nombre de lignes NE G différent, par exemple, en ne faisant apparaître que les noeuds de départ, d'arrivée et obligatoires dans le vecteur Xi. [0070] Dans un mode de réalisation, le module de traitement 10 encode directement l'instance 1(5, D, M) sous forme de matrice MA T 1 . [0071] La Fig. 5 illustre schématiquement une procédure d'apprentissage de paramètres d'un réseau de neurones convolutif de graphe. [0072] Dans une étape 501, le module de traitement 10 génère une fenêtre d'apprentissage F . La fenêtre d'apprentissage F comprend des couples, la fenêtre pouvant comprendre un nombre de couples limité à un nombre prédéfini g. Chaque couple associe une instance à un prochain noeud obligatoire à visiter. Dans un mode de réalisation, la fenêtre d'apprentissage F est initialisée à l'ensemble vide et q=50000. [0073] Dans une étape 502, le module de traitement 10 génère une instance aléatoire I(S,D [0074] Dans une étape 503, le module de traitement 10 applique le procédé décrit en relation avec la Fig. 6 à l'instance aléatoire /(S,D,M) afin d'obtenir une liste ordonnée L OR yc G de noeuds obligatoires à traverser par le véhicule V entre le noeud de départ Set le noeud d'arrivée D. La liste ordonnée L Op\fcc est représentative d'un premier ordre de parcours des noeuds obligatoires. Le procédé décrit en relation avec la Fig. 6 fait intervenir le RNCG pour définir la liste ordonnée L O ieNc 100751 L'étape 503 est suivie par une étape 504 au cours de laquelle le module de traitement 10 génère une liste ordonnée L °RAND pour l'instance aléatoire l(S,D,M) dans laquelle l'ordre des noeuds obligatoires de l'ensemble de noeuds obligatoires M est défini aléatoirement. La liste ordonnée L OR_I D est représentative d'un deuxième ordre de parcours des noeuds obligatoires. [0076] Dans une étape 505, le module de traitement 10 obtient une liste ordonnée optimisée 1H enpartant de la liste ordonnée L ORycc. Pour ce faire, le module de RNCG traitement 10 utilise par exemple la procédure d'optimisation locale de l'ordre des noeuds obligatoires que nous décrivons par la suite en relation avec la Fig. 7. Lors de l'étape 505, le module de traitement 10 calcule un coût de transition global in° P 1; N C du chemin entre le noeud de départ et le noeud d'arrivée de l'instance aléatoire l(S,D,M) générée lors de l'étape 502. Le coût de transition global d'un chemin entre un noeud de départ et un noeud d'arrivée d'une instance d'un graphe dépend de l'ordre de parcours 13 des noeuds obligatoires de cette instance. Le coût de transition global d'un chemin entre un noeud de départ et un noeud d'arrivée d'une instance d'un graphe est une somme de coûts de plus court chemin entre chaque paire de noeuds successifs de l'instance formant ledit chemin. Le calcul du coût de transition global O» du RNCG chemin s'appuie sur un tableau précalculé TAB comprenant pour chaque paire de noeuds du graphe G, un plus court chemin reliant les deux noeuds de ladite paire et un coût dudit plus court chemin Chaque coût de plus court chemin est calculé en utilisant le coût de transition associé à chaque arête du graphe G utilisée pour Ruiner ledit plus court chemin. Le plus court chemin entre chaque paire de noeuds du graphe G a par exemple été déterminé en utilisant un algorithme de Dijkstra décrit clans le document Dijkstra, E. W., « A note on two problems in connexion with graphs », Numerische Matheinatik, vol. 1, 1959, p. 269-271. La liste ordonnée L °PI est représentative "RNCG d'un premier ordre de parcours optimisé des noeuds obligatoires. [0077] Dans une étape 506, le module de traitement 10 obtient une liste ordonnée optimisée T n1 t en partant de la liste ordonnée aléatoire Lp, A ND obtenue à l'étape R .4 N!) 504. Pour ce faire, le module de traitement 10 utilise par exemple la procédure d'optimisation locale de l'ordre des noeuds obligatoires que nous décrivons par la suite en relation avec la Fig. 7. Lors de l'étape 506, le module de traitement 10 calcule un coût de transition global °Pt du chemin entre le noeud de départ et le noeud R 4 N'I) d'arrivée de l'instance aléatoire I(S,D,M) générée lors de l'étape 502. Comme lors de l'étape 505, le calcul du coût de transition global roi' du chemin s'appuie sur le RAND tableau précalculé TAB. La liste ordonnée L 'OP/ est représentative d'un "RAND deuxième ordre de parcours optimisé des noeuds obligatoires. [0078] Dans une étape 507, le module de traitement 10 compare le coût f-,°P e au coût RNCG roP . Si le coût roP1 est supérieur au coût (-0P , le module de RAND RN cc L. RAND traitement 10 sélectionne la liste ordonnée T n°P t dans une étape 508. Sinon, le '-'RAND module de traitement 10 sélectionne la liste ordonnée T ni)Pt dans une étape 509. L. La liste ordonnée sélectionnée est alors notée T nOP 1-'-"SELECT- [0079] Dans une étape 510, le module de traitement 10 initialise une variable j à l'unité. [0080] Dans une étape 511, le module de traitement initialise une instance temporaire i( s,d,iii )à la valeur de l'instance aléatoire /(5',D,M) générée lors de l'étape 502. [0081] Dans une étape 512, le module de traitement 10 identifie le noeud obligatoire in de l'ensemble de noeuds obligatoires ni en position/ dans la liste ordonnée sélectionnée 14 no pi . Lors du premier passage par l'étape 512, la variable j étant égale à L u SELECT «1», le module de traitement 10 choisit le noeud obligatoire I situé en première position dans la liste ordonnée sélectionnée/. 7,10P e "SELECT [0082] Dans une étape 513, le module de traitement 10 sauvegarde le couple formé par l'instance temporaire i(s,d,m) et le noeud obligatoire 1/11 en dernière position dc la fenêtre d'apprentissage F. Si avant la sauvegarde dudit couple dans la fenêtre d'apprentissage F, la fenêtre contenait q couples, le couple situé en première position de la fenêtre d'apprentissage F est supprimé de ladite fenêtre. Ainsi, la fenêtre d'apprentissage F comprend toujours un nombre q de couples. [0083] Dans une étape 514, le module dc traitement 10 donne au noeud de départ s de l'instance temporaire i(s,d,m) la valeur Mi et retire le noeud obligatoire Mi de l'ensemble dc noeuds obligatoires tu. [0084] Dans une étape 515, le module dc traitement 10 détermine si l'ensemble dc noeuds obligatoires m est vide. [0085] Si l'ensemble de noeuds obligatoires in n'est pas vide, le module de traitement 10 in- crémente la variable/ d'une unité dans une étape 516 et retourne à l'étape 512. [0086] Si l'ensemble de noeuds obligatoires m est vide, le module de traitement 10 exécute une étape 517. Lors de l'étape 517, le module de traitement 10 lance une procédure d'entraînement itérative du RNCG. La procédure d'entraînement itérative comprend K [TER itérations. Dans un mode de réalisation, K TTER=10000. A chaque itération, le module de traitement 10 sélectionne aléatoirement un nombre B« de couples associant une instance à un prochain noeud obligatoire à visiter dans la fenêtre d'apprentissage F. Dans un mode de réalisation, le nombre de couples B c=32. Pour chaque couple sélectionné, le module de traitement 10 applique le RNCG à l'instance représentée dans le couple tel que décrit en relation avec la Fig. 4 en ajustant (i.e. en apprenant selon la terminologie des réseaux de neurones) des paramètres du RNCG afin que le noeud obligatoire du couple soit associé à la probabilité la plus élevée d'être le prochain noeud obligatoire à visiter. Les paramètres entraînés sont les poids de chaque matrice de poids vi/n utilisée dans le RNCG et les poids utilisés lors de la phase de combinaison linéaire de l'étape 405. Chaque itération dc la procédure d'entraînement des paramètres du RNCG comprend une minimisation d'une fonction de coût ii(e ) par descente stochastique de gradient, e étant l'ensemble des paramètres du RNCG à apprendre. [0087] où N B G est le nombre de noeuds dans le graphe G. 1-i est une variable qui vaut 1 » si pour l'instance numéro i, le prochain noeud obligatoire à visiter est le noeud du graphe G d'indice j, et « O » sinon. Xi est le vecteur résultant d'un encodage de l'instance numéro i tel que décrit en relation avec l'étape 401. L'instance numéro i est une instance correspondant à un des B couples sélectionnés aléatoirement dans la fenêtre d'apprentissage F, le prochain noeud obligatoire à visiter étant le noeud associé à l'instance numéro i dans ledit couple. Les instances de la fenêtre d'apprentissage F sont des instances considérées comme résolues sur lesquelles la procédure d'apprentissage s'appuie pour apprendre les paramètres du réseau de neurones. La composante B G de la fonction de coût H 09 ) re- L. -t. (f(Xi, 0) 1 ,i =1 /,.1 I présente une erreur de prédiction par le RNCG du prochain noeud obligatoire à traverser correspondant à l'instance numéro i. la fonction de coût me) est donc une moyenne d'erreurs de prédiction par le RNCG de prochains noeuds à traverser pour un ensemble de B, instances. Lors de la première itération de la procédure d'apprentissage de paramètres du RNCG (et donc lors de la première itération de la procédure d'entraînement des paramètres du RNCG), le module de traitement 10 utilise des paramètres du RNCG déterminés aléatoirement pour le démarrage de la descente stochastique de gradient. Lors des itérations suivantes de la procédure d'apprentissage des paramètres du RNCG ou de la procédure d'entraînement des paramètres du RNCG, le module de traitement 10 initialise la descente stochastique de gradient avec les paramètres du RNCG déterminés lors de la dernière exécution de la procédure d'entraînement des paramètres du RNCG. [0088] L'étape 517 est suivie d'une étape 518 au cours de laquelle le module de traitement 10 détermine si une condition d'arrêt de la procédure d'apprentissage des paramètres du RNCG est respectée. Dans une mode de réalisation, la condition d'arrêt est une durée maximum d'exécution de la procédure d'apprentissage de paramètres du RNCG. Si à l'étape 518 cette durée maximum est atteinte, la procédure d'apprentissage des paramètres du RNCG s'arrête lors d'une étape 519. Sinon, le module de traitement 10 retourne à l'étape 502. Dans un mode de réalisation, la durée maximum est égale à «24 » heures. 100891 A la fin de la procédure d'apprentissage de paramètres du RNCG, le RNCG est considéré comme entraîné. 100901 La Fig. 6 illustre schématiquement une procédure itérative de détermination d'un ordre de parcours de noeuds obligatoires pour une instance d'un graphe basée sur le RNCG décrit en relation avec la Fie. 4. Le procédé de la Fig. 6 est utilisé dans la procédure d'apprentissage décrite en relation avec la Fig. 5, mais aussi, une fois l'apprentissage effectué, pour déterminer un ordre des noeuds obligatoires pour une 16 instance lors de l'étape 31. [0091] Dans une étape 3100, le module de traitement 10 obtient une instance courante à résoudre 4(So,Dc,M,). Lors de l'étape 503, l'instance courante /c. ( Se, D M r) = 1(5, D, M). Lors de l'étape 31, l'instance courante ( IR (S. R, DR, MR). [0092] Dans une étape 3101, le module de traitement 10 détermine si l'ensemble de noeuds obligatoires M c est vide. Si c'est le cas, l'étape 3101 est suivie d'une étape 3102 au cours de laquelle le module de traitement 10 génère une liste ordonnée .L RNcG vide et met lin à l'étape 503. [0093] Si l'ensemble de noeuds obligatoires M c n'est pas vide, le module de traitement 10 détermine lors d'une étape 3103, si l'ensemble de noeuds obligatoires Me contient un noeud obligatoire (Le. si le cardinal de l'ensemble de noeuds obligatoires Mc est égal « 1 »). Si l'ensemble de noeuds obligatoires Mc ne contient qu'un noeud obligatoire, le module de traitement 10 génère une liste ordonnée LOR.NjcG contenant uniquement ce noeud obligatoire et met fin à l'étape 503. [0094] Si l'ensemble de noeuds obligatoires M contient une pluralité de noeuds obli- gatoires, le module de traitement 10 initialise une instance temporaire ic(sc,d,,m,) à la valeur de l'instance courante I ( Se,D 31",) lors d'une étape 3105. [0095] Dans une étape 3106, le module de traitement 10 initialise une variable./ à l'unité. [0096] Dans une étape 3107, le module de traitement 10 applique le RNCG décrit en Fig. 4 à l'instance temporaire îc( s c, de,me). L'application du RNCG à l'instance temporaire i c (s c, tic, ) permet d'obtenir un vecteur de probabilité associant à chaque noeud du graphe G une valeur de probabilité. [0097] Dans une étape 3108, le module de traitement 10 détermine le noeud obligatoire 111 de l'ensemble de noeuds obligatoires c ayant la probabilité la plus élevée ci d'être le prochain noeud obligatoire à traverser à la suite du noeud de départ 5 c. Le module de traitement 10 insère alors le noeud obligatoire In dans la liste ordonnée L LOR ;\T c G des noeuds obligatoires dans une étape 3109. [0098] Dans une étape 3110, le module de traitement 10 donne au noeud de départ S c de l'instance temporaire î c (5 c, d c, mc) la valeur du noeud obligatoire 111 et retire le noeud obligatoire 111 de l'ensemble de noeuds obligatoires en c c [0099] Dans une étape 3111, le module de traitement 10 détermine si le nombre de noeuds obligatoires restant dans l'ensemble de noeuds obligatoires en c est égal à l'unité. Si 17 c'est le cas, le module de traitement 10 ajoute le noeud obligatoire restant à la fin de la liste ordonnée LORNcG dans une étape 3113. A cette étape, tous les noeuds obli- gatoires de l'instance IL ( Se, D ) apparaissent dans la liste ordonnée L 0 R\ico dans l'ordre proposé par le RNCG. La liste ordonnée L OR Nt, G est alors une information représentative d'un ordre de parcours de noeuds obligatoires de l'ensemble de noeuds obligatoires Mc de l'instance IL.(Se,D,,M,.). [0100] Si le nombre de noeuds obligatoires restant dans l'ensemble de noeuds obligatoires c est supérieur à l'unité, le module de traitement 10, incrémente la variable./ d'une unité lors d'une étape 3112 et retourne à l'étape 3107. Le module de traitement 10 repart donc avec une nouvelle instance ayant pour noeud de départ S c le noeud obligatoire m déterminé lors de l'itération précédente, pour noeud d'arrivée, le même noeud d que dans l'itération précédente et une liste de noeuds obligatoires identique à la précédente de laquelle a été supprimée M Li [0101] La Fig. 7 illustre schématiquement un exemple de procédure d'optimisation locale de l'ordre des noeuds obligatoires. La procédure de la Fig. 7 est donc une procédure d'optimisation locale. L'initialisation de cette procédure par un ordre de parcours de noeuds obligatoires obtenu par un réseau de neurones adapté au graphe G, permet d'obtenir quasiment systématiquement un ordre de parcours des noeuds obligatoires meilleur qu'en initialisant ladite procédure avec un ordre de parcours de noeuds obligatoires définis aléatoirement. [0102] La procédure d'optimisation locale de l'ordre des noeuds obligatoires est utilisée lors des étapes 505, 506 et 32. Cette procédure reçoit en entrée une instance eopt lls()}", DM'-',") et une liste ordonnée à optimiser L cyttt. [0103] Dans une étape 3200, le module de traitement 10 crée une liste ordonnée variable opt 10 [0104] Dans une étape 3201, le module de traitement 10 calcule un coût de transition global c or t du chemin entre le noeud de départ s'or et le noeud d'arrivée D "P de l'instance aléatoire "c't' t(s° P 1 Dar", Mc'P) en prenant en compte l'ordre des noeuds obligatoires de la liste ordonnée L 0 ()Pt. Le calcul du coût de transition global c Dr du chemin s'appuie sur le tableau précalculé TAB. [0105] Dans une étape 3202, le module de traitement 10 change l'ordre dans la liste ordonnée " 0 "PI et sauvegarde la liste ordonnée obtenue dans la liste ordonnée variable /0 c'r/. Lors de l'étape 3202, le module de traitement 10 détermine une paire d'éléments, dits éléments pivots, dans la liste ordonnée L 00Pt et intervertit les 18 éléments de la liste ordonnée L 00P situés entre les deux éléments pivots de manière symétrique. La paire d'éléments pivots déterminée est différente de toutes paires d'éléments pivots déjà utilisées pour la liste ordonnée L 0P e. A partir de la liste ordonnée L 00p t on obtient alors une liste ordonnée variable / 0 LIP f dans laquelle les éléments de la liste ordonnée L °PI situés entre les deux éléments pivots ont été intervertis symétriquement. [0106] Dans une étape 3203, le module de traitement 10 calcule un coût de transition global (7 e du chemin entre le noeud de départ s P et le noeud d'arrivée D"» de l'instance aléatoire i" P s P DaPI, maPt) en prenant en compte l'ordre des noeuds obligatoires de la liste ordonnée variable 7 C) P t obtenue lors de l'étape 0 3202. [0107] Dans une étape 3204, le module de traitement 10 compare le coût de transition global "P e au coût de transition global c t. Si c,6' P r REVENDICATIONSProcédé de définition d'un chemin à suivre par un véhicule dans un environnement représenté par un graphe de noeuds reliés par des arêtes, chaque noeud dudit graphe représentant une position pouvant être prise par ledit véhicule, chaque arête entre deux noeuds étant associée à un coût de transition entre les deux noeuds, caractérisé en ce qu'il comprend [Revendication 2] - obtenir (30) une instance dudit graphe, dite instance à résoudre, chaque instance étant représentée par un noeud de départ, un noeud d'arrivée et un ensemble de noeuds obligatoires par lesquels le véhicule doit passer, lesdits noeuds de départ, d' anivée et obligatoires formant les noeuds de l'instance à résoudre ; - obtenir (31) une information représentative d'un ordre initial de parcours desdits noeuds obligatoires en appliquant une procédure utilisant un réseau de neurones convolutif de graphe, dit RNCG, adapté audit graphe à ladite instance à résoudre ; - exécuter (32) une procédure d'optimisation locale de l'ordre des noeuds obligatoires afin d'obtenir un ordre des noeuds obligatoires optimisé, ladite procédure étant initialisée avec ladite information représentative de l'ordre initial ; - définir (33) un chemin pour ladite instance à résoudre à partir de l'ordre des noeuds obligatoires optimisé et pour chaque paire de noeuds de ladite instance à résoudre, d'un plus court chemin entre les noeuds de ladite paire. Procédé selon la revendication 1, caractérisé en ce que la procédure utilisant le RNCG est une procédure itérative prenant une instance du graphe en entrée, dite instance d'entrée et générant une information représentative d'un ordre initial de parcours des noeuds obligatoires de l'instance d'entrée en sortie, dite information de sortie, et comprenant à chaque itération: - appliquer (3107) le RNCG à ladite instance d'entrée afin d'obtenir pour chaque noeud du graphe une valeur représentative d'une probabilité d'être le prochain noeud obligatoire à traverser à la suite du noeud de départ de l'instance d'entrée ; - identifier (3108) le noeud obligatoire de l'ensemble de noeuds obligatoires de l'instance d'entrée possédant la probabilité la plus élevée ; - insérer (3109) le noeud obligatoire identifié clans une liste ordonnée de 20 [Revendication 3] noeuds obligatoires ; - remplacer (3110) le noeud de départ de l'instance d'entrée par le noeud obligatoire identifié et retirer le noeud obligatoire identifié de l'ensemble de noeuds obligatoires de l'instance d'entrée ; - les itérations prenant fin lorsqu'un nombre de noeuds dans l'ensemble de noeuds obligatoires de l'instance d'entrée est égal à un, le noeud obligatoire restant dans l'ensemble de noeuds obligatoires de l'instance d'entrée étant inséré dans ladite liste ordonnée et ladite liste ordonnée formant l'information de sortie. Procédé selon la revendication 1 ou 2, caractérisé en ce que la procédure d'optimisation locale de l'ordre des noeuds obligatoires est une procédure itérative prenant une instance, dite instance initiale, et une information représentative d'un ordre de noeuds obligatoires, dit ordre initial, en entrée et générant une information représentative d'un ordre de noeuds obligatoires optimisé en sortie, dit ordre optimisé, - chaque information représentative d'un ordre de noeuds obligatoires étant une liste de noeuds obligatoires ordonnés, et comprend à chaque itération : - déterminer (3202) une paire de noeuds obligatoires, dits noeuds pivots, parmi les noeuds obligatoires de la liste de noeuds obligatoires ordonnée de l'ordre initial, dite liste initiale, et obtenir une liste de noeuds obligatoires ordonnée modifiée, dite liste modifiée, dans laquelle les noeuds obligatoires de la liste initiale situés entre les deux noeuds pivots ont été intervertis symétriquement, la paire de noeuds pivots déterminée étant différente de toutes paires de noeuds pivots déjà utilisées pour modifier l'ordre des noeuds obligatoires dans la liste initiale ; - définir (3204) une information représentative de l'ordre des noeuds obligatoires dans la liste modifiée comme étant un ordre optimisé temporaire lorsqu'un coût de transition global (3203) d'un chemin entre les noeuds de départ et d'arrivée de l'instance initiale en suivant l'ordre des noeuds obligatoires dans la liste modifiée est inférieur à un coût de transition global dudit chemin en suivant l'ordre des noeuds obligatoires dans la liste initiale; et définir (3206) l'ordre optimisé temporaire comme étant l'ordre initial ; et, - mettre fin (3207) aux itérations de la procédure d'optimisation locale lorsqu'une condition d'arrêt est remplie (3205), l'ordre optimisé étant le dernier ordre optimisé temporaire obtenu par la procédure d'optimisation locale. 21 [Revendication 4] Procédé selon la revendication 1, 2 ou 3, caractérisé en ce que le RNCG a été adapté audit graphe lors d'une phase préalable d'adaptation, la phase préalable d'adaptation comprenant une procédure d'apprentissage permettant d'adapter des paramètres d'une phase de convolution et d'une phase dc combinaison linéaire dudit RNCG, dits paramètres du RNCG, la procédure d'apprentissage étant une procédure itérative comprenant à chaque itération : - générer (502) une instance aléatoire du graphe ; - appliquer (503) la procédure utilisant le RNCG à l'instance aléatoire afin d'obtenir une première information représentative d'un ordre des noeuds obligatoires de l'instance aléatoire, dite première information ; - générer (504) une deuxième information représentative d'un ordre des noeuds obligatoires de l'instance aléatoire défini aléatoirement, dite deuxième information ; - obtenir une première et une deuxième informations représentatives d'un ordre des noeuds obligatoires optimisées, dites première et deuxième informations optimisées, en appliquant la procédure d'optimisation locale respectivement à l'ordre des noeuds obligatoires correspondant à la première et à la deuxième informations ; - sélectionner (507, 508, 509) l'ordre représenté par ladite première ou par ladite deuxième information optimisée permettant de minimiser un coût de transition global d'un chemin entre les noeuds de départ et d'arrivée de l'instance aléatoire ; - former une nouvelle instance à partir de chaque noeud obligatoire de l'instance aléatoire, chaque nouvelle instance ayant pour noeud de départ le noeud obligatoire correspondant à la nouvelle instance, pour noeud d'arrivée le noeud d'arrivée de l'instance aléatoire et pour ensemble de noeuds obligatoires, les noeuds suivant le noeud obligatoire utilisé comme noeud de départ de la nouvelle instance dans l'ordre sélectionné ; et pour l'instance aléatoire et chaque nouvelle instance, former un couple en associant ladite instance à un prochain noeud obligatoire à traverser pour ladite instance, ledit prochain noeud obligatoire à traverser étant le noeud obligatoire suivant le noeud de départ de ladite instance dans l'ordre sélectionné ; - mettre à jour une fenêtre d'apprentissage avec les couples ainsi formés ; - faire évoluer les paramètres du RNCG pour minimiser une erreur de prédiction par le RNCG d'un prochain noeud obligatoire à traverser en [Revendication 5] utilisant le prochain noeud obligatoire de couples de la fenêtre d'apprentissage comme référence de prochains noeuds obligatoires à traverser à obtenir par le RNCG. Dispositif pour définir un chemin à suivre par un véhicule dans un environnement représenté par un graphe de noeuds reliés par des arêtes, chaque noeud dudit graphe représentant une position pouvant être prise par ledit véhicule, chaque arête entre deux noeuds étant associée à un coût de transition entre les deux noeuds, caractérisé en ce qu'il comprend [Revendication 6] [Revendication 7] [Revendication 8] - des moyens d'obtention pour obtenir (30) une instance dudit graphe, dite instance à résoudre, chaque instance étant représentée par un noeud de départ, un noeud d'arrivée et un ensemble de noeuds obligatoires par lesquels le véhicule doit passer, lesdits noeuds de départ, d'arrivée et obligatoires formant les noeuds de l'instance à résoudre ; - des moyens d'obtention pour obtenir (31) une information représentative d'un ordre initial de parcours desdits noeuds obligatoires en appliquant une procédure utilisant un réseau de neurones convolutif de graphe, dit RNCG, adapté audit graphe à ladite instance à résoudre ; - des moyens d'exécution pour exécuter (32) une procédure d'optimisation locale de l'ordre des noeuds obligatoires afin d'obtenir un ordre des noeuds obligatoires optimisé, ladite procédure étant initialisée avec ladite information représentative de l'ordre initial ; - des moyens de définition pour définir (33) un chemin pour ladite instance à résoudre à partir de l'ordre des noeuds obligatoires optimisé et pour chaque paire de noeuds de ladite instance à résoudre, d'un plus court chemin entre les noeuds de ladite paire. Véhicule comprenant un dispositif selon la revendication 5. Programme d'ordinateur, caractérisé en ce qu'il comprend des instructions pour mettre en oeuvre, par un dispositif, le procédé selon l'une quelconque des revendications 1 à 4, lorsque ledit programme est exécuté par un processeur dudit dispositif. Moyens de stockage, caractérisés en ce qu'ils stockent un programme d'ordinateur comprenant des instructions pour exécuter, par un dispositif, le procédé selon l'une quelconque des revendications 1 à 4, lorsque ledit programme est exécuté par un processeur dudit dispositif