Brevet FR2862379A1 — publié le 20050520

PROCEDE DE DETERMINATION D'UN TRAJET DE LONGUEUR MINIMALE EN PRESENCE D'OBSTACLE L'invention est relative à la détermination d'un trajet de longueur minimale reliant un point de départ à un point d'arrivée en contournant un ou des obstacles. Cette détermination s'impose dans différentes situations et notamment, en aéronautique, lorsqu'un aéronef doit rallier une position en contournant un relief. Elle concerne plus précisément une telle détermination en présence d'une carte de distances tenant compte des obstacles et ayant le point de départ pour origine des mesures de distance. Les cartes de distances sont souvent réalisées en utilisant une transformée de distance par propagation également connue sous la 10 dénomination de transformée de distance de chanfrein. Les transformées de distance de chanfrein sont apparues initialement en analyse d'image pour estimer des distances entre objets. Gunilla Borgefors en décrit des exemples dans son article intitulé " Distance Transformation in Digital Images." Paru dans la revue: Computer Vision, Graphics and Image Processing, Vol. 34 pp. 344-378 en février 1986. Les transformées de distance de chanfrein estiment, dans une image et de manière plus ou moins précise, la distance euclidienne séparant un pixel dit pixel but d'un autre pixel dit pixel source à partir de la longueur du trajet le plus court, allant du pixel source au pixel but en passant par des pixels de l'image, choisi parmi une sélection limitée des différents trajets possibles qui ne prend en compte que les trajets passant par des points proches voisins du point but et empruntant, sur leurs parties allant du point source à un point proche voisin, le trajet le plus court déterminé au cours d'estimations de distance effectuées antérieurement. Pour réaliser la sélection limitée des trajets servant à établir une estimation de distance d'un point but, les transformées de distance de chanfrein analysent, tour à tour, tous les pixels d'une image, au cours d'un balayage complet de l'image justifiant le terme de propagation à la surface de l'image Pour que la sélection de trajets effectuée pour chaque pixel de l'image renferme à coup sûr un trajet de longueur minimale, le balayage doit satisfaire une contrainte de régularité. G. Borgefors propose, pour satisfaire cette contrainte de régularité, de balayer les pixels d'une image deux fois consécutivement, dans deux ordres inverses l'un de l'autre, qui sont soit l'ordre lexicographique, l'image étant analysée de haut en bas, ligne par ligne et de gauche à droite au sein de chaque ligne, et l'ordre lexicographique inverse, soit l'ordre lexicographique transposé, l'image ayant subi une rotation de 90 , et l'ordre lexicographique transposé inverse. L'analyse d'un pixel se fait au moyen d'un masque de chanfrein répertoriant les distances séparant le pixel en analyse des pixels les plus proches dans les différentes directions, le maillage des pixels de l'image étant supposé régulier. Elle consiste à sélectionner les pixels du proche voisinage qui, d'une part ont déjà reçu une estimation de distance au cours de la même passe de balayage et qui, d'autre part ont leurs distances au pixel en analyse mentionnées dans le masque de chanfrein, à répertorier les trajets allant, au plus court, du pixel source au pixel en analyse en passant par les différents pixels sélectionnés du proche voisinage, à estimer les longueurs de chacun de ces trajets par sommation de la distance estimée pour le pixel du proche voisinage emprunté par le trajet considéré et de la distance de ce même pixel du proche voisinage au pixel en analyse, et à assimiler la distance du pixel en analyse à la plus courte longueur des trajets répertoriés. Les transformées de distance de chanfrein s'accommodent des obstacles à contourner puisqu'il suffit d'imposer, aux points de ceux-ci, des valeurs de distance non modifiables, supérieures aux distances mesurables dans l'image afin que les plus courts trajets les évitent. Pour appliquer une transformée de distance de chanfrein à une carte géographique, il suffit d'ajouter un maillage à la carte et de considérer les noeuds du maillage comme les pixels d'une image. Les transformées de distance de chanfrein ont divers intérêts dont les principaux sont: une réduction de la complexité des calculs d'une estimation de distance euclidienne grâce à un emploi exclusif de nombres entiers fait au prix d'approximations et une complexité de calcul qui, tout en étant moindre, reste constante et n'augmente pas avec la présence d'obstacles dans l'image contrairement à la complexité du calcul classique de distance euclidienne qui croît avec la présence d'obstacles dans l'image. Les transformées de distance de chanfrein estiment les distances des points d'une image par rapport à un point origine des distances en déterminant le plus court chemin reliant chaque point de l'image au point origine des distances en contournant les obstacles mais ne mémorisent pas les tracés de ces plus courts chemins car cela nécessiterait de mobiliser des capacités de mémoire considérables pour un intérêt limité puisque l'on se s'intéresse jamais à tous les tracés des plus courts chemins reliant les points d'une image au point origine des distances mais seulement à un très petit nombre d'entre eux. Pour tracer le cheminement d'un robot vers un point de destination sur une surface parsemée d'obstacles à contourner, il est connu de construire par arborescence, sur une carte de distances préétablie 1 o répertoriant les obstacles à contourner et ayant la position de départ du robot pour origine des distances, des cheminements partant du point de destination et cherchant à aller en direction de la position de départ du robot, en sélectionnant, à chaque fois que plusieurs possibilités se présentent au cours de la progression des cheminements, le pixel dont la distance estimée est la plus courte par rapport à la position de départ, cela jusqu'à atteindre la position de départ. Cette méthode arborescente de construction qui s'apparente à une méthode du gradient est coûteuse en temps de calcul car les directions suivies par le cheminement recherché sont mal connues en raison de la présence des obstacles, ce qui oblige à prendre en considération les cheminements en direction de la position de départ situés dans un large secteur centré sur le point de destination et orienté vers la position de départ. La présente invention a pour but de faciliter la détermination du tracé, au moyen de carte de distances, d'un trajet de longueur minimale reliant un point de départ à un point de destination tout en contournant des obstacles. Elle a pour objet un procédé de détermination d'un trajet de longueur minimale pour relier un point de départ à un point de destination tout en contournant d'éventuels obstacles, mettant en oeuvre une carte de distances, qui couvre une zone d'évolution contenant les points de départ et de destination, et le ou les obstacles à contourner, et dont chaque point est affecté d'une valeur de distance correspondant à une estimation de la longueur minimale des trajets contournant le ou les obstacles et reliant le point considéré au point de départ pris pour origine des mesures de distance. Ce procédé est remarquable en ce qu'il consiste à établir une deuxième et une troisième carte de distances couvrant la même zone d'évolution que la première carte de distances, la deuxième carte de distances ayant le point de destination pour origine des mesures de distance et la troisième carte de distances ayant une valeur de distance affectée à chacun de ses points correspondant à la somme des valeurs de distance affectées au même point dans les première et deuxième cartes de distances, et à adopter, comme tracé de trajet, un tracé reliant le point de départ au point d'arrivée en passant par des points intermédiaires ayant, dans la troisième carte de distances, les valeurs de distance affectées les plus petites possibles. En effet, les valeurs de distance affectées aux points de la première carte de distances représentant les longueurs minimales des chemins les reliant au point de départ en contournant les obstacles et celles affectées aux mêmes points dans la deuxième carte de distances représentant les longueurs minimales des chemins les reliant au point de destination toujours en contournant les obstacles, leur somme représente pour chaque point la longueur minimale des trajets allant du point de départ au point de destination en passant par ce point. Ainsi, lorsque l'on choisit sur la troisième carte de distances un chemin allant du point de départ au point de destination en passant par les points intermédiaires affectés des plus petites valeurs de distance possibles, on est sûr d'emprunter un chemin de longueur minimale puisqu'un chemin plus court devrait nécessairement passer par des points affectés de valeurs moindres de distance. Avantageusement, les cartes de distances sont tracées au moyen d'une transformée de distance de chanfrein. Avantageusement, lorsque plusieurs possibilités de tracés passant par des points intermédiaires affectés, sur la troisième carte de distances, des plus petites valeurs possibles de distance se présentent, on choisit le moins sinueux. D'autres caractéristiques et avantages de l'invention ressortiront de la description ci-après d'un mode de réalisation donné à titre d'exemple. 35 Cette description sera faite en regard du dessin dans lequel: une figure 1 représente une première carte de distances couvrant une zone d'évolution renfermant un point de départ et un point de destination ainsi que des obstacles à contourner, et ayant le point de départ pour origine des mesures de distance, une figure 2 représente une deuxième carte de distances couvrant la même zone d'évolution que celle de la figure 1 mais avec le point de destination comme origine des mesures de distance, une figure 3 représente une troisième carte de distances couvrant la même zone d'évolution que celles des figures 1 et 2 mais avec des valeurs de distance correspondant aux sommes des valeurs de distance des cartes de distances des figures 1 et 2, une figure 4 représente un exemple de localisation d'un point de départ et d'un point d'arrivée par rapport à un obstacle où il existe plusieurs trajets de longueur minimale contournant l'obstacle, une figure 5 représente un exemple de masque de chanfrein, et des figures 6a et 6b montrent les cellules du masque de chanfrein illustré à la figure 1, qui sont utilisées dans une passe de balayage selon l'ordre lexicographique et dans une passe de balayage selon l'ordre lexicographique inverse, Une carte de distances sur une zone d'évolution est formée de l'ensemble des valeurs des distances des points placés aux noeuds d'un maillage régulier de la zone d'évolution par rapport à un point de la zone pris pour origine des mesures de distance. Comme montré aux figures 1 à 3, elle peut être présentée sous la forme d'un tableau de valeurs dont les cases correspondent à un découpage de la zone d'évolution en cellules centrées sur les noeuds du maillage. Pour le pilotage d'un mobile, elle est établie de manière à couvrir une zone d'évolution du mobile, avec une origine des mesures des distances correspondant à la position instantanée du mobile dans sa zone d'évolution. Elle n'est pas affichée directement mais sert à la 10 15 20 construction d'une carte qui, elle, est affichée et représente la zone d'évolution par régions en fausses couleurs délimitées en fonction de la possibilité du mobile à les franchir et du temps que celui-ci mettrait à les atteindre (par exemple: rouge pour des obstacle infranchissables, jaune pour les régions lointaines d'accès et verte pour les régions proches d'accès). La figure 1 est un exemple simplifié de carte de distances facilitant la compréhension de l'invention. Cette carte de distances couvre une zone d'évolution d'un mobile sensé être au point S et cherchant à se rendre à un point de destination T en contournant des obstacles infranchissables 10 et 11. Elle a été établie à l'aide d'une transformée de distance de chanfrein dont le principe est explicité par la suite, cette transformée de distance de chanfrein étant la plus simple des transformées de distance proposées par Gunilla Borgefors, à masque de chanfrein de dimension 3x3 avec deux distances de voisinage. Le masque de chanfrein de cette transformée de distance ne renferme que les deux premières valeurs de distance de voisinage d'un point et utilise un coefficient amplificateur d'échelle de 3. Dans ce masque, la première distance de voisinage correspondant à l'écartement des points du maillage selon les lignes et les colonnes est prise égale à 3 tandis que la deuxième distance de voisinage correspondant à l'écartement des points du maillage selon les diagonales est prise égal à 4. Les cellules de la zone d'évolution appartenant ou interceptant un obstacle infranchissable 10 ou 11 sont mises hors de portée du mobile en leur imposant, a priori, une estimation de distance de valeur infinie ou, à tout le moins, très supérieure à la plus grande distance mesurable par la transformée de distance. La cellule correspondant à la position instantanée S du mobile, utilisée comme origine des mesures de distance a, par définition, une valeur de distance estimée nulle. Les autres cellules se voient affecter, pour valeur de distance, les longueurs minimales des trajets les reliant à la position instantanée S du mobile tout en contournant les obstacles 10 et 11. La distance augmente avec l'éloignement des cellules de la position instantanée S du mobile et avec l'importance des détours à faire pour contourner les obstacles 10, 11. Ainsi les cellules qui sont hors de la vision directe de la position instantanée S du mobile, derrière l'obstacle 11 ont des valeurs de distance très supérieures à celles placées en vision directe de la position instantanée du mobile, de l'autre côté de l'obstacle 11. Par exemple la cellule 13 a une valeur de distance égale à 71 alors que la cellule 14 qui lui est relativement proche a une valeur de distance égale à 31 Les transformées de distance de chanfrein permettent d'obtenir progressivement des estimations de distance pour toutes les cellules extérieures aux contours des obstacles infranchissables par un effet de propagation dû au déplacement du masque de chanfrein au cours d'un balayage de la zone d'évolution couverte par la carte. En raison de cet effet de propagation, elles n'accèdent que de manière implicite aux tracés des io chemins de longueur minimale reliant chaque cellule si bien que la simple construction d'une carte de distances avec la position instantanée du mobile pour origine des mesures de distance ne permet pas, à elle seule, de connaître le tracé d'un chemin de longueur minimale menant de la position instantanée S du mobile à un point de destination T et que l'on emploie habituellement, pour ce faire, une méthode de tracé arborescente partant du point de destination T en direction du point de départ S qui est coûteuse en temps de calcul et consommatrice de mémoire comme indiqué dans le préambule. On propose ici de procéder différemment et de mettre à profit la maîtrise de l'établissement des cartes de distances que l'on a nécessairement dans le cas d'un mobile en raison des fréquentes remises à jour de la carte de distances nécessaires au suivi des déplacements du mobile, pour déterminer un chemin de longueur minimum allant de la position instantanée S du mobile au point de destination T. On commence par établir une deuxième carte de distances couvrant la même zone d'évolution que la première carte de distances mais ayant le point de destination T pour origine des mesures de distance. Cette deuxième carte de distances représentée à la figure 2 reprend le même maillage et la même transformée de distance de chanfrein que la première carte de distances mais avec une valeur de distance estimée nulle imposée à la cellule contenant le point de destination T et non à la cellule contenant la position du point de départ S. Dans cette deuxième carte de distances, les cellules de la zone d'évolution interceptant les obstacles infranchissables 10, 11 sont toujours sont mises hors de portée du mobile en leur imposant, a priori, une estimation de distance de valeur infinie ou, à tout le moins, très supérieure à la plus grande distance mesurable par la transformée de distance. Mais les autres cellules, exceptée celle contenant le point de destination, se voient affecter, pour valeur de distance, les longueurs minimales des trajets les reliant au point de destination T tout en contournant les obstacles 10 et 11. On remarque que l'estimation de distance faite, dans cette deuxième carte de distances, pour la cellule contenant le point de départ S est la même: 57, que celle faite pour la cellule contenant le point de destination T dans la première carte de distances, ce qui est très rarement le cas pour d'autres cellules. Une fois la deuxième carte de distances établie, on en établit une troisième couvrant la même zone d'évolution que les deux premières, toujours avec le même maillage mais en affectant aux cellules la somme des deux estimations de distance qui leur ont été affectées dans les deux premières cartes de distances. Cette troisième carte de distances représentée à la figure 3 renferme pour chaque cellule, une valeur de distance correspondant à la somme des estimations de la longueur minimale des trajets reliant la cellule considérée à la cellule contenant le point de départ S et de la longueur minimale des trajets reliant la cellule considérée au point de destination T. Or cette somme d'estimations n'est, ni plus ni moins, que l'estimation de la longueur minimale des trajets allant du point de départ au point d'arrivée et ayant la contrainte de passer par la cellule considérée. Lorsqu'elle a une valeur minimale sur la troisième carte de distances, la contrainte de passage par la cellule considérée n'est pas une car la cellule considérée appartient à un trajet de longueur minimale allant de la cellule contenant le point de départ S à la cellule contenant le point de destination T. En effet, si ce n'était pas le cas, il existerait dans la troisième carte de distances, au moins une valeur de distance plus petite que cette valeur minimale, ce qui est impossible. On peut donc construire au moyen de la troisième carte de distances le tracé d'un trajet de longueur minimale reliant le point de départ S au point de destination T en se déplaçant du point de départ S au point de destination T ou inversement, en n'empruntant que des cellules intermédiaires marquées d'une distance minimale. Cela est toujours possible dès que la cellule contenant le point de destination T a, dans la première carte de distances, une distance estimée accessible, inférieure à une limite fixée en fonction de l'autonomie du mobile. Lors de cette construction, plusieurs possibilités peuvent se présenter, on choisit alors le tracé le moins sinueux. Sur la figure 3, ce trajet est montré en pointillés. On remarque que la valeur minimale de distance apparaissant sur la troisième carte de distances est celle 57 affectée soit, sur la première carte de distances, à la cellule contenant le point de destination T soit, sur la deuxième carte de distances, au point de départ S. La figure 4 donne un exemple de situation où il existe plusieurs 10 tracés possibles de longueur minimale ne contournant pas un obstacle infranchissable par le même côté. Pour une meilleure compréhension de ce qui précède, on décrit ci-après le fonctionnement d'une transformée de distance par propagation. La distance d'entre deux points d'une surface est la longueur minimale de tous les parcours possibles sur la surface partant de l'un des points et aboutissant à l'autre. Dans une image formée de pixels répartis selon un maillage régulier de lignes, colonnes et diagonales, une transformée de distance par propagation estime la distance d'un pixel dit pixel "but" par rapport à un pixel dit pixel "source" en construisant progressivement, en partant du pixel source, le plus court trajet possible suivant le maillage des pixels et aboutissant au pixel but, et en s'aidant des distances trouvées pour les pixels de l'image déjà analysés et d'un tableau dit masque de chanfrein répertoriant les valeurs des distances entre un pixel et ses proches voisins. Comme montré à la figure 5, un masque de chanfrein se présente sous la forme d'un tableau avec une disposition de cases reproduisant le motif d'un pixel entouré de ses proches voisins. Au centre du motif, une case affectée de la valeur 0 repère le pixel pris pour origine des distances répertoriées dans le tableau. Autour de cette case centrale, s'agglomèrent des cases périphériques remplies de valeurs de distance de proximité non nulles et reprenant la disposition des pixels du voisinage d'un pixel supposé occuper la case centrale. La valeur de distance de proximité figurant dans une case périphérique est celle de la distance séparant un pixel occupant la position de la case périphérique concernée, d'un pixel occupant la position 2862379 10 de la case centrale. On remarque que les valeurs de distance de proximité se répartissent en cercles concentriques. Un premier cercle de quatre cases correspondant aux quatre pixels de premier rang, qui sont les plus proches du pixel de la case centrale, soit sur la même ligne, soit sur la même colonne, sont affectées d'une valeur de distance de proximité Dl. Un deuxième cercle de quatre cases correspondant aux quatre pixels de deuxième rang, qui sont pixels les plus proches du pixel de la case centrale placés sur les diagonales, sont affectées d'une valeur de distance de proximité D2. Un troisième cercle de huit cases correspondant aux huit pixels 1 o de troisième rang, qui sont les plus proches du pixel de la case centrale tout en restant en dehors de la ligne, de la colonne et des diagonales occupées par le pixel de la case centrale, sont affectées d'une valeur de distance de proximité D3. Le masque de chanfrein peut couvrir un voisinage plus ou moins étendu du pixel de la case centrale en répertoriant les valeurs des distances de proximité d'un nombre plus ou moins important de cercles concentriques de pixels du voisinage. Il peut être réduit aux deux premiers cercles formés par les pixels du voisinage d'un pixel occupant la case centrale comme dans l'exemple des cartes de distances des figures 1 et 2 ou être étendu au-delà des trois premiers cercles formés par les pixels du voisinage du pixel de la case centrale. II est habituel de s'arrêter à trois premiers cercles et ce n'est que dans un but de simplification que l'on s'est arrêté au deux premiers cercles pour les cartes de distances des figures 1 à 3. Les valeurs des distances de proximité Dl, D2, D3 qui correspondent à des distances euclidiennes sont exprimées dans une échelle dont le facteur multiplicatif autorise l'emploi de nombres entiers au prix d'une certaine approximation. C'est ainsi que G. Borgefors adopte une échelle correspondant à un facteur multiplicatif 3 ou 5. Dans le cas d'un masque de chanfrein retenant les trois premiers cercles, elle donne à la distance Dl correspondant à un échelon en abscisse x ou en ordonnée y la valeur 5, à la distance D2 correspondant à la racine de la somme des carrés des échelons en abscisse et ordonnée Jx2 +y2 la valeur 7 qui est une approximation de 5-fi, et à la distance D3 la valeur 11 qui est une approximation de 5,R-. La construction progressive du plus court trajet possible allant à un pixel but, en partant d'un pixel source et en suivant le maillage des pixels se fait par un balayage régulier des pixels de l'image au moyen du masque de chanfrein. Initialement, les pixels de l'image se voient affecter une valeur de distance infinie, en fait un nombre suffisamment élevé pour dépasser toutes les valeurs des distances mesurables dans l'image, à l'exception du pixel source qui se voit affecter une valeur de distance nulle. Puis les valeurs initiales de distance affectées aux points but sont mises à jour au cours du balayage de l'image par le masque de chanfrein, une mise à jour consistant à remplacer une valeur de distance attribuée à un point but, par une nouvelle valeur moindre résultant d'une estimation de distance faite à l'occasion d'une nouvelle application du masque de chanfrein au point but considéré. Une estimation de distance par application du masque de chanfrein à un pixel but consiste à répertorier tous les trajets allant de ce pixel but au pixel source et passant par un pixel du voisinage du pixel but dont la distance a déjà été estimée au cours du même balayage, à rechercher parmi les trajets répertoriés, le ou les trajets les plus courts et à adopter la longueur du ou des trajets les plus courts comme estimation de distance. Cela se fait en plaçant le pixel but dont on veut estimer la distance dans la case centrale du masque de chanfrein, en sélectionnant les cases périphériques du masque de chanfrein correspondant à des pixels du voisinage dont la distance vient d'être mise à jour, en calculant les longueurs des trajets les plus courts reliant le pixel but à mettre à jour au pixel source en passant par un des pixels sélectionnés du voisinage, par addition de la valeur de distance affectée au pixel du voisinage concerné et de la valeur de distance de proximité donnée par le masque de chanfrein, et à adopter, comme estimation de distance, le minimum des valeurs de longueur de trajet obtenues et de l'ancienne valeur de distance affectée au pixel en cours d'analyse. L'ordre de balayage des pixels de l'image influe sur la fiabilité des estimations de distance et de leurs mises à jour car les trajets pris en compte en dépendent. En fait, il est soumis à une contrainte de régularité qui fait que si les pixels de l'image sont repérés selon l'ordre lexicographique (pixels classés dans un ordre croissant ligne par ligne en partant du haut de l'image et en progressant vers le bas de l'image, et de gauche à droite au sein d'une ligne), et si un pixel p a été analysé avant un pixel q alors un pixel p+x doit être analysé avant le pixel q+x. Les ordres lexicographique, lexicographique inverse (balayage des pixels de l'image ligne par ligne de bas en haut et, au sein d'une ligne, de droite à gauche), lexicographique transposé (balayage des pixels de l'image colonne par colonne de gauche à droite et, au sein d'une colonne, de haut en bas), lexicographique transposé inverse (balayage des pixels par colonnes de droite à gauche et au sein d'une colonne de bas en haut) satisfont cette condition de régularité et plus généralement tous les balayages dans lesquels les lignes et colonnes sont balayées de droite à 1 o gauche ou de gauche à droite. G. Borgefors préconise un double balayage des pixels de l'image, une fois dans l'ordre lexicographique et une autre dans l'ordre lexicographique inverse. La figure 6a montre, dans le cas d'une passe de balayage selon l'ordre lexicographique allant du coin supérieur gauche au coin inférieur droit de l'image, les cases du masque de chanfrein de la figure 1 utilisées pour répertorier les trajets allant d'un pixel but placé sur la case centrale (case indexée par 0) au pixel source en passant par un pixel du voisinage dont la distance a déjà fait l'objet d'une estimation au cours du même balayage. Ces cases sont au nombre de huit, disposées dans la partie supérieure gauche du masque de chanfrein. Il y a donc huit trajets répertoriés pour la recherche du plus court dont la longueur est prise pour estimation de la distance. La figure 6b montre, dans le cas d'une passe de balayage selon l'ordrelexicographique inverse allant du coin inférieur droit au coin supérieur gauche de l'image, les cases du masque de chanfrein de la figure 1 utilisées pour répertorier les trajets allant d'un pixel but placé sur la case centrale (case indexée par 0) au pixel source en passant par un pixel du voisinage dont la distance a déjà fait l'objet d'une estimation au cours du même balayage. Ces cases sont complémentaires de celles de la figure 2a. Elles sont également au nombre de huit mais disposées dans la partie inférieure droite du masque de chanfrein. II y a donc encore huit trajets répertoriés pour la recherche du plus court dont la longueur est prise pour estimation de la distance. REVENDICATIONS 1. Procédé de détermination d'un trajet de longueur minimale reliant un point de départ (S) à un point de destination (T) pour permettre à un mobile de rallier une position tout en contournant d'éventuels obstacles, mettant en oeuvre une carte de distances (figure 1), qui couvre une zone d'évolution contenant les points de départ (S) et de destination (T) et le ou les obstacles à contourner (10, 11), et dont chaque point est affecté d'une valeur de distance correspondant à une estimation de la longueur minimale des trajets contournant le ou les obstacles et reliant le point considéré au point de départ (S) pris pour origine des mesures de distance, caractérisé en ce qu'il consiste à établir une deuxième et une troisième cartes de distances couvrant la même zone d'évolution, la deuxième carte de distances (figure 2) ayant le point de destination (T) pour origine des mesures de distances et la troisième carte de distances (figure 3) ayant une valeur de distance affectée à chacun de ses points correspondant à la somme des valeurs de distance affectées au même point dans les première et deuxième cartes de distances, et à adopter comme tracé de trajet, un tracé reliant le point de départ au point d'arrivée en passant par des points intermédiaires ayant, dans la troisième carte de distances, les valeurs de distance affectées les plus petites possibles. 2.Procédé selon la revendication 1, caractérisé en ce que les 25 cartes de distances sont tracées au moyen d'une transformée de distance de chanfrein. 3. Procédé selon la revendication 1, caractérisé en ce que, lorsque plusieurs possibilités de tracés passant par des points intermédiaires affectés, sur la troisième carte de distances, des plus petites valeurs possibles de distance se présentent, on choisit le tracé le moins sinueux.