1、第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家自然科学基金面上资助项目（）；上海市自然科学基金资助项目（）；机械系统与振动国家重点实验室资助项目（）。：，（），（），（）面向大型三维结构检测的多机器人覆盖路径规划方法程晓明，刘银华，赵文政（上海理工大学 机械工程学院，上海 ）摘要：多机器人覆盖检测技术在汽车、航空航天部件等大型三维结构检测中的推广应用，为产品的全型面质量评价与工艺优化提供了依据。然而，受到大型结构件全覆盖视点采样、多机任务分配、路径规划等多重 问题求解的复杂性限制，多机器人覆盖路径规划的工程应用仍主要依赖经验，缺乏有效的理论依据。为此，针对大型三
2、维结构的覆盖检测问题，提出一种多机器人检测路径规划的新方法。首先，根据待测几何特征分布生成初始冗余视点集合，采用贪心算法实现全覆盖视点的优化采样；在此基础上，构建了面向多机器人视点任务分配与视点次序规划的集成优化模型，并通过将多机器人可达性、视点次序、距离矩阵等多源信息编码，提出基于改进遗传算法的覆盖路径规划问题的求解新方法。最后，通过白车身结构的仿真案例与对比分析，验证所提方法的有效性。结果表明，基于所提方法的工位内检测周期平均下降 ，多机检测一致性提升 。关键词：三维结构；质量检测；多机器人系统；覆盖路径规划中图分类号：文献标识码：，（，）：，：；第期程晓明 等：面向大型三维结构检测的多机
3、器人覆盖路径规划方法引言大型三维结构的质量检测是实现其制造精度评价、监控与质量诊断的基础。汽车车身、航空航天部件、高速列车车体等大型薄板、薄壁件具有外形尺寸大、曲面结构复杂、待测特征多且检测精度较高等特点。近年来，非接触光学检测精度与效率的提升使得大型三维结构的覆盖测量获得推广应用。因此，面向 质 量 检 测 的 覆 盖 路 径 规 划（，）研究也获得关注。覆盖路 径 规 划 主 要 包 括 集 合 覆 盖 问 题（，）与路径规划问题（，）两个子问题。传统研究中一般对上述问题进行独立求解，但受到视点采样与规划路径非最优等限制，学者们逐渐尝试将 与 同时解决，如卡内基梅隆大学 等创新性地提出 集
4、成模型以求解全局最优路径结果。然而，对于车身等大型三维结构来说，往往需要采用多机器人或冗余自由度机器人系统进行测量，这也引出了多机器人 问题，即 （）问题。多机覆盖路径规划过程一般包含视点的覆盖采样、多机任务分配以及单机路径规划等子问题。研究主要集中在二维场景下清洁与修剪、三维环境下模型重构、工业测量与远程救援等。其中多机器人任务分配问题为典型的混合整数线性规划问题，如 等 基于最小距离利用 对任务进行聚类，然后计算每个机器人与聚类群所组成集合的成本，最终根据拍卖算法进行任务分配。等 采用聚类算法将任务集划分和机器人相同的数量，然后利用线性分配法实现任务集分配。等 提出一种新的多任务多群优化算
5、法来解决多层任务分配问题。等 和 等 提出萤火虫算法、动态分布式例子全优化算法的全局分配和聚类算法实现多机任务分配。进一步，等 提出有偏随机密钥遗传算法（，）的多机三维模型重构的规划方法。等 利用基于机器人初始位置划分区域（，）算法将区域划分为多个等面积的子区域，从而将 问题转化为多个 问题，通过构造每个子区域的理想生成树获得优化覆盖路径。肖玉婷等 基于分块优化的思想，提出一种可应用于大规模复杂环境的多无人机覆盖路径规划方法，该方法兼顾了环境的差异性和覆盖的完整性。上述 主要通过无人机、无人地面车等寻找覆盖整个目标表面的无碰撞路径，多应用在模型重建和测绘监视等领域，而鲜有提出关于多工业机器人的
6、覆盖路径优化问题的解决办法。同时，与多无人机等覆盖路径规划问题不同，面向质量检测的多机器人覆盖规划问题受到机械臂运动学可达性、多机运行一致性以及光学入射角度等因素的特殊性要求，导致传统 方法的适用性不足，检测规划结果难以满足要求。因此，本文提出一种多机器人覆盖路径规划新方法，旨在构建检测任务分配与机器人路径规划问题的集成规划模型，并提出基于改进的自适应遗传算法对模型进行优化求解，获得大型产品结构全覆盖测量要求下机器人运动时间的近最优规划结果。进一步，通过整车的仿真案例与对比分析，验证所提方法的可行性及有效性。多机器人覆盖路径规划的优化模型构建大型三维结构产品的制造精度直接影响后续装配过程以及产
7、品使用性能。因此，必须对产品结构的尺寸、位置及表面质量进行质量检测，以评估其是否满足公差要求。针对大型结构的质量检测，需要对产品上布置的面点、圆孔、棱边点、槽孔以及螺纹孔等特征进行全覆盖测量。如图所示为搭载结构光测头的多机器人覆盖检测工位示意图。由图可知，光学测头被搭载在工业机器人末端，在机器人可达的视点位置对产品上待测特征进行覆盖测量。测头的可视性覆盖区域主要由视场（，）和 景 深（，）两个参数决定。多机器人覆盖路径规划的目计算机集成制造系统第 卷的是通过优化的视点采样、任务分配以及多机的路径规划以获得理想的覆盖测量规划结果。为实现检测特征的覆盖检测，需开展以下子问题进行求解：根据待测特征生
8、成冗余视点集；面向结构全覆盖的视点优化采样；全覆盖视点集的多机器人任务分配；各机器人任务集的检测次序与路径规划。传统方法往往针对上述子问题进行单独处理，虽然能够降低问题复杂度，但同时会使得可行解空间远小于真实情况，导致最终规划方案非优。而若将上述问题集成求解虽在理论上能够找到全局最优解，但往往导致高计算复杂度下的求解效率问题。本文综合考虑全局最优解和计算复杂度之间的协调关系，在全覆盖视点采样基础上，创新性地将多机任务分配与路径规划子问题进行集成建模并开展优化求解，以实现结构光检测路径的综合寻优。结合以上问题描述，多机器人任务分配模型可表达为：（，），（，）。（）（，）（，）（，）；（，）（，）
9、（，）；（，）（，）。（）其中各符号含义如下：为候选分配方案；（，）为候选方案中机器人访问的第个视点；为机器人代号；为单视点检测时间；为分配方案中机器人的视点数；为距离矩阵；为机器人末端平均移动速度；为机器人总数；（，）为方案中机器人任务集；为全覆盖视点集；为机器人可达信息；（，）为机器人可达视点集。多机器人任务分配与路径规划的综合寻优 全覆盖视点集采样本文首先基于随机采样生成初始视点集，根据视点的结构光参数计算可视性矩阵。进一步，基于可视性矩阵从初始冗余视点集中提取全覆盖子集，以保证每个待测特征至少被覆盖一次，称该子集为全覆盖视点集。构建的优化模型为：，。（）式中：表示初始视点集中的第个视点
10、，与分别表示该视点是否被采样；为的可视性矩阵；表示单个待测特征至少被覆盖一次。该问题为典型的集合覆盖问题，即在保证对三维结构待测特征全覆盖测量基础上使获得视点集数目 最 小 化。现 有 多 种 启 发 式 算 法 可 用 于 求 解 问题，本文采用贪心算法对全覆盖视点集进行求解，具体算法流程如算法所示。算法贪心算法求解全覆盖视点集。输入：待测特征集；冗余视点集；可视性矩阵；输出：全覆盖视点集 ；全覆盖视点集视点个数 。：；：（，）；：（，）；：（，）；：（，），：（，）；：（）；：，；算法中的相关函数及变量名解释如下：（）为选择当前冗余视点集中覆盖待测特征最多的视点，（）将所选择的视点添加到全
11、覆盖视点集中，（）为从冗余视点集中将选择过的视点删除，（）为计算当前待测特征被覆盖次数，（）为计算当前全覆盖视点集中的视点数，为单个视点，为单个待测特征。基于改进遗传算法的综合优化求解路径规划问题的求解主要有遗传算法、蚁群算法 等。直接采用上述算法无法使每一次迭代过程中产生的解方案均满足机器人可达性约束，因此，基于多机器人的视点分配与路径规划的集成模型，本文提出改进的遗传算法，以实现多机器人视点第期程晓明 等：面向大型三维结构检测的多机器人覆盖路径规划方法分配与运动路径的综合求解。传统遗传算法通过适应度函数反复筛选每一代种群较优解方案，直至迭代出满意解。由于存在结构全覆盖和机器人可达性约束，传
12、统遗传算法在迭代过程中往往产生过大量无效解，浪费了计算机算力，且易陷入死循环。因此，本文在遗传算法基础上，提出新的编码与种群初始化策略，并针对传统交叉变异算子易引起新解失效问题，提出新式变异算子使得初始解方案以及后续迭代过程中产生的每一种新解都能够同时满足全覆盖要求以及机器人可达性约束。此外，得益于提出的嵌入式优化策略，使得改进的遗传算法具有更快的收敛速度。为合理分配各机器人任务集以及路径顺序，需首先确定全覆盖视点集中各视点之间的距离，以及各机器人与视点之间的距离。本文将两部分距离计算结果合并建立统一的距离矩阵，其形式如图所示。其中：为全覆盖集视点中视点数目，为当前工位中机器人数目。距离矩阵分
13、为部分，分别记录了视点间距离（部分），视点与机器人间距离（、部分）以及机器人间距离（部分）。另外，将矩阵中机器人到视点间不可达位置用 来表示。（）编码与种群初始化相比于传统的染色体编码结构，本文构建了一个 的矩阵 来储存染色体，其中：为机器人数，为全覆盖视点集中视点数，该种编码形式具有易于区分各机器人任务集的好处，为后续算法迭代中处理可达性约束问题提供了便利，后文会详细论述该部分内容。所构建的矩阵中其行号表示机器人代号，每行非零元素表示该行指代机器人所分配的有序视点集。如矩阵中第行，表示机器人在当前方案中分配了个视点，且其访问顺序依次为、。需指出，由于各机器人分配视点数并非绝对一致，故用元素补
14、充至 以构成矩阵形式。具体的，矩阵结构如图所示。另外，对于种群初始化，本方法采取的策略为：优先将单机器人可达视点分配至各机器人；对于多机器人可达视点该如何分配，基于机器人检测过程中旅行成本和拍摄成本的协调关系，本方法提出两个策略：“就近原则”与“就少原则”。具体的，对于单个待分配视点，前者将该视点分配至距离其最近的机器人，而后者将该视点分配至当前任务集中视点数最少的机器人。首先，由两种策略确定两个可选机器人方案，分别计算两机器人与当前视点之间距离的差值以及各自当前任务集中视点数的差值，取视点数差值与路径差值之间的比值与选择系数（）比较，若比值大于，则采取“就少原则”；反之采取“就近原则”。若设
15、 ，意味着若视点数差值超过距离差值的十分之一，则采取“就少原则”；反之采取“就近原则”。其具体过程如算法所示。算法 。输入：当前分配方案 ；选择系数；机器人信息 ；机器人可达信息；输出：选择的机器人 。：（）；：（，）；：（，）；：（，）；：（，）；：（，）；：；：计算机集成制造系统第 卷：；：；算法中相关函数及变量名解释如下：（）为寻找可达当前视点的机器人集，（）为寻找可达机器人中当前分配视点数最少的，（）为寻找可达机器人中距离该视点最近的，（）为计算两机器人分配视点数差值，（）为计算两机器人与该视点距离差值，为可由多机器人覆盖检测的特征集，为单个待测特征。在所有视点都分配完成之后，将各机器
16、人的任务集中的试点顺序随机打乱，使初始种群更具随机性，以使得后续算法迭代过程中产生更多解。需补充的是，算法的思想除了用于种群初始化之外，还被应用于后续的交叉和变异算子中。（）种群适应度评价函数由于多机器人工位存在生产节拍的限制，要求多机器人检测系统在检测周期内完成检测任务，即要求耗费时间最长的机器人完成检测任务的时间不得超过。在检测过程中，花费时间的成本由机器人运行的时间成本和光学测头在视点处的拍摄成本两部分组成，本文构建的种群适应度评价函数可表达为。其中，表示给定分配方案下工位内检测总时间，即耗时最长机器人的运行时间成本与光学测头拍摄时间成本之和，（，），（，）。（）其中各项参数含义同式（）。越小则该个体的适应度越高，算法的目标即求解出最小的分配方案，并要求不大于给定的检测周期，即。基于上述分析，种群适应度求解策略为：首先，计算个体中各机器人检测时间，以耗时最长机器人的检测时间的倒数作为该个体的适应度，再比较种群所有个体适应度，将最高适应度作为当前种群适应度，并将该个体视为该种群的最优个体。（）选择、交叉、变异算子的设计选择算子采用轮盘赌选择法，其核心思想为个体被选中的概率与其适应度