Complete Coverage Path Planning for Multiple Robots for Facade Maintenance Operations

doi:10.3778/j.issn.1002-8331.2208-0246

Abstract

Abstract: The current multi-robot complete coverage algorithm is aimed at the problems of uneven task distribution, inadequate consideration of flexibility in the selection of robot starting and ending positions, single objective of algorithm solution, and inflexible coverage of complex infeasible domain maps. Combined with a method for solving the multiple traveling salesman problems, the improved immune genetic algorithm is applied to multi-robot complete coverage path planning for facade maintenance operations. The method utilizes a region decomposition method that relies on infeasible domain distribution to decompose the region to be covered into several sub-regions. Minimizing the maximum work duration and the total workload of multiple robots, an adaptation calculation method is designed based on the premise that the coverage task is equally divided using a dynamic equalization operator and considering the characteristics of arbitrary starting and ending positions of robots for facade maintenance operations. The global approximate optimal solution is also found by using a stepped clone selection operator combined with a dynamic programming algorithm. Then, the transposition operator with heuristically superior chromosome fragments is used to speed up the convergence of the algorithm. Finally, the effectiveness and stability of the algorithm as well as the computational quality of the algorithm are verified through simulation and comparison experiments of complex maps.

Key words: multiple robots, complete coverage path planning, traveling salesman problem, immune genetic algorithm, multi-optimization objectives

摘要： 针对目前多机器人全覆盖算法存在任务分配不均、对机器人起始位置和终点位置选择的灵活性考虑不充分、算法求解目标单一以及对复杂不可行域地图覆盖不灵活等问题。将改进的免疫遗传算法结合求解多旅行商问题的综合方法，应用于立面维护作业的多机器人全覆盖路径规划中。该方法利用一种依靠不可行域分布的区域分解方法，将待覆盖区域分解为若干个子区域。以使用动态均分算子均分覆盖任务并考虑立面维护作业机器人起点位置和终点位置的任意性特点为前提，设计具有多机器人工作中最大的工作时长最小和多机器人总工作量最小两个求解目标的适应度计算方法。同时利用结合了动态规划算法的阶梯型克隆选择算子寻找全局近似最优解，再利用具有启发式的优秀染色体片段移植算子加快算法收敛速度。通过复杂地图的仿真实验以及对比实验，验证算法有效性和稳定性以及算法的运算质量。

关键词: 多机器人, 全覆盖路径规划, 旅行商问题, 免疫遗传算法, 多优化目标

XIE Bicheng, ZHANG Xiaojun. Complete Coverage Path Planning for Multiple Robots for Facade Maintenance Operations[J]. Computer Engineering and Applications, 2023, 59(24): 319-327.

谢必成, 张小俊. 立面维护作业的多机器人全覆盖路径规划[J]. 计算机工程与应用, 2023, 59(24): 319-327.

References

[1] AMEED I A.Motion planning for autonomous landmine detection and clearance robots[C]//2016 International Workshop on Recent Advances in Robotics and Sensor Technology for Humanitarian Demining and Counter-IEDs（RST），2016：1-5.
[2] 王宁，韩雨晓，王雅萱，等.农业机器人全覆盖作业规划研究进展[J].农业机械学报，2022，53（S1）：1-19.
WANG N，HAN Y X，WANG Y X，et al.Research progress of agricultural robots full coverage operation planning[J].Transactions of the Chinese Society for Agricultural Machinery，2022，53（S1）：1-19.
[3] CHO S W，PARK J H，PARK H J，et al.Multi-UAV coverage path planning based on hexagonal grid decomposition in maritime search and rescue[J].Mathematics，2021，10（1）：83.
[4] SONG L，SUN H，XU K，et al.Path planning under the hull bottom of painting robot based on heuristic multi-robot cooperation in ship manufacturing[J].Manufacturing Technology，2022，22（2）：218-230.
[5] PARK S J，YEU T K，YOON S M，et al.A study of sweeping coverage path planning method for deep-sea manganese nodule mining robot[C]//OCEANS’11 MTS/IEEE KONA，2011：1-5.
[6] 许伦辉，林世城.基于分治思想的扫地机器人全覆盖路径规划算法研究[J].广西师范大学学报（自然科学版），2021，39（6）：54-62.
XU L H，LIN S C.Research on full coverage path planning algorithm of sweeping robot based on divide and conquer[J].Journal of Guangxi Normal University（Natural Science Edition），2021，39（6）：54-62.
[7] 周星.多机器人全覆盖问题的任务分配算法研究[D].长沙：国防科技大学，2019.
ZHOU X.Study of task assignment algorithm for multi-robot full coverage problem[D].Changsha：National University of Defense Technology，2019.
[8] 李珺，段钰蓉，郝丽艳，等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索，2022，16（7）：1623-1632.
LI J，DUAN Y R，HAO L Y，et al.Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1623-1632.
[9] 胡士娟，鲁海燕，黄洋，等.求解工作量平衡多旅行商问题的改进遗传算法[J].计算机工程与应用，2019，55（17）：150-155.
HU S J，LU H Y，HUANG Y，et al.Improved genetic algorithm for solving multiple traveling salesman problem with balanced workload[J].Computer Engineering and Applications，2019，55（17）：150-155.
[10] LI C，SONG Y，WANG F，et al.A bounded strategy of the mobile robot coverage path planning based on Lorenz chaotic system[J].International Journal of Advanced Robotic Systems，2016，13（3）：107.
[11] PARK J H，HUH U Y.Path planning for autonomous mobile robot based on safe space[J].Journal of Electrical Engineering and Technology，2016，11（5）：1441-1448.
[12] DRAKE D，KOZIOL S，CHABOT E.Mobile robot path planning with a moving goal[J].IEEE Access，2018，6：12800-12814.
[13] 张硕航，郭改枝.多旅行商模型及其应用研究综述[J].计算机科学与探索，2022，16（7）：1516-1528.
ZHANG S H，GUO G Z.Review of multiple traveling salesman model and its application[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1516-1528.
[14] TANG Y，ZHOU R，SUN G，et al.A novel cooperative path planning for multirobot persistent coverage in complex environments[J].IEEE Sensors Journal，2020，20（8）：4485-4495.
[15] GAO C，KOU Y，LI Z，et al.Optimal multirobot coverage path planning：ideal-shaped spanning tree[J].Mathematical Problems in Engineering，2018：3436429.
[16] NAIR V G，GURUPRASAD K R.GM-VPC：an algorithm for multi-robot coverage of known spaces using generalized Voronoi partition[J].Robotica，2020，38（5）：845-860.
[17] 阮贵航，陈教料，胥芳.基于滚动优化和分散捕食者猎物模型的全覆盖路径规划算法[J].控制与决策，2023，38（9）：2545-2553.
RUAN G H，CHEN J L，XU F.Complete coverage path planning algorithm based on rolling optimization and decentralized predator-prey model[J].Journal of Control and Decision，2023，38（9）：2545-2553.
[18] CHOSET H.Coverage of known spaces：the boustrophedon cellular decomposition[J].Autonomous Robots，2000，9（3）：247-253.
[19] TUNG W C，LIU J S.Solution of an integrated traveling salesman and coverage path planning problem by using a genetic algorithm with modified operators[J].IADIS International Journal of Computer Science and Information Systems，2019，14（2）：95-114.
[20] ZHU H R，TANG W，GAO C Z，et al.Self-powered metal surface anti-corrosion protection using energy harvested from rain drops and wind[J].Nano Energy，2015，14：193-200.