劉少睿,田 威,沈建新,李 波,胡俊山

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

0 引言

諸如飛機(jī)機(jī)身、飛船艙體等大型復(fù)雜結(jié)構(gòu)的制造任務(wù)是航空航天領(lǐng)域中一類典型難題，其工作量大、周期長(zhǎng)、精度要求高，且直接影響最終產(chǎn)品的成本和服役性能。當(dāng)前，新一代產(chǎn)品正呈現(xiàn)大型化和復(fù)雜化的趨勢(shì)，結(jié)構(gòu)件尺寸普遍超過現(xiàn)有加工中心的工作行程，導(dǎo)致近年來多機(jī)器人協(xié)同制造系統(tǒng)和原位作業(yè)模式興起[1-4]，其在車間內(nèi)部署多臺(tái)機(jī)器人加工單元，通過協(xié)同作業(yè)實(shí)現(xiàn)復(fù)雜產(chǎn)品的高效率、高柔性制造。然而，多機(jī)器人系統(tǒng)的工作空間非結(jié)構(gòu)化和分布式特性導(dǎo)致其協(xié)同復(fù)雜、避碰問題顯著；此外，復(fù)雜產(chǎn)品的加工任務(wù)通常因工藝和工序要求而存在加工時(shí)序約束。為解決以上問題，同時(shí)最大化系統(tǒng)的加工效率，有必要對(duì)多機(jī)器人系統(tǒng)的加工任務(wù)調(diào)度規(guī)劃方法開展研究。

加工任務(wù)的工藝、工序要求引起的時(shí)序約束，以及機(jī)器人關(guān)于任務(wù)的沖突和避碰，通?？梢詺w類為帶有時(shí)間和順序約束的多機(jī)器人規(guī)劃問題。NUNES等[5]于2017年對(duì)此類問題進(jìn)行了系統(tǒng)性分析和歸類，提出用時(shí)間窗(Time Window, TW)表示任務(wù)的時(shí)間約束，用并發(fā)和優(yōu)先(Synchronization and Precedence, SP)表示任務(wù)的順序約束。時(shí)序約束的建模和約束一致性檢驗(yàn)是該領(lǐng)域中的首要問題，DECHTER等[6]提出了簡(jiǎn)單時(shí)間網(wǎng)絡(luò)(Simple Temporal Network, STN)模型，其中用頂點(diǎn)表示時(shí)間窗的起止時(shí)間變量，用加權(quán)有向邊表示隱含的時(shí)間代價(jià)及變量之間的不等式約束。STN規(guī)定任意兩時(shí)間變量之間至多只存在一項(xiàng)約束，使模型很容易通過變量的不等式關(guān)系檢驗(yàn)一致性[7-8]，加之其支持動(dòng)態(tài)修改和擴(kuò)充的特性[9-10]，使STN大量應(yīng)用于調(diào)度優(yōu)化問題的求解中[10-15]。NUNES等[11]將STN與連續(xù)單件拍賣算法結(jié)合，提出了能夠處理時(shí)間約束任務(wù)的多機(jī)器人任務(wù)分配算法TeSSI，其核心是基于插入啟發(fā)式的任務(wù)競(jìng)標(biāo)機(jī)制，機(jī)器人借助STN確定不破壞時(shí)間約束并使代價(jià)函數(shù)最小化的任務(wù)及任務(wù)在時(shí)序中的插入位置;GOMBOLAY等[13-14]針對(duì)多機(jī)器人應(yīng)用于飛機(jī)裝配任務(wù)時(shí)遇到的時(shí)間和空間約束提出了Tercio算法，其中結(jié)合了多智能體任務(wù)調(diào)度器與混合整數(shù)線性規(guī)劃，并使用STN表達(dá)任務(wù)的優(yōu)先約束和時(shí)間窗寬度限制，從而得到滿足裝配任務(wù)工序和工時(shí)要求的調(diào)度計(jì)劃。

