FR 3096637 A1 20201204 FR 1905555 A 20190527 Description Titre de l'invention : Procédé et dispositif de détermination d'un chemin pour un véhicule autonome Domaine technique [0001] L'invention concerne un procédé et un dispositif de détermination d'un chemin pour véhicule autonome. L'invention concerne plus particulièrement un procédé et un dispositif de détermination d'un nouveau chemin pour contourner un obstacle détecté sur un chemin établi précédemment. Arrière-plan technologique [0002] Avec le développement des véhicules autonomes, des besoins en termes de plani- fication du chemin à suivre en fonction de la géométrie de la route et de l'espace libre sont apparus. [0003] Différentes méthodes de planification de trajectoire pour véhicules autonomes ont été présentées, par exemple dans une étude de 2018 intitulée « Planning and DecisionMaking for Autonomous Vehicles » de Wilko Schwarting, Javier Alonso-Mora et Daniela Rus ou encore dans une étude de 2017 intitulée « Perception, Planning, Control and Coordination for Autonomous Vehicles » de Pendleton et al. [0004] Les méthodes de planification détaillées dans les études mentionnées ci-dessus sont classées en 3 catégories, à savoir : [0005] - les méthodes à base de discrétisation (souvent de l'espace), aussi appelées méthodes combinatoires, ces méthodes reposant sur l'utilisation d'algorithmes de parcours d'arbres ou de graphes ; [0006] - les méthodes à base d'exploration probabiliste de l'espace, aussi appelées méthodes à échantillonnage ; [0007] - les méthodes à base d'optimisation et d'horizon glissant (de type « Model Predictive Control » ou en français « commande prédictive basée model ») incluant les méthodes à base d'interpolation. [0008] Les méthodes de planification de chemin à base de discrétisation de l'espace sont gé- néralement associées à une planification globale et ne permettent alors pas la précision spatiale nécessaire à l'évitement d'un obstacle en environnement réduit. De plus, elles ne sont pas directement adaptées à la prise en compte de contraintes technologiques associées au véhicule (par exemple la valeur maximale de l'angle au volant ou encore la vitesse de braquage). [0009] Les méthodes de planification de chemin à base d'échantillonnage aléatoire de l'espace ne garantissent pas l'obtention d'un chemin optimal respectant les contraintes, dans un temps donné, limitant leur mise en oeuvre pour des applications temps réel. 2 100101 Les méthodes de planification de chemin à base d'optimisation et horizon glissant nécessitent une forte capacité calculatoire également, limitant leur mise en oeuvre pour des applications temps réel. [0011] Selon ces méthodes de l'état de l'art, les contraintes temps réels sont souvent incom- patibles avec la prise en compte des contraintes véhicules par la difficulté de les modéliser sous une forme adaptée à la résolution du problème en temps réel. Résumé de l'invention [0012] Un objet de la présente invention est de résoudre le problème de l'évitement d'un obstacle statique par un véhicule autonome avec la détermination d'un nouveau chemin en temps réel. [0013] Selon un premier aspect, l'invention concerne un procédé de détermination d'un chemin pour un véhicule autonome, le procédé comprenant : [0014] - réception de premiers paramètres représentatifs d'un premier chemin dans un repère absolu ; [0015] - réception de données représentatives d'un obstacle détecté le long du premier chemin, les données étant exprimées dans un repère associé à l'obstacle ; [0016] - détermination de deuxièmes paramètres représentatif du premier chemin dans le repère de l'obstacle à partir des premiers paramètres ; [0017] - détermination de la présence d'un conflit entre l'obstacle et le premier chemin en fonction des données représentatives de l'obstacle, de données représentatives de dimensions du véhicule autonome et des deuxièmes paramètres ; [0018] - détermination de deux points d'un deuxième chemin contournant l'obstacle, les deux points étant déterminés en fonction des données représentative de dimensions du véhicule autonome et de la largeur de l'obstacle de manière à être situés à une distance latérale minimale de l'obstacle ; [0019] - détermination d'un point de départ du deuxième chemin, le point de départ cor- respondant au point du premier chemin pour lequel l'angle de braquage pour atteindre un premier point parmi les deux points est minimal le long du deuxième chemin ; [0020] - détermination de troisièmes paramètres représentatifs du deuxième chemin à partir d'une pluralité de courbes paramétriques polynomiales d'au moins le troisième ordre continues aux deux points et passant par les deux points. [0021] Selon une variante, la détermination de la présence d'un conflit comprend la déter- mination de la position relative de l'obstacle vis-à-vis du premier chemin dans le repère de l'obstacle, la détermination du sens d'un virage formé par le premier chemin au niveau de l'obstacle, la détermination de la présence d'un conflit dépendant de la position relative et du sens du virage. [0022] Selon une autre variante, la détermination de la présence d'un conflit comprend en 3 outre la comparaison de l'empreinte du véhicule sur le premier chemin avec l'empreinte de l'obstacle, l'empreinte du véhicule étant décrite avec une enveloppe supérieure et une enveloppe inférieure chacune décrite par deux points du véhicule autonome dépendant du sens du virage. [0023] Selon encore une variante, la détermination du point de départ comprend la déter- mination d'une variable spatiale pour laquelle le deuxième chemin débute, la détermination de la variable spatiale correspondant au point de départ comprenant les étapes de : [0024] - détermination d'un intervalle auquel appartient ladite variable spatiale, l'intervalle étant borné par une position minimale sur le premier chemin correspondant à l'instant de réception des données représentatives d'un obstacle et par une position maximale sur le premier chemin correspondant à la position où le véhicule autonome atteint un point d'abscisse X égale à (-(1-PAF,a)-10,) dans le repère de l'obstacle, où] correspond à la longueur du véhicule autonome, PAF', correspond à la longueur du porte-à-faux arrière du véhicule autonome et correspond à la longueur de l'obstacle ; [0025] - détermination de ladite variable spatiale comme correspondant à la position mi- nimisant l'écart entre le lacet du deuxième chemin au point de départ et un lacet idéal du deuxième chemin permettant d'éviter l'obstacle, le lacet idéal correspondant à un angle formé par un vecteur colinéaire à l'axe des abscisses du repère de l'obstacle et un vecteur colinéaire à une droite passant par le centre de l'essieu arrière du véhicule et le premier point parmi les deux points et orientée du centre vers le premier point. [0026] Selon une variante supplémentaire, la pluralité de courbes paramétriques poly- nomiales d'au moins le troisième ordre comprend : [0027] - trois courbes de Bézier cubiques ; ou [0028] - deux courbes de Bézier cubiques et une courbe de Bézier d'ordre 4. [0029] Selon encore une variante, les données représentatives de dimensions du véhicule autonome comprennent la longueur du véhicule autonome, la largeur du véhicule autonome et la longueur du porte-à-faux arrière du véhicule autonome. [0030] Selon une variante supplémentaire, la détermination des deuxièmes paramètres repré- sentatif du premier chemin dans le repère de l'obstacle est réalisée à partir des premiers paramètres représentatifs du premier chemin non parcouru par le véhicule autonome à la réception de données représentatives de l'obstacle détecté. [0031] Selon un deuxième aspect, l'invention concerne un dispositif de détermination d'un chemin pour un véhicule autonome, le dispositif comprenant une mémoire associée à au moins processeur configuré pour la mise en oeuvre des étapes du procédé tel que décrit ci-dessus selon le premier aspect de l'invention. [0032] Selon un troisième aspect, l'invention concerne un véhicule, par exemple de type au- tomobile, comprenant un dispositif tel que décrit ci-dessus selon le deuxième aspect de l'invention. [0033] Selon un quatrième aspect, l'invention concerne un programme d'ordinateur qui comporte des instructions adaptées pour l'exécution des étapes du procédé selon le premier aspect de l'invention, ceci notamment lorsque le programme d'ordinateur est exécuté par au moins un processeur. [0034] Un tel programme d'ordinateur peut utiliser n'importe quel langage de pro- grammation, et être sous la forme d'un code source, d'un code objet, ou d'un code intermédiaire entre un code source et un code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. [0035] Selon un cinquième aspect, l'invention concerne un support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé selon le premier aspect de l' invention. [0036] D'une part, le support d'enregistrement peut être n'importe quel entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une mémoire ROM, un CD-ROM ou une mémoire ROM de type circuit rnicroélectronique, ou encore un moyen d'enregistrement magnétique ou un disque dur. [0037] D'autre part, ce support d'enregistrement peut également être un support trans- missible tel qu'un signal électrique ou optique, un tel signal pouvant être acheminé via un câble électrique ou optique, par radio classique ou hertzienne ou par faisceau laser autodirigé ou par d'autres moyens. Le programme d'ordinateur selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. [0038] Alternativement, le support d'enregistrement peut être un circuit intégré dans lequel le programme d'ordinateur est incorporé, le circuit intégré étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. Brève description des figures [0039] D'autres caractéristiques et avantages de l'invention ressortiront de la description des modes de réalisation non limitatifs de l'invention ci-après, en référence aux figures 1 à 10 annexées, sur lesquelles : [0040] [fig.1] illustre de façon schématique un véhicule autonome sur un premier chemin comprenant un obstacle, selon un exemple de réalisation particulier de la présente invention ; [0041] [fig.2] illustre de façon schématique une modélisation du véhicule autonome de la figure 1, selon un exemple de réalisation particulier de la présente invention ; [0042] [fig.3] illustre un organigramme des différentes étapes d'un procédé de détermination d'un chemin pour le véhicule autonome de la figure 1, selon un exemple de réalisation particulier de la présente invention ; [0043] [fig.4] illustre de façon schématique la définition du repère associé à l'obstacle de la figure 1, selon un exemple de réalisation particulier de la présente invention ; [0044] [fig.5] illustre de façon schématique un obstacle localisé à droite du premier chemin de la figure 1, selon un premier exemple de réalisation particulier de la présente invention ; [0045] [fig.6] illustre de façon schématique un obstacle localisé à droite du premier chemin de la figure 1, selon un deuxième exemple de réalisation particulier de la présente invention ; [0046] [fig.7] illustre de façon schématique un obstacle localisé à gauche du premier chemin de la figure 1, selon un premier exemple de réalisation particulier de la présente invention ; [0047] [fig.8] illustre de façon schématique un obstacle localisé à gauche du premier chemin de la figure 1, selon un deuxième exemple de réalisation particulier de la présente invention ; [0048] [fig.9] illustre de façon schématique la détermination d'un début de deuxième chemin contournant l'obstacle de la figure 1, selon un exemple de réalisation particulier de la présente invention ; [0049] [fig.10] illustre de façon schématique un dispositif de détermination d'un chemin pour le véhicule autonome de la figure 1, selon un exemple de réalisation particulier de la présente invention. Description des modes de réalisation [0050] Un procédé et un dispositif de détermination d'un chemin pour véhicule autonome vont maintenant être décrits dans cc qui va suivre en référence conjointement aux figures 1 à 10. Des mêmes éléments sont identifiés avec des mêmes signes de référence tout au long de la description qui va suivre. [0051] Selon un exemple particulier et non limitatif de réalisation de l'invention, un procédé de détermination d'un chemin pour le véhicule autonome comprend la réception de premiers paramètres représentatif d'un premier chemin, aussi appelé chemin de référence, dans un repère absolu. Ces premiers paramètres correspondent par exemple en des points de contrôle du premier chemin définis par une courbe polynomiale de 3 'me ordre, par exemple une courbe de Bézier cubique. Ces premiers paramètres sont issus d'une première planification selon par exemple une méthode de l'état de l'art, par exemple une méthode par interpolation. Ces points de contrôle sont par exemple définis par un indice pour chaque point avec un jeu de coordonnées X et Y dans un repère absolu. Des données représentatives d'un obstacle détecté le long du premier chemin sont également reçues, ces données étant exprimées dans un repère associé à 6 l'obstacle. Ces données sont par exemple reçues d'un modèle de l'obstacle généré à partir de données capturées par un dispositif de détection d'obstacle, par exemple un lidar. Des deuxièmes paramètres représentatif du premier chemin dans le repère de l'obstacle sont obtenus à partir des premiers paramètres, les deuxièmes paramètres correspondant aux points de contrôle du premier chemin exprimés dans le repère de l'obstacle. La présence d'un conflit, entre l'obstacle et le premier chemin est déterminé en fonction des données représentatives de l'obstacle, de données représentatives de dimensions du véhicule autonome et des deuxièmes paramètres du premier chemin. Deux points d'un deuxième chemin contournant l'obstacle sont déterminés en fonction des données représentative de dimensions du véhicule autonome et de la largeur de l'obstacle, les deux points étant déterminés de manière à être situés à une distance latérale minimale de l'obstacle. Un point de départ du deuxième chemin contournant l'obstacle est déterminé. Ce point de départ correspond au point du premier chemin pour lequel l'angle de braquage pour atteindre un premier point parmi les deux points déterminés précédemment est minimal le long du deuxième chemin. Enfin, des troisièmes paramètres représentatifs du deuxième chemin sont déterminés à partir de plusieurs courbes paramétriques polynomiales de 3s0e ordre ou plus, ces courbes étant continues aux deux points et passant par les deux points. Ces troisièmes paramètres correspondent en des points de contrôle chacun défini par un indice et des coordonnées X, Y. [0052] La détermination d'un deuxième chemin permet au véhicule autonome de contourner un obstacle détecté le long d'un premier chemin préalablement calculé. La détermination du deuxième chemin étant fonction du premier chemin, de dimensions propres au véhicule et à l'obstacle, la solution proposée permet de générer le chemin le plus proche du chemin initialement planifié, garantissant l'évitement de l'obstacle, tout en minimisant la modification de l'empreinte au sol du véhicule sur le chemin. Définitions [0053] Chemin [0054] Un chemin C ' ( P r, T in in, rmax) est défini comme l'association d'une fonction p r F FR2 d'un scalaire réel 7- EL [ T min' T 1,» a x appelée variable spatiale, et des bornes de son domaine de variation T en tn et T rn ax, [0055] Les coordonnées de P-,- représentent alors les coordonnées d'un point dans un ré- férentiel ( G ) terrestre fixe (repère galiléen fixé à la terre et considéré comme invariant, la surface étant supposée plane), encore appelé repère global ou absolu. Sous cette forme, un chemin est alors également défini par deux fonctions X r(T ) et Yr -t- ) du même scalaire réel T , de telle sorte que [0056] 7 [Math.1] p (7. = X ( ) [Y, (-t- )1 [0057] La vitesse spatiale V ( T ) associée à un chemin C - (pT, r in in, r in ax) est définie comme étant la norme de la dérivée de pi_ ) par rapport à la variable spatiale du chemin considéré : [0058] [Math.2] Vr(r) (T) dT [0059] ou encore, en utilisant la notation de la relation 1, [0060] [Math.3] Y1(r) = ) )2 (cntà-,(-1-) )2 [0061] 11 s'agirait de la vitesse du point Pr si la variable spatiale r était le temps. [0062] L'empreinte e(C) d'un chemin C ID r ni in, r max) est définie comme l'ensemble des points P r (r ) parcouru sur le chemin, c'est-à-dire [0063] [Math.4] e(C) = ( ), r min "±:---r Tinox [0064] Il peut être remarqué qu'une même empreinte de chemin e peut être associée à une infinité de chemins : toute fonction g : -> DR strictement croissante peut en effet permettre de redéfinir l'empreinte du chemin e(c) où C : Tmin, T in a x ) , par utilisation d'un chemin C_( pr ;pi ax \ de même empreinte e( [0065] grâce à la relation [0066] [Math.5] = g ( ) [0067] Dans ce cas, [0068] [Math.63] Pr (T iT(g(T)) 100691 c'est-à-dire 100701 IMath.71 P, = Pr. og [0071] [Math.8] r ni in (T rn i [0072] et [0073] c ) =e(c), 8 [Math.9] ?TI tlX = g (1.- m tl x 100741 Afin de garantir que T 1-71 i n ( U2) = U2(1- rspiit) T st> 1 ir permet un changement de variable qui montre que P 1i2 = P r(f 2( U2), c'est-à dire que P[T,(U,) Py( ) e [0,11 et V T Ersplit, [0157] [fig.1] illustre schématiquement un obstacle 11 le long d'un premier chemin 101 suivi par un véhicule autonome 10, selon un exemple de réalisation particulier et non limitatif de la présente invention. [0158] La figure 1 illustre la planification d'un deuxième chemin 102 pour contourner lo- calement un obstacle 11 situé le long d'un premier chemin 101. L'obstacle 11 correspond par exemple à un véhicule stationné sur une portion de route correspondant à une partie du premier chemin 101. Pour éviter toute collision avec l'obstacle 11, un deuxième chemin 102 est replanifié pour éviter cet obstacle 11. [0159] Lc véhicule autonome 10 correspond à un véhicule équipé d'un système d'aide à la conduite abouti assurant le contrôle du véhicule qui est apte à rouler dans son environnement routier sans intervention du conducteur. Pour ce faire, un premier chemin est planifié, par exemple dans le système d'aide à la conduite du véhicule, en fonction d'instructions du conducteur (par exemple la destination). Lc premier chemin est planifié en utilisant toute méthode connue de l'homme du métier, par exemple une des méthodes décrites dans l'étude de 2018 intitulée « Planning and Dccision-Making for Autonomous Vehicles » de Wilko Schwarting, :ravier Alonso-Mora et Danicla Rus ou dans l'étude de 2017 intitulée « Perception, Phuming, Control and Coordination for Autonomous Vehicles » de Pendleton et al. [0160] Selon une variante, le premier chemin est déterminé par un serveur distant (par exemple au « cloud » ou « nuage » en français) auquel le véhicule autonome 10 est relié via une liaison sans fil, par exemple via une liaison LTE 4G ou 5G. Le véhicule 14 autonome 10 reçoit ainsi un ensemble de premiers paramètres (par exemple un ensemble de premiers points de contrôle) décrivant le premier chemin. [0161] L'obstacle 11 est par exemple détecté par un système embarqué dans le véhicule autonome 10, par exemple via un capteur de type lidar (de l'anglais « Light Detection And Ranging », ou « Détection et estimation de la distance par la lumière » en français) ou via une ou plusieurs caméras (associées à un capteur de profondeur selon une variante), l'obstacle étant alors déterminé par analyse des images acquises par la ou les caméras. [0162] Selon un autre exemple, la détection de l'obstacle est réalisée par un autre véhicule situé dans l'environnement du véhicule autonome. Les données relatives à l'obstacle 11 (localisation, données géométriques) sont alors transmises au véhicule autonome 10 via une liaison sans fil entre les 2 véhicules dans le cadre d'une communication véhicule à véhicule V2V (de l'anglais « vehicle-to-vehicle »), ou par l'intermédiaire d'une infrastructure mise en place dans le cadre d'une communication véhicule à infrastructure V2I (de l'anglais « vehicle-to-infrastructure »), dans le cadre d'une infrastructure réseau utilisant des technologies de communication telles que l'ITS G5 (de l'anglais « Intelligent Transportation System G5 » ou en français « Système de transport intelligent G5 ») en Europe ou DSRC (de l'anglais « Dedicated Short Range Communications » ou en français « Communications dédiées à courte portée ») aux Etats-Unis d'Amérique qui reposent tous les deux sur le standard IEEE 802.11p ou encore la technologie basée sur les réseaux cellulaires nommée C-V2X (de l'anglais « Cellular - Vehicle to Everything » ou en français « Cellulaire - Véhicule vers tout ») qui s'appuie sur la 4G basé sur LTE (de l'anglais « Long Term Evolution » ou en français « Evolution à long terme ») et bientôt la 5G. [0163] Le deuxième chemin 102 est déterminé par exemple par un ou plusieurs calculateurs ad hoc du système embarqué du véhicule autonome, en temps réel, pour éviter l'obstacle 11. La détermination de ce deuxième chemin est décrite plus en détail dans ce qui va suivre. [0164] [fig.2] illustre schématiquement un modèle 20 du véhicule autonome 10, selon un exemple de réalisation particulier et non limitatif de la présente invention. [0165] Afin d'évaluer l'atteignabilité d'un chemin, un modèle cinématique non linéaire 20 du véhicule autonome est utilisé. L'atteignabilité désigne ici la possibilité que le chemin puisse être suivi par le véhicule (autonome ou non). Ce modèle cinématique permet d'évaluer le lacet e .,. T) et le braquage (Ir ' i (r ) en fonction du chemin suivi par le véhicule. Ces grandeurs peuvent être exprimées en fonction des coordonnées de l'essieu arrière P r ^, ,T ) ^ = X._ (T) et de ses dérivées conformément à la théorie [ YT(T) de la platitude. [0166] Sous l'hypothèse de roulement sans glissement (RSG), la vitesse de l'essieu arrière ( ) est alors parallèle à la direction du véhicule ( ( ) et la vitesse de l'essieu avant ( ) est quant à elle parallèle à la direction des roues avant. [0167] Le roulement sans glissement signifie qu'il est considéré qu'il n'y a pas de mouvement de translation entre la roue et la route. Cc mouvement de translation apparait lorsque les taux de glissement des roues du véhicule sont trop importants, c'est-à-dire lors de fortes accélérations, et/ou lorsque les angles de dérives deviennent importants, c'est-à-dire lorsque l'adhérence diminue (verglas, route mouillée). [0168] L'hypothèse RSG est notamment justifiée par : [0169] - le fait que la vitesse du véhicule est faible (par exemple vitesse inférieure à 50 km/ h). En effet, le taux de glissement étant proportionnel (en valeur absolue) à la vitesse du véhicule, le taux de glissement est lui-même négligeable, [0170] - le fait que les accélérations sont supposées modérées, notamment dans les envi- ronnements urbains, [0171] - et le fait que les conditions d'adhérence restent suffisantes, de telle sorte que le co- efficient d'adhérence reste proche de 1. [0172] Par conséquent, il est possible (l'exprimer les relations liant e ) et le braquage r(r ) aux coordonnées de l'essieu arrière et à leurs vitesses et accélérations : [0173] [Math.34] d Y Ter ) I d r tan ( 9 .r(r )) dXr(r)/ dr [0174] et [0175] [Math.35] tan ( q9 ( r ))- d. der(r) [0176] où d est l'empattement, Gin [0177] [Math.36] V (r) ti~T(r) _ y (d XX' r) ± Y(i- )\2 d r 101781 conformément à la relation 3, et 101791 IMath.371 de r(r) d r crY T(r ) dXr(r) r(r) d2X (r) dr 2 ci - d r 6172 f d Y r(r ) )2 t dr I (dYcir(r ) ) 2 16 [0180] d'où [0181] [Math.38] ti2Yr(r) dX,(r)d17,(r) oi2X,(r) f) tan ( ) -d dr 2 tirdr d y dX,(r ))2 (dYr( T )2 ) k tir tir p1821 Ces relations sont utilisées pour exprimer les coordonnées de quatre points par- ticuliers A, B, Cet D du polytope modélisant le véhicule 10. Ces points sont également exprimés en fonction des coordonnées de l'essieu arrière conformément à la figure 2. [0183] On obtient alors les relations : [01 84] [Math.39] X4s Jr) Xr(r) (1-PAF',)cos (61-'(r)) -4sin (e (T)) X ti, Jr)) C, r(r) X D, r(r) Xy(T) XT(r) (1-PAF,)cos (O (r)) (0,(7)) Xr(r) 0 Tsin (91(T)) 0 (e T(T)) 1-2-e°s (13 T [0187] avec 1 la longueur du véhicule, L la largeur du véhicule et PA Fcir le porte à faux arrière (distance entre l'arrière du véhicule et le milieu de l'essieu arrière). [0188] Il peut être montré que la surface balayée par le véhicule le long d'un chemin est celle balayée par les points A , B,C et D. Ainsi, si ces 4 points restent dans une zone libre de tout obstacle statique, l'ensemble du véhicule reste dans une zone libre et il ne peut pas avoir de collision avec un obstacle statique tel que l'obstacle 11 de la figure 1. [0189] Il est possible de réduire la complexité calculatoire en s'intéressant à l'expression du gabarit de chemin décrit par le véhicule lorsque ce dernier tourne à une intersection. Ce gabarit est formé d'une enveloppe supérieure et d'une enveloppe inférieure. Il est possible de montrer que la borne supérieure Pe (r ) =[Xexi(r ) I est [ Yex et- ) décrite par le point situé à l'extrémité avant du véhicule et à l'extérieur du virage soit le point A lorsque le véhicule tourne à droite ou le point B si le véhicule tourne à [0185] Et [0186] [Math.401 Y*, (r) YE,r(r) T ) T ) (1-PAFar)sin(61,(T)) (1-PAF')sin (0,(r)) 0 1cos (er(T)) -4cos (ey(T)) -5-cos (6 (r)) 17 (r X1,,t(r ) est Yint(r gauche. De la même manière, la borne inférieure Pi décrite par le point situé à l'extrémité de l'essieu arrière et à l'intérieur du virage soit le point C lorsque le véhicule tourne à droite ou le point D si le véhicule tourne à gauche. [0190] [fig.3] illustre un organigramme des différentes étapes d'un procédé de détermination d'un chemin pour véhicule autonome 10, selon un exemple de réalisation particulier et non limitatif de la présente invention. Le procédé est par exemple mis en oeuvre par le dispositif 10 de la figure 10. [0191] Dans une première étape 31, des prcmicrs paramètres représentatifs d'un premier chemin, aussi appelé chemin de référence, sont reçus. Ces premiers paramètres sont exprimés dans un repère absolu (aussi appelé repère monde ou repère terrestre fixe). Ces prcmicrs paramètres correspondent par exemple en des points de contrôle du premier chemin défini par une courbe paramétrique polynomiale de troisième ordre, par exemple une courbe de Bézicr cubique ou une courbe de B-splinc ou NURBS (de l'anglais « Non-Uniform Rational Basis Splines » ou en français « B-splincs rationnelles non uniformes »). Ces premiers paramètres sont issus d'une première planification selon par exemple une méthode de l'état (le l'art, par exemple une méthode par interpolation. [0192] Dans une deuxième étape 32, des données représentatives d'un obstacle détecté le long du premier chemin sont reçues, ces données étant exprimées dans un repère associé à l'obstacle. Ces données sont par exemple reçues d'un ou plusieurs capteurs (par exemple Lidar) ou d'un autre véhicule. Les données correspondent par exemple à des données issues de la modélisation de l'obstacle, par exemple sous la forme d'une boîte englobante (de l'anglais « bounding box »). Cette représentation ou modélisation correspond au plus petit rectangle contenant l'obstacle. Dans ce qui va suivre, ce rectangle représentant. l'obstacle sera défini par son centre géométrique G ainsi que par sa longueur t 0 b s et sa largeur L 0 bs. [0193] Dans une troisième étape 33, des deuxièmes paramètres représentatifs du premier chemin dans le repère de l'obstacle sont obtenus à partir des premiers paramètres. Les deuxièmes paramètres correspondant aux points de contrôle du premier chemin exprimés dans le repère de l'obstacle. Cette troisième étape 33 correspond à une reparamétrisation du premier chemin dans le repère associé à l'obstacle, telle qu'illustré en figure 4. [0194] [fig.4] illustre selon un exemple particulier et non limitatif de l'invention la re- paramétrisation du premier chemin (ou au moins la partie du premier chemin 101 non parcourue par le véhicule autonome au moment de la détection de l'obstacle). 18 [0195] Un repère lié à l'obstacle est défini. Cc repère a pour origine le centre géométrique de la représentation de l'obstacle 11 et est défini par le vecteur unitaire , de direction le côté de l'obstacle 11 de même sens que le premier chemin 101, ainsi que par le vecteur unitaire , tels que ( x0 b , ) forment une base directe. Le sens du premier chemin est ici défini par P s t'r tP end le sens de Xobs peut alors être défini tel que X0 1, s . P ,r,'rP ,,,,,r > O. L'angle e , ,., , est l'angle entre le repère obstacle et le repère absolu conformément à la figure 4. [0196] Soit un vecteur quelconque de coordonnées X dans le repère absolu. Les co- [ Y [ X0 I'. 1 I. Y 0 b s .1 _ cos (6 ' h ,) sin (0 ois) [ x .1 i Y i _ Px, Ob S P y, 0 h 8 - sin (0 c -, h) cos (9 'I, s) [0198] dl Px. 0 bs = 0 G .X et P3,obs= 0 G .1" - [0199] Ainsi la transformation homogène permettant de passer du repère absolu au repère obstacle est la combinaison d'une translation de vecteur O G et d'une rotation d'angle e 0 ,, s . La transformation étant homogène, le calcul dans le repère obstacle du lacet et de l'angle de braquage se fait toujours par le biais des équations 3 et 5. Cependant, il est important de noter que ces grandeurs exprimées dans le repère obstacle sont des grandeurs relatives. Dans le reste de la description, les équations ( = (1 seront écrites dans le repère obstacle c'est-à-dire que P T ) X T T) sera [Yr(r) toujours exprimé dans le repère obstacle. 102001 Dans une quatrième étape 34, la présence d'un conflit entre l'obstacle 11 et le premier chemin 101 est déterminé en fonction des données représentatives de l'obstacle, de données représentatives de dimensions du véhicule autonome 10 et des deuxièmes paramètres du premier chemin 101. 102011 Afin de détecter la présence d'un conflit, il est nécessaire de connaître la position relative de l'obstacle 11 vis à vis du premier chemin 101. En effet, la détection d'un éventuel conflit avec l'obstacle 11 dépend du type de manoeuvre effectuée par le véhicule autonome 10 (ou du sens du virage) ainsi que la position relative de l'obstacle 11 par rapport au premier chemin 101. 4 cas de figure se présentent, illustrés respectivement en regard des figures 5, 6, 7 et 8 selon des exemples particuliers et non li- ordonnées X , I, s de ce vecteur clans le repère obstacle s'expriment par le biais de [ Yohs la matrice de rotatioi de la manière suivante : 101971 1Math.411 19 mitatifs de l'invention. [0202] [fig.5] illustre de façon schématique un obstacle 11 localisé à droite du premier chemin 101 avec un virage à droite. Soit 7 0 tel que X Ter 0) '= si Y (r 0) > (7) alors l'obstacle 11 est situé sur la droite du premier chemin 101. [0203] Soit : [0204] [Math.42[ T obsint. tel que [Math.42] Xin (1- X obsinf [0205] [Math.43] lobs T 2 obss tel que [Math.43] 11 0 178 p [0206] avec /0 bs la longueur de l'obstacle et L obs la largeur de l'obstacle. Il y a conflit si .17 ,.._ ' c Lobs pourr E TA: ; 1- obs -I int- L ) 2 obsinf [ dichotomie E T3 -1- obsinf o bssup " I-V est calculé par dichotom e tel que , Lobs n. Si lors de la recherche dichotomique Y ( -r - Int dichoto e ) - 2 = u L ,, t, , , un conflit est détecté, la recherche est stoppée et Y int(T dichotomie) =1 1:2' la replanification de chemin est alors nécessaire, se traduisant par la détermination d'un deuxième chemin pour contourner l'obstacle Il. [0207] La résolution par dichotomie est utilisée pour résoudre des problèmes d'optimisation en temps réel sur système embarqué. Elle est détaillée ci-dessous par souci de clarté et de dénomination. [0208] Soit deux nombres réels a [a, b f telle que f(a) et f(19) soient de signes opposés. La méthode de dichotomie cherche à résoudre l'équation f(x) = O. D'après le théorème des valeurs inter- médiaires, f a au moins un zéro dans l'intervalle , b I. La méthode de dichotomie consiste à diviser l'intervalle en deux en calculant( Cl b Il y a 171 - 2 et b et une fonction réelle f continue sur l'intervalle maintenant deux possibilités : ou f (u) et f (m) sont de signes contraires, ou f (nt) et f(b ) sont de signes contraires. [0209] L'algorithme de dichotomie est alors appliqué au sous-intervalle dans lequel le changement de signe se produit, ce qui signifie que l'algorithme de dichotomie est récursif L'erreur absolue de la méthode de dichotomie est au plus b - a après n 2n + 1 itérations (n E N) car l'erreur est diminuée de moitié à chaque étape. Ainsi, la méthode converge linéairement, ce qui est très lent par comparaison avec la méthode de Newton. L'avantage par rapport à cette dernière est son domaine d'application plus vaste : il suffit seulement que f(a) et f(b) soient de signes opposés et qu'on puisse déterminer le signe de f(m) à chaque itération. De plus, si l'on se donne la tolérance relative e, on sait majorer le nombre d'itérations nécessaires pour satisfaire cette tolérance : 102101 IMath.441 + 1 0, alors b n = h 0. De plus : [0212] [Math.45] + rn. +1- a n 2 [0213] Or l'algorithme de dichotomie s'arrête lorsque ( b - an) s obs., _ 2 [0217] 21 [Math.47] "1" obssrp tel que [Math.47] lobs Xest rx obs ) - 2 ( Lob, pour T E T 2 L obsinf obs sup 1-d i cl? o i omie e [TX ext(r dichotomie) 2 ohs 1 , t bs L 0 ; I- x o est calculé par dichotomie tel que b s 0 di - s u p Si lors de la recherche chotomique ) o h , un conflit est détecté, la recherche est stoppée et la replani- 1 ext', L 2 fication de chemin est alors nécessaire, se traduisant par la détermination d'un deuxième chemin pour contourner l'obstacle 11. [0219] [fig.7] illustre de façon schématique un obstacle 11 localisé à gauche du premier chemin 101 avec un virage à droite. Soit T 0 tel que XI- (T = 0, si yr er 0) .xt r ) s p [0223] 11 y a conflit si v, e Xe xt (TA obs 2 pour T e [7-;Ti obsinr obs. 1" sur L r, b n Si lors de la recherche dichotomique ext(T dichotomie) + 2 =u- L o h s un conflit est détecté, la recherche est stoppée et la replani- Yex (T. fication de chemin est alors nécessaire, se traduisant par la détermination d'un deuxième chemin pour contourner l'obstacle 11. [0224] [fig.8] illustre de façon schématique un obstacle 11 localisé à gauche du premier chemin 101 avec un virage à gauche. [0225] Soit : [0226] [Math.50] Tx obsint jobs tel que 2 [Math.50] [0227] [Math.Sl] Tti obssup tel que [Math.51] iob Xint( TA - 2s [0228] ii y a conflit si , ; TA inf; TI:Tbs pour T E rx 2 0 ti sin f 0 b s SU r int(T ) S: T dichou,mi,' e T \ [ obs oh& est calculé par dichotomie tel que stip L ,,, I., s n Si lors de la recherche dichotomique Yi ( I- dicho ro m i e ) + = u. L 0 h s , un conflit est détecté, la recherche est Yrni (T ch/Amict/nu ) 2 stoppée et la replanification de chemin est alors nécessaire, se traduisant par la détermination d'un deuxième chemin pour contourner l'obstacle 11. [0229] Dans une cinquième étape 35, deux points d'un deuxième chemin contournant l'obstacle sont déterminés en fonction des données représentative de dimensions du véhicule autonome et de la largeur de l'obstacle, les deux points étant déterminés de manière à être situés à une distance latérale minimale de l'obstacle. [0230] Afin d'éviter l'obstacle, le chemin replanifié est contraint de passer par deux points particuliers p C. 2 et p 0 n+ 1 [0231] [Math.52] 23 P (C)2 -(1 PAF')- lobs ± (Li + Lo2i), _i_,) et [Math.52] C2 Pn+ = [(1-PAF0r) +1,17, ±l 2 +L(2138 +A) 102321 situés à une distance minimale latérale de l'obstacle de I Lo h et avec 2 une marge de sécurité. Le deuxième chemin peut alors par exemple être défini par trois courbes de Bézicr cubique afin d'imposer deux points de passage, comme expliqué à l'étape 37. Selon une variante, le deuxième chemin est déterminé à partir de courbes de troisième ordre ou plus de type B-spline passant par les deux points de passage. [0233] Dans une sixième étape 36, le point de départ du deuxième chemin contournant l'obstacle est déterminé. Ce point de départ correspond avantageusement au point du premier chemin pour lequel l'angle de braquage pour atteindre un premier point parmi les deux points déterminés précédemment est minimal le long du deuxième chemin [0234] [fig.9] illustre de manière schématique la détermination de ce point de départ du deuxième chemin, selon un exemple particulier et non limitatif de la présente invention. [0235] Soit r n la valeur de r associée à la position sur le premier chemin 101 où le véhicule autonome 10 détecte l'obstacle 11 et z ni ax la valeur de r maximal au-delà duquel la replanification de chemin ne garantit plus l'évitement de l'obstacle. r N est ainsi défini tel que Xr (Tmax) - -(1-PAF,, ) - /obs. L'instant de rcplanification Tre E T r i n T rn a J cst défini tel que : [0236] [Math.53[ argmin N,,,,:'') -e large e replann repiati [0237] r r e plan est la valeur de r minimisant l'écart entre le lacet à l'instant 17 re r, / a n du véhicule autonome 10 et le lacet idéal permettant d'effectuer la manoeuvre d'évitement. Ce lacet idéal est défini comme l'angle formé par un vecteur colinéaire à l'axe des abscisses du repère obstacle et un vecteur colinéaire à la direction P1 replan n C2 . Minimiser e - r re p tif ta nie t(T te plan Plp revient à minimiser l'angle de braquage du véhicule 10 le long du deuxième chemin. Cette minimisation est réalisée par dichotomie pour un souci de temps de calcul et pour 24 respecter les contraintes temps réel de détermination du deuxième chemin. [0238] Dans une septième étape 37, des troisièmes paramètres représentatifs du deuxième chemin 102 sont déterminés à partir de plusieurs courbes paramétriques polynomiales C2 et n C2 de i.3>riie ordre ou plus, ces courbes étant continues aux deux points D et -1- 0 r n + 1 passant par les deux points p C 2 et p C2 . Ces troisièmes paramètres correspondent n + I par exemple à des points de contrôle chacun défini par un indice et des coordonnées X, Y. [0239] Les courbes paramétriques polynomiales utilisées correspondent par exemple à : [0240] - trois courbes de Bézier cubiques ; [0241] - deux courbes de Bézier cubiques combinées à une courbe de Bézier d'ordre 4 ; ou [0242] - toute combinaison de courbes paramétriques polynomiales d'au moins du 3ème ordre, par exemple des courbes de type B-Spline ou NURBS. [0243] L' utilisation de trois courbes de Bézier cubiques offre l'avantage d'une complexité calculatoire moindre que l'utilisation de deux courbes de Bézier cubiques combinées à une courbe de Bézier d'ordre 4. Cependant, l'utilisation de deux courbes de Bézier cubiques combinées à une courbe de Bézier d'ordre 4 offre l'avantage d'une meilleure continuité de l'angle de braquage relatif au chemin replanifié. [0244] Exemple d'utilisation de trois courbes de Bézier cubiques [0245] Le problème est d'identifier le chemin le plus court respectant les contraintes de continuités et de passage par deux points particuliers. Le chemin est défini par trois courbes de Bézier cubiques afin d'imposer deux points de passage. La traduction de ce problème en problème d'optimisation sous contraintes est réalisée de la manière suivante : [0246] [Math.54] :;i [0247] avec C k désignant la k-ième courbe de Bézier, c k k et Pi yiC k yCk] [0248] Les contrain es de type égalité sont les suivantes : [0249] - Continuité de la courbe : [0250] - au premier point de passage p 3 - [0251] [Math.55] Ci LT2 X X 3 - - 0 ' k XL k ( PrC T/_ r [0252] [Math.56] n (7 2 C /7E:1 y (C;2 r = 0 102531 - au deuxième point de passage [0254] [Math.57] )(C2 - X(..3 - 0 [0255] [Math.58] C'2 ,C3 13 - [0256] - Continuité du lacet : [0257] - au premier point de passage p C 3 = PO - C:2. 102581 1Math.591 d YTC2 (T)/dt dIrica (r) I dr - dXf 2 CO /dr d Ag (r) / dr r=i 7=0 dri (T) de (r) E9 -1dr dr y=1 d lire (r)1 dY,9 (r) [0259] - au deuxième point de passage [0260] [Math.60] dYL2('r)/dr (T)/tir- dXF2 (T)/ r=i riXf3(T)/dr q2 = dr dr r=i D C2 OC: -1- 3 =p0 0 « 17=0 = -evc2 + 2xL2 0 r=0 = + - dX.P(T) q3 dr dY,c2 er) E c14 dr dX (r) dr T=1 YrC3 (T) dr r=1 = 24.2 - - XC3 32 7=0 = 1/3C 2 - yiC 3 r = 102611 - Continuité du lacet initiale 0: 102621 IMath.611 Eq 5= e (o)-e'=yi"-Y[Ïil + tan ( ')(XY [0263] - Continuité du lacet final e oe : [0264] [Math.62] c Eq6=9 (1) -0,0- 2'3+ tan (0 )(X Y' - [0265] - Continuité du braquage : [0266] - au premier point de passage p z = C 2 - . C 1 C [0267] [Math.63] 26 (12 yE1(..0 a 2 yre2 (T) T=0 d 2x,(72 (T) el (T) (12-2 CIT" d 2 CF2XF2 ciT2 T=1 d 7-2 C12 E = C12-2 Cfra q 7 T=1 T=0 EqR ci2yrCl(r) r=1. d2 YTC2 (r) T2 dr2 T=0 X ,`" - o.5x5.2 + o.sxF - xp = Y,c2 - 0.5K2 + 0.5Y1 - [0268] - au deuxième point de passage p L 2- p 3 - [0269] [Math.64] d 2 yrC 3 ET ) ÉlT d 2 yrC2 (T) - d= )(Per) dr2 d2Xf2(r) dr2 dr= T=1 17=0 ERS - d 2 xrC1 (T) T=1 d 2 X,C2 (±) =0 Eche T=0 d-c2 dr2 d2 -}-( d 2 irez (r) dr2 T=1 dr2 = -x22 + o.5xf2 +xf3 - 0.sxf3 = -Y,c2 + o.s + - 0syr3 102701 Soit E , les contraintes de type égalité deviennent alors E Q = 0 E (2 E 10 Afin de réduire le nombre de variables d'optimisation, on cherche à exprimer les contraintes de type égalité de la façon suivante : [0271] [Math.65] cons,Ccons bcons = [0272] avec X = _ci Cl _c yy x 'crins L171 11( 2 Y2 L'équation 65 est équivalente à [0273] [Math.66] A consXcons + 19 cons - E Q [0274] Par identification terme à terme, on obtient : [0275] [Math.67] {A _ adEQ b CONSXCM/ S COTS =EQ - A COÏLSX CORS 27 [0276] Remarque : cette méthode n'est utilisable que dans le cas de contrainte linéaire. [0277] Il est alors possible d'exprimer Xco s en fonction de yc, VlCI. ,û 2, y0 2, zsa I 0 vC2 7(.2 f-'3 et vc3 de la manière suivante : . A 3 v 3 [0278] [Math.681 A 1 Xcons cor: sb cons [0279] Les contraintes de type inégalité quant à elles sont les suivantes : [0280] - Points de passage afin d'éviter l'obstacle : [0281] [Math.69] y(C) 2 > +Fr 102821 I Math.701 L Lob, - -2± 2 ± 2 + A [0283] Le problème d'optimisation étant posé, il s'agit maintenant du problème de sa ré- solution, notamment en temps réel. [0284] Afin de résoudre le problème de la résolution du problème d'optimisation, le critère doit être mis sous forme d'un critère quadratique : [0285] [Math.71] J longueur (x) = Ex + x F [0286] Si l'on considère que l'encombrement du véhicule selon l'axe longitudinal est délimité par les abscisses - /0 ha.+ - PAF') et I o h s (1 - PA-Far ) , on obtient alors les équations - 102871 IMath.721 X0C2 - /obs. PAFar) [0288] Et [0289] [Math.73] c9 X3 = lots - (1 - PAF,) [0290] En injectant l'équation 66 dans l'équation 69, on obtient le problème d'optimisation suivant : [0291] [Math.74] -1 r(j min liong^ieUr (X) = sc Mx y, = [0 -1 0 Di avec x = [Xi ye 1/2.C2 Xf3r, E = h'"snenr F - dila"9"e'LO 0 -1 of = [L Lob, + a 2 2 et Lobs largeur de l'obstacle. _L _ Lob, ± a 102921 Afin de trans orner notre problème sous contraintes en problème sans contraintes, le Lagrangien du problème est établi : 102931 IMath.751 j(X, À) = X T Ex -E- xTF 4 À (Afx - y) [0294] Trouver le vecteur x qui minimime le critère J revient à résoudre le problème : [0295] [Math.76] naax min Ex + X TF + À T VI X - y)1 0 x [0296] En annulant la dérivée du critère en fonction de X, il es possible d'obtenir x = f(À ): [0297] [Math.77] X = -E 1(F JUTA) [0298] En remplaçant x dans l'équation 76 par son expression de la relation 77, on obtient la relation : [0299] [Math.78] max(-1,À HÀ - K E-1F) À - [0300] qui peut sc réécrire, en posant H = ME-1mT et K [0301] [Math.79] minklÀ lHA +À K + 3--yTE y) 0 " [0302] Le problème peut par exemple être résolu par l'algorithme de Hildreth. [0303] Exemple (l'utilisation de deux courbes de Bézier cubiques combinées à une courbe de Bézier d'ordre 4 [0304] Le problème est (l'identifier le chemin le plus court respectant les contraintes de continuités et de passage par deux points particuliers. Le chemin est défini dans cette partie par deux courbes de Bézier cubiques et une courbe de Bézier d'ordre 4 afin d'imposer deux points de passage et la continuité de la vitesse de braquage. 103051 Le problème est donc d'identifier le chemin le plus court respectant les contraintes de 28 XTF 2 2 y +ME 29 continuités et de passage par deux points particuliers. La traduction de cc problème en problème d'optimisation sous contraintes est réalisée de la manière suivante : [0306] [Math.80] [0307] avec C k désignant la k-ième courbe de Bézicr,= Cil etCk X k p TC k(T = t re k ,k 7 . Y; k 103081 Les coi Craintes de type égalité sont les suivantes : 103091 - Continuité de la courbe : 103101 - au premier point de passage p 3 c I pc 2: [0311] [Math.81] [0312] [Math.82] CL v-(72 / :3 = / 0 [0313] - au deuxième point de passage p 4C 2 p0 3: [0314] [Math.83[ ,C2= XF 103151 1Math.841 /74C2 - Yoc3 [0316] - Continuité du lacet : [0317] - au premier point de passage p c C 1 _ p 2' 3 - 0 « d YC2 (T)/Cir T dXf2 Wird r =1 dXci T.) r=1 LIX;(:" 2 (17) Ir= 0 = -4,xg2 + 7xg - 3Xf13Y,C1 -r=0 = -21-YE2 7K2 E - tir dv d y:5 2 (..0 dijrn (r) Eq2 = dr dr [0318] [Math.85] dyp(r)/it dx47.1(i)/dr r= 17=1 [0319] - au deuxième point de passage [0320] E [Math.86] d Y.,c2 (T) I cIT dXfa (T)I cly d113 (T)/ tiXg3 (T)/dT 7= de2 (r) 3 dT 1,,C2 (.0 Eq4 = C1T T=1 d.,CP ('r) dr dY,P er) dr = -4X - 7X.2 - 3x 3 = 4 Y3C2 - 3 Yin T = 1=1 1=1 =0 [0321] - Continuité du lacet initial 9 : [0322] [Math.87] E e 10)-80= ci - Y 0 + tan ( e )kx -x(1 1-) [0323] - Continuité du lacet final e [0324] [Math.88] c- Eci 6= e (1) -e Y? - Y.? + tan te ,,o) (t» -x?) [0325] - Continuité du braquage : 1 C 2 : [0326] - au premier point de passage p [0327] [Math.89] [0328] - au deuxième point de passage 103291 IMath.901 da Yre2 (y) da Yr(3(r.) dr2 dr2 d2Xf2 CO d 2 X.F3 (T) 2 r d 2-=1 r2 t=o d2Xfi( r) d2_472(r) (19 - = 21-`72 44:2 + eiP2 + 2X? - dr2 dr 2 T=1 T=0 d2 C1(.0 d2 yC2 (.0 _ yoc2 = 4}C,c2 1=0 - 21erzca + Yica 2yc1 d 2 yrei (.0 dr2 a 2 (T) dr2 d2Yrca(r) dr2 d2 Arf2 (T) CIT2 r=1 T=0 d2Xiçier) d2X,Ç2(r) dr2 dr2 T=1 d 2 yrtl d 2 yrC2 (T) dr2 T=1. - 442 - X ,(5.2 - M'Y + Xf-] - 2e] Eq7 E q, = dr2 7=0 r P 2 C 3 : Egio = eir2 dr2 211c2 - 4Yr2 + Ye2 + 211c3 - 2 3 4 1 2 T=0 r=1 [0330] - Continuité de la vitesse de braquage : 31 [0331] - au premier point de passage p ,C 1 = p (C- ) 2: 103321 IMath.911 ci3Yrc1(r) c13 Y» (+) dx-' _ dr". d3 X .;:" (r) (13 X f 2 CO di- '1 C1T3 r=o d' e (r) d' e Il+) E g, - = 5A"g2 - 12e 2)(-P - 4X :F - el + 3k.ft - 3)(2- dr.' d r3 27=1 =0 d3 yfl (5) I d' Yrn. (1-r1 E g 12 - - SY,f 2 - 12Yra + 12YP - ilYac - Yoci + 3 yr - 3Y2n dr-1 Ir.' CIT'' r=0 . 103331 - au deuxième po nt de passage p 4C 2 _ p (C:3: [0334] [Math.92] d 3 %Tt 2 (.-,) d3 yre3 (.-0 d "L 3C11:3 - d34:2 Cr) d 3 X.P CO d-r 3 1 dry T=o E ct2 X 2 (1-.)1 (Tl] 12)(72 - 4KP2 - 124 + - 3Xf 3 + 3e,-73 - q = E-17'3 ci E-3 k=f1 d3Y,C2(T)I d3Yrc(r.) Eq14 12YP - 47Y1c2 - 12YP + 5Y.F2 - 3 YF3 + 3YP r=i T=o 103351 Soit Eq i les contraintes de type égalité deviennent alors EQ-0 EQ = Fg. I 4 Afin de réduire le nombre de variables d'optimisation, on cherche à exprimer les contraintes de type égalité de la façon suivante : [0336] [Math.93] A consX cons + b cons = (1) [0337] avec XCtillS[dr; 1 1 312 1 2 211 yel vel C1 vl 2 x.f" 3 -,C 3 "c t133 -C3 L'équation 93 est équivalente à : [0338] [Math.94] A cons X cons f 11 cons = EQ [0339] Par identification terme à terme, on obtient : [0340] [Math.95] {. ° licous=ernEQ-- aAcE2 Au 11SXcons X cons 32 [0341] Remarque : cette méthode n'est utilisable que dans le cas de contrainte linéaire. [0342] Il est alors possible d'exprimer Xco ris en fonction de .5(- CI, yr I, v-C2, i /C2. rs0 0 1,--C 2 C 2 -Ir e 3 et y C 3 de la manière suivante : 214 4 A 3 3 [0343] [Math.96] A X C 0 il S nconsb cons [0344] Les contraintes de type inégalité quant à elles sont les suivantes : [0345] - Points de passage afin d'éviter l'obstacle : [0346] [Math.97] -C2 L 0 bs 2 103471 IMath.981 Y4? , Lobs +A) > 2 2 [0348] Le problème d'optimisation étant posé, il s'agit maintenant du problème de sa ré- solution, ce qui est l'objet du paragraphe suivant. [0349] Afin de résoudre le problème, le critère doit être mis sous forme d'un critère qua- dratique : [0350] [Math.99] jlonqueur(X)= 2 x Ex ± x [0351] Si l'on considère que l'encombrement du véhicule selon l'axe longitudinal est délimité par, - /0 hs / 2 et lobs / 2 , on obtient alors les équations : [0352] [Math.100] Xr:--lobs + -P-AFur) [0353] Et [0354] [Math.101] cz = d'bs - (ï - P A F '') [0355] En injectant l'équation 96 dans l'équation 99, on obtient le problème d'optimisation suivant : [0356] [Math.102] arg = 2 x' x' F sc Mx avec r = D'oc' Vi2], a 2 I i071.9 ur az 2 103571 et Lobs largeur de l'obstacle. 33 [0358] Afin de transformer notre problème sous contraintes en problème sans contraintes, le Lagrangien du problème est établi : [0359] [Math.103] j(X , = 2X Ex xi.F --FAT(Mx- y) [0360] Trouver le vecteur x qui minimime le critère J revient à résoudre le problème : [0361] [Math.1041 J)-x TEx + x F +Al(Mx- y)] max min A 0 x [0362] En annulant la dérivée du critère en fonction de x , il es possible d'obtenir x = T(À): [0363] [Math.105] X = -E-1(E MIÀ [0364] En remplaçant x dans l'équation 104 par son expression de la relation 105, on obtient la relation [0365] [Math.106] max ( THÀ -À K 1F) À 0 [0366] qui peut se réécrire, en posant H = ME IMT et K - y + ME 'F [0367] [Math.107] min (1,À THÀ HÀrK-H-y Ely) À 103681 Le problème peut alors être résolu par exemple par l'algorithme de H ildreth. 103691 Les étapes 32 à 37 sont avantageusement réitérées à la détection d'un nouvel obstacle et les étapes 31 à 37 sont avantageusement réitérées pour tout nouveau premier chemin avec détection d'obstacle. 103701 Un tel procédé permet à un véhicule autonome de planifier un nouveau chemin pour éviter un obstacle, notamment un obstacle statique (dont la vitesse est nulle), à partir d'un chemin établi précédemment. Le nouveau chemin planifié peut être suivi par le véhicule autonome car il respecte des contraintes associées au véhicule telles que par exemple la valeur maximale de l'angle au volant (limite technologique) ou encore la vitesse de braquage (habituellement contournée par limitation de la vitesse du véhicule, ce qui peut générer de l'inconfort pour les passagers). La planification du nouveau chemin respecte également des contraintes de temps (planification en temps réel), ce nouveau chemin devant avantageusement être planifié suffisamment rapidement pour ne pas avoir à diminuer trop fortement la vitesse du véhicule pendant le calcul de ce nouveau chemin. [0371] En effet, le procédé repose sur la description d'un premier chemin, reparamétré dans 34 un nouveau repère lié à l'obstacle. Les paramètres du deuxième chemin sont optimisés par optimisation quadratique. Pour cela, le problème et les contraintes associées sont exprimés sous une forme adaptée (quadratique). [0372] Le procédé permet de générer le deuxième chemin le plus proche du premier chemin initialement planifié, garantissant l'évitement de l'obstacle, tout en minimisant la modification de l'empreinte au sol du véhicule sur le chemin. [0373] Grace à une contrainte sur la continuité de l'angle de lacet et de l'angle de braquage en fonction du déplacement, le véhicule autonome n'est pas obligé de s'arrêter afin de suivre le chemin obtenu, ce qui est plus confortable pour les passagers, et aucune contrainte technologique associée au véhicule ne peut l'empêcher de suivre le nouveau chemin. [0374] L'utilisation d'une méthode d'optimisation de type programmation quadratique permet d'obtenir un temps de calcul réduit, compatible avec une utilisation temps réel. [0375] [fig.10] illustre schématiquement un dispositif 1000 de détermination d'un chemin pour un véhicule autonome 10, selon un exemple de réalisation particulier et non limitatif de la présente invention. Le dispositif 1000 est par exemple configuré pour la mise en oeuvre des étapes du procédé décrit en regard des figures 1 à 9. [0376] Des exemples d'un tel dispositif 1000 comprennent, sans y être limités, différents appareils électroniques tels qu'un calculateur, une UCE (« Unité de Commande Elccironique » ou en anglais ECU « Electronic Control Unit ») ou un équipement électronique embarqué tel qu'un ordinateur de boni d'un véhicule, un téléphone intelligent (de l'anglais « Smartphone »). Les éléments du dispositif 1000, individuellement ou en combinaison, peuvent être intégrés dans un unique circuit intégré, dans plusieurs circuits intégrés, et/ou dans des composants discrets. Le dispositif 1000 peut être réalisé sous la forme de circuits électroniques ou de modules logiciels (ou informatiques) ou encore d'une combinaison de circuits électroniques et de modules logiciels. Selon différents modes de réalisation particuliers, le dispositif 1000 est couplé en communication avec d'autres dispositifs ou systèmes similaires, par exemples des calculateurs ou ECU, par exemple par l'intermédiaire d'un bus de communication ou au travers de ports d'entrée / sortie dédiés. [0377] Le dispositif 1000 comprend un (ou plusieurs) processeur(s) 1020 configurés pour exécuter des instructions pour la réalisation des étapes du procédé. Le processeur 1020 peut inclure de la mémoire intégrée, une interface d'entrée/sortie, et différents circuits connus de l'homme du métier. Le dispositif 1000 comprend en outre au moins une mémoire 1021, par exemple une mémoire volatile at/ou non volatile et/ou comprend un dispositif de stockage mémoire qui peut comprendre de la mémoire volatile et/ou non volatile, telle que EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, disque magnétique ou optique. Les informations reçues de l'infrastructure réseau et/ou les in- formations mesurées ou déterminées par le dispositif 1000 sont avantageusement enregistrées et stockées dans la mémoire 1021. Le code informatique comprenant les instructions à charger et exécuter par le processeur 1020 est par exemple stocké sur la mémoire ou le dispositif de stockage mémoire 1021. [0378] Selon un mode de réalisation particulier et non limitatif, le dispositif 1000 comprend un bloc 1022 d'éléments d'interface pour communiquer avec des dispositifs externes, par exemple le « cloud », un téléphone intelligent, un lecteur multimédia, des capteurs odométriques, un capteur GPS. Les éléments d'interface du bloc 1022 comprennent une ou plusieurs des interfaces suivantes : [0379] - interface radiofréquence RF, par exemple de type Bluctooth® ou Wi-Fi®, LTE 4G ou 5G ; [0380] - interface USB (de l'anglais « Universal Serial Bus » ou « Bus Universel en Série » en français) ; [0381] - interface HDMI (de l'anglais « High Définition Multimedia Interface ou « Interface Multimedia Haute Définition » en français). [0382] Selon un autre mode de réalisation particulier, le dispositif 1000 comprend une interface de communication 1023 qui permet d'établir une communication avec d'autres dispositifs (tels que des calculateurs ou ECU du système embarqué) via un canal de communication 1230, par exemple un bus de communication de type bus de données CAN (de l'anglais « Controller Arca Network » ou en français « Réseau de contrôleurs »), CAN FD (de l'anglais « Controller Area Network flexible Data-Rate » ou en français « Réseau de contrôleurs à débit de données flexible »), FlexRay (selon la norme ISO 17458) ou Ethernet (selon la norme ISO/IEC 802-3). L'interface de communication 1023 correspond par exemple à un transmetteur configuré pour transmettre et recevoir des informations et/ou des données via le canal de communication 1230. L'interface de communication 1023 comprend par exemple un modem etlou une carte réseau et le canal de communication peut par exemple être mis en oeuvre dans un medium filaire etlou sans fil. [0383] Selon un mode de réalisation particulier supplémentaire, le dispositif 1000 peut recevoir et/ou fournir des signaux d'entrée / de sortie de / à un ou plusieurs dispositifs externes, tels qu'un dispositif d'affichage (tactile ou non), un ou plusieurs haut-parleurs et/ou d'autres périphériques (micro par exemple) via respectivement des interfaces de sortie adaptées. Selon une variante, l'un ou l'autre des dispositifs externes est intégré au dispositif 1000. 36 [Revendication 1] [Revendication 2] [Revendication 3] REVENDICATIONSProcédé de détermination d'un chemin pour un véhicule autonome (10), ledit procédé comprenant les étapes suivantes : - réception (31) de premiers paramètres représentatifs d'un premier chemin (101) dans un repère absolu ; - réception (32) de données représentatives d'un obstacle (11) détecté le long dudit premier chemin (101), lesdites données étant exprimées dans un repère associé à l'obstacle (11) ; - détermination (33) de deuxièmes paramètres représentatif dudit premier chemin (101) dans le repère dudit obstacle (101) à partir desdits premiers paramètres ; - détermination (34) de la présence d'un conflit entre ledit obstacle (11) et ledit premier chemin (101) en fonction desdites données représentatives de l'obstacle (11), de données représentatives de dimensions dudit véhicule autonome (10) et desdits deuxièmes paramètres ; - détermination (35) de deux points d'un deuxième chemin (102) contournant ledit obstacle (11), lesdits deux points étant déterminés en fonction desdites données représentative de dimensions dudit véhicule autonome (10) et de la largeur dudit obstacle (11) de manière à être situés à une distance latérale minimale dudit obstacle (11) ; - détermination (36) d'un point de départ dudit deuxième chemin (102), ledit point de départ correspondant au point dudit premier chemin (101) pour lequel l'angle de braquage pour atteindre un premier point parmi lesdits deux points est minimal le long dudit deuxième chemin (102) ; - détermination (37) de troisièmes paramètres représentatifs dudit deuxième chemin (102) à partir d'une pluralité de courbes paramétriques polynomiales d'au moins le troisième ordre continues auxdits deux points et passant par lesdits deux points. Procédé selon la revendication 1, pour lequel ladite détermination (34) de la présence d'un conflit comprend la détermination de la position relative dudit obstacle (11) vis-à-vis dudit premier chemin (101) dans le repère dudit obstacle, la détermination du sens d'un virage formé par ledit premier chemin au niveau dudit obstacle, la détermination (34) de la présence d'un conflit dépendant de ladite position relative et dudit sens du virage. Procédé selon la revendication 2, pour lequel ladite détermination (34) de la présence d'un conflit comprend en outre la comparaison de 37 [Revendication 4] [Revendication 5] [Revendication 6] [Revendication 7] l'empreinte dudit véhicule autonome (10) sur le premier chemin (101) avec l'empreinte dudit obstacle (11), l'empreinte dudit véhicule étant décrit avec une enveloppe supérieure et une enveloppe inférieure chacune décrite par deux points dudit véhicule autonome (10) dépendant du sens du virage. Procédé selon l'une des revendications 1 à 3, pour lequel la détermination (36) dudit point de départ comprend la détermination d'une variable spatiale pour laquelle ledit deuxième chemin (102) débute, la détermination de la variable spatiale correspondant au point de départ comprenant les étapes de : - détermination d'un intervalle auquel appartient ladite variable spatiale, l'intervalle étant borné par une position minimale sur le premier chemin (101) correspondant à l'instant de réception des données représentatives d'un obstacle (11) et par une position maximale sur le premier chemin (101) correspondant à la position où le véhicule autonome (10) atteint un point d'abscisse X égale à (-(1-PAF',)-1,') dans le repère de l'obstacle, où I correspond à la longueur du véhicule autonome, PAF, correspond à la longueur du porte-à-faux arrière du véhicule autonome (10) et correspond à la longueur de l'obstacle ; - détermination de ladite variable spatiale comme correspondant à la position minimisant l'écart entre le lacet du deuxième chemin au point de départ et un lacet idéal du deuxième chemin (102) permettant d'éviter ledit obstacle (11), le lacet idéal correspondant à un angle formé par un vecteur colinéaire à l'axe des abscisses du repère de l'obstacle (11) et un vecteur colinéaire à une droite passant par le centre de l'essieu arrière dudit véhicule autonome (10) et ledit premier point parmi lesdits deux points et orientée dudit centre vers ledit premier point. Procédé selon l'une des revendications 1 à 4, pour lequel ladite pluralité de courbes paramétriques polynomiales d'au moins le troisième ordre comprend : - trois courbes de Bézier cubiques ; ou - deux courbes de Bézier cubiques et une courbe de Bézier d'ordre 4. Procédé selon l'une des revendications 1 à 5, pour lequel lesdites données représentatives de dimensions du véhicule autonome (10) comprennent la longueur dudit véhicule autonome, la largeur dudit véhicule autonome et la longueur du porte-à-faux arrière dudit véhicule autonome. Procédé selon l'une des revendications 1 à 6, pour lequel la déter- 38 [Revendication 8] mination (37) des deuxièmes paramètres représentatifs dudit premier chemin dans le repère dudit obstacle est réalisée à partir des premiers paramètres représentatifs du premier chemin non parcouru par ledit véhicule autonome (10)à la réception de données représentatives de l'obstacle '11) détecté. [Revendication 9] [Revendication 10] Dispositif (1000) de détermination d'un chemin pour un véhicule autonome, ledit dispositif comprenant une mémoire (1021) associée à au moins processeur (1020) configure pour la mise en oeuvre des étapes du procédé selon l'une quelconque des revendications 1 à 7. Véhicule automobile (10) comprenant le dispositif selon la revendication 8. Produit programme d'ordinateur comportant des instructions adaptées pour l'exécution des étapes du procédé selon rune des revendications 1 à 7, lorsque le programme d'ordinateur est exécuté par au moins un processeur.