程曉明，劉銀華，趙文政

(上海理工大學 機械工程學院，上海 200093)

0 引言

大型三維結(jié)構(gòu)的質(zhì)量檢測是實現(xiàn)其制造精度評價、監(jiān)控與質(zhì)量診斷的基礎(chǔ)。汽車車身、航空航天部件、高速列車車體等大型薄板、薄壁件具有外形尺寸大、曲面結(jié)構(gòu)復雜、待測特征多且檢測精度較高等特點。近年來，非接觸光學檢測精度與效率的提升使得大型三維結(jié)構(gòu)的覆蓋測量獲得推廣應用。因此，面向質(zhì)量檢測的覆蓋路徑規(guī)劃(Coverage Path Planning, CPP)研究也獲得關(guān)注[1-3]。

覆蓋路徑規(guī)劃主要包括集合覆蓋問題(Set Covering Problem, SCP)與路徑規(guī)劃問題(Travelling Salesman Problem, TSP)兩個子問題。傳統(tǒng)研究中一般對上述問題進行獨立求解[4]，但受到視點采樣與規(guī)劃路徑非最優(yōu)等限制，學者們逐漸嘗試將SCP與TSP同時解決，如卡內(nèi)基梅隆大學JING等[5]創(chuàng)新性地提出SCP-TSP集成模型以求解全局最優(yōu)路徑結(jié)果。

然而，對于車身等大型三維結(jié)構(gòu)來說，往往需要采用多機器人或冗余自由度機器人系統(tǒng)進行測量，這也引出了多機器人CPP問題，即MCPP(multi-robots CPP)問題。多機覆蓋路徑規(guī)劃過程一般包含視點的覆蓋采樣、多機任務(wù)分配以及單機路徑規(guī)劃等子問題。MCPP研究主要集中在二維場景下清潔與修剪、三維環(huán)境下模型重構(gòu)、工業(yè)測量與遠程救援等[6-9]。其中多機器人任務(wù)分配問題為典型的混合整數(shù)線性規(guī)劃問題，如ELANGO等[10]基于最小距離利用K-means對任務(wù)進行聚類，然后計算每個機器人與聚類群所組成集合的成本，最終根據(jù)拍賣算法進行任務(wù)分配。JANATI等[11]采用聚類算法將任務(wù)集劃分和機器人相同的數(shù)量，然后利用線性分配法實現(xiàn)任務(wù)集分配。SONG等[12]提出一種新的多任務(wù)多群優(yōu)化算法來解決多層任務(wù)分配問題。ZITOUNI等[13]和AYARI等[14]提出螢火蟲算法、動態(tài)分布式例子全優(yōu)化算法的全局分配和聚類算法實現(xiàn)多機任務(wù)分配。進一步，JING等[15]提出有偏隨機密鑰遺傳算法(Biased Random Key Genetic Algorithm, BRKGA)的多機三維模型重構(gòu)的規(guī)劃方法。

GAO等[16]利用基于機器人初始位置劃分區(qū)域(Divide Areas based on Robots initials Positions, DARP)算法將區(qū)域劃分為多個等面積的子區(qū)域，從而將MCPP問題轉(zhuǎn)化為多個CPP問題，通過構(gòu)造每個子區(qū)域的理想生成樹獲得優(yōu)化覆蓋路徑。肖玉婷等[17]基于分塊優(yōu)化的思想，提出一種可應用于大規(guī)模復雜環(huán)境的多無人機覆蓋路徑規(guī)劃方法，該方法兼顧了環(huán)境的差異性和覆蓋的完整性。

上述MCPP主要通過無人機、無人地面車等尋找覆蓋整個目標表面的無碰撞路徑，多應用在模型重建和測繪監(jiān)視等領(lǐng)域，而鮮有提出關(guān)于多工業(yè)機器人的覆蓋路徑優(yōu)化問題的解決辦法。同時，與多無人機等覆蓋路徑規(guī)劃問題不同，面向質(zhì)量檢測的多機器人覆蓋規(guī)劃問題受到機械臂運動學可達性、多機運行一致性以及光學入射角度等因素的特殊性要求，導致傳統(tǒng)MCPP方法的適用性不足，檢測規(guī)劃結(jié)果難以滿足要求。