以STN為代表的任務(wù)時(shí)序約束建模方法及其變體[16]盡管大量地應(yīng)用于包括制造領(lǐng)域在內(nèi)的多機(jī)器人任務(wù)分配/時(shí)序規(guī)劃中，但認(rèn)為時(shí)序約束是任務(wù)的固有性質(zhì)或在優(yōu)化前已經(jīng)給定，如制造問題中較常見的工序要求[17]。在本文面向的多機(jī)器人協(xié)同制造系統(tǒng)中，除部分任務(wù)固有的并發(fā)約束外，還存在解決避碰問題所需的優(yōu)先約束和機(jī)器人自身調(diào)度計(jì)劃內(nèi)生成的優(yōu)先約束，此類約束在算法尋優(yōu)前并未確定，例如兩空間臨近的任務(wù)互為前序均可實(shí)現(xiàn)避碰要求，但如何設(shè)置此部分約束才能使算法找到效率最優(yōu)的結(jié)果，則仍是一個(gè)開放問題。此外，避碰的優(yōu)先約束還導(dǎo)致了機(jī)器人之間的跨調(diào)度依賴性[18-20]，且優(yōu)先約束的不恰當(dāng)設(shè)置還可能導(dǎo)致約束不一致問題[7-9]，進(jìn)一步增加了問題復(fù)雜度和尋優(yōu)難度。

針對(duì)加工任務(wù)的時(shí)序約束存在不確定部分時(shí)，通過多機(jī)器人調(diào)度優(yōu)化實(shí)現(xiàn)加工效率最大化的問題，本文基于帶雙向邊的有向圖提出一種時(shí)序約束表達(dá)模型，能夠快速生成完整的時(shí)序約束集實(shí)例，并通過閉環(huán)檢測(cè)算法高效地完成約束一致性的定性檢驗(yàn)，從而消除死鎖并處理機(jī)器人的跨調(diào)度依賴性；在此基礎(chǔ)上通過迭代局部搜索(Iterated Local Search, ILS)迭代優(yōu)化有向圖模型實(shí)例，實(shí)現(xiàn)對(duì)約束集的搜索，從而找到支持加工效率最大化的約束集實(shí)例；為快速生成完整的機(jī)器人調(diào)度計(jì)劃、減小每次迭代的計(jì)算量，采用插入啟發(fā)式將時(shí)序約束模型外的無約束安全任務(wù)快速插入到機(jī)器人調(diào)度計(jì)劃中，將調(diào)度計(jì)劃由定性時(shí)間描述轉(zhuǎn)變?yōu)槎繒r(shí)間描述。最后結(jié)合仿真與實(shí)驗(yàn)驗(yàn)證了上述方法在處理時(shí)序約束、提升加工效率及防碰撞上的有效性和可靠性。

1 工程需求

本文以大型飛船艙體表面特征的多機(jī)器人協(xié)同原位制造任務(wù)為研究對(duì)象，如圖1所示。飛船艙體為一大尺寸圓柱形結(jié)構(gòu)件，為安裝傳感器、雷達(dá)天線及空間機(jī)械臂等艙外載荷，需在其表面安裝大量支架作為載荷的固定點(diǎn)。艙體制造任務(wù)的挑戰(zhàn)在于艙外載荷對(duì)安裝精度有極高要求，而艙體本身因滾彎、焊接等工藝原因而存在變形誤差，為保證載荷相對(duì)艙體全局基準(zhǔn)的精度，必須在支架安裝于艙體表面的狀態(tài)下對(duì)支架頂部的安裝面進(jìn)行原位測(cè)量和精加工，通過精確去除加工余量達(dá)到保證載荷最終安裝精度的目標(biāo)。工程中采用多機(jī)器人協(xié)同制造系統(tǒng)完成該制造任務(wù)，機(jī)器人每次能夠處理艙體表面一定區(qū)域內(nèi)的支架，艙體通過多次旋轉(zhuǎn)完成全部支架的加工，本文研究?jī)?nèi)容為機(jī)器人一次協(xié)同加工中的調(diào)度優(yōu)化。

2 問題建模

Sj=[sj,1sj,2…sj,l…]

(1)

(2)

并滿足以下約束：

C1:Ai?Trch(ri)(i∈[1,k]);

C3:?i,j∈[1,k](i≠j),Ai∩Aj=?;

C6:‖t(Si,c)-t(Sj,c)‖≥dr2r_min,i≠j。

(3)

在以上調(diào)度優(yōu)化問題中，并發(fā)約束是并發(fā)任務(wù)所固有的，而對(duì)于避碰問題涉及的任務(wù)(可能令機(jī)器人不滿足C6的任務(wù))，其優(yōu)先約束并未在問題中給定。為實(shí)現(xiàn)避碰目標(biāo)，優(yōu)化算法必須明確此類任務(wù)之間的優(yōu)先約束，從而使可能引起碰撞的任務(wù)的加工時(shí)間窗完全錯(cuò)開。而由于能夠?qū)崿F(xiàn)避碰的優(yōu)先約束通常有多種設(shè)置方式(如第1章中，令t1→t2或t1←t2均可避免機(jī)器人在t1、t2上發(fā)生碰撞)，本文首先在3.2節(jié)提出一種時(shí)序約束建模方法，以獲得一組可行的優(yōu)先約束設(shè)置，而后在3.3節(jié)通過迭代局部搜索算法尋找使加工效率最優(yōu)的約束集，從而最終明確理想的優(yōu)先約束設(shè)置方式。

