謝必成，張小俊

河北工業(yè)大學(xué) 機(jī)械工程學(xué)院，天津 300401

隨著智能機(jī)器人技術(shù)的不斷發(fā)展，全覆蓋路徑規(guī)劃（complete coverage path planning，CCPP）技術(shù)已經(jīng)成為智能機(jī)器人領(lǐng)域的關(guān)鍵技術(shù)。近些年來由于其在軍事[1]、農(nóng)業(yè)[2]、搜救[3]、工業(yè)[4]、商業(yè)[5]和民用[6]等領(lǐng)域的廣泛應(yīng)用，進(jìn)而得到越來越多的學(xué)者的關(guān)注和研究。對于工作效率更高的多機(jī)器人全覆蓋路徑規(guī)劃（multirobot complete coverage path planning，MCCPP）的研究也已經(jīng)得到學(xué)者們的廣泛關(guān)注[7]。目前對MCCPP 的研究也大多是在平面環(huán)境下進(jìn)行的，而對于石油儲罐檢測、船舶噴漆與除銹以及大型玻璃外表面清潔等工作環(huán)境更為復(fù)雜和危險的立面維護(hù)作業(yè)MCCPP的研究便更有其特定的研究價值。

目前，路徑規(guī)劃主要分為兩大類：一類是在多個固定點(diǎn)之間尋找最短無碰撞路徑的路徑規(guī)劃方法[8-10]；另一類是在除不可行域以外的任務(wù)空間里尋找完全遍歷的最大覆蓋、最小長度的路徑規(guī)劃方法[11-12]。

然而，對于第一類路徑規(guī)劃方法一般歸結(jié)為對旅行商問題（travelling salesman problem，TSP）的解決，TSP是確定對若干個點(diǎn)無重復(fù)訪問順序的典型NP-hard 問題，即從任一點(diǎn)出發(fā)并回到這一點(diǎn)，以歐幾里德距離作為路徑長度的度量方法尋找最短路徑，然而多旅行商問題（multiple travelling salesman problem，MTSP）是經(jīng)典TSP 的一種泛化[13]，即同時解決多個TSP。而對于第二類問題的解決，MCCPP 是一種工作效率比較高的解決辦法，可以看作是MTSP與覆蓋路徑規(guī)劃（coverage path planning，CPP）的組合。目前MCCPP 可以大致分為以下幾種：聚類法，如Tang 等人[14]采用改進(jìn)的k-means 聚類方法對預(yù)先部署的傳感器點(diǎn)進(jìn)行分類，引入反饋機(jī)制來平衡每條路由的長度，最后通過求解TSP得到每個機(jī)器人的封閉路徑來實(shí)現(xiàn)MCCPP，由于傳感器點(diǎn)布置具有隨機(jī)性，所以這種方法對于立面維護(hù)作業(yè)而言主要的局限性是路徑重復(fù)率較高，無法充分考慮立面維護(hù)作業(yè)機(jī)器人起點(diǎn)和終點(diǎn)位置特點(diǎn)對覆蓋工作的影響；柵格地圖法，如Gao等人[15]利用基于機(jī)器人特定初始位置劃分區(qū)域的算法將區(qū)域劃分為多個相等的子區(qū)域，然后對各子區(qū)域之間交換特定的端點(diǎn)節(jié)點(diǎn)得到理想生成樹從而實(shí)現(xiàn)MCCPP，由于生成樹本身具有的柵格性，所以這種方法對于立面維護(hù)作業(yè)而言主要的局限性是對復(fù)雜環(huán)境和多工藝過程工作變現(xiàn)較差，同時不方便對感興趣權(quán)重的設(shè)置；幾何圖法，如Nair 等人[16]使用基于機(jī)器人特定的初始位置并結(jié)合測地線-曼哈頓Voronoi 分區(qū)方法對任務(wù)空間劃分，然后使用傳統(tǒng)的Boustrophedon 和回溯式覆蓋方法對每個區(qū)域覆蓋來實(shí)現(xiàn)MCCPP，由于這種方法對機(jī)器人的初始位置具有較大的依賴性，所以這種方法主要局限性是不能充分考慮立面維護(hù)作業(yè)機(jī)器人起點(diǎn)位置和終點(diǎn)位置具有邊緣性的特點(diǎn)；仿生法，如阮貴航等人[17]提出了一種基于滾動優(yōu)化和分散捕食者獵物模型的多機(jī)器人全覆蓋路徑規(guī)劃算法，構(gòu)建分散捕食者獵物模型，同時引入滾動優(yōu)化方法，避免機(jī)器人陷入局部最優(yōu)，最終實(shí)現(xiàn)MCCPP，這種方法的局限性主要表現(xiàn)在對多機(jī)器人工作均衡性無法保證，以及不能很好地適應(yīng)復(fù)雜障礙物環(huán)境。

