面向多機(jī)器人協(xié)調(diào)運(yùn)動(dòng)規(guī)劃的層級(jí)化任務(wù)分配方法

趙文政，劉銀華+，金 隼

(1.上海理工大學(xué) 機(jī)械工程學(xué)院，上海 200093；2.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240)

0 引言

多機(jī)器人光學(xué)測(cè)量系統(tǒng)以其非接觸、可在線等特點(diǎn)在汽車制造領(lǐng)域得到廣泛推廣，檢測(cè)系統(tǒng)的路徑規(guī)劃研究也逐漸受到學(xué)者們的關(guān)注[1]。在實(shí)際應(yīng)用中，多機(jī)器人光學(xué)檢測(cè)系統(tǒng)的運(yùn)動(dòng)規(guī)劃需要綜合考慮任務(wù)分配、機(jī)器人路徑規(guī)劃和多機(jī)器人協(xié)調(diào)等問題[2-4]，其中在線檢測(cè)的任務(wù)分配是光學(xué)測(cè)量路徑規(guī)劃的重要環(huán)節(jié)，也是影響檢測(cè)周期、多機(jī)器人沖突以及測(cè)量路徑結(jié)果的重要因素[5]。

多機(jī)器人任務(wù)分配問題是典型的混合整數(shù)線性規(guī)劃問題(Mixed Integer Linear Programming, MILP)，需要對(duì)考慮機(jī)器人路徑規(guī)劃和機(jī)器人之間協(xié)調(diào)等條件下的多約束問題進(jìn)行優(yōu)化求解。典型的方法有基于MILP模型的求解策略研究[6-7]，另外Spensieri等[8]通過建立的MILP模型，利用分支定界的方法實(shí)現(xiàn)焊點(diǎn)分配，并搜索得到最優(yōu)解;Lopes等[9]在MILP模型框架下，考慮機(jī)器人參數(shù)變換、分布限制、運(yùn)動(dòng)時(shí)間和機(jī)器人干擾約束等因素，對(duì)機(jī)器人焊接生產(chǎn)線進(jìn)行任務(wù)分配。MILP求解可獲得最優(yōu)解，但其計(jì)算資源占用量大，計(jì)算效率低，因此不適合大規(guī)模問題求解。為了提高求解效率，一些學(xué)者利用啟發(fā)式算法進(jìn)行任務(wù)分配，如遺傳算法(genetic algorithm)、拍賣算法模型(auction algorithm)及博弈論(game theory)[10-12]等。進(jìn)一步，Jones等[13]提出雙層拍賣方法解決路徑約束的多機(jī)器人任務(wù)分配問題；Garapati等[14]通過比較博弈論算法找到無人機(jī)之間的沖突平衡，并通過投票制度獲得最終的分配結(jié)果;Zitouni等[15]首先采用螢火蟲算法進(jìn)行全局分配，然后結(jié)合量子遺傳算法和人工蜂群優(yōu)化進(jìn)行局部任務(wù)分配;楊煜俊等[16]以最小化完工時(shí)間為優(yōu)化目標(biāo)，利用領(lǐng)域搜索策略和啟發(fā)式規(guī)則相結(jié)合的混合遺傳算法求解作業(yè)車間內(nèi)多機(jī)器人制造單元調(diào)度問題;張則強(qiáng)等[17]針對(duì)裝配線平衡問題的具體特點(diǎn)，綜合考慮裝配作業(yè)時(shí)間和后續(xù)任務(wù)數(shù)的分級(jí)位置權(quán)重，通過改進(jìn)蟻群算法進(jìn)行裝配線平衡問題求解。

上述算法可實(shí)現(xiàn)多機(jī)在規(guī)定時(shí)間內(nèi)的任務(wù)均衡分配。但隨著任務(wù)數(shù)目增加，以上方法存在計(jì)算量指數(shù)增加的問題。為此，學(xué)者們提出對(duì)任務(wù)集進(jìn)行聚類分析[18-20]，并對(duì)聚類后的簇進(jìn)行多機(jī)分配以達(dá)到降低計(jì)算量。如早期研究中，Elango等[21]首先基于K-means和最小距離對(duì)任務(wù)集進(jìn)行聚類，然后計(jì)算每個(gè)機(jī)器人與聚類集群所組成集合的成本，最終根據(jù)拍賣算法進(jìn)行任務(wù)分配;Janati等[22]利用K-means算法將任務(wù)劃分為機(jī)器人的數(shù)量，利用線性分配將機(jī)器人分配給任務(wù)集。

