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.

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. https://doi.org/10.1109/JAS.2017.7510385
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). https://doi.org/10.3969/j.issn.1673-4785.2011.01.002
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. https://doi.org/10.1109/ICEICE.2011.5777555
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. https://doi.org/10.4028/www.scientific.net/AMM.530-531.1063
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. https://doi.org/10.1109/ICRA.2013.6631164
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. https://doi.org/10.1007/s10846-013-9834-6
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. https://doi.org/10.1109/ROBOT.2001.932890
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. https://doi.org/10.1007/s10846-016-0461-x
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. https://doi.org/10.1007/s10845-010-0404-5
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. https://doi.org/10.1016/j.eswa.2010.11.097
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. https://doi.org/10.1007/s10472-009-9120-2
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. https://doi.org/10.1109/ICCA.2017.8003087
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. https://doi.org/10.1109/IROS.2017.8206000
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. https://doi.org/10.1017/S0263574718000292
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. https://doi.org/10.1631/FITEE.1800551
16. [16] X. Zheng et al., “Multi-robot forest coverage,” 2005 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3852-3857, 2005. https://doi.org/10.1109/IROS.2005.1545323
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). https://doi.org/10.27466/d.cnki.gzzdu.2021.002966
18. [18] W. Hu, “Research on multi-robot path planning and task assignment in obstacle environment,” Master Thesis, Hunan University, 2018 (in Chinese).