本文主要針對以上MCCPP方法在立面維護(hù)作業(yè)場景下存在的局限性，提出了使用BCD[18]（boustrophedon cellular decomposition）將任務(wù)空間分解成若干個Cell，然后基于免疫遺傳算法對MCCPP問題求解。該方法一方面是要解決每個Cell的CPP 問題，另一方面還要解決對若干個Cell的訪問順序的MTSP問題，即在確定每一個Cell的路徑入口點(diǎn)和出口點(diǎn)組合的同時還要確定對所有Cell的訪問順序。該方法主要完成目標(biāo)是：結(jié)合立面維護(hù)作業(yè)工藝和環(huán)境特征，解決任務(wù)空間邊緣任意起始點(diǎn)和終點(diǎn)的MTSP-CPP 問題。在最大程度地均衡每個機(jī)器覆蓋任務(wù)的前提下，實(shí)現(xiàn)工作時間最短以及總工作量最小的多求解目標(biāo)，以便充分發(fā)揮立面作業(yè)MCCPP的優(yōu)勢。

1 前提與假設(shè)

在開始問題研究之前，需要聲明幾點(diǎn)前提條件和幾點(diǎn)假設(shè)。

首先，本文提出幾點(diǎn)前提：

（1）本文所使用的地圖是二維平面的先驗(yàn)地圖，所以對如何構(gòu)建地圖不做討論，只對覆蓋方法的可行性進(jìn)行驗(yàn)證。

（2）本文所使用的地圖對不可行域已經(jīng)進(jìn)行了大小為機(jī)器人半徑R的膨脹處理（覆蓋時不考慮機(jī)器人與不可行域重合的問題），同時認(rèn)為機(jī)器人不可跨越不可行域。

其次，本文提出幾點(diǎn)假設(shè)：

（1）假設(shè)所使用的機(jī)器人具有無限的續(xù)航能力。

為了研究跟專注于全覆蓋路徑規(guī)劃算法的研究，假設(shè)機(jī)器人擁有彼此防撞機(jī)制。

（2）假設(shè)每一個機(jī)器人為一個質(zhì)點(diǎn)，其單位覆蓋范圍為是一個以質(zhì)點(diǎn)為中心、半徑為R的圓形。

忽略機(jī)器人轉(zhuǎn)彎運(yùn)動和直線運(yùn)動的差異性，即不考慮機(jī)器人轉(zhuǎn)彎運(yùn)動的時間和能量損失。

2 任務(wù)空間分解與覆蓋路徑分解

本文將采用文獻(xiàn)[18]中提到的BCD 方法對任務(wù)空間進(jìn)行分解。同時本文將使用文獻(xiàn)[19]中提到的Cell內(nèi)部遍歷路徑模型與Cell間過渡路徑模型，目的在于將多機(jī)器人立面維護(hù)作業(yè)全覆蓋問題的模型進(jìn)行簡化。在此，需要對本文所使用的BCD 方法和下文將要使用的路徑模型做出一定的解釋。與傳統(tǒng)的BCD方法中依靠障礙物分解方法相比，本文將“障礙物”這一概念引申為“不可行域”，設(shè)置不可行域的目的是：除了簡單的障礙物區(qū)域不可到達(dá)以外，由于立面環(huán)境下存在不同材質(zhì)或者裝飾物的原因而被語義識別為具有保護(hù)性質(zhì)的不可行域。例如噴漆與除銹混合工藝過程無法同時空進(jìn)行[20]，所以出于對上一級工藝成果的保護(hù)而被識別為不可行域。為了方便工藝調(diào)度以及為不同作業(yè)區(qū)域分配不同的時間權(quán)重，而將任務(wù)空間劃分為若干個Cell。為了最大程度均衡每個機(jī)器人的覆蓋任務(wù)，同時保證機(jī)器人起點(diǎn)與終點(diǎn)位置選擇的靈活性，進(jìn)而選用了下文介紹的Cell內(nèi)部路徑覆蓋模型和Cell間過渡路徑模型?；谝陨厦枋?，不難看出不可行區(qū)域的形狀和位置具有任意性，遍歷路徑應(yīng)具有靈活性，所以作者采用BCD分解方法分解任務(wù)空間，并使用下文中所介紹的路徑模型對問題模型進(jìn)行簡化。