3 方法實(shí)現(xiàn)

3.1 基于任務(wù)分配的機(jī)器人分區(qū)加工

在調(diào)度規(guī)劃前必須首先將任務(wù)集T分配至機(jī)器人，即首先確定任務(wù)分配TA={A1,A2,…,Ak}。任務(wù)分配期望向k臺(tái)機(jī)器人平均分配任務(wù)集T的加工工作量，從而改善多機(jī)器人加工效率，為此應(yīng)最小化機(jī)器人之間的工作量差距，這等價(jià)于最小化k臺(tái)機(jī)器人中的工作量最大值：

(4)

(5)

(6)

(7)

并滿足約束：

C1:ta∈Aj∩Trch(ri),

(8)

3.2 時(shí)序約束表達(dá)模型

IZi={ta|ta∈Ai,?tb∈Ak,

k≠i,‖ta-tb‖

(9)

為實(shí)現(xiàn)由Gu生成最終的時(shí)序約束模型，將全部2m個(gè)并發(fā)任務(wù)和干涉區(qū)隨機(jī)排序形成序列Q，而后根據(jù)頂點(diǎn)在Q中的順序確定優(yōu)先約束，并在Gu中設(shè)置對(duì)應(yīng)有向邊：

(1)當(dāng)任意兩頂點(diǎn)vi，vj之間有干涉關(guān)系，則按照順序先后有優(yōu)先約束vi→vj或vi←vj，無向邊變?yōu)橛邢蜻叀?/p>

(2)當(dāng)兩頂點(diǎn)vi，vj屬于同一機(jī)器人rk，且兩者之間沒有其他頂點(diǎn)屬于rk，則同樣按順序先后為其增加優(yōu)先約束，圖中增加了代表本地調(diào)度內(nèi)優(yōu)先約束的新有向邊。

有向圖的閉環(huán)檢驗(yàn)通?？梢允褂蒙疃葍?yōu)先搜索(Depth First Search, DFS )，為避免經(jīng)典DFS直接將雙向邊連接的頂點(diǎn)誤判為閉環(huán)，特別令DFS采取以下策略：當(dāng)頂點(diǎn)有雙向邊連接時(shí)，總是在遍歷其他路徑后才沿雙向邊搜索。該策略能有效檢驗(yàn)帶雙向邊有向圖的閉環(huán)，證明如下：

(1)假設(shè)有向圖Gd中的兩頂點(diǎn)A、B之間有雙向邊連接(記為A?B)， 且A、B在某一閉環(huán)內(nèi)，則必有?以外的路徑可由A到B或由B到A。

(2)對(duì)于(1)中第一種情況，即存在不依賴?由A到B的路徑，假如DFS先到達(dá)A，并在使用?之前沿該路徑來到B，則最終由B通過?到達(dá)A，從而發(fā)現(xiàn)閉環(huán)。若DFS先到達(dá)B，則最終通過?來到A，并從A發(fā)現(xiàn)到達(dá)B的其他路徑，從而發(fā)現(xiàn)閉環(huán)。

(3)對(duì)于(1)中第二種情況(存在不依賴?由B到A的路徑)，通過DFS發(fā)現(xiàn)閉環(huán)的原理與2相同。

本節(jié)參照一具體實(shí)例對(duì)所提出的時(shí)序約束模型進(jìn)行說明，但該模型的應(yīng)用并不受限于實(shí)例中特定的機(jī)器人數(shù)量、加工分區(qū)情況以及多機(jī)器人的布局方式，且能夠反映任意兩機(jī)器人之間滿足并發(fā)和避碰條件的時(shí)序約束，因此有條件應(yīng)用于本研究之外的其他多機(jī)器人調(diào)度規(guī)劃問題中。此外，與廣泛應(yīng)用的STN模型相比，所提出模型的區(qū)別主要在于：

