This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Ant Colony Optimization for Efficient Distance and Time Optimization in Swarm Drone Formation
Corresponding Author(s) : Ronny Mardiyanto
Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control,
Vol. 9, No. 1, February 2024
Abstract
One of the challenges in swarm drone formation is achieving fast and effective formation with optimal distances. In this paper, we propose a swarm drone formation approach utilizing Ant Colony Optimization (ACO) for achieving it. We conducted simulations involving the formation of three or more drones, aiming to identify the best formation based on distance, acceleration, and time criteria. Simulation results demonstrate that formation time is significantly reduced when employing ACO optimization compared to non-optimized methods. Additionally, the optimized formations exhibit shorter inter-drone distances compared to non-optimized formations. By implementing this approach, swarm drone formations can be rapidly established with minimized distances, resulting in substantial battery savings. The simulation encompassed various patterns formed by 3, 5, 10, 15, 20, and 25 drones. The findings indicate that the approach can reduce formation time by varying degrees, ranging from 12% to 51%, across 66% of the conducted experiments, notably for patterns created with a substantial drone count. The degree of diversity observed among the proposed solutions reached 60%, with minimal variances of less than 1% for each.
Keywords
Download Citation
Endnote/Zotero/Mendeley (RIS)BibTeX
- S. Ahirwar, R. Swarnkar, S. Bhukya, and G. Namwade, “Application of Drone in Agriculture,” Int.J.Curr.Microbiol.App.Sci, vol. 8, no. 01, pp. 2500–2505, Jan. 2019. https://doi.org/10.20546/ijcmas.2019.801.264
- S. Candiago, F. Remondino, M. De Giglio, M. Dubbini, and M. Gattelli, “Evaluating Multispectral Images and Vegetation Indices for Precision Farming Applications from UAV Images,” Remote Sensing, vol. 7, no. 4, pp. 4026–4047, Apr. 2015. https://doi.org/10.3390/rs70404026
- S. Zhao, “The Role of Drone Photography in City Mapping,” in Application of Intelligent Systems in Multi-modal Information Analytics, vol. 1234, V. Sugumaran, Z. Xu, and H. Zhou, Eds. Cham: Springer International Publishing, 2021, pp. 343–348. http://dx.doi.org/10.1007/978-3-030-51556-0_50
- V. C. Hollman, “Drone Photography and the Re-aestheticisation of Nature,” in Decolonising and Internationalising Geography, B. Schelhaas, F. Ferretti, A. Reyes Novaes, and M. Schmidt di Friedberg, Eds. Cham: Springer International Publishing, 2020, pp. 57–66. https://doi.org/10.1007/978-3-030-49516-9_6
- L.-S. Yoo, J.-H. Lee, S.-H. Ko, S.-K. Jung, S.-H. Lee, and Y.-K. Lee, “A Drone Fitted With a Magnetometer Detects Landmines,” IEEE Geosci. Remote Sensing Lett., vol. 17, no. 12, pp. 2035–2039, Dec. 2020. https://doi.org/10.1109/LGRS.2019.2962062
- J. Liu, Z. Guan, and X. Xie, “Truck and Drone in Tandem Route Scheduling under Sparse Demand Distribution,” in 2018 8th International Conference on Logistics, Informatics and Service Sciences (LISS), Toronto, ON, Aug. 2018, pp. 1–6. https://doi.org/10.1109/LISS.2018.8593233
- G. Quiroz and S. J. Kim, “A Confetti Drone: Exploring drone entertainment,” in 2017 IEEE International Conference on Consumer Electronics (ICCE), Las Vegas, NV, USA, 2017, pp. 378–381. https://doi.org/10.1109/ICCE.2017.7889362
- A. B. C. News, “Thousands of drones used for light show during Olympics opening ceremony,” ABC News.
- “Drone show to mark countdown to Asian Games 2018,” Republika Online, Jul. 29, 2017.
- P. Wu, Y. Wang, and B. Wang, “An ant colony algorithm for drone path planning,” in 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE), Harbin, China, Dec. 2020, pp. 1559–1562. https://doi.org/10.1109/ICMCCE51767.2020.00341
- Y. Guan, M. Gao, and Y. Bai, “Double-ant Colony Based UAV Path Planning Algorithm,” in Proceedings of the 2019 11th International Conference on Machine Learning and Computing - ICMLC ’19, Zhuhai, China, 2019, pp. 258–262. https://doi.org/10.1145/3318299.3318376
- S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, and J. M. de la Cruz, “Ant colony optimization for multi-UAV minimum time search in uncertain domains,” Applied Soft Computing, vol. 62, pp. 789–806, Jan. 2018. https://doi.org/10.1016/j.asoc.2017.09.009
- W. Zhang and B. Zhang, “Improvement of UAV Track Trajectory Algorithm Based on Ant Colony Algorithm,” in 2019 International Conference on Intelligent Transportation, Big Data & Smart City (ICITBS), Changsha, China, Jan. 2019, pp. 28–31. https://doi.org/10.1109/ICITBS.2019.00016
- L. Ji, C. Zhang, Z. Li, and M. Liu, “Path planning for drones reconnaissance based on ant colony algorithms,” IOP Conf. Ser.: Earth Environ. Sci., vol. 330, no. 5, p. 052047, Oct. 2019. https://doi.org/10.1088/1755-1315/330/5/052047
- C. Li, C. Xueli, and X. Chenfa, “Establishment of UAV Path Planning Model Based on Ant Colony and Simulated Annealing Algorithm,” Journal of Electronics and Information Science, vol. 6, pp. 32–38, 2021. http://dx.doi.org/10.23977/jeis.2021.61005
- F. Ma and F. Xiong, “Research on Path Planning of Plant Protection UAV Based on Grid Method and Improved Ant Colony Algorithm,” IOP Conf. Ser.: Mater. Sci. Eng., vol. 612, no. 5, p. 052053, Oct. 2019. https://doi.org/10.1088/1757-899X/612/5/052053
- Z. Ma, H. Gong, and X. Wang, “An UAV Path Planning Method in Complex Mountainous Area Based on a New Improved Ant Colony Algorithm,” in 2019 International Conference on Artificial Intelligence and Advanced Manufacturing (AIAM), Dublin, Ireland, Oct. 2019, pp. 125–129. https://doi.org/10.1109/AIAM48774.2019.00032
- Z. Huang, X. Zhai, H. Wang, H. Zhou, H. Zhao, and M. Feng, “On the 3D Track Planning for Electric Power Inspection Based on the Improved Ant Colony Optimization and A ∗ Algorithm,” Mathematical Problems in Engineering, vol. 2020, pp. 1–11, Jun. 2020. https://doi.org/10.1155/2020/8295362
- H. T. Dinh, M. H. Cruz Torres, and T. Holvoet, “Dancing UAVs: Using linear programming to model movement behavior with safety requirements,” in 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, Jun. 2017, pp. 326–335. https://doi.org/10.1109/ICUAS.2017.7991352
- C. Kung, W.-S. Yang, T.-Y. Wei, and S.-T. Chao, “The fast flight trajectory verification algorithm for Drone Dance System,” in 2020 IEEE International Conference on Industry 4.0, Artificial Intelligence, and Communications Technology (IAICT), Bali, Indonesia, Jul. 2020, pp. 97–101. https://doi.org/10.1109/IAICT50021.2020.9172016
- L. Bai, Z. Zhao, X. Meng, Y. Wang, Q. Rao and X. Deng, "Research on UAV Formation Simulation and Evaluation Technology," 2022 5th International Conference on Intelligent Autonomous Systems (ICoIAS), Dalian, China, 2022, pp. 166-171. https://doi.org/10.1109/ICoIAS56028.2022.9931226
- Z. Gu, B. Song, Y. Fan and X. Chen, "Design and Verification of UAV Formation Controller based on Leader-Follower Method," 2022 7th International Conference on Automation, Control and Robotics Engineering (CACRE), Xi'an, China, 2022, pp. 38-44. https://doi.org/10.1109/CACRE54574.2022.9834161
- S. -S. Liu, M. -F. Ge and Z. -W. Liu, "Multi-UAV Formation Control Based on Distributed Model Predictive Control*," 2022 IEEE International Conference on Cyborg and Bionic Systems (CBS), Wuhan, China, 2023, pp. 292-297. https://doi.org/10.1109/CBS55922.2023.10115368
- Y. Hu, C. Liu, P. Wang, M. Zhang, H. Mu and Q. Yuan, "Multi-UAV Formation Control Based on Parameter Optimization ADRC," 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS), Chengdu, China, 2022, pp. 168-172. https://doi.org/10.1109/CCIS57298.2022.10016414
- S. Kim, H. Cho and D. Jung, "Circular Formation Guidance of Fixed-Wing UAVs Using Mesh Network," in IEEE Access, vol. 10, pp. 115295-115306, 2022. https://doi.org/10.1109/ACCESS.2022.3218673
References
S. Ahirwar, R. Swarnkar, S. Bhukya, and G. Namwade, “Application of Drone in Agriculture,” Int.J.Curr.Microbiol.App.Sci, vol. 8, no. 01, pp. 2500–2505, Jan. 2019. https://doi.org/10.20546/ijcmas.2019.801.264
S. Candiago, F. Remondino, M. De Giglio, M. Dubbini, and M. Gattelli, “Evaluating Multispectral Images and Vegetation Indices for Precision Farming Applications from UAV Images,” Remote Sensing, vol. 7, no. 4, pp. 4026–4047, Apr. 2015. https://doi.org/10.3390/rs70404026
S. Zhao, “The Role of Drone Photography in City Mapping,” in Application of Intelligent Systems in Multi-modal Information Analytics, vol. 1234, V. Sugumaran, Z. Xu, and H. Zhou, Eds. Cham: Springer International Publishing, 2021, pp. 343–348. http://dx.doi.org/10.1007/978-3-030-51556-0_50
V. C. Hollman, “Drone Photography and the Re-aestheticisation of Nature,” in Decolonising and Internationalising Geography, B. Schelhaas, F. Ferretti, A. Reyes Novaes, and M. Schmidt di Friedberg, Eds. Cham: Springer International Publishing, 2020, pp. 57–66. https://doi.org/10.1007/978-3-030-49516-9_6
L.-S. Yoo, J.-H. Lee, S.-H. Ko, S.-K. Jung, S.-H. Lee, and Y.-K. Lee, “A Drone Fitted With a Magnetometer Detects Landmines,” IEEE Geosci. Remote Sensing Lett., vol. 17, no. 12, pp. 2035–2039, Dec. 2020. https://doi.org/10.1109/LGRS.2019.2962062
J. Liu, Z. Guan, and X. Xie, “Truck and Drone in Tandem Route Scheduling under Sparse Demand Distribution,” in 2018 8th International Conference on Logistics, Informatics and Service Sciences (LISS), Toronto, ON, Aug. 2018, pp. 1–6. https://doi.org/10.1109/LISS.2018.8593233
G. Quiroz and S. J. Kim, “A Confetti Drone: Exploring drone entertainment,” in 2017 IEEE International Conference on Consumer Electronics (ICCE), Las Vegas, NV, USA, 2017, pp. 378–381. https://doi.org/10.1109/ICCE.2017.7889362
A. B. C. News, “Thousands of drones used for light show during Olympics opening ceremony,” ABC News.
“Drone show to mark countdown to Asian Games 2018,” Republika Online, Jul. 29, 2017.
P. Wu, Y. Wang, and B. Wang, “An ant colony algorithm for drone path planning,” in 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE), Harbin, China, Dec. 2020, pp. 1559–1562. https://doi.org/10.1109/ICMCCE51767.2020.00341
Y. Guan, M. Gao, and Y. Bai, “Double-ant Colony Based UAV Path Planning Algorithm,” in Proceedings of the 2019 11th International Conference on Machine Learning and Computing - ICMLC ’19, Zhuhai, China, 2019, pp. 258–262. https://doi.org/10.1145/3318299.3318376
S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, and J. M. de la Cruz, “Ant colony optimization for multi-UAV minimum time search in uncertain domains,” Applied Soft Computing, vol. 62, pp. 789–806, Jan. 2018. https://doi.org/10.1016/j.asoc.2017.09.009
W. Zhang and B. Zhang, “Improvement of UAV Track Trajectory Algorithm Based on Ant Colony Algorithm,” in 2019 International Conference on Intelligent Transportation, Big Data & Smart City (ICITBS), Changsha, China, Jan. 2019, pp. 28–31. https://doi.org/10.1109/ICITBS.2019.00016
L. Ji, C. Zhang, Z. Li, and M. Liu, “Path planning for drones reconnaissance based on ant colony algorithms,” IOP Conf. Ser.: Earth Environ. Sci., vol. 330, no. 5, p. 052047, Oct. 2019. https://doi.org/10.1088/1755-1315/330/5/052047
C. Li, C. Xueli, and X. Chenfa, “Establishment of UAV Path Planning Model Based on Ant Colony and Simulated Annealing Algorithm,” Journal of Electronics and Information Science, vol. 6, pp. 32–38, 2021. http://dx.doi.org/10.23977/jeis.2021.61005
F. Ma and F. Xiong, “Research on Path Planning of Plant Protection UAV Based on Grid Method and Improved Ant Colony Algorithm,” IOP Conf. Ser.: Mater. Sci. Eng., vol. 612, no. 5, p. 052053, Oct. 2019. https://doi.org/10.1088/1757-899X/612/5/052053
Z. Ma, H. Gong, and X. Wang, “An UAV Path Planning Method in Complex Mountainous Area Based on a New Improved Ant Colony Algorithm,” in 2019 International Conference on Artificial Intelligence and Advanced Manufacturing (AIAM), Dublin, Ireland, Oct. 2019, pp. 125–129. https://doi.org/10.1109/AIAM48774.2019.00032
Z. Huang, X. Zhai, H. Wang, H. Zhou, H. Zhao, and M. Feng, “On the 3D Track Planning for Electric Power Inspection Based on the Improved Ant Colony Optimization and A ∗ Algorithm,” Mathematical Problems in Engineering, vol. 2020, pp. 1–11, Jun. 2020. https://doi.org/10.1155/2020/8295362
H. T. Dinh, M. H. Cruz Torres, and T. Holvoet, “Dancing UAVs: Using linear programming to model movement behavior with safety requirements,” in 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, Jun. 2017, pp. 326–335. https://doi.org/10.1109/ICUAS.2017.7991352
C. Kung, W.-S. Yang, T.-Y. Wei, and S.-T. Chao, “The fast flight trajectory verification algorithm for Drone Dance System,” in 2020 IEEE International Conference on Industry 4.0, Artificial Intelligence, and Communications Technology (IAICT), Bali, Indonesia, Jul. 2020, pp. 97–101. https://doi.org/10.1109/IAICT50021.2020.9172016
L. Bai, Z. Zhao, X. Meng, Y. Wang, Q. Rao and X. Deng, "Research on UAV Formation Simulation and Evaluation Technology," 2022 5th International Conference on Intelligent Autonomous Systems (ICoIAS), Dalian, China, 2022, pp. 166-171. https://doi.org/10.1109/ICoIAS56028.2022.9931226
Z. Gu, B. Song, Y. Fan and X. Chen, "Design and Verification of UAV Formation Controller based on Leader-Follower Method," 2022 7th International Conference on Automation, Control and Robotics Engineering (CACRE), Xi'an, China, 2022, pp. 38-44. https://doi.org/10.1109/CACRE54574.2022.9834161
S. -S. Liu, M. -F. Ge and Z. -W. Liu, "Multi-UAV Formation Control Based on Distributed Model Predictive Control*," 2022 IEEE International Conference on Cyborg and Bionic Systems (CBS), Wuhan, China, 2023, pp. 292-297. https://doi.org/10.1109/CBS55922.2023.10115368
Y. Hu, C. Liu, P. Wang, M. Zhang, H. Mu and Q. Yuan, "Multi-UAV Formation Control Based on Parameter Optimization ADRC," 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS), Chengdu, China, 2022, pp. 168-172. https://doi.org/10.1109/CCIS57298.2022.10016414
S. Kim, H. Cho and D. Jung, "Circular Formation Guidance of Fixed-Wing UAVs Using Mesh Network," in IEEE Access, vol. 10, pp. 115295-115306, 2022. https://doi.org/10.1109/ACCESS.2022.3218673