從上述研究可以看出，已有任務(wù)分配方法主要適用于單層次任務(wù)分配問題，即任務(wù)到多機(jī)器人的分配。而在車身在線檢測(cè)(生產(chǎn)節(jié)拍為60～90 s)過程中，需要將數(shù)百甚至上千個(gè)檢測(cè)任務(wù)同時(shí)分配到多機(jī)器人、多批次車身，以實(shí)現(xiàn)有限檢測(cè)周期內(nèi)車身特征的全檢，同時(shí)滿足多機(jī)器人動(dòng)態(tài)環(huán)境下的協(xié)調(diào)運(yùn)動(dòng)等需求。面對(duì)大量檢測(cè)任務(wù)到多批次車身、多機(jī)器人的分配問題，當(dāng)機(jī)器人數(shù)目、車次數(shù)目一定時(shí)，潛在的任務(wù)分配方案的數(shù)目與待分配任務(wù)數(shù)目之間呈指數(shù)關(guān)系，且每次候選分配方案均涉及機(jī)器人運(yùn)動(dòng)學(xué)與路徑規(guī)劃的優(yōu)化求解。因此，本文提出層級(jí)化測(cè)量任務(wù)分配(Hierarchical Inspection Task Allocation, HITA)算法，通過將待測(cè)任務(wù)集的初步分配、模糊聚類以及面向多機(jī)協(xié)調(diào)的多目標(biāo)優(yōu)化的細(xì)化分配，實(shí)現(xiàn)檢測(cè)任務(wù)的高效分配，降低算法復(fù)雜度(具體分析見2.2節(jié))，提升在線檢測(cè)效率。

1 車身光學(xué)在線檢測(cè)的任務(wù)分配問題

在汽車車身裝配生產(chǎn)線中，光學(xué)在線檢測(cè)(如圖1)是實(shí)現(xiàn)車身質(zhì)量100%測(cè)量的重要手段?？紤]到車身大型曲面結(jié)構(gòu)，需通過多臺(tái)搭載光學(xué)傳感器的機(jī)器人對(duì)車身特征(如孔、槽、曲面、邊緣、螺紋等)進(jìn)行非接觸和在線測(cè)量。圖2所示為多機(jī)器人光學(xué)在線檢測(cè)過程，其中BIW(body in white)表示白車身。由于在線生產(chǎn)節(jié)拍的限制，多機(jī)器人工位無法從單一車身上采集到所有關(guān)鍵特征的信息。這就要求將任務(wù)集分配給同一批次內(nèi)連續(xù)m個(gè)車次進(jìn)行檢測(cè)，每臺(tái)車身分配到的任務(wù)子集互不相交且各子集之和為任務(wù)全集。另一方面，針對(duì)確定的車次，需將檢測(cè)任務(wù)分配給工位內(nèi)不同機(jī)器人，并要求多機(jī)器人系統(tǒng)無干涉協(xié)調(diào)運(yùn)動(dòng)，且滿足工位內(nèi)檢測(cè)周期、多機(jī)運(yùn)行時(shí)間一致性等要求。

本文的目的是將檢測(cè)任務(wù)分配到不同檢測(cè)車次內(nèi)的各機(jī)器人，使得每個(gè)機(jī)器人所分配的任務(wù)量的檢測(cè)時(shí)間盡可能短且滿足生產(chǎn)節(jié)拍限制等約束。結(jié)合上述問題描述，本文層次化任務(wù)分配過程進(jìn)行如下假設(shè)：

(1)多層次任務(wù)分配時(shí)，待分配車次的數(shù)目為提前預(yù)設(shè)；

(2)各待測(cè)特征的光學(xué)最佳測(cè)量參數(shù)(如入射角、景深等)及公差已知；

(3)車身檢測(cè)過程各機(jī)器人的起始測(cè)量時(shí)間相同；

(4)針對(duì)不同類型的待測(cè)特征，其光學(xué)檢測(cè)時(shí)間相同，即機(jī)器人到達(dá)測(cè)量位置后的測(cè)量時(shí)間相同；