(1)在所提出模型中，頂點(diǎn)表示某一存在時(shí)序約束的子任務(wù)集(并發(fā)任務(wù)或干涉區(qū))，而非STN中的時(shí)間變量，頂點(diǎn)間連接的有向邊表示時(shí)序約束而非時(shí)間代價(jià)。

(2)所提出模型定性描述任務(wù)時(shí)序，并首先檢驗(yàn)約束一致性，再根據(jù)約束確定時(shí)間變量之間的不等式關(guān)系，而在STN中，任務(wù)時(shí)序由時(shí)間變量定量描述，約束一致性直接通過時(shí)間變量的不等式關(guān)系檢驗(yàn)。

以上特點(diǎn)使所提出模型相比STN能夠更明確地表達(dá)兩機(jī)器人之間的跨調(diào)度約束(如并發(fā)和避碰)，由于約束一致性檢驗(yàn)與時(shí)間變量的賦值分開進(jìn)行，使該模型易于在原有實(shí)例上不斷產(chǎn)生新實(shí)例，從而快速搜索不同的可行約束集，且時(shí)間變量的賦值過程簡(jiǎn)單。以上特性使該模型能夠配合3.3節(jié)提出的算法高效進(jìn)行多機(jī)器人的調(diào)度優(yōu)化。

3.3 結(jié)合插入啟發(fā)式的迭代局部搜索

在確定并發(fā)任務(wù)和干涉區(qū)的起止時(shí)間變量后，采用插入啟發(fā)式算法將各機(jī)器人的安全任務(wù)加入到調(diào)度計(jì)劃中，形成初始解。算法將遍歷問題中的所有安全任務(wù)，并計(jì)算每個(gè)任務(wù)插入到其所屬機(jī)器人的并發(fā)任務(wù)或干涉區(qū)前后造成的總時(shí)間代價(jià)增量ΔTCglb，選擇ΔTCglb最小的任務(wù)插入到對(duì)應(yīng)插入位置上，通過迭代上述過程即可將所有安全任務(wù)加入調(diào)度計(jì)劃。ΔTCglb定義為插入后調(diào)度計(jì)劃的總時(shí)間跨度與插入前的總時(shí)間跨度之差。以圖4為例，具體過程如下：

(1)遍歷A1中的安全任務(wù)并將其插入到調(diào)度計(jì)劃中的3個(gè)位置：P1之前、IZ1,2之前和之后，計(jì)算整個(gè)加工過程的總時(shí)間代價(jià)增量ΔTCglb。若在前方插入任務(wù)導(dǎo)致P1或IZ1,2的開始時(shí)間延遲，則需更新Gd中所有頂點(diǎn)的時(shí)間變量。

(2)以同樣方式處理A2中的安全任務(wù)，而后從中找出ΔTCglb最小值所對(duì)應(yīng)的任務(wù)和插入位置。當(dāng)ΔTCglb最小值非唯一時(shí)，則機(jī)器人路徑代價(jià)最小的插入方案為優(yōu)勝。

(3)執(zhí)行插入，并更新調(diào)度計(jì)劃S1、S2，以及檢查更新Gd中所有頂點(diǎn)的時(shí)間變量。

(4)重復(fù)(1)～(3)直至A1和A2中都沒有剩余安全任務(wù)。

在插入啟發(fā)式形成完整調(diào)度計(jì)劃后，為了充分搜索可行約束集E，達(dá)到優(yōu)化加工效率的目的，采取了迭代局部搜索(ILS)策略，通過驅(qū)動(dòng)約束模型Gd迭代優(yōu)化約束集E，找到使加工效率最優(yōu)的E的實(shí)例，繼而找到效率最優(yōu)解?；谀骋籊d實(shí)例的插入啟發(fā)式可以視為對(duì)問題解空間的一次局部搜索，ILS則通過對(duì)局部搜索產(chǎn)生的解施加擾動(dòng)，使其變?yōu)榻饪臻g鄰域上的某一點(diǎn)，從而幫助局部搜索過程跳出局部最優(yōu)并搜索解空間中新的區(qū)域，增加找到更優(yōu)解乃至最優(yōu)解的機(jī)會(huì)[21-22]。在本方法中，擾動(dòng)為對(duì)序列Q的隨機(jī)更改：通過隨機(jī)調(diào)轉(zhuǎn)Q局部隨機(jī)數(shù)量頂點(diǎn)的排序產(chǎn)生新的序列Q′，繼而可通過Q′產(chǎn)生新的Gd實(shí)例Gd′和新的約束集E′。在此基礎(chǔ)上重新執(zhí)行插入啟發(fā)式即可獲得問題的新解。ILS總是立即接受當(dāng)前最優(yōu)解，并在當(dāng)前最優(yōu)解上施加新的擾動(dòng)，直至迭代過程結(jié)束。本研究方法的總體流程圖如圖6所示，ILS過程啟動(dòng)后會(huì)不斷搜索新的時(shí)序約束模型實(shí)例，直至達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

