一種生物地理學(xué)移動機(jī)器人路徑規(guī)劃算法

莫宏偉，馬靖雯

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

一種生物地理學(xué)移動機(jī)器人路徑規(guī)劃算法

莫宏偉，馬靖雯

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

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

移動機(jī)器人；路徑規(guī)劃；生物地理優(yōu)化算法；有效頂點(diǎn)；柵格編碼法

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

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

1 有效頂點(diǎn)柵格環(huán)境

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

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

2）自由柵格大部分都不是有效柵格，路徑規(guī)劃結(jié)果的信息僅包含障礙物頂點(diǎn)附近的部分柵格；

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

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

在m×n的柵格環(huá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個柵格中必存在一個有效頂點(diǎn)gv（xv，yv），gob與gv同時滿足以下2個條件：

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

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

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

2 BBO

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

2．1 適應(yīng)度指數(shù)變量SIV與機(jī)器人路徑的關(guān)系

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

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

SIVi需要包含的變量個數(shù)需要達(dá)到N－1（N為有效頂點(diǎn)列表S的個數(shù)）才能夠保證機(jī)器人路徑生成的絕對安全。

2．2 BBO的遷移操作

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

2．3 BBO的變異操作

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

生物地理學(xué)認(rèn)為棲息地的物種數(shù)量過大和過小都將導(dǎo)致棲息地的SIV變異率較高。定義島嶼i的變異率mi：

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

2．4 算法流程

基于生物地理學(xué)的路徑規(guī)劃算法流程下：

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

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

3）初始化迭代次數(shù)nc＝0；

4）執(zhí)行遷移操作；

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

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

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

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

2．5 算法的改進(jìn)

2．5．1 精英策略

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

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

2．5．2 降維

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

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

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

t時刻所有島嶼的SIV的維數(shù)：

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

3 仿真與分析

實(shí)驗(yàn)加載30×30環(huán)境模型路徑起始點(diǎn)坐標(biāo)為（0，0），目的地坐標(biāo)為（29，29）。

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

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

圖3 精英島嶼對算法結(jié)果的影響統(tǒng)計Fig．3 Statistics of the influence of the elite island on results of algorithm

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

從規(guī)劃結(jié)果統(tǒng)計來看，有精英島嶼具有更高的穩(wěn)定性，標(biāo)準(zhǔn)差為0．941 9而無精英島嶼為1．384 3；有精英島嶼具有更好求解最小路徑能力，誤差率為2．59%，而無精英島嶼為4．15%。從規(guī)劃時間統(tǒng)計來看，有精英島嶼的BBO算法具有更小的時間消耗，節(jié)省時間平均約1．512 1 s。

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

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

圖6 降維機(jī)制對算法結(jié)果影響的統(tǒng)計Fig．6 Statistics of the influence of dimensionality re?duction mechanism on results of algorithm

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

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

圖8 仿真環(huán)境模型Fig．8 Simulation environment models

為了能更好的評價4個算法的性能，現(xiàn)將算法參數(shù)設(shè)置如下：

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

PSO：粒子個數(shù)M＝30，慣性常數(shù)ωmax＝0．8，ωmmin＝0．4，c1＝0．5，c2＝0．5，采用線性動態(tài)ω調(diào)整策略、降維機(jī)制和雙向搜索機(jī)制；

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

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

每個算法統(tǒng)一迭代次數(shù)為2 000次。

為移動機(jī)器人在圖8環(huán)境下進(jìn)行路徑規(guī)劃，路徑起始點(diǎn)為柵格圖的左上角（0，0）點(diǎn)，目的地為柵格圖的右下角（N－1，N－1）。

算法運(yùn)行在不同的環(huán)境模型下的復(fù)雜度及理論最小路徑統(tǒng)計如表1所示。

每個算法在每種柵格環(huán)境下重復(fù)運(yùn)行30次得到的規(guī)劃結(jié)果和時間消耗結(jié)果統(tǒng)計如下表2所示。

表1 仿真環(huán)境參數(shù)指標(biāo)Table 1 The performance of parameters in simulation en?vironment

表2 4種算法路徑規(guī)劃統(tǒng)計結(jié)果Table 2 Statistical results of four path planning algorithms

續(xù)表2

柵格規(guī)模算法最小值最大值均值中間值標(biāo)準(zhǔn)差誤差率／% 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種環(huán)境與其他算法結(jié)果相同以外，其余5種環(huán)境下規(guī)劃效果均好于其他4種算法。表明本文針對機(jī)器人路徑規(guī)劃問題，所提出的生物地理優(yōu)化算法改進(jìn)策略對于機(jī)器人路徑規(guī)劃問題是有效的。

5 結(jié)束語

本文基于BBO的機(jī)器人路徑規(guī)劃問題，提出了復(fù)雜環(huán)境下基于有效頂點(diǎn)降維策略的移動機(jī)器人路徑規(guī)劃算法，并提出慣性遷移操作算子。改進(jìn)的BBO與人工蜂群算法、人工魚群算法、粒子群算法進(jìn)行對比，仿真結(jié)果表明所提出的生物地理機(jī)器人路徑優(yōu)化算法對于機(jī)器人路徑規(guī)劃是有效的。在此基礎(chǔ)上，繼續(xù)研究該算法在多目標(biāo)路徑規(guī)劃、城市交通實(shí)際環(huán)境下的汽車路徑規(guī)劃等問題。

［1］朱大奇，顏明重．移動機(jī)器人路徑規(guī)劃技術(shù)綜述［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］陳清陽，張小波，孫振平，等．非結(jié)構(gòu)化環(huán)境下自主車輛軌跡規(guī)劃方法［J］．中南大學(xué)學(xué)報：然科學(xué)版．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ī)器人的研究現(xiàn)狀與發(fā)展趨勢［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ī)器人技術(shù)研究進(jìn)展［J］．自動化學(xué)報，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，F(xiàn)EILAT 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

莫宏偉，馬靖雯．一種生物地理學(xué)移動機(jī)器人路徑規(guī)劃算法［J］．智能系統(tǒng)學(xué)報，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年生，教授，主要研究方向?yàn)樽匀挥嬎憷碚撆c應(yīng)用、機(jī)器人、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。主持完成國家自然科學(xué)基金等國家、省部級及橫向課題16項，獲得省科技進(jìn)步獎2項，發(fā)表學(xué)術(shù)論文60余篇，其中被SCI檢索11篇，EI檢索40篇。

馬靖雯，女，1988年生，碩士研究生，主要研究方向?yàn)樽匀挥嬎慵捌鋺?yīng)用。

2014?07?01．

日期：2014?10?08．

黑龍江省杰出青年科學(xué)基金資助項目（JC201212）；中央高校基本科研業(yè)務(wù)經(jīng)費(fèi)資助項目（HEUCFX041306）．

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