(5)機(jī)器人完成單車次任務(wù)檢測(cè)后均返回其初始位置。

基于上述假設(shè)，本文的在線檢測(cè)多任務(wù)分配模型可表達(dá)為：

minTi(Ri),Ri={Ri1,Ri2,…,Rin},Ri∈R。

(1)

s.t.

Ti

(2)

ΔTi<ε;

(3)

R11∩R12∩…∩Rmn-1∩Rmn=?;

(4)

R11∪R12∪…∪Rmn-1∪Rmn=R。

(5)

其中各符號(hào)的含義如下：

n為檢測(cè)工位內(nèi)機(jī)器人總數(shù)；

m為批次內(nèi)車次總數(shù)；

Rij為第i個(gè)車次第j個(gè)機(jī)器人分配的任務(wù)集，i={1,2,…,m},j={1,2,…,n}；

Ri為批次內(nèi)第i個(gè)車次下各個(gè)機(jī)器人候選任務(wù)集;

R為檢測(cè)任務(wù)全集；

Ti為第i車次的實(shí)際檢測(cè)周期；

T0為在線檢測(cè)工位的生產(chǎn)節(jié)拍；

ΔTi為第i個(gè)車次內(nèi)n個(gè)機(jī)器人中檢測(cè)時(shí)間的極差；

Tij為第i個(gè)車次第j個(gè)機(jī)器人的檢測(cè)時(shí)間；

ε為最大的運(yùn)行時(shí)間極差閾值。

第i個(gè)車次第j個(gè)機(jī)器人在給定任務(wù)集下檢測(cè)時(shí)間的計(jì)算公式可表示為：

(6)

(7)

(8)

其中：t01、tM0為分別表示從機(jī)器人運(yùn)動(dòng)路徑中初始位置到首個(gè)待測(cè)特征和最終待測(cè)特征返回機(jī)器人初始位置的機(jī)器人運(yùn)動(dòng)時(shí)間；xpq為0，1變量；tpq為給定車次下某機(jī)器人從特征Fp移動(dòng)到特征Fq的運(yùn)動(dòng)時(shí)間；

2 層次化檢測(cè)任務(wù)分配

為了提高在線檢測(cè)效率，本文采用層級(jí)化方法對(duì)該分配問題進(jìn)行啟發(fā)式求解，具體流程為：首先基于懶惰旅行商問題的求解策略，將檢測(cè)共享空間內(nèi)的檢測(cè)特征分配給不同機(jī)器人，實(shí)現(xiàn)檢測(cè)任務(wù)全集到多機(jī)器人的初步分配。然后，針對(duì)上述機(jī)器人分配到的任務(wù)集，采用模糊C-Means(Fuzzy C-means, FCM)算法進(jìn)行聚類分析，獲得與檢測(cè)工位機(jī)器人數(shù)目相同的任務(wù)簇。最后，提出考慮任務(wù)簇中心和單機(jī)運(yùn)動(dòng)時(shí)間等多目標(biāo)的任務(wù)分配優(yōu)化模型，實(shí)現(xiàn)測(cè)量任務(wù)到具體車次、機(jī)器人的細(xì)化分配。

2.1 檢測(cè)任務(wù)到機(jī)器人系統(tǒng)的粗分配

通常，搭載光學(xué)測(cè)頭的六軸機(jī)器人左右對(duì)稱分布于在線檢測(cè)工位，車身尺寸特征通常會(huì)落在一個(gè)或多個(gè)機(jī)器人可達(dá)范圍內(nèi)。當(dāng)檢測(cè)特征落在多機(jī)器人共享空間內(nèi)時(shí)，需將其分配給某個(gè)確定的機(jī)器人。傳統(tǒng)基于距離的分配方法將導(dǎo)致每個(gè)車次下多機(jī)器人檢測(cè)時(shí)間的極差增大，從而導(dǎo)致檢測(cè)效率不高。因此，為了保證每個(gè)車次機(jī)器人工作時(shí)間的一致性，本文在設(shè)置每個(gè)機(jī)器人所分配檢測(cè)特征數(shù)目約束的條件下，利用懶惰旅行商問題(lazy Traveling Salesman Problem, lazy TSP)的求解策略，將共享空間內(nèi)的檢測(cè)特征粗分配到每個(gè)機(jī)器人。具體共享空間內(nèi)檢測(cè)任務(wù)的分配策略如下：

