一種生物地理學移動機器人路徑規劃算法

莫宏偉，馬靖雯

（哈爾濱工程大學自動化學院，黑龍江哈爾濱150001）

一種生物地理學移動機器人路徑規劃算法

莫宏偉，馬靖雯

（哈爾濱工程大學自動化學院，黑龍江哈爾濱150001）

目前，雖然有多種智能計算方法用于移動機器人路徑規劃問題，但在復雜環境下，多數智能計算方法表現出效率低下，結果較差的問題。提出一種結合基于有效頂點的柵格編碼法和改進的生物地理學優化算法的移動機器人路徑規劃方法，以解決該類問題。結合已知的環境信息，從精英策略、降維機制和基于慣性算子的遷移操作3方面改進了生物地理學優化算法。改進算法用于機器人移動路徑，與人工蜂群算法、粒子群算法和人工魚群算法等智能算法進行比較，實驗的結果證實改進算法能夠更有效地解決復雜環境下機器人路徑規劃問題。

移動機器人；路徑規劃；生物地理優化算法；有效頂點；柵格編碼法

移動機器人路徑規劃主要解決3個問題：1）使機器人能從初始點運動到目標點；2）用一定的算法使機器人能繞開障礙物，并且經過某些必須經過的點完成相應的作業任務；3）在完成以上任務的前提下，盡量優化機器人運行軌跡。移動機器人路徑規劃技術從移動機器人路徑規劃的具體算法與策略可概括為以下4類［1］：模版匹配路徑規劃技術、人工勢場路徑規劃技術、地圖構建路徑規劃技術和人工智能路徑規劃技術。

模版匹配技術在環境確定情況下，有較好的應用效果［2?5］。人工勢場路徑規劃將機器人在環境中的運動視為一種機器人在虛擬的人工受力場中的運動。障礙物對機器人產生斥力，目標點對機器人產生引力，引力和斥力的合力作為機器人的控制力，從而控制機器人避開障礙物而到達目標位置［6－12］。地圖構建分為路標法和柵格法，路標法是構造一幅由標志點和連接邊線組成的機器人可行路徑圖，如可視線方法、切線圖方法、Voronoi圖方法和概率圖展開法等［13］。計算智能路徑規劃將生物啟發的計算方法應用于移動機器人的路徑規劃中，如人工神經網絡、進化計算、蟻群算法生物地理優化算法等［14］。但上述方法尤其是計算智能方法在復雜環境下都缺乏效率，結果也不夠準確。本文針對一類復雜環境下的機器人路徑規劃問題，提出基于改進的生物地理學優化方法（biogeography?based optimization，BBO），以期更有效地解決該類問題。

1 有效頂點柵格環境

柵格法是將環境離散化為二維（或三維）的基本單元柵格，柵格大小決定了離散化環境的分辨率，通過對這些柵格的標示來完成對機器人環境的建模，若為了節約存儲空間可采用四叉樹等方法進行建模，也可以從方便訪問的角度出發建立逐點掃描的二維環境，最后利用搜索算法得到規劃路徑。這種方法因離散化的建模思想極其符合計算機的存儲運算特點而得到了廣泛的應用。基本柵格法包括4個步驟：1）柵格化二維平面；2）障礙物膨脹；3）標記障礙物；4）自由柵格之間的連接信息。這種方法存在以下缺點：

1）柵格在被選入路徑后需要加入禁忌表，即該柵格不能再次被選入路徑中，這樣當遇到一些U型槽等復雜環境會迅速生成有效的路徑；

2）自由柵格大部分都不是有效柵格，路徑規劃結果的信息僅包含障礙物頂點附近的部分柵格；

3）分辨率大小難以確定。分辨率過高，增加搜索算法的運算量；分辨率過小會導致路徑規劃結果粗糙，在極端情況下會造成本來分開的障礙物連通，最終得不到有效的路徑。

本文針對基本柵格法的以上3方面缺點，引入了一種更為有效的方法——基于有效定點的柵格編碼法。該方法充分借鑒了可視圖法和基本柵格法的特點而提出的方法，有效地解決了基本柵格法因分辨率而增加額外運算規模，搜索規模只與有效頂點個數，即障礙物個數及其輪廓復雜度有關系。該方法從模型上解決了U型槽等障礙物模型機器人路徑規劃導致的算法陷入局部收斂問題。

