计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (24): 319-327.DOI: 10.3778/j.issn.1002-8331.2208-0246

• 工程与应用 • 上一篇    下一篇

立面维护作业的多机器人全覆盖路径规划

谢必成,张小俊   

  1. 河北工业大学 机械工程学院,天津 300401
  • 出版日期:2023-12-15 发布日期:2023-12-15

Complete Coverage Path Planning for Multiple Robots for Facade Maintenance Operations

XIE Bicheng, ZHANG Xiaojun   

  1. School of Mechanical Engineering, Hebei University of Technology, Tianjin 300401, China
  • Online:2023-12-15 Published:2023-12-15

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

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

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