Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
METHOD FOR DETERMINING THE PATH OF AN UNMANNED AERIAL DEVICE AND OTHER ASSOCIATED METHODS
Document Type and Number:
WIPO Patent Application WO/2021/001768
Kind Code:
A1
Abstract:
A modelling method using digital processing of a three-dimensional environment to establish pathways for unmanned aerial devices which are optimised according to different priorities, the method being characterised in that it comprises the following digital processing steps: (a) providing a three-dimensional model of volumes (PEXi) wherein flight is prohibited, (b) subdividing the model into individual elements (PVk), (c) determining a centre (Pk) for each individual element, (d) establishing and memorising a graph, the nodes (Pk, Ik) of which are formed by at least one portion of the centres, and the branches of which are weighted by the distances between the nodes and by at least one weighting associated with a given priority. A method is also proposed for determining, using an unmanned aerial device, a path between two points in a three-dimensional space modelled by such a graph, and steering methods using such a determination.

Inventors:
PELE, Pierre (FR)
Application Number:
IB2020/056227
Publication Date:
January 07, 2021
Filing Date:
July 01, 2020
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
UAVIA (FR)
International Classes:
G08G5/00; G05D1/10
Attorney, Agent or Firm:
LE FORESTIER, Eric (FR)
Download PDF:
Claims:
Revendications

1. Procédé de modélisation par traitement numérique d’un environnement tridimensionnel en vue de d’établir des chemins de parcours pour des appareils aériens non habités optimisés en fonction de priorités différentes, caractérisé en ce qu’il comprend les étapes de traitement numérique suivantes :

(a) fournir un modèle tridimensionnel de volumes (PEXi) dans lesquels le vol est interdit,

(b) subdiviser le modèle en éléments individuels (PVk),

(c) déterminer un centre (Pk) pour chaque élément individuel,

(d) établir et mémoriser un graphe dont les nœuds (Pk, Ik) sont constitués par au moins une partie desdits centres, et dont les branches sont pondérées par les distances entre les nœuds et par au moins une pondération associée à une priorité donnée.

2. Procédé selon la revendication 1 , dans lequel les priorités comprennent au moins deux priorités parmi une priorité en distance absolue, une priorité en temps de parcours, une priorité en consommation d’énergie, une priorité en risque.

3. Procédé selon l’une des revendication 1 et 2, dans lequel au moins l’une des pondérations dépend d’une contrainte affectant l’ensemble des branches. 4. Procédé selon la revendication 3, dans lequel ladite contrainte comprend un vecteur de contrainte affectant l’ensemble des branches.

5. Procédé selon la revendication 4, dans lequel le vecteur de contrainte est un vecteur de vent, chaque branche possédant une paire de poids associés respectivement au sens de parcours et chaque poids étant assujetti de façon distincte au vecteur de vent. 6. Procédé selon l’une des revendications 1 et 2, dans lequel ladite pondération est telle que des poids différents sont affectés à une même branche selon le sens de parcours, de façon à générer des sens de parcours privilégiés.

7. Procédé selon l’une des revendications 1 et 2, dans lequel ladite pondération est basée sur une cartographie définissant différents niveaux de contraintes en fonction de l’emplacement dans un espace de vol.

8. Procédé selon la revendication 7, dans lequel les niveaux de contraintes sont compris dans un groupe comprenant une contrainte de vitesse maximale autorisée et une contrainte de risque.

9. Procédé selon la revendication 8, dans lequel la contrainte est apte à prendre une valeur telle que la zone correspondante devient une zone de vol interdit.

10. Procédé selon l’une des revendications 1 à 9, dans lequel l’étape (a) comprend la fourniture d’un modèle tridimensionnel comportant des volumes (PEXi) dans lesquels le vol est physiquement impossible, et le retraitement de ce modèle avec des données de marges de sécurité statiques.

1 1 . Procédé selon la revendication 10, dans lequel l’étape (a) comprend la subdivision du modèle tridimensionnel en tranches horizontales (Txy), la projection des volumes sur un plan horizontal étant la même dans toute l’épaisseur de chaque tranche, et la mise en œuvre d’une subdivision en éléments individuels dans chaque plan horizontal.

12. Procédé selon la revendication 11 , dans lequel la subdivision est effectuée par triangulation. 13. Procédé selon la revendication 12, dans lequel la triangulation est une triangulation de Delaunay.

14. Procédé selon l’une des revendications 1 1 à 13, dans lequel l’étape (d) comprend l’établissement de branches du graphe entre des nœuds situés dans des plans horizontaux adjacents par une approche de minimisation de distances.

15. Procédé de détermination par un appareil aérien non habité d’un trajet entre deux points d’un espace tridimensionnel modélisé par un graphe obtenu par le procédé de l’une des revendications 1 à 14, caractérisé en ce qu’il comprend les étapes suivantes :

- détermination d’une priorité pour le parcours du trajet,

- prise en compte ou établissement d’un graphe donné correspondant à la priorité déterminée, et

- élaboration du trajet, à bord de l’appareil, par un calcul de meilleur chemin dans ledit graphe donné.

16. Procédé selon la revendication 15, dans lequel l’étape de pondération des branches du graphe est mise en œuvre par réception à distance d’un graphe de départ à branches non pondérées, et pondération, à bord de l’appareil, desdites branches en fonction de la priorité.

17. Procédé selon l’une des revendications 15 et 16, lequel comprend, au cours du vol, une étape de mise à jour des poids des branches d’au moins une partie du graphe et une étape de recalcul de meilleur chemin dans le graphe.

18. Procédé selon la revendication 17, dans lequel la mise à jour des poids des branches du graphe est effectuée en fonction d’un changement de priorité. 19. Procédé selon la revendication 17 ou 18, dans lequel la mise à jour des poids des branches d’au moins une partie du graphe est effectuée en fonction de la réception de données de pondération modifiées pour la pondération correspondant à la priorité en vigueur.

20. Procédé selon l’une des revendications 15 à 19, dans lequel l’étape de mise à jour des poids des branches du graphe comprend la génération de branches interdites en fonction d’une zone interdite apparaissant dynamiquement.

21 . Procédé selon la revendication 20, dans lequel la zone interdite est déterminée par communication à distance de l’engin avec autre équipement dont la position détermine la zone interdite.

22. Procédé selon la revendication 21 , dans lequel l’autre équipement est un autre appareil aérien non habité.

23. Procédé selon la revendication 22, dans lequel la zone interdite est un palier d’altitude interdit.

24. Procédé selon la revendication 23, dans lequel l’autre équipement est associé à une intervention temporaire sur le site.

25. Procédé selon l’une des revendications 15 à 24, dans lequel le calcul du meilleur chemin est réalisé en fonction d’une contrainte d’agilité de l’appareil.

26. Procédé de pilotage d’un appareil aérien non habité, comprenant les étapes suivantes :

- détermination d’un trajet par le procédé selon l’une des revendications 15 à 25, - application d’au moins une facteur de relâchement de trajectoire,

- détermination d’un écart de trajectoire admissible en fonction du facteur de relâchement, et

- application d’une instruction de correction de trajectoire seulement lorsqu’un écart de trajectoire réel mesuré dépasse d’écart de trajectoire admissible.

27. Procédé selon la revendication 26, dans lequel le facteur de relâchement est déterminé à partir d’au moins une donnée représentative de l’une des informations suivantes : précision courante d’une unité GPS embarquée dans l’appareil, vent, réponse de l’appareil aux commandes de pilotage, encombrement de l’appareil, type d’appareil.

28. Procédé de pilotage d’un appareil aérien non habité, comprenant les étapes suivantes :

- détermination d’un trajet par le procédé selon l’une des revendications 15 à 25,