4 仿真與實(shí)驗(yàn)分析

4.1 時(shí)序約束任務(wù)調(diào)度優(yōu)化仿真

4.1.1 仿真場(chǎng)景設(shè)計(jì)

4.1.2 多機(jī)器人任務(wù)分配

采用兩步式任務(wù)分配為3臺(tái)機(jī)器人分配任務(wù)集T，聚類初始分配與市場(chǎng)方法再分配的結(jié)果如表1所示。可見，再分配很好地平衡了機(jī)器人之間的工作量，使3臺(tái)機(jī)器人之間的最大工作量差距僅為2.7 min；此外，8組并發(fā)任務(wù)也完成了分配，其中r1與r2協(xié)同完成2組、r1與r3協(xié)同完成4組，r2與r3協(xié)同完成2組。

表1 加工任務(wù)集T分配結(jié)果

4.1.3 對(duì)照方法

目前工程應(yīng)用上采用一種貪心加插入啟發(fā)式的調(diào)度方法，分3個(gè)階段分別規(guī)劃并發(fā)任務(wù)、干涉區(qū)任務(wù)和安全任務(wù)的加工時(shí)序：

(1)首先使用貪心策略調(diào)度并發(fā)任務(wù)，根據(jù)最早開始的原則為多機(jī)器人指派第一組并發(fā)任務(wù)，且每當(dāng)出現(xiàn)兩臺(tái)機(jī)器人待機(jī)時(shí)都立即嘗試為其指派新的并發(fā)任務(wù)，直至全部并發(fā)任務(wù)加入調(diào)度計(jì)劃。

(2)采用插入啟發(fā)式策略，尋找使總加工時(shí)間增量ΔTCglb最小的干涉區(qū)及對(duì)應(yīng)插入位置，從而向調(diào)度計(jì)劃中增加干涉區(qū)任務(wù)，直至全部干涉區(qū)都插入。

(3)仍采用插入啟發(fā)式策略，尋找使總加工時(shí)間增量ΔTCglb最小的安全任務(wù)及對(duì)應(yīng)插入位置，直至3臺(tái)機(jī)器人的全部安全任務(wù)都插入到加工時(shí)序中。

以上策略的詳細(xì)規(guī)則設(shè)置如表2所示，確保該調(diào)度方法的行為較為合理高效。

表2 對(duì)照調(diào)度方法所采取策略的詳細(xì)設(shè)置

4.1.4 仿真結(jié)果與分析

以任務(wù)分配結(jié)果為輸入，采用本文提出的方法進(jìn)行調(diào)度優(yōu)化，工程應(yīng)用方法則作為對(duì)照，其中本文方法共搜索200次，結(jié)果分別如圖8和圖9所示。兩圖中紅藍(lán)灰三色條帶代表了并發(fā)任務(wù)、干涉區(qū)和安全任務(wù)的加工時(shí)序，條帶間的空隙則表示機(jī)器人出現(xiàn)了停頓。本文方法最終加工時(shí)間為251.5 min，最后完成加工的機(jī)器人為r1，其非加工時(shí)間為15.4 min；對(duì)照方法最終加工時(shí)間為295.4 min，最后完成加工的機(jī)器人為r2，非加工時(shí)間達(dá)到了57.5 min。相比對(duì)照方法，本文方法使加工時(shí)間縮短約14.9%。本文方法最終形成的加工調(diào)度中，機(jī)器人交替執(zhí)行并發(fā)任務(wù)和干涉區(qū)任務(wù)，且各機(jī)器人均沒有顯著的停頓時(shí)間；而對(duì)照方法通過貪心策略先行確定并發(fā)任務(wù)的加工時(shí)序，盡管并發(fā)任務(wù)的加工時(shí)序較為緊湊，但隨后的插入啟發(fā)式策略無法為干涉區(qū)任務(wù)找到緊湊的加工時(shí)序，導(dǎo)致位于中間位置、避碰問題最復(fù)雜的機(jī)器人r2出現(xiàn)了顯著的停頓時(shí)間，降低了整體效率。