(1)根據(jù)機(jī)器人可達(dá)性計(jì)算得到多個(gè)機(jī)器人共享空間內(nèi)的檢測(cè)特征集合，如第j個(gè)和第j+1個(gè)機(jī)器人共享空間內(nèi)檢測(cè)特征集合為Uj,j+1。以Uj,j+1內(nèi)的特征為例，說明提出算法的分配過程。

(2)根據(jù)檢測(cè)特征的總數(shù)目以及機(jī)器人的數(shù)目，設(shè)置單機(jī)器人最大檢測(cè)特征數(shù)目的閾值為φ。

(5)若同時(shí)滿足LjLj+1和b>φ，則將Fp分配給第j個(gè)機(jī)器人；若同時(shí)滿足Ljφ，或者同時(shí)滿足Lj>Lj+1和b<φ，則將Fp分配給第j+1個(gè)機(jī)器人。

(6)重復(fù)步驟(3)～步驟(5)直到Uj,j+1內(nèi)的特征分配完成。

基于上述分配算法，即可得到每個(gè)機(jī)器人分配的特征任務(wù)集R1,R2,…,Rn。具體分配過程的偽代碼如下：

imax=sizeof(Uj,j+1);%imax表示Uj,j+1內(nèi)集合的數(shù)目；

for i=1:imax

if LjLj+1& b>φ

elseif Ljφ‖Lj>Lj+1& b<φ

end

end

2.2 針對(duì)不同車次下多機(jī)器人的細(xì)化分配

對(duì)檢測(cè)任務(wù)粗分配后，需進(jìn)一步將其細(xì)分給批次內(nèi)不同車次下的多個(gè)檢測(cè)機(jī)器人。傳統(tǒng)將路徑距離或檢測(cè)時(shí)間作為目標(biāo)函數(shù)的MILP模型的任務(wù)分配方法，往往忽略多機(jī)器人分配任務(wù)集之間的關(guān)系，導(dǎo)致多機(jī)協(xié)調(diào)階段機(jī)器人發(fā)生沖突甚至停機(jī)的現(xiàn)象，從而降低了檢測(cè)效率。為解決該問題，本文基于聚類算法將第j個(gè)機(jī)器人的粗分任務(wù)集Rj劃分成m類。然后，根據(jù)式(6)計(jì)算機(jī)器人無碰檢測(cè)路徑的最短時(shí)間。進(jìn)一步，考慮批次內(nèi)多車次下機(jī)器人的檢測(cè)時(shí)間一致性，以及多車次下相鄰機(jī)器人任務(wù)集的聚類中心間距離，構(gòu)建任務(wù)細(xì)化分配的多目標(biāo)優(yōu)化模型，并利用改進(jìn)的模擬退火(Simulated Annealing, SA)算法進(jìn)行求解，獲得不同車次內(nèi)多機(jī)器人的任務(wù)分配結(jié)果。

傳統(tǒng)K-means聚類是一種將每個(gè)任務(wù)對(duì)象非此即彼地嚴(yán)格分類的聚類算法。然而，在多機(jī)器人檢測(cè)工位中，對(duì)于檢測(cè)任務(wù)集內(nèi)的部分測(cè)量任務(wù)可以由多個(gè)車次內(nèi)多個(gè)機(jī)器人檢測(cè)，即并非嚴(yán)格的“0-1”關(guān)系，若利用K-means進(jìn)行聚類，將很難得到較為明顯的簇，且由于車身檢測(cè)特征分布差異較大，致使各個(gè)簇內(nèi)元素較為分散，優(yōu)化分配后會(huì)增加各車次內(nèi)的機(jī)器人運(yùn)行時(shí)間增加，降低檢測(cè)效率。FCM算法作為一種無監(jiān)督聚類算法，利用模糊理論對(duì)重要數(shù)據(jù)進(jìn)行分析和建模，使得被劃分到同一簇的任務(wù)之間相似度較大，而不同簇之間的相似度較小。因此，F(xiàn)CM能通過優(yōu)化每個(gè)檢測(cè)任務(wù)的隸屬度獲得較為明顯的聚類效果，使得簇內(nèi)元素分布較為集中，從而為后續(xù)分配優(yōu)化提供基礎(chǔ)。

