機器人導航路徑的動態(tài)細化分工花授粉算法規(guī)劃

王志俊

（山西建筑職業(yè)技術學院計算機工程系，山西 太原 030006）

1 引言

當前機器人應用領域越來越廣泛，包括工農(nóng)業(yè)生產(chǎn)、生活服務、軍事領域等，不僅將人類從繁重生產(chǎn)勞動中解放出來，而且可以高效高質量完成生產(chǎn)任務。機器人導航方法決定了機器人工作效率和安全性，包括目標定位、環(huán)境建模、路徑規(guī)劃等三個方面[1]，研究的是路徑規(guī)劃這一關鍵技術，旨在提高機器人行走效率和順滑性。

根據(jù)路徑規(guī)劃方法提出時間，一般將路徑規(guī)劃分為傳統(tǒng)方法和智能規(guī)劃方法，傳統(tǒng)規(guī)劃方法有柵格法、可視圖法、拓撲法、人工勢場法等[2-3]，智能規(guī)劃方法有遺傳算法、神經(jīng)網(wǎng)絡、混合算法等[4-5]。智能規(guī)劃方法的效果與環(huán)境適應性明顯優(yōu)于傳統(tǒng)方法，而傳統(tǒng)算法高效的環(huán)境建模方法和面對機器的可識別性具有借鑒價值，因此傳統(tǒng)規(guī)劃方法與智能規(guī)劃方法的結合成為了一個研究方向。文獻[6]將蝗蟲優(yōu)化算法與柵格環(huán)境法結合，使用Pareto 最優(yōu)準則給出了路徑長度、平滑度、安全性的多目標優(yōu)化解；文獻[7]將遺傳算法與人工勢場法相結合，使用遺傳算法規(guī)劃靜態(tài)全局最優(yōu)路徑，使用人工勢場法實現(xiàn)動態(tài)避障，可以實現(xiàn)動態(tài)環(huán)境下路徑規(guī)劃?？v觀各種智能規(guī)劃方法，路徑性能主要取決于算法性能，但是單一算法皆具有局限性，新算法提出、現(xiàn)有算法性能升級、多算法優(yōu)勢互補融合成了當前的熱門研究方向。

研究了機器人在靜態(tài)環(huán)境下的路徑規(guī)劃問題，通過改善現(xiàn)有算法性能達到減小路徑長度的目的。以花授粉算法為基礎，將花粉劃分為精英個體、優(yōu)等個體、差等個體，精英個體引領算法進化方向，優(yōu)等個體負值尋優(yōu)搜索，差等個體通過柯西變異逃出局部最優(yōu)。使用個體動態(tài)細化分工花授粉算法進行路徑規(guī)劃，達到了減少路徑長度的目的。

2 個體動態(tài)細化分工花授粉算法

2.1 花授粉算法

花朵授粉存在自花授粉和異化授粉兩種方式，自花授粉是指花粉成熟后傳播到自身植株上，異化授粉是指花粉以蜜蜂等動物攜帶的方式傳播到其他植株上，傳播范圍較廣。模擬花授粉行為，將自花授粉視為局部搜索，將異化授粉視為全局搜索，因而出現(xiàn)了花授粉算法?；ㄊ诜鬯惴ê诵乃枷霝椋涸O置一個轉換概率p和隨機數(shù) rand∈（0，1），當 rand＞p則進行全局搜索，若 rand≤p則進行局部搜索[8]。

（1）全局搜索。全局搜索模擬Levy飛行方式進行位置更新[9]，方法為：

式中：λ=1.5，Γ（λ）—標準 gamma 函數(shù)；s—利用 Mantegna 算法產(chǎn)生的步長，即：

式中：v—N（0，1）；μ—N（0，σ2），方差 σ2的計算方法為：

（2）局部搜索。局部搜索以異于自身的兩個花粉差分為牽引，即：

（3）貪婪選擇?；ǚ勖扛乱徊剑瑒t判斷更新前后位置優(yōu)劣，并根據(jù)貪婪準則選擇[10]。記f（）為目標函數(shù)，目標函數(shù)越小則花粉位置越優(yōu)。當時進行位置更新，否則不進行位置更新?；ǚ畚恢酶潞筮M行全局最優(yōu)判斷，若則更新全局最優(yōu)，否則不更新。

（4）算法結束條件。當所有花粉完成一次迭代時才進入下一輪迭代，當?shù)螖?shù)達到最大迭代次數(shù)Tmax時算法停止，輸出全局最優(yōu)即為花粉最優(yōu)位置。

通過以上介紹可以看出，花授粉算法依據(jù)隨機數(shù)選擇授粉方式，種群內個體位置更新方式完全一致，沒有進行細致分工。另外，算法后期多數(shù)花粉在全局最優(yōu)牽引下向其接近，不僅使種群多樣性降低，而且位置更新能力極低。為了解決以上問題，使用動態(tài)細化分工方法和改進搜索策略進行改進，提出了個體動態(tài)細化分工的花授粉算法。