在m×n的柵格環境中，定義g（i，j）為｛g（i，j）｜i∈［1，m－1］，j∈［1，n－1］，i∈N，j∈N｝。若柵格g（i，j），g（i，i＋1），g（i＋1，j），g（i＋1，j＋1）4個柵格中有且只有一個障礙物柵格gob（xob，yob），那么這個4個柵格中必存在一個有效頂點gv（xv，yv），gob與gv同時滿足以下2個條件：

以圖1為例，按照有效頂點法將產生31個有效頂點加入到有效頂點列表S，遍歷這31個有效頂點并刪除重復的頂點，最后如圖1所示10×10的柵格地圖描述為27個有效頂點。在路徑規劃之前，需要將起始頂點和目的頂點加入到有效頂點列表。

定義Availablei＝?表示，頂點si∈S的直線可達頂點集合。對于每個頂點sj∈S且i≠j若直線可達檢測通過，則向Availablei添加sj，并記錄dij＝dji＝

圖1 基于有效頂點的柵格示意圖Fig．1 Schematic diagram of grids based on effective vertex

2 BBO

生物地理學是一門研究物種生存的自然學科，物種種群分布的地域（棲息地）各不相同。每個棲息地的生活環境各不相同，而且每個物種根據自身的生活條件也各不相同，所以對每個棲息地的適應程度也不相同，因此就有了物種的各式各樣的分布、遷移和滅絕等現象。每個棲息地的適應度指數（habitat suitability index，HSI）的高低根據該棲息地的多種因素稱為適應度指數變量（suitability index variable，SIV）相關，如種群類別、降雨量、地質狀況、植被和氣候等。如果該棲息地的適應度指數較高，那么有以下結果：物種必然呈現多樣性，即物種數量大，但每個棲息地容納物種的數量是有限度的，棲息地會因為物種眾多而導致資源匱乏，適應度下降導致了物種選擇離開棲息地；進入該棲息地的物種數量小于遷出該棲息地的物種數量；若棲息地的適應度指數較低，那么物種多樣性減少，即物種數量稀少，但是由于物種較少，導致物種選擇遷入到該棲息地的數量高于遷出該棲息地的物種。任何一個棲息地的環境狀況都有一定概率發生變異，導致HIS發生改變。本文提出了基于生物地理優化的旅行商問題求解算法［15］。

2．1 適應度指數變量SIV與機器人路徑的關系

設有m個島嶼，那么第i個島嶼的SIVi＝，對于每一個有

另外，生成第i個島嶼所代表的路徑列表Pathi＝?，令Vs加入到Pathi中，設當前路徑頂點列表Pathi有j個頂點，那么第j個頂點sj的可直線到達列表Availablei，定義集合Mi＝Availablei－Pathi，定義n為Mi的個數，那么添加頂點sj＋1到Pathi的隊尾直到目的地頂點Vt添加到Pathi。sj＋1選取方法如式（4）所示。

SIVi需要包含的變量個數需要達到N－1（N為有效頂點列表S的個數）才能夠保證機器人路徑生成的絕對安全。

2．2 BBO的遷移操作

遷入操作描述如下，根據每個島嶼的遷出率μi進行貪婪算法選擇島嶼k，遷出操作將遷入到如式（5）所示。

2．3 BBO的變異操作

設有M個島嶼，根據2．1描述的如何將SIV轉換為路徑列表Path，計算每個島嶼的所代表的路徑的長度D＝｛D1，D2，…，Dm－1，Dm｝，Di越小的代表越高的HIS，所以按照Di的大小由小到大將集合D排序，排序索引可以表示為Index＝｛I1，I2，…，IM－1， IM｝，Ii表示M個Di由小到大排序的島嶼i在排序的中的位置。那么島嶼i的物種數Si可表示為

生物地理學認為棲息地的物種數量過大和過小都將導致棲息地的SIV變異率較高。定義島嶼i的變異率mi：

式中：mmax為算法需要人工設定的最大變異率。

2．4 算法流程

基于生物地理學的路徑規劃算法流程下：

1）初始化最大循環次數N；初始化BBO的各個參數：島嶼數M，最大變異率mmax；最大物種數Smax＝M－1，最大遷出率E＝1，最大嵌入率I＝1；初始化每個島嶼i的

2）計算每個島嶼的路徑D，并根據Di確定以及PSi；保存最小路徑信息和最小路徑值到Dmin；

3）初始化迭代次數nc＝0；

4）執行遷移操作；

5）是否執行變異操作，若不執行則跳過；

