孫麗娜，田軍委，劉雪松，王 沁

(1.西安工業(yè)大學(xué) 機(jī)電工程學(xué)院，西安 710021；2.內(nèi)蒙古北方重工業(yè)集團(tuán)有限公司，包頭 014033)

在“中國制造2025”飛速發(fā)展和創(chuàng)新中國戰(zhàn)略實(shí)行下，移動(dòng)機(jī)器人技術(shù)不斷進(jìn)步[1]。為了提高機(jī)器人作業(yè)效率和整體效益，常常將多個(gè)任務(wù)同時(shí)賦予單個(gè)機(jī)器人以實(shí)現(xiàn)最佳作業(yè)能力[2]。田間作業(yè)有任務(wù)多樣性和環(huán)境復(fù)雜性的特點(diǎn)，路徑規(guī)劃作為機(jī)器人田間正常工作的基礎(chǔ)之一，研究工作十分必要。

路徑規(guī)劃是指以順利到達(dá)目標(biāo)位置的代價(jià)最小化為目標(biāo)，規(guī)劃出一條機(jī)器人行走的路徑[3]。遺傳算法是機(jī)器人路徑規(guī)劃較常用的算法之一，但是經(jīng)典遺傳算法存在局部搜索能力較差、易產(chǎn)生早熟收斂等缺陷，所以不少學(xué)者對(duì)經(jīng)典遺傳算法進(jìn)行了改進(jìn)。文獻(xiàn)[4-9]從遺傳算法的操作算子進(jìn)行改進(jìn)，重新定義各個(gè)算子、自適應(yīng)交叉概率和變異概率。改進(jìn)后加快算法的收斂速度，但當(dāng)任務(wù)復(fù)雜度增加時(shí)算法會(huì)過早陷入局部收斂。文獻(xiàn)[10-13]對(duì)適應(yīng)度函數(shù)進(jìn)行了改進(jìn)，如添加轉(zhuǎn)彎角度控制因子、路徑連貫性，同時(shí)考慮多個(gè)適應(yīng)度影響因素時(shí)不能有效保證路徑值最短。文獻(xiàn)[14-16]遺傳算法分別與不同算法進(jìn)行融合，解決了局部最優(yōu)解的問題，但沒有考慮多個(gè)任務(wù)點(diǎn)的情況，不能驗(yàn)證改進(jìn)算法在增加任務(wù)點(diǎn)后的算法可行性。

本文針對(duì)多個(gè)任務(wù)點(diǎn)的作業(yè)環(huán)境，將模擬退火算法的進(jìn)化機(jī)制融合至遺傳算法,改善遺傳算法的局部搜索能力和算法收斂速度。

1 環(huán)境地圖建模

環(huán)境地圖包含了大量的空間準(zhǔn)確位置信息：機(jī)器人的起點(diǎn)、終點(diǎn)、任務(wù)點(diǎn)、障礙物等,如圖1所示。

圖1 柵格地圖模型

文中環(huán)境是二維平面靜態(tài)地圖，用柵格法來建立環(huán)境模型(20 m×20 m的尺寸)，柵格法是環(huán)境建模方面應(yīng)用最廣泛的方法之一，它將機(jī)器人所在空間抽象為二維空間。每個(gè)單元格具備一種環(huán)境信息，占據(jù)柵格的數(shù)值為1，未占據(jù)的柵格數(shù)值為0。圖1中的白色網(wǎng)格表示機(jī)器人可以穿越的區(qū)域，黑色網(wǎng)格表示障礙物。

2 改進(jìn)的多任務(wù)機(jī)器人路徑規(guī)劃

遺傳算法作為一種群體智能算法，具有較強(qiáng)的全局尋優(yōu)能力。文中以遺傳算法作為模型求解算法，針對(duì)其易于早熟收斂、收斂速度慢等問題進(jìn)行改進(jìn)，融合模擬退火算法Metropolis準(zhǔn)則提高算法的局部尋優(yōu)能力。模擬退火算法源于現(xiàn)實(shí)的物理退火過程，通過抽象真實(shí)物理退火過程中的加溫過程、等溫過程、冷卻過程來求得最優(yōu)解，通過其特有的接受準(zhǔn)則來保證算法局部尋優(yōu)能力。