2.2 個體動態(tài)細化分工

原始花授粉算法中，僅僅依賴概率分為自花傳播和異花傳播，單一而固定的位置更新方式容易破壞算法多樣性，且難以跳出局部最優(yōu)。為了解決以上問題，將種群內個體任務進行細致分工。根據(jù)目標函數(shù)值將花粉劃分為精英個體、優(yōu)等個體和差等個體，精英個體指全局最優(yōu)解，用于引領進化方向；優(yōu)等個體指排名靠前的花粉，按照傳統(tǒng)方式進行更新搜索；差等個體使用柯西變異負責跳出局部最優(yōu)。

（1）精英個體引領進化方向。根據(jù)式（1），將精英個體代入后有這意味著全局最優(yōu)解完全失去了進化能力，為了保持全局最優(yōu)解的進化能力，同時起到引領種群進化的作用，對精英個體更新方法進行改進。實驗研究表明，種群進化具有的一定的規(guī)律和方向性，連續(xù)兩次迭代的最優(yōu)解連線及其延長線上，必有部分點接近下次迭代最優(yōu)解。由此，精英個體的更新方法為：

（2）差等個體柯西變異跳出局部最優(yōu)?；ㄊ诜鬯惴ㄔ诘笃诘倪M化能力弱，容易陷入局部最優(yōu)但是沒有跳出機制。種群中較差個體的位置更新價值和借鑒價值極小，因此使用柯西變異的方法使差等花粉的目標函數(shù)值快速改變，以柯西變異方式產(chǎn)生新的種群最優(yōu)，產(chǎn)生新的更新中心點，達到跳出局部最優(yōu)的目的?？挛髯儺惙椒椋?/p>

式中：C（0，1）—柯西分布。

2.3 優(yōu)等個體改進的搜索方式

前文中提到，優(yōu)等個體使用傳統(tǒng)搜索方式進行位置更新，但是隨著迭代的進行，花粉以當前全局最優(yōu)解為中心進行聚集，此時式（1）中的值極小，則這意味著隨著算法的迭代，粒子的更新能力和進化能力極弱，使花授粉算法陷入局部最優(yōu)的僵局。為了使算法在迭代過程中保持更新和進化活力，提出了搜索策略動態(tài)調整方法：

式中：T—最大迭代次數(shù)；t—當前迭代次數(shù)；Xs—隨機選擇的異于Xi的花粉，為第t次迭代的位置中心。分析式（7）可知，算法前期主要依賴全局最優(yōu)進行引導更新，算法后期為了保持更新和進化能力，主要依賴位置中心與個體差分進行引導，使花粉在整個迭代過程中都能夠保持進化活力。

2.4 改進花授粉算法流程

將個體動態(tài)細化分工和改進搜索方式融入到花授粉算法中，得到個體動態(tài)細化分工花授粉算法（Individual Dynamic Refine Division Flower Pollination Algorithm，IDRDFPA）步驟為：

（1）初始化算法參數(shù)，包括最大迭代次數(shù)T、種群規(guī)模Size、轉換概率p、花粉移動范圍Range；

（2）初始化花粉位置，按照花粉位置的目標函數(shù)值進行排序，將花粉區(qū)分為精英個體、優(yōu)等個體、差等個體；

（3）精英個體按式（5）進行位置更新，差等個體按式（6）進行柯西變異；優(yōu)等個體按式（4）和式（7）進行搜索；位置每更新一次，同時判斷是否更新全局最優(yōu)位置；

（4）判斷一次迭代中是否所有花粉完成位置更新，若是則進入（5），否則轉至（3）；

（5）判斷是否達到最大迭代次數(shù)，若否則轉至（3）；若是則輸出全局最優(yōu)解，算法結束。

3 路徑規(guī)劃建模及流程

機器人在簡單或復雜環(huán)境下經(jīng)過若干次轉彎能夠達到避障效果，轉彎點即為路徑結點?；趥€體動態(tài)細化分工花授粉算法的機器人路徑規(guī)劃思路為：根據(jù)環(huán)境中障礙物分布確定路徑節(jié)點數(shù)量，使用三次樣條插值法確定插值點數(shù)量、位置并形成規(guī)劃路徑。花授粉算法的作用是搜索最優(yōu)的路徑結點位置，使規(guī)劃路徑最短。

3.1 三次樣條插值法

