趙文政,劉銀華+,金 隼
(1.上海理工大學(xué) 機(jī)械工程學(xué)院,上海 200093;2.上海交通大學(xué) 機(jī)械與動力工程學(xué)院,上海 200240)
多機(jī)器人光學(xué)測量系統(tǒng)以其非接觸、可在線等特點在汽車制造領(lǐng)域得到廣泛推廣,檢測系統(tǒng)的路徑規(guī)劃研究也逐漸受到學(xué)者們的關(guān)注[1]。在實際應(yīng)用中,多機(jī)器人光學(xué)檢測系統(tǒng)的運(yùn)動規(guī)劃需要綜合考慮任務(wù)分配、機(jī)器人路徑規(guī)劃和多機(jī)器人協(xié)調(diào)等問題[2-4],其中在線檢測的任務(wù)分配是光學(xué)測量路徑規(guī)劃的重要環(huán)節(jié),也是影響檢測周期、多機(jī)器人沖突以及測量路徑結(jié)果的重要因素[5]。
多機(jī)器人任務(wù)分配問題是典型的混合整數(shù)線性規(guī)劃問題(Mixed Integer Linear Programming, MILP),需要對考慮機(jī)器人路徑規(guī)劃和機(jī)器人之間協(xié)調(diào)等條件下的多約束問題進(jìn)行優(yōu)化求解。典型的方法有基于MILP模型的求解策略研究[6-7],另外Spensieri等[8]通過建立的MILP模型,利用分支定界的方法實現(xiàn)焊點分配,并搜索得到最優(yōu)解;Lopes等[9]在MILP模型框架下,考慮機(jī)器人參數(shù)變換、分布限制、運(yùn)動時間和機(jī)器人干擾約束等因素,對機(jī)器人焊接生產(chǎn)線進(jìn)行任務(wù)分配。MILP求解可獲得最優(yōu)解,但其計算資源占用量大,計算效率低,因此不適合大規(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]以最小化完工時間為優(yōu)化目標(biāo),利用領(lǐng)域搜索策略和啟發(fā)式規(guī)則相結(jié)合的混合遺傳算法求解作業(yè)車間內(nèi)多機(jī)器人制造單元調(diào)度問題;張則強(qiáng)等[17]針對裝配線平衡問題的具體特點,綜合考慮裝配作業(yè)時間和后續(xù)任務(wù)數(shù)的分級位置權(quán)重,通過改進(jìn)蟻群算法進(jìn)行裝配線平衡問題求解。
上述算法可實現(xiàn)多機(jī)在規(guī)定時間內(nèi)的任務(wù)均衡分配。但隨著任務(wù)數(shù)目增加,以上方法存在計算量指數(shù)增加的問題。為此,學(xué)者們提出對任務(wù)集進(jìn)行聚類分析[18-20],并對聚類后的簇進(jìn)行多機(jī)分配以達(dá)到降低計算量。如早期研究中,Elango等[21]首先基于K-means和最小距離對任務(wù)集進(jìn)行聚類,然后計算每個機(jī)器人與聚類集群所組成集合的成本,最終根據(jù)拍賣算法進(jìn)行任務(wù)分配;Janati等[22]利用K-means算法將任務(wù)劃分為機(jī)器人的數(shù)量,利用線性分配將機(jī)器人分配給任務(wù)集。
從上述研究可以看出,已有任務(wù)分配方法主要適用于單層次任務(wù)分配問題,即任務(wù)到多機(jī)器人的分配。而在車身在線檢測(生產(chǎn)節(jié)拍為60~90 s)過程中,需要將數(shù)百甚至上千個檢測任務(wù)同時分配到多機(jī)器人、多批次車身,以實現(xiàn)有限檢測周期內(nèi)車身特征的全檢,同時滿足多機(jī)器人動態(tài)環(huán)境下的協(xié)調(diào)運(yùn)動等需求。面對大量檢測任務(wù)到多批次車身、多機(jī)器人的分配問題,當(dāng)機(jī)器人數(shù)目、車次數(shù)目一定時,潛在的任務(wù)分配方案的數(shù)目與待分配任務(wù)數(shù)目之間呈指數(shù)關(guān)系,且每次候選分配方案均涉及機(jī)器人運(yùn)動學(xué)與路徑規(guī)劃的優(yōu)化求解。因此,本文提出層級化測量任務(wù)分配(Hierarchical Inspection Task Allocation, HITA)算法,通過將待測任務(wù)集的初步分配、模糊聚類以及面向多機(jī)協(xié)調(diào)的多目標(biāo)優(yōu)化的細(xì)化分配,實現(xiàn)檢測任務(wù)的高效分配,降低算法復(fù)雜度(具體分析見2.2節(jié)),提升在線檢測效率。
在汽車車身裝配生產(chǎn)線中,光學(xué)在線檢測(如圖1)是實現(xiàn)車身質(zhì)量100%測量的重要手段。考慮到車身大型曲面結(jié)構(gòu),需通過多臺搭載光學(xué)傳感器的機(jī)器人對車身特征(如孔、槽、曲面、邊緣、螺紋等)進(jìn)行非接觸和在線測量。圖2所示為多機(jī)器人光學(xué)在線檢測過程,其中BIW(body in white)表示白車身。由于在線生產(chǎn)節(jié)拍的限制,多機(jī)器人工位無法從單一車身上采集到所有關(guān)鍵特征的信息。這就要求將任務(wù)集分配給同一批次內(nèi)連續(xù)m個車次進(jìn)行檢測,每臺車身分配到的任務(wù)子集互不相交且各子集之和為任務(wù)全集。另一方面,針對確定的車次,需將檢測任務(wù)分配給工位內(nèi)不同機(jī)器人,并要求多機(jī)器人系統(tǒng)無干涉協(xié)調(diào)運(yùn)動,且滿足工位內(nèi)檢測周期、多機(jī)運(yùn)行時間一致性等要求。
本文的目的是將檢測任務(wù)分配到不同檢測車次內(nèi)的各機(jī)器人,使得每個機(jī)器人所分配的任務(wù)量的檢測時間盡可能短且滿足生產(chǎn)節(jié)拍限制等約束。結(jié)合上述問題描述,本文層次化任務(wù)分配過程進(jìn)行如下假設(shè):
(1)多層次任務(wù)分配時,待分配車次的數(shù)目為提前預(yù)設(shè);
(2)各待測特征的光學(xué)最佳測量參數(shù)(如入射角、景深等)及公差已知;
(3)車身檢測過程各機(jī)器人的起始測量時間相同;
(4)針對不同類型的待測特征,其光學(xué)檢測時間相同,即機(jī)器人到達(dá)測量位置后的測量時間相同;
(5)機(jī)器人完成單車次任務(wù)檢測后均返回其初始位置。
基于上述假設(shè),本文的在線檢測多任務(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) 其中各符號的含義如下: n為檢測工位內(nèi)機(jī)器人總數(shù); m為批次內(nèi)車次總數(shù); Rij為第i個車次第j個機(jī)器人分配的任務(wù)集,i={1,2,…,m},j={1,2,…,n}; Ri為批次內(nèi)第i個車次下各個機(jī)器人候選任務(wù)集; R為檢測任務(wù)全集; Ti為第i車次的實際檢測周期; T0為在線檢測工位的生產(chǎn)節(jié)拍; ΔTi為第i個車次內(nèi)n個機(jī)器人中檢測時間的極差; Tij為第i個車次第j個機(jī)器人的檢測時間; ε為最大的運(yùn)行時間極差閾值。 第i個車次第j個機(jī)器人在給定任務(wù)集下檢測時間的計算公式可表示為: (6) (7) (8) 其中:t01、tM0為分別表示從機(jī)器人運(yùn)動路徑中初始位置到首個待測特征和最終待測特征返回機(jī)器人初始位置的機(jī)器人運(yùn)動時間;xpq為0,1變量;tpq為給定車次下某機(jī)器人從特征Fp移動到特征Fq的運(yùn)動時間; 為了提高在線檢測效率,本文采用層級化方法對該分配問題進(jìn)行啟發(fā)式求解,具體流程為:首先基于懶惰旅行商問題的求解策略,將檢測共享空間內(nèi)的檢測特征分配給不同機(jī)器人,實現(xiàn)檢測任務(wù)全集到多機(jī)器人的初步分配。然后,針對上述機(jī)器人分配到的任務(wù)集,采用模糊C-Means(Fuzzy C-means, FCM)算法進(jìn)行聚類分析,獲得與檢測工位機(jī)器人數(shù)目相同的任務(wù)簇。最后,提出考慮任務(wù)簇中心和單機(jī)運(yùn)動時間等多目標(biāo)的任務(wù)分配優(yōu)化模型,實現(xiàn)測量任務(wù)到具體車次、機(jī)器人的細(xì)化分配。 通常,搭載光學(xué)測頭的六軸機(jī)器人左右對稱分布于在線檢測工位,車身尺寸特征通常會落在一個或多個機(jī)器人可達(dá)范圍內(nèi)。當(dāng)檢測特征落在多機(jī)器人共享空間內(nèi)時,需將其分配給某個確定的機(jī)器人。傳統(tǒng)基于距離的分配方法將導(dǎo)致每個車次下多機(jī)器人檢測時間的極差增大,從而導(dǎo)致檢測效率不高。因此,為了保證每個車次機(jī)器人工作時間的一致性,本文在設(shè)置每個機(jī)器人所分配檢測特征數(shù)目約束的條件下,利用懶惰旅行商問題(lazy Traveling Salesman Problem, lazy TSP)的求解策略,將共享空間內(nèi)的檢測特征粗分配到每個機(jī)器人。具體共享空間內(nèi)檢測任務(wù)的分配策略如下: (1)根據(jù)機(jī)器人可達(dá)性計算得到多個機(jī)器人共享空間內(nèi)的檢測特征集合,如第j個和第j+1個機(jī)器人共享空間內(nèi)檢測特征集合為Uj,j+1。以Uj,j+1內(nèi)的特征為例,說明提出算法的分配過程。 (2)根據(jù)檢測特征的總數(shù)目以及機(jī)器人的數(shù)目,設(shè)置單機(jī)器人最大檢測特征數(shù)目的閾值為φ。 (5)若同時滿足Lj (6)重復(fù)步驟(3)~步驟(5)直到Uj,j+1內(nèi)的特征分配完成。 基于上述分配算法,即可得到每個機(jī)器人分配的特征任務(wù)集R1,R2,…,Rn。具體分配過程的偽代碼如下: imax=sizeof(Uj,j+1);%imax表示Uj,j+1內(nèi)集合的數(shù)目; for i=1:imax if Lj elseif Lj end end 對檢測任務(wù)粗分配后,需進(jìn)一步將其細(xì)分給批次內(nèi)不同車次下的多個檢測機(jī)器人。傳統(tǒng)將路徑距離或檢測時間作為目標(biāo)函數(shù)的MILP模型的任務(wù)分配方法,往往忽略多機(jī)器人分配任務(wù)集之間的關(guān)系,導(dǎo)致多機(jī)協(xié)調(diào)階段機(jī)器人發(fā)生沖突甚至停機(jī)的現(xiàn)象,從而降低了檢測效率。為解決該問題,本文基于聚類算法將第j個機(jī)器人的粗分任務(wù)集Rj劃分成m類。然后,根據(jù)式(6)計算機(jī)器人無碰檢測路徑的最短時間。進(jìn)一步,考慮批次內(nèi)多車次下機(jī)器人的檢測時間一致性,以及多車次下相鄰機(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聚類是一種將每個任務(wù)對象非此即彼地嚴(yán)格分類的聚類算法。然而,在多機(jī)器人檢測工位中,對于檢測任務(wù)集內(nèi)的部分測量任務(wù)可以由多個車次內(nèi)多個機(jī)器人檢測,即并非嚴(yán)格的“0-1”關(guān)系,若利用K-means進(jìn)行聚類,將很難得到較為明顯的簇,且由于車身檢測特征分布差異較大,致使各個簇內(nèi)元素較為分散,優(yōu)化分配后會增加各車次內(nèi)的機(jī)器人運(yùn)行時間增加,降低檢測效率。FCM算法作為一種無監(jiān)督聚類算法,利用模糊理論對重要數(shù)據(jù)進(jìn)行分析和建模,使得被劃分到同一簇的任務(wù)之間相似度較大,而不同簇之間的相似度較小。因此,F(xiàn)CM能通過優(yōu)化每個檢測任務(wù)的隸屬度獲得較為明顯的聚類效果,使得簇內(nèi)元素分布較為集中,從而為后續(xù)分配優(yōu)化提供基礎(chǔ)。 綜上所述,本文基于FCM算法對任務(wù)集Rj進(jìn)行聚類,具體過程為:設(shè)第j個機(jī)器人的任務(wù)集為Rj={F1,F2,…,FN},其中N為Rj內(nèi)測點數(shù)量,F(xiàn)為Rj內(nèi)的測點;通過迭代的方法將任務(wù)集Rj分解為m個子集Cij(i=1,2,…,m,j=1,2,…,n),并根據(jù)隸屬度計算每個子集聚類中心vij(i=1,2,…,m)。因此,基于FCM算法求解,可將2.1節(jié)中每個機(jī)器人分配到的檢測任務(wù)集Rj分解成n×m個子集。 在上述任務(wù)集聚類基礎(chǔ)上,為了縮短機(jī)器人之間的運(yùn)行時間差,同時減少機(jī)器人之間發(fā)生沖突的概率,本文以SA算法對不同車次、多機(jī)器人檢測任務(wù)進(jìn)行優(yōu)化分配,算法流程如圖3所示。 具體算法流程如下: (2)基于上述計算得到的每個車次內(nèi)機(jī)器人檢測時間Tij及產(chǎn)生的新解W,計算各車次內(nèi)檢測時間的極差值ΔTi。其中單車次下機(jī)器人檢測時間的計算方法如下:針對給定的機(jī)器人檢測任務(wù),本文采用幾何避障算法對機(jī)器人初步分配得到的測點集Cij內(nèi)的兩兩檢測特征的局部無碰撞路徑進(jìn)行優(yōu)化,建立兩兩檢測測點之間的無碰撞運(yùn)動時間矩陣[23-24]。同時,為了保證單機(jī)器人檢測時間最優(yōu),將問題轉(zhuǎn)換為尋找時間最短的無碰撞路徑的TSP。對于TSP,可通過SA、GA以及分支定界等算法進(jìn)行求解,最終得到每個機(jī)器人對不同測點集Cij的檢測時間Tij。 (3)以ΔTi和相鄰兩機(jī)器人(若兩機(jī)器人之間存在檢測共享空間,即為兩機(jī)器人相鄰)所分配的任務(wù)集Cij的聚類中心vij之間距離建立SA算法的加權(quán)多目標(biāo)函數(shù): (9) (4)通過不同行內(nèi)元素相互交換產(chǎn)生新解W′(如圖4),計算ΔF=F(W′)-F(W)。 (5)計算ΔF,并判斷其是否小于零,若ΔF<0,則接受W′為新的當(dāng)前解;若ΔF>0,則以一定概率接受為新解。 (6)判斷W′是否滿足迭代終止條件,滿足則輸出多車次、多機(jī)器人任務(wù)分配結(jié)果;否則,添加擾動產(chǎn)生新解,并返回步驟(2)。 基于上述改進(jìn)SA算法對聚類后的測點集進(jìn)行多目標(biāo)優(yōu)化,即可求解得到不同車次內(nèi)滿足節(jié)拍周期T0分配結(jié)果。本文以每個工位內(nèi)相鄰機(jī)器人測量任務(wù)集的聚類中心之間的距離為優(yōu)化參數(shù),當(dāng)相鄰兩機(jī)器人之間的聚類中心差值越大時,則所建立的目標(biāo)函數(shù)F越小,使得相鄰機(jī)器人檢測任務(wù)集在空間位置中得到分離,減少機(jī)器人檢測任務(wù)集之間相互“交叉”的現(xiàn)象,從而降低了機(jī)器人間發(fā)生碰撞的概率。 為進(jìn)一步減少機(jī)器人在運(yùn)行過程中由于潛在沖突造成的時間損耗,本文通過解耦法實現(xiàn)多機(jī)器人協(xié)調(diào)運(yùn)動。第一階段采用幾何法避障[23-24]實現(xiàn)每個機(jī)器人兩兩檢測任務(wù)在靜態(tài)環(huán)境中的局部無碰撞路徑規(guī)劃,建立檢測任務(wù)之間無碰撞時間矩陣,從而將單機(jī)器人路徑優(yōu)化問題抽象為TSP問題,通過優(yōu)化序列完成路徑優(yōu)化;第二階段以各機(jī)器人完成檢測任務(wù)的周期時間最短為優(yōu)化目標(biāo),采用動態(tài)優(yōu)先級的策略實現(xiàn)多機(jī)器人在碰撞狀態(tài)空間的協(xié)調(diào)優(yōu)化[25]。 從算法的時間復(fù)雜度上看,以基于模擬退火算法的單層次任務(wù)分配算法為例,其任務(wù)分配的時間復(fù)雜度約為O((log(Qmin/Q)L)2R0N)。其中:Q為模擬退火算法的初始溫度;Qmin為模擬退火算法的溫度下限;L為每次得到的Q值下算法的迭代次數(shù);R0為各工位、各機(jī)器人中分配任務(wù)數(shù)目的最大值;N為待分配任務(wù)數(shù)目。而基于所提出HITA算法的時間復(fù)雜度約為O((log(Qmin/Q)L)2R0)。因此,所提出的HITA算法可有效地降低多車次多機(jī)器人檢測任務(wù)分配的算法復(fù)雜度,提高在線檢測任務(wù)分配問題的求解效率。 結(jié)合某整車制造企業(yè)在線檢測工位對所提方法進(jìn)行應(yīng)用,該車型待測特征數(shù)目為200,其檢測測點位置與矢量方向如圖5所示。該檢測工位布置有4個搭載有光學(xué)測頭的工業(yè)機(jī)器人,型號為FANUC 2000iB-125L,在批次內(nèi)擬對4個車次白車身進(jìn)行全特征檢測,在線檢測工位檢測時間閾值T0=45 s。為了驗證所提方法的有效性,本文引入目前廣泛應(yīng)用的就近原則和基于SA算法的求解方法[11,26](以下稱為對比方法)與本文提出的HITA方法進(jìn)行對比,通過提取各車次檢測周期、工位內(nèi)多機(jī)運(yùn)動時間差等指標(biāo)對各方法的有效性進(jìn)行驗證。 基于就近原則分配到各檢測機(jī)器人的任務(wù)集R1、R2、R3和R4中測點數(shù)目分別為63、36、46和55。進(jìn)一步基于SA退火算法[26]對不同車次內(nèi)多機(jī)器人的檢測任務(wù)進(jìn)行優(yōu)化分配,獲得最終的檢測任務(wù)細(xì)化分配結(jié)果如圖6所示。 根據(jù)本文提出的層次化任務(wù)分配算法,各檢測機(jī)器人的任務(wù)集R1、R2、R3和R4中測點數(shù)目分別為48、52、49和51,如圖7所示。 進(jìn)一步,利用FCM聚類算法對上述機(jī)器人的檢測任務(wù)集Rj進(jìn)行聚類,并劃分為4個簇。同時,考慮機(jī)器人與車身之間的碰撞檢測規(guī)避,計算每個任務(wù)簇內(nèi)單機(jī)無碰撞檢測路徑所需運(yùn)行時間。然后,利用提出的改進(jìn)SA算法將機(jī)器人檢測任務(wù)集的每個簇進(jìn)行組合優(yōu)化分配給各個車次。其中,需考慮不同任務(wù)簇組合時機(jī)器人的動態(tài)碰撞規(guī)避,并根據(jù)碰撞情況更新各簇內(nèi)檢測路徑所需運(yùn)行時間,分配結(jié)果需滿足檢測周期,即T0<45 s,同時盡可能減少多機(jī)運(yùn)行時間差ΔT。如圖8所示為基于所提出的HITA方法給出的各車次任務(wù)分配結(jié)果。 基于上述兩類方法的任務(wù)分配結(jié)果,計算各車次在檢測工位內(nèi)各機(jī)器人的檢測時間并進(jìn)行對比分析。如表1所示為不同任務(wù)分配方法下的多機(jī)器人工位檢測時間。如圖9所示為不同車次在多機(jī)器人測量工位的檢測周期T0與多機(jī)最大運(yùn)行時間差ΔT。 表1 不同任務(wù)分配方法下的多機(jī)器人工位檢測時間對比 s 從圖6和圖8的測點集位置圖可見,對比方法得到每個車次的各機(jī)器人所分配測點在空間位置中出現(xiàn)相互”交叉”的現(xiàn)象,如圖6中方框內(nèi)測點,這將增大多機(jī)器人在運(yùn)行過程的干涉可能性。而基于HITA算法得到的每個機(jī)器人分配測點集在空間位置上盡可能相互獨立,減少了多機(jī)器人運(yùn)行過程中的干涉可能。這種相互分離的分配策略雖然存在延長機(jī)器人運(yùn)行時間的可能性,但將有效降低機(jī)器人間協(xié)調(diào)規(guī)劃成本。 從任務(wù)分配結(jié)果的檢測時間上看,圖9顯示兩種方法得到各機(jī)器人在不同車次的檢測周期在34~44 s。基于對比方法,得到不同車次檢測周期平均為41.17 s,基于HITA算法的平均檢測周期為37.84 s,減少3.33 s,這將為在線測量中的測點數(shù)目增加提供條件。另外,針對多機(jī)運(yùn)行時間的一致性,本文將各車次的多機(jī)最大運(yùn)行時間差的平均值降低5.25 s,有效提升了多車次內(nèi)各機(jī)器人運(yùn)行時間的均衡性。因此,本文所提算法在既定檢測任務(wù)下,可保證工位內(nèi)多機(jī)器人檢測時間的一致性,同時可有效提高檢測工位內(nèi)多機(jī)器人工作效率,更好地保證車身精度的在線測量需求。 本文提出一種在線光學(xué)檢測系統(tǒng)層級化任務(wù)分配方法,包括機(jī)器人間特征分配、面向車次的特征聚類及任務(wù)集組合優(yōu)化分配求解等步驟。通過基于歐式距離的惰性旅行商問題求解確定了各機(jī)器人的檢測特征任務(wù)集,為后續(xù)進(jìn)行車次間任務(wù)分配提供了基礎(chǔ)。通過FCM算法對機(jī)器人獲得的檢測任務(wù)集進(jìn)行聚類,并利用改進(jìn)的SA算法將各任務(wù)簇細(xì)化分配給不同車次,在保證生產(chǎn)節(jié)拍、多機(jī)運(yùn)行時間差等多約束下,提升了車身在線檢測效率。通過案例分析,驗證了本文算法對在線檢測過程中任務(wù)分配問題求解的有效性,也將為多機(jī)器人檢測系統(tǒng)的運(yùn)動規(guī)劃仿真軟件開發(fā)提供算法基礎(chǔ)。2 層次化檢測任務(wù)分配
2.1 檢測任務(wù)到機(jī)器人系統(tǒng)的粗分配
2.2 針對不同車次下多機(jī)器人的細(xì)化分配
3 案例分析
4 結(jié)束語