基于改進(jìn)算法的移動機(jī)器人路徑規(guī)劃

謝沖沖，李 瑩

(昆明理工大學(xué)機(jī)電工程學(xué)院，昆明 650504)

機(jī)器人的路徑規(guī)劃在一定程度上反映了機(jī)器人的研發(fā)水平[1]。研究學(xué)者在機(jī)器人路徑規(guī)劃方面已經(jīng)研發(fā)出了較多的規(guī)劃方法。由于當(dāng)下仍處于優(yōu)化階段，不同規(guī)劃路徑方法均有自身特點及其優(yōu)劣性，不同規(guī)劃方法面向的應(yīng)用領(lǐng)域也不盡相同[2-3]。對移動機(jī)器人路徑規(guī)劃的主要目的是獲取機(jī)器人從某一位置起始點到需要到達(dá)的位置點的可行路徑。在眾多可行路徑中通過對移動路徑的行走距離、移動時間及機(jī)器人能耗等不同指標(biāo)進(jìn)行擇優(yōu)即為對機(jī)器人路徑規(guī)劃的優(yōu)化。通過在機(jī)器人上裝置傳感器從而滿足對周圍環(huán)境進(jìn)行探測，通過對外界障礙物的位置進(jìn)行感知可以有效改變運(yùn)動路徑，規(guī)避障礙物從而實現(xiàn)避障[4-5]。

在路徑規(guī)劃中可以分為傳統(tǒng)的路徑規(guī)劃算法和智能規(guī)劃算法兩大類[6]。在實際規(guī)劃中，通常有衍生出各算法的改進(jìn)算法以及混合算法[7]。機(jī)器人路徑規(guī)劃中最基礎(chǔ)的算法為遺傳算法，該算法是一種使用隨機(jī)迭代進(jìn)行搜索運(yùn)動路徑的規(guī)劃方法[8]。該算法引用生物遺傳學(xué)對自然法則進(jìn)行延伸并在路徑規(guī)劃中廣泛應(yīng)用[9]，通過消除迭代過程中不滿足的因素，能夠?qū)崿F(xiàn)最優(yōu)路徑的搜索[10]。該算法在解碼種群適應(yīng)度函數(shù)時會存在較大的計算量，從而導(dǎo)致系統(tǒng)處理時間較長，效率低下。改進(jìn)算法主要是對算法中適應(yīng)度函數(shù)問題進(jìn)行改進(jìn)[11]。鯨魚算法主要是對鯨魚的群體捕食方法進(jìn)行模擬。

文獻(xiàn)[3]運(yùn)用傳統(tǒng)遺傳算法對行走機(jī)器人的路徑進(jìn)行規(guī)劃，使用該算法一般會存在收斂耗時較長、結(jié)果不穩(wěn)定等規(guī)劃問題。

文獻(xiàn)[7]中使用了鯨魚優(yōu)化法來對機(jī)器人進(jìn)行路徑規(guī)劃，該算法通過反復(fù)迭代來搜索目標(biāo)，但是對于路徑復(fù)雜情況，此算法迭代次數(shù)過多，不能快速地搜索到最終目標(biāo)。

為彌補(bǔ)傳統(tǒng)遺傳算法的不足，筆者將改進(jìn)遺傳算法和鯨魚優(yōu)化法融合，增強(qiáng)移動機(jī)器人路徑規(guī)劃對動態(tài)環(huán)境的適應(yīng)性能，以提高原算法的求解速度和準(zhǔn)確率。

1 環(huán)境建模

根據(jù)現(xiàn)實環(huán)境構(gòu)建仿真環(huán)境來進(jìn)行機(jī)器人的路徑規(guī)劃[12]。對于環(huán)境模型的創(chuàng)建不僅需要對其機(jī)器人實際移動路徑有客觀真實的反映，同時需要賦予算法良好的魯棒性和穩(wěn)定性。魯棒性即針對創(chuàng)建的環(huán)境或構(gòu)建的系統(tǒng)及規(guī)劃流程本體變化所能保持的能力。穩(wěn)定性即為構(gòu)建的系統(tǒng)針對初始條件變化后自身所能保持的能力。為達(dá)到環(huán)境建模目的需要制定必要措施：