- mesure d’une caractéristique dynamique de l’engin au cours du vol,

- détermination dynamique d’un nouveau trajet en fonction de l’évolution de ladite caractéristique dynamique.

29. Procédé selon la revendication 28, dans lequel ladite caractéristique dynamique comprend au moins une caractéristique parmi l’énergie disponible à bord et une anomalie de comportement.

30. Procédé selon la revendication 28 ou 29, dans lequel le graphe comprend des nœuds désignant des stations ou zones d’atterrissage, et dans lequel l’étape de détermination dynamique du nouveau trajet prend en compte les positions des nœuds de stations ou zones d’atterrissage. 31. Procédé selon la revendication 30, dans lequel l’étape de détermination dynamique du nouveau trajet prend également en compte des statuts (libre, occupé) des nœuds de stations ou zones d’atterrissage. 32. Procédé selon la revendication 29, lequel comprend une modification de la priorité en cas d’anomalie de comportement.

33. Appareil aérien non habité, caractérisé en ce qu’il comprend des circuits de traitement numérique et de communication sans fil adaptés pour la mise en œuvre en tout ou partie du procédé selon l’une des revendications 1 à 32.

34. Programme d’ordinateur, apte à être chargé à bord d’un appareil aérien non habité, caractérisé en ce qu’il comprend des instructions aptes à mettre en œuvre tout ou partie du procédé selon l’une des revendications 1 à 32.

Description:
Titre : Procédé de détermination de trajet d’un appareil aérien non habité et autres procédés associés

Domaine de l’invention

La présente invention concerne d’une façon générale les appareils aériens non habités ou drones, et en particulier la détermination de trajets pour des drones dans des environnements contraints.

État de la technique

Les drones de surveillance sont de plus en plus largement utilisés pour la surveillance, notamment la surveillance d’ouvrages, de sites sensibles, etc.

On connaît par ailleurs dans la littérature des solutions pour faire décrire à des drones des trajets imposés.

Dans le domaine du vol aérien habité, un plan de vol est une suite de points de passage sans dimensions verticales (cf. par exemple EP1614086A2) choisis à l’avance par l’utilisateur dans le respect des contraintes environnementales et matérielles.

Ce document décrit des techniques de suivi de la trajectoire théorique, prenant en entrée une liste de coordonnées de points de passage et les données de différents capteurs (Lidar, Laser, ...) qui sont traitées pour modifier dynamiquement ladite trajectoire.

L’état de l’art actuel ne propose pas de technique permettant l’établissement automatique d’un programme de vol sous contraintes environnementales et matérielles d’une part et sous contraintes de plus haut niveau déterminées par l’utilisateur.

Ainsi dans l’état de l’art actuel, c’est l’utilisateur d’un UAV a la charge de construire la liste des points de passage permettant à l’engin d’atteindre la destination. L’utilisateur doit construire ce chemin en évitant les obstacles, en prenant en compte l’incertitude de positionnement de l’UAV, en vérifiant que l’énergie nécessaire à l’UAV pour parcourir le chemin soit disponible, etc.

Toujours dans l’état de l’art actuel, un pilote de sécurité doit être présent lors de l’exécution de la mission automatique de l’UAV, de manière à pouvoir reprendre la main en cas de problème. Il aura alors la charge de prendre les bonnes décisions quant aux trajectoires permettant à l’UAV de se rendre en zone sûre.

Résumé de l’invention

La présente invention se propose d’améliorer la génération de programmes de vol automatiques en limitant la nécessité d’interventions humaines au cours du vol, avec une grande souplesse dans la détermination du chemin de vol.

On propose selon un premier aspect un procédé de modélisation par traitement numérique d’un environnement tridimensionnel en vue de d’établir des chemins de parcours pour des appareils aériens non habités optimisés en fonction de priorités différentes, caractérisé en ce qu’il comprend les étapes de traitement numérique suivantes :

(a) fournir un modèle tridimensionnel de volumes (PEXi) dans lesquels le vol est interdit,

(b) subdiviser le modèle en éléments individuels (PVk),

(c) déterminer un centre (Pk) pour chaque élément individuel,

(d) établir et mémoriser un graphe dont les nœuds (Pk, Ik) sont constitués par au moins une partie desdits centres, et dont les branches sont pondérées par les distances entre les nœuds et par au moins une pondération associée à une priorité donnée.

Ce procédé comprend avantageusement mais facultativement les caractéristiques additionnelles suivantes, prises individuellement ou en toutes combinaison que l’homme du métier appréhendera comme étant techniquement compatibles :

* les priorités comprennent au moins deux priorités parmi une priorité en distance absolue, une priorité en temps de parcours, une priorité en consommation d’énergie, une priorité en risque.

* au moins l’une des pondérations dépend d’une contrainte affectant l’ensemble des branches. * ladite contrainte comprend un vecteur de contrainte affectant l’ensemble des branches.

* le vecteur de contrainte est un vecteur de vent, chaque branche possédant une paire de poids associés respectivement au sens de parcours et chaque poids étant assujetti de façon distincte au vecteur de vent.

* ladite pondération est telle que des poids différents sont affectés à une même branche selon le sens de parcours, de façon à générer des sens de parcours privilégiés.

* ladite pondération est basée sur une cartographie définissant différents niveaux de contraintes en fonction de l’emplacement dans un espace de vol.

* les niveaux de contraintes sont compris dans un groupe comprenant une contrainte de vitesse maximale autorisée et une contrainte de risque.

* la contrainte est apte à prendre une valeur telle que la zone correspondante devient une zone de vol interdit.

* l’étape (a) comprend la fourniture d’un modèle tridimensionnel comportant des volumes (PEXi) dans lesquels le vol est physiquement impossible, et le retraitement de ce modèle avec des données de marges de sécurité statiques.

* l’étape (a) comprend la subdivision du modèle tridimensionnel en tranches horizontales (Txy), la projection des volumes sur un plan horizontal étant la même dans toute l’épaisseur de chaque tranche, et la mise en œuvre d’une subdivision en éléments individuels dans chaque plan horizontal.

* la subdivision est effectuée par triangulation.

* la triangulation est une triangulation de Delaunay.

* l’étape (d) comprend l’établissement de branches du graphe entre des nœuds situés dans des plans horizontaux adjacents par une approche de minimisation de distances.

Selon un deuxième aspect, on propose un procédé de détermination par un appareil aérien non habité d’un trajet entre deux points d’un espace tridimensionnel modélisé par un graphe obtenu par le procédé de modélisation tel que défini ci-dessus, caractérisé en ce qu’il comprend les étapes suivantes :

- détermination d’une priorité pour le parcours du trajet,

- prise en compte ou établissement d’un graphe donné correspondant à la priorité déterminée, et

- élaboration du trajet, à bord de l’appareil, par un calcul de meilleur chemin dans ledit graphe donné.

Ce procédé comprend avantageusement mais facultativement les caractéristiques additionnelles suivantes, prises individuellement ou en toutes combinaison que l’homme du métier appréhendera comme étant techniquement compatibles :

* l’étape de pondération des branches du graphe est mise en œuvre par réception à distance d’un graphe de départ à branches non pondérées, et pondération, à bord de l’appareil, desdites branches en fonction de la priorité.

* le procédé comprend, au cours du vol, une étape de mise à jour des poids des branches d’au moins une partie du graphe et une étape de recalcul de meilleur chemin dans le graphe.

* la mise à jour des poids des branches du graphe est effectuée en fonction d’un changement de priorité.

* la mise à jour des poids des branches d’au moins une partie du graphe est effectuée en fonction de la réception de données de pondération modifiées pour la pondération correspondant à la priorité en vigueur.