綜上所述，本文基于FCM算法對(duì)任務(wù)集Rj進(jìn)行聚類，具體過程為：設(shè)第j個(gè)機(jī)器人的任務(wù)集為Rj={F1,F2,…,FN}，其中N為Rj內(nèi)測(cè)點(diǎn)數(shù)量，F(xiàn)為Rj內(nèi)的測(cè)點(diǎn)；通過迭代的方法將任務(wù)集Rj分解為m個(gè)子集Cij(i=1,2,…,m,j=1,2,…,n)，并根據(jù)隸屬度計(jì)算每個(gè)子集聚類中心vij(i=1,2,…,m)。因此，基于FCM算法求解，可將2.1節(jié)中每個(gè)機(jī)器人分配到的檢測(cè)任務(wù)集Rj分解成n×m個(gè)子集。

在上述任務(wù)集聚類基礎(chǔ)上，為了縮短機(jī)器人之間的運(yùn)行時(shí)間差，同時(shí)減少機(jī)器人之間發(fā)生沖突的概率，本文以SA算法對(duì)不同車次、多機(jī)器人檢測(cè)任務(wù)進(jìn)行優(yōu)化分配，算法流程如圖3所示。

具體算法流程如下：

(2)基于上述計(jì)算得到的每個(gè)車次內(nèi)機(jī)器人檢測(cè)時(shí)間Tij及產(chǎn)生的新解W，計(jì)算各車次內(nèi)檢測(cè)時(shí)間的極差值ΔTi。其中單車次下機(jī)器人檢測(cè)時(shí)間的計(jì)算方法如下：針對(duì)給定的機(jī)器人檢測(cè)任務(wù)，本文采用幾何避障算法對(duì)機(jī)器人初步分配得到的測(cè)點(diǎn)集Cij內(nèi)的兩兩檢測(cè)特征的局部無碰撞路徑進(jìn)行優(yōu)化，建立兩兩檢測(cè)測(cè)點(diǎn)之間的無碰撞運(yùn)動(dòng)時(shí)間矩陣[23-24]。同時(shí)，為了保證單機(jī)器人檢測(cè)時(shí)間最優(yōu)，將問題轉(zhuǎn)換為尋找時(shí)間最短的無碰撞路徑的TSP。對(duì)于TSP，可通過SA、GA以及分支定界等算法進(jìn)行求解，最終得到每個(gè)機(jī)器人對(duì)不同測(cè)點(diǎn)集Cij的檢測(cè)時(shí)間Tij。

(3)以ΔTi和相鄰兩機(jī)器人(若兩機(jī)器人之間存在檢測(cè)共享空間，即為兩機(jī)器人相鄰)所分配的任務(wù)集Cij的聚類中心vij之間距離建立SA算法的加權(quán)多目標(biāo)函數(shù)：

(9)

(4)通過不同行內(nèi)元素相互交換產(chǎn)生新解W′(如圖4)，計(jì)算ΔF=F(W′)-F(W)。

(5)計(jì)算ΔF，并判斷其是否小于零，若ΔF<0，則接受W′為新的當(dāng)前解;若ΔF>0，則以一定概率接受為新解。

(6)判斷W′是否滿足迭代終止條件，滿足則輸出多車次、多機(jī)器人任務(wù)分配結(jié)果；否則，添加擾動(dòng)產(chǎn)生新解，并返回步驟(2)。

基于上述改進(jìn)SA算法對(duì)聚類后的測(cè)點(diǎn)集進(jìn)行多目標(biāo)優(yōu)化，即可求解得到不同車次內(nèi)滿足節(jié)拍周期T0分配結(jié)果。本文以每個(gè)工位內(nèi)相鄰機(jī)器人測(cè)量任務(wù)集的聚類中心之間的距離為優(yōu)化參數(shù)，當(dāng)相鄰兩機(jī)器人之間的聚類中心差值越大時(shí)，則所建立的目標(biāo)函數(shù)F越小，使得相鄰機(jī)器人檢測(cè)任務(wù)集在空間位置中得到分離，減少機(jī)器人檢測(cè)任務(wù)集之間相互“交叉”的現(xiàn)象，從而降低了機(jī)器人間發(fā)生碰撞的概率。