1)當(dāng)設(shè)定機(jī)器人處在二維平面移動時，機(jī)器人運(yùn)動時可將其視為具有尺寸的圓在平面中進(jìn)行移動，不再考慮三維環(huán)境中的高度因素。

2)若二維平面中兩個障礙物間的距離小于圓的直徑(機(jī)器人長寬尺寸)，則視其為整體障礙物，不能滿足機(jī)器人通過。

3)路徑規(guī)劃過程使用網(wǎng)格設(shè)定機(jī)器人整體運(yùn)動區(qū)間，建立二維結(jié)構(gòu)化空間后，將障礙物網(wǎng)格和自動空間網(wǎng)格進(jìn)行區(qū)分，如圖1所示，圖中所有陰影區(qū)域為障礙物網(wǎng)格，其余為自由網(wǎng)格，每個網(wǎng)格尺寸相同，并適當(dāng)選取2個位置點設(shè)定為機(jī)器人起始點(start)和目標(biāo)點(target point)進(jìn)行機(jī)器人路徑規(guī)劃前提。

圖1 環(huán)境模型Fig. 1 Environment model

2 使用融合算法進(jìn)行路徑規(guī)劃

采用鯨魚算法與改進(jìn)算法結(jié)合，預(yù)先使用鯨魚算法對種群進(jìn)行整體優(yōu)化，提高整體種群質(zhì)量；使用改進(jìn)算法與鯨魚算法相融合尋求最優(yōu)解，可以有效解決遺傳算法中存在的收斂耗時長，優(yōu)化結(jié)果不穩(wěn)定等規(guī)劃時產(chǎn)生的問題，更快實現(xiàn)搜索目標(biāo)提煉出最優(yōu)算子，同時也可提高遺傳算法的準(zhǔn)確率。

2.1 改進(jìn)遺傳算法

傳統(tǒng)的遺傳算法在對適應(yīng)度函數(shù)進(jìn)行求解時需要進(jìn)行大量的計算，改進(jìn)算法即是使用種群差異度之和的均值對適應(yīng)度函數(shù)進(jìn)行改進(jìn)，改進(jìn)遺傳算法能運(yùn)用于全局，加快機(jī)器人到達(dá)目標(biāo)點的時間[13]。

2.1.1 改進(jìn)遺傳算法的設(shè)計

為使目標(biāo)函數(shù)最小化，將其定義為

(1)

運(yùn)用差異度函數(shù)D(t)，適應(yīng)度函數(shù)為D(t)與Fit的乘積,產(chǎn)生的差異度是：

(2)

(3)

其中xik和xjk二者代表個體xi和xj第k位的值。

D(t)表示除t以外群體差異度之和的均值：

(4)

適應(yīng)度函數(shù)是：

(5)

2.1.2 選擇算子

遺傳算法中選擇算子是從群體中選擇個體優(yōu)良、排除劣質(zhì)，它通過個體適應(yīng)性能評估后將劣質(zhì)個體替換掉，保存優(yōu)秀個體[14]。具體步驟如下：

Step1：對種群適應(yīng)度數(shù)值F進(jìn)行統(tǒng)計，對最短和最長路徑Fmin，F(xiàn)max的適應(yīng)度值分別進(jìn)行記錄。

Step2：F′即在[Fmin，F(xiàn)max]區(qū)間內(nèi)出現(xiàn)。

Step3：依次用F′與各個體的數(shù)值進(jìn)行比較，得出高個體和低個體。

Step4：將Sep3中的個體進(jìn)行替換，即高個體替換低個體。

Step5：循環(huán)上述步驟，直到得出高個體數(shù)目。

通過上述步驟選擇保存優(yōu)勝個體數(shù)，使種群多樣性得到保障且避免算法提前收斂結(jié)束。

2.1.3 交叉算子

研究中使用交叉算子中的兩點交叉，使用該算子進(jìn)行編碼時可以在兩點交叉后對部分基因進(jìn)行交換。具體操作步驟為：

1)隨機(jī)設(shè)置兩兩相配的編碼交叉點。

