基于HGM與TGSA的機(jī)器人路徑規(guī)劃算法研究

姚成信，王冠凌，陳孟元

(安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000)

移動(dòng)機(jī)器人路徑規(guī)劃問題就是在充滿各種障礙物的環(huán)境中，機(jī)器人遵從一定的規(guī)則(如路徑最短、耗時(shí)最短或安全度最高等)，從起點(diǎn)到終點(diǎn)獨(dú)立搜索出一條與障礙物無碰撞的最優(yōu)或者次優(yōu)路徑．因此，機(jī)器人路徑規(guī)劃問題的研究需要解決環(huán)境建模與最優(yōu)路徑搜索兩大基本問題．為解決以上路徑規(guī)劃的兩個(gè)問題，一是需要根據(jù)已知環(huán)境信息建立較為精確的環(huán)境地圖模型；二是在規(guī)模較大、環(huán)境復(fù)雜的情況下，運(yùn)用一種合適的建模方法和高效率的算法對路徑進(jìn)行規(guī)劃[1]．

自然界一直給人們帶來各種靈感與啟發(fā)，人們一直在嘗試?yán)脕碜杂谧匀唤缰械姆N種現(xiàn)象來解決許多類似的實(shí)際問題，如人工神經(jīng)網(wǎng)絡(luò)，遺傳算法，人工勢場法，粒子群算法，蟻群算法，蜂群算法，人工魚群算法等的提出和改進(jìn)都為相關(guān)問題的解決提供了很好的思路．上述算法都是基于仿生原理或者模擬自然現(xiàn)象，但從生物進(jìn)化角度來看，作為生長在生物底層的植物具有更簡單和更有效的特征，模擬植物生長過程構(gòu)建的路徑規(guī)劃算法可能會(huì)達(dá)到更好的效果．最早基于植物生長形態(tài)提出仿生計(jì)算算法是在1968年，荷蘭Utrecht大學(xué)的生物學(xué)和植物學(xué)家，匈牙利裔的林登麥伊爾(Aristid Lindenmayer)等人提出利用計(jì)算機(jī)模擬植物生長系統(tǒng)(L-systems)，主要用于分形領(lǐng)域及計(jì)算機(jī)圖形學(xué)的研究．土耳其Ali KARCI基于栽培和種植樹苗的自然過程，提出了樹苗生長算法(SGuA)．使用交配、分枝和接種三個(gè)階段來對樹苗的播種和成長過程進(jìn)行抽樣優(yōu)化，并將所提出的方法應(yīng)用于標(biāo)準(zhǔn)測試函數(shù)，結(jié)果表明該方法在尋找更好的解決方案和函數(shù)評估次數(shù)的情況下要優(yōu)于遺傳算法[2]．

國內(nèi)最早對于以植物為對象的算法的研究，是由李彤[3]等在2005年提出的模擬植物生長算法(PGSA)，主要是將該算法運(yùn)用于整數(shù)規(guī)劃問題的求解，并取得了較為滿意的效果．崔志華等人從植物的生長機(jī)制上對植物進(jìn)行研究，模擬包括光合作用、向光性、頂端優(yōu)勢這三個(gè)生長機(jī)制，提出了標(biāo)準(zhǔn)的人工植物優(yōu)化算法(APOA)，分析論證了人工植物算法的運(yùn)行機(jī)理，建立起比較科學(xué)、完整的算法研究框架，并開始初步探討了有關(guān)算法的收斂性、穩(wěn)定性和計(jì)算復(fù)雜度等一系列理論問題[4-5]．郭改文[6]等提出模擬自然樹生長的競爭算法(GCA)，并建立了自然樹生長的競爭模型．該算法具有擬合精確度高、運(yùn)行速度快、內(nèi)存占用率低等優(yōu)點(diǎn)，為優(yōu)化設(shè)計(jì)和計(jì)算等問題的解決提供了一種新的思路．周堯明[7]等提出一種基于植物生長機(jī)制的生物啟發(fā)計(jì)算算法(PGPP)，并描述其在路徑規(guī)劃中的應(yīng)用．該算法具有良好的路徑規(guī)劃能力，并提供了一種新穎的路徑規(guī)劃方法．

