JACIII Vol.27 No.6 pp. 1183-1191
doi: 10.20965/jaciii.2023.p1183

Research Paper:

Multi-Robot Cooperative Multi-Area Coverage Based on Circular Coding Genetic Algorithm

Bin Xin*,**, Heng Wang*,†, and Ming Li***

*School of Automation, Beijing Institute of Technology
No.5 South Street, Zhongguancun, Haidian District, Beijing 100081, China

Corresponding author

**Key Laboratory of Intelligent Control and Decision of Complex Systems
No.5 South Street, Zhongguancun, Haidian District, Beijing 100081, China

***BIT Navigation and Control Technology Co., Ltd.
Beijing , China

March 18, 2023
August 4, 2023
November 20, 2023
cooperative area coverage, genetic algorithm, multiple robots, area allocation

This paper studies the cooperative multi-area coverage problem with obstacles, which requires a group of robots to cover an area while avoiding collisions. This problem is very common in scenarios such as garbage removal, mine clearance, and regional information collection. The currently proposed algorithms usually have the problem of high redundancy and weak scene scalability. This paper designs a cooperative area coverage algorithm for multiple robots. First, a set of rules is proposed to divide the area to be covered into several small areas. Then, a genetic algorithm based on circular coding is designed to allocate these divided areas to several robots. Finally, the coverage path of the robot is designed using the zigzag method, so that the robot can cover the area allocated to it. Through computational experiments, it has been verified that this algorithm has efficiency advantages over state-of-the-art algorithms in certain scenarios and has scalability for different scenarios.

Cite this article as:
B. Xin, H. Wang, and M. Li, “Multi-Robot Cooperative Multi-Area Coverage Based on Circular Coding Genetic Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.27 No.6, pp. 1183-1191, 2023.
Data files:
  1. [1] D. Wu et al., “Gini coefficient-based task allocation for multi-robot systems with limited energy resources,” IEEE/CAA J. of Automatica Sinica, Vol.5, No.1, pp. 155-168, 2018.
  2. [2] J. Wu et al., “A survey of recent advances in cooperative multi-robot systems,” CAAI Trans. on Intelligent System, Vol.6, No.1, pp. 13-27, 2011 (in Chinese).
  3. [3] Y. Liang et al., “Dynamic coverage path planning and obstacle avoidance for cleaning robot based on behavior,” 2011 Int. Conf. on Electric Information and Control Engineering, pp. 4952-4956, 2011.
  4. [4] W. Ji et al., “Obstacle avoidance path planning for harvesting robot manipulator based on MAKLINK graph and improved ant colony algorithm,” Applied Mechanics and Materials, Vols.530-531, pp. 1063-1067, 2014.
  5. [5] E. Galceran and M. Carreras, “Planning coverage paths on bathymetric maps for in-detail inspection of the ocean floor,” 2013 IEEE Int. Conf. on Robotics and Automation, pp. 4159-4164, 2013.
  6. [6] I. A. Hameed, “Intelligent coverage path planning for agricultural robots and autonomous machines on three-dimensional terrain,” J. of Intelligent & Robotic Systems, Vol.74, Nos.3-4, pp. 965-983, 2014.
  7. [7] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” 2001 IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 1927-1933, 2001.
  8. [8] A. C. Kapoutsis, S. A. Chatzichristofis, and E. B. Kosmatopoulos, “DARP: Divide areas algorithm for optimal multi-robot coverage path planning,” J. of Intelligent & Robotic Systems, Vol.86, No.3, pp. 663-680, 2017.
  9. [9] M. Kapanoglu et al., “A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time,” J. of Intelligent Manufacturing, Vol.23, No.4, pp. 1035-1045, 2012.
  10. [10] M. Elango, S. Nachiappan, and M. K. Tiwari, “Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms,” Expert Systems with Applications, Vol.38, No.6, pp. 6486-6491, 2011.
  11. [11] I. Rekleitis et al., “Efficient boustrophedon multi-robot coverage: An algorithmic approach,” Annals of Mathematics and Artificial Intelligence, Vol.52, No.2, pp. 109-142, 2008.
  12. [12] B. Xin et al., “Distributed multi-robot motion planning for cooperative multi-area coverage,” 2017 13th IEEE Int. Conf. on Control & Automation (ICCA), pp. 361-366, 2017.
  13. [13] N. Karapetyan et al., “Efficient multi-robot coverage of a known environment,” 2017 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 1846-1852, 2017.
  14. [14] H. Azpúrua et al., “Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys,” Robotica, Vol.36, No.8, pp. 1144-1166, 2018.
  15. [15] G.-Q. Gao and B. Xin, “A-STC: Auction-based spanning tree coverage algorithm formotion planning of cooperative robots,” Frontiers of Information Technology & Electronic Engineering, Vol.20, No.1, pp. 18-31, 2019.
  16. [16] X. Zheng et al., “Multi-robot forest coverage,” 2005 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3852-3857, 2005.
  17. [17] S. Zhang, “Research on task scheduling algorithm for high performance computing based on genetic-ant colony,” Master Thesis, Zhengzhou University, 2021 (in Chinese).
  18. [18] W. Hu, “Research on multi-robot path planning and task assignment in obstacle environment,” Master Thesis, Hunan University, 2018 (in Chinese).

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

Last updated on Nov. 24, 2023