AUT Journal of Mechanical Engineering

AUT Journal of Mechanical Engineering

Minimum Time Search Path Planning for Multiple Fixed-Wing Unmanned Aerial Vehicles with Adaptive Formation

Document Type : Research Article

Authors
Ali Motamedi 1
Mehdi Sabzeh Parvar 1
Mahdi Mortazavi 2
1 Department of Aerospace Engineering, Amirkabir University of Technology, Tehran, Iran
2 Department of Mechanical Engineering, Faculty of Engineering, University of Isfahan, Isfahan, Iran.
10.22060/ajme.2024.22615.6069
Abstract
Planning the flight path for a fleet of fixed-wing unmanned aerial vehicles during search and rescue operations poses a significant challenge as it requires minimizing search time and optimizing the formation of the unmanned aerial vehicles. This paper proposes a novel integration of a leaderfollower formation flight technique for multiple fixed-wing unmanned aerial vehicles with a minimumtime search path planning algorithm. In the first step, the proposed algorithm, based on continuous ant colony optimization, plans a sequence of safe and feasible waypoints for the leader while determining appropriate azimuth angles for the followers. In the next step, the algorithm utilizes a nonlinear threedegree-of-freedom model, developed based on a leader-follower formation flight technique, to plan the followers’ flight paths. Applying Dubins curves based on kinematic constraints of the unmanned aerial vehicles not only reduces computational time but also ensures the feasibility of the best search paths between planned waypoints. Furthermore, in the presence of static obstacles, a developed function in the planning process addresses collision and obstacle avoidance constraints. The effectiveness and performance of the suggested method in detecting targets in minimum-time search missions and the ability of the planner to reconfigure the formation of unmanned aerial vehicles in cluttered environments are demonstrated through comprehensive simulation studies and Monte Carlo analysis .
Keywords
Ant colony optimization
Search and rescue
Reconfiguration
Unmanned aerial vehicle
Dubins curve
Subjects
  1. -P. Yong, Y.-C. Yeong, Human object detection in forest with deep learning based on drone’s vision, in: 2018 4th International Conference on Computer and Information Sciences (ICCOINS), IEEE, 2018, pp. 1-5.
  2. Yu, C. Li, G.G. Yen, A knee-guided differential evolution algorithm for unmanned aerial vehicle path planning in disaster management, Applied Soft Computing, 98 (2021) 106857.
  3. Martinez-Alpiste, G. Golcarenarenji, Q. Wang, J.M. Alcaraz-Calero, Search and rescue operation using UAVs: A case study, Expert Systems with Applications, 178 (2021) 114937.
  4. Zhang, W. Zhou, W. Qin, W. Tang, A novel UAV path planning approach: Heuristic crossing search and rescue optimization algorithm, Expert Systems with Applications, 215 (2023) 119243.
  5. Khalil, S.U. Rahman, I. Ullah, I. Khan, A.J. Alghadhban, M.H. Al-Adhaileh, G. Ali, M. ElAffendi, A UAV-Swarm-Communication Model Using a Machine-Learning Approach for Search-and-Rescue Applications, Drones, 6(12) (2022) 372.
  6. Dong, G. Hu, Time-varying formation control for general linear multi-agent systems with switching directed topologies, Automatica, 73 (2016) 47-55.
  7. Seo, Y. Kim, S. Kim, A. Tsourdos, Collision avoidance strategies for unmanned aerial vehicles in formation flight, IEEE Transactions on aerospace and electronic systems, 53(6) (2017) 2718-2734.
  8. Ueno, S.J. Kwon, Optimal reconfiguration of UAVs in formation flight, in: SICE Annual Conference 2007, IEEE, 2007, pp. 2611-2614.
  9. Hu, M. Wang, C. Zhao, Q. Pan, C. Du, Formation control and collision avoidance for multi-UAV systems based on Voronoi partition, Science China Technological Sciences, 63(1) (2020) 65-72.
  10. Bożko, L. Ambroziak, E. Pawluszewicz, Genetic algorithm for parameters tuning of two stage switching controller for UAV autonomous formation flight, in: Conference on Automation, Springer, 2021, pp. 154-165.
  11. Shao, Y. Peng, C. He, Y. Du, Efficient path planning for UAV formation via comprehensively improved particle swarm optimization, ISA transactions, 97 (2020) 415-430.
  12. Yang, Y. Zhang, Q. Feng, L. Yang, H. Zhang, UAV formation optimization model based on ant colony algorithm and particle swarm optimization algorithm, in: 2023 IEEE 3rd International Conference on Power, Electronics and Computer Applications (ICPECA), IEEE, 2023, pp. 869-875.
  13. Dong, Y. Li, C. Lu, G. Hu, Q. Li, Z. Ren, Time-varying formation tracking for UAV swarm systems with switching directed topologies, IEEE transactions on neural networks and learning systems, 30(12) (2018) 3674-3685.
  14. Liu, Q. Meng, F. Peng, F.L. Lewis, Heterogeneous formation control of multiple UAVs with limited-input leader via reinforcement learning, Neurocomputing, 412 (2020) 63-71.
  15. Lin, M. Wang, X. Zhou, G. Ding, S. Mao, Dynamic spectrum interaction of UAV flight formation communication with priority: A deep reinforcement learning approach, IEEE Transactions on Cognitive Communications and Networking, 6(3) (2020) 892-903.
  16. Li, J. Zhang, L. Dai, K.L. Teo, S. Wang, A hybrid offline optimization method for reconfiguration of multi-UAV formations, IEEE Transactions on Aerospace and Electronic Systems, 57(1) (2020) 506-520.
  17. Harikumar, J. Senthilnath, S. Sundaram, MultiUAV oxyrrhis marina-inspired search and dynamic formation control for forest firefighting, IEEE Transactions on Automation Science and Engineering, 16(2) (2018) 863-873.
  18. -y. Chen, Y.-f. Lu, G.-w. Jia, Y. Li, B.-j. Zhu, J.-c. Lin, Path planning for UAVs formation reconfiguration based on Dubins trajectory, Journal of Central South University, 25(11) (2018) 26642676.
  19. Brown, L. Sun, Dynamic exhaustive mobile target search using unmanned aerial vehicles, IEEE Transactions on Aerospace and Electronic Systems, 55(6) (2019) 3413-3423.
  20. Lanillos, S.K. Gan, E. Besada-Portas, G. Pajares, S. Sukkarieh, Multi-UAV target search using decentralized gradient-based negotiation with expected observation, Information Sciences, 282 (2014) 92-110.
  21. Morin, I. Abi-Zeid, C.-G. Quimper, Ant colony optimization for path planning in search and rescue operations, European Journal of Operational Research, 305(1) (2023) 53-63.
  22. Yao, H. Wang, H. Ji, Gaussian mixture model and receding horizon control for multiple UAV search in complex environment, Nonlinear Dynamics, 88 (2017) 903-919.
  23. Hoffmann, S. Waslander, C. Tomlin, Distributed cooperative search using information-theoretic costs for particle filters, with quadrotor applications, in: AIAA Guidance, Navigation, and Control Conference and Exhibit, 2006, pp. 6576.
  24. W. Cho, H.J. Park, H. Lee, D.H. Shim, S.-Y. Kim, Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations, Computers & Industrial Engineering, 161 (2021) 107612.
  25. Gao, Z. Zhen, H. Gong, A self-organized search and attack algorithm for multiple unmanned aerial vehicles, Aerospace Science and Technology, 54 (2016) 229-240.
  26. Raap, M. Preuß, S. Meyer-Nieberg, Moving target search optimization–a literature review, Computers & Operations Research, 105 (2019) 132140.
  27. Zhen, Y. Chen, L. Wen, B. Han, An intelligent cooperative mission planning scheme of UAV swarm in uncertain dynamic environment, Aerospace Science and Technology, 100 (2020) 105826.
  28. Perez-Carabaza, E. Besada-Portas, J.A. LopezOrozco, J.M. de la Cruz, Ant colony optimization for multi-UAV minimum time search in uncertain domains, Applied Soft Computing, 62 (2018) 789806.
  29. Darsini, N. Ganvkar, K. Gurunathan, R.K. Dash, Minimum Time Search Methods for Unmanned Aerial Vehicles, in: Smart Computing Techniques and Applications: Proceedings of the Fourth International Conference on Smart Computing and Informatics, Volume 1, Springer, 2021, pp. 681-691.
  30. Pérez-Carabaza, J. Scherer, B. Rinner, J.A. López-Orozco, E. Besada-Portas, UAV trajectory optimization for Minimum Time Search with communication constraints and collision avoidance, Engineering Applications of Artificial Intelligence, 85 (2019) 357-371.
  31. Lanillos, E. Besada-Portas, G. Pajares, J.J. Ruz, Minimum time search for lost targets using cross entropy optimization, in: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2012, pp. 602-609.
  32. Pérez-Carabaza, E. Besada-Portas, J.A. LopezOrozco, G. Pajares, Minimum time search in realworld scenarios using multiple UAVs with onboard orientable cameras, Journal of Sensors, 2019 (2019).
  33. ] K. Socha, M. Dorigo, Ant colony optimization for continuous domains, European journal of operational research, 185(3) (2008) 1155-1173.
  34. Babaei, M. Mortazavi, Three-dimensional curvature-constrained trajectory planning based on in-flight waypoints, Journal of Aircraft, 47(4) (2010) 1391-1398.
  35. Motamedi, A. Naghash, Design of Multi-Input Multi-Output Controller for an Unmanned Aerial Vehicle by Eigenstructure Assignment Method, Journal of Aerospace Science and Technology, 14(1) (2021) 117-127.
  36. Zipfel, Modeling and Simulation of Aerospace Vehicle Dynamics–Third edition, in, 2014.
  37. Liu, S. Anavatti, M. Garratt, H.A. Abbass, Modified continuous ant colony optimisation for multiple unmanned ground vehicle path planning, Expert Systems with Applications, 196 (2022) 116605.
  38. Yue, Y. Xi, X. Guan, A new searching approach using improved multi-ant colony scheme for multiUAVs in unknown environments, Ieee Access, 7 (2019) 161094-161102.
  39. Zhang, J. Song, L. Huang, C. Zhang, Distributed cooperative search with collision avoidance for a team of unmanned aerial vehicles using gradient optimization, Journal of Aerospace Engineering, 30(1) (2017) 04016064.
  40. Hu, Y. Liu, G. Wang, Optimal search for moving targets with sensing capabilities using multiple UAVs, Journal of Systems Engineering and Electronics, 28(3) (2017) 526-535.
  41. Li, X. Zhang, W. Yue, Z. Liu, Cooperative search for dynamic targets by multiple UAVs with communication data losses, ISA transactions, 114 (2021) 230-241.
  42. -K. Oh, M.-C. Park, H.-S. Ahn, A survey of multiagent formation control, Automatica, 53 (2015) 424440.
  43. Soleymani, F. Saghafi, Behavior-based acceleration commanded formation flight control, in: ICCAS 2010, IEEE, 2010, pp. 1340-1345.
  44. Perez-Carabaza, J. Bermudez-Ortega, E. BesadaPortas, J.A. Lopez-Orozco, J.M. de la Cruz, A multiuav minimum time search planner based on aco r, in: Proceedings of the genetic and evolutionary computation conference, 2017, pp. 35-42.
  45. Dorigo, G. Di Caro, Ant colony optimization: a new meta-heuristic, in: Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), IEEE, 1999, pp. 1470-1477.
  46. Wang, J. Li, L. Yang, Z. Yang, P. Li, G. Xia, Distributed Multi-Mobile Robot Path Planning and Obstacle Avoidance Based on ACO–DWA in Unknown Complex Terrain, Electronics, 11(14) (2022) 2144.
  47. B. Escario, J.F. Jimenez, J.M. Giron-Sierra, Ant colony extended: experiments on the travelling salesman problem, Expert Systems with Applications, 42(1) (2015) 390-410.
  48. E. Dubins, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, American Journal of mathematics, 79(3) (1957) 497-516.
  49. Roskam, C.-T.E. Lan, Airplane aerodynamics and performance, DARcorporation, 1997.
  50. Kennedy, Swarm intelligence, in: Handbook of nature-inspired and innovative computing: integrating classical models with emerging technologies, Springer, 2006, pp. 187-219.
AUT Journal of Mechanical Engineering
Volume 7, Issue 3
2023
Pages 297-316