Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

Imaginez que vous jouez à une partie de cache-cache à enjeux élevés, mais que la personne que vous cherchez s'enfuit, que la carte est immense et que vous n'avez qu'une paire de jumelles qui deviennent floues si le soleil est trop brillant ou si le vent est trop fort. C'est la réalité quotidienne des équipes de recherche et de sauvetage qui tentent de retrouver des randonneurs égarés ou des survivants dans des zones de catastrophe. Dans le monde de la science, cela est connu sous le nom de « recherche optimale », un casse-tête où les ordinateurs tentent de déterminer le meilleur chemin à prendre pour ne pas perdre de temps précieux. L'idée clé ici est que le temps est l'ennemi ; plus on cherche, plus il devient difficile de trouver quelqu'un car sa localisation devient une supposition plutôt qu'un fait. Pour résoudre cela, les scientifiques utilisent des « drones » (robots volants) équipés de caméras, mais programmer ces drones pour qu'ils suivent l'itinéraire parfait est incroyablement difficile car les drones ont des limites physiques — ils ne peuvent pas tourner instantanément, ils ont une vitesse maximale et ils ne peuvent pas voler éternellement.

Ce document présente une nouvelle méthode ingénieuse pour apprendre aux drones comment chasser des cibles mobiles, comme une personne égarée ou un survivant flottant. Les auteurs, une équipe de chercheurs du Vietnam et de Corée, ont créé un nouvel algorithme appelé « Évolution Différentielle basée sur les coordonnées polaires » (ou PDE pour court). Considérez cela comme un entraîneur super intelligent qui ne se contente pas de dire au drone où aller, mais comment bouger son corps pour y arriver. Au lieu d'utiliser des coordonnées cartésiennes standards (comme « aller 10 mètres à droite, puis 5 mètres en haut »), l'algorithme PDE parle la langue native du drone : « tourne de cet angle et vole cette distance ». En faisant cela, le drone évite de se retrouver coincé dans des impasses ou d'essayer de faire des virages impossibles. Les chercheurs ont testé cette méthode dans des simulations informatiques et avec un vrai drone dans un champ, et ils ont constaté que le PDE était meilleur pour trouver la cible plus rapidement que d'autres méthodes populaires, surtout lorsque la cible était en mouvement et que la zone de recherche était vaste.

Le Problème : La course contre le « Temps d'Or »

Dans la recherche et le sauvetage, il existe un concept appelé le « temps d'or ». Il s'agit de la courte fenêtre qui suit immédiatement la disparition de quelqu'un, lorsque les chances de le retrouver vivant sont les plus élevées. À mesure que le temps s'écoule, les probabilités chutent. Pourquoi ? Parce que la personne peut se déplacer, le vent peut la pousser ou le terrain peut la cacher. Les méthodes de recherche traditionnelles reposent souvent sur des équipes au sol ou des avions pilotés, qui peuvent être lents ou dangereux. C'est ici qu'intervient le drone (UAV). Les drones peuvent foncer sur des terrains dangereux et voir des choses que les humains ne peuvent pas voir. Mais attention : si vous dites simplement à un drone de voler de manière aléatoire, il pourrait rater la cible. Si vous lui dites de voler selon une grille parfaite, il pourrait perdre du temps à survoler des zones vides. L'objectif est de trouver le parfait itinéraire de vol qui maximise la chance de repérer la cible le plus rapidement possible.

Le Cerveau : Comment le drone « pense »

Pour trouver le meilleur chemin, le drone a besoin d'un cerveau capable de prédire où la cible pourrait se trouver. Les auteurs ont modélisé le mouvement de la cible comme un « processus de Markov ». En termes simples, cela signifie que le prochain mouvement de la cible dépend principalement de l'endroit où elle se trouve actuellement et de la façon dont elle se déplace, et non de l'endroit où elle était il y a une heure. C'est comme prédire le mouvement d'une feuille flottant sur une rivière ; vous connaissez la direction du courant, donc vous pouvez deviner où elle sera dans quelques secondes.

Le drone doit également savoir quelle est la qualité de ses « yeux ». Le document utilise un modèle appelé NVESD pour calculer la probabilité de repérer la cible. Il ne s'agit pas seulement de la distance à laquelle se trouve la cible ; il s'agit de la qualité de l'image. Si le soleil est éblouissant, ou si la cible est petite et floue, la probabilité de la voir chute. L'algorithme combine ces deux éléments — où la cible pourrait être et quelle est la probabilité que la caméra puisse la voir — pour créer une « carte de croyance ». Cette carte est comme une carte thermique où les points les plus brillants indiquent la plus haute probabilité que la cible soit là.

La Solution : L'astuce des coordonnées polaires