為直觀分析加工調(diào)度的效率，此處借鑒文獻(xiàn)[23]，將加工調(diào)度的效率定義為任務(wù)分配后多機(jī)器人中出現(xiàn)的最大工作量與完成最后一個(gè)任務(wù)的機(jī)器人所用的總時(shí)間跨度之比，即

(10)

其中:i=1,2,…,k；當(dāng)機(jī)器人的加工調(diào)度中不存在任何停頓時(shí)，e=100%。由表1可知，3臺(tái)機(jī)器人中出現(xiàn)的最大工作量為r2的237.9 min，則本文方法與對(duì)照方法所產(chǎn)生加工調(diào)度的效率分別為94.6%和80.5%，本文方法帶來的調(diào)度效率提升為：(0.946-0.805)/0.805×100%=17.5%。由于加工調(diào)度的效率已接近95%，可知本文方法的尋優(yōu)性能較好，結(jié)果所剩優(yōu)化空間已較小。

由于本文所提出的調(diào)度優(yōu)化算法本質(zhì)上是一種啟發(fā)式算法，需要檢驗(yàn)其魯棒性，即是否總能在有限次迭代中穩(wěn)定地找到較優(yōu)解，以及在優(yōu)化問題的要素(如任務(wù)數(shù)量)發(fā)生變化時(shí)性能是否仍然穩(wěn)定。為此設(shè)置34和67兩種任務(wù)總數(shù)以及30%和50%兩種并發(fā)任務(wù)占比，共生成4組不同的隨機(jī)任務(wù)集，每組包含50個(gè)隨機(jī)實(shí)例，支架在艙體上的分布位置需隨機(jī)生成，加工時(shí)間在5～15 min之間隨機(jī)指定。在任務(wù)分配后，采用兩種方法分別計(jì)算全部200個(gè)任務(wù)集實(shí)例，其中本文方法的最大迭代次數(shù)仍設(shè)為200次；將4組規(guī)劃結(jié)果對(duì)應(yīng)的加工時(shí)間分別用箱線圖表示，結(jié)果如圖10所示。

箱線圖中箱體的橫線對(duì)應(yīng)數(shù)據(jù)的中位數(shù)和上下四分位數(shù)，因此箱體位置反映了數(shù)據(jù)的分布。從圖中可見，本文方法在不同條件下所產(chǎn)生的優(yōu)化結(jié)果總是優(yōu)于對(duì)照方法，且箱體更扁平，反映了算法尋優(yōu)的穩(wěn)定性和可靠性較好、受調(diào)度問題本身的影響更小。通過觀察還得出以下規(guī)律：

(1)在任務(wù)總數(shù)相同時(shí)，并發(fā)任務(wù)比例的增加使兩種方法產(chǎn)生的最終加工時(shí)間均增加。表明并發(fā)約束增多導(dǎo)致尋優(yōu)的困難性增加，但本文方法所產(chǎn)生的結(jié)果增幅相對(duì)更小。

(2)通過切分干涉區(qū)來降低時(shí)序優(yōu)化難度的手段在不同條件下均有一定效果，且對(duì)照方法的性能對(duì)是否切分干涉區(qū)更加敏感。

4.2 避碰可靠性實(shí)機(jī)驗(yàn)證

保證多機(jī)器人避碰安全是調(diào)度優(yōu)化方法的基本功能，為驗(yàn)證其可靠性，基于實(shí)驗(yàn)室內(nèi)艙體模擬件設(shè)計(jì)了一避碰問題較復(fù)雜的多機(jī)器人加工場(chǎng)景，并使用兩種不同的機(jī)器人試驗(yàn)平臺(tái)進(jìn)行了實(shí)機(jī)驗(yàn)證，如表3所示。表中的最大可達(dá)距離系機(jī)器人本體腕關(guān)節(jié)的最大可達(dá)距離，系對(duì)比機(jī)器人的規(guī)格差異，實(shí)驗(yàn)中機(jī)器人對(duì)任務(wù)的可達(dá)性并非基于此參數(shù)進(jìn)行判斷。

表3 試驗(yàn)平臺(tái)機(jī)器人規(guī)格