2.1 任務(wù)空間分解

BCD 是依據(jù)不可行域的分布將任務(wù)空間分解成若干個Cell，然后機(jī)器人采用割草式往復(fù)運(yùn)動對每一個Cell實(shí)現(xiàn)覆蓋。分解過程中將既得的二值化不可行域地圖視為一系列切片，所以為了方便算法實(shí)現(xiàn)，作者在設(shè)置中認(rèn)為一個1 像素寬的垂直地圖條為一個切片。這些切片或不被不可行域分割，或被一個乃至多個不可行域區(qū)域分割成非重疊的自由空間。約定將每一個切片自由空間數(shù)目記作當(dāng)前切片的連通性計數(shù)。在算法實(shí)現(xiàn)方面，在沿著水平方向逐一掃描每一個切片的同時計算每一個切片的連通性。切片的連通性將會在臨界點(diǎn)處發(fā)生變化。每當(dāng)連通性增加，則觸發(fā)一個IN事件，封閉當(dāng)前Cell，并開啟兩個新的Cell。若遇到連通性降低，則觸發(fā)一個OUT 事件，當(dāng)前的兩個Cell封閉，并開啟一個新的Cell。據(jù)此，完成整個人空間的分解。如圖1所示為簡單情況下分解原理圖。

圖1 地圖分解原理Fig.1 Principle of map decomposition

2.2 覆蓋路徑分解

在任務(wù)空間通過BCD分解為N個Cell之后，分解得到的每一個Cell將被標(biāo)記一個id（Cell的編號，記作Cellid）。每個機(jī)器人要完成的覆蓋的任務(wù)由一組id序列組成，所有機(jī)器人覆蓋任務(wù)共同排列起來組成一個長度為N的非重復(fù)id序列。由于預(yù)先把割草式往復(fù)運(yùn)動作為Cell內(nèi)部覆蓋形式，所以接下來的工作就是沒有遺漏地為機(jī)器人分配覆蓋任務(wù)，并確定訪問順序。本文假設(shè)只能將一個Cell內(nèi)部路徑的出口點(diǎn)通過Cell間過渡路徑與臨近Cell的內(nèi)部路徑的入口點(diǎn)連接，當(dāng)前Cell會通過兩條過渡路徑與前后兩個臨近Cell鏈接。所以，Cell間過渡路徑起點(diǎn)和終點(diǎn)分別與前一的Cell的出口點(diǎn)和下一個Cell入口點(diǎn)重合。對于同一個Cell執(zhí)行了不同割草式覆蓋方向，會形成4對可選入口和出口點(diǎn)組合。

如果將每個Cell內(nèi)部路徑入口點(diǎn)和出口點(diǎn)組合固定且每個機(jī)器人的初始位置不同，那么每個機(jī)器人在各自任務(wù)空間中尋找最短訪問路徑問題就是解決TSP 問題，多個機(jī)器人在各自任務(wù)空間中尋找最短訪問路徑問題就變成了MTSP 問題。在解決這個問題之前必須設(shè)法尋找Cell間最短過渡路徑問題的解，也就是當(dāng)前Cell內(nèi)部路徑出口點(diǎn)作為起始點(diǎn)與下一個Cell內(nèi)部路徑入口點(diǎn)作為終點(diǎn)的最短路徑，且要求這條路徑與不可行域無重疊。為了解決這個問題可以利用不可行域頂點(diǎn)并把過渡路徑的起點(diǎn)和終點(diǎn)作為附加點(diǎn)，構(gòu)建可視圖。以歐幾里德距離作為過渡路徑度量，通過使用Dijkstra 算法尋找從起點(diǎn)到終點(diǎn)的最短路徑。

然而，對于具體到每個Cell的全覆蓋問題，會有四條不同遍歷方向的覆蓋路徑作為待選路徑，具體如圖2的舉例所示。因此，不同的Cell內(nèi)部路徑的入口點(diǎn)和出口點(diǎn)組合的選擇不僅對自身內(nèi)部路徑長路有影響（圖2 中四種情況路徑長度存在（a）=（b），（c）=（d）的關(guān)系），而且對具有固定訪問順序的Cell間過渡路徑長度產(chǎn)生影響。為了方便理解，暫且忽略不可行域?qū)偮窂介L度的影響，圖3舉例說明了不同的Cell訪問順序以及不同的Cell入口和出口點(diǎn)組合對總路徑長度的影響。圖3（a）中Cell訪問順序?yàn)??2?3；圖3（b）中Cell訪問順序與圖3（a）中相同，但每個Cell入口和出口點(diǎn)組合不同，顯然總路徑長度也有所不同；圖3（c）中Cell訪問順序與圖3（a）中不同，訪問順序?yàn)??2?1，但圖3（c）與圖3（a）的每個Cell入口和出口點(diǎn)組合相同，顯然這樣總路徑長度也有所不同。

