Brevet FR2918471A1 — publié le 20090109

Domaine de l'invention La présente invention concerne un procédé de planification d'une trajectoire de déplacement, notamment pour un engin volant comprenant les étapes suivantes : a. on discrétise un domaine compris entre un point de départ et un point de destination en établissant un premier réseau de points d'appui, b. on détermine une trajectoire en polygone, optimale du point de vue de paramètres d'optimisation prédéterminés parmi les trajectoires en polygone possibles passant par le point de départ et le point de des- tination et par le premier réseau de points d'appui, et c. on affine la trajectoire en polygone, optimale, déterminée dans l'étape b) Etat de la technique Les engins que l'on veut déplacer entre différents emplacements (appelés ici points de départ et points de destination) avec de nombreux trajets possibles posent le problème de la détermination en tenant compte d'au moins un paramètre d'optimisation tel que par exemple la durée minimale de déplacement ou le risque, pour obtenir un trajet optimum de manière fiable et sans nécessiter la mise en oeuvre de moyens trop importants. En particulier pour un vol à basse altitude, la difficulté est celle de la programmation d'un trajet de vol, car le vol en ligne droite avec montée et descente en permanence de l'engin volant suivant le profil en altitude du paysage le long du trajet est une solution défavorable de façon générale du point de vue de la durée du vol et de la consommation en carburant. Egalement du point de vue de la sécurité, c'est-à-dire d'une couverture aussi bonne que possible de l'engin volant pendant son vol, en général un vol en ligne droite n'est pas avantageux, car il ne tient pas compte des possibilités de couverture. On doit éviter si possible de grandes surfaces d'eau ainsi que des sommets de montagne à cause de la faible couverture qu'ils offrent. Le cas échéant, pendant le vol il faut modifier la trajectoire préprogrammée car brusquement apparaît un obstacle ou une zone à risque. Il serait alors très souhaitable de faire une nouvelle optimisation de la trajectoire de déplacement pendant le vol en tenant compte de ces nouvelles circonstances. Ce problème d'optimisation de la trajectoire de mouvement ne se pose pas seulement pour les engins volant sans pilote, les véhicules robots ou analogues ; également dans le cas d'engins occupés comme par exemple des avions, on peut envisager de déterminer une trajectoire de vol optimale pour un pilotage automatique de l'engin volant. Le document DE 39 27 299 C2 qui définit le type auquel il est fait référence décrit un procédé de planification de trajectoire de mouvement ; selon ce procédé, on discrétise un domaine situé entre un point de départ et un point de destination en établissant une série de points d'appui. Dans ce procédé connu, on détermine parmi les trajectoires en polygone possibles, passant par le point de départ et le point de destination et par les points d'appui, la trajectoire en polygone, optimale du point de vue d'un paramètre d'optimisation. La précision avec laquelle on peut déterminer la trajectoire en polygone, optimale dépend de la résolution du réseau de points d'appui. Toutefois, le temps nécessaire au calcul de la trajectoire en polygone, optimale augmente fortement avec la résolution du réseau de points d'appui car il faut vérifier l'ensemble du réseau de points d'appui possibles. La planification de la trajectoire de mouvement d'un engin volant doit se faire en temps réel pendant le vol. Cette nécessité de travail en temps réel limite la résolution possible d'un réseau de points d'appui. Dans les situations complexes il peut même arriver que la ré-solution compatible avec la nécessité de travail en temps réel ne soit plus suffisante pour les conditions de vol relatives au terrain. Ce problème est résolu par le procédé décrit dans le document DE 39 27 299 C2 par l'application d'un calcul d'optimisation en continu de la trajectoire en polygone déterminée avec le réseau de point d'appui (par exemple le procédé Ritzsch). L'inconvénient de cette solution est que le calcul d'optimisation en continu ne permet plus de compenser les imprécisions de la planification de la trajectoire de mouvement à cause du ré-seau de points d'appui trop grossier. De plus, il est difficile de modéliser des équations de mouvement complexes et on risque de converger vers un minimum secondaire. But de l'invention La présente invention a pour but de développer un pro-cédé fournissant une trajectoire de mouvement plus précise et plus ro-buste que celle de l'état de la technique,. Exposé de l'invention Ce problème est résolu un procédé caractérisé en ce qu'on affine selon l'étape c) par les étapes suivantes : cl. on discrétise un domaine prédéfini autour de la trajectoire déterminée dans l'étape b) en établissant un second réseau de points d'appui plus finement subdivisé, et c2. on détermine une autre trajectoire plus fine du point de vue des paramètres d'optimisation prédéfinis dans l'étape b) parmi les trajectoires possibles, passant par les points de départ et les points de destination et le second réseau de points d'appui. Le point de départ de l'invention est une première trajectoire en polygone déterminée à partir d'un paramètre d'optimisation donné, cette trajectoire étant choisie parmi les trajectoires en polygone, possibles passant par le point de départ et le point de destination et le premier réseau de points d'appui (étape a) et b)). Selon l'invention, dans une étape cl) on discrétise un domaine prédéfini autour de la trajectoire en polygone obtenue dans l'étape b) précédente. Cette trajectoire qui peut être également appelée trajectoire optimale, peut être par exemple une courbe de vol lissée. L'expression trajectoire désigne ainsi soit une trajectoire en polygone soit une trajectoire de vol . L'établissement du second réseau de points d'appui plus fin peut se fonder sur le premier réseau de points d'appui c'est-à-dire que tous les points du premier réseau de points d'appui sont également des points du second réseau de points d'appui. Pour établir le domaine dans lequel se situent tous les points voisins de réseau d'ordre n par rapport aux points du réseau de la première trajectoire en polygone, n étant un nombre choisi dans l'ensemble de tous les entiers positifs. Le second réseau de points d'appui peut également se choisir sans tenir compte du premier réseau de points d'appui. Pour fixer le domaine dans lequel on définit le second réseau de points d'appui plus fin, on peut utiliser un domaine qui correspond à une distance perpendiculaire par rapport à un point de la première trajectoire en polygone. Pour le cas tridimensionnel simple, le domaine d'un second réseau de points d'appui, plus fin à définir se situe dans un tube de rayon prédéfini, la première trajectoire en polygone constituant l'axe de ce tube. Le rapport de la dimension d'une cellule formée des voisins directs (voisins du premier degré) d'un point du premier réseau de points d'appui a la dimension d'une cellule formée des voisins directs (voisins du premier ordre) d'un point du second réseau de points d'appui doit être égal au moins à 2. La dimension d'une cellule représente selon la dimension de l'espace choisi, le volume ou la surface de la cellule. Le volume peut également avoir une dimension supérieure à 2. A partir de ce second réseau de points d'appui plus fin que le premier réseau de points d'appui, dans l'étape c2) on établit une autre trajectoire en polygone optimisée selon les paramètres prédéfinis dans l'étape b) parmi les trajectoires en polygone passant par le point de départ et le point de destination et le second réseau de points d'appui. Le paramètre d'optimisation donné dans l'étape b) peut être avantageu-sement modifié. La trajectoire en polygone obtenue dans l'étape b) n'est pas nécessairement prise en compte pour l'autre trajectoire en polygone obtenue dans l'étape c2). Dans la détermination de l'autre trajectoire en polygone selon l'étape c2), la trajectoire en polygone résultant de l'étape b) n'a plus d'influence en ce que cette trajectoire est éventuellement l'une des nombreuses trajectoires à partir de laquelle on détermine l'autre trajectoire en polygone. De façon avantageuse selon une autre étape, on affine la trajectoire en polygone, optimale obtenue dans l'étape c2) par un calcul d'optimisation en continu ou un filtrage/lissage en tenant compte des conditions de vol notamment de l'accélération maximale ou du rayon de courbure minimal de la trajectoire de vol. Les trajectoires en polygone, optimales résultant de l'étape b) et/ou de l'étape c2) peuvent se déterminer à partir de trajec- toires en polygone selon un premier mode de réalisation, trajectoires passant par le point de départ et le point de destination et qui sont cal-culées selon l'algorithme Dijkstra ou par programmation dynamique. Les trajectoires en polygone, optimales de l'étape b) et/ou de l'étape c2) peuvent selon un second mode de réalisation, se détermi- ner à partir de trajectoires en polygone passant par le point de départ et le point de destination et qui sont calculées selon l'algorithme Dual-Dijkstra. Le filtrage/lissage peut se faire par exemple par un filtrage passe bas d'ordre n causal ou non causal. Le nombre (n) corres- pond par exemple à 2 si l'on filtre les accélérations ; il correspond à 3 si l'on filtre la dérivée de l'accélération (par exemple la position du véhicule). 20 REVENDICATIONS 1 ) Procédé de planification d'une trajectoire de déplacement, notamment pour un engin volant, comprenant les étapes suivantes : d. on discrétise un domaine compris entre un point de départ et un point de destination en établissant un premier réseau de points d'appui, e. on détermine une trajectoire en polygone, optimale du point de vue de paramètres d'optimisation prédéterminés parmi les trajectoires en polygone possibles passant par le point de départ et le point de destination et par le premier réseau de points d'appui, et f. on affine la trajectoire en polygone, optimale, déterminée dans l'étape b), caractérisé en ce qu' on affine selon l'étape c) par les étapes suivantes : 15 Cl. on discrétise un domaine prédéfini autour de la trajectoire déterminée dans l'étape b) en établissant un second réseau de points d'appui plus finement subdivisé, et c2. on détermine une autre trajectoire plus fine du point de vue des paramètres d'optimisation prédéfinis dans l'étape b) parmi les trajectoires possibles, passant par les points de départ et les points de destination et le second réseau de points d'appui. 2 ) Procédé selon la revendication 1, caractérisé en ce qu' 25 on affine l'autre trajectoire déterminée dans l'étape c2) par un calcul d'optimisation continu ou par un filtrage/lissage en tenant compte des conditions de vol, notamment de l'accélération maximale, du rayon de courbure de vol minimum ou de leur dérivée. 30 3 ) Procédé selon l'une quelconque des revendications 1 ou 2, caractérisé en ce que le rapport de dimension d'une cellule formée à partir du voisin direct d'un point de réseau dans le premier réseau de points d'appui, à la dimension d'une cellule formée à partir du voisin direct d'un point du se- 35 Gond réseau de points d'appui est au moins égal à2.4 ) Procédé selon la revendication 1, caractérisé en ce que dans l'étape b) et/ou dans l'étape c2) on détermine la trajectoire optimale respective à partir des trajectoires passant par le point de départ et le point de destination et qui ont été calculées selon l'algorithme Dijkstra. 5 ) Procédé selon la revendication 1, caractérisé en ce que dans l'étape b) et/ou dans l'étape c2) on détermine la trajectoire optimale respective à partir des trajectoires passant par le point de départ et le point de destination et qui ont été calculées selon l'algorithme Dual-Dijkstra. 6 ) Procédé selon la revendication 1, caractérisé en ce que dans l'étape b) et/ou c2) on tient compte de plusieurs paramètres d'optimisation pondérés sélectivement, notamment d'un risque minimum et/ou de la rapidité, ou d'un risque minimum et/ou d'une con- sommation de carburant.25