艙體模擬件模擬了直徑約2 m的大型艙體局部，寬2.73 m，高1.0 m，表面設(shè)置48個(gè)虛擬支架。實(shí)機(jī)驗(yàn)證平臺(tái)布局如圖11所示，AUBO-i5機(jī)器人位于中央，中線與模擬件中線對(duì)齊，兩臺(tái)KR60-3 HA機(jī)器人則對(duì)稱布置于AUBO機(jī)器人的兩側(cè)，將其按圖11由左到右分別命名為r0，r1和r2。該布局令3臺(tái)機(jī)器人的工作包絡(luò)相互重疊，3臺(tái)機(jī)器人可能同時(shí)發(fā)生沖突，增加了避碰問題的復(fù)雜性。該場(chǎng)景可模擬大型艙體制造中加工機(jī)器人與輔助機(jī)器人協(xié)同的情況，其中r1用于承擔(dān)輔助性任務(wù)，如搭載視覺跟蹤設(shè)備或夾爪進(jìn)行精度補(bǔ)償或支架零件裝調(diào)等任務(wù)。

3臺(tái)機(jī)器人由同一臺(tái)工控機(jī)控制，規(guī)劃結(jié)果對(duì)應(yīng)的運(yùn)動(dòng)指令由上位機(jī)生成并發(fā)送至機(jī)器人，與機(jī)器人控制器的通訊則通過TCP/IP經(jīng)由網(wǎng)絡(luò)交換機(jī)實(shí)現(xiàn)。實(shí)驗(yàn)中，末端之間的最小安全距離dr2r_min=0.52 m，r0和r2完成每個(gè)任務(wù)所需的時(shí)間設(shè)為1 min，而r1為2 min。實(shí)驗(yàn)前通過計(jì)算機(jī)器人工具坐標(biāo)系關(guān)于任務(wù)目標(biāo)位姿的運(yùn)動(dòng)學(xué)逆解來判斷機(jī)器人對(duì)各加工任務(wù)的可達(dá)性，從而建立各機(jī)器人的可達(dá)任務(wù)集Trch(ri)(i=1,2,3)，以便實(shí)施任務(wù)分配。r0，r1和r2的工具坐標(biāo)系均設(shè)在法蘭坐標(biāo)系沿自身X軸正方向平移0.3 m處。任務(wù)分配結(jié)果見表4，其中r1因可達(dá)性限制只能加工7個(gè)任務(wù)，該結(jié)果已最大限度地平衡了機(jī)器人工作量差距。

表4 實(shí)機(jī)驗(yàn)證機(jī)器人任務(wù)分配結(jié)果

本節(jié)實(shí)機(jī)驗(yàn)證中的3臺(tái)機(jī)器人彼此均可能發(fā)生碰撞，r0，r1和r2的干涉區(qū)寫作IZ0,(1,2)，IZ1,(0,2)和IZ2,(0,1)，表示其中的任務(wù)分別與兩個(gè)隊(duì)友的任務(wù)干涉(如圖12a左)。以上干涉區(qū)同樣采取切分策略來細(xì)分避碰所需的優(yōu)先約束，實(shí)施規(guī)則為：原干涉區(qū)中僅與特定隊(duì)友存在干涉的任務(wù)可構(gòu)成一個(gè)獨(dú)立的干涉區(qū)。具體結(jié)果如下：

切分后形成的6個(gè)干涉區(qū)及其在模擬件表面的分布情況如圖12所示，其中的白色區(qū)域表示r0和r2的安全任務(wù)所在的位置。

使用本文提出的算法對(duì)3臺(tái)機(jī)器人的干涉區(qū)和安全任務(wù)進(jìn)行時(shí)序規(guī)劃，經(jīng)過28次迭代后，調(diào)度計(jì)劃的效率已達(dá)到90%以上，遂停止迭代。最終確定的干涉區(qū)優(yōu)先約束集如圖12a右所示，具體加工時(shí)序則如圖13所示，圖中標(biāo)出了6個(gè)干涉區(qū)對(duì)應(yīng)的時(shí)序以及實(shí)現(xiàn)避碰的優(yōu)先約束；以上調(diào)度計(jì)劃預(yù)計(jì)所需加工時(shí)間為23.27 min，最后完成加工的機(jī)器人為r2。整個(gè)實(shí)機(jī)驗(yàn)證過程最終用時(shí)23.83 min，相比時(shí)序規(guī)劃預(yù)計(jì)的總時(shí)間略增加了33 s，其原因除機(jī)器人加減速過程使實(shí)際移動(dòng)速度并非規(guī)劃時(shí)的固定值外，還與機(jī)器人的加工時(shí)間波動(dòng)導(dǎo)致部分干涉區(qū)的完成時(shí)間滯后、增加了隊(duì)友停頓時(shí)間有關(guān)。在以上驗(yàn)證過程中以1 s為時(shí)間步長(zhǎng)采集3臺(tái)機(jī)器人末端執(zhí)行器TCP的空間位置，并計(jì)算兩兩之間出現(xiàn)的最小空間距離，結(jié)果如圖14所示，其中虛線代表dr2r_min的值(0.52 m)，可見r0，r1和r2在整個(gè)加工過程中都滿足了避碰要求，在約第12～14 min，r1和r2之間出現(xiàn)了全局最小距離0.61 m，其余時(shí)間中，3臺(tái)機(jī)器人的末端TCP之間的距離均顯著高于dr2r_min，證明了機(jī)器人加工全過程的操作安全。在約21分20秒后僅剩r2仍在運(yùn)行，而r0、r1已返回HOME姿態(tài)，因此不再計(jì)算r2與r0和r1的距離。