2.1 編碼方式

柵格序號(hào)與柵格坐標(biāo)相比，具有形式簡(jiǎn)單的優(yōu)點(diǎn)。因此，本文對(duì)染色體的編碼采用柵格序號(hào)。即在柵格地圖中按照從上到下、從左到右的順序?qū)⑿鸥襁M(jìn)行編號(hào)，0代表機(jī)器人移動(dòng)起點(diǎn)，399代表移動(dòng)終點(diǎn)，中間任務(wù)點(diǎn)的位置編號(hào)同樣。

為確保機(jī)器人路徑規(guī)劃的可靠性，要求每條可行路徑不能出現(xiàn)障礙物序號(hào)和重復(fù)序號(hào)。如：P={S,P1,P2,P3…Pn,G}表示一條可行路徑，其中S為起點(diǎn)，G為終點(diǎn)，Pi(i=1,2,3…n)是柵格中的可行節(jié)點(diǎn)。

2.2 種群初始化

種群初始化時(shí)，由機(jī)器人移動(dòng)環(huán)境中障礙物信息已知，柵格化環(huán)境地圖后，自由柵格和障礙柵格容易區(qū)分。所以采用在移動(dòng)機(jī)器人運(yùn)動(dòng)起點(diǎn)到終點(diǎn)之間，隨機(jī)選擇一系列標(biāo)記為0的自由柵格作為路徑節(jié)點(diǎn)。連接起點(diǎn)、終點(diǎn)和選定的路徑節(jié)點(diǎn)作為機(jī)器人移動(dòng)的一條無障礙路徑。

2.3 建立適應(yīng)度函數(shù)

算法的適應(yīng)度函數(shù)即模型優(yōu)化目標(biāo)函數(shù)。文中以路徑距離作為函數(shù)評(píng)價(jià)指標(biāo)，一條可行路徑上是由許多個(gè)節(jié)點(diǎn)連接而成，則路徑距離L為

(1)

式中：n為機(jī)器人通過的柵格總數(shù)；xi為第i個(gè)節(jié)點(diǎn)的橫坐標(biāo)；yi為第i個(gè)節(jié)點(diǎn)的縱坐標(biāo)。

對(duì)機(jī)器人路徑選擇，路徑越短則為更優(yōu)，則目標(biāo)函數(shù)即適應(yīng)度函數(shù)F為路徑距離L的倒數(shù)。

2.4 遺傳算子操作

2.4.1 選擇算子

在遺傳算法開始時(shí)，總是隨機(jī)的產(chǎn)生一些個(gè)體(即初始解)，根據(jù)預(yù)定的目標(biāo)函數(shù)對(duì)每一個(gè)體進(jìn)行評(píng)估，給出一個(gè)適應(yīng)度值，基于此適應(yīng)度值選擇一些個(gè)體用來產(chǎn)生下一代。較優(yōu)的個(gè)體被留下，經(jīng)過交叉和變異算子進(jìn)行組合再生成新的一代，這樣逐步朝著最優(yōu)解的方向進(jìn)化。文中采用輪盤賭選擇方法，個(gè)體被選中的概率與適應(yīng)度函數(shù)值大小成正比。即N個(gè)的適應(yīng)值變換為1至N，則編號(hào)為m的個(gè)體被選中的概率P為

(2)

2.4.2 交叉算子

遺傳算法通過交叉算子來維持種群的多樣性。文中采用常見單點(diǎn)交叉方法，即隨機(jī)選擇兩條父代路徑，在兩條路徑的相同節(jié)點(diǎn)處進(jìn)行交叉操作，不包含起點(diǎn)和終點(diǎn)，若相同節(jié)點(diǎn)有多個(gè)則隨機(jī)選擇一個(gè)節(jié)點(diǎn)交叉。當(dāng)兩條父代路徑?jīng)]有相同節(jié)點(diǎn)或者交叉后基因相同時(shí)，則放棄本次交叉操作，父代個(gè)體為

V1={0,23,89,156,235,289,376,399},

V2={0,34,93,158,321,289,364,399}。

選擇父代的相同節(jié)點(diǎn)289作為交叉點(diǎn)，則生成的兩條子代個(gè)體為

C1={0,23,89,156,235,289,364,399}，