為進(jìn)一步減少機(jī)器人在運(yùn)行過程中由于潛在沖突造成的時(shí)間損耗，本文通過解耦法實(shí)現(xiàn)多機(jī)器人協(xié)調(diào)運(yùn)動(dòng)。第一階段采用幾何法避障[23-24]實(shí)現(xiàn)每個(gè)機(jī)器人兩兩檢測(cè)任務(wù)在靜態(tài)環(huán)境中的局部無碰撞路徑規(guī)劃，建立檢測(cè)任務(wù)之間無碰撞時(shí)間矩陣，從而將單機(jī)器人路徑優(yōu)化問題抽象為TSP問題，通過優(yōu)化序列完成路徑優(yōu)化;第二階段以各機(jī)器人完成檢測(cè)任務(wù)的周期時(shí)間最短為優(yōu)化目標(biāo)，采用動(dòng)態(tài)優(yōu)先級(jí)的策略實(shí)現(xiàn)多機(jī)器人在碰撞狀態(tài)空間的協(xié)調(diào)優(yōu)化[25]。

從算法的時(shí)間復(fù)雜度上看，以基于模擬退火算法的單層次任務(wù)分配算法為例，其任務(wù)分配的時(shí)間復(fù)雜度約為O((log(Qmin/Q)L)2R0N)。其中：Q為模擬退火算法的初始溫度；Qmin為模擬退火算法的溫度下限；L為每次得到的Q值下算法的迭代次數(shù)；R0為各工位、各機(jī)器人中分配任務(wù)數(shù)目的最大值；N為待分配任務(wù)數(shù)目。而基于所提出HITA算法的時(shí)間復(fù)雜度約為O((log(Qmin/Q)L)2R0)。因此，所提出的HITA算法可有效地降低多車次多機(jī)器人檢測(cè)任務(wù)分配的算法復(fù)雜度，提高在線檢測(cè)任務(wù)分配問題的求解效率。

3 案例分析

結(jié)合某整車制造企業(yè)在線檢測(cè)工位對(duì)所提方法進(jìn)行應(yīng)用，該車型待測(cè)特征數(shù)目為200，其檢測(cè)測(cè)點(diǎn)位置與矢量方向如圖5所示。該檢測(cè)工位布置有4個(gè)搭載有光學(xué)測(cè)頭的工業(yè)機(jī)器人，型號(hào)為FANUC 2000iB-125L，在批次內(nèi)擬對(duì)4個(gè)車次白車身進(jìn)行全特征檢測(cè)，在線檢測(cè)工位檢測(cè)時(shí)間閾值T0=45 s。為了驗(yàn)證所提方法的有效性，本文引入目前廣泛應(yīng)用的就近原則和基于SA算法的求解方法[11,26](以下稱為對(duì)比方法)與本文提出的HITA方法進(jìn)行對(duì)比，通過提取各車次檢測(cè)周期、工位內(nèi)多機(jī)運(yùn)動(dòng)時(shí)間差等指標(biāo)對(duì)各方法的有效性進(jìn)行驗(yàn)證。

基于就近原則分配到各檢測(cè)機(jī)器人的任務(wù)集R1、R2、R3和R4中測(cè)點(diǎn)數(shù)目分別為63、36、46和55。進(jìn)一步基于SA退火算法[26]對(duì)不同車次內(nèi)多機(jī)器人的檢測(cè)任務(wù)進(jìn)行優(yōu)化分配，獲得最終的檢測(cè)任務(wù)細(xì)化分配結(jié)果如圖6所示。

根據(jù)本文提出的層次化任務(wù)分配算法，各檢測(cè)機(jī)器人的任務(wù)集R1、R2、R3和R4中測(cè)點(diǎn)數(shù)目分別為48、52、49和51，如圖7所示。

進(jìn)一步，利用FCM聚類算法對(duì)上述機(jī)器人的檢測(cè)任務(wù)集Rj進(jìn)行聚類，并劃分為4個(gè)簇。同時(shí)，考慮機(jī)器人與車身之間的碰撞檢測(cè)規(guī)避，計(jì)算每個(gè)任務(wù)簇內(nèi)單機(jī)無碰撞檢測(cè)路徑所需運(yùn)行時(shí)間。然后，利用提出的改進(jìn)SA算法將機(jī)器人檢測(cè)任務(wù)集的每個(gè)簇進(jìn)行組合優(yōu)化分配給各個(gè)車次。其中，需考慮不同任務(wù)簇組合時(shí)機(jī)器人的動(dòng)態(tài)碰撞規(guī)避，并根據(jù)碰撞情況更新各簇內(nèi)檢測(cè)路徑所需運(yùn)行時(shí)間，分配結(jié)果需滿足檢測(cè)周期，即T0<45 s，同時(shí)盡可能減少多機(jī)運(yùn)行時(shí)間差ΔT。如圖8所示為基于所提出的HITA方法給出的各車次任務(wù)分配結(jié)果。