三次樣條插值法使用一系列三次多項式的插值點區(qū)間，形成一條平滑的行駛路徑，使機器人經(jīng)過路徑結點時具有良好的動力學特性。假設在［a，b］上等距離插入n+1 個點a=x0＜x1＜L＜xn=b，插入點函數(shù)值為f（xi）=fi，i=0，1，L，n，三次樣條插值函數(shù)s（x）需滿足三個條件[11]：（1）s（x）在區(qū)間［a，b］上二階連續(xù)；（2）s（xi）=fi，i=0，1，L，n；（3）s（x）在每個［xi，xi+1］區(qū)間上為三次多項式。則在區(qū)間［xi，xi+1］上s（x）表示為：

式中：ai、bi、ci、di—多項式系數(shù)，s（x）在區(qū)間［a，b］上共4n個未知系數(shù)，共需4n個確定條件。

3.2 編碼方法及目標函數(shù)

以每個花粉的編碼作為一組路徑結點，根據(jù)環(huán)境中障礙物分布和起點、終點位置確定路徑結點數(shù)量m，使用改進花授粉算法搜索最優(yōu)路徑結點，由此可知一條路徑上m個路徑結點橫坐標構成了花粉的m維橫坐標，路徑上m個路徑結點縱坐標構成了花粉的m維縱坐標。基于以上分析，將花粉編碼為［（xi1，xi2，L，xim），（yi1，yi2，L，yim）］，其中（xim，yim）表示花粉i搜索到的第m個路徑結點。

設定的路徑規(guī)劃目標為：在滿足避障要求的情況下，規(guī)劃出最短的行駛路徑。目標函數(shù)圍繞避障和路徑最短兩個規(guī)劃目標，構造為：

式中：L—路徑長度；P—機器人碰撞標志變量；β—足夠大的系數(shù)，用于排除發(fā)生碰撞的路徑，在此取為β=100。路徑長度L為：

式中：（xi，yi）—插值點坐標。

為了方便進行碰撞判斷，將所有障礙物膨脹為圓形，碰撞標志變量P計算方法為：

式中：（xobsk，yobsk）—第k個障礙物圓心；（xi，yi）—插值點坐標；dk—插值點與第k個障礙物的距離最小值；robsk—第k個障礙物的半徑；θk—軌跡與第k個障礙物的碰撞標志值；nobs—所有障礙物數(shù)量。

分析式（11）可知，當存在某一插入點與障礙物中心距離小于障礙物半徑時，此時機器人與障礙物發(fā)生碰撞，同時θk＞0，則P＞0，結合式（9）在系數(shù) β 的放大作用下，有z＝L（1+βP）＞＞L，此時z值較大，不會成為最優(yōu)路徑。當所有插入點與障礙物不發(fā)生碰撞時，θk＝0，P＝0，1+βP＝0，此時z=L，長度最短的無碰路徑即為最優(yōu)路徑。

3.3 路徑規(guī)劃流程

結合三次樣條插入法原理、改進花授粉算法原理、花粉編碼方法及建立的目標函數(shù)模型，制定路徑規(guī)劃流程如下：（1）根據(jù)路徑起點、終點及障礙物分布情況確定路徑結點數(shù)量m和插入點數(shù)量n；初始化改進花授粉算法參數(shù)；（2）調用前文給出的改進花授粉算法，分精英花粉、優(yōu)等花粉和差等花粉分別進行位置更新；（3）根據(jù)迭代后的花粉位置和三次樣條插值法，確定插值點橫縱坐標；根據(jù)式（9）計算花粉迭代后位置的目標函數(shù)值，依據(jù)目標函數(shù)值判斷是否進行位置更新；（4）若算法迭代次數(shù)未達到最大值，則轉至（2）繼續(xù)迭代；若算法達到最大迭代次數(shù)，則算法結束，同時輸出全局最優(yōu)路徑。

4 仿真驗證與分析

分別在簡單環(huán)境和復雜環(huán)境下對個體動態(tài)細化分工花授粉算法的規(guī)劃性能進行驗證，同時使用傳統(tǒng)花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）、個體動態(tài)細化分工花授粉算法（IDRDFPA）、文獻[10]的改進蝙蝠算法（UGBA）進行路徑規(guī)劃，仿真運行環(huán)境為Windows7，編程環(huán)境為Matlab R2014a。為了保證公平公正，算法共有的參數(shù)設置為相同值，種群規(guī)模Size=30，最大迭代次數(shù)T=500，轉換概率p=0.8。改進蝙蝠算法的種群規(guī)模、最大迭代次數(shù)與花授粉算法一致，其余參數(shù)與文獻[12]保持不變。

4.1 簡單環(huán)境下規(guī)劃性能驗證

在簡單環(huán)境下，設置6 個圓形障礙物，根據(jù)障礙物、起點和終點分布情況，將路徑結點數(shù)設置為3，插值點數(shù)設置為100。為了防止隨機性對實驗結果影響，分別使用FPA 算法、IDRDFPA算法、UGBA 算法各自獨立運行30 次，取各算法的最優(yōu)結果進行展示。運行結果，如圖1 所示。

