第27卷第4期2021年4月
计算机集成制造系统
Computer Integrated Manufacturing Systems
Vol.27No.4
Apr.2021
DOI：10.13196/j.cims.2021.04.004
赵文政1，刘银华1+，金隼2
(1.上海理工大学机械工程学院，上海200093；
2.上海交通大学机械与动力工程学院，上海200240)
摘要：针对动态环境下多机器人任务分配过程高维运动规划计算量大、优化分析复杂与结果适用性不足
等问题，以多机器人检测工位为对象，提出面向多机器人协调运动规划的层级化任务分配方法，降低任务分配计算量、减少共享空间内多机干涉可能性。首先，针对多机器人共享任务集，提出一种基于惰性旅行商问题求解的粗分配方法，实现大量任务集到多机器人的分配。然后，采用模糊C-Means对单机器人任务集进行聚类；在此基础上，建立了面向任务子集聚类中心和单机运动时间等多目标的任务优化模型，实现测量任务到多车次、多机的细化分配。最后，通过某车型在线测量案例，从测量周期、多机一致性等方面对所提分配方法进行验证。结果表明，提出的层次化任务分配方法可实现在线测量下多任务的高效分配，同时能有效降低多机器人运动干涉概率。 关键词：车身；质量检测；多机器人；任务分配；路径规划
中图分类号:TP15文献标识码：A
基因敲除Hierarchical task assignment algorithm for multi-robot coordinated path planning
ZHAO Wenzheng1,LIUYinhua1+,JIN Sun2
(1.School of Mechanical Engineering,University of Shanghai for Science and Technology,
Shanghai200093,China；
2.School of Mechanical Engineering,Shanghai Jiao Tong University,Shanghai200240,China)
Abstract:Aiming at the optimization problems o£complex multi-robot task allocation,there are always high-dimensional motion planning calculations and insufficient applicability of planning results in a dynamic environment.Taking the multi-robot inspection station for an example,a hierarchical task allocation method was proposed for multirobot coordinated motion planning to reduce the possibility of interference in the multi-robot shared space.For the shared task set of multiple robots)a task allocation method based on the lazy traveling salesman problem solution was proposed to realize the allocation of a large number of task sets to multiple robots.Then fuzzy C-Means was used to cluster the single robot task set.On the basis of clustering,a multi-objective task allocation optimization model considering the center of the subset clustering and the motion time of the single robot was proposed to realize the task allocation to multiple robots in the sensing process of multiple products.Through an inline inspection case of an auto body,the task allocation method was verified in terms of inspection cycle and multi-robot consistency.
Results showed that the proposed method could realize efficient allocation of tasks for inline measurement,and could reduce the conflict probability of multi-robot effectively.
Keywords■auto body；quality inspection；multi-robotics；task allocation；path planning
收稿日期:2020-09-04；修订日期：2020-11-12°Received04Sep.2020；accepted12Nov.2020.
基金项目：国家自然科学基金资助项目(51875362)；机械系统与振动国家重点实验室资助项目(MSV202010)o Foundation items：Project supported by the National Natural Science Foundation,China(No.51875362),and the State Key Laboratory of Mechanical System and Vibration,China(No.MSV202010).
1000计算机集成制造系统第27卷
0引言
多机器人光学测量系统以其非接触、可在线等特点在汽车制造领域得到广泛推广，检测系统的路径规划研究也逐渐受到学者们的关注在实际应用中，多机器人光学检测系统的运动规划需要综合考虑任务分配、机器人路径规划和多机器人协调等问题於］，其中在线检测的任务分配是光学测量路径规划的重要环节，也是影响检测周期、多机器人冲突以及测量路径结果的重要因素凶。
多机器人任务分配问题是典型的混合整数线性规划问题(Mixed Integer Linear Programming, MILP)，需要对考虑机器人路径规划和机器人之间协调等条件下的多约束问题进行优化求解。典型的方法有基于MILP模型的求解策略研究"也，另外Spensieri等⑷通过建立的MILP模型，利用分支定界的方法实现焊点分配，并搜索得到最优解5Lopes 等⑹在MILP模型框架下，考虑机器人参数变换、分布限制、运动时间和机器人干扰约束等因素，对机器人焊接生产线进行任务分配。MILP求解可获得最优解，但其
计算资源占用量大，计算效率低，因此不适合大规模问题求解。为了提高求解效率，一些学者利用启发式算法进行任务分配，如遗传算法(genetic algorithm)、拍卖算法模型(auction algorithm)及博弈论(game theory)“闵等。进一步，J o nes 等［⑷提出双层拍卖方法解决路径约束的多机器人任务分配问题;Garapati等〔⑷通过比较博弈论算法到无人机之间的冲突平衡，并通过投票制度获得最终的分配结果;Zitouni等［旧首先采用萤火虫算法进行全局分配，然后结合量子遗传算法和人工蜂优化进行局部任务分配；杨煜俊等血」以最小化完工时间为优化目标，利用领域搜索策略和启发式规则相结合的混合遗传算法求解作业车间内多机器人制造单元调度问题；张则强等口“针对装配线平衡问题的具体特点，综合考虑装配作业时间和后续任务数的分级位置权重，通过改进蚁算法进行装配线平衡问题求解。
上述算法可实现多机在规定时间内的任务均衡分配。但随着任务数目增加，以上方法存在计算量指数增加的问题。为此，学者们提出对任务集进行聚类分析口
*旳，并对聚类后的簇进行多机分配以达到降低计算量。如早期研究中,Elango等⑶］首先基于K-means和最小距离对任务集进行聚类，然后计算每个机器人与聚类集所组成集合的成本，最终根据拍卖算法进行任务分配;Janati等利用K-means算法将任务划分为机器人的数量，利用线性分配将机器人分配给任务集。
从上述研究可以看出，已有任务分配方法主要适用于单层次任务分配问题，即任务到多机器人的分配。而在车身在线检测(生产节拍为60〜90s)过程中，需要将数百甚至上千个检测任务同时分配到多机器人、多批次车身，以实现有限检测周期内车身特征的全检，同时满足多机器人动态环境下的协调运动等需求。面对大量检测任务到多批次车身、多机器人的分配问题，当机器人数目、车次数目一定时，潜在的任务分配方案的数目与待分配任务数目之间呈指数关系，且每次候选分配方案均涉及机器人运动学与路径规划的优化求解。因此，本文提出层级化测量任务分配(Hierarchical Inspection Task Allocation,HITA)算法，通过瘠待测任务集的初步分配、模糊聚类以及面向多机协调的多目标优化的细化分配，实现检测任务的高效分配，降低算法复杂度(具体分析见2.2节)，提升在线检测效率。
1车身光学在线检测的任务分配问题
在汽车车身装配生产线中，光学在线检测(如图1)是实现车身质量100%测量的重要手段。考虑到车身大型曲面结构，需通过多台搭载光学传感器的机器人对车身特征(如孔、槽、曲面、边缘、螺纹等)进行非接触和在线测量。图2所示为多机器人光学在线检测过程，其中BlWCbody in white)表示白车身。由于在线生产节拍的限制，多机器人工位无法从单一车身上采集到所有关键特征的信息。这就要求将任务集分配给同一批次内连续m个车次进行检测，每台车身分配到的任务子集互不相交且各子集之和
图I坨9
多机器人光学在线检测丄位
第4期赵文政等：面向多机器人协调运动规划的层级化任务分配方法1001
图2多机器人光学在线检测过程示怠图
为任务全集。另一方面，针对确定的车次，需将检测任务分配给工位内不同机器人，并要求多机器人系统无干涉协调运动，且满足工位内检测周期、多机运行时间一致性等要求。
本文的目的是将检测任务分配到不同检测车次内的各机器人，使得每个机器人所分配的任务量的检测时间尽可能短且满足生产节拍限制等约束。结合上述问题描述，本文层次化任务分配过程进行如下假设：
(1)多层次任务分配时，待分配车次的数目为提前预设；
(2)各待测待征的光学最佳测量参数(如入射角、景深等)及公差已知；
(3)车身检测过程各机器人的起始测量时间相同；
(4)针对不同类型的待测特征，其光学检测时间相同，即机器人到达测量位置后的测量时间相同；
(5)机器人完成单车次任务检测后均返回其初始位置。
基于上述假设，本文的在线检测多任务分配模型可表达为：
min T{(R)={Rn,K乜，…，K*},&€K■>
(1) s.t.Ti<T。；(2)
△UVe;(3) Rn D R12Cl…n^mn-l n Rmn=0；(4)
Rn U Ri2U•••U U R湘=K。(5)其中各符号的含义如下；
死为检测工位内机器人总数；
m为批次内车次总数；
K&为第2个车次第，个机器人分配的任务集鼻={1,2,…，,j={l,2,…，兀}；
Ri为批次内第亍个车次下各个机器人候选任务集；
R为检测任务全集；
1；为第分车次的实际检测周期；
To为在线检测工位的生产节拍；
为第分个车次内雄个机器人中检测时间的极差；
丁妙为第
*个车次第j个机器人的检测时间；
€为最大的运行时间极差阈值。
淘书吧第d个车次第j个机器人在给定任务集下检测时间的计算公式可表示为：
T,?=(tol+如0+X如)。(6)
<另工曲=\，H q W—；
p
(7)
〉
2工冉=1»V/>€{1,2,—,m}o⑻其中：如、加)为分别表示从机器人运动路径中初始位置到首个待测特征和最终待测特征返回机器人初始位置的机器人运动时间；工丹为0,1变量；如为给定车次下某机器人从特征F"移动到特征Fq的运动时间；
2层次化检测任务分配
为了提高在线检测效率，本文采用层级化方法
对该分配问题进行启发式求解，具体流程为：首先基
于懒惰旅行商问题的求解策略，将检测共享空间内
1002计算机集成制造系统第27卷
的检测特征分配给不同机器人，实现检测任务全集到多机器人的初步分配。然后，针对上述机器人分配到的任务集，采用模糊C-Means(Fuzzy C-means, FCM)算法进行聚类分析，获得与检测工位机器人数目相同的任务簇。最后，提出考虑任务簇中心和单机运动时间等多目标的任务分配优化模型，实现测量任务到具体车次、机器人的细化分配。
2.1检测任务到机器人系统的粗分配
通常，搭载光学测头的六轴机器人左右对称分布于在线检测工位，车身尺寸特征通常会落在一个或多个机器人可达范围内。当检测特征落在多机器人共享空间内时，需将其分配给某个确定的机器人O 传统基于距离的分配方法将导致每个车次下多机器人检测时间的极差增大，从而导致检测效率不高。因此，为了保证每个车次机器人工作时间的一致性，本文在设置每个机器人所分配检测特征数目约束的条件下，利用懒惰旅行商问题(lazy Traveling Salesman Problem,lazy TSP)的求解策略，将共享空间内的检测特征粗分配到每个机器人。具体共享空间内检测任务的分配策略如下：
(1)根据机器人可达性计算得到多个机器人共享空间内的检测特征集合，如第j个和第J+1个机器人共享空间内检测特征集合为Uj,j+1。以U“+i 内的特征为例，说明提出算法的分配过程。
(2)根据检测特征的总数目以及机器人的数目，设置单机器人最大检测特征数目的阈值为卩。
(3)对于U…j+1内的特征F p，记F p和第j、j+1个机器人已分配任务集合的并集分别为和R'屮，设R八心+】集合内元素数目分别为a』。
(4)在不考虑机器人碰撞的前提下，求解从第j J+1个机器人初始位置S,、S,+i出发，遍历码、R r i+i内特征点并回到初始位置的最小距离Lj、Lj+1。
(5)若同时满足JVLj+i和或者同时满足—和6>卩，则将F p分配给第j个机器人；若同时满足Lj<L j+1和a>°，或者同时满足Lj>乙+i和b<<p，则将F”分配给第j+1个机器人。
(6)重复步骤(3)〜步骤(5)直到内的特征分配完成。
基于上述分配算法，即可得到每个机器人分配的特征任务集衣，…,R”。具体分配过程的伪代码如下：
imax=sizeof(Uj,j+i);%imax表示U"+i内集合的数目；
for i=1:imax
R'j+i=[U"+i(i),Ri+i：|；
石家庄化肥厂a=sizeof(R'»;%a表示R'j内测点的数目；
解放台湾b=sizeof(R'j+Q；%b表示R'j+i内测点的数目；
%计算从第j个机器人初始位置Sj出发遍历R'j内特征点回到S的最短距离L“
L；=min(D s i+D,,s+S xki,k2Dki,k2)；
」J kl€a,k2€a
%计算从第j+1机器人初始位置s汁1出发遍历R'j+1内特征点回到Sj十1的最短距离Lj十-
L i+1=min(D Sj+1」+U,Sj+1+空离旦级3叫"
if LjVLj+i&a<；甲||Lj>Lj+i&b>®
Rj=R'j；
elseif LjVLj+i&a><p||Lj>Lj+i&bV<p
Rj+iuR'j+i；
end
开放info共享平台end
2.2针对不同车次下多机器人的细化分配
对检测任务粗分配后，需进一步将其细分给批次内不同车次下的多个检测机器人。传统将路径距离或检测时间作为目标函数的MILP模型的任务分配方法，往往忽略多机器人分配任务集之间的关系，导致多机协调阶段机器人发生冲突甚至停机的现象，从而降低了检测效率。为解决该问题，本文基于聚类算法将第j个机器人的粗分任务集划分成观类。然后，根据式(6)计算机器人无碰检测路径的最短时间。进一步，考虑批次内多车次下机器人的检测时间一致性，以及多车次下相邻机器人任务集的聚类中心间距离，构建任务细化分配的多目标优化模型，并利用改进的模拟退火(Simulated Annealing,SA)算法进行求解，获得不同车次内多机器人的任务分配结果。
传统K-means聚类是一种将每个任务对象非此即彼地严格分类的聚类算法。然而，在多机器人检测工位中，对于检测任务集内的部分测量任务可以由多个车次内多个机器人检测，即并非严格的“0-1”关系，若利用K-means进行聚类，将很难得到较为明显的簇，且由于车身检测特征分布差异较大，致使各个簇内元素较为分散，优化分配后会增加各车次内的机器人运行时间增加，降低检测效率。FCM 算法作为一种无监督聚类算法，利用模糊理论对重要数据进行分析和建模，使得被划分到同一簇的任务之间相似度较大，而不同簇之间的相似度较小。因此,FCM能通过优化每个检测任务的隶属度获得较为明显的聚类效果，使得簇内元素分布较为集中，
第4期赵文政等：面向多机器人协调运动规划的层级化任务分配方法1003
从而为后续分配优化提供基础。
综上所述，本文基于FCM算法对任务集便进
行聚类，具体过程为：设第；个机器人的任务集为
K，={F］,F2,…,F"，其中N为衣内测点数量,F
为R，内的测点；通过迭代的方法将任务集R分解
为个子集Cij Q=l,2，♦“=1,2,•••,n)，并根
据隶属度计算每个子集聚类中心吗(2=1,2,…，
m)0因此，基于FCM算法求解，可将2.1节中每个
机器人分配到的检测任务集R分解成nXm个
子集。
在上述任务集聚类基础上，为了缩短机器人之
间的运行时间差，同时减少机器人之间发生冲突的
概率，本文以SA算法对不同车次、多机器人检测任
务进行优化分配，算法流程如图3所示。
初始化任务分配方案炉
曹仁伟
构建多「I标函数尸(們
1$机运行时间差2-聚类屮心间趾离
随机扰动下新方案1厂产生
计算
接受新解炉'F(們一F(fT)
按Metropolis 准则接受新解
最优任务分配方案护
*
圈3不同车次间检测任务分配篦法流程
具体算法流程如下：
(1)将任务子集Q进行编码，并随机分配给不同车次，如第1个机器人检测任务子集c n,C21,-, C”i分别分配到每个车次，其编码为1基于此，可得到SA算法的初始分配解W=「12-11
:::Vn.W中每一列即每个车次内第1〜«个机器人所分配的检测任务集。
(2)基于上述计算得到的每个车次内机器人检测时间兀及产生的新解W，计算各车次内检测时间的极差值△4。其中单车次下机器人检测时间的计算方法如下：针对给定的机器人检测任务，本文采用几何避障算法对机器人初步分配得到的测点集Q内的两两检测特征的局部无碰撞路径进行优化，建立两两检测测点之间的无碰撞运动时间矩阵皿-24］。同时，为了保证单机器人检测时间最优，将问题转换为寻时间最短的无碰撞路径的TSP O 对于TSP，可通过SA、GA以及分支定界等算法进行求解，最终得到每个机器人对不同测点集Q的检测时间巧。
(3)以g和相邻两机器人(若两机器人之间存在检测共享空间，即为两机器人相邻)所分配的任务集Q的聚类中心巾之间距离建立SA算法的加权多目标函数：
m m n n
F=a)i△T；+c«2UII(吗—吗')II2)。
i=l£=1;=1j'=j+l
(9)式中：吗，s为权重系数；⑷为第i个车次检测过程中第j个机器人测量任务集的聚类中心；心为0-1变量，心=1时，表示第j个机器人和第/个机器人为相邻的两机器人，心=0时，表示第j个机器人和第『个机器人为不相邻的两机器人。当越小而II印一讥II越大时，车次内多机器人协调运行敷果越好，因此设阴为正数，©为负数。此外，由于变量的量纲不同需对数据进行归一化处理。
(4)通过不同行内元素相互交换产生新解W f (如图4)，计算AF=F(W z)-F(W)0
12|…卜T|wr
第I组第［组
.—
—，新解产％
12ffi~l
笫"组第"组
2■•••1w
图4SA算法中新解的产生
(5)计算AF，并判断其是否小于零，若AFV0，则接受W'为新的当前解；若△/>()，则以一定概率接受为新解。
(6)判断W'是否满足迭代终止条件，满足则输出多车次、多机器人任务分配结果；否则，添加扰动产生新解，并返回步骤(2)。
基于上述改进SA算法对聚类后的测点集进行多目标优化，即可求解得到不同车次内满足节拍周
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议