An Innovative Approach for Mission Sharing and Route Planning of Swarm Unmanned Aerial Vehicles in Disaster Management

Abstract

Fast and effective response in disaster situations is critical for the success of rescue operations. In this context, swarm Unmanned Aerial Vehicles (UAVs) play an important role in disaster response by rapidly scanning large areas and performing situation assessments. In this paper, we propose an innovative method for task allocation and route planning for swarm UAVs. By combining Genetic Algorithm (GA) and Ant Colony Optimization (ACO) techniques, this method aims to ensure the most efficient movement of UAVs. First, clusters are created using GA to determine the regions of the disaster area that need to be scanned. At this stage, factors such as the capacities of the UAVs, their flight times, and the breadth of their mission areas are taken into account. Each UAV is optimized to scan a specific area assigned to it. Once the clusters are formed, the routes of the UAVs within each cluster are determined by the Ant Colony Algorithm (ACA). The route planning is tested both on Google Maps and in a simulation environment. Google Maps is used to evaluate the accuracy and feasibility of route planning based on real-world conditions, while the simulation environment provides the opportunity to test the behavior of the UAVs and the effectiveness of the routes in a virtual setting. With real-time data integration, the UAVs' route planning can be updated instantly and quickly adapted to emergency situations.

Keywords

• : UAV
• Mission Sharing
• Route Planning
• Disaster management
• optimization

Supporting Institution

TUBITAK

Project Number

123E669

References

1. [1] G. C. Deepak, A. Ladas, Y. A. Sambo, H. Pervaiz, C. Politis, and M. A. Imran, "An overview of post-disaster emergency communication systems in the future networks," IEEE Wireless Communications, vol. 26, no. 6, pp. 132-139, Dec. 2019.
2. [2] L. D. Nguyen, K. K. Nguyen, A. Kortun, and T. Q. Duong, "Real-time deployment and resource allocation for distributed UAV systems in disaster relief," in Proc. IEEE 20th Int. Workshop Signal Process. Advances Wireless Commun. (SPAWC), Cannes, France, Jul. 2019, pp. 1-5.
3. [3] M. Erdelj and E. Natalizio, "UAV-assisted disaster management: Applications and open issues," in Proc. Int. Conf. Comput., Netw. Commun. (ICNC), Kauai, HI, USA, Feb. 2016, pp. 1-5.
4. [4] H. Ijaz, R. Ahmad, R. Ahmed, W. Ahmad, Y. Kai, and W. Jun, "A UAV assisted edge framework for real-time disaster management," IEEE Trans. Geosci. Remote Sens., 2023.
5. [5] D. Erdos, A. Erdos, and S. E. Watkins, "An experimental UAV system for search and rescue challenge," IEEE Aerosp. Electron. Syst. Mag., vol. 28, no. 5, pp. 32-37, May 2013.
6. [6] A. Nedjati, G. Izbirak, B. Vizvari, and J. Arkat, "Complete coverage path planning for a multi-UAV response system in post-earthquake assessment," Robotics, vol. 5, no. 4, pp. 26-41, 2016.
7. [7] S. Değirmen, F. Çavdur, and A. Sebatlı, "Afet Operasyonları Yönetiminde İnsansız Hava Araçlarının Kullanımı: Gözetleme Operasyonları için Rota Planlama," Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, vol. 23, no. 4, pp. 45-55, 2018.
8. [8] M. Kwong, "Nepal earthquake: Drones used by Canadian relief team," CBC News, Apr. 27, 2015. [Online]. Available: https://www.cbc.ca/news/world/nepal-earthquake-drones-used-by-canadian-relief-team-1.3051106. [Accessed: Jul. 08, 2024].