C2={0,34,93,158,321,289,376,399}。

2.4.3 變異算子

采取隨機(jī)變異的方法進(jìn)行變異操作。從個(gè)體中除終點(diǎn)和起點(diǎn)之外隨機(jī)選擇一個(gè)序號(hào)視為變異點(diǎn)，然后刪除該序號(hào)，這樣可避免出現(xiàn)不可行解。

2.5 融合Metropolis準(zhǔn)則

模擬退火算法具有較強(qiáng)的局部尋優(yōu)能力，為了解決遺傳算法易陷入局部最優(yōu)解的問題，文中將模擬退火算法的進(jìn)化機(jī)制融合至遺傳算法中。

模擬退火算法存在一定的容錯(cuò)能力，能以一定概率接受劣質(zhì)解，概率P為新解接受概率，大小受當(dāng)前溫度T及新舊解適應(yīng)度E差的影響，總的趨勢(shì)是溫度越低接受概率越低，差值越大接受概率越低。

當(dāng)E(xnew)

當(dāng)E(xnew)≥E(xold)時(shí)，

(3)

得到接受概率后隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)，介于0到1之間，當(dāng)其大于接受概率P時(shí)，不接受新解，當(dāng)其小于P時(shí)，接受新解。故在遺傳算法操作產(chǎn)生新解后可采用Metropolis準(zhǔn)則決定是否保留新解。

2.6 多任務(wù)分解

文中設(shè)置了多個(gè)任務(wù)點(diǎn)，機(jī)器人在移動(dòng)過程中從起點(diǎn)出發(fā)經(jīng)歷多個(gè)任務(wù)點(diǎn)最終到達(dá)終點(diǎn)。要使機(jī)器人行走的總路徑最短，將多任務(wù)路徑分解成單任務(wù)路徑，保證單任務(wù)路徑最短則總路徑即為最短。柵格圖中起點(diǎn)編號(hào)為0，終點(diǎn)編號(hào)為399，兩個(gè)任務(wù)點(diǎn)編號(hào)分別為110和246，則可以分解為：[0,110],[110,246],[246,399]，總路徑即為三段路徑之和。

3 仿真結(jié)果及分析

為驗(yàn)證文中提出算法的合理性和有效性，運(yùn)用Matlab軟件在20 m×20 m的柵格環(huán)境模型中進(jìn)行仿真分析。參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中分別設(shè)置障礙物個(gè)數(shù)為31個(gè)和69個(gè)，在不同任務(wù)點(diǎn)個(gè)數(shù)下對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃，實(shí)驗(yàn)圖中路徑長度取單位為米。

3.1 雙任務(wù)實(shí)驗(yàn)

障礙物個(gè)數(shù)為31個(gè)時(shí)的仿真實(shí)驗(yàn)結(jié)果如圖2和圖3所示，經(jīng)典遺傳算法在進(jìn)化8代得到路徑值為39.799 0 m。改進(jìn)遺傳算法在進(jìn)化第5代后趨于穩(wěn)定，得到路徑值為37.799 0 m。為了驗(yàn)證本文所提出改進(jìn)遺傳算法的有效性，與文獻(xiàn)[7]提出的自適應(yīng)改進(jìn)遺傳算法選擇相同的工作環(huán)境，即障礙物的個(gè)數(shù)設(shè)置為31個(gè)。雙任務(wù)點(diǎn)下三種算法的仿真實(shí)驗(yàn)結(jié)果對(duì)比見表2。

表2 仿真實(shí)驗(yàn)結(jié)果對(duì)比

圖2 實(shí)驗(yàn)運(yùn)動(dòng)軌跡圖

圖3 算法收斂曲線圖

當(dāng)障礙物數(shù)量增加到69個(gè)時(shí)，三種算法的仿真實(shí)驗(yàn)結(jié)果如圖4和圖5所示，結(jié)果對(duì)比見表3。

圖4 實(shí)驗(yàn)運(yùn)動(dòng)軌跡圖

圖5 算法收斂曲線圖

表3 仿真實(shí)驗(yàn)結(jié)果對(duì)比