圖1 簡單環(huán)境下各算法搜索的最優(yōu)路徑Fig.1 Optimal Path Searched by Different Algorithm Under Simple Environment

從圖1 中可以直觀看出，IDRDFPA 算法搜索的路徑最短且平滑，而另外兩個算法搜索的路徑存在明顯的曲折部分。算法對最優(yōu)路徑的搜索過程中，目標函數(shù)值隨迭代過程的變化曲線，如圖2 所示。從圖中可以看出，提出的IDRDFPA 算法最早搜索到最優(yōu)路徑，迭代次數(shù)為82 次；UGBA 和FPA 搜索到最優(yōu)路徑時的迭代次數(shù)相差不大，都迭代了200 次左右。從最優(yōu)路徑質量上講，IDRDFPA 算法規(guī)劃的路徑質量最好，其次為UGBA 算法，F(xiàn)PA 算法規(guī)劃路徑質量最差。為了比較三種算法的性能穩(wěn)定性，統(tǒng)計30 次獨立運行的最優(yōu)值、最差值和平均值結果，如表1 所示。從表中可以看出，提出的IDRDFPA 算法搜索的路徑質量最高，而且穩(wěn)定性最好。UGBA 算法的最優(yōu)解質量優(yōu)于FPA 算法，但是最差解和平均值差于FPA 算法，說明UGBA 算法的穩(wěn)定性比FPA 算法差。綜上所述，在簡單環(huán)境下，IDRDFPA 算法的最優(yōu)解質量、算法穩(wěn)定性和收斂速度均優(yōu)于另外兩種算法。

圖2 簡單環(huán)境下各算法迭代過程Fig.2 Iteration Process of Different Algorithm Under Simple Environment

表1 簡單環(huán)境下各算法搜索的路徑統(tǒng)計Tab.1 Path Statistics Searched by Different Algorithm Under Simple Environment

4.2 復雜環(huán)境下規(guī)劃性能驗證

在復雜環(huán)境下，設置11 個圓形障礙物，根據(jù)障礙物、起點和終點分布情況，將路徑結點數(shù)設置為4，插值點數(shù)設置為100。為了防止隨機性對實驗結果影響，分別使用FPA 算法、IDRDFPA算法、UGBA 算法各自獨立運行30 次，取各算法的最優(yōu)結果進行展示。運行結果，如圖3 所示。從圖3 中可以直觀看出，在復雜環(huán)境下IDRDFPA 算法搜索的路徑最短，算法對最優(yōu)路徑的搜索過程中，目標函數(shù)值隨迭代過程的變化曲線與簡單環(huán)境下相似，這里不再給出。為了比較三種算法在復雜環(huán)境中的性能穩(wěn)定性，統(tǒng)計30 次獨立運行的最優(yōu)值、最差值和平均值結果，如表2 所示。從表2 中可以看出，IDRDFPA 算法搜索的最優(yōu)路徑長度為8.8446，比UGBA 算法和FPA 算法分別減少了5.93%和9.86%。從最優(yōu)值、最差值和平均值看，IDRDFPA 算法具有最佳的穩(wěn)定性，其次為FPA 算法，UGBA 算法的穩(wěn)定性最差。綜上所述，在簡單環(huán)境或者復雜環(huán)境下，IDRDFPA 算法具有最好的尋優(yōu)能力、最快的收斂速度、最佳的穩(wěn)定性。這是因為對花粉個體的分工進行細化，使精英個體引領進化方向，差等個體通過變異跳出局部最優(yōu)，優(yōu)等個體使用改進搜索方式尋優(yōu)，不同花粉之間協(xié)調配合，提高了算法尋優(yōu)能力、收斂速度和穩(wěn)定性。

圖3 復雜環(huán)境下各算法搜索的最優(yōu)路徑Fig.3 Optimal Path Searched by Different Algorithm Under Complex Environment

表2 復雜環(huán)境下各算法搜索的路徑統(tǒng)計Tab.2 Path Statistics Searched by Different Algorithm Under Complex Environment

5 結論

研究了機器人在靜態(tài)環(huán)境中點對點的路徑規(guī)劃問題，提出了個體動態(tài)細化分工花授粉算法，使用改進花授粉算法搜索最優(yōu)路徑結點，而后使用三次樣條插值法規(guī)劃出最優(yōu)路徑。經(jīng)仿真得出以下結論：（1）差等個體的柯西變異可以使算法有效跳出局部最優(yōu)；（2）優(yōu)等個體改進的搜索方式可以保持算法長期的更新能力和進化能力；（3）與花授粉算法相比，個體動態(tài)細化分工花授粉算法具有最好的尋優(yōu)能力、收斂速度和穩(wěn)定性。