立面維護(hù)作業(yè)的多機(jī)器人全覆蓋路徑規(guī)劃

謝必成，張小俊

河北工業(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)注和研究。對(duì)于工作效率更高的多機(jī)器人全覆蓋路徑規(guī)劃（multirobot complete coverage path planning，MCCPP）的研究也已經(jīng)得到學(xué)者們的廣泛關(guān)注[7]。目前對(duì)MCCPP 的研究也大多是在平面環(huán)境下進(jìn)行的，而對(duì)于石油儲(chǔ)罐檢測(cè)、船舶噴漆與除銹以及大型玻璃外表面清潔等工作環(huán)境更為復(fù)雜和危險(xiǎn)的立面維護(hù)作業(yè)MCCPP的研究便更有其特定的研究?jī)r(jià)值。

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

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

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

1 前提與假設(shè)

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

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

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

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

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

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

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

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

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

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

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

2.1 任務(wù)空間分解

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

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

2.2 覆蓋路徑分解

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

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

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

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

圖3 路徑長(zhǎng)度的影響因素Fig.3 Influencing factors of path length

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

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

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

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

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

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

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

3.1 編碼與解碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 階梯型克隆選擇算子

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

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

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

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

多機(jī)器人全覆蓋算法性能的優(yōu)劣和所要覆蓋的地圖的復(fù)雜度有關(guān)，本文設(shè)計(jì)了3個(gè)不同復(fù)雜程度的像素地圖對(duì)全覆蓋算法仿真驗(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)部路徑時(shí)間因子μa=3，外部路徑時(shí)間因子μ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個(gè)同質(zhì)機(jī)器人對(duì)較為復(fù)雜的圖7（c）所示地圖實(shí)現(xiàn)全覆蓋。如圖8所示，分別對(duì)每代最優(yōu)個(gè)體的工作時(shí)長(zhǎng)（所有機(jī)器人工作時(shí)長(zhǎng)中最大值，即max{ti}）、總工作量（所有機(jī)器人工作時(shí)長(zhǎng)算術(shù)和，即、不均衡度U以及適應(yīng)度值的倒數(shù)1/Fit的50 次迭代收斂情況分析。其中不均衡度計(jì)算方法如式（8）所示，用于評(píng)價(jià)多機(jī)器人全覆蓋過程中任務(wù)分配的不均衡程度，U數(shù)值越大說明多機(jī)器人任務(wù)分配的越不均衡。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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