Optimization of UAVs deployment and coordination for exploration and monitoring applications
Optimisation du déploiement et de la coordination de drones pour les applications d'exploration et de surveillance
Résumé
Unmanned Aerial Vehicles (UAVs) have gained tremendous attention lately. These autonomous flying devices have several advantages in terms of deployment cost and processing capabilities, making them a promising solution for a wide range of military and commercial applications such as aerial monitoring, disaster management, packet delivery, traffic control, smart agriculture, etc. In this thesis, we have studied two applications: creating a flying network to connect mobile sensors to a base station and wirelessly charging fixed ground sensors.In the first application, we want to communicate with mobile sensors in a disaster scenario without pre-existing communication infrastructure. These mobile sensors collect essential information that can help us manage the disaster scenario, such as the victims' location, identification of terrain instability, detection of hazardous chemicals, or any other threat. UAVs are a low-cost and effective solution to establish an emergency network that we can use to connect the sensors to the base station. Our goal in this application is to determine the optimal positions the UAVs should occupy at each time step. Therefore, we look for the best flight plans for the UAVs. The UAVs' positioning must ensure the sensors communicate with the base station. In other words, the UAVs must maintain a connected path between the base station and the sensors to allow the sensors to send critical information when necessary. We optimise the UAVs' total distance travelled and energy consumed. We proposed a solution method based on linear programming with column generation, which allows us to find good-quality solutions faster than state of the art methods. We also leverage the better scalability of our model to consider more positions and, consequently, find more precise answers.The second application has a set of fixed ground sensors we need to recharge. Equipping the UAVs and sensors with power harvesting technology allows us to recharge these sensors wirelessly. We aim to organise the UAVs to charge these sensors efficiently. The UAVs' altitude changes their coverage area, and the distance between a UAV and a sensor affects how much power can be received by the sensor. We consider that UAVs can recharge multiple sensors simultaneously when they are in range, which other works often overlook. We proposed a 2 step solution where first, a linear program finds where each drone needs to go and how long it should stay there to ensure the sensors get enough power. Then, greedy scheduling algorithms determine the order in which UAVs visit these spots, ensuring they don't get in each other's way or reduce the charging efficiency. We minimise the total time to charge all sensors in both steps.
Les véhicules aériens sans pilote (UAV) ont suscité une attention considérable récemment. Ces appareils volants autonomes présentent plusieurs avantages en termes de coûts de déploiement et de capacités de traitement, ce qui en fait une solution prometteuse pour un large éventail d'applications militaires et commerciales telles que la surveillance aérienne, la gestion des catastrophes, la livraison de colis, le contrôle de la circulation, l'agriculture intelligente, etc. Dans cette thèse, nous avons étudié deux applications : la création d'un réseau aérien pour connecter des capteurs mobiles à une station de base et la recharge sans fil de capteurs fixes au sol.Dans la première application, nous voulons communiquer avec des capteurs mobiles dans un scénario de catastrophe sans infrastructure de communication préexistante. Ces capteurs mobiles collectent des informations essentielles qui peuvent nous aider à gérer le scénario de catastrophe, telles que l'emplacement des victimes, l'identification de l'instabilité du terrain, la détection de produits chimiques dangereux ou toute autre menace. Les UAV sont une solution peu coûteuse et efficace pour établir un réseau d'urgence que nous pouvons utiliser pour connecter les capteurs à la station de base. Notre objectif dans cette application est de déterminer les positions optimales que les UAV devraient occuper à chaque étape. Par conséquent, nous recherchons les meilleurs plans de vol pour les UAV. Le positionnement des UAV doit garantir que les capteurs communiquent avec la station de base. En d'autres termes, les UAV doivent maintenir un chemin connecté entre la station de base et les capteurs pour permettre aux capteurs d'envoyer des informations critiques si nécessaire. Nous optimisons la distance totale parcourue par les UAV et l'énergie consommée. Nous proposons une méthode de résolution du problème basée sur la programmation linéaire avec génération de colonnes qui permet d'obtenir des solutions de bonne qualité plus rapidement qu'avec les méthodes de l'état de l'art. Nous tirons également parti de la meilleure évolutivité de notre modèle pour envisager plus de positions et, par conséquent, trouver des réponses plus précises.La deuxième application concerne un ensemble de capteurs au sol fixes que nous devons recharger. La technologie de récupération d'énergie, basée sur l'échanges de signaux radio-fréquence, permettant de recharger les batteries des capteurs sans fil. Nous visons à organiser les UAV pour recharger ces capteurs efficacement. L'altitude des UAV modifie leur zone de couverture, et la distance entre un UAV et un capteur affecte la quantité d'énergie qui peut être reçue par le capteur. Nous considérons que les UAV peuvent recharger plusieurs capteurs simultanément lorsqu'ils sont à portée, ce que d'autres travaux négligent souvent. Nous avons proposé une solution en 2 étapes où d'abord, un programme linéaire détermine où chaque drone doit aller et combien de temps il doit y rester pour s'assurer que les capteurs reçoivent suffisamment d'énergie. Ensuite, des algorithmes gloutons d'ordonnancement déterminent l'ordre dans lequel les UAV visitent ces points, en veillant à ce qu'ils ne se gênent pas mutuellement ou ne réduisent pas l'efficacité de la charge. Nous minimisons le temps total nécessaire pour recharger tous les capteurs dans les deux étapes.
Origine : Version validée par le jury (STAR)