文中通過采用一種既考慮到全局路徑信息又考慮到行走安全性和有效性的蜂巢柵格法構(gòu)建了機(jī)器人環(huán)境地圖模型．針對利用傳統(tǒng)算法求解機(jī)器人路徑規(guī)劃時(shí)全局搜索能力差，易陷入局部最小點(diǎn)的問題，用一種新的優(yōu)化算法——生長樹算法，對原機(jī)器人路徑規(guī)劃模型進(jìn)行改進(jìn)，尋找一條更優(yōu)路徑．

1 蜂巢柵格法環(huán)境建模

圖1 移動(dòng)機(jī)器人運(yùn)行環(huán)境

在由蜂巢柵格組成的環(huán)境地圖中，環(huán)境被等分為形狀相同的六邊形柵格，文中地圖環(huán)境模型的構(gòu)建建立在由40*50的蜂巢柵格組成的二維空間平面中，且空間內(nèi)僅存在靜態(tài)障礙物，同時(shí)賦予相應(yīng)數(shù)值表示障礙物對應(yīng)的位置．假設(shè)移動(dòng)機(jī)器人運(yùn)動(dòng)區(qū)域中的起始位置為第一個(gè)蜂巢柵格B(xB,yB)、目標(biāo)位置為T(xT,yT)，區(qū)域中靜態(tài)障礙物位置及大小已知，根據(jù)區(qū)域環(huán)境地圖中的起始位置、目標(biāo)位置以及障礙物位置，以橫軸為X軸，縱軸為Y軸，構(gòu)建新的蜂巢柵格坐標(biāo)系，如圖1所示．在實(shí)際應(yīng)用中根據(jù)地面機(jī)器人的尺寸，將移動(dòng)機(jī)器人縮小為一個(gè)質(zhì)點(diǎn)，機(jī)器人在柵格地圖中的移動(dòng)看作質(zhì)點(diǎn)的移動(dòng).環(huán)境中將障礙物邊界做相應(yīng)的擴(kuò)展及模糊化處理(黑色陰影)，空白柵格表示機(jī)器人能夠自由通過的地方，圖1a代表機(jī)器人路徑的起始點(diǎn)位置，圖1b代表目標(biāo)點(diǎn)位置，這樣就將空間中機(jī)器人路徑規(guī)劃問題轉(zhuǎn)化為柵格圖中的最短路徑搜索問題，簡化了問題求解的復(fù)雜性．

2 樹生長模擬算法

2.1 算法的尋優(yōu)原理

完整的大樹包括樹干和無數(shù)的分枝，它們的生長方向始終向著太陽，這個(gè)生長的過程可以類比無數(shù)條路徑的組合；由于在陽光照射下，一些上層枝葉會(huì)對下層枝葉遮擋，產(chǎn)生的陰影可看作面積不同的障礙物；各分枝當(dāng)中最優(yōu)的向光生長過程就是最優(yōu)的路徑規(guī)劃形式．樹的頂端優(yōu)勢現(xiàn)象就是其中一條最理想的機(jī)器人路徑規(guī)劃，它描述的是從樹根到樹冠頂端的無障礙理想路徑方式．

將樹向光分枝生長的路徑過程看作是機(jī)器人路徑規(guī)劃中的全局遍歷式路徑搜索尋優(yōu)過程，決定其隨機(jī)分枝生長所獲得的光照強(qiáng)度看作一種適應(yīng)值函數(shù)，即目標(biāo)函數(shù)；光照強(qiáng)度最適宜的位置對應(yīng)到算法中為適應(yīng)值最優(yōu)的位置，即局部最優(yōu)解；最優(yōu)位置處生長出的嫩芽看成算法中進(jìn)行局部搜索的點(diǎn)；眾多不斷分枝出來的枝條看作搜索空間的路徑；樹木生長方式看作個(gè)體移動(dòng)；樹苗描述為路徑規(guī)劃的起點(diǎn)，太陽位置描述為目標(biāo)點(diǎn)，樹苗向著太陽方向不斷生長的過程看作是一條規(guī)劃起點(diǎn)到終點(diǎn)的最優(yōu)過程[8-10]．其對應(yīng)關(guān)系如表1所示．

