JACIII Vol.28 No.1 pp. 159-168
doi: 10.20965/jaciii.2024.p0159

Research Paper:

Fair Path Generation for Multiple Agents Using Ant Colony Optimization in Consecutive Pattern Formations

Yoshie Suzuki, Stephen Raharja ORCID Icon, and Toshiharu Sugawara ORCID Icon

Department of Computer Science and Communications Engineering, Waseda University
3-4-1 Okubo, Shinjuku-ku, Tokyo 169-8555, Japan

May 17, 2023
September 11, 2023
January 20, 2024
pattern formation, formation control, ant colony optimization, swarm intelligence, multi-agent system

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.

Formation performed by multiple agents

Formation performed by multiple agents

Cite this article as:
Y. Suzuki, S. Raharja, and T. Sugawara, “Fair Path Generation for Multiple Agents Using Ant Colony Optimization in Consecutive Pattern Formations,” J. Adv. Comput. Intell. Intell. Inform., Vol.28 No.1, pp. 159-168, 2024.
Data files:
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  26. [26] S. Chib and E. Greenberg, “Understanding the metropolis-hastings algorithm,” The American Statistician, Vol.49, No.4, pp. 327-335, 1995.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Feb. 19, 2024