基于HGM與TGSA的機器人路徑規劃算法研究

姚成信，王冠凌，陳孟元

(安徽工程大學 安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000)

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

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

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

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

1 蜂巢柵格法環境建模

圖1 移動機器人運行環境

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

2 樹生長模擬算法

2.1 算法的尋優原理

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

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

表1樹生長模擬算法與路徑規劃問題的對應表

路徑規劃問題的定義域[xmin,xmax]樹的生長環境算法的迭代次數t樹分枝的生長期局部最優解(xbest,ybest)光照強度適宜的位置目標函數I(i)光照強度算法中的一段路徑i樹的枝條機器人位置移動(xti,yti)枝條的生長所有路徑條數m枝條的總數

2.2 尋找全局最優解的理論依據

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

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

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

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

3 樹生長模擬算法在機器人路徑規劃中的研究應用

3.1 路徑規劃的數學模型

在標準生長樹模型中，將光照強度分布在特定生長樹的區域范圍視為該生長樹模型的定義域區間，樹在生長過程中通過不斷感知區域內不同的光照強度來進行分枝-生長，最終向最佳光照方向尋優出最優生長路徑．生長樹算法將優化問題的定義域視為樹的生長環境，算法的迭代次數視為樹的生長周期．在枝芽的光合作用進入向光性階段時，樹分別利用生長期優化規則進行尋優分枝點；最后進入生長尋優階段，枝芽會在向光生長過程中根據尋優規則完成全局遍歷式尋優．在生長樹經歷完整個生長周期后，算法收斂停止，找到最優生長路徑．

圖3 蜂巢柵格坐標圖

(1)

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

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

(2)

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

(2)光合速率計算.首先在環境區域內遍尋各位置處的光照強度及對應的光合速率，即尋找目標函數，式(3)表示坐標上任意點(xi,yi)處枝條的光照強度，式(4)代表坐標(xi,yi)位置處枝條的光合速率．

(3)

式中，kl表示光照強度系數，(xD,yD)是目標點的位置，(xB,yB)是起始樹芽的位置．

(4)

圖4 生長素濃度與生長速率的關系

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

(5)

一旦新分枝發芽時，新枝和舊枝合二為一，均看作同一平面內的同一枝干．

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

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

(6)

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

(7)

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

(8)

針對模擬環境下尋優生長的3種不同模型，對該算法下的最優路徑規劃設計目標函數為：

(9)

式中，μ1,μ2,μ3均為權值系數，用來調整尋找出一條最優路徑．

3.2 基本算法流程

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

圖5 TGSA流程圖

4 仿真實驗對比分析

4.1 兩種不同環境地圖下的算法對比

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

在圖6、圖7中，地圖環境區域分別設置為30*30的傳統柵格和蜂巢柵格．障礙物全部擴展為圓形障礙物，兩種地圖中的障礙物圓心及半徑已知，即地圖中全部靜態圓形障礙物位置已知，且全部位置對應相同，兩種地圖中的起始位置和目標位置均相同．

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

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

蜂巢柵格下的TGSA算法和普通柵格下的TGSA算法仿真結果對比如表2所示.30*30最優路徑收斂曲線圖如圖8所示.由表2和圖8可以看出，蜂巢柵格下的TGSA算法相比普通柵格下的TGSA算法，迭代次數和運行時間都有所降低，最優路徑長度減小．

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

4.2 同種環境地圖下不同算法的實驗對比

實驗地圖環境區域設置在30*30的蜂巢柵格中，如圖9所示．蟻群算法下的機器人路徑如圖9中粗折線所示，TGSA算法下的機器人路徑圖如圖9中細折線所示．障礙物全部擴展為圓形障礙物，兩種地圖中的障礙物圓心及半徑已知，即地圖中全部靜態圓形障礙物位置已知，且全部位置對應相同，兩種地圖中的起始位置和目標位置均相同．

圖8 30*30最優路徑收斂曲線圖圖9 蜂巢柵格下的路徑圖

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

表3 蟻群算法和TGSA算法仿真結果對比

圖10 40*50最優路徑收斂曲線圖

5 結論

樹生長模擬算法不同于以往的仿生算法，它是模擬現實中樹木的一般生長過程，從樹木的內在生長機理出發，打破了以往眾多其他仿生算法模型中主要以模擬自然規律或者細菌、昆蟲以及動物的生長生活方式為主的傳統研究方法，為群智能計算的發展開辟了新的領域[13]．

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

文中提出了一種基于樹生長機制的路徑規劃算法，詳細描述了TGSA的基本原理，建模和實現過程．TGSA的運行效率高，操作過程穩定，具有良好的路徑規劃能力．未來TGSA在其他最優問題上的應用將是一個必要和有趣的研究．

[1] 曾辰,許瑛.一種蜂巢柵格下機器人路徑規劃的蟻群算法[J].機械科學與技術,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] 李彤,王春峰,王文波,等.求解整數規劃的一種仿生類全局優化算法-模擬植物生長算法[J].系統工程理論與實踐,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] 劉坤.人工植物優化算法混合策略的研究及應用[D].太原：太原科技大學,2011.

[6] 郭改文,黃卡瑪.模擬自然樹生長的競爭算法及在曲線擬合中的應用[J].電子學報,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] 孔令飛,王淳,熊云,等.模擬植物多向生長的配電網重構算法[J].電測與儀表,2016,53(24):1-5.

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

[10] 王莉,秦勇,徐杰,等.植物多向生長模擬算法[J].系統工程理論與實踐,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] 蔡偉.不確定性多目標MDO理論及其在飛行器總體設計中的應用研究[D].北京：國防科學技術大學,2008.

[13] 楊紅娟.人工植物算法設計[D].太原：太原科技大學,2011.

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