圖2 Cell 的4種不同的入口和出口點(diǎn)組合Fig.2 4 different combinations of entry and exit points for Cell

圖3 路徑長度的影響因素Fig.3 Influencing factors of path length

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

承接前文的準(zhǔn)備工作，本章將詳細(xì)介紹用于解決具有MTSP 性質(zhì)的全覆蓋問題的免疫遺傳算法的具體實(shí)現(xiàn)過程。算法的總體流程如下：

步驟1初始化種群。使用Knuth洗牌法，將任務(wù)空間分解得到的N個Cell隨機(jī)排列，并為每個Cell隨機(jī)確定一組入口點(diǎn)和出口點(diǎn)，這樣得到一個個體。照此方法產(chǎn)生m個個體，m為預(yù)設(shè)的種群規(guī)模。

步驟2適應(yīng)度計算。按照個體染色體順序整體估算工作時間，按照每個機(jī)器人工作時間盡可能相等原則分割基因段。在考慮每個機(jī)器人初始位置情況下，優(yōu)化機(jī)器人所訪問Cell的入口和出口組合。計算每一個機(jī)器人從指定初始位置出發(fā)的工作時間，取出最大的工作時間與所有機(jī)器人工作時間之和的乘積的倒數(shù)作為每個個體的適應(yīng)度。選出適應(yīng)度值最高的個體。

步驟3按照基因移植概率，對整個種群重復(fù)進(jìn)行優(yōu)秀染色體片段移植操作。

步驟4對種群進(jìn)行階梯型克隆選擇操作。

步驟5重復(fù)步驟3 和步驟4 操作，尋找每一次迭代后的適應(yīng)度值最高的個體，不斷更新最優(yōu)個體。直到迭代預(yù)設(shè)代數(shù)后結(jié)束操作。按照步驟2 中適應(yīng)度計算方法，輸出最優(yōu)個體的工作時間、所有機(jī)器人總工作時間以及染色體分割結(jié)果。

3.1 編碼與解碼

本文中影響每個機(jī)器人對所分配的子任務(wù)空間的覆蓋效果的因素主要為以下兩點(diǎn)：

（1）機(jī)器人對子任務(wù)空間中Cell的覆蓋順序。

（2）子任務(wù)空間中每個Cell入口點(diǎn)和出口點(diǎn)組合的選擇。

因此，本文使用十進(jìn)制整數(shù)編碼基因，每一位基因gene要符合以上兩點(diǎn)要素，具體編碼規(guī)則如下：

式中，i為Cell的4種內(nèi)部路徑入口點(diǎn)和出口點(diǎn)組合編號，0、1、2、3 分別對應(yīng)圖2（a）、圖2（b）、圖2（c）、圖2（d）這4種情況。

由式（1）不難得到解碼規(guī)則如下：

式中，//為整除運(yùn)算符，%為取余運(yùn)算符。舉例說明某個體染色體的編碼與解碼過程如圖4 所示。圖4（a）為編碼過程，其中個體染色體第一位編碼“23”是由“id”行第一位“6”與“i”行第一位“3”按照式（1）運(yùn)算得到，即（6-1）×4+3=23；圖4（b）為解碼過程，其中“id”行最后一位“10”是由個體染色體最后一位編碼“39”按照式（2）運(yùn)算得到，即39//4+1=10，“i”行最后一位“3”是由個體染色體最后一位編碼“39”按照式（2）運(yùn)算得到，即39%4=3。

圖4 編碼與解碼原理Fig.4 Principle of encoding and decoding

3.2 適應(yīng)度計算方法

基因編碼和解碼規(guī)則介紹完后，下面介紹基于動態(tài)均衡每個機(jī)器人工作時間的原則計算個體適應(yīng)度值。首先按照染色體中每一位基因解碼得到的Cell的id和對應(yīng)Cell內(nèi)部路徑入口點(diǎn)和出口點(diǎn)組合，計算覆蓋整個任務(wù)空間中所有Cell內(nèi)部路徑所需要的總工作時間Ta：