6）計算每個島嶼的路徑D，并根據Di確定Si，以及PSi；計算當前代數最小路徑若則Dncmin＝Dmin，保存最小路徑信息；

7）nc＜N是否成立，若成立，則nc＝nc＋1，跳到4）；若不成立，則跳到7）；

8）輸出最短路徑值和最短路徑信息。

2．5 算法的改進

2．5．1 精英策略

由2．3可知，mi為島嶼i的變異率，那么當i＝Index（1）時，將得到最大的變異率，也就是說：路徑最短的島嶼具有很高的變異率。這一結果將可能導致算法的進化出現退化。因此，精英島嶼具有變異率為0的特性。設算法有n個精英島嶼，那么設置方法如下：

在算法步驟上，只需要將算法流程中所述的算法步驟的2）和6）分別在最末加入式（8）。

2．5．2 降維

根據2．1描述可以看出，SIVi需要包含的變量個數需要達到N－1（N為有效頂點列表S的個數），即島嶼的變量需要達到和有效頂點數相同（或在單項搜索的時候少1個變量，雙向搜索的時候少2個變量）才能夠保證機器人路徑生成的絕對穩定。但一般情況下，路徑規劃的結果只包含整個有效頂點結合中少數個頂點。這說明，若不改進算法，算法將會是一個維數巨大的計算，而且是不必要的大維度計算。

本文嘗試提出了一種降維機制描述如下：

對于在t＝0時，有效頂點集合S內共有X個頂點，那么所有島嶼的SIV0的維數Y＝X－2；按照2．1方法生成完整的路徑，記錄第i個島嶼的正向有效的SIV個數xi，和反向有效的SIV個數yi。在t時刻，定義

t時刻所有島嶼的SIV的維數：

式中：α為降維因子，α≥1，b為常數。

3 仿真與分析

實驗加載30×30環境模型路徑起始點坐標為（0，0），目的地坐標為（29，29）。

1）BBO算法島嶼總數M設為30，最大變異率mmax設為0．4。算法1為有精英島嶼的BBO算法，算法2為無精英島嶼的BBO算法。2個算法各運行30次，仿真迭代趨勢圖，規劃結果統計圖，規劃時間消耗統計圖分別如圖2～4所示。

圖2 精英島嶼對算法迭代的影響趨勢Fig．2 Influence of the elite island on algorithm iteration

圖3 精英島嶼對算法結果的影響統計Fig．3 Statistics of the influence of the elite island on results of algorithm

圖4 精英島嶼對算法時效的影響統計Fig．4 Statistics of influence of the elite island on algo?rithm effectiveness

從規劃結果統計來看，有精英島嶼具有更高的穩定性，標準差為0．941 9而無精英島嶼為1．384 3；有精英島嶼具有更好求解最小路徑能力，誤差率為2．59%，而無精英島嶼為4．15%。從規劃時間統計來看，有精英島嶼的BBO算法具有更小的時間消耗，節省時間平均約1．512 1 s。

2）設BBO算法島嶼總數M設為30，最大變異率mmax設為0．4。算法1為有降維機制的BBO算法，算法2為無降維機制的BBO算法。2個算法各運行30次，仿真迭代趨勢圖，規劃結果統計圖，規劃時間消耗統計圖分別如圖5～7所示。

圖5 降維機制對算法迭代影響的趨勢圖Fig．5 Influence of the dimensionality reduction mecha?nism on algorithm iteration

圖6 降維機制對算法結果影響的統計Fig．6 Statistics of the influence of dimensionality re?duction mechanism on results of algorithm

圖7 降維機制對算法時效影響的統計Fig．7 Statistics of the influence of dimensionality re?duction mechanism on algorithm effectiveness

根據仿真統計結果及下降趨勢圖顯示，降維機制對算法尋找最小路徑效果上有作用。由圖5可以看出降維機制加快了算法的收斂速度。由圖6可以得到，降維機制呈現了較好的穩定性，30次結果的標準差為0．941 9，而無降維機制為1．297 4；也呈現了較好的搜索能力，30次結果的誤差率為2．59%，而無降維機制為3．35%。在規劃時間消耗上圖7顯而易見的表明了其降維機制的優勢。

圖8 仿真環境模型Fig．8 Simulation environment models

為了能更好的評價4個算法的性能，現將算法參數設置如下：

BBO：島嶼數M＝30，最大變異率mmax＝0．3，采用上面提到的降維機制和精英策略，以及雙向搜索機制；