2)將兩個交叉點之間的部分個體進(jìn)行交換。

2.1.4 修正算子

在機(jī)器人運(yùn)行空間中，若只通過隨機(jī)取值不易得到可靠路徑，需要多次重復(fù)算子，此時需要修正算子。由沿墻導(dǎo)航法可知在對未知路徑進(jìn)行修正時，需要通過檢測不同路徑擇優(yōu)選取可行路徑，再對存在障礙物的路徑段進(jìn)行修正[15]。

2.1.5 優(yōu)化算子

在使用改進(jìn)遺傳算法對機(jī)器人路徑進(jìn)行規(guī)劃時，有時會出現(xiàn)上代種群適應(yīng)度會優(yōu)于下代適應(yīng)度的情況。為更好選出最優(yōu)適應(yīng)度算子，一般運(yùn)用個體保留法，即將上下代中的最優(yōu)個體進(jìn)行比較，如果上代個體更優(yōu)，則記錄上代最優(yōu)個體為當(dāng)前最優(yōu)個體。反之，使用下代最優(yōu)個體對當(dāng)前最優(yōu)個體進(jìn)行替換，從而可以良好保持種群的進(jìn)化。

2.2 鯨魚優(yōu)化算法

該算法通過對鯨魚群體捕獵進(jìn)行研究提出的一種算法，對捕獵過程進(jìn)行模擬。根據(jù)鯨魚捕食的搜索策略，此算法不需大規(guī)模網(wǎng)絡(luò)搜索，經(jīng)過多次送代實現(xiàn)收斂的最優(yōu)解。使用該優(yōu)化方法的參數(shù)較少且容易布局，擁有科學(xué)的局部優(yōu)化機(jī)制且可實現(xiàn)全局智能搜索。

2.2.1 包圍獵物

通過不斷接近或者圍捕獵物位置，當(dāng)最佳座頭鯨位置產(chǎn)生后其他搜索將向該位置靠近，其公式為

(6)

(7)

式中：A，C分別代表變量的系數(shù)；X*(j)指代最優(yōu)鯨魚位；X(j)為當(dāng)前鯨魚位；j為進(jìn)行迭代搜索的次數(shù)。A和C的求解公式為

A=2a×r-a，

(8)

C=2r，

(9)

式(8)和(9)中a是一個常數(shù)，其區(qū)間為[0,2]，以遞減形式呈現(xiàn)，更新方式為

(10)

其中M代表最終迭代次數(shù)，r的取值范圍是0～1。

2.2.2 發(fā)泡網(wǎng)

主要針對鯨魚吐氣泡的捕食方式進(jìn)行數(shù)字模擬。

1)包圍并收縮：將式(8)中的a值進(jìn)行減少，A的區(qū)間原定為[-a，a]，a的取值會隨著包圍范圍大小變化而改變，當(dāng)a為確定數(shù)值時即確定了包圍位置和收縮范圍。

2)螺旋式位置更新：分析出鯨魚群體位置，然后計算獵物具體位置，引入螺旋式位置

X(m+1)=D′eblcos(2πd)+X*(m)，

(11)

(12)

式中：b為常數(shù)；D′為鯨群與獵物間距離；m范圍為[-1,1]。

捕獵時，鯨魚通過螺旋游動逼近獵物并不斷壓縮范圍，位置更新閱值為1/2時公式為

(13)

式中p為[0,1]上的任意數(shù)值。

2.2.3 搜索獵物

鯨魚一般在特定范圍內(nèi)進(jìn)行隨機(jī)捕獵食物，只需捕捉位置最近的獵物而并非要捕食每個鯨魚的目標(biāo)獵物。因此，當(dāng)A不在[-1,1]時，鯨魚會放棄之前的意向目標(biāo)轉(zhuǎn)為捕捉與自身位置最近的目標(biāo)獵物。公式為

(14)

(15)

式(14)與(15)中Xrand表示鯨魚個體隨機(jī)位置。

2.2.4 移動機(jī)器人路徑規(guī)劃步驟

Step 1：設(shè)定種群的數(shù)量規(guī)模X，并隨機(jī)分布鯨魚的位置點。