表1樹生長模擬算法與路徑規(guī)劃問題的對應(yīng)表

路徑規(guī)劃問題的定義域[xmin,xmax]樹的生長環(huán)境算法的迭代次數(shù)t樹分枝的生長期局部最優(yōu)解(xbest,ybest)光照強(qiáng)度適宜的位置目標(biāo)函數(shù)I(i)光照強(qiáng)度算法中的一段路徑i樹的枝條機(jī)器人位置移動(dòng)(xti,yti)枝條的生長所有路徑條數(shù)m枝條的總數(shù)

2.2 尋找全局最優(yōu)解的理論依據(jù)

(1)在樹的生長過程中頂枝會(huì)不斷地分化出側(cè)枝，由于頂枝受光面積大，相比側(cè)枝生長活躍，這樣頂枝的相關(guān)性選擇機(jī)制更多，從而使各頂枝能不斷地進(jìn)行局部尋優(yōu)．

(2)生長素和光照的分布使得在枝干最優(yōu)位置點(diǎn)附近區(qū)域局部搜索的可能性更加合理，從而在最優(yōu)解周圍搜索出更優(yōu)解的可能性增大．

(3)光照的作用使得部分頂枝生長停止，側(cè)枝替代其成為頂枝，并重新生成新的側(cè)枝向光生長．這種方式能將當(dāng)前局部搜索能力較強(qiáng)的位置(頂枝)加以屏蔽，從而能迅速改變樹枝的生長方向，有效地跳出局部極值點(diǎn)進(jìn)行全局尋優(yōu)．樹向光生長有3種典型的情況，如圖2所示．圖2a表示沒有障礙物的情況，圖2b、圖2c表示具有一些障礙的情況；Bud處網(wǎng)格表示當(dāng)前樹芽，Target處網(wǎng)格表示當(dāng)前增長的終點(diǎn)，黑色的是障礙，灰色的是樹生長路徑的過程．首先，采用傾斜方式生長，如圖2a所示.樹在生長過程中沒有遇到障礙物，保持正常的向光生長；如果障礙物出現(xiàn)在生長方向上，則繞開障礙物朝目標(biāo)方向繼續(xù)生長，如圖2b所示；如果生長過程中沒有可行的方向，如圖2c所示，樹停止分枝生長，將不會(huì)進(jìn)行任何進(jìn)一步的計(jì)算．障礙處可能首先出現(xiàn)的分枝將首先生長．被障礙阻塞的其他分枝將決定是繼續(xù)增長還是停止，這取決于障礙物在哪里．

圖2 樹向光生長的3種典型情況

3 樹生長模擬算法在機(jī)器人路徑規(guī)劃中的研究應(yīng)用

3.1 路徑規(guī)劃的數(shù)學(xué)模型

在標(biāo)準(zhǔn)生長樹模型中，將光照強(qiáng)度分布在特定生長樹的區(qū)域范圍視為該生長樹模型的定義域區(qū)間，樹在生長過程中通過不斷感知區(qū)域內(nèi)不同的光照強(qiáng)度來進(jìn)行分枝-生長，最終向最佳光照方向?qū)?yōu)出最優(yōu)生長路徑．生長樹算法將優(yōu)化問題的定義域視為樹的生長環(huán)境，算法的迭代次數(shù)視為樹的生長周期．在枝芽的光合作用進(jìn)入向光性階段時(shí)，樹分別利用生長期優(yōu)化規(guī)則進(jìn)行尋優(yōu)分枝點(diǎn)；最后進(jìn)入生長尋優(yōu)階段，枝芽會(huì)在向光生長過程中根據(jù)尋優(yōu)規(guī)則完成全局遍歷式尋優(yōu)．在生長樹經(jīng)歷完整個(gè)生長周期后，算法收斂停止，找到最優(yōu)生長路徑．

圖3 蜂巢柵格坐標(biāo)圖

(1)

式中，Nx為X軸上的最大序號數(shù)，Ny為Y軸上的最大序號數(shù)．

蜂巢柵格坐標(biāo)(xi,yi)與序號i的關(guān)系可表示為：

(2)

