This study proposes a method to automatically generate paths for multiple autonomous agents to collectively form a sequence of consecutive patterns. Several studies have considered minimizing the total travel distances of all agents for formation transitions in applications with multiple self-driving robots, such as unmanned aerial vehicle shows by drones or group actions in which self-propelled robots synchronously move together, consecutively transforming the patterns without collisions. However, few studies consider fairness in travel distance between agents, which can lead to battery exhaustion for certain agents and thereafter reduced operating time. Furthermore, because these group actions are usually performed with a large number of agents, they can have only small batteries to reduce cost and weight, but their performance time depends on the battery duration. The proposed method, which is based on ant colony optimization (ACO), considers the fairness in distances traveled by agents as well as the less total traveling distances, and can achieve long transitions in both three- and two-dimensional spaces. Our experiments demonstrate that the proposed method based on ACO allows agents to execute more formation patterns without collisions than the conventional method, which is also based on ACO.

1. [1] D. C. Tsouros, S. Bibi, and P. G. Sarigiannidis, “A review on UAV-based applications for precision agriculture,” Information, Vol.10, No.11, Article No.349, 2019. https://doi.org/10.3390/info10110349
2. [2] F. Racek et al., “Tracking, aiming, and hitting the UAV with ordinary assault rifle,” Proc. SPIE Vol.10441, Counterterrorism, Crime Fighting, Forensics, and Surveillance Technologies, Article No.104410C, 2017. https://doi.org/10.1117/12.2276310
3. [3] B. D. Song, K. Park, and J. Kim, “Persistent UAV delivery logistics: MILP formulation and efficient heuristic,” Computers & Industrial Engineering, Vol.120, pp. 418-428, 2018. https://doi.org/10.1016/j.cie.2018.05.013
4. [4] M. A. Ma’sum et al., “Simulation of intelligent unmanned aerial vehicle (UAV) for military surveillance,” 2013 Int. Conf. on Advanced Computer Science and Information Systems (ICACSIS), pp. 161-166, 2013. https://doi.org/10.1109/ICACSIS.2013.6761569
5. [5] K. S. Kappel et al., “Strategies for patrolling missions with multiple UAVs,” J. of Intelligent & Robotic Systems, Vol.99, No.3, pp. 499-515, 2020. https://doi.org/10.1007/s10846-019-01090-2
6. [6] A. Suhartono and R. Mardiyanto, “Pattern forming acceleration for dancing UAVs using ant colony optimization,” 2020 Int. Seminar on Intelligent Technology and its Applications (ISITIA), pp. 279-284, 2020. https://doi.org/10.1109/ISITIA49792.2020.9163718
7. [7] Y. Suzuki, S. Raharja, and T. Sugawara, “Fair formation control of multiple agents using ant colony optimization,” 2022 Joint 12th Int. Conf. on Soft Computing and Intelligent Systems and 23rd Int. Symp. on Advanced Intelligent Systems (SCIS&ISIS), 2022. https://doi.org/10.1109/SCISISIS55246.2022.10002048
8. [8] B. D. O. Anderson et al., “UAV formation control: Theory and application,” V. D. Blondel, S. P. Boyd, and H. Kimura (Eds.), “Recent Advances in Learning and Control,” pp. 15-33, Springer, 2008. https://doi.org/10.1007/978-1-84800-155-8_2
9. [9] A. Khasawneh et al., “Human adaptation to latency in teleoperated multi-robot human-agent search and rescue teams,” Automation in Construction, Vol.99, pp. 265-277, 2019. https://doi.org/10.1016/j.autcon.2018.12.012
10. [10] L. Li et al., “Exact and heuristic multi-robot Dubins coverage path planning for known environments,” Sensors, Vol.23, No.5, Article No.2560, 2023. https://doi.org/10.3390/s23052560
11. [11] A. Nath, A. R. Arun, and R. Niyogi, “A distributed approach for road clearance with multi-robot in urban search and rescue environment,” Int. J. of Intelligent Robotics and Applications, Vol.3, No.4, pp. 392-406, 2019. https://doi.org/10.1007/s41315-019-00111-5
12. [12] S.-K. Pang, Y.-H. Li, and H. Yi, “Joint formation control with obstacle avoidance of towfish and multiple autonomous underwater vehicles based on graph theory and the null-space-based method,” Sensors, Vol.19, No.11, Article No.2591, 2019. https://doi.org/10.3390/s19112591
13. [13] H. Xiao and C. L. P. Chen, “Leader-follower consensus multi-robot formation control using neurodynamic-optimization-based nonlinear model predictive control,” IEEE Access, Vol.7, pp. 43581-43590, 2019. https://doi.org/10.1109/ACCESS.2019.2907960
14. [14] J. Zhang, J. Yan, and P. Zhang, “Multi-UAV formation control based on a novel back-stepping approach,” IEEE Trans. on Vehicular Technology, Vol.69, No.3, pp. 2437-2448, 2020. https://doi.org/10.1109/TVT.2020.2964847
15. [15] J. Hu et al., “Voronoi-based multi-robot autonomous exploration in unknown environments via deep reinforcement learning,” IEEE Trans. on Vehicular Technology, Vol.69, No.12, pp. 14413-14423, 2020. https://doi.org/10.1109/TVT.2020.3034800
16. [16] E. Olcay, F. Schuhmann, and B. Lohmann, “Collective navigation of a multi-robot system in an unknown environment,” Robotics and Autonomous Systems, Vol.132, Article No.103604, 2020. https://doi.org/10.1016/j.robot.2020.103604
17. [17] F. Adolf et al., “Probabilistic roadmaps and ant colony optimization for UAV mission planning,” IFAC Proc. Volumes, Vol.40, No.15, pp. 264-269, 2007. https://doi.org/10.3182/20070903-3-FR-2921.00046
18. [18] S. Konatowski and P. Pawłowski, “Ant colony optimization algorithm for UAV path planning,” 2018 14th Int. Conf. on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), pp. 177-182, 2018. https://doi.org/10.1109/TCSET.2018.8336181
19. [19] Y. Li et al., “Multi-UAV cooperative mission assignment algorithm based on ACO method,” 2020 Int. Conf. on Computing, Networking and Communications (ICNC), pp. 304-308, 2020. https://doi.org/10.1109/ICNC47757.2020.9049667
20. [20] Z. Nie and H. Zhao, “Research on robot path planning based on Dijkstra and ant colony optimization,” 2019 Int. Conf. on Intelligent Informatics and Biomedical Sciences (ICIIBMS), pp. 222-226, 2019. https://doi.org/10.1109/ICIIBMS46890.2019.8991502
21. [21] L. Wang et al., “3D path planning for the ground robot with improved ant colony optimization,” Sensors, Vol.19, No.4, Article No.815, 2019. https://doi.org/10.3390/s19040815
22. [22] C. Zhang et al., “UAV path planning method based on ant colony optimization,” 2010 Chinese Control and Decision Conf., pp. 3790-3792, 2010. https://doi.org/10.1109/CCDC.2010.5498477
23. [23] N. Melaouene and R. Romadi, “An enhanced routing algorithm using ant colony optimization and VANET infrastructure,” MATEC Web of Conf., Vol.259, Article No.02009, 2019. https://doi.org/10.1051/matecconf/201925902009
24. [24] B. B. Rao, V. V. Kumari, and K. V. S. V. N. Raju, “Semantic similarity computation: Ant colony optimization algorithm using ontology,” 2010 Int. Conf. on Intelligent Network and Computing (ICINC 2010), pp. 199-204, 2010.
25. [25] H.-P. Shih, “Two algorithms for maximum and minimum weighted bipartite matching,” Master’s Thesis, National Taiwan University, 2008. https://doi.org/10.6342/NTU.2008.00324
26. [26] S. Chib and E. Greenberg, “Understanding the metropolis-hastings algorithm,” The American Statistician, Vol.49, No.4, pp. 327-335, 1995. https://doi.org/10.2307/2684568