PSO：粒子個數M＝30，慣性常數ωmax＝0．8，ωmmin＝0．4，c1＝0．5，c2＝0．5，采用線性動態ω調整策略、降維機制和雙向搜索機制；

AFSA：人工魚個數M＝30，擁擠度因子設為2，感知距離為0．1，最大移動步長0．08，最大試探次數10，同樣采用雙向搜索機制和降維機制；

ABC：人工蜂個數M＝30，最大嘗試次數Limit＝15，同樣采用雙向搜索機制和降維機制。

每個算法統一迭代次數為2 000次。

為移動機器人在圖8環境下進行路徑規劃，路徑起始點為柵格圖的左上角（0，0）點，目的地為柵格圖的右下角（N－1，N－1）。

算法運行在不同的環境模型下的復雜度及理論最小路徑統計如表1所示。

每個算法在每種柵格環境下重復運行30次得到的規劃結果和時間消耗結果統計如下表2所示。

表1 仿真環境參數指標Table 1 The performance of parameters in simulation en?vironment

表2 4種算法路徑規劃統計結果Table 2 Statistical results of four path planning algorithms

續表2

柵格規模算法最小值最大值均值中間值標準差誤差率／% BBO59．423 265．792 163．229 263．600 31．275 37．18 40×40（575）PSO70．058 292．295 377．519 877．268 44．736 331．40 AFSA62．941 473．515 468．606 068．770 42．433 616．29 ABC64．973 681．521 474．413 974．051 83．785 026．14 BBO81．799 492．407 688．612 988．733 33．271 319．84 50×50（903）PSO90．701 7126．772 0109．324 3108．261 011．269 847．85 AFSA87．008 4100．621 095．752 196．859 13．931 529．50 ABC92．565 6116．311 0105．551 4106．293 57．353 542．75 BBO103．741 0120．983 0114．791 5116．312 55．918 029．24 60×60（1305）PSO121．012 0156．372 0136．067 2136．008 010．605 753．19 AFSA117．059 0136．808 0128．630 1131．973 06．455 544．82 ABC125．807 0154．789 0142．289 9143．070 510．756 960．20 BBO147．224 0174．286 0158．493 0157．741 08．401 952．86 70×70（1781）PSO141．577 0219．568 0181．430 5177．859 525．627 574．98 AFSA132．976 0170．408 0149．900 2148．404 512．995 154．21 ABC164．998 0234．324 0194．063 4191．770 024．829 087．16

由表2中可見，BBO算法除第1種環境與其他算法結果相同以外，其余5種環境下規劃效果均好于其他4種算法。表明本文針對機器人路徑規劃問題，所提出的生物地理優化算法改進策略對于機器人路徑規劃問題是有效的。

5 結束語

本文基于BBO的機器人路徑規劃問題，提出了復雜環境下基于有效頂點降維策略的移動機器人路徑規劃算法，并提出慣性遷移操作算子。改進的BBO與人工蜂群算法、人工魚群算法、粒子群算法進行對比，仿真結果表明所提出的生物地理機器人路徑優化算法對于機器人路徑規劃是有效的。在此基礎上，繼續研究該算法在多目標路徑規劃、城市交通實際環境下的汽車路徑規劃等問題。

［1］朱大奇，顏明重．移動機器人路徑規劃技術綜述［J］．控制與決策，2010，25（7）：961?967．ZHU Daqi，YAN Mingzhong．Survey on technology of mo?bile robot path planning［J］．Control and Decision，2010，25（7）：961?967．

［2］VASUDEVAN C，GANESAN K．Case?based path planning for autonomous underwater vehicles［C］／／Proceedings of the 1994 IEEE International Symposium on Intelligent Control． Columbus，USA，1994：160?165．

［3］LIU Yu，ZHU Shiqiang，JIN Bo，et al．Sensory navigation of autonomous cleaning robots［C］／／The 5th World Confer?ence on Intelligent Control Automation．Hangzhou，China，2004：4793?4796．

［4］RAM A，SANTAMARíA J C．Continuous case?based rea?soning［J］．Artificial Intelligence，1997，90（1／2）：25?77．

［5］ARLEO A，SMERALDI F，GERSTNER W．Cognitive navi?gation based on nonuniform Gabor space sampling，unsuper?vised growing Networks，and reinforcement learning［J］．IEEE Transactions on Neural Network，2004，15（3）：639?652．

［6］FUJIMURA K，SAMET H．A hierarchical strategy for path planning among moving obstacles［mobile robot］［J］．IEEE Transactions on Robotic Automation，1989，5（1）：61?69．