* l’étape de mise à jour des poids des branches du graphe comprend la génération de branches interdites en fonction d’une zone interdite apparaissant dynamiquement.

* la zone interdite est déterminée par communication à distance de l’engin avec autre équipement dont la position détermine la zone interdite.

* l’autre équipement est un autre appareil aérien non habité.

* la zone interdite est un palier d’altitude interdit.

* l’autre équipement est associé à une intervention temporaire sur le site. * le calcul du meilleur chemin est réalisé en fonction d’une contrainte d’agilité de l’appareil.

Selon un troisième aspect, on propose un procédé de pilotage d’un appareil aérien non habité, comprenant les étapes suivantes :

- détermination d’un trajet par le procédé de détermination défini ci- dessus,

- application d’au moins une facteur de relâchement de trajectoire,

- détermination d’un écart de trajectoire admissible en fonction du facteur de relâchement, et

- application d’une instruction de correction de trajectoire seulement lorsqu’un écart de trajectoire réel mesuré dépasse d’écart de trajectoire admissible.

Avantageusement mais facultativement, le facteur de relâchement est déterminé à partir d’au moins une donnée représentative de l’une des informations suivantes : précision courante d’une unité GPS embarquée dans l’appareil, vent, réponse de l’appareil aux commandes de pilotage, encombrement de l’appareil, type d’appareil.

Selon un quatrième aspect, on propose un procédé de pilotage d’un appareil aérien non habité, comprenant les étapes suivantes :

- détermination d’un trajet par le procédé de détermination défini ci- dessus,

- mesure d’une caractéristique dynamique de l’engin au cours du vol,

- détermination dynamique d’un nouveau trajet en fonction de l’évolution de ladite caractéristique dynamique.

Ce procédé comprend avantageusement mais facultativement les caractéristiques additionnelles suivantes, prises individuellement ou en toutes combinaison que l’homme du métier appréhendera comme étant techniquement compatibles :

* ladite caractéristique dynamique comprend au moins une caractéristique parmi l’énergie disponible à bord et une anomalie de comportement. * le graphe comprend des nœuds désignant des stations ou zones d’atterrissage, et l’étape de détermination dynamique du nouveau trajet prend en compte les positions des nœuds de stations ou zones d’atterrissage.

* l’étape de détermination dynamique du nouveau trajet prend également en compte des statuts (libre, occupé) des nœuds de stations ou zones d’atterrissage.

* le procédé comprend une modification de la priorité en cas d’anomalie de comportement.

On propose par ailleurs un appareil aérien non habité, caractérisé en ce qu’il comprend des circuits de traitement numérique et de communication sans fil adaptés pour la mise en œuvre en tout ou partie d’un quelconque des procédés ci-dessus, ainsi qu’un programme d’ordinateur, apte à être chargé à bord d’un appareil aérien non habité, caractérisé en ce qu’il comprend des instructions aptes à mettre en œuvre tout ou partie d’un quelconque des procédés ci-dessus.

Brève description des dessins

D’autres aspects, buts et avantages de la présente invention apparaîtront mieux à la lecture de la description détaillée suivante de formes de réalisation préférées de celle-ci, donnée à titre d’exemple non limitatif et faite en référence aux dessins annexés, sur lesquels :

- la Figure 1 est une vue de dessus en plan d’un site simplifié sur lequel doit évoluer un UAV,

- la Figure 2 est une vue en élévation du site simplifié de la Figure 1 ,

- la Figure 3 est une vue en perspective du site simplifié des Figures 1 et 2,

- la Figure 4 est une vue analogue à la Figure 1 , montrant des zones de sécurité entourant des zones de vol interdit,

- la Figure 5 est une vue analogue à la Figure 2, montrant des zones de sécurité entourant des zones de vol interdit,

- la Figure 6 est une vue en plan à une première altitude, illustrant une décomposition spatiale possible du site simplifié à cette altitude, - la Figure 7 est une vue en plan à une deuxième altitude, illustrant une décomposition spatiale possible du site simplifié à cette altitude,

- la Figure 8 est une vue en plan à une troisième altitude, illustrant une décomposition spatiale possible du site simplifié à cette altitude,

- la Figure 9 est une vue en plan à une quatrième altitude, illustrant une décomposition spatiale possible du site simplifié à cette altitude,

- la Figure 10 illustre un trajet théorique via des points de la décomposition spatiale de la Figure 6,

- la Figure 11 illustre un trajet corrigé établi à partir des points de la Figure 10, et

- la Figure 12 illustre l’architecture d’ensemble d’un système de drones apte à mettre en œuvre l’invention.

Description détaillée de formes de réalisation préférées

Introduction

Dans la suite on désignera par drone (ou UAV pour « Unmanned Aerial Vehicle » en terminologie anglo-saxonne) un engin aérien non habité et télé- et/ou auto-piloté, équipé de préférence d’une voilure tournante, des drones à aile(s) portantes(s) étant également couverts.

On va décrire ici différents aspects du calcul et de suivi de chemins dynamiques et sécurisés dans un espace de vol tridimensionnel complexe et potentiellement dangereux. On décrira ensuite une architecture capable de mettre en œuvre ces fonctions, en particulier en termes de répartition des tâches liées à ces fonctions entre les engins volants et le sol.

Le système auquel s’applique l’invention comprend un ou plusieurs drones aptes à voler dans un espace donné, ainsi qu’une ou plusieurs stations de recharge a sol. L’invention s’attache en particulier à la recherche de chemin sous contraintes dans cet espace, le respect de la trajectoire calculée ainsi que la réévaluation de la trajectoire et de la destination.

Plus particulièrement, la présente invention vise à permettre à un drone de se déplacer avec la plus grande sécurité dans un espace à trois dimensions, dont une partie de la topologie est connue à l’avance. Cette connaissance permet d’établir une représentation de l’espace de vol, de prendre en compte à la fois les changements dynamiques de cet espace et de changements d’état de l’appareil tels que le niveau de batterie ou l’apparition d’anomalies de comportement, et encore de prendre en compte des priorités données au vol par l’utilisateur ou automatiquement en fonction d’un contexte donné (chemin le plus court, le plus économe en énergie, etc.).

Selon une caractéristique, une unité de traitement construit à partir de données de mission comprenant en particulier les coordonnées d’un point de départ et les coordonnées d’un point à atteindre, une liste de points de passage optimisée du point de vue d’un certain nombre de critères, dont la sécurité du vol.

Cette liste de points de passage est recalculée au cours du temps à chaque fois que la topologie du terrain change, que de nouvelles informations deviennent disponibles ou que des informations précédemment disponibles ne le sont plus.

Ce procédé vise à prendre en compte en temps réel et de manière automatique des effets aussi variés qu’une baisse de la qualité du réseau dans une certaine zone de l’espace, une obligation de déplacement à sens unique sur une certaine zone, les coordonnées d’une station de recharge disponible, la présence d’autres drones au voisinage de la trajectoire, etc.

L’espace de vol tridimensionnel fourni comme données d’entrée est un volume fini pouvant contenir des volumes ou le vol est interdit. Afin de prévenir les incertitudes de positionnement, des marges de sécurités statiques sont prises en compte : le volume de l’espace de vol est diminué en réduisant l’extension spatiale de ses limites extérieures et en augmentant l’extension spatiale des limites des volumes interdits qu’il contient.

