Brevet FR2931936A1 — publié le 20091204

Procédé de planification de trajectoire en présence de courants variables dans le temps L'invention concerne un procédé de planification de trajectoire pour un mobile entre un point de départ et un point d'arrivée situés dans un environnement donné en présence de courants variables dans le temps. Elle s'applique notamment à la recherche d'une trajectoire optimale et d'une date de départ optimale pour un mobile se déplaçant dans des conditions de courant non uniforme et non constant. Par trajectoire optimale et date de départ optimale, on entend respectivement la trajectoire et la date de départ permettant à l'engin mobile de relier le point de départ au point d'arrivée en un minimum de temps. L'engin mobile est par exemple un avion sans pilote, également appelé drone, ou un robot autoguidé sous-marin. Selon le cas, les courants auxquels est soumis l'engin mobile sont soit des courants aériens, soit des courants marins. Dans les deux cas, l'engin mobile se déplace généralement à des vitesses relativement faibles, ces vitesses pouvant même être inférieures à celles des courants. Par conséquent, la prise en compte de ces courants est indispensable afin de fournir la trajectoire et la date de départ optimales pour le mobile. Actuellement, les procédés de planification de trajectoire en présence de courants utilisent principalement des techniques d'optimisation continue, des algorithmes génétiques ou des algorithmes de propagation d'onde adaptés afin de prendre en compte la présence de courants. Les techniques d'optimisation continue sont par exemple décrites dans INANC, T., S.C. SHADDEN et J.E. MARSDEN. Optimal trajectory generation in ocean flows, Proceedings of the American Control Conference, 2005, p. 674- 679 et dans PANNEQUIN, J., A. BAYEN, I. MITCHELL, H. CHUNG et S. SASTRY. Multiple aircraft deconflicted path planning with weather avoidance constraints, Proceedings of the AIAA Guidance, Navigation and Control Conference, 2007. Les algorithmes génétiques sont par exemples décrits dans RUBIO, J. et S. KRAGELUND. The trans-pacific crossing: long range adaptive path planning for UAVs through variable wind fields, Proceedings of the Digital Avionics Systems Conference (2) et dans ALVAREZ, A., A. CAITI et R. ONKEN. Evolutionary path planning for autonomous vehicles in a variable ocean, Journal of Oceanic Engineering (29), 2004, p. 418-429. Les algorithmes de propagation d'onde adaptés à la présence de courants sont par exemple décrits dans GARAU, B., A. ALVAREZ et G. OLIVER. Path planning of autonomous underwater vehicles in current fields with complex spatial variability: an A* approach, Proceedings of the International Conference on Robotics and Automation, 2005, p. 194-198, dans PETRES, C., Y. PAILHAS, Y. PETILLOT et D. LANE. Underwater path planning using fast marching algorithms, Proceedings of Oceans 2005 - Europe, 2005, p. 814-819 et dans SOULIGNAC, M., P. TAILLIBERT et M. RUEHER. Adapting the wavefront expansion in presence of strong currents, Proceedings of the International Conference on Robotics and Automation, 2008. Ces procédés permettent certes de déterminer la trajectoire minimisant le temps de parcours entre le point de départ et le point d'arrivée pour une date de départ donnée, mais ils ne permettent pas de déterminer, simultanément à cette trajectoire, la date de départ optimale lorsque les courants évoluent en fonction du temps. Une solution consiste, dans un premier temps, à déterminer une trajectoire optimale et le temps de parcours associé à cette trajectoire pour différentes dates de départ et, dans un deuxième temps, à choisir la trajectoire optimale pour laquelle le temps de parcours est minimal. Cependant, cette solution ne permet pas de déterminer précisément la date de départ optimale, les temps de parcours étant déterminés de façon discrète pour différentes dates de départ. Un but de l'invention est notamment de pallier cet inconvénient en proposant un procédé de planification de trajectoire permettant de déterminer conjointement une trajectoire optimale et une date de départ optimale. A cet effet, l'invention a pour objet un procédé de planification d'une trajectoire d'un mobile entre un point de départ et un point d'arrivée situés dans un environnement donné en présence de courants, l'environnement étant discrétisé en plusieurs cellules comportant chacune un point de passage possible pour le mobile, à chaque cellule étant associé un vecteur vitesse de courant variable dans le temps et un coût cz(d). Selon l'invention, le coût cz(d) associé à une cellule représente le temps de parcours entre le point de départ et le point de passage de ladite cellule en fonction d'une date de départ du point de départ comprise dans une fenêtre temporelle et le procédé comporte les étapes suivantes : • initialiser les fonctions de coût cZ (d) des cellules de l'environnement et attribuer à un ensemble Fo de cellules la cellule contenant le point de départ, • réitérer les étapes suivantes tant que le point d'arrivée n'est pas 5 contenu dans un ensemble He de cellules : o déterminer, parmi l'ensemble Fo de cellules, l'ensemble He de cellules pour lesquelles le minimum cH(dH) de la fonction de coût cH (d) est minimal, o déterminer un ensemble Vo de cellules adjacentes aux cellules 10 de l'ensemble He et n'ayant pas déjà appartenu à l'ensemble He, o déterminer une fonction de coût c,, (d) pour chaque cellule de l'ensemble Vo, o supprimer de l'ensemble Fo, les cellules appartenant à l'ensemble He et ajouter à cet ensemble Fo les cellules appartenant à 15 l'ensemble Vo, • déterminer la trajectoire du mobile à partir des fonctions de coûts cz(d). Selon une forme particulière de réalisation, l'étape de 20 détermination de la fonction de coût cv(d) comprend une étape consistant à déterminer le minimum de différentes fonctions de coût c,, (d) pour chaque date de départ de la fenêtre temporelle, chaque fonction de coût c;, (d) correspondant au temps de parcours d'une trajectoire entre le point de départ et le point de passage de la cellule considérée et passant par l'une 25 des différentes cellules de l'ensemble He. Selon une forme particulière de réalisation, l'étape de détermination de la fonction de coût c,, (d) comprend une étape consistant à composer une fonction de coût local r' ,v (t), représentant un temps de 30 déplacement entre le point de passage d'une cellule considérée parmi l'ensemble He et le point de passage de la cellule considérée parmi l'ensemble Vo, avec la fonction de coût cH(d) associée à la cellule considérée parmi l'ensemble He selon la relation : cv(d)= [rH,.. a (cH +d'Id). 35 Selon une forme particulière de réalisation, des cartes de courants C , i étant un entier compris entre 1 et k, modélisent les vecteurs vitesse des courants wZ entre des instants t = t._1 et des instants t = t; dans un repère (O, x, y), les instants t = to = 0 et t = tk =T formant les bornes de la fenêtre temporelle, et la fonction de coût local r' (t) est définie à partir d'un coût local r, (t) par les relations : • pour t>-tk, ,,,(t)=TH,V(T), • Vi [1,k], si t; ù rH,V (ti_1 )>ù t;-1 o pour tE[t;_,;t,-rH,,(t_1)1' rH' ,V (t) = rH,V ti-I o pour t E [t, rH y (ti -I ); ti i , rHj' (t) - / T H,V (ti) - tl t+ rH,V ti \:2-I)-1/ rN,V (ti) - t; . \ rH,V (ti-1) , Vi e [1,k], si t; ùrHv(t;_,) Le procédé de planification de trajectoire selon l'invention est 15 adapté de l'algorithme de propagation d'onde introduit par Dorst et Trovato. Cet algorithme est par exemple décrit dans DORST, L. et K. TROVATO. Optimal path planning by cost wave propagation in metric configuration space, Proceedings of SPIE û The International Society for Optical Engineering, 1988, p. 186-197. Cet algorithme de propagation d'onde, 20 appelé algorithme de propagation d'onde classique, est introduit au regard des figures 1 et 2. La figure 1 représente un environnement 1 planaire de dimension finie auquel un repère (O, x, y) est associé. L'environnement 1 comporte un point de départ A et un point d'arrivée B, pour un mobile, non représenté. 25 L'environnement 1 est discrétisé par une grille 2 de dimension (m, n) délimitant m*n cellules Z. A chaque cellule Z est associé un point de passage 3 possible pour le mobile. Les points de passage 3 correspondent par exemple aux centres des cellules Z. Les points de départ A et d'arrivée B sont par exemple approximés par les points de passage 3 respectifs des 30 cellules Z contenant ces points de départ A et d'arrivée B. Les cellules Z contenant les points de départ A et d'arrivée B sont respectivement appelées cellules de départ 4 et d'arrivée ZB. A chaque cellule Z sont également associées les propriétés suivantes : wZ (wx; wy) : un vecteur vitesse de courant correspondant au flux de courant dans ladite cellule. Le courant est considéré homogène dans l'ensemble de la cellule Z. - cZ : un temps de parcours, également appelé coût, requis pour atteindre le point de passage 3 de la cellule Z à partir du point de départ A. Conformément à l'algorithme de propagation d'onde classique, lors d'une première étape, toutes les cellules Z adjacentes à la cellule de départ ZA sont explorées. En d'autres termes, un temps de parcours cZ est déterminé pour chaque cellule Z adjacente à la cellule de départ ZA. Classiquement, pour une itération donnée, on appelle front d'onde Fo, l'ensemble des cellules F adjacentes aux cellules Z pour lesquelles un temps de parcours cZ n'a pas encore été déterminé. De même, pour une itération donnée, on appelle tête He du front d'onde Fo, l'ensemble des cellules H du front d'onde Fo pour lesquelles le temps de parcours cF est minimal. Lors des étapes ultérieures, on considère successivement les cellules H de la tête He du front d'onde Fo et on évalue les temps de parcours locaux entre ces cellules H et leurs cellules Z adjacentes. Le temps de parcours cZ associé à une cellule Z adjacente peut alors être déterminé par une simple addition du temps de parcours cH associé à la cellule H considérée de la tête He du front d'onde Fo et du temps de parcours local respectif. Dans le cas où plusieurs temps de parcours cz sont attribués à une même cellule Z du fait d'une multiplicité de trajectoires, seul le temps de parcours cZ minimal est conservé. De fait, l'algorithme de propagation d'onde classique peut être considéré comme une propagation du front d'onde Fo à partir de la cellule de départ ZA, la propagation étant effectuée de manière itérative au sein des cellules Z de la grille 2 jusqu'à ce que la tête He du front d'onde Fo atteigne la cellule d'arrivée ZB. La propagation d'un front d'onde Fo est par exemple illustrée à la figure 2, où le front d'onde Fo est représenté à intervalles réguliers d'itérations. Par convention, le front d'onde initial Fo; correspond à la cellule de départ ZA. La trajectoire optimale peut ensuite être construite en utilisant un algorithme couramment appelé "hill climbing" dans la littérature anglo-saxonne. Cet algorithme est l'équivalent de la méthode du gradient dans le domaine discret. II consiste essentiellement à se déplacer de proche en proche au sein des cellules Z en partant de la cellule d'arrivée ZB et jusqu'à atteindre la cellule de départ ZA, chaque déplacement étant déterminé afin d'atteindre la cellule Z de coût cZ minimal dans le voisinage direct de la cellule Z courante. L'algorithme de propagation d'onde classique permet bien d'obtenir la trajectoire optimale pour une date de départ donnée, mais elle ne permet pas de déterminer la date de départ permettant de minimiser le temps de parcours entre le point de départ A et le point d'arrivée B lorsque la distribution des courants évolue au cours du temps. Le procédé de planification de trajectoire selon l'invention, appelé 10 algorithme de propagation d'onde symbolique, consiste principalement en une généralisation de l'algorithme de propagation d'onde classique. Selon ce procédé de planification de trajectoire, les coûts cZ associés aux points de passage 3 des cellules Z ne sont plus déterminés par des nombres, autrement dit une grandeur scalaire, mais par des fonctions dépendant de la 15 date de départ. Les opérations de l'algorithme de propagation d'onde classique sont alors adaptées à ces nouvelles fonctions de coût. Un exemple de réalisation du procédé de planification de trajectoire selon l'invention est décrit ci-dessous. Pour cela, on introduit les notations suivantes : 20 - Z : une cellule repérée par les coordonnées (xz ; yZ) de son point de passage 3, d : une date de départ à partir du point de départ A, dZ : une date de départ optimale à partir du point de départ A pour atteindre la cellule Z. dB représente alors la date de départ optimale 25 pour le mobile, - W = [o;T] : une fenêtre temporelle délimitant les dates de départ d possibles, - cz(d) : une fonction de coût correspondant au temps de parcours entre le point de départ A et le point de passage 3 de la cellule Z en 30 fonction de la date de départ d , - r' ,, (t) : une fonction de coût local correspondant au temps de déplacement entre une cellule H et une cellule V en partant à l'instant t, wZ (wx; wy,) : un vecteur vitesse de courant correspondant au flux de courant dans la cellule Z, les coordonnées wX et wy du vecteur 35 vitesse étant déterminées par rapport au repère (O, x, y), v : une vitesse du mobile par rapport aux courants, supposée constante, - C; : des cartes de courants modélisant les vecteurs vitesse wZ des courants entre les instants t = t;_1 et t = t; . L'indice i est un entier compris entre 1 et k. Par convention, on fixe to = 0 et tk =T et on considère que les courants après t =T restent modélisés par la carte de courants Ck . Pour la suite de la description, on introduit également les définitions suivantes. On considère qu'une cellule Z est explorée lorsqu'une fonction de coût cz(d) autre qu'une fonction de coût initiale lui est attribuée. On considère par ailleurs qu'une cellule Z est développée lorsque ses cellules voisines V sont explorées. Le procédé de planification de trajectoire selon l'invention peut être illustré par la figure 3. Il comprend notamment une étape 31 15 d'initialisation et une boucle 32 de propagation du front d'onde Fo. L'étape 31 d'initialisation comporte par exemple les sous-étapes suivantes, représentées à la figure 4. Dans une étape 311, une fonction de coût cz(d) constante sur la fenêtre temporelle W et de valeur infinie est associée à chaque cellule Z de la grille 2. Toute valeur autre que l'infini peut 20 être attribuée initialement aux fonctions de coût cz(d) dans la mesure où cette valeur reste toujours supérieure à une valeur que pourrait prendre la fonction de coût cZ (d) lors d'une itération de la boucle 32 de propagation du front d'onde Fo. Dans une étape 312, une fonction de coût cA égale à la fonction nulle sur la fenêtre temporelle W est associée à la cellule de départ 25 ZA. Dans une étape 313, la date de départ optimale dA pour la cellule de départ ZA peut être initialisée, par convention, à zéro. Cette étape 313 est facultative dans la mesure où la valeur attribuée à dA n'a aucune incidence sur le procédé de planification de trajectoire. Dans une étape 314, le front d'onde Fo est initialisé à un ensemble de cellules F comprenant uniquement 30 la cellule de départ ZA. L'ordre des étapes 311 à 314 n'a pas d'importance dans la mesure où la fonction de coût cA(d) est une fonction nulle à la fin de l'étape 31 d'initialisation. La boucle 32 de propagation du front d'onde Fo comporte par exemple les sous-étapes représentées à la figure 3. Dans une première 35 étape 321, la tête He du front d'onde Fo est déterminée. La tête He du front d'onde Fo correspond à l'ensemble des cellules F du front d'onde Fo pour lesquelles le minimum cF(dF) de la fonction de coût cF(d) est minimal. Lors d'une première itération de la boucle 32 de propagation du front d'onde Fo, la tête He du front d'onde Fo correspond au front d'onde Fo lui-même, c'est-à- dire à la cellule de départ ZA. Dans une deuxième étape 322, les voisins V de la tête He du front d'onde Fo sont déterminés. La détermination des voisins V de la tête He du front d'onde Fo est par exemple réalisée en utilisant une fonction V(Z) renvoyant l'ensemble Vo des cellules V adjacentes à la cellule Z considérée et n'ayant pas déjà appartenu à la tête He du front d'onde Fo. La condition de non-appartenance préalable à la tête He du front d'onde Fo empêche le front d'onde Fo de se propager vers la cellule de départ ZA. Dans une troisième étape 323, les cellules H appartenant à la tête He du front d'onde Fo sont développées. Autrement dit, pour chaque voisin V de la tête He du front d'onde Fo, une fonction de coût cv(d) est déterminée. Un exemple de détermination de cette fonction de coût c,, (d) est exposé ci-dessous. Dans une quatrième étape 324, le front d'onde Fo est mis à jour. La mise à jour du front d'onde Fo consiste à supprimer du front d'onde Fo les cellules H appartenant à la tête He du front d'onde Fo et à lui ajouter les cellules V appartenant au voisinage de la tête He du front d'onde Fo. Dans une cinquième étape 325, on vérifie si la cellule d'arrivée ZB appartient à la tête He du front d'onde Fo. Si tel est le cas, il est mis fin à la boucle 32 de propagation du front d'onde Fo dans une étape 326. Sinon, la boucle 32 est répétée à partir de la première étape 321. La suite de la description concerne la troisième étape 323 de la boucle 32 de propagation du front d'onde Fo, autrement dit la construction des fonctions de coût cv(d ). On considère dans un premier temps un coût local r11 v (t) correspondant au temps de parcours entre une cellule H et une cellule V en 30 partant à l'instant t, autrement dit pour des vecteurs vitesse de courant wä et w,, définis à l'instant t. Les vecteurs vitesse de courant wä et wv sont considérés égaux et notés 1î' par la suite. Le vecteur vitesse de courant ' est considéré constant pendant toute la durée du déplacement entre les cellules H et V. Le coût local TH. (t) est par exemple utilisé dans l'algorithme 35 de propagation d'onde classique. II est par exemple défini par : TH,v(t)=-(wx(t).Gx+w,,(t).ôy)+~1v2.(&2+vJ2)-(wx(t). -wy.(t).&)2 (1) VVV V2 - w(t)2 OÙ 5 x = Xv û XH et 8y = Yv YH Dans la mesure où les vecteurs vitesse de courant w évoluent au cours du temps, le coût local zH v (t), grandeur scalaire, doit être adapté afin d'anticiper l'impact de cette évolution, autrement dit afin de prendre en compte les différentes cartes de courants Ci. Dans un mode de réalisation, on introduit une fonction de coût local zH ,v (t) définie à partir du coût local zH v (t) de la manière suivante : • pour t>-T, 1 o zH,v (t) = rH,v (T) (2.1) • ViE[l,k], o pour t{t;_1;t rH,v (t) = rH.v (t;-1) (2.2) o pour tE[t;-rHV(t;_,),t;], 15 zH1 (t)_ zH,v(tr) -1 .t+ zH,v(t;)ùt; zHv(t;) _1\ (2.3) rH,v (ti-1) zH,v (ti-I) Conformément aux équations 2.1 à 2.3, la fonction de coût local rH' ,v (t) est définie par tronçons pour plusieurs intervalles de temps, une transition étant susceptible de se produire aux instants t; et t; - zH v (t;_,) pour i variant de 1 20 à k -1. Les intervalles de temps [t;_, ;t; - zH v (t;_, )], pour i variant de 1 à k -1, correspondent aux instants pour lesquels le parcours entre les points de passage 3 des cellules H et V est effectué intégralement dans la carte de courants C; . La fonction de coût local rH' ,v (t) a une valeur constante sur cet intervalle. Les intervalles de temps [t;_,;t; - zH v (t;_, )], pour i variant de 1 à 25 k -1 correspondent aux instants pour lesquels le parcours entre les points de passage 3 des cellules H et V est effectué en partie dans la carte de courants C. et en partie dans la carte de courants C;+, . La portion de parcours effectuée dans la carte de courants C. est proportionnelle à l'intervalle de temps séparant la date de départ de la cellule H de l'instant t; . 30 Cette proportionnalité concorde avec la forme de l'équation 2.3, zH v (t) = m.t + p , m et p étant deux constantes réelles. Dans certains cas, il peut arriver que l'instant t; - zH ,, (ti_1) précède l'instant t;_, . Ce cas correspond à la situation dans laquelle le temps de parcours rH V (t;_1) est supérieur à la durée de vie de la carte de courants C, , c'est-à-dire la durée t, . Dans ce cas, les équations 2.2 et 2.3 peuvent être remplacées par l'équation suivante : o pour t E [t _,;t ], rH (t) = ( rH,V (ti) -1 t + rH,V (t,) û ti •/ 'Jiu (t;) -1 (2.4) TH,V (ti-1) rH,V (ti-l) La figure 5 illustre, à travers un graphe 51, un exemple de fonction de coût local r~, v (t) entre deux cellules H et V. Ce graphe 51 représente la 1 o fonction de coût local rN ,v (t) en fonction du temps t pour cinq (k = 5) cartes de courants Ci. On considère par conséquent une carte de courants Cl entre les instants t = to = 0 et t = t1, une carte de courants C2 entre les instants t = t1 et t = t2 , une carte de courants C3 entre les instants t= t2 et t = t3, une carte de courants C4 entre les instants t = t3 et t = t4 et une carte 15 de courants C5 entre l'instant t = t4 et l'infini. Le graphe 51 comporte une succession de segments de droites reliés entre eux aux instants t; et t; ù rH v (t;-1) pour i variant de 1 à k -1. Sur ce graphe 51, les segments de droite 521, 523 et 524 de pente nulle correspondent aux équations 2.2, les segments de droite 5201, 5223 et 5234 de pente non nulle correspondent 20 aux équations 2.3, le segment de droite 5212 correspond à l'équation 2.4 et le segment de droite 525 de pente nulle correspond à l'équation 2.1. Dans le cas où les vecteurs vitesse de courants wH et wV respectivement associés aux cellules H et V diffèrent en module et/ou en direction l'un de l'autre, le coût local rH V (t) nécessite d'être décomposé en 25 deux parties. En considérant un point de jonction J entre les cellules H et V, comme représenté à la figure 6, une première partie du coût local rH ,v (t) correspond au coût rH j(t) entre le point de passage 3 de la cellule H et le point de jonction J et une deuxième partie correspond au coût local rj ,v (t) entre le point de jonction J et le point de passage 3 de la cellule V. 30 Selon l'algorithme de propagation d'onde classique, le coût cV associé à une cellule V peut être déterminé par une addition du coût cH associé à une cellule H et du coût local rH V (t). Selon le procédé de planification de trajectoire, les coûts cZ (d) associés à une cellule Z ainsi que les coûts locaux r' ,v (t) entre deux cellules H et V ne sont plus des nombres mais des fonctions. L'opération d'addition peut ainsi être remplacée par une opération de composition définie sur la fenêtre temporelle W par la relation 5 suivante : cv (d) = [r' ,,v ° (cH + d )Jld) (3) Conformément à cette relation 3, la fonction de coût local rH v (t) n'est pas composée avec la fonction de coût cH (d) , mais avec la fonction cH(d)+d. En effet, la fonction de coût cH(d) représente, pour chaque date 10 de départ d, le temps de parcours nécessaire pour atteindre la cellule H, et non la date d'arrivée à la cellule H. L'ajout de la date de départ d à la fonction de coût cH (d) permet ainsi d'obtenir la date d'arrivée à la cellule H, et donc la date de départ de la cellule H vers la cellule V. 15 Dans l'algorithme de propagation d'onde classique, une opération de minimum est effectuée lors de la détermination du coût cv associé à une cellule V. Cette opération de minimum permet de comparer des provenances concurrentes, par exemple HI et H2, pour une même cellule d'arrivée V et de sélectionner la trajectoire de coût minimal. En pratique, les coûts c. et c12,, 20 correspondant respectivement aux temps de parcours entre HI et V et entre H2 et V, sont comparés et le minimum de ces deux coûts est associé à la cellule V. Dans le procédé de planification de trajectoire selon l'invention, l'opération de minimum peut être appliquée aux fonctions de coût cv(d) sur la fenêtre temporelle W. L'exposant i de cv (d) symbolise les différentes 25 trajectoires en concurrence pour parvenir à la cellule V. Autrement dit, la fonction de coût cv (d) correspond au minimum des fonctions de coût c,, (d) pour chaque date de départ d. Il est à noter que, selon le procédé de planification de trajectoire, la trajectoire optimale entre la cellule de départ ZA et une cellule Z peut évoluer en fonction de la date de départ d. 30 La figure 7 illustre l'opération de minimum appliquée au procédé de planification de trajectoire selon l'invention. Dans cette figure, on considère deux cellules HI et H2 appartenant à la tête He du front d'onde Fo et une cellule V adjacente aux cellules HI et H2. Chaque cellule HI, H2 est développée successivement et permet de construire une fonction de coût 35 c v (d) et c. (d) respectivement. La fonction de coût cv (d) obtenue correspond alors au minimum des fonctions de coût c,,(d) et cv(d) sur la fenêtre temporelle W. Selon un mode particulier de réalisation du procédé de planification de trajectoire, les cellules Z de la tête H du front d'onde F sont développées successivement. L'opération de minimum peut alors consister à minimiser deux fonctions, à savoir la fonction de coût cj,(d) précédemment associée à la cellule V et la fonction de coût c. (d) correspondant à une trajectoire passant par la cellule Z en cours de développement. 10 A l'issue de la boucle 32 de propagation du front d'onde F, soit lorsque le point d'arrivée B appartient à la tête H du front d'onde F, il est possible de déterminer conjointement la date de départ optimale dB et la trajectoire optimale permettant de relier le point de départ A au point d'arrivée B. En effet, une fonction de coût cB(d) a été construite pour la 15 cellule d'arrivée ZB. Une telle fonction est par exemple représentée à la figure 8. La détermination du minimum cB (dB) de la fonction de coût cB (d) permet de déterminer la date de départ optimale dB pour parvenir à la cellule d'arrivée ZB. II reste alors à déterminer la trajectoire optimale. Pour cela, les fonctions de coût cz(d) de toutes les cellules Z de la grille 2 sont évaluées à 20 la date de départ dB. Un coût particulier, égal à cZ (dB) , étant attribué à chaque cellule Z, le problème de la détermination de la trajectoire optimale est alors comparable au problème de détermination de trajectoire optimale de l'algorithme de propagation d'onde classique. Les méthodes usuellement appliquées à l'algorithme de propagation d'onde classique peuvent alors être 25 appliquées de la même manière au procédé de planification de trajectoire selon l'invention. En particulier, la trajectoire optimale peut être déterminée par l'algorithme de "hill climbing". Le procédé de planification de trajectoire selon l'invention permet 30 par conséquent de déterminer conjointement la trajectoire optimale et la date de départ optimale pour un mobile devant se déplacer entre un point de départ A et un pont d'arrivée B dans des conditions de courants variables dans l'espace et dans le temps. REVENDICATIONS1. Procédé de planification d'une trajectoire d'un mobile entre un point de départ (A) et un point d'arrivée (B) situés dans un environnement (1) donné en présence de courants, l'environnement (1) étant discrétisé en plusieurs cellules (Z) comportant chacune un point de passage (3) possible pour le mobile, à chaque cellule (Z) étant associé un vecteur vitesse de courant (wZ) variable dans le temps et un coût cZ (d ), caractérisé en ce que, le coût cZ (d) associé à une cellule (Z) représentant le temps de parcours entre le point de départ (A) et le point de passage (3) de ladite cellule (Z) en fonction d'une date de départ (d) du point de départ (A) comprise dans une 10 fenêtre temporelle (W ), ledit procédé comporte les étapes suivantes : • initialiser (31) les fonctions de coût cz(d) des cellules (Z) de l'environnement (1) et attribuer à un ensemble Fo de cellules (F) la cellule (ZA) contenant le point de départ (A), • réitérer les étapes (32) suivantes tant que (325) le point d'arrivée (B) 15 n'est pas contenu dans un ensemble He de cellules (Z) : o déterminer (321), parmi l'ensemble Fo de cellules (F), l'ensemble He de cellules (H) pour lesquelles le minimum cH (dH) de la fonction de coût cH (d) est minimal, o déterminer (322) un ensemble Vo de cellules (V) adjacentes 20 aux cellules (H) de l'ensemble He et n'ayant pas déjà appartenu à l'ensemble He, o déterminer (323) une fonction de coût c,,(d) pour chaque cellule (V) de l'ensemble Vo, o supprimer (324) de l'ensemble Fo, les cellules (H) appartenant 25 à l'ensemble He et ajouter à cet ensemble Fo les cellules (V) appartenant à l'ensemble Vo, • déterminer la trajectoire du mobile à partir des fonctions de coûts cZ (d) . 30 2. Procédé selon la revendication 1, caractérisé en ce que l'étape (323) de détermination de la fonction de coût c,,(d) comprend une étape consistant à déterminer le minimum de différentes fonctions de coût c;, (d) pour chaque date de départ (d) de la fenêtre temporelle (W), chaque fonction de coût cv(d) correspondant au temps de parcours d'une trajectoireentre le point de départ (A) et le point de passage (3) de la cellule (V) considérée et passant par l'une des différentes cellules (Hi) de l'ensemble He. 3. Procédé selon l'une des revendications 1 ou 2, caractérisé en ce que l'étape (323) de détermination de la fonction de coût cv (d) comprend une étape consistant à composer une fonction de coût local rH ,, (t), représentant un temps de déplacement entre le point de passage (3) d'une cellule (H) considérée parmi l'ensemble He et le point de passage (3) de la 1 o cellule (V) considérée parmi l'ensemble Vo, avec la fonction de coût c11(d) associée à la cellule (H) considérée parmi l'ensemble He selon la relation : c,, (d) _ [r'Hv o (cH + d)](d). 4. Procédé selon la revendication 3, caractérisé en ce que, des 15 cartes de courants Ci , i étant un entier compris entre 1 et k , modélisant les vecteurs vitesse des courants wZ entre des instants t = ti_1 et des instants t = ti dans un repère (O, x, y), les instants t = to = 0 et t = tk =T formant les bornes de la fenêtre temporelle (W), la fonction de coût local z- ,, (t) est définie à partir d'un coût local rH, (t) par les relations : 20 • pour ttk, r'Hv(t)=rHV(T), Vi E [1, k] , Si ti - rH,V (ti-1 ) ! ti-I o pour te[t_,;t rH,V (t) - rH,V (ti-1) , 25 o pour tE[t;}t;], r t _ rH,V (t,) r - l~.t + H,V O \ \r H ,i�ç1) , Vi [1, k] , si ti -rH y (ti_, ) 5. Procédé selon l'une quelconque des revendications 3 ou 4, caractérisé en ce que, dans le cas où les vecteurs vitesse de courants wH et associés aux cellules (H, V) considérées différent l'un de l'autre, le coût local rH ,, (t) est décomposé en un premier coût local rH, (t) représentant le temps de parcours entre le point de passage (3) de la première cellule (H) considérée et un point d'intersection (J) des deux cellules (H, V) considérées et un deuxième coût local r,,, (t) représentant le temps de parcours entre le point d'intersection (J) des deux cellules (H, V) considérées et le point de passage (3) de la deuxième cellule (V) considérée. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape (31) d'initialisation des fonctions de coûts cz(d) comprend une étape consistant à attribuer à chaque cellule (Z) une fonction de coût cZ (d) constante sur la fenêtre temporelle (W) et de 25 valeur infinie. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de détermination de la trajectoire du mobile comprend les sous-étapes suivantes : 30 • déterminer une date de départ (dB) correspondant au minimum (cB (dB )) de la fonction de coût cB (d) associée à la cellule (ZB) contenant le point d'arrivée (B), • évaluer les fonctions de coût cz(d) de toutes les cellules (Z) de l'environnement (1) à ladite date de départ (dB ),• déterminer une séquence de cellules (Z) partant de la cellule (ZB) contenant le point d'arrivée (B) et rejoignant la cellule (ZA) contenant le point de départ (A) en passant par les cellules (Z) dont les valeurs des fonctions de coût (cz (dB)) évaluées à la date de départ (dB) sont minimales.