式中,Nx1為第一奇數(shù)行最大序號數(shù)，Nx2為第一偶數(shù)行最大序號數(shù)．int表示取最大整數(shù)運(yùn)算；mod表示求余運(yùn)算．

(2)光合速率計(jì)算.首先在環(huán)境區(qū)域內(nèi)遍尋各位置處的光照強(qiáng)度及對應(yīng)的光合速率，即尋找目標(biāo)函數(shù)，式(3)表示坐標(biāo)上任意點(diǎn)(xi,yi)處枝條的光照強(qiáng)度，式(4)代表坐標(biāo)(xi,yi)位置處枝條的光合速率．

(3)

式中，kl表示光照強(qiáng)度系數(shù)，(xD,yD)是目標(biāo)點(diǎn)的位置，(xB,yB)是起始樹芽的位置．

(4)

圖4 生長素濃度與生長速率的關(guān)系

(3)隨機(jī)分枝.生物學(xué)實(shí)驗(yàn)證明，決定枝芽細(xì)胞分裂和生長的生長素信息不是每個(gè)細(xì)胞與生俱來就被賦予的，而是細(xì)胞生長系統(tǒng)從其環(huán)境中接受到了分裂生長的位置信息，根據(jù)這種信息，表現(xiàn)出明顯的向光性生長特點(diǎn)[12]．由于光照強(qiáng)度大的位置，樹生長時(shí)進(jìn)行光合速率快，生長速率快，此處生長素濃度往往處于最佳生長素點(diǎn)附近，如圖4所示.由圖4可知，芽的生長素濃度與生長速率的關(guān)系處于一個(gè)變化的過程，生長素濃度太高或者太低都會(huì)對芽的生長速率產(chǎn)生很大的影響，所以最佳芽生長素濃度位置附近最容易首先產(chǎn)生分枝，即規(guī)定光照強(qiáng)度最大位置對應(yīng)光合速率最大位置，也是最佳生長素濃度處．這也是算法中的局部最優(yōu)解處．

(5)

一旦新分枝發(fā)芽時(shí)，新枝和舊枝合二為一，均看作同一平面內(nèi)的同一枝干．

(4)模擬環(huán)境下尋優(yōu)生長.植物在生長過程中會(huì)受到許多影響，如自身頂端優(yōu)勢的影響、自然災(zāi)害(火災(zāi)、雷擊等)及人工作用(人工剪枝等)，在此為了簡單起見，一律將其分為沒有障礙和具有一些障礙兩種典型的情況．樹在生長過程中沒有遇到障礙物，保持正常的向光生長；如果障礙物出現(xiàn)在生長方向上，則另一個(gè)方向變?yōu)樯L方向；如果生長過程中沒有可用的方向，則樹停止分枝生長，將不會(huì)進(jìn)行任何進(jìn)一步的計(jì)算．障礙可能是首先出現(xiàn)的分枝．首先出現(xiàn)的分枝將首先生長．被分枝阻塞的其他分枝將決定是繼續(xù)增長還是停止，這取決于障礙物在哪里．其具體的規(guī)則如下：

式(6)表示枝條的頂芽(最優(yōu)位置)在頂端優(yōu)勢作用下生長，看作是路徑規(guī)劃中沒有遭遇障礙物模型．

(6)

式(7)表示由于上面的枝葉遮擋導(dǎo)致光合作用不足，在自然因素的作用下，樹枝隨機(jī)選擇性轉(zhuǎn)變生長方向，看作是路徑規(guī)劃中遭遇障礙物模型．

(7)

式(8)則表示側(cè)枝在向光生長過程中由于光合作用不足，生長素濃度不足以提供枝葉生長所需的能量，導(dǎo)致枝條停止生長，看作是路徑規(guī)劃中陷入障礙物模型．

(8)

針對模擬環(huán)境下尋優(yōu)生長的3種不同模型，對該算法下的最優(yōu)路徑規(guī)劃設(shè)計(jì)目標(biāo)函數(shù)為：

(9)

式中，μ1,μ2,μ3均為權(quán)值系數(shù)，用來調(diào)整尋找出一條最優(yōu)路徑．

3.2 基本算法流程

TGSA主要包括6個(gè)步驟，TGSA流程圖如圖5所示．

圖5 TGSA流程圖

