Explication de l'algorithme de recherche de trajectoire multi-drones

Lorsque vous essayez de résoudre un algorithme de recherche de chemin multi-drones!

Avez-vous déjà vu comment fonctionne un robot « en vrai » ?
Avez-vous réfléchi à la manière dont un déplace un objet – inanimé par définition – dans l’espace ?
Comment on fait bouger leurs doigts, comment on les fait avancer ?
Ou comment on permet aux drones de voler, par exemple ?

Ce travail n’est pas facile, car chaque pas, chaque mouvement doit être calculé et codé dans une perspective globale et de long terme.

Qu’est-ce qu’un « algorithme de navigation autonome » ?

Il s’agit d’un ensemble de techniques et de méthodes utilisées par des robots ou des véhicules pour se déplacer et effectuer des tâches sans intervention humaine.
Cet algorithme leur permet d'observer, de s'orienter, de prendre des décisions et d’agir dans leur environnement.
Ces algorithmes sont conçus pour garantir la sécurité et l'efficacité dans le déroulement des tâches qui leur sont confiées.

Rentrons un peu plus en détail dans le sujet.
Tout ce qui est lié à l’espace est relativement simple – plus simple par exemple que le machine learning, car cela repose simplement sur des calculs géométriques, calculs de graphes ou calculs trigonométriques.
Ces calculs sont vraiment plus précis et permettent de trouver l’intégralité d’une solution à un problème donné. Cela n’a rien à avoir avec le fait d’essayer d’imiter le cerveau humain, son mode de pensée et son intelligence.
Voilà la conviction forgée à partir de l’une de mes expériences, qui consistait à essayer de créer un algorithme de recherche de trajectoire pour drone.

Cet algorithme de recherche de trajectoire m’avait été commandé pour un spectacle de lumière.
L’enjeu était de trouver un itinéraire pour que tous les drones puissent évoluer au sein d’un même espace sans entrer en collision les uns avec les autres.
L’algorithme devait permettre de déplacer les drones d’un endroit à l’autre et de générer de cette manière le spectacle de lumière.

L’algorithme permet à plusieurs drones de se déplacer au sein d’un même espace d’un point A à un point B sans entrer en collision.

Sachant qu’il existe déjà un algorithme de recherche de trajectoire pour les drones, je me suis dit qu’il pourrait être pertinent de l’utiliser.

L’idée d’origine était de créer une matrice en 3 dimensions. On divise ainsi l’espace en carrés et chaque carré comprend la taille du drone ainsi que la zone de sécurité.

Ensuite on déplace le drone petit à petit, à chaque fois sur une dimension, et on place un drapeau dans la matrice pour signaler que l’endroit est occupé. De cette manière, on signale aux autres drones qu’ils ne doivent pas se déplacer vers cet espace

On peut tout simplement effectuer ce calcul de graphe : x + 1 ou y + 1 ou z + 1.

Les algorithmes de navigation utilisés actuellement pour le vol de drones consistent à trouver la trajectoire dans l’espace permettant d’aller du point A au point B, en utilisant l’algorithme pour trouver le chemin le plus court.

Pour cela on divise l’espace en cubes. Chaque cube est un nœud et chaque nœud est connecté à tous les autres nœuds qui sont physiquement proches de lui. Dans un graphe, par exemple, x est connecté à x + 1, etc.

On essaye ensuite de trouver le chemin le plus court entre le nœud A et le nœud B.
L'algorithme de Dijkstra permet de trouver le chemin le plus court entre un nœud donné (appelé « nœud source ») et d'autres nœuds dans le graphe. Cet algorithme utilise les poids des arêtes pour trouver le chemin qui réduit le plus la distance totale (poids) entre le nœud source et les autres nœuds.

Cet algorithme n’a pas donné la solution au problème posé.

Ici l'algorithme est différent. Nous n'avons pas besoin d'utiliser l'algorithme de trajectoire pour un drone en particulier, mais de trouver un algorithme pour synchroniser tous les drones ensemble.
De plus, dans l'espace physique, nous n'avons pas besoin d'utiliser l'algorithme des nœuds, mais plutôt d’utiliser les fonctions de graphes. Ainsi on peut calculer la ligne entre 2 points du graphe et trouver facilement le point suivant. Puis pour se déplacer facilement d'un point A à un point B au sein d’un graphe, on peut le faire en utilisant une dimension à chaque fois : x+y, y+1, z+1.