基于上述兩類方法的任務(wù)分配結(jié)果，計(jì)算各車次在檢測(cè)工位內(nèi)各機(jī)器人的檢測(cè)時(shí)間并進(jìn)行對(duì)比分析。如表1所示為不同任務(wù)分配方法下的多機(jī)器人工位檢測(cè)時(shí)間。如圖9所示為不同車次在多機(jī)器人測(cè)量工位的檢測(cè)周期T0與多機(jī)最大運(yùn)行時(shí)間差ΔT。

表1 不同任務(wù)分配方法下的多機(jī)器人工位檢測(cè)時(shí)間對(duì)比 s

從圖6和圖8的測(cè)點(diǎn)集位置圖可見，對(duì)比方法得到每個(gè)車次的各機(jī)器人所分配測(cè)點(diǎn)在空間位置中出現(xiàn)相互”交叉”的現(xiàn)象，如圖6中方框內(nèi)測(cè)點(diǎn)，這將增大多機(jī)器人在運(yùn)行過程的干涉可能性。而基于HITA算法得到的每個(gè)機(jī)器人分配測(cè)點(diǎn)集在空間位置上盡可能相互獨(dú)立，減少了多機(jī)器人運(yùn)行過程中的干涉可能。這種相互分離的分配策略雖然存在延長(zhǎng)機(jī)器人運(yùn)行時(shí)間的可能性，但將有效降低機(jī)器人間協(xié)調(diào)規(guī)劃成本。

從任務(wù)分配結(jié)果的檢測(cè)時(shí)間上看，圖9顯示兩種方法得到各機(jī)器人在不同車次的檢測(cè)周期在34～44 s。基于對(duì)比方法,得到不同車次檢測(cè)周期平均為41.17 s，基于HITA算法的平均檢測(cè)周期為37.84 s，減少3.33 s，這將為在線測(cè)量中的測(cè)點(diǎn)數(shù)目增加提供條件。另外，針對(duì)多機(jī)運(yùn)行時(shí)間的一致性，本文將各車次的多機(jī)最大運(yùn)行時(shí)間差的平均值降低5.25 s，有效提升了多車次內(nèi)各機(jī)器人運(yùn)行時(shí)間的均衡性。因此，本文所提算法在既定檢測(cè)任務(wù)下，可保證工位內(nèi)多機(jī)器人檢測(cè)時(shí)間的一致性，同時(shí)可有效提高檢測(cè)工位內(nèi)多機(jī)器人工作效率，更好地保證車身精度的在線測(cè)量需求。

4 結(jié)束語

本文提出一種在線光學(xué)檢測(cè)系統(tǒng)層級(jí)化任務(wù)分配方法，包括機(jī)器人間特征分配、面向車次的特征聚類及任務(wù)集組合優(yōu)化分配求解等步驟。通過基于歐式距離的惰性旅行商問題求解確定了各機(jī)器人的檢測(cè)特征任務(wù)集，為后續(xù)進(jìn)行車次間任務(wù)分配提供了基礎(chǔ)。通過FCM算法對(duì)機(jī)器人獲得的檢測(cè)任務(wù)集進(jìn)行聚類，并利用改進(jìn)的SA算法將各任務(wù)簇細(xì)化分配給不同車次，在保證生產(chǎn)節(jié)拍、多機(jī)運(yùn)行時(shí)間差等多約束下，提升了車身在線檢測(cè)效率。通過案例分析，驗(yàn)證了本文算法對(duì)在線檢測(cè)過程中任務(wù)分配問題求解的有效性，也將為多機(jī)器人檢測(cè)系統(tǒng)的運(yùn)動(dòng)規(guī)劃仿真軟件開發(fā)提供算法基礎(chǔ)。