王志俊

（山西建筑職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，山西 太原 030006）

1 引言

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

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

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

2 個(gè)體動(dòng)態(tài)細(xì)化分工花授粉算法

2.1 花授粉算法

花朵授粉存在自花授粉和異化授粉兩種方式，自花授粉是指花粉成熟后傳播到自身植株上，異化授粉是指花粉以蜜蜂等動(dòng)物攜帶的方式傳播到其他植株上，傳播范圍較廣。模擬花授粉行為，將自花授粉視為局部搜索，將異化授粉視為全局搜索，因而出現(xiàn)了花授粉算法。花授粉算法核心思想為：設(shè)置一個(gè)轉(zhuǎn)換概率p和隨機(jī)數(shù) rand∈（0，1），當(dāng) rand＞p則進(jìn)行全局搜索，若 rand≤p則進(jìn)行局部搜索[8]。

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

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

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

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

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

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

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

2.2 個(gè)體動(dòng)態(tài)細(xì)化分工

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

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

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

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

2.3 優(yōu)等個(gè)體改進(jìn)的搜索方式

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

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

2.4 改進(jìn)花授粉算法流程

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

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

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

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

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

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

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

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

3.1 三次樣條插值法

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

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

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

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

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

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

式中：（xi，yi）—插值點(diǎn)坐標(biāo)。

為了方便進(jìn)行碰撞判斷，將所有障礙物膨脹為圓形，碰撞標(biāo)志變量P計(jì)算方法為：

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

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

3.3 路徑規(guī)劃流程

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

4 仿真驗(yàn)證與分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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