On peut aussi trouver le chemin en se déplaçant à chaque fois de 3 dimensions et en utilisant le calcul de la distance D dans un graphe 3D. On peut ainsi, pour chaque étape, trouver le point suivant en utilisant la formule D. De cette façon, le chemin est plus court, car au lieu de se déplacer d'une dimension à chaque fois, qui est x + 1, y + 1, z + 1 Ce qui signifie : en haut, en bas, à droite ou à gauche, devant ou derrière, comme dans le graphique, nous allons directement au but. Pour cela, nous devons calculer le point suivant avec le calcul de la distance et la longueur du pas. Cette solution n'a pas été implémentée dans l'algorithme, mais c'est une idée d'amélioration qui a été partiellement implémentée, donc je pourrais vous dire, si elle réussira sans aucun autre problème.

Il n’est pas non plus nécessaire d’essayer de trouver le chemin le plus court en examinant toutes les possibilités, car en règle générale, un drone devra attendre ou bouger, ou un autre doit s’écarter, donc peu importe de quel drone il s’agit.
Le chemin le plus court consiste donc à aller tout droit vers la destination, puis à résoudre le problème de collision.
En règle générale, pour tous les drones, il s’agira du chemin le plus court, et on pourra obtenir un algorithme très rapidement, sans avoir besoin de recourir à la force brute (tester toutes les possibilités par récursion) ou une méthode du même genre.

La solution ici est donc de trouver un algorithme qui synchronise tous les drones ensemble. Pour cela nous allons utiliser des fonctions graphiques.

De plus, il n’est pas nécessaire de vérifier tous les nœuds pour savoir quel est le chemin le plus court, car si l’on déplace chaque drone sur le graphe directement du point A au point B, alors on obtient le chemin le plus court. Ici nous avons seulement besoin gérer le problème de collision et répondre à la question suivante : comment gérer le fait qu’un point de la matrice puisse être utilisé par un autre drone et comment éviter cela ?

Nous avons donc ici vraiment beaucoup d’options, et beaucoup d'algorithmes différents.
J'ai inventé plusieurs algorithmes plus compliqués et pas forcément assez efficaces. Finalement, j'en ai trouvé deux qui fonctionnent réellement et qui sont faciles à mettre en œuvre.

En guise d’exemple, je vais vous présenter un problème et sa solution.
Si on génère une collision avec un drone ayant déjà atteint sa destination, que doit-on faire ?
On ne peut pas attendre qu’il s’en aille, car ayant déjà atteint sa destination, il ne bougera plus.
On peut aussi, c’est vrai, se déplacer autour de lui, mais on a trouvé une meilleure solution, plus facile à résoudre : il suffit de déplacer le drone fixe d’une place, afin de laisser passer le drone mobile, puis de remettre le drone fixe à sa place.

Si dans cet exemple, il ne s’agissait pas d’un drone, mais d’un arbre, alors bien sûr on ne pourrait pas déplacer l’arbre, mais uniquement se déplacer autour de lui.
C’est pourquoi, lorsqu’on construit un algorithme, on doit toujours trouver la solution à un problème spécifique, et non pas se contenter de copier un autre algorithme chargé de résoudre un autre problème.

Parfois, le génie consiste simplement à trouver la solution la plus simple et la plus efficace au problème, et non la plus complexe.

C'est aussi une règle d'or : ne compliquez pas les choses si vous pouvez les simplifier !


Un problème qui se situe dans l’espace physique pourrais être résolu à l’aide d’un graphe, de la géométrie ou de la trigonométrie. Il est toujours nécessaire de réaliser un calcul pour déplacer un objet dans l’espace.
N’essayez pas de résoudre un problème dans l’espace en utilisant de simples algorithmes de nœuds, utilisez plutôt une solution géométrique si c’est possible, ce qui devrait donner une solution plus rapide et plus performante.

Quand il s’agit par exemple de contourner un obstacle, pourquoi ne pas utiliser les fonctions paraboliques ? Lorsqu’il s’agit de trouver un point sur une parabole, je suis persuadée que les mathématiques offrent des solutions à de multiples problèmes dans l’espace. Il suffit de connaître toutes les formules. Quoi qu’il en soit, on peut trouver des solutions par des manières très simples.