式中，n表示個體染色體中基因的位置，μa表示Cell內(nèi)部路徑時間因子，la,n表示第n個位置上gene解碼后計算得到內(nèi)部路徑長度。由于Ta遠(yuǎn)大于所有覆蓋Cell間過渡路徑Te，所以在分配任務(wù)前估算所有機(jī)器人總工作時間為Ta。那么，按式（4）所示計算得到Nrobot個機(jī)器人理想工作時間為tdream。然而通過BCD 分解得到的Cell面積存在不均勻性，為了均衡每個機(jī)器人的工作時間，仍然以圖4 中的個體染色體為例，當(dāng)Nrobot=3時，如圖5所示舉例說明染色體動態(tài)均勻分割方法。用線段長度表示時間長短，圖中理想分割點(diǎn)就是tdream的具體表達(dá)，然后動態(tài)地取最靠近理想分割點(diǎn)的線段端點(diǎn)作為實(shí)際分割點(diǎn)，所得的(Nrobot-1) 個實(shí)際分割點(diǎn)把整個個體染色體盡可能均勻地分成Nrobot個子染色體段。

圖5 染色體動態(tài)均分原理Fig.5 Principle of dynamic homogeneity of chromosomes

個體染色體被分割成多段染色體片段后就會分配給對應(yīng)的機(jī)器人。如算法1所示利用動態(tài)規(guī)劃算法，同時考慮立面維護(hù)作業(yè)機(jī)器人起點(diǎn)位置和終點(diǎn)位置的特征對每一個染色體段重新優(yōu)化，目的在于機(jī)器人對各個Cell的覆蓋順序不變的情況下，合理調(diào)整每個Cell的入口點(diǎn)和出口點(diǎn)組合，以達(dá)到每個機(jī)器人總工作時間最短的目的。然后按照優(yōu)化結(jié)果，使用式（5）計算個體適應(yīng)度值。最后將所有染色體片段按原來順序重新拼接成新的染色體，方便其他操作。

式中，ti表示第i個機(jī)器人從路徑起點(diǎn)出發(fā)覆蓋相應(yīng)的子染色體段中的所有Cell并到達(dá)終點(diǎn)結(jié)束的工作時間；Fit表示個體適應(yīng)度值；max{}?表示取最大值運(yùn)算；lstart表示機(jī)器人從起點(diǎn)出發(fā)到達(dá)相應(yīng)的子染色體段上第一個Cell入口點(diǎn)的路徑長度；lend表示機(jī)器人從子染色體段上最后一個Cell出口點(diǎn)出發(fā)到達(dá)路徑終點(diǎn)的路徑長度；le,j表示從子染色體段上第j個Cell的出口點(diǎn)到下一個Cell入口點(diǎn)之間的過渡路徑長度；la,j表示子染色體段上第j個Cell的內(nèi)部路徑長度；μe表示外部路徑時間因子，μe≤μa。

算法1使用動態(tài)規(guī)劃算法優(yōu)化機(jī)器人固定訪問順序下覆蓋路徑最短的每個Cell的最佳入口和出口點(diǎn)組合

3.3 優(yōu)秀染色體片段移植（交叉）算子

與傳統(tǒng)的遺傳算法中的順序交叉算子產(chǎn)生兩個新子代個體相比，本文中優(yōu)秀染色體片段移植算子操作后產(chǎn)生一個新的個體offspring。將種群按照適應(yīng)度的值從大到小排序，在種群的前25%優(yōu)秀個體中隨機(jī)選擇個體parent1，再從種群中使用式（6）所示的個體被選中的概率與其適應(yīng)度值成負(fù)相關(guān)關(guān)系的輪盤賭來選擇個體parent2：

式中，F(xiàn)iti表示第i個個體的適應(yīng)度值；pi表示第i個個體被選中的概率；qi表示第i個個體的累積概率；這樣設(shè)置輪盤賭的目的是使種群中的劣質(zhì)個體更容易被選中。

然后，在parent1 中隨機(jī)選擇起始點(diǎn)切取自適應(yīng)長度Sg的染色體片段，式（7）為Sg計算方法：

式中，int{?}為向下取整運(yùn)算符。

當(dāng)起點(diǎn)位置加上Sg超過parent1 長度時，從parent1的首位開始繼續(xù)切取直到滿足Sg長度。把從parent1中切取的染色體片段放到offspring的相同位置上，同時從parent2 中找到與offspring插入結(jié)束點(diǎn)相同的位置，從這個位置開始檢索與從parent1 中切取的染色體片段不同的基因依次放置到offspring的空缺位置上，結(jié)束后用offspring替換掉種群中的parent2。最后，計算offspring適應(yīng)度值并保存。這樣類似于將parent1 染色體片段移植到parent2，所以把該算子稱作優(yōu)秀染色體片段移植算子。如圖6所示舉例說明優(yōu)秀基因移植實(shí)現(xiàn)過程。