4 仿真實(shí)驗(yàn)對比分析

4.1 兩種不同環(huán)境地圖下的算法對比

實(shí)驗(yàn)地圖環(huán)境模型建立在由30*30的蜂巢柵格組成的二維空間平面中．地圖中左下角處柵格為機(jī)器人的路徑起點(diǎn)，地圖中右上角處柵格為終點(diǎn)，黑色柵格為障礙物．算法仿真結(jié)果對比如圖6、圖7所示，普通柵格地圖下的機(jī)器人路徑如圖6所示，蜂巢柵格地圖下的機(jī)器人路徑如圖7所示．

在圖6、圖7中，地圖環(huán)境區(qū)域分別設(shè)置為30*30的傳統(tǒng)柵格和蜂巢柵格．障礙物全部擴(kuò)展為圓形障礙物，兩種地圖中的障礙物圓心及半徑已知，即地圖中全部靜態(tài)圓形障礙物位置已知，且全部位置對應(yīng)相同，兩種地圖中的起始位置和目標(biāo)位置均相同．

通過圖6、圖7中轉(zhuǎn)彎處位置可以看出，蜂巢柵格遇到障礙物，每次移動(dòng)方向改變的轉(zhuǎn)角為60°，相比傳統(tǒng)柵格法的90°轉(zhuǎn)角，降低了運(yùn)動(dòng)過程中轉(zhuǎn)彎帶來的安全性問題，同時(shí)單次轉(zhuǎn)彎走過的路徑總長度與無障礙時(shí)通過的直線距離比傳統(tǒng)策略更高，使得最后規(guī)劃的路徑長度要比傳統(tǒng)路徑短且安全性并不降低．同時(shí)可見，樹生長模擬算法在兩幅地圖中均能很好地繞開障礙物，從起點(diǎn)到終點(diǎn)搜索到一條最優(yōu)路徑．

圖6 柵格地圖下的路徑圖圖7 蜂巢柵格下的路徑圖

蜂巢柵格下的TGSA算法和普通柵格下的TGSA算法仿真結(jié)果對比如表2所示.30*30最優(yōu)路徑收斂曲線圖如圖8所示.由表2和圖8可以看出，蜂巢柵格下的TGSA算法相比普通柵格下的TGSA算法，迭代次數(shù)和運(yùn)行時(shí)間都有所降低，最優(yōu)路徑長度減?。?/p>

表2 蜂巢柵格下的TGSA算法和普通柵格下的TGSA算法仿真結(jié)果對比

4.2 同種環(huán)境地圖下不同算法的實(shí)驗(yàn)對比

實(shí)驗(yàn)地圖環(huán)境區(qū)域設(shè)置在30*30的蜂巢柵格中，如圖9所示．蟻群算法下的機(jī)器人路徑如圖9中粗折線所示，TGSA算法下的機(jī)器人路徑圖如圖9中細(xì)折線所示．障礙物全部擴(kuò)展為圓形障礙物，兩種地圖中的障礙物圓心及半徑已知，即地圖中全部靜態(tài)圓形障礙物位置已知，且全部位置對應(yīng)相同，兩種地圖中的起始位置和目標(biāo)位置均相同．

圖8 30*30最優(yōu)路徑收斂曲線圖圖9 蜂巢柵格下的路徑圖

仿真結(jié)果對比如表3所示.40*50最優(yōu)路徑收斂曲線圖如圖10所示.在表3和圖10中，相同規(guī)模大小的環(huán)境地圖，通過對比蟻群算法下的機(jī)器人路徑規(guī)劃，由仿真實(shí)驗(yàn)結(jié)果可以看出蜂巢柵格法下結(jié)合樹生長模擬算法具有迭代層次少，路徑長度短，規(guī)劃時(shí)間更短的優(yōu)點(diǎn)，同時(shí)樹生長模擬算法具有更快的收斂速度和全局搜索能力，使移動(dòng)機(jī)器人路徑規(guī)劃問題得到一定的提高．

表3 蟻群算法和TGSA算法仿真結(jié)果對比

圖10 40*50最優(yōu)路徑收斂曲線圖

5 結(jié)論