經(jīng)典遺傳算法在進(jìn)化11代陷入了局部最優(yōu)解，自適應(yīng)改進(jìn)算法在進(jìn)化6代收斂，而文中的改進(jìn)遺傳算法進(jìn)化4代達(dá)到穩(wěn)定。由此可得，改進(jìn)遺傳算法的收斂速度優(yōu)于這兩種算法，且路徑值更短。

3.2 三任務(wù)實(shí)驗(yàn)

障礙物個(gè)數(shù)為31個(gè)時(shí)，機(jī)器人在工作時(shí)需要經(jīng)歷三個(gè)任務(wù)點(diǎn)的仿真實(shí)驗(yàn)結(jié)果如圖6和圖7所示，標(biāo)準(zhǔn)遺傳算法的路徑長度為37.799 0 m，自適應(yīng)改進(jìn)算法的路徑長度為37.799 0 m，而文中的改進(jìn)算法路徑長度為36.627 4 m。經(jīng)典遺傳算法在12代時(shí)陷入了局部最優(yōu)解，自適應(yīng)改進(jìn)算法在8代達(dá)到收斂，實(shí)驗(yàn)結(jié)果如圖8所示，而改進(jìn)后的算法在4代時(shí)候趨于穩(wěn)定狀態(tài)，改進(jìn)后的算法對(duì)移動(dòng)機(jī)器人的靜態(tài)最優(yōu)路徑優(yōu)于標(biāo)準(zhǔn)遺傳算法。三種算法在收斂速度、最短路徑長度方面的對(duì)比見表4。

圖6 實(shí)驗(yàn)運(yùn)動(dòng)軌跡圖

圖7 算法收斂曲線圖

圖8 自適應(yīng)改進(jìn)算法仿真實(shí)驗(yàn)結(jié)果

表4 仿真實(shí)驗(yàn)結(jié)果對(duì)比

移動(dòng)機(jī)器人作業(yè)需要在69個(gè)障礙物下遍歷三個(gè)任務(wù)點(diǎn)時(shí)，實(shí)驗(yàn)結(jié)果如圖9和圖10所示。自適應(yīng)改進(jìn)算法的實(shí)驗(yàn)結(jié)果如圖11所示。經(jīng)典遺傳算法在進(jìn)化18代得到路徑值為36.727 9 m；自適應(yīng)改進(jìn)算法算法在進(jìn)化9代得到路徑值35.313 7 m，而本文的改進(jìn)遺傳算法克服了局部最優(yōu)解的缺陷，在進(jìn)化7代后趨于穩(wěn)定，得到路徑值為34.729 7 m。三種算法的仿真實(shí)驗(yàn)結(jié)果對(duì)比見表5。

圖9 實(shí)驗(yàn)運(yùn)動(dòng)軌跡圖

圖10 算法收斂曲線圖

圖11 自適應(yīng)改進(jìn)算法仿真實(shí)驗(yàn)結(jié)果

表5 仿真實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié) 論

1) 本文以遺傳算法為求解算法模型，提出一種融合模擬退火的改進(jìn)算法。

2) 在雙任務(wù)作業(yè)要求下，障礙物個(gè)數(shù)設(shè)置為31個(gè)和69個(gè)時(shí)，文中提出的算法較經(jīng)典遺傳算法的路徑值分別縮短了約5%和9%，收斂速度分別提高了約44%和64%；對(duì)比自適應(yīng)改進(jìn)算法，路徑值分別縮短了約5%和2%，收斂速度分別提高了約29%和33%。

3) 任務(wù)點(diǎn)增加到三個(gè)時(shí)，同樣在障礙物個(gè)數(shù)為31個(gè)和69個(gè)中驗(yàn)證改進(jìn)算法，對(duì)比遺傳算法路徑值分別縮短了約3%和5%，收斂速度分別提高了約67%和61%；與自適應(yīng)改進(jìn)算法作比較，路徑值分別縮短了約3%和2%，收斂速度分別提高了約50%和22%。

4) 文中提出的融合模擬退火改進(jìn)遺傳算法適用于二維環(huán)境下的地面移動(dòng)機(jī)器人路徑規(guī)劃，尚未擴(kuò)展到無人機(jī)以及水下機(jī)器人的應(yīng)用，可將多任務(wù)路徑規(guī)劃問題逐步拓展到如海洋探測(cè)、山林探險(xiǎn)、自然災(zāi)害救災(zāi)等三維環(huán)境。