L’espace de vol autorisé, défini comme l’exclusion des volumes représentant les zones de vol non-autorisées du volume total, est ensuite subdivisé en un ensemble d’éléments tous contenus dans l’espace de vol autorisé. Pour chacun de ces éléments, un point caractéristique est choisi. Un graphe est construit en reliant les points entre plus proches voisins. Avantageusement, une pondération est associée à chacune des branches et dépend des contraintes imposées au système et sont décrites plus bas. Cette pondération peut être orientée, à savoir que deux points différents peuvent être associés à une branche, selon le sens dans lequel elle doit être parcourue. Lorsque la destination est indiquée par l’utilisateur, le graphe est parcouru pour trouver le chemin optimal en fonction des contraintes.

Une fois le chemin calculé, c’est-à-dire une fois le plan de vol constitué, le chemin est suivi par l’UAV. Afin d’assurer le respect de la trajectoire calculée, un volume contenant la trajectoire est calculé en fonction des conditions environnementales, des paramètres de vol (vitesse, accélération, etc.). Ce volume est issu de l’application d’un facteur de relâchement non- isotrope de la trajectoire et correspond à un volume de vol obligatoire pour l’UAV suivant ladite trajectoire. Le facteur de relâchement est calculé périodiquement et le volume de vol obligatoire est modifié en conséquence pour prendre en compte des changements dynamiques des conditions de modifications dudit facteur de relâchement. La pondération associée aux branches du graphe est périodiquement recalculée et le chemin entre la position courante et la destination minimisant le « coût » du parcours selon un ou plusieurs critères est recalculé. La notion de coût de parcours est déterminée par une priorité haut niveau choisie par l’utilisateur : priorité à un temps de parcours le plus court, à une vitesse moyenne de parcours la plus élevée, à une sécurité accrue. Lorsque le nouveau chemin traverse le volume associé au précédent chemin, alors le facteur de relâchement est recalculé et le volume de vol obligatoire recalculé en conséquence. Le comportement de l’UAV est surveillé et lorsqu’une anomalie est détectée une modification de la destination peut avoir lieu, et l’UAV se dirige alors vers la zone de sécurité, définie apriori, maximisant la sécurité du vol.

Représentation de l’espace de vol

On va maintenant décrire en détail, en référence aux Figures 1 à 1 1 , un procédé de recherche de chemin et de construction et de suivi de la trajectoire. [0076] En référence tout d’abord aux Figures 1 à 3, la représentation de l’espace de vol E peut être effectuée en trois dimensions en le considérant comme un polyèdre dit « englobant » PEG (typiquement un cylindre de directrice verticale s’appuyant sur les limites d’un site, ici une clôture CL) contenant entièrement un ensemble d’autres polyèdres dits « exclus », ici par souci de simplification des parallélépipèdes rectangles PEX1 , PEX2 et PEX3, dont le volume est interdit de vol. Ces polyèdres peuvent représenter par exemple des bâtiments, des installations industrielles, des cuves, des zones de stationnement ou de travail. Afin de prendre en compte à la fois l’incertitude des instruments de mesure de la position et des erreurs introduites par le modèle tridimensionnel en lui-même, des marges de sécurité statiques aussi bien pour le polyèdre englobant que pour les polyèdres exclus sont calculées en déterminant un accroissement prédéfini de la taille des polyèdres exclus et une diminution prédéfinie de la taille du polyèdre englobant. La distance d’accroissement ou de diminution peut être choisie de différentes manières en utilisant par exemple l’erreur connue du système de positionnement. Elle peut être différente dans les deux dimensions horizontales et la dimension verticale. Elle est typiquement de l’ordre de 5 m.

Ainsi les références PEG’ et PEX1’, PEX2’ et PEX3’ désignent sur les Figures 4 et 5 ces polyèdres « dilatés » après correction.

En référence maintenant aux Figures 5 et 6 à 9, le modèle tridimensionnel de l’espace de vol est ici vu comme la superposition de couches horizontales à des altitudes différentes. Des tranches horizontales d’altitudes fixes sont créées entre des plans horizontaux situés aux d’altitudes minimum et maximum de chacun des polyèdres contenus dans l’espace de vol. Ici un plan PO correspond à l’altitude minimum commune des trois polyèdres exclus PEX1 , PEX2, PEX3, tandis que des plans P1 à P3 correspondent aux altitudes maximales dans le sens croissant des polyèdres exclus, à savoir PEX3, PEX2 et PEX1. L’intersection entre chaque plan et chaque polyèdre lui-même forme un polygone. Ici les polyèdres sont de section horizontale constante sur toute leur hauteur. Dans le cas de polyèdres de section variable, on détermine par calcul la projection du polyèdre dans les plans au niveau de sa section la plus large pour la tranche considérée.

La conception du modèle tridimensionnel peut également comprendre un plan P4 (voir Figure 5) déterminé en fonction d’une altitude maximale de vol des UAV, ce plan étant reporté à une altitude quasi-infinie en cas d’absence d’une telle limitation.

L’espace de vol est modélisé par un espace en 2,5 dimensions constitué d’un ensemble de tranches ici T01 , T12, T23 et T34 de sections horizontales constantes, qui respectivement sont délimités par les paires de plans P0-P1 , ..., P3-P4, dont les limites sont extérieurement celles du polyèdre englobant corrigé PEG’ et intérieurement celles des polyèdres exclus corrigés PEX1’ à PEX3’ qui ont des intersections avec ces tranches, chacune de ces tranches définissant sur toute sa hauteur une zone de vol autorisé.

Les Figures 6 à 9 illustrent respectivement les sections des quatre tranches sur la base du modèle des Figures 1 à 5.

On observe sur la Figure 9 que la tranche T34 de plus grande altitude ne contient aucun polygone exclus.

Dans cet espace de vol, un ou plusieurs UAVs sont amenés à évoluer et sont en interaction avec une ou plusieurs stations de recharge situées dans des zones accessibles de la zone de vol. Des zones d’atterrissage d’urgence peuvent également être prises en compte dans la définition de l’espace de vol. Elles correspondent à des zones pouvant contenir ou non une station de recharge et sont des zones choisies dans lesquelles un UAV peut atterrir en sécurité. Une station de recharge doit nécessairement se trouver dans une zone d’atterrissage d’urgence : en cas de problème lors de l’atterrissage d’un UAV dans la station, l’UAV a une solution de repli accessible rapidement et de manière sécuritaire. Dans la description actuelle, une zone d’atterrissage d’urgence peut être situé au-dessus d’un obstacle, mais ne peut pas être situé au même niveau.

La création du modèle du site à parcourir comprend également le positionnement, effectué à l’aide d’une interface utilisateur approprié, de stations de recharge pour les UAV, et le cas échéant de zones d’atterrissage d’urgence distinctes des zones de stations de recharge.

Avantageusement, ce positionnement s’effectue en prenant en compte les marges de sécurité des zones interdites, de façon à éviter qu’un UAV n’ait à pénétrer dans une telle zone interdite lors d’un atterrissage en urgence. Subdivision de l’espace de vol en éléments individuels et construction d’une représentation de l’espace de vol sous forme de graphe

A cette étape, le plan horizontal de la zone de vol autorisé dans chacune des tranches précitées est subdivisé par un système de traitement en un ensemble d’éléments ou pavés individuels PVk constituant ainsi un pavage de la zone de vol autorisé dans cette tranche. Le pavage peut être fait de différentes manières. Avantageusement, on utilise pour ce pavage une triangulation de Delaunay ou une de ses variantes (voir notamment https://fr.wikipedia.org/wiki/Triangulation_de_Delaunay), les pavés étant ainsi tous de forme triangulaire.

Avantageusement, on utilise une triangulation de Delaunay sous contrainte (voir par exemple Christophe Lemaire. Triangulation de Delaunay et arbres multidimensionnels. Synthèse d’image et réalité virtuelle [cs.GR]. Ecole Nationale Supérieure des Mines de Saint-Etienne ; Université JeanMonnet - Saint-Etienne, 1997. Français. NNT : 1997STET4021 ; tel- 00850521 , chapitre 1 .5).

Un avantage de la triangulation de Delaunay est qu’elle est peu exigeante en ressources de calcul nécessaires pour réaliser la triangulation, si bien que la subdivision en pavés peut être réalisée à bord de l’UAV.

En outre, la triangulation sous contrainte permet d’imposer que le résultat de la triangulation respecte une forme particulière par endroits du fait que les éléments individuels du modèle peuvent s'entrecouper (cas par exemple d’une zone de vol interdite au milieu d'une zone de vol autorisée).