因此，本文提出一種多機器人覆蓋路徑規(guī)劃新方法，旨在構(gòu)建檢測任務(wù)分配與機器人路徑規(guī)劃問題的集成規(guī)劃模型，并提出基于改進的自適應遺傳算法對模型進行優(yōu)化求解，獲得大型產(chǎn)品結(jié)構(gòu)全覆蓋測量要求下機器人運動時間的近最優(yōu)規(guī)劃結(jié)果。進一步，通過整車的仿真案例與對比分析，驗證所提方法的可行性及有效性。

1 多機器人覆蓋路徑規(guī)劃的優(yōu)化模型構(gòu)建

大型三維結(jié)構(gòu)產(chǎn)品的制造精度直接影響后續(xù)裝配過程以及產(chǎn)品使用性能。因此，必須對產(chǎn)品結(jié)構(gòu)的尺寸、位置及表面質(zhì)量進行質(zhì)量檢測，以評估其是否滿足公差要求。針對大型結(jié)構(gòu)的質(zhì)量檢測，需要對產(chǎn)品上布置的面點、圓孔、棱邊點、槽孔以及螺紋孔等特征進行全覆蓋測量。如圖1所示為搭載結(jié)構(gòu)光測頭的多機器人覆蓋檢測工位示意圖。

由圖1可知，光學測頭被搭載在工業(yè)機器人末端，在機器人可達的視點位置對產(chǎn)品上待測特征進行覆蓋測量。測頭的可視性覆蓋區(qū)域主要由視場(Field of View, FOV)和景深(Field of Depth, FOD)兩個參數(shù)決定。多機器人覆蓋路徑規(guī)劃的目的是通過優(yōu)化的視點采樣、任務(wù)分配以及多機的路徑規(guī)劃以獲得理想的覆蓋測量規(guī)劃結(jié)果。為實現(xiàn)檢測特征的覆蓋檢測，需開展以下子問題進行求解：①根據(jù)待測特征生成冗余視點集；②面向結(jié)構(gòu)全覆蓋的視點優(yōu)化采樣；③全覆蓋視點集的多機器人任務(wù)分配；④各機器人任務(wù)集的檢測次序與路徑規(guī)劃。

傳統(tǒng)方法往往針對上述子問題進行單獨處理，雖然能夠降低問題復雜度，但同時會使得可行解空間遠小于真實情況，導致最終規(guī)劃方案非優(yōu)。而若將上述問題集成求解雖在理論上能夠找到全局最優(yōu)解，但往往導致高計算復雜度下的求解效率問題。

本文綜合考慮全局最優(yōu)解和計算復雜度之間的協(xié)調(diào)關(guān)系，在全覆蓋視點采樣基礎(chǔ)上[18]，創(chuàng)新性地將多機任務(wù)分配與路徑規(guī)劃子問題進行集成建模并開展優(yōu)化求解，以實現(xiàn)結(jié)構(gòu)光檢測路徑的綜合尋優(yōu)。結(jié)合以上問題描述，多機器人任務(wù)分配模型可表達為：

