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

謝沖沖，李 瑩

(昆明理工大學機電工程學院，昆明 650504)

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

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

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

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

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

1 環(huán)境建模

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

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

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

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

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

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

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

2.1 改進遺傳算法

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

2.1.1 改進遺傳算法的設計

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

(1)

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

(2)

(3)

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

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

(4)

適應度函數(shù)是：

(5)

2.1.2 選擇算子

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

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

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

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

Step4：將Sep3中的個體進行替換，即高個體替換低個體。

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

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

2.1.3 交叉算子

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

1)隨機設置兩兩相配的編碼交叉點。

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

2.1.4 修正算子

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

2.1.5 優(yōu)化算子

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

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

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

2.2.1 包圍獵物

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

(6)

(7)

式中：A，C分別代表變量的系數(shù)；X*(j)指代最優(yōu)鯨魚位；X(j)為當前鯨魚位；j為進行迭代搜索的次數(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)

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

1)包圍并收縮：將式(8)中的a值進行減少，A的區(qū)間原定為[-a，a]，a的取值會隨著包圍范圍大小變化而改變，當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)進行隨機捕獵食物，只需捕捉位置最近的獵物而并非要捕食每個鯨魚的目標獵物。因此，當A不在[-1,1]時，鯨魚會放棄之前的意向目標轉為捕捉與自身位置最近的目標獵物。公式為

(14)

(15)

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

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

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

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

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

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

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

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 適應度函數(shù)曲線Fig. 3 Adaptability function curve

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

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

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

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

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

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

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

表2 位移與時間對比

4 結 語

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