圖6 優(yōu)秀染色體片段移植Fig.6 Excellent chromosome fragment transplantation

圖6中取出優(yōu)質(zhì)個體parent1 的連續(xù)染色體片段并放到offspring的相同位置上的原因在于gene的位置具有實(shí)際意義。將優(yōu)秀個體的隨機(jī)位上開始的一段染色體移植到劣質(zhì)個體的相同位置上，使劣質(zhì)個體顯性表達(dá)了優(yōu)質(zhì)個體的部分優(yōu)質(zhì)特征從而產(chǎn)生了新的個體offspring。之所以控制從優(yōu)質(zhì)個體上切取染色體片段的長度，是因?yàn)閮?yōu)秀個體的優(yōu)秀特征主要取決于一段染色體的連續(xù)編碼順序，但是移植的太長勢必會降低種群的多樣性，太短又失去了移植的意義，所以需要自適應(yīng)控制Sg的值。之所以保留優(yōu)質(zhì)染色體片段在子代中的位置，原因在于多機(jī)器人任務(wù)分配與適應(yīng)度計算是按照機(jī)器人起點(diǎn)和終點(diǎn)位置序列對個體染色體動態(tài)分割的，所以優(yōu)質(zhì)的連續(xù)編碼安放的位置也十分重要。這樣操作在某種程度上不僅保留種群多樣性的，還不破壞優(yōu)秀個體，更是對劣質(zhì)個體的改良。此方法模仿生物族群進(jìn)化原理，將種群中優(yōu)質(zhì)特征基因選擇性遺傳下來。微觀上看，由于優(yōu)質(zhì)個體片段切取位置具有隨機(jī)性，所以這種操作對劣質(zhì)個體的啟發(fā)能力是有限的。但從宏觀上看，優(yōu)質(zhì)特征在種群中的傳播，將增大劣質(zhì)群體的適應(yīng)度，結(jié)合下文中的階梯型克隆選擇算子，勢必啟發(fā)種群加大對改良后的個體的克隆選擇的能力。在控制適當(dāng)?shù)膬?yōu)秀染色體片段移植發(fā)生的概率，在整體上將啟發(fā)種群更快的得到全局近似解。

3.4 階梯型克隆選擇算子

將種群按照適應(yīng)度的值從大到小排序，對種群的前25%的個體克隆4×M（M為基礎(chǔ)克隆倍數(shù)，根據(jù)個體染色體長度確定）份，在保留被克隆的個體同時，將4×(M-1)個個體的染色體中隨機(jī)兩個Cell調(diào)換位置，實(shí)現(xiàn)基因突變。計算4×M個體適應(yīng)度值，將適應(yīng)度值最高的個體更新為新的個體。對前25%～50%的個體按照3×M的倍數(shù)重復(fù)上面操作。對前50%～75%的個體按照2×M的倍數(shù)重復(fù)操作。對種群后25%的個體刪除，并重新初始化相應(yīng)數(shù)目的個體，計算適應(yīng)度后放入種群。

這樣操作的目的是在保證種群多樣性的同時使算法獲得較好的收斂效果。將種群按照適應(yīng)值大小平均分成了4 組，模仿生物免疫理論，提高親和能力強(qiáng)的分組被克隆選擇的能力，降低適應(yīng)能力差的分組被克隆選擇的能力，甚至將其淘汰。將適應(yīng)度值最小的一組淘汰并重新初始化新的個體加入種群，為了剔除劣質(zhì)個體并保持種群多樣性；按照適應(yīng)度值越大克隆選擇倍數(shù)越高的階梯型法則，可以加快優(yōu)質(zhì)解向最優(yōu)解靠近速度，同時降低由于過渡求解次優(yōu)解而導(dǎo)致不必要的資源浪費(fèi)。

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

4.1 可行性仿真驗(yàn)證

