程晓明，刘银华，赵文政
(上海理工大学 机械工程学院，上海 200093)
大型三维结构的质量检测是实现其制造精度评价、监控与质量诊断的基础。汽车车身、航空航天部件、高速列车车体等大型薄板、薄壁件具有外形尺寸大、曲面结构复杂、待测特征多且检测精度较高等特点。近年来，非接触光学检测精度与效率的提升使得大型三维结构的覆盖测量获得推广应用。因此，面向质量检测的覆盖路径规划(Coverage Path Planning, CPP)研究也获得关注[1-3]。
覆盖路径规划主要包括集合覆盖问题(Set Covering Problem, SCP)与路径规划问题(Travelling Salesman Problem, TSP)两个子问题。传统研究中一般对上述问题进行独立求解[4]，但受到视点采样与规划路径非最优等限制，学者们逐渐尝试将SCP与TSP同时解决，如卡内基梅隆大学JING等[5]创新性地提出SCP-TSP集成模型以求解全局最优路径结果。
然而，对于车身等大型三维结构来说，往往需要采用多机器人或冗余自由度机器人系统进行测量，这也引出了多机器人CPP问题，即MCPP(multi-robots CPP)问题。多机覆盖路径规划过程一般包含视点的覆盖采样、多机任务分配以及单机路径规划等子问题。MCPP研究主要集中在二维场景下清洁与修剪、三维环境下模型重构、工业测量与远程救援等[6-9]。其中多机器人任务分配问题为典型的混合整数线性规划问题，如ELANGO等[10]基于最小距离利用K-means对任务进行聚类，然后计算每个机器人与聚类群所组成集合的成本，最终根据拍卖算法进行任务分配。JANATI等[11]采用聚类算法将任务集划分和机器人相同的数量，然后利用线性分配法实现任务集分配。SONG等[12]提出一种新的多任务多群优化算法来解决多层任务分配问题。ZITOUNI等[13]和AYARI等[14]提出萤火虫算法、动态分布式例子全优化算法的全局分配和聚类算法实现多机任务分配。进一步，JING等[15]提出有偏随机密钥遗传算法(Biased Random Key Genetic Algorithm, BRKGA)的多机三维模型重构的规划方法。
GAO等[16]利用基于机器人初始位置划分区域(Divide Areas based on Robots initials Positions, DARP)算法将区域划分为多个等面积的子区域，从而将MCPP问题转化为多个CPP问题，通过构造每个子区域的理想生成树获得优化覆盖路径。肖玉婷等[17]基于分块优化的思想，提出一种可应用于大规模复杂环境的多无人机覆盖路径规划方法，该方法兼顾了环境的差异性和覆盖的完整性。
上述MCPP主要通过无人机、无人地面车等寻找覆盖整个目标表面的无碰撞路径，多应用在模型重建和测绘监视等领域，而鲜有提出关于多工业机器人的覆盖路径优化问题的解决办法。同时，与多无人机等覆盖路径规划问题不同，面向质量检测的多机器人覆盖规划问题受到机械臂运动学可达性、多机运行一致性以及光学入射角度等因素的特殊性要求，导致传统MCPP方法的适用性不足，检测规划结果难以满足要求。
因此，本文提出一种多机器人覆盖路径规划新方法，旨在构建检测任务分配与机器人路径规划问题的集成规划模型，并提出基于改进的自适应遗传算法对模型进行优化求解，获得大型产品结构全覆盖测量要求下机器人运动时间的近最优规划结果。进一步，通过整车的仿真案例与对比分析，验证所提方法的可行性及有效性。
大型三维结构产品的制造精度直接影响后续装配过程以及产品使用性能。因此，必须对产品结构的尺寸、位置及表面质量进行质量检测，以评估其是否满足公差要求。针对大型结构的质量检测，需要对产品上布置的面点、圆孔、棱边点、槽孔以及螺纹孔等特征进行全覆盖测量。如图1所示为搭载结构光测头的多机器人覆盖检测工位示意图。
由图1可知，光学测头被搭载在工业机器人末端，在机器人可达的视点位置对产品上待测特征进行覆盖测量。测头的可视性覆盖区域主要由视场(Field of View, FOV)和景深(Field of Depth, FOD)两个参数决定。多机器人覆盖路径规划的目的是通过优化的视点采样、任务分配以及多机的路径规划以获得理想的覆盖测量规划结果。为实现检测特征的覆盖检测，需开展以下子问题进行求解：①根据待测特征生成冗余视点集；
②面向结构全覆盖的视点优化采样；
③全覆盖视点集的多机器人任务分配；
④各机器人任务集的检测次序与路径规划。
传统方法往往针对上述子问题进行单独处理，虽然能够降低问题复杂度，但同时会使得可行解空间远小于真实情况，导致最终规划方案非优。而若将上述问题集成求解虽在理论上能够找到全局最优解，但往往导致高计算复杂度下的求解效率问题。
本文综合考虑全局最优解和计算复杂度之间的协调关系，在全覆盖视点采样基础上[18]，创新性地将多机任务分配与路径规划子问题进行集成建模并开展优化求解，以实现结构光检测路径的综合寻优。结合以上问题描述，多机器人任务分配模型可表达为：
(1)
s.t.X(1,∶)∪X(2,∶)∪…∪X(nr,∶)=Vres；
X(1,∶)∩X(2,∶)∩…∩X(nr,∶)=∅；
X(k,i)∈nt(k,∶)。
(2)
其中各符号含义如下：
X为候选分配方案；
X(k,i)为候选方案X中机器人k访问的第i个视点；
k为机器人代号；
ω0为单视点检测时间；
nXk为分配方案X中机器人k的视点数；
G为距离矩阵；
Ve为机器人末端平均移动速度；
nr为机器人总数；
X(j,∶)为X方案中机器人j任务集；
Vres为全覆盖视点集；
nt为机器人可达信息；
nt(k,∶)为机器人k可达视点集。
2.1 全覆盖视点集采样
本文首先基于随机采样生成初始视点集V，根据视点的结构光参数计算可视性矩阵A。进一步，基于可视性矩阵从初始冗余视点集中提取全覆盖子集，以保证每个待测特征至少被覆盖一次，称该子集为全覆盖视点集。构建的优化模型为：
A·X≥1。
(3)
式中：xi表示初始视点集中的第i个视点，xi=1与xi=0分别表示该视点是否被采样；
A为n×n的可视性矩阵；
A·X≥1表示单个待测特征至少被覆盖一次。该问题为典型的集合覆盖问题，即在保证对三维结构待测特征全覆盖测量基础上使获得视点集数目最小化。现有多种启发式算法可用于求解SCP问题，本文采用贪心算法对全覆盖视点集进行求解，具体算法流程如算法1所示。
算法1贪心算法求解全覆盖视点集。
输入：待测特征集N；
冗余视点集V；
可视性矩阵A；
输出：全覆盖视点集Vres;全覆盖视点集视点个数nres。
1：
Vres←∅；
2：
while N≠∅ do
3：
v←maxCover(V,N,A)；
4：
Vres←append(Vres,v)；
5：
V←delete(V,v)；
6：
for each ni∈N do
7：
if count(ni,Vres,A)≥1,then
8：
N←delete(N,ni)；
9：
end if
10：
end for
11：
end while
12：nres=sizeof(Vres)；
13：
return nres,Vres；
算法1中的相关函数及变量名解释如下:maxCover()为选择当前冗余视点集中覆盖待测特征最多的视点，append()将所选择的视点添加到全覆盖视点集中，delete()为从冗余视点集中将选择过的视点删除，count()为计算当前待测特征被覆盖次数，sizeof()为计算当前全覆盖视点集中的视点数，v为单个视点，ni为单个待测特征。
2.2 基于改进遗传算法的综合优化求解
路径规划问题的求解主要有遗传算法[19]、蚁群算法[20]等。直接采用上述算法无法使每一次迭代过程中产生的解方案均满足机器人可达性约束，因此，基于多机器人的视点分配与路径规划的集成模型，本文提出改进的遗传算法，以实现多机器人视点分配与运动路径的综合求解。
传统遗传算法通过适应度函数反复筛选每一代种群较优解方案，直至迭代出满意解。由于存在结构全覆盖和机器人可达性约束，传统遗传算法在迭代过程中往往产生过大量无效解，浪费了计算机算力，且易陷入死循环。因此，本文在遗传算法基础上，提出新的编码与种群初始化策略，并针对传统交叉变异算子易引起新解失效问题，提出新式变异算子使得初始解方案以及后续迭代过程中产生的每一种新解都能够同时满足全覆盖要求以及机器人可达性约束。此外，得益于提出的嵌入式优化策略，使得改进的遗传算法具有更快的收敛速度。
为合理分配各机器人任务集以及路径顺序，需首先确定全覆盖视点集中各视点之间的距离，以及各机器人与视点之间的距离。本文将两部分距离计算结果合并建立统一的距离矩阵G，其形式如图2所示。其中：nres为全覆盖集视点中视点数目，nr为当前工位中机器人数目。距离矩阵分为4部分，分别记录了视点间距离(①部分)，视点与机器人间距离(②、③部分)以及机器人间距离(④部分)。另外，将矩阵中机器人到视点间不可达位置用inf来表示。
(1)编码与种群初始化
相比于传统的染色体编码结构，本文构建了一个nr×nres的矩阵ind来储存染色体，其中:nr为机器人数，nres为全覆盖视点集中视点数，该种编码形式具有易于区分各机器人任务集的好处，为后续算法迭代中处理可达性约束问题提供了便利，后文会详细论述该部分内容。所构建的矩阵中其行号表示机器人代号，每行非零元素表示该行指代机器人所分配的有序视点集。如矩阵中第2行[v14,v7,v5,v25,v63,v42,0…0]表示机器人2在当前方案中分配了5个视点，且其访问顺序依次为v14、v7、v5、v63、v42。需指出，由于各机器人分配视点数并非绝对一致，故用0元素补充至nres以构成矩阵形式。具体的，矩阵结构如图3所示。
另外，对于种群初始化，本方法采取的策略为：优先将单机器人可达视点分配至各机器人；
对于多机器人可达视点该如何分配，基于机器人检测过程中旅行成本和拍摄成本的协调关系，本方法提出两个策略：“就近原则”与“就少原则”。具体的，对于单个待分配视点，前者将该视点分配至距离其最近的机器人，而后者将该视点分配至当前任务集中视点数最少的机器人。
首先，由两种策略确定两个可选机器人方案，分别计算两机器人与当前视点之间距离的差值以及各自当前任务集中视点数的差值，取视点数差值与路径差值之间的比值与选择系数(PR)比较，若比值大于PR，则采取“就少原则”;反之采取“就近原则”。若设PR=0.1，意味着若视点数差值超过距离差值的十分之一，则采取“就少原则”；
反之采取“就近原则”。其具体过程如算法2所示。
算法2Rob_select。
输入：当前分配方案ind；
选择系数PR；
机器人信息Robs；
机器人可达信息Rt；
输出：选择的机器人Rob。
1：
Nmultirob←findMultirob(Rt)；
2：
for each niin Nmultirob
3：
Rob_to←findUpto(Rt,ni);
4：
Rob_Less←findLess(ind,Rob_to)；
5：
Rob_Near←findNear(Rob_to,Robs)；
6：
diff_VP←countVP(Rob_Less,Rob_Near,ind)；
7：
diff_Dist←countDist(Rob_Less,Rob_Near,ni)；
8：
if diff_VP∕diff_Dist>PR
9：
Rob=Rob_Less；
10：
else
11：
Rob=Rob_Near；
12：
end for
13：
return Rob；
算法2中相关函数及变量名解释如下：findUpto()为寻找可达当前视点的机器人集，findLess()为寻找可达机器人中当前分配视点数最少的，findNear()为寻找可达机器人中距离该视点最近的，countVP()为计算两机器人分配视点数差值，countDist()为计算两机器人与该视点距离差值，Nmultirob为可由多机器人覆盖检测的特征集，ni为单个待测特征。
在所有视点都分配完成之后，将各机器人的任务集中的试点顺序随机打乱，使初始种群更具随机性,以使得后续算法迭代过程中产生更多解。需补充的是，算法2的思想除了用于种群初始化之外，还被应用于后续的交叉和变异算子中。
(2)种群适应度评价函数
由于多机器人工位存在生产节拍的限制，要求多机器人检测系统在检测周期T内完成检测任务，即要求耗费时间最长的机器人完成检测任务的时间不得超过T。在检测过程中，花费时间的成本由机器人运行的时间成本和光学测头在视点处的拍摄成本两部分组成，本文构建的种群适应度评价函数可表达为1/Q。其中，Q表示给定分配方案下工位内检测总时间，即耗时最长机器人的运行时间成本与光学测头拍摄时间成本之和，
(4)
其中各项参数含义同式(1)。Q越小则该个体的适应度越高，算法的目标即求解出Q最小的分配方案，并要求Q不大于给定的检测周期，即Q≤T。
基于上述分析，种群适应度求解策略为：首先，计算个体中各机器人检测时间，以耗时最长机器人的检测时间的倒数作为该个体的适应度，再比较种群所有个体适应度，将最高适应度作为当前种群适应度，并将该个体视为该种群的最优个体。
(3)选择、交叉、变异算子的设计
选择算子采用轮盘赌选择法，其核心思想为个体被选中的概率与其适应度成正比。在该方法中，个体k被选中的概率为：
(5)
其中：Fk为个体k的适应度；
NUMPOP为种群中个体数。通过该算子使适应度较高的个体有较大的机会被选择，从而使得种群向好的方向进化。
在传统交叉算子过程中，会因父代与母代染色体(各机器人任务集)交叉而出现某些视点被重复分配或遗漏的情况。本文在传统交叉方案的基础上添加后处理措施，使得每次交叉结果能够满足可达性约束并使整体方案更加优化，具体策略如下：
步骤1对于交叉后染色体中重复出现的视点，选择将原属于母代中的该部分视点删除，其具体过程如算法3所示。算法3中:vi为单个视点，count()为计算当前染色体中视点vi个数，link()表示将两部分染色体连接。
算法3DeleteOverCover。
输入：交叉后的染色体child；
原父代染色体部分child_f；
原母代染色体部分child_m；
输出：更新后的染色体child。
1：
for each viin child
2：
if count(vi)>1
3：
child_m←delete(child_m,vi)；
4：
end if
5：
end for
6：
child_n←link(child_f,child_m)；
7：return child；
步骤2对于因交叉操作而丢失的视点，令其重新添加至染色体，从而保证全覆盖检测。首先，将当前视点分配至合理机器人任务集(算法2)。然后，为使该视点放入当前机器人有序任务集后所构成的新路径耗时最短，将比较当前视点位于所有可行位置后的新路径耗时，并选取耗时最短的位置作为放置点。具体过程如算法4所示。
算法4Add_ViewPoints。
输入：需添加的视点Vadd；
选定机器人Rob；
当前染色体child；
输出：更新后的子代染色体child。
1：for each viin Vadd
2：
Rout←Extract(child,Rob)；
3：
AllLocation←findLocation(Rout)；
4：
singtime←countTime(All Location,Rout,vi)；
5：
Location←chooseMin(Usingtime,AllLocation)；
6：
Rout←insert(Rout,Location,vi)；
7：
child←putBack(chile,Rout,Rob)；
8：
end for
9：
return child；
算法4中相关函数及变量名解释如下：Extract()为提取当前染色体中该机器人路径(机器人选择方法见算法2:Rob_select)，findLocation()为寻找当前路径所有可行插入位置，countTime()为计算视点位于当前插入位置整条路径耗时，chooseMin()为选择耗时最短的位置，insert()为将当前视点插入选择的路径位置，putBack()为将当前路径放回至原染色体相应位置，vi为单个视点。
至于变异算子，采取的策略为：在满足变异概率的情况下，从全覆盖视点集中随机选取一个视点vr，找到该视点位于当前染色体中的位置并删除，并利用算法2与算法4将该视点补充回染色体以得到变异后的染色体。由前文对算法2与算法4的介绍，可知变异产生的新解依然满足全覆盖要求以及可达性约束并且在一定程度上优化了变异前的方案。变异过程如图4所示。
基于上述算法设计，保证了产生所有解方案均满足可达性约束，实现了对全覆盖视点集的任务分配以及路径规划的综合优化求解，同时，得益于算法2与算法4在每一步迭代过程中的择优策略，使得本方法具有高速收敛性。
为验证本文方法的可行性，结合某车身大型曲面结构进行案例验证。该车身表面结构布置待测特征共计1 200余个，如图5所示，包括面点、圆孔、棱边点以及槽孔等，对应待测特征的位置及矢量方向在图中分别用红点与黑色箭头表示。在MATLAB软件机器人工具箱搭建4机器人视觉检测平台对提出的覆盖路径规划方法进行仿真验证，采用的机器人型号为FANUC 2000iB-125L，各机器人搭载光学测头的参数如表1所示。同时，鉴于未检索到多工业机器人覆盖路径规划的相关文献，故通过与卡内基梅隆大学JING等[15]提出的多无人机覆盖路径规划算法对比分析，结合视点分配数目、测量时间等指标对本文方法进行有效性验证。
表1 机器人搭载的光学测头参数
根据上述车身待测特征生成初始视点集[18],并基于贪心算法获得全覆盖条件下视点集Vres，包含82个视点。如图6所示为视点处光学测头的位姿示意图，其中红点表示视点位置，箭头表示视点处结构光入射方向。
采用本文提出改进的遗传算法对以上获取的全覆盖视点集进行多机器人任务分配及路径规划综合寻优求解，算法中涉及的参数如表2所示。
表2 算法参数
设选择系数PR=0.005，机器人末端平均移动速度Ve=600 mm/s。基于本文提出算法的规划结果如图7所示，其中R1～R4的视点分配数目分别为20，20，22，20，各机器人对应检测时间分别为27.20 s，27.19 s，27.01 s和25.69 s。如图8所示为对应分配方案下多机器人中最大运行时间随迭代次数的收敛情况。
进一步，为验证所提出方法的有效性，本文通过随机仿真实验对本文方法与文献[15]方法进行对比分析。对比指标包括工位内测量周期(max{ti})、视点采样数目极差值(Δt)、多机检测时间极差值(Δn)，如图9所示为两种方法连续60次的随机仿真规划结果对比。
通过对实验数据分析，得到两种方法在max{ti}、Δt以及Δn三个评价指标的平均值如图10所示。由图10可知，所提方法将检测工位内机器人最大运行时间平均下降31.56%，分配至各机器人视点数极差降低20%，各机器人运行时间极差值降低13.13%。可见，本文方法能够有效提升车身等大型结构的光学检测效率，也为其他大型三维结构的全覆盖检测规划提供了理论依据。
本文针对大型三维结构的覆盖检测问题，提出了一种新的多机器人结构光覆盖路径规划方法，包括全覆盖视点集提取、多机器人任务分配和路径规划的综合寻优等流程。首先，通过贪心算法获得全覆盖视点集，在待测特征全覆盖条件下最小化视点数目；
进一步，为解决多机任务分配与路径规划问题的综合寻优问题，提出了改进遗传算法实现机器人可达性约束下的高效运动规划与路径优化。最后，通过案例分析，验证了本文方法的可行性及有效性。
此外，本文是首次针对多机器人覆盖路径规划新问题开展研究，尚未考虑多机碰撞与避障等问题，未来将在本文集成的MCPP模型中考虑多机协同与避障问题，进一步提升所提方法的工程适用性。
猜你喜欢视点适应度染色体改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28多一条X染色体，寿命会更长科学之谜(2019年3期)2019-03-28为什么男性要有一条X染色体？科学之谜(2018年8期)2018-09-29一种基于改进适应度的多机器人协作策略郑州大学学报（工学版）(2018年2期)2018-04-13能忍的人寿命长恋爱婚姻家庭·养生版(2016年9期)2016-09-07基于空调导风板成型工艺的Kriging模型适应度研究中国塑料(2016年11期)2016-04-16视点河南电力(2016年5期)2016-02-06再论高等植物染色体杂交中央民族大学学报（自然科学版）(2015年2期)2015-06-09让你每天一元钱,物超所值——《今日视点—2014精萃》序新闻前哨(2015年2期)2015-03-11两会视点中国水利(2015年5期)2015-02-28本文来源：http://www.triumph-cn.com/fanwendaquan/gongwenfanwen/2023/0729/92644.html