以上實(shí)驗(yàn)證明了本文的調(diào)度優(yōu)化模型和算法在處理機(jī)器人避碰問題上的可靠性，且當(dāng)機(jī)器人的加工時(shí)間相對(duì)規(guī)劃時(shí)間出現(xiàn)波動(dòng)時(shí)仍能夠保證實(shí)現(xiàn)避碰，表明本方法有一定的魯棒性，具備工程應(yīng)用條件。此外，基于干涉區(qū)進(jìn)行的調(diào)度規(guī)劃使機(jī)器人在多數(shù)運(yùn)動(dòng)過程中都保持較充足的距離，有助于減少離線編程時(shí)為兩個(gè)安全間距偏低的機(jī)器人進(jìn)行精細(xì)軌跡規(guī)劃的工作量，提升了編程效率。

5 結(jié)束語

針對(duì)多機(jī)器人協(xié)同制造系統(tǒng)處理航空航天復(fù)雜產(chǎn)品時(shí)的多機(jī)器人避碰問題、加工任務(wù)時(shí)序約束，以及加工效率優(yōu)化問題，本文提出一種加工任務(wù)時(shí)序約束的建模方法和調(diào)度優(yōu)化算法。首先采用帶雙向邊的有向圖建模和表達(dá)任務(wù)集中的干涉任務(wù)、并發(fā)任務(wù)以及對(duì)應(yīng)的優(yōu)先和并發(fā)約束，繼而通過有向圖的閉環(huán)檢測(cè)實(shí)現(xiàn)了時(shí)序約束一致性檢驗(yàn)，閉環(huán)檢測(cè)則通過改造深度優(yōu)先搜索算法得以實(shí)現(xiàn)；提出結(jié)合插入啟發(fā)式的迭代局部搜索算法實(shí)現(xiàn)機(jī)器人調(diào)度優(yōu)化，其中迭代局部搜索算法用以驅(qū)動(dòng)時(shí)序約束有向圖模型不斷搜索新的約束集，插入啟發(fā)式則用以在給定約束集下快速構(gòu)建完整的機(jī)器人調(diào)度計(jì)劃。仿真結(jié)果證明所提出的模型和算法相比目前工程應(yīng)用的方法顯著提升了加工效率，同時(shí)結(jié)果滿足了多機(jī)器人避碰要求和加工任務(wù)的并發(fā)約束；算法魯棒性測(cè)試表明本文提出的算法在任務(wù)規(guī)模和時(shí)序約束復(fù)雜程度發(fā)生變化時(shí)仍能穩(wěn)定地找到機(jī)器人調(diào)度計(jì)劃的較優(yōu)解。此外，在實(shí)驗(yàn)室條件下進(jìn)行了三機(jī)器人調(diào)度避碰實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文所提出方法能可靠地處理機(jī)器人避碰問題，并對(duì)加工時(shí)間的波動(dòng)具有一定魯棒性。

在本文工作基礎(chǔ)上，未來應(yīng)進(jìn)一步考慮機(jī)器人隨機(jī)故障/換刀、特征加工余量在線檢測(cè)等制造現(xiàn)場(chǎng)復(fù)雜擾動(dòng)和不確定因素，研究能夠處理不確定性和隨機(jī)事件的時(shí)序規(guī)劃算法和模型，以便形成在線決策和實(shí)時(shí)優(yōu)化能力，進(jìn)一步提升多機(jī)器人在復(fù)雜制造任務(wù)中的智能化水平和魯棒性。