多機(jī)器人全覆蓋算法性能的優(yōu)劣和所要覆蓋的地圖的復(fù)雜度有關(guān)，本文設(shè)計了3個不同復(fù)雜程度的像素地圖對全覆蓋算法仿真驗(yàn)證。地圖復(fù)雜度包括地圖大小、不可行域形狀的任意性以及分解后Cell數(shù)目的多少。所有仿真實(shí)驗(yàn)中同質(zhì)機(jī)器人覆蓋半徑R=10，種群規(guī)模m=2 048，基礎(chǔ)克隆倍數(shù)M=160，優(yōu)秀染色體片段移植發(fā)生概率0.02，內(nèi)部路徑時間因子μa=3，外部路徑時間因子μe=1，為了方便觀察算法收斂性取算法迭代代數(shù)為50。考慮到在立面維護(hù)作業(yè)的多機(jī)器人全覆蓋作業(yè)過程中，機(jī)器人工作路徑的起點(diǎn)和終點(diǎn)多是待覆蓋區(qū)域的邊緣，所以本文仿真實(shí)驗(yàn)所選取的機(jī)器人起點(diǎn)和終點(diǎn)都在待覆蓋區(qū)域邊緣。如圖7（a）～（c）分別展示了算法在不同復(fù)雜程度的地圖中的仿真結(jié)果。表1 展示了不同仿真地圖的相關(guān)信息。

表1 不同復(fù)雜度程度的仿真數(shù)據(jù)Table 1 Data for simulations of different degrees of complexity

圖7 不同復(fù)雜度程度的仿真結(jié)果Fig.7 Simulation results for different levels of complexity

4.2 多指標(biāo)分析

為了檢驗(yàn)算法的質(zhì)量，本文使用5個同質(zhì)機(jī)器人對較為復(fù)雜的圖7（c）所示地圖實(shí)現(xiàn)全覆蓋。如圖8所示，分別對每代最優(yōu)個體的工作時長（所有機(jī)器人工作時長中最大值，即max{ti}）、總工作量（所有機(jī)器人工作時長算術(shù)和，即、不均衡度U以及適應(yīng)度值的倒數(shù)1/Fit的50 次迭代收斂情況分析。其中不均衡度計算方法如式（8）所示，用于評價多機(jī)器人全覆蓋過程中任務(wù)分配的不均衡程度，U數(shù)值越大說明多機(jī)器人任務(wù)分配的越不均衡。

圖8 算法收斂性效果曲線Fig.8 Curve of convergence effect of algorithm

式中，min{ti}表示取最小值運(yùn)算。

觀察圖8 發(fā)現(xiàn)工作時長在1 至21 代整體呈現(xiàn)減小趨勢，但在5至6代、19至20代略有增大，在第21代后收斂于39 287.5；總工作量在1至23代整體呈現(xiàn)減小趨勢，但在6 至7 代略有增大，在第23 代后收斂于194 481；不均衡度在1 至23 代呈現(xiàn)較大波動，在23 代后穩(wěn)定在0.004 438<1%；1/Fit在1 代至23 代持續(xù)減小，在第23代后收斂于7.640 69×109。由于工作時長和總工作量相互影響，但1/Fit持續(xù)減小，所以工作時長和總工作量在收斂過程略有波動屬于正常現(xiàn)象，這樣更有利于彼此跳出局部最優(yōu)解。由于BCD 分解具有不均勻性，使得不均衡度在穩(wěn)定之前呈現(xiàn)很大波動，但是前面介紹的算法已經(jīng)考慮到任務(wù)分配的均衡問題，所以相比于不均衡度的收斂過程，關(guān)注不均衡度的穩(wěn)定值更有意義。綜上可得，本文所提出的用于解決立面維護(hù)作業(yè)的多機(jī)器人全覆蓋路徑規(guī)劃的免疫遺傳算法具有較好的收斂穩(wěn)定性。

4.3 對比實(shí)驗(yàn)

為了檢驗(yàn)算法的收斂速度、運(yùn)算復(fù)雜度、收斂精度。將本文的雙目標(biāo)適應(yīng)度方法與傳統(tǒng)的單目標(biāo)適應(yīng)度方法進(jìn)行比較，使用1 至5 個同質(zhì)機(jī)器人對較為復(fù)雜的圖7（c）所示地圖分別實(shí)現(xiàn)全覆蓋。每個實(shí)驗(yàn)數(shù)據(jù)取10次實(shí)驗(yàn)平均值。其中單目標(biāo)方法把工作時長作為算法的主要求解目標(biāo)。

如圖9所示，顯示了兩種方法對路徑規(guī)劃時間的比較實(shí)驗(yàn)。不難發(fā)現(xiàn)本文雙目標(biāo)方法在使用2 臺乃至更多機(jī)器人時，算法在運(yùn)算速度方面有明顯的加快，在穩(wěn)定性上也有明顯提升。尤其需要注意的是，在機(jī)器人臺數(shù)增加時本文的雙目標(biāo)適應(yīng)度方法的路徑規(guī)劃時間（算法復(fù)雜度）會有所減少。主要原因是本文動態(tài)分割染色體后使用了動態(tài)規(guī)劃算法來優(yōu)化Cell內(nèi)部覆蓋路徑的入口點(diǎn)與出口點(diǎn)組合。隨著機(jī)器人的數(shù)目增加，相同地圖下動態(tài)規(guī)劃算法的計算規(guī)模會有所減少。所以在機(jī)器人臺數(shù)增加時，本文所使用的算法更能發(fā)揮其優(yōu)勢。