(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的視點數(shù)；G為距離矩陣；Ve為機器人末端平均移動速度；nr為機器人總數(shù)；X(j,∶)為X方案中機器人j任務(wù)集；Vres為全覆蓋視點集；nt為機器人可達信息；nt(k,∶)為機器人k可達視點集。

2 多機器人任務(wù)分配與路徑規(guī)劃的綜合尋優(yōu)

2.1 全覆蓋視點集采樣

本文首先基于隨機采樣生成初始視點集V，根據(jù)視點的結(jié)構(gòu)光參數(shù)計算可視性矩陣A。進一步，基于可視性矩陣從初始冗余視點集中提取全覆蓋子集，以保證每個待測特征至少被覆蓋一次，稱該子集為全覆蓋視點集。構(gòu)建的優(yōu)化模型為：

A·X≥1。

(3)

式中：xi表示初始視點集中的第i個視點，xi=1與xi=0分別表示該視點是否被采樣；A為n×n的可視性矩陣；A·X≥1表示單個待測特征至少被覆蓋一次。該問題為典型的集合覆蓋問題，即在保證對三維結(jié)構(gòu)待測特征全覆蓋測量基礎(chǔ)上使獲得視點集數(shù)目最小化?，F(xiàn)有多種啟發(fā)式算法可用于求解SCP問題，本文采用貪心算法對全覆蓋視點集進行求解，具體算法流程如算法1所示。

算法1貪心算法求解全覆蓋視點集。

輸入：待測特征集N；冗余視點集V；可視性矩陣A；輸出：全覆蓋視點集Vres;全覆蓋視點集視點個數(shù)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中的相關(guān)函數(shù)及變量名解釋如下:maxCover()為選擇當前冗余視點集中覆蓋待測特征最多的視點，append()將所選擇的視點添加到全覆蓋視點集中，delete()為從冗余視點集中將選擇過的視點刪除，count()為計算當前待測特征被覆蓋次數(shù)，sizeof()為計算當前全覆蓋視點集中的視點數(shù)，v為單個視點，ni為單個待測特征。

2.2 基于改進遺傳算法的綜合優(yōu)化求解

路徑規(guī)劃問題的求解主要有遺傳算法[19]、蟻群算法[20]等。直接采用上述算法無法使每一次迭代過程中產(chǎn)生的解方案均滿足機器人可達性約束，因此，基于多機器人的視點分配與路徑規(guī)劃的集成模型，本文提出改進的遺傳算法，以實現(xiàn)多機器人視點分配與運動路徑的綜合求解。

傳統(tǒng)遺傳算法通過適應度函數(shù)反復篩選每一代種群較優(yōu)解方案，直至迭代出滿意解。由于存在結(jié)構(gòu)全覆蓋和機器人可達性約束，傳統(tǒng)遺傳算法在迭代過程中往往產(chǎn)生過大量無效解，浪費了計算機算力，且易陷入死循環(huán)。因此，本文在遺傳算法基礎(chǔ)上，提出新的編碼與種群初始化策略，并針對傳統(tǒng)交叉變異算子易引起新解失效問題，提出新式變異算子使得初始解方案以及后續(xù)迭代過程中產(chǎn)生的每一種新解都能夠同時滿足全覆蓋要求以及機器人可達性約束。此外，得益于提出的嵌入式優(yōu)化策略，使得改進的遺傳算法具有更快的收斂速度。

為合理分配各機器人任務(wù)集以及路徑順序，需首先確定全覆蓋視點集中各視點之間的距離，以及各機器人與視點之間的距離。本文將兩部分距離計算結(jié)果合并建立統(tǒng)一的距離矩陣G，其形式如圖2所示。其中：nres為全覆蓋集視點中視點數(shù)目，nr為當前工位中機器人數(shù)目。距離矩陣分為4部分，分別記錄了視點間距離(①部分)，視點與機器人間距離(②、③部分)以及機器人間距離(④部分)。另外，將矩陣中機器人到視點間不可達位置用inf來表示。

(1)編碼與種群初始化

相比于傳統(tǒng)的染色體編碼結(jié)構(gòu)，本文構(gòu)建了一個nr×nres的矩陣ind來儲存染色體，其中:nr為機器人數(shù)，nres為全覆蓋視點集中視點數(shù)，該種編碼形式具有易于區(qū)分各機器人任務(wù)集的好處，為后續(xù)算法迭代中處理可達性約束問題提供了便利，后文會詳細論述該部分內(nèi)容。所構(gòu)建的矩陣中其行號表示機器人代號，每行非零元素表示該行指代機器人所分配的有序視點集。如矩陣中第2行[v14,v7,v5,v25,v63,v42,0…0]表示機器人2在當前方案中分配了5個視點，且其訪問順序依次為v14、v7、v5、v63、v42。需指出，由于各機器人分配視點數(shù)并非絕對一致，故用0元素補充至nres以構(gòu)成矩陣形式。具體的，矩陣結(jié)構(gòu)如圖3所示。

另外，對于種群初始化，本方法采取的策略為：優(yōu)先將單機器人可達視點分配至各機器人；對于多機器人可達視點該如何分配，基于機器人檢測過程中旅行成本和拍攝成本的協(xié)調(diào)關(guān)系，本方法提出兩個策略：“就近原則”與“就少原則”。具體的，對于單個待分配視點，前者將該視點分配至距離其最近的機器人，而后者將該視點分配至當前任務(wù)集中視點數(shù)最少的機器人。

首先，由兩種策略確定兩個可選機器人方案，分別計算兩機器人與當前視點之間距離的差值以及各自當前任務(wù)集中視點數(shù)的差值，取視點數(shù)差值與路徑差值之間的比值與選擇系數(shù)(PR)比較，若比值大于PR，則采取“就少原則”;反之采取“就近原則”。若設(shè)PR=0.1，意味著若視點數(shù)差值超過距離差值的十分之一，則采取“就少原則”；反之采取“就近原則”。其具體過程如算法2所示。

算法2Rob_select。

輸入：當前分配方案ind；選擇系數(shù)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中相關(guān)函數(shù)及變量名解釋如下：findUpto()為尋找可達當前視點的機器人集，findLess()為尋找可達機器人中當前分配視點數(shù)最少的，findNear()為尋找可達機器人中距離該視點最近的，countVP()為計算兩機器人分配視點數(shù)差值，countDist()為計算兩機器人與該視點距離差值，Nmultirob為可由多機器人覆蓋檢測的特征集，ni為單個待測特征。

在所有視點都分配完成之后，將各機器人的任務(wù)集中的試點順序隨機打亂，使初始種群更具隨機性,以使得后續(xù)算法迭代過程中產(chǎn)生更多解。需補充的是，算法2的思想除了用于種群初始化之外，還被應用于后續(xù)的交叉和變異算子中。

(2)種群適應度評價函數(shù)

由于多機器人工位存在生產(chǎn)節(jié)拍的限制，要求多機器人檢測系統(tǒng)在檢測周期T內(nèi)完成檢測任務(wù)，即要求耗費時間最長的機器人完成檢測任務(wù)的時間不得超過T。在檢測過程中，花費時間的成本由機器人運行的時間成本和光學測頭在視點處的拍攝成本兩部分組成，本文構(gòu)建的種群適應度評價函數(shù)可表達為1/Q。其中，Q表示給定分配方案下工位內(nèi)檢測總時間，即耗時最長機器人的運行時間成本與光學測頭拍攝時間成本之和，

(4)

其中各項參數(shù)含義同式(1)。Q越小則該個體的適應度越高，算法的目標即求解出Q最小的分配方案，并要求Q不大于給定的檢測周期，即Q≤T。

基于上述分析，種群適應度求解策略為：首先，計算個體中各機器人檢測時間，以耗時最長機器人的檢測時間的倒數(shù)作為該個體的適應度，再比較種群所有個體適應度，將最高適應度作為當前種群適應度，并將該個體視為該種群的最優(yōu)個體。

(3)選擇、交叉、變異算子的設(shè)計

選擇算子采用輪盤賭選擇法，其核心思想為個體被選中的概率與其適應度成正比。在該方法中，個體k被選中的概率為：

(5)

其中：Fk為個體k的適應度；NUMPOP為種群中個體數(shù)。通過該算子使適應度較高的個體有較大的機會被選擇，從而使得種群向好的方向進化。

在傳統(tǒng)交叉算子過程中，會因父代與母代染色體(各機器人任務(wù)集)交叉而出現(xiàn)某些視點被重復分配或遺漏的情況。本文在傳統(tǒng)交叉方案的基礎(chǔ)上添加后處理措施，使得每次交叉結(jié)果能夠滿足可達性約束并使整體方案更加優(yōu)化，具體策略如下：

步驟1對于交叉后染色體中重復出現(xiàn)的視點，選擇將原屬于母代中的該部分視點刪除，其具體過程如算法3所示。算法3中:vi為單個視點，count()為計算當前染色體中視點vi個數(shù)，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對于因交叉操作而丟失的視點，令其重新添加至染色體，從而保證全覆蓋檢測。首先，將當前視點分配至合理機器人任務(wù)集(算法2)。然后，為使該視點放入當前機器人有序任務(wù)集后所構(gòu)成的新路徑耗時最短，將比較當前視點位于所有可行位置后的新路徑耗時，并選取耗時最短的位置作為放置點。具體過程如算法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中相關(guān)函數(shù)及變量名解釋如下：Extract()為提取當前染色體中該機器人路徑(機器人選擇方法見算法2:Rob_select)，findLocation()為尋找當前路徑所有可行插入位置，countTime()為計算視點位于當前插入位置整條路徑耗時，chooseMin()為選擇耗時最短的位置，insert()為將當前視點插入選擇的路徑位置，putBack()為將當前路徑放回至原染色體相應位置，vi為單個視點。

至于變異算子，采取的策略為：在滿足變異概率的情況下，從全覆蓋視點集中隨機選取一個視點vr，找到該視點位于當前染色體中的位置并刪除，并利用算法2與算法4將該視點補充回染色體以得到變異后的染色體。由前文對算法2與算法4的介紹，可知變異產(chǎn)生的新解依然滿足全覆蓋要求以及可達性約束并且在一定程度上優(yōu)化了變異前的方案。變異過程如圖4所示。

基于上述算法設(shè)計，保證了產(chǎn)生所有解方案均滿足可達性約束，實現(xiàn)了對全覆蓋視點集的任務(wù)分配以及路徑規(guī)劃的綜合優(yōu)化求解，同時，得益于算法2與算法4在每一步迭代過程中的擇優(yōu)策略，使得本方法具有高速收斂性。

3 案例分析

為驗證本文方法的可行性，結(jié)合某車身大型曲面結(jié)構(gòu)進行案例驗證。該車身表面結(jié)構(gòu)布置待測特征共計1 200余個，如圖5所示，包括面點、圓孔、棱邊點以及槽孔等，對應待測特征的位置及矢量方向在圖中分別用紅點與黑色箭頭表示。在MATLAB軟件機器人工具箱搭建4機器人視覺檢測平臺對提出的覆蓋路徑規(guī)劃方法進行仿真驗證，采用的機器人型號為FANUC 2000iB-125L，各機器人搭載光學測頭的參數(shù)如表1所示。同時，鑒于未檢索到多工業(yè)機器人覆蓋路徑規(guī)劃的相關(guān)文獻，故通過與卡內(nèi)基梅隆大學JING等[15]提出的多無人機覆蓋路徑規(guī)劃算法對比分析，結(jié)合視點分配數(shù)目、測量時間等指標對本文方法進行有效性驗證。

表1 機器人搭載的光學測頭參數(shù)

根據(jù)上述車身待測特征生成初始視點集[18],并基于貪心算法獲得全覆蓋條件下視點集Vres，包含82個視點。如圖6所示為視點處光學測頭的位姿示意圖，其中紅點表示視點位置，箭頭表示視點處結(jié)構(gòu)光入射方向。

采用本文提出改進的遺傳算法對以上獲取的全覆蓋視點集進行多機器人任務(wù)分配及路徑規(guī)劃綜合尋優(yōu)求解，算法中涉及的參數(shù)如表2所示。

表2 算法參數(shù)

設(shè)選擇系數(shù)PR=0.005，機器人末端平均移動速度Ve=600 mm/s。基于本文提出算法的規(guī)劃結(jié)果如圖7所示，其中R1～R4的視點分配數(shù)目分別為20，20，22，20，各機器人對應檢測時間分別為27.20 s，27.19 s，27.01 s和25.69 s。如圖8所示為對應分配方案下多機器人中最大運行時間隨迭代次數(shù)的收斂情況。

進一步，為驗證所提出方法的有效性，本文通過隨機仿真實驗對本文方法與文獻[15]方法進行對比分析。對比指標包括工位內(nèi)測量周期(max{ti})、視點采樣數(shù)目極差值(Δt)、多機檢測時間極差值(Δn)，如圖9所示為兩種方法連續(xù)60次的隨機仿真規(guī)劃結(jié)果對比。

通過對實驗數(shù)據(jù)分析，得到兩種方法在max{ti}、Δt以及Δn三個評價指標的平均值如圖10所示。由圖10可知，所提方法將檢測工位內(nèi)機器人最大運行時間平均下降31.56%，分配至各機器人視點數(shù)極差降低20%，各機器人運行時間極差值降低13.13%?？梢?，本文方法能夠有效提升車身等大型結(jié)構(gòu)的光學檢測效率，也為其他大型三維結(jié)構(gòu)的全覆蓋檢測規(guī)劃提供了理論依據(jù)。

4 結(jié)束語

本文針對大型三維結(jié)構(gòu)的覆蓋檢測問題，提出了一種新的多機器人結(jié)構(gòu)光覆蓋路徑規(guī)劃方法，包括全覆蓋視點集提取、多機器人任務(wù)分配和路徑規(guī)劃的綜合尋優(yōu)等流程。首先，通過貪心算法獲得全覆蓋視點集，在待測特征全覆蓋條件下最小化視點數(shù)目；進一步，為解決多機任務(wù)分配與路徑規(guī)劃問題的綜合尋優(yōu)問題，提出了改進遺傳算法實現(xiàn)機器人可達性約束下的高效運動規(guī)劃與路徑優(yōu)化。最后，通過案例分析，驗證了本文方法的可行性及有效性。

此外，本文是首次針對多機器人覆蓋路徑規(guī)劃新問題開展研究，尚未考慮多機碰撞與避障等問題，未來將在本文集成的MCPP模型中考慮多機協(xié)同與避障問題，進一步提升所提方法的工程適用性。