single-jc.php

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

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

Received:
May 17, 2023
Accepted:
September 11, 2023
Published:
January 20, 2024
Keywords:
pattern formation, formation control, ant colony optimization, swarm intelligence, multi-agent system
Abstract

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:
References
  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

*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