J’ai développé de nombreuses solutions pour cet algorithme, mais j’en ai terminé seulement deux.
Je ne rentre pas dans les details des 2 algorithms, ce que je ferais probablement dans un des futur articles.
L’idée est de vous expliquer dans cet article comment résoudre un problème similaire.
En résumé :

1. N’essayez pas de copier un algorithme existant s’il ne correspond pas exactement à votre besoin. Essayez plutôt de trouver une solution à une situation spécifique.
2. N’essayez pas la force brute (le fait de tester toutes les possibilités) en première tentative, en particulier dans des cas comme celui-ci où l’on peut trouver la solution rapidement juste en se déplaçant tout droit comme sur un graphe.
3. Un problème d’algorithme n’est pas qu’une histoire de code.
Cela consiste aussi à trouver comment résoudre des problèmes.
Soyez créatifs et essayez de trouver des solutions comme si vous vous trouviez dans la réalité. Oubliez un peu le code et pensez tout cela comme un jeu.
Essayez de représenter tout cela concrètement sur un papier ou aussi dans la vie réelle. C’est comme cela que vous pourrez trouver une solution concrète à chaque problème (comme le fait de déplacer le drone fixe et de ne pas essayer de le contourner).
Abordez d’abord la question comme s’il s’agissait d’un problème dans la vie réelle, et après seulement, réfléchissez à la manière dont vous pouvez coder cela.

Je présente dans cet article un exemple d’algorithme, mais j’aimerais surtout vous détailler les différents éléments à prendre en compte lorsque l’on construit un robot.

Si l’on attend de lui qu’il puisse effectuer une action dans l’espace (se déplacer, manipuler quelque chose, etc.), cela nécessite des compétences élaborées en matière de graphe, de géométrie et de trigonométrie, afin de savoir comment lui faire manipuler des éléments dans l’espace.

En robotique, nous n’avons absolument pas l’intention de réinventer des calculs dans l’espace, puisque tout a déjà été dit il y a longtemps. Il suffit d’apprendre les mathématiques et de savoir comment les utiliser pour coder.

Voici quelques exemples d’utilisation des calculs dans l’espace.

Mouvements dans l’espace d’un robot ou d’un drone.
Si j’avais à développer un outil tel qu’un robot-tondeuse, le travail inclurait probablement des calculs graphiques, de la géométrie, des calculs dans l’espace, etc.

Et pourquoi ne pas utiliser des formules plus complexes pour les robots ? Pas uniquement la distance sur un graphe ou quelque chose de ce genre, mais par exemple des formules paraboliques pour se déplacer autour des objets ?

Et pour une voiture sans conducteur ? Sur les sites de construction, les véhicules autonomes ont besoin d’algorithmes permettant de générer un graphe de navigation. Ces algorithmes sont utilisés pour trouver les itinéraires sans collision les plus courts au sein d’environnements dynamiques. L’une des approches consiste à utiliser le « Visibiliy Graph » (graphique de visibilité), qui calcule l’ensemble du graphe, puis recherche activement des itinéraires à l’aide d’algorithmes comme A* ou Dijkstra.

Il est possible d’utiliser cet algorithme à chaque fois qu’on doit synchroniser plusieurs éléments entre eux. On peut par exemple le faire dans un studio si l’on souhaite que toute la lumière puisse se déplacer dans la pièce. Ou sur une scène de spectacle, si l’on souhaite que tous les éléments puissent se déplacer sur la scène. Cela peut peut-être même faciliter une chorégraphie, en permettant aux différents danseurs de se déplacer d’un endroit à l’autre… l’algorithme peut cartographier la danse sur la scène.

Cet algorithme a été spécialement conçu pour synchroniser des drones dans le cadre d’un spectacle de lumière…
Mais il pourrait être utilisé dans le cadre de n’importe quel projet nécessitant de faire se déplacer différents éléments au sein d’un espace donné.

Exemples de cas d’usage avec plusieurs drones:

Périmètre de sécurité

Tester des systèmes anti-drones protégeant les aéroports, les sites industriels et autres infrastructures critiques en envoyant de manière simultanée des drones depuis différentes directions jusqu’à la zone à protéger.

Agriculture

Pulvériser simultanément différentes cultures en parallèle à l’aide de plusieurs drones.

Cartographie

Cartographier de grandes zones en utilisant plusieurs drones de manière simultanée.

Entreprise de construction

L’intégration de drones dans l’industrie de la construction a ouvert une nouvelle ère en matière d’efficacité, de précision et de sûreté tout au long des différentes phases des projets de construction.

