謝沖沖，李 瑩

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

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

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

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

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

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

1 環(huán)境建模

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)

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

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

(4)

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

(5)

2.1.2 選擇算子

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

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

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

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

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

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

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

2.1.3 交叉算子

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

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

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

2.1.4 修正算子

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

2.1.5 優(yōu)化算子

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

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

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

2.2.1 包圍獵物

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

(6)

(7)

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

A=2a×r-a，

(8)

C=2r，

(9)

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

(10)

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

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

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

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

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

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

(11)

(12)

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

捕獵時(shí)，鯨魚(yú)通過(guò)螺旋游動(dòng)逼近獵物并不斷壓縮范圍，位置更新閱值為1/2時(shí)公式為

(13)

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

2.2.3 搜索獵物

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

(14)

(15)

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

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

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

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

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

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

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

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

3 仿真研究

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

圖2 在靜態(tài)環(huán)境下的3種算法的路徑仿真對(duì)比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í)間對(duì)比

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

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

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

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

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

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

表2 位移與時(shí)間對(duì)比

4 結(jié) 語(yǔ)

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