9. [9] N. Nikhil, S. M. Shreyas, G. Vyshnavi, and S. Yadav, "Unmanned Aerial Vehicles (UAV) in Disaster Management Applications", in 2020 Third International Conference on Smart Systems and Inventive Technology (ICSSIT), Tirunelveli, India, 2020, pp. 140-148.
10. [10] STM ThinkTech, "Savunma ve Güvenlik Bilim ve Teknoloji Özel Dosya: Kahramanmaraş Merkezli Depremler Odağında Doğal Afetlerde Teknoloji Kullanımı," May 5, 2023. [Online]. Available: https://thinktech.stm.com.tr/tr/kahramanmaras-merkezli-depremler-odaginda-dogal-afetlerde-teknoloji-kullanimi. [Accessed: Jul. 08, 2024].
11. [11] B. Yang, X. Xiong, H. Liu, Y. Jia, Y. Gao, A. Tolba, and X. Zhang, "Unmanned Aerial Vehicle Assisted Post-Disaster Communication Coverage Optimization Based on Internet of Things Big Data Analysis", Sensors, vol. 23, no. 6795, 2023.
12. [12] Y. Chen, D. Yang, and J. Yu, “Multi-UAV Task Assignment With Parameter and Time-Sensitive Uncertainties Using Modified Two-Part Wolf Pack Search Algorithm,” IEEE Transactions on Aerospace and Electronic Systems, vol. 54, no. 6, pp. 2853-2872, 2018.
13. [13] L. Zhu, Y. Wang, and Z. Wu, “An Adaptive Priority Allocation for Formation UAVs in Complex Context,” IEEE Transactions on Aerospace and Electronic Systems, vol. 57, no. 2, pp. 1002-1015, 2021.
14. [14] N. M. Elfatih, E. S. Ali, and R. A. Saeed, "Navigation and Trajectory Planning Techniques for Unmanned Aerial Vehicles Swarm," in Artificial Intelligence for Robotics and Autonomous Systems Applications, A. T. Azar and A. Koubaa, Eds., vol. 1093, Studies in Computational Intelligence. Cham: Springer, 2023.
15. [15] D. Xie, R. Hu, C. Wang, C. Zhu, H. Xu, and Q. Li, "A Simulation Framework of Unmanned Aerial Vehicles Route Planning Design and Validation for Landslide Monitoring," Remote Sens., vol. 15, no. 24, Art. no. 5758, Dec. 2023.
16. [16] S. Zhang and J. Liu, "Analysis and optimization of multiple unmanned aerial vehicle-assisted communications in post-disaster areas," IEEE Trans. Veh. Technol., vol. 67, no. 12, pp. 12049-12060, Dec. 2018.
17. [17] İ. Aydın and G. Altun, "Hesapsal Zekâ Yöntemleri ile İnsansız Hava Araçları için Rota Planlaması," Dicle Üniversitesi Mühendislik Fakültesi Mühendislik Dergisi, vol. 12, no. 1, pp. 37-45, 2021.
18. [18] X. Wang, T. M. Choi, H. Liu, and X. Yue, "A novel hybrid ant colony optimization algorithm for emergency transportation problems during post-disaster scenarios," IEEE Trans. Syst., Man, Cybern. Syst., vol. 48, no. 4, pp. 545-556, Apr. 2016.
19. [19] X. Zhang, X. Yu, and X. Wu, "Exponential rank differential evolution algorithm for disaster emergency vehicle path planning," IEEE Access, vol. 9, pp. 10880-10892, 2021.
20. [20] Y. Wan, Y. Zhong, A. Ma, and L. Zhang, "An accurate UAV 3-D path planning method for disaster emergency response based on an improved multiobjective swarm intelligence algorithm," IEEE Trans. Cybern., vol. 53, no. 4, pp. 2658-2671, Apr. 2023.
21. [21] J. Scherer et al., "An Autonomous Multi-UAV System for Search and Rescue," in Proc. 1st Workshop Micro Aerial Vehicle Netw., Syst., Appl. Civ. Use, May 2015, pp. 33-38.
22. [22] M. Silvagni, A. Tonoli, E. Zenerino, and M. Chiaberge, "Multipurpose UAV for search and rescue operations in mountain avalanche events," Geomatics, Nat. Hazards Risk, vol. 8, no. 1, pp. 18-33, Jan. 2017.
23. [23] R. Arnold, J. Jablonski, B. Abruzzo, and E. Mezzacappa, "Heterogeneous UAV Multi-Role Swarming Behaviors for Search and Rescue," in Proc. 2020 IEEE Int. Conf. Cogn. Comput. Asp. Situat. Manag. (CogSIMA), 2020, pp. 122-128.
24. [24] E. Karaköse, "Sürü İnsansız Hava Araçlarının Görev Paylaşımı için Genetik Algoritma Tabanlı Bir Yaklaşım," Fırat Üniversitesi Mühendislik Bilim. Derg., vol. 34, no. 1, pp. 351-360, Mar. 2022.
25. [25] L. M. Gladence, V. M. Anu, A. Anderson, I. Stanley, and S. Revathy, "Swarm Intelligence in Disaster Recovery," in Proc. 2021 5th Int. Conf. Intell. Comput. Control Syst. (ICICCS), 2021, pp. 1-8.
26. [26] W. Alawad, N. Ben Halima, and L. Aziz, "An Unmanned Aerial Vehicle (UAV) System for Disaster and Crisis Management in Smart Cities," Electronics, vol. 12, no. 4, p. 1051, Feb. 2023.
27. [27] M. Bakirci and M. M. Ozer, "Post-Disaster Area Monitoring with Swarm UAV Systems for Effective Search and Rescue," in Proc. 2023 10th Int. Conf. Recent Advances Air Space, 2023.
28. [28] R. Masroor, M. Naeem, and W. Ejaz, "Efficient deployment of UAVs for disaster management: A multi-criterion optimization approach," Comput. Commun., vol. 177, pp. 185-194, 2021.
29. [29] J. Wang, Y. Sun, B. Wang, & T. Ushio, “Mission-Aware UAV Deployment for Post-Disaster Scenarios: A Worst-Case SAC-Based Approach,” IEEE Transactions on Vehicular Technology, 2023
30. [30] M. Ashraf, A. Gaydamaka, B. Tan, D. Moltchanov, & Y. Koucheryavy, “Low Complexity “Algorithms for Mission Completion Time Minimization in UAV-Based Emergency Response,” IEEE Transactions on Intelligent Vehicles, 2024.
31. [31] P. Mahajan, P. Balamurugan, A. Kumar, G. S. S. Chalapathi, V. Chamola, & M. Khabbaz, “Multi-“Objective MDP-based Routing In UAV Networks For Search-based Operations,” IEEE Transactions on Vehicular Technology, 2024.
32. [32] X. Li, M. Tao, S. Yang, M. A. Jan, J. Du, L.Liu, & C. Wu, “AI Empowered Intelligent Search for Path Planning in UAV-Assisted Data Collection Networks,” IEEE Internet of Things Journal, 2024
33. [33] P. Wan, G. Xu, J. Chen, & Y. Zhou, “Deep Reinforcement Learning Enabled Multi-UAV Scheduling for Disaster Data Collection With Time-Varying Value,” IEEE Transactions on Intelligent Transportation Systems, 2024
34. [34] M. Mitchell, “An Introduction to Genetic Algorithms,” in MIT Press, Cambridge, MA, USA, 1998.
35. [35] M. Dorigo and G. Di Caro, "Ant colony optimization: a new meta-heuristic," in Proc. 1999 Congr. Evol. Comput.-CEC99, Washington, DC, USA, Jul. 1999, vol. 2, pp. 1470-1477.
36. [36] M. Quigley et al., "ROS: an open-source Robot Operating System," in ICRA Workshop Open Source Software, 2009, vol. 3, no. 3.2, p. 5.
37. [37] P. Y. O. Yoonseok, C. HanCheol, J. RyuWoon, and L. TaeHoon, “ROS Robot Programming,” in Robot Co., Seoul, South Korea, Ltd., 2017.
38. [38] C. Bernardeschi, A. Fagiolini, M. Palmieri, G. Scrima, and F. Sofia, "Ros/gazebo based simulation of co-operative uavs," in Modelling and Simulation for Autonomous Systems: 5th International Conference, MESAS 2018, Prague, Czech Republic, Oct. 2018, Revised Selected Papers, 2019, pp. 321-334.
39. [39] K. Conley, "ROS/Introduction - ROS Wiki," ROS Wiki, 2011. [Online]. Available: http://wiki.ros.org/ROS/Introduction. [Accessed: Mar. 20, 2024].
40. [40] Open Robotics, "Gazebo: Tutorial: Beginner: Overview," Gazebo Sim, 2014. [Online]. Available: https://classic.gazebosim.org/tutorials?cat=guided_b&tut=guided_b1. [Accessed: Mar. 20, 2024].