Une fois la triangulation réalisée, l’unité de traitement détermine pour chaque pavé les coordonnées d’un point caractéristique Pk. Un choix possible est de prendre le centre de masse du pavé. En effet, par définition, le centre de masse d’un pavé triangulaire issu d’une triangulation de Delaunay est nécessairement situé à l’intérieur de ce pavé, et donc dans la zone de vol autorisé de la tranche horizontale Txy considérée.

L’unité de traitement construit alors un graphe dont les nœuds sont chacun de ces points caractéristiques Pk. Chaque nœud a pour propriétés un identifiant de nœud Ik et ses trois coordonnées Xk, Yk, Zk dans un espace tridimensionnel orthonormé. Les branches du graphe comprennent des branches reliant les nœuds les plus proches situés dans une même tranche, et d’autre part des branches reliant les nœuds les plus proches dans deux tranches voisines. Les nœuds constitués comme les plus proches dans une même tranche sont avantageusement les points caractéristiques de triangles adjacents par l’un de leurs côtés (simplicité de construction). Les nœuds les plus proches de deux tranches adjacentes sont les nœuds dont la distance mutuelle calculée est la plus courte, étant précisé qu’un nœud d’une tranche donnée peut avoir une ou plusieurs branches le reliant à un ou plusieurs nœuds de la branche immédiatement supérieure (lorsqu’elle existe), et une ou plusieurs branches le reliant à un ou plusieurs nœuds de la branche immédiatement inférieure (lorsqu’elle existe). En règle générale, l’unité de traitement ne génère pas de branche entre des nœuds de tranches qui ne sont pas immédiatement adjacentes, mais il peut exister des exceptions pour des configurations de sites particulières. Par ailleurs, dans tous les cas une branche ne peut être générée entre deux nœuds que si elle ne crée pas d’intersection avec les bordures intérieures et extérieures des tranches considérées, et l’unité de traitement vérifie cette condition par application de règles géométriques simples à chaque génération de branche.

Les Figures 6 à 9 illustrent les triangulations de Delaunay et les points caractéristiques associés dans chacune des tranches du modèle simplifié utilisé jusqu’à présent.

Une fois le graphe établi (ou au cours de sa construction), l’unité de traitement affecte à chacune de ces branches un poids de base qui est proportionnel à la longueur de la branche, déterminée à partir des coordonnées des deux nœuds qu’elle relie.

Dans une forme de réalisation préférée, ce poids de base peut être affecté par un coefficient correcteur de sens de parcours, pour favoriser un trajet dans un sens plutôt qu’un autre, en diminuant le poids de base et en l’augmentant dans le sens opposé, éventuellement jusqu’à le rendre suffisamment grand pour qu’aucun parcours dans ce sens ne puisse être proposé lors de la recherche de meilleur parcours par l’unité de traitement (voir plus loin).

Concernant des branches reliant des nœuds situés à des altitudes différentes, le poids de base peut être corrigé d’un facteur d’altitude déterminé en fonction de la différence d’altitude entre les deux nœuds. La valeur de ce facteur correctif peut être choisie de manière heuristique, et est positif dans le sens de la montée et négatif dans le sens de la descente. De cette manière, un changement d’altitude est favorisé dans le sens de la descente, et défavorisé dans le sens de la montée.

On décrira dans la suite d’autres facteurs de variation dynamique du poids des branches.

Recherche et mise à jour de chemin

L’unité de traitement embarquée dans le drone est apte à recevoir comme données d’entrée les coordonnées d’une destination souhaitée sur le site, cette destination étant soit entrée par un utilisateur et communiquée au drone par les moyens de communication disponibles, soit déterminée automatiquement en fonction d’autres traitements. En fonction de sa position courante et des données de destination, l’unité de traitement embarquée dans l’UAV s’appuie sur le graphe défini comme décrit ci-dessus, chargé dans la mémoire de chaque UAV lors de son installation sur site, pour construire le chemin permettant de se rendre à ladite destination, et exécuter les commandes de contrôle permettant de suivre le chemin.

La détermination du chemin est décomposée en deux parties : - la première consiste en la recherche d’un chemin de manière globale dans tout l’espace de vol ;

- la seconde consiste en la construction d’une trajectoire permettant de suivre le chemin trouvé à l’étape précédente.

Lorsque la destination est reçue par le drone, l’unité de traitement parcourt le pavage déterminé comme décrit précédemment pour identifier le pavé triangulaire englobant la destination, dans la tranche d’altitude immédiatement inférieure à l’altitude de la destination. Cette recherche peut s’effectuer en parcourant une table listant l’ensemble des caractéristiques géométriques du pavage, telles que déterminées par la triangulation de Delaunay.

Si un tel pavé est trouvé dans la table, alors la destination est bien contenue dans la zone de vol autorisé. En d’autres termes les destinations à l’extérieure de l’espace de vol autorisé sont inatteignables par construction.