Projets topographiques

Cartographie de terrain

Sécurité et surveillance

Utilisation conjointe de plusieurs drones à des fins d’inspection

• Inspection de biens

Les drones sont en mesure d’effectuer des inspections visuelles rapprochées de différents biens, afin de repérer rapidement des défauts tels que : fissures, problèmes de structure, fuites, tuiles abîmées, corrosion, etc.

• Inspection de toits

Ce système aérien est particulièrement adapté à l’inspection de toits. Les drones peuvent se rendre dans des endroits inaccessibles à l’homme. Cela réduit voire élimine le risque de blessure et représente également un gain de temps considérable.

• Centrale électrique, transmission et distribution

La technologie des drones permet de s’assurer du bon fonctionnement des lignes de transmission. Les opérateurs peuvent analyser un dysfonctionnement à partir du sol avant de monter pour le réparer. Les drones augmentent donc l’efficacité et la rapidité de la maintenance.

• Inspection des tours de télécommunication et de radio

L'inspection des tours par drone permet de capturer des images en haute résolution pour évaluer les conditions de fonctionnement, ce qui permet aux entreprises d'analyser les résultats afin de prendre des décisions éclairées.

• Industries pétrolière et gazière

Les drones peuvent inspecter le pétrole et le gaz, ce qui permet d’obtenir plus rapidement des données consolidées, améliorant ainsi la longévité des installations. Cela réduit également les risques et les temps d’arrêt.

• Gestion des déchets

Utilisés dans la gestion des déchets , les drones peuvent simplifier de nombreuses opérations, notamment le ramassage des ordures et la surveillance des décharges. Ils peuvent également être utilisés pour nettoyer les poubelles, identifier et ramasser les déchets à éliminer.

• Sécurité routière

L’utilisation de drones dans le cadre de la sécurité routière englobe l’évaluation des risques, la réalisation d’enquêtes poussées sur les accidents et la surveillance globale du réseau routier.

• Surveillance et gestion du trafic

Les drones sont utilisés pour la surveillance et le suivi du trafic. Des paramètres de trafic – en ligne et hors ligne – sont extraits des données vidéo des drones afin d'améliorer les mécanismes de suivi et de gestion du trafic

• Gestion des infrastructures autoroutières

La technologie des drones est utilisée pour surveiller et gérer les infrastructures autoroutières. Plus important encore, elle est utilisée pour l’inspection des ponts et la reconnaissance des dégradations de la chaussée.

• Agriculture

Les drones utilisés dans le secteur agricole permettent aux agriculteurs, aux chercheurs et aux prestataires de services de surveiller rapidement et efficacement leurs cultures, suivre la croissance des plantes, repérer le stress, créer des plans de traitement, et bien d’autres choses.

• Environnement

La technologie des drones représente la méthode la plus rapide, la plus sûre et la plus rentable pour cartographier et surveiller de vastes étendues dans le cadre de l’étude, la protection et la gestion de l’environnement. C’est d’autant plus intéressant dans des zones dangereuses et difficilement accessibles aux hommes et aux véhicules.

• Risques naturels et catastrophes naturelles

Les drones permettent une intervention rapide sur le terrain en cas de catastrophes naturelles, de manière incomparablement plus rapide que la détection, l’analyse et l’intervention réalisées manuellement. Leur utilisation réduit significativement le temps de réponse aux catastrophes, et donc également l’étendue des dégâts potentiels. Équipés de capteurs tels que l’infrarouge, les drones peuvent localiser avec précision et identifier visuellement des personnes en détresse, et ensuite les aider en leur fournissant du matériel médical et des médicaments, des équipements et de la nourriture, ainsi que les secourir.

• Gestion des forêts

Les drones sont utilisées pour cartographier à la fois les forêts naturelles et celles créées par la main de l’homme, fournissant ainsi des données précises et pertinentes pour l’analyse de la santé des arbres, leur comptage, l’estimation de la biomasse, le calcul de l’indice de canopée et la gestion des plantations.

• Le potentiel de la cinématographie par drone dans l’industrie du cinéma et du divertissement

Ces dernières années, l'industrie du cinéma et du divertissement a connu une forte augmentation de l'utilisation de drones pour les besoins du cinéma. La possibilité de capturer de superbes séquences aériennes à vol d’oiseau a révolutionné la manière dont les films et les émissions de télévision sont filmés.