Step2：對每只鯨魚各自的適應(yīng)度值進(jìn)行計算并進(jìn)行對比，獲取適應(yīng)度值最優(yōu)的個體X′。

step3：當(dāng)P<0.5且A<1，則鯨魚群體中每個個體均以公式(6)來實現(xiàn)位置點的變化，否則按照公式(15)更新鯨魚個體位置。如果P≥0.5，則運(yùn)用公式(13)更新。

Step4：在全局最優(yōu)狀態(tài)下對鯨魚種群進(jìn)行重新評估，獲取鯨魚及其各自位置信息。

Step5：若達(dá)到該算法的終止條件則停止迭代，獲取最大迭代次數(shù)；若未達(dá)到終止條件會繼續(xù)轉(zhuǎn)入Step2中進(jìn)行再次迭代。

step6：輸出全局最優(yōu)解X。

3 仿真研究

3.1 靜態(tài)環(huán)境路徑規(guī)劃仿真

圖2 在靜態(tài)環(huán)境下的3種算法的路徑仿真對比Fig. 2 Comparison of the path simulation of three algorithms in static environment

圖3 適應(yīng)度函數(shù)曲線Fig. 3 Adaptability function curve

表1 3種算法位移與時間對比

通過分析實驗數(shù)據(jù)可知，將優(yōu)化后的兩種算法結(jié)合能夠大幅度提升收斂速度并且可避免陷入局部循環(huán)，綜合運(yùn)用兩種模式搜索移動機(jī)器人最優(yōu)路徑時，產(chǎn)生的效果要優(yōu)于傳統(tǒng)的遺傳算法和改進(jìn)遺傳算法。

3.2 動態(tài)環(huán)境路徑規(guī)劃仿真

仿真實驗中同樣采用柵格環(huán)境，設(shè)定機(jī)器人傳感器探測半徑為1 m，機(jī)器人與環(huán)境中存在的障礙物之間的安全閾值為0.1 m，設(shè)定2個動態(tài)障礙物為D1，D2。其中D1的運(yùn)動路徑為圖中綠色標(biāo)識，D2運(yùn)動路徑為藍(lán)色標(biāo)識，2個動態(tài)障礙物勻速往返于各自設(shè)定軌跡。對于機(jī)器人在遇到上述2個障礙物的情形下，采用3種算法規(guī)劃全局路徑。

經(jīng)過matlab軟件對機(jī)器人運(yùn)動路徑在動態(tài)環(huán)境下仿真試驗分析后，3種算法規(guī)劃出的最佳運(yùn)動路徑分別如圖4(a)(b)(c)所示，動態(tài)仿真適應(yīng)度函數(shù)曲線如圖5所示。

圖4 在動態(tài)環(huán)境下的3種算法的路徑仿真對比Fig. 4 Comparison of the path simulation of three algorithms in dynamic environment

圖5 適應(yīng)度函數(shù)曲線Fig. 5 Adaptability function curve

表2 位移與時間對比

4 結(jié) 語

通過運(yùn)用改進(jìn)遺傳算法與鯨魚算法結(jié)合并通過設(shè)定的靜態(tài)障礙物環(huán)境和動態(tài)障礙物環(huán)境2種狀態(tài)下對機(jī)器人進(jìn)行路徑規(guī)劃試驗。機(jī)器人運(yùn)動路徑規(guī)劃分別運(yùn)用遺傳算法、改進(jìn)遺傳算法、融合算法3種方法進(jìn)行仿真實驗，并通過試驗對比驗證了融合算法自身的優(yōu)越性。減少了迭代次數(shù)，縮短了機(jī)器人路徑規(guī)劃時長，并實現(xiàn)了機(jī)器人運(yùn)動路徑的位移長度縮短，從而達(dá)到了最佳路徑規(guī)劃目的?，F(xiàn)實路徑規(guī)劃存在于動態(tài)環(huán)境中，障礙物都有一定程度的復(fù)雜因素，深入探索復(fù)雜環(huán)境，實時反饋傳感器信息，提升路徑規(guī)劃，進(jìn)一步優(yōu)化算法是未來研究方向。