圖9 路徑規(guī)劃時間的對比實(shí)驗(yàn)Fig.9 Comparative experiments on timing of path planning

為了檢驗(yàn)算法在多機(jī)器人全覆蓋效果方面的表現(xiàn)，同時也為了對比本文的雙目標(biāo)適應(yīng)度方法與傳統(tǒng)的單目標(biāo)適應(yīng)度方法在各種指標(biāo)上的表現(xiàn)。如表2所示，不難看出兩種方法在機(jī)器人臺數(shù)為1時表現(xiàn)相同，主要因?yàn)楫?dāng)面對單機(jī)器人全覆蓋問題時，兩種方法可以看作是相同方法。本文的雙目標(biāo)適應(yīng)度方法隨著機(jī)器人數(shù)目增加，相同環(huán)境下的工作時長呈線性減小，說明算法求解對于不同數(shù)目機(jī)器人全覆蓋問題具有較好的穩(wěn)定性。由于本文提出的算法考慮了每個機(jī)器人起始位置和終點(diǎn)位置的調(diào)度問題，所以隨著機(jī)器人數(shù)目增加總工作量和路徑重復(fù)率都呈線性小幅度增加。同時，各種情況實(shí)驗(yàn)后不均衡度值均小于1%且并無異常值出現(xiàn)，說明任務(wù)分配相對均衡。在面對MCCPP 時，本文所提供的算法不管在工作時長、總工作量以及路徑重復(fù)率方面都有小幅優(yōu)化。所以不難看出，本文所提出的用于解決立面維護(hù)作業(yè)的多機(jī)器人全覆蓋路徑規(guī)劃的雙目標(biāo)適應(yīng)度免疫遺傳算法具有很好的綜合收益。

表2 對比實(shí)驗(yàn)Table 2 Comparison experiments

5 結(jié)束語

針對目前多機(jī)器人全覆蓋算法存在任務(wù)分配不均、對機(jī)器人起始位置和終點(diǎn)位置選擇的靈活性考慮不充分、算法求解目標(biāo)單一以及復(fù)雜不可行域地圖覆蓋靈活性不足等問題。本文將立面維護(hù)作業(yè)下的多機(jī)器人全覆蓋問題視為多旅行商問題的擴(kuò)展，作者將改進(jìn)的免疫遺傳算法結(jié)合求解多旅行商問題的綜合方法應(yīng)用于多機(jī)器人全覆蓋領(lǐng)域。首先，本文完成了一些相關(guān)工作：（1）解決了多機(jī)器人任意起點(diǎn)和終點(diǎn)全覆蓋路徑優(yōu)化問題；（2）提出了覆蓋任務(wù)動態(tài)均衡分配算子；（3）為了加快算法收斂速度使用的具有啟發(fā)式的優(yōu)秀染色體片段移植算子；（4）為了尋找全局近似最優(yōu)解將動態(tài)規(guī)劃算法與階梯型克隆選擇算子相結(jié)合；（5）在任務(wù)得到均衡分配和考慮立面維護(hù)作業(yè)機(jī)器人起點(diǎn)位置和終點(diǎn)位置的任意性特點(diǎn)的前提下，本文適應(yīng)度函數(shù)同時包含多機(jī)器人工作中最大的工作時長最小和多機(jī)器人總工作量最小兩個求解目標(biāo)。最后，通過對不同復(fù)雜程度仿真實(shí)驗(yàn)，驗(yàn)證了算法的可行性；通過對復(fù)雜地圖的全覆蓋仿真實(shí)驗(yàn)，驗(yàn)證了該算法對多個優(yōu)化目標(biāo)的近似解具有較好的收斂性；通過對比實(shí)驗(yàn)，深入分析了本文所提出的算法的復(fù)雜度、運(yùn)算速度以及運(yùn)算精度，檢驗(yàn)了算法的質(zhì)量。未來，在面對復(fù)雜的實(shí)際應(yīng)用場景，均勻Cell的面積、優(yōu)化算法時間和空間復(fù)雜度以及優(yōu)化感興趣區(qū)域權(quán)重因子分配方法等方面可作為下一階段研究內(nèi)容。