Une fois la destination validée, l’unité de traitement met en jeu un processus de parcours de graphe, de type connu en soi, pour trouver le chemin le plus court dans le graphe en minimisant la somme des poids des branches à parcourir. Ce processus peut se baser par exemple sur un algorithme connu tel que A * ou Dikjstra (voir par exemple https://dzone.com/articles/from-dijkstra-to-a-star-a-part-2- the-a-star-a-algo).

La Figure 10 illustre un chemin de base CHB obtenu, qui est une ligne brisée dont les points intermédiaires ou points de passage sont les points caractéristiques du graphe pour lesquels la somme des poids est minimisé.

Ce chemin de base CHB a pour objet principal, dans des environnements complexes, de déterminer la route optimale entre les zones interdites par rapport à cette minimisation de poids.

A partir de ce chemin de base, l’unité de traitement élabore un chemin effectif CHE, dont un exemple est illustré sur la Figure 11 , en effectuant su le chemin de base un certain nombre d’opérations, en particulier :

- élimination de certains points de passage à l’aide de tests d’alignement (si trois points de passage PPn-1 , PPn et PPn+1 sont, à une approximation près, sur la même droite, alors le point de passage intermédiaire PPn est éliminé) ;

- élimination de certains points de passage en calculant une droite reliant des points de passage PPn-1 et PPn+1 situés de part et d’autre d’un point de passage PPn, en déterminant si cette droite coupe une ou plusieurs zones interdites dilatées, et élimination du point de passage Pn dans le cas où ce test est négatif ;

- raffinement du chemin débarrassé de certains points intermédiaires inutiles par une approche de réduction de la somme des poids ; ce processus met en jeu par exemple une approche dichotomique : si l’on considère une section de chemin constituée par trois points de passages PPn-1 , PPn et PPn+1 , le point PPn est remplacé par un point PPn’ du segment PPn-1 -PPn telle que le poids associé à la branche PPn’-PPn+1 soit inférieur au poids associé à la branche PPn-PPn+1 , cette recherche du point PPn’ étant effectuée par dichotomie ; on génère ainsi un chemin effectif CHE dont le poids total des branches est minimisé.

À l’issue de ces étapes, l’unité de traitement se base sur les données du chemin effectif CHE pour construire un volume ou couloir de vol que doit obligatoirement respecter l’UAV. Ce volume est construit en prenant en compte un facteur de relâchement autour du chemin CHE.

Ce facteur de relâchement est déterminé à partir d’une donnée d’envergure maximale de l’UAV, augmentée d’un facteur qui peut être soit uniforme et dépendre de la nature du site, soit variable en fonction de l’endroit du chemin CHE et notamment de sa distance à des zones de vol interdit (après dilatation), soit encore la somme d’un facteur uniforme et d’un facteur variable.

Dans une forme de réalisation de base, la prise en compte de ce facteur de relâchement dans le calcul du couloir de vol obligatoire met en jeu le calcul d’un ensemble de cônes tronqués mis bout à bout autour du chemin CHE, le rayon de la base de chaque tronc de cône étant égal au facteur de relâchement. De proche en proche le volume de vol est construit autour du chemin à suivre CHE. Ce couloir de vol peut être soit calculé après établissement du chemin CHE, pour l’ensemble de celui-ci, soit calculé dynamiquement au cours du vol de l’UAV. Il sera recalculé à chaque fois que l’IlAV détermine un nouveau chemin CHE après variation des poids des branches du graphe.

Périodiquement, l’UAV compare sa position réelle du moment avec les données géométriques du couloir de vol. Lorsque cette comparaison détecte une sortie du couloir de vol (notamment en fonction de facteurs extérieurs tels qu’un fort vent, un problème temporaire de localisation GPS, etc.), une instruction de vol correctrice est appliquée à l’autopilote en fonction de l’écart de position mesuré.

On notera que d’autres facteurs peuvent être utiles à la détermination statique ou dynamique du couloir de vol autorisé, et notamment :

- des facteurs d’agilité de l’IlAV (type de voilure, vitesses minimale - cas d’une voilure portante fixe - et maximale, accélération maximale, etc.),

- caractéristiques de capteurs embarqués (Lidar, Laser, etc.), ces facteurs influençant notamment l’aptitude de l’UAV à détecter et éviter dynamiquement les collisions. D’une façon générale, on prévoit un couloir de vol d’autant plus étroit que ces aptitudes sont faibles.

Par ailleurs, une fois la dimension du couloir de vol établie, on peut prévoir que l’UAV, au sein de ce couloir, adopte une trajectoire qui est différente selon ces paramètres ou d’autres paramètres, qu’ils soient dynamiques ou statiques. Ainsi la détermination de la trajectoire peut être influencée par la valeur de différents paramètres ayant pour effet de favoriser une trajectoire la plus courte possible, ou bien une permettant de réduire au maximum le temps d’exécution, ou encore celle restant le plus éloigné possible des obstacles.

Selon une autre caractéristique, on peut prévoir qu’une sortie du couloir de vol provoque, plutôt qu’une action correctrice sur l’autopilote visant à permettre à l’UAV de retrouver son couloir, un nouveau calcul du chemin puis du couloir de vol associé. Dans la pratique, lorsqu’un ordre de mission comportant des données de destination est reçu par l’UAV, l’unité de traitement embarquée lance la première recherche de chemin globale. Ensuite, au cours du vol, des canaux de communication entre l’UAV et d’autres équipements (équipements au sol, capteurs, autres UAV, etc.) permettent à l’unité de traitement de mettre à jour les poids des branches du graphe.

Parallèlement, soit à une fréquence déterminée (par exemple une fois par seconde), soit à chaque fois qu’un poids est modifié, l’unité de traitement de l’UAV effectue une nouvelle recherche de chemin entre sa position courante et la destination indiquée au départ.

Il est également possible, au cours du vol, que l’UAV reçoive ou détermine une nouvelle destination, et dans ce cas un nouveau chemin entre sa position courante et la nouvelle destination est calculé, et mis à jour comme décrit ci-dessus.

Une fois que le chemin est trouvé, le couloir de vol est calculé et mémorisé de façon à être accessible par un planificateur local de trajectoire.

Le cas échéant, dans le cas où l’unité de traitement embarquée dispose d’une information d’autonomie de la ou des batteries de l’UAV, cette information est confrontée à la somme des poids du chemin CHE, pour déterminer si l’UAV possède l’autonomie suffisante pour atteindre la destination, avec une marge d’erreur appropriée.

Dans le cas où le vol est possible, le planificateur local de trajectoire, à une fréquence déterminée et par exemple 50 fois par seconde, applique à l’autopilote des instructions de vol pour que l’UAV se déplace dans le couloir. Comme on l’a décrit plus haut, ce planificateur teste également, de préférence selon la même périodicité, les éventuelles sorties de couloir et applique à l’autopilote les instructions correctrices appropriées.

On notera également que ce planificateur de trajectoire peut prendre en compte, soit de façon statique, doit de façon dynamique, une vitesse maximale autorisée dans le couloir.

Ajustement des poids des branches du graphe Dans la description qui précède, les poids de base associés aux branches du graphe représentant l’espace de vol sont calculés comme étant proportionnels à la distance entre les nœuds que les branches relient.

Chaque UAV susceptible de voler sur un site contient dans sa mémoire les données de ce graphe, avec les poids de base, et comme on l’a vu l’unité de traitement embarquée va déterminer le couloir de vol à suivre pour atteindre une destination donnée.

Dans le même temps, les moyens de communication de l’UAV avec le sol, voire avec d’autres UAV volant sur le même site, voire encore avec des sources d’informations sur site (capteurs, etc.) ou externes (données météo, etc.) permettent à l’UAV de collecter des données susceptibles d’affecter les valeurs de poids.

Sur un plan mathématique, ces données peuvent être de type champ scalaire ou de type champ vectoriel.

Un champ scalaire correspond par exemple à une variable telle qu’une note de qualité du réseau de communication entre les UAV et le sol, la température, l’humidité, etc.

Ces données sont scalaires en ce sens qu’elles ne sont pas orientées et affectent de la même manière l’ensemble des poids du graphe.

Par exemple, une température particulièrement basse peut conduire à augmenter les poids de base d’un facteur multiplicateur donné, pour tenir compte du fait que l’autonomie de l’UAV à basse température est réduite du fait d’une perte d’efficacité des batteries.

En revanche, le vent peut être représenté sous la forme d’un champ vectoriel, à chaque point ou région de l’espace de vol étant associé un vecteur dont l’orientation représente sa direction, et dont la norme représente sa force. La réception d’un champ vectoriel (ou d’un vecteur applicable à l’emplacement courant du drone) permet de recalculer les poids des branches du graphe par une fonction de produit scalaire, la branche étant également considérée comme un vecteur dont l’orientation correspond à sa direction et dont la norme représente le poids de base. Dans le cas où la valeur du vecteur de vent le long d’une branche donnée change en fonction de la position dans la branche, l’unité de traitement détermine une moyenne des produits vectoriels en différents points de la branche.

On notera que la granularité d’un champ vectoriel susceptible d’affecter les poids peut largement varier. Par exemple dans le cas du vent, on peut recourir à un vecteur de vent unique pour l’ensemble du site, accessible à partir d’un anémomètre connecté ou d’une source météo externe, ou à différents vecteurs de vent selon les zones du site, que le vent « local » soit mesuré par des capteurs ou déterminé par exemple par simulation.

On notera que la composante du poids d’une branche issue de ce calcul est orientée : la force d’un vent non perpendiculaire à une branche diminue le poids de base dans un sens (parcours vent contre), et augmente le poids de base dans l’autre (parcours vent avec).

Un module de mise à jour des poids des branches du graphe modifie les poids de préférence à chaque fois que de nouvelles données issues des contraintes extérieures sont disponibles. Pour minimiser le risque d’erreur, toute nouvelle demande de calcul de chemin pendant une opération de mise à jour des poids s’effectue sur la base du graphe courant avant mise à jour, dont une copie est conservée à cet effet.

Modification du chemin en fonction d’une priorité donnée au vol - différents types de poids

Lors de l’établissement d’une mission, soit par un utilisateur, soit de façon automatisée, les données de mission peuvent avantageusement comprendre un type de priorité pour atteindre la destination fixée par la mission.

Par exemple, on peut prévoir quatre types de priorités, à savoir :

- minimisation de la distance absolue à parcourir,

- minimisation du temps de parcours,

- minimisation de la consommation d’énergie, - minimisation du risque, avec des sous-catégories possibles selon le type de risque (sur personnes, sur biens, etc.).

De manière générale, la valeur courante du poids d’une branche pour un sens de parcours donné est obtenue par combinaison du poids de base (longueur de la branche) avec les différentes corrections apportées par un ou plusieurs champs scalaires et/ou par un ou plusieurs champs vectoriels, comme on l’a décrit plus haut.

La gestion des priorités implique de pouvoir donner à chaque branche une nature ou une valeur de poids différente.

Dans le cas où la priorité est la minimisation de la distance absolue, la recherche de chemin s’effectue sur le graphe pondéré avec les poids de base ou des poids de base corrigés par exemple avec un vecteur de vent.

Pour pouvoir prendre en compte une priorité de type minimisation du temps de parcours, on peut corriger le poids de distance (poids de base, corrigé ou non) affecté à chaque branche un coefficient lié à la vitesse maximale autorisée dans cette branche.

Avantageusement, cette correction est réalisée en incluant dans les données du site à modéliser une cartographie de vitesses autorisées (en fonction notamment du type d’équipement avoisiné ou survolé, d’un risque lié aux personnes, etc.). Ensuite, une fois la structure du graphe établie, l’unité de traitement affecte à chaque branche une information de vitesse maximale autorisée en fonction de l’emplacement de cette branche dans la cartographie de vitesses. A partir du poids de base (longueur de la branche) et de cette information de vitesse maximale, l’unité de traitement calcule un poids de temps de parcours minimal (celui obtenu pour la vitesse maximale autorisée), en multipliant le poids de base éventuellement corrigé par champ scalaire ou vectoriel par un coefficient d’autant plus petit que la vitesse autorisée est élevée, et inversement.

Si la mission comporte cette priorité de minimisation de temps de parcours, la recherche du meilleur chemin s’effectue non plus en fonction de des poids représentatifs de la distance, mais en fonction de ces poids de temps de parcours.

Une autre cartographie que le système peut avantageusement utiliser est une cartographie définissant des zones ayant différents niveaux de risque. Cette cartographie de risques permet par exemple de prendre en compte la présence de personnel ou de zones de circulation de personnel, la dangerosité des différentes installations, etc. De la même manière que pour la cartographie de vitesses autorisées, l’unité de traitement altère le poids de chaque branche en fonction de la note de risque de la zone dans laquelle la branche se situe, pour ainsi, au bout du compte, défavoriser des chemins traversant des zones de risque élevé par rapport à des chemins traversant des zones de risque moindre.

Dans le cas où la priorité de la mission est la minimisation de la consommation d’énergie, une approche possible est la détermination d’une densité de points de passage. A cet égard, plus le nombre de points de passage est important, plus les changements de direction et de vitesse de l’UAV seront fréquents, ce qui constitue un facteur important pour la consommation d’énergie.

La détermination du chemin peut alors s’effectuer non plus par recherche du chemin le plus court en distance ou en temps, mais en déterminant un ensemble de chemins possibles ayant tous une somme de poids en temps ou en distance inférieure à un seuil, et à sélectionner le chemin qui comporte le nombre de points de passage minimum.

Enfin si la priorité est la sécurité du vol, on peut affecter à chaque branche un facteur de risque dérivé de sa proximité avec un équipement constituant une zone interdite. Plus la proximité est grande, plus le facteur de risque est élevé. Une fois la structure du graphe obtenu, ce poids « de risque » est déterminé en calculant la distance de chaque branche générée avec la zone interdite la plus proche, et en affectant au poids de distance (poids de base après correction éventuelle par champ scalaire ou vectoriel) un coefficient multiplicateur d’autant plus important que cette distance est courte (le coefficient étant typiquement égal à 1 pour toutes les branches dont l’éloignement d’une zone interdite est supérieur à un seuil déterminé).

Le meilleur chemin du point de vue de la sécurité du vol est alors celui qui minimise la somme des poids de risque.

Pour raffiner encore cette gestion des priorités, il est possible de combiner les poids de base (éventuellement corrigés par champs scalaires et/ou vectoriels) avec les facteurs de vitesse, de consommation d’énergie et de risque précités dans des mesures différentes, de manière à adapter l’importance de chaque altération à la priorité de la mission.

Par exemple, on peut fixer un ordre des priorités (par exemple sécurité puis vitesse puis énergie) et moduler en conséquence l’impact des facteurs de correction de poids correspondants.

On va maintenant décrire un exemple de calcul du poids d’une branche du graphe.

La formule générale du calcul de ce poids est donnée par :

wAB;j = SOMMEi(Yi;jGi(A,B))

• A et B sont des nœuds du graphe pouvant être reliés par une ligne droite sans intersection avec l’intérieur d’une zone interdite (et le cas échéant sans contact avec son bord),

• j est un facteur de priorité,

• Gi(A,B) sont des fonctions représentant une contribution au calcul du poids,

• Yi;j est un facteur associé à une contribution.

Dans un exemple concret, considérons trois contributions au calcul du poids, à savoir trois fonctions G1 , G2 et G3 ;

• G1 (A,B) représente la distance entre les points A et B,

• G2(A,B) représente la qualité moyenne du signal de positionnement GPS entre les points A et B,

• G3(A,B) représente la prise en compte des zones de risques.

La formulation mathématique de ces trois fonctions peut répondre à différentes approches qu’il n’est pas nécessaire de détailler ici. Considérons maintenant deux priorités :

• j = 1 : Distance parcourue la plus faible,

• j = 2 : Prise en compte des zones de risques.

Pour chacune de ces deux priorités, le système choisit la contribution des trois fonctions G1 , G2, G3 au poids de la branche en modifiant la valeur du paramètre Yi;j correspondant.

Ainsi, dans le cas ci-dessus où la priorité est donnée seulement à une distance parcourue la plus faible (j = 1 ), on peut utiliser :

- Yi=1 =1

- Yi=2,3 = 0

Dans le cas où la priorité est donnée seulement à la prise en compte des zones de risque (j = 2), on peut utiliser :

- Yi=1 ,2 = 0

- Yi=3 =1

Bien entendu, des coefficients Yi;j de valeurs différentes de 0 et de 1 , assurant une prise en compte combinée de différentes priorités, peuvent être utilisés.

Modification de l’espace de vol en fonction d’un sens de circulation imposé

À tout moment l’utilisateur ou un facteur externe peut imposer une zone, notamment une zone de passage entre deux zones interdites, dans laquelle un certain sens de circulation est rendu obligatoire.

Dans ce cas, les poids associés aux branches du graphe s’étendant au moins partiellement dans cette zone sont modifiés de façon à laisser intacts les poids associés aux branches dans la direction qui respect ce sens de circulation, et à rendre infinis ou quasi-infinis les poids dans le sens inverse (du point de vue de la mathématique du graphe, leur donner une valeur très élevée).

On notera ici qu’en règle générale, un UAV devra pouvoir revenir à sa zone de départ. Or, en fonction de la topologie de sens de vol imposée, il est possible que le critère de sens unique ne le permette pas. Pour garantir que l’UAV puisse revenir à son point de départ, même dans un contexte de sens unique de circulation, l’existence d’un poids élevé mais non infini pour le parcours dans le sens interdit permet néanmoins à l’UAV de parcourir une zone à sens unique dans le sens interdit lorsqu’il pas d’autre choix.

Modification du plan de vol en réponse aux caractéristiques dynamiques de l’UAV

À partir de la mise sous tension de l’UAV, un module d’estimation de temps de vol disponible est lancé et détermine ce temps de vol en fonction notamment de l’état de charge de la batterie, de mesures de consommations en vol effectuées récemment, de la température ambiante, etc.

Lorsque l’UAV est en mission, l’unité de traitement calcule à cadence donnée, par exemple une fois par seconde, un chemin dit « de secours » entre sa position courante et la position de la station de recharge disponible la plus proche (ou autre zone d’atterrissage). Tant que la durée nécessaire pour parcourir ce chemin est inférieure à l’estimation de temps restant indiqué par le module précitée, l’UAV continue sa mission.

Lorsque l’estimation du temps de vol disponible devient égale au temps de vol pour atteindre la station de recharge la plus proche (éventuellement à une marge de sécurité près), alors l’unité de traitement de l’UAV provoque un abandon de mission en remplaçant le chemin actuellement parcouru dans le cadre de cette mission par le chemin de secours calculé à partir de la position courante et de la position d’atterrissage la plus proche, de manière à rentrer vers celle-ci et se poser.

Selon une autre approche, le chemin de secours est imposé en réponse à des anomalies techniques constatées par l’UAV au cours de la mission. Ainsi les autopilotes sont en général capables de fournir différentes données concernant l’état de santé du drone, comme la précision du circuit de détermination de position (circuit dit EKF pour « Extended Kalman Filter »), le niveau de vibration, etc.

À partir de la mise sous tension de l’UAV, un module permettant de détection d’anomalie connecté au circuit EKF et à un capteur de vibration (faisant partie typiquement de sa centrale inertielle) est activé. Pour tous les types de données analysés, ce module estime si les valeurs reçues sont dans le domaine des valeurs acceptables ou non. Une implémentation possible consiste à calculer une simple moyenne sur une fenêtre de temps donnée pour chaque type de donnée reçue, et à la comparer avec une gamme de valeurs acceptables mémorisée. Si une valeur moyenne se situe en dehors de cette gamme, le chemin de secours est automatiquement calculé, chargé et suivi. Modification de l’espace de vol : altitudes interdites, présence d’autres UAV

Sachant que plusieurs UAV peuvent voler sur un même site, on prévoit selon cette fonctionnalité que la présence d’autres UAV en cours de vol sur le site soit prise en compte dans l’établissement du chemin ou la modification dynamique de celui-ci.

Cette fonctionnalité est avantageusement mise en œuvre en complément de dispositifs anti-collision qui peuvent équiper les UAV, tels que Laser ou Lidar, dont l’efficacité implique une visibilité directe de l’obstacle et qui en outre peuvent exiger des ressources de traitement numérique importantes.

Plus précisément, plutôt que de recalculer la structure du graphe en considérant un drone comme une zone mobile de vol interdit, une solution peut consister à recevoir au niveau d’un UAV la position courante d’un autre UAV en vol dans le voisinage, à identifier les branches du graphe situés à une distance inférieure à un seuil de cette position, et à attribuer aux poids des branches ainsi identifiées un facteur multiplicateur très élevé, de telle sorte qu’un chemin recalculé après mise à jour des poids évite les branches en question.

Cet aspect permet de renforcer significativement la sécurité des vols lorsqu’une flotte d’UAV est apte à circuler sur un même site.

Architecture

On a illustré sur la Figure 12 une architecture permettant de mettre en œuvre les différents aspects décrits dans ce qui précède.

Une première unité de traitement 100 reçoit des données de modèle du site et les cartographies associées. A partir ce des données, elle effectue la dilatation des zones de vol interdit, détermine les zones de vol autorisé aux différentes altitudes, réalise les subdivisions par exemple par triangulations de Delaunay à chacune des altitudes, génère les points du graphe à partir des coordonnées des pavés individuels, et interconnecte ces points d’une part dans chaque plan horizontal correspondant à une altitude et d’autre part entre plans horizontaux adjacents.

Pour chaque branche de ce graphe, sa longueur est calculée à partir des coordonnées des points qu’elle réunit, pour ainsi déterminer son poids de base.

Les données de ce graphe sont transmises par les canaux de communication adaptés à chacun des UAVs 200a, 200b, 200c, etc. susceptibles de circuler sur le site, où elles sont mémorisées.

A chaque fois que l’environnement du site change (apparition ou disparition d’une zone interdite de vol par exemple), un graphe mis à jour est déterminé et transmis à chaque UAV.

Une mission est en général déclenchée par transmission de données de mission d’une station au sol 300, distincte de l’unité de traitement 100 ou en faisant partie, vers un UAV donné, ici 200a.

L’unité de traitement 210 embarquée dans cet UAV reçoit les données de mission, comportant typiquement :

- les coordonnées d’une destination,

- une priorité pour le vol, ou plusieurs priorités ordonnées,

- d’autres paramètres de la mission, et notamment des instructions de prise de vues en déplacement ou en vol stationnaire, etc.

L’unité de traitement 210 embarquée dans l’UAV reçoit également, soit avant le début de la mission, soit de façon périodique y compris au cours du vol, des données scalaires et/ou vectorielles susceptible d’affecter les poids de base des branches.

En fonction des données de priorité et des données scalaires et/ou vectorielles, ainsi que des éventuelles données affectant les sens de circulation, l’unité de traitement 210 calcule les poids effectifs des différentes branches, et détermine le chemin de base CHB en fonction des données du graphe doté de ses poids effectifs, des coordonnées courantes de l’UAV (point de départ) et des données de destination reçues.

L’unité de traitement 210 détermine ensuite le chemin effectif CHE.

La capacité de l’UAV à effectuer la mission, en fonction de son autonomie, est ensuite mesurée.

En cas d’autonomie suffisante, la mission peut alors démarrer, et pendant le vol, l’unité de traitement embarquée surveille les éventuelles sorties de couloir et applique à l’autopilote les actions correctrices nécessaires, reçoit des données dynamiques susceptibles d’affecter les poids des branches du graphe, recalcule en tant que de besoin le chemin, recalcule la faisabilité de la mission en fonctionne de l’autonomie mise à jour, et surveille les éventuelles anomalies à bord, susceptibles de provoquer le remplacement du chemin courant de la mission par un chemin de secours.

Bien entendu, la présente invention n’est nullement limitée à la description qui précède et de nombreuses variantes sont possibles.

En particulier :

- les données de vol peuvent être collectées et rassemblées pour accès par un processus d’apprentissage permettant de déterminer, lorsque les contraintes sont similaires à des contraintes rencontrées précédemment, de déterminer le chemin à parcourir par l’expérience plutôt que par calcul ;

- les données de mission peuvent inclure non seulement des données de destination, mais également des données de points de passage obligatoires, notamment pour de la surveillance planifiée ;

- les différents traitements décrits dans ce qui précède comme étant effectués au sol ou de façon embarquée peuvent être réalisés dans des architectures de traitement différentes ; en particulier, la réalisation et la mise à jour du graphe à partir du modèle du site peuvent être effectuées, si la puissance de calcul est adaptée, à bord de chacun des UAVs.