Un nouvel algorithme empêche les drones d’entrer en collision dans les airs | Nouvelles du MIT

Lorsque plusieurs drones travaillent ensemble dans le même espace aérien, pulvérisant peut-être des pesticides sur un champ de maïs, il y a un risque qu’ils se percutent.

Pour aider à éviter ces accidents coûteux, les chercheurs du MIT ont introduit un système appelé MADER en 2020. Ce planificateur d’itinéraire multifactoriel permet à un groupe de drones de créer des trajectoires optimales et sans collision. Chaque agent diffuse son itinéraire afin que les autres drones sachent où il prévoit d’aller. Les agents prennent ensuite en compte les chemins des autres lorsqu’ils optimisent les leurs pour s’assurer qu’ils ne se heurtent pas.

Mais lorsque l’équipe a testé le système sur de vrais drones, ils ont constaté que si le drone ne disposait pas d’informations à jour sur les trajectoires de ses partenaires, il pourrait choisir par inadvertance une trajectoire qui conduirait à une collision. Les chercheurs ont réorganisé leur système et déploient maintenant Robust MADER, un planificateur d’itinéraire multi-facteurs qui génère des itinéraires sans collision même lorsque les communications entre les clients sont retardées.

« MADER a très bien fonctionné dans les simulations, mais il n’a pas été testé dans le matériel. Nous avons donc construit un tas de drones et commencé à les faire voler. Les drones ont besoin de se parler pour partager des chemins, mais une fois qu’ils commencent à voler, vous réalisez rapidement Le gros problème, c’est qu’il y a toujours des retards dans les communications qui entraînent certaines pannes », explique Kota Kondo, étudiant diplômé en aéronautique et astronautique.

L’algorithme comprend une étape de vérification du délai pendant laquelle le drone attend un certain temps avant de s’engager sur une trajectoire nouvelle et améliorée. S’il reçoit des informations de trajectoire supplémentaires d’autres drones pendant la période de retard, il peut abandonner sa nouvelle trajectoire et recommencer le processus d’optimisation.

Lorsque Kondo et ses collègues ont testé le système Robust MADER, à la fois dans des simulations et des essais en vol avec de vrais drones, il a atteint un taux de réussite de 100 % dans la création de trajectoires sans collision. Bien que le temps de trajet du drone ait été légèrement plus lent qu’il ne le serait pour d’autres méthodes, il n’y a pas d’autres lignes de base qui peuvent garantir la sécurité.

« Si vous voulez voler de manière plus sûre, vous devez être prudent, il est donc raisonnable que si vous ne voulez pas heurter un obstacle, il vous faudra plus de temps pour atteindre votre destination. Si vous heurtez quelque chose, peu importe comment vous êtes rapide, cela n’a pas vraiment d’importance parce que vous n’arriverez pas à destination », dit Kondo.

Fichier de livres Kondo papier Avec Jesus Tordesillas, chercheur postdoctoral ; Parker C. Lusk, étudiant diplômé ; Reynaldo Figueroa, Juan Rashid et Josef Merkel, étudiants de premier cycle du MIT ; et l’auteur principal Jonathan P. How, professeur d’aéronautique et d’astronautique Richard C. McLaurin et membre du MIT-IBM Watson AI Lab. La recherche sera présentée à la Conférence internationale sur la robotique et l’automatisation.

Pistes de planification

MADER est un planificateur d’itinéraire asynchrone, décentralisé et multi-agents. Cela signifie que chaque drone trace son propre chemin, et que si tous les clients doivent s’accorder sur chaque nouveau chemin, ils n’ont pas besoin de se mettre d’accord en même temps. Cela rend MADER plus évolutif que d’autres approches, car il serait très difficile pour des milliers de drones de s’entendre sur un chemin à la fois. En raison de sa nature décentralisée, le système fonctionnera également mieux dans des environnements réels où les drones peuvent s’éloigner de l’ordinateur central.

Avec MADER, chaque drone optimise une nouvelle trajectoire grâce à un algorithme qui intègre les trajectoires qu’il a reçues des autres agents. En améliorant et en diffusant sans cesse leurs nouvelles trajectoires, les drones évitent les collisions.

Mais un agent peut avoir partagé son nouvel itinéraire il y a plusieurs secondes, mais un autre agent ne l’a pas reçu tout de suite car la connexion a été retardée. Dans les environnements réels, les signaux sont souvent retardés en raison d’interférences provenant d’autres appareils ou de facteurs environnementaux tels que les intempéries. En raison de ce retard inévitable, un drone peut s’engager par inadvertance sur une nouvelle trajectoire qui le place sur une trajectoire de collision.

Le système robuste de MADER empêche de telles collisions car chaque agent dispose de deux chemins disponibles. Il garde une voie qu’il sait sûre et l’a déjà vérifiée pour les collisions potentielles. Tout en suivant ce chemin d’origine, le drone optimise un nouveau chemin mais ne s’engage pas sur le nouveau chemin tant qu’il n’a pas terminé l’étape de vérification du délai.

Lors d’un contrôle de retard, le drone passe un temps fixe à rechercher à plusieurs reprises les communications d’autres agents pour voir si sa nouvelle route est sûre. S’il détecte une collision potentielle, il abandonne le nouveau chemin et recommence le processus d’optimisation.

Kondo dit que la durée d’un contrôle de retard dépend de la distance et des facteurs environnementaux qui peuvent entraver les communications. Si les agents sont éloignés de plusieurs kilomètres, par exemple, la période de vérification des délais doit être plus longue.

Complètement sans collision

Les chercheurs ont testé leur nouvelle approche en exécutant des centaines de simulations dans lesquelles ils ont artificiellement introduit des retards de communication. Dans chaque simulation, le Robust MADER a réussi à 100 % à créer des trajectoires sans collision, tandis que toutes les lignes de base ont provoqué des collisions.

Les chercheurs ont également construit six drones et deux obstacles aériens et testé Robust MADER dans un environnement de vol multi-agents. Ils ont découvert que même si l’utilisation de la version originale de MADER dans cet environnement aurait entraîné sept collisions, Robust MADER n’a provoqué aucun plantage dans aucune des expériences matérielles.

« Jusqu’à ce que vous utilisiez réellement le matériel, vous ne savez pas ce qui pourrait causer un problème. Parce que nous savons qu’il y a une différence entre les simulations et le matériel, nous avons rendu l’algorithme robuste, donc il a fonctionné sur de vrais drones, et voir cela en action était très gratifiant », dit Kondo.

Les drones ont pu voler à une vitesse de 3,4 mètres par seconde en utilisant Robust MADER, bien que leur temps de trajet moyen soit légèrement plus long que certaines lignes de base. Mais aucune autre méthode n’était complètement sans collision dans chaque essai.

À l’avenir, Kondo et ses collaborateurs souhaitent tester Robust MADER à l’extérieur, où de nombreux obstacles et types de bruit peuvent affecter les communications. Ils souhaitent également équiper les drones de capteurs optiques afin qu’ils puissent détecter des facteurs ou d’autres obstacles, prédire leurs mouvements et inclure ces informations dans les améliorations de trajectoire.

Ce travail a été soutenu par Boeing Research and Technology.