L'innovation centrale de ce document est la manière dont le drone planifie son itinéraire de vol. La plupart des algorithmes informatiques utilisent des « coordonnées cartésiennes », qui sont comme une grille sur une feuille de papier millimétré (des valeurs x et y). Bien que cela fonctionne pour les mathématiques, c'est terrible pour les drones. Si un drone est en plein vol et doit tourner, un algorithme cartésien pourrait calculer un chemin qui exige que le drone pivote instantanément sur lui-même ou vole plus vite que son moteur ne le permet. C'est comme dire à une voiture de « se déplacer de 5 mètres vers le nord et de 5 mètres vers l'est » sans se soucier du fait que la voiture possède un rayon de braquage minimum.

Les auteurs ont proposé d'utiliser les « coordonnées polaires » à la place. Au lieu de dire « allez au point (x, y) », l'algorithme dit au drone : « Vole cette distance ($\rho$) à cet angle ($\psi$) ». Cela correspond à la façon dont le drone se déplace réellement. En utilisant cette méthode, l'algorithme respecte naturellement les limites physiques du drone. Il ne peut pas suggérer un virage trop serré ou une vitesse trop élevée car les mathématiques sont construites autour de ces limites dès le départ.

Ils ont enveloppé cette idée dans un algorithme d'« Évolution Différentielle » (DE). La DE est un type d'« intelligence en essaim » qui fonctionne comme une équipe d'explorateurs. Imaginez un groupe de randonneurs essayant de trouver le sommet le plus élevé dans une chaîne de montagnes embrumée. Ils ne connaissent pas toute la carte, mais ils partagent des notes. Si un randonneur trouve un point élevé, les autres se déplacent vers cette zone mais essaient aussi des directions légèrement différentes pour voir s'ils peuvent trouver quelque chose d'encore plus haut. La partie « Différentielle » signifie qu'ils regardent la différence entre l'endroit où se trouvent deux randonneurs pour décider de la direction du prochain saut.

Les auteurs ont combiné cette intelligence en essaim avec leur système de coordonnées polaires. Ils l'appellent PDE. Dans leurs simulations, cette équipe de drones virtuels a exploré la zone de recherche de manière beaucoup plus efficace que des équipes utilisant des méthodes standards.

Les Résultats : Simulations et vols réels

Les chercheurs ont testé leur algorithme PDE dans six scénarios différents, allant de petites zones de 600 m x 600 m à de vastes zones de 2000 m x 2000 m. Ils ont comparé le PDE à d'autres algorithmes célèbres comme l'Optimisation par Essaim de Particules (PSO), les Algorithmes Génétiques (GA) et l'Évolution Différentielle (DE) standard.

Dans les simulations informatiques, le PDE a systématiquement trouvé la cible avec une probabilité plus élevée et l'a fait plus rapidement. Par exemple, dans un scénario, le PDE a atteint une probabilité de détection d'environ 0,529, tandis que l'algorithme DE standard n'a réussi qu'à atteindre 0,410. Le document note que le DE standard se retrouve souvent « piégé » dans des optima locaux — ce qui signifie qu'il a trouvé un bon endroit mais n'a pas pu voir le meilleur endroit car il était bloqué dans une boucle. Le PDE, grâce à ses coordonnées polaires, était meilleur pour échapper à ces boucles et trouver le meilleur chemin global.

Ils ne se sont pas arrêtés aux jeux informatiques. Ils ont emmené un vrai drone 3DR Solo dans un champ pour tester la théorie. Le drone a été programmé avec le chemin PDE et a volé au-dessus d'une zone de 80 m x 80 m. Une personne (la cible) marchait à une vitesse de 1,5 m/s. Le drone a suivi le chemin généré par l'algorithme et le chemin qu'il a réellement parcouru correspondait très étroitement au plan. Le drone a réussi à survoler la zone où la cible était attendue, et la caméra a capturé la personne. Les auteurs notent que, bien que le test en conditions réelles ait été un succès, il reposait sur le fait que la cible se déplaçait exactement comme prévu. Dans une situation réelle, les choses sont plus désordonnées, mais le test a prouvé que l'algorithme génère des chemins que les vrais drones peuvent réellement suivre.

Pourquoi c'est important

Le document suggère qu'en parlant la langue du drone (coordonnées polaires) et en utilisant une stratégie de recherche intelligente basée sur le travail d'équipe, nous pouvons rendre les opérations de recherche et de sauvetage plus efficaces. L'algorithme PDE ne se contente pas de trouver un chemin ; il trouve un chemin réalisable qui respecte les limites du drone tout en maximisant les chances de sauvetage. Bien que les auteurs admettent qu'un seul drone ne peut couvrir qu'une zone limitée en raison de l'autonomie de sa batterie, ils suggèrent que cette méthode pourrait être la base d'une flotte de drones travaillant ensemble à l'avenir. Pour l'instant, c'est une étape significative vers la création de robots volants plus intelligents, plus rapides et plus utiles quand chaque seconde compte.