樹生長模擬算法不同于以往的仿生算法，它是模擬現(xiàn)實(shí)中樹木的一般生長過程，從樹木的內(nèi)在生長機(jī)理出發(fā)，打破了以往眾多其他仿生算法模型中主要以模擬自然規(guī)律或者細(xì)菌、昆蟲以及動(dòng)物的生長生活方式為主的傳統(tǒng)研究方法，為群智能計(jì)算的發(fā)展開辟了新的領(lǐng)域[13]．

植物與動(dòng)物有著不同的生長方式，植物的生長周期慢、生長區(qū)域范圍較廣，而且植物種群在一定程度上對自然的適應(yīng)能力要超過動(dòng)物群體，這些使問題研究的穩(wěn)定性和可靠性得到保證．其他生物由于生長周期短，所以一些行為必須要求在較短時(shí)間內(nèi)完成，這使得在模擬相關(guān)算法求解優(yōu)化問題時(shí)，算法收斂速度較快，容易使算法陷入局部極值點(diǎn)．可見，樹生長算法為機(jī)器人路徑規(guī)劃優(yōu)化問題提供了一種新思路，豐富了群智能算法[14]．

文中提出了一種基于樹生長機(jī)制的路徑規(guī)劃算法，詳細(xì)描述了TGSA的基本原理，建模和實(shí)現(xiàn)過程．TGSA的運(yùn)行效率高，操作過程穩(wěn)定，具有良好的路徑規(guī)劃能力．未來TGSA在其他最優(yōu)問題上的應(yīng)用將是一個(gè)必要和有趣的研究．

[1] 曾辰,許瑛.一種蜂巢柵格下機(jī)器人路徑規(guī)劃的蟻群算法[J].機(jī)械科學(xué)與技術(shù),2016,35(8):1 308-1 312.

[2] A KARCI.Natural inspired computational intelligence method:saplings growing up algorithm[C]//IEEE International Conference on Computational Cybernetics，Gammarth：IEEE,2007:221-226.

[3] 李彤,王春峰,王文波,等.求解整數(shù)規(guī)劃的一種仿生類全局優(yōu)化算法-模擬植物生長算法[J].系統(tǒng)工程理論與實(shí)踐,2005，25(1):76-85.

[4] X CAI,X WU,L WANG,et al.Hydrophobic-polar model structure prediction with binary-coded artificial plant optimization algorithm[J].Journal of Computational & Theoretical Nanoscience,2013,10(6):1 550-1 554.

[5] 劉坤.人工植物優(yōu)化算法混合策略的研究及應(yīng)用[D].太原：太原科技大學(xué),2011.

[6] 郭改文,黃卡瑪.模擬自然樹生長的競爭算法及在曲線擬合中的應(yīng)用[J].電子學(xué)報(bào),2008,36(9):1 839-1 843.

[7] Y ZHOU,Y WANG,X CHEN,et al.A novel path planning algorithm based on plant growth mechanism[J].Soft Computing,2016，21(2):1-11.

[8] 孔令飛,王淳,熊云,等.模擬植物多向生長的配電網(wǎng)重構(gòu)算法[J].電測與儀表,2016,53(24):1-5.

[9] 吳俊秋,何迪.模擬植物生長算法及其改進(jìn)研究[J].通信技術(shù),2016,49(12):1 629-1 634.

[10] 王莉,秦勇,徐杰,等.植物多向生長模擬算法[J].系統(tǒng)工程理論與實(shí)踐,2014,34(4):1 018-1 027.

[11] S AKYOL,B ALATAS.Plant intelligence based metaheuristic optimization algorithms[J].Artificial Intelligence Review,2016,47(4):1-46.

[12] 蔡偉.不確定性多目標(biāo)MDO理論及其在飛行器總體設(shè)計(jì)中的應(yīng)用研究[D].北京：國防科學(xué)技術(shù)大學(xué),2008.

[13] 楊紅娟.人工植物算法設(shè)計(jì)[D].太原：太原科技大學(xué),2011.

[14] 曹策俊,李從東,楊琴,等.模擬植物生長算法在組合優(yōu)化問題中的應(yīng)用:研究進(jìn)展[J]. 技術(shù)經(jīng)濟(jì),2017,36(5):127-136.