［7］KO N Y，LEE B H．Avoidability measure in moving obsta?cle avoidance problem and its use for robot motion planning［C］／／IEEE International Conference on Intelligent Robots and System．Osaka，1996：1296?1303．

［8］GE S S，CUI Y J．New potential functions for mobile robot path planning［J］．IEEE Transactions on Robotics and Auto?mation，2000，16（5）：615?620．

［9］陳清陽，張小波，孫振平，等．非結構化環境下自主車輛軌跡規劃方法［J］．中南大學學報：然科學版．2011，42（11）：3377?3383．CHEN Qingyang，ZHANG Xiaobo，SUN Zhenping，et al．Trajectory planning for autonomous driving in unstructured environments［J］．Journal of Central South University：atu?ral and Technology，2011，42（11）：3377?3383．

［10］王鴻鵬，楊云，劉景泰．高速移動機器人的研究現狀與發展趨勢［J］．自動化與儀表，2011，26（12）：1?4．WANG Hongpeng，YANG Yun，LIU Jingtai．Research and development trend of high?speed mobile robot［J］．Automa?tion and Instrumentation，2011，26（12）：1?4．

［11］譚民，王碩．機器人技術研究進展［J］．自動化學報，2013，39（7）：963?972．TAN Min，WANG Shuo．Research progress on robotics［J］．Acta Automatica Sinica，2013，39（7）：963?972．

［12］JARADAT M A K，GARIBEH M H，FEILAT E A．Dy?namic motion planning for autonomous mobile robot using fuzzy potential field［C］／／Proceeding of the 6th Interna?tional Symposium on Mechatronics and its Applications．Sharjah，UAE，2009：24?26．

［13］LINGELBACH F．Path planning using probabilistic cell de?composition［C］／／IEEE International Conference on Ro?botics and Automation．New Orleans，USA，2004：467?472．

［14］MO Hongwei，MENG Longlong．Robot path planning based on differential evolution in static environment［J］．Interna?tional Journal of Digital Content Technology and its Appli?cations，2012，6（20）：122?129．

［15］MO Hongwei，XU Lifang．Biogeography migration algo?rithm for traveling salesman problem［J］．International Journal of Intelligent Computing and Cybernetics，2011，4（3）：311?330．

A biogeography?based mobile robot path planning algorithm

MO Hongwei，MA Jingwen
（College of Automation，Harbin Engineering University，Harbin 150001，China）

At present，there are many intelligent computing methods used in mobile robot path planning；however，in complex environments，most of them have low efficiency and poor results．In order to solve such problems，this paper proposes a new method for mobile robot path planning，which combines the grid coding method based on the effective vertex with the improved biogeography?based optimization（BBO）．On the basis of the environmental infor?mation that has been learned，the BBO is improved in three aspects：elite strategies，dimension reduction mecha?nisms and migration based on inertial operator．The improved BBO is applied in path planning．The method is com?pared with artificial bee colony（ABC），particle swarm optimization（PSO）and artificial fish algorithm（AFA）．Experiment results show that the improved method can solve the problem of mobile robot path planning in a complex environment more efficiently．

mobile robot；path planning；biogeography?based optimization（BBO）；effective vertex；grid coding method

TP301

A

1673?4785（2015）05?0705?07

10．11992／tis．201407003

http：／／www．cnki．net／kcms／detail／23．1538．tp．20151008．1000．004．html

莫宏偉，馬靖雯．一種生物地理學移動機器人路徑規劃算法［J］．智能系統學報，2015，10（5）：705?711．

英文引用格式：MO Hongwei，MA Jingwen．A biogeography?based mobile robot path planning algorithm［J］．CAAI Transactions on Intelligent Systems，2015，10（5）：705?711．

莫宏偉，男，1973年生，教授，主要研究方向為自然計算理論與應用、機器人、機器學習與數據挖掘。主持完成國家自然科學基金等國家、省部級及橫向課題16項，獲得省科技進步獎2項，發表學術論文60余篇，其中被SCI檢索11篇，EI檢索40篇。

馬靖雯，女，1988年生，碩士研究生，主要研究方向為自然計算及其應用。

2014?07?01．

日期：2014?10?08．

黑龍江省杰出青年科學基金資助項目（JC201212）；中央高校基本科研業務經費資助項目（HEUCFX041306）．

莫宏偉．E?mail：honwei2004＠126．com．