小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法

姜 濤,王建中,施家棟

(北京理工大學(xué)爆炸科學(xué)與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京100081)

小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法

姜 濤,王建中,施家棟

(北京理工大學(xué)爆炸科學(xué)與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京100081)

針對(duì)遙控小型移動(dòng)機(jī)器人在自主返航實(shí)際應(yīng)用中定位精度低等問(wèn)題,提出一種小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法。介紹小型移動(dòng)機(jī)器人的任務(wù)流程及硬件系統(tǒng),利用膨脹算子對(duì)柵格地圖中的障礙物進(jìn)行運(yùn)算得到柵格Voronoi圖。使用雙邊界路徑矢量化方法從柵格Voronoi圖中提取出矢量路徑,并對(duì)該路徑進(jìn)行拓?fù)鋬?yōu)化。通過(guò)Dijkstra算法對(duì)拓?fù)渎窂竭M(jìn)行路徑規(guī)劃并進(jìn)行算法驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,該方法所得路徑可使環(huán)境中的機(jī)器人與障礙物之間的距離最大化,并使移動(dòng)機(jī)器人的運(yùn)動(dòng)軌跡具有較高的可執(zhí)行性,提高了小型移動(dòng)機(jī)器人自主返航的成功率。

移動(dòng)機(jī)器人;數(shù)學(xué)形態(tài)學(xué);路徑規(guī)劃;Voronoi圖;拓?fù)鋬?yōu)化;Dijkstra算法

1 概述

小型移動(dòng)機(jī)器人主要用于城市巷戰(zhàn)執(zhí)行偵察任務(wù),通常采用遙控方式進(jìn)入偵察區(qū)域,在樓宇間或房屋樓道內(nèi)進(jìn)行情報(bào)搜集。在實(shí)際使用過(guò)程中,遙控信號(hào)在樓群或室內(nèi)極易被遮擋與屏蔽,所以需要移動(dòng)機(jī)器人在失去控制時(shí)進(jìn)行路徑規(guī)劃使其具有自主返航能力。

路徑規(guī)劃是從一個(gè)地方運(yùn)動(dòng)到另一個(gè)地方的路徑問(wèn)題。其主要目的是為移動(dòng)機(jī)器人規(guī)劃出最優(yōu)路徑,使平臺(tái)安全高效的到達(dá)目的地,目前所提出的計(jì)算方法多數(shù)以尋求全局最優(yōu)解為目標(biāo)。A?算法引入啟發(fā)式函數(shù)引導(dǎo)搜索方向,提高了搜索效率。通過(guò)對(duì)估價(jià)函數(shù)和圖搜索方向的改進(jìn),可以提高路徑規(guī)劃速度,具有一定復(fù)雜環(huán)境適應(yīng)能力[1]的遺傳算法是基于自然選擇和基因遺傳學(xué)原理的隨機(jī)搜索算法,其采用多點(diǎn)搜索有更高概率搜索到全局最優(yōu)解[2]。人工神經(jīng)網(wǎng)絡(luò)方法是對(duì)人腦的模擬,該方法具有并行處理效率高,學(xué)習(xí)能力強(qiáng),能收斂到最優(yōu)路徑[3]。模糊算法運(yùn)用近似自然語(yǔ)言方式,可較好處理數(shù)據(jù)不確定性和非精確性[4]。粒子群算法屬于進(jìn)化算法的一種,以隨機(jī)解出發(fā)通過(guò)迭代尋找最優(yōu)解,該方法具有易實(shí)現(xiàn)、高精度和快收斂等特點(diǎn)[5-6]。蟻群算法是一種模擬螞蟻群體智能行為的仿生優(yōu)化算法,具有較強(qiáng)的魯棒性與適應(yīng)性[7-8]。偵察類移動(dòng)機(jī)器人體積較小,自身攜帶的傳感器數(shù)量與重量都有嚴(yán)格限制,導(dǎo)致其智能化水平與定位導(dǎo)航精度較低,所以創(chuàng)建與規(guī)劃的返航路徑需要有較高的可執(zhí)行性,才可以滿足實(shí)際使用要求。

本文針對(duì)小型移動(dòng)機(jī)器人在自主返航實(shí)際應(yīng)用中所存在的問(wèn)題,提出一種小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法。介紹偵察類小型移動(dòng)機(jī)器人的任務(wù)流程,設(shè)計(jì)移動(dòng)機(jī)器人的硬件系統(tǒng)。對(duì)所建立的柵格地圖進(jìn)行障礙物膨脹運(yùn)算,使用雙邊界路徑矢量化方法提取矢量路徑,并對(duì)該路徑進(jìn)行拓?fù)鋬?yōu)化。利用Dijkstra算法進(jìn)行路徑規(guī)劃,通過(guò)實(shí)驗(yàn)驗(yàn)證該算法的可行性。

2 小型移動(dòng)機(jī)器人任務(wù)流程及系統(tǒng)結(jié)構(gòu)

在遙控偵察的過(guò)程中機(jī)器人除了執(zhí)行任務(wù)外,自身所攜帶的多種傳感器自動(dòng)對(duì)周圍環(huán)境進(jìn)行地圖創(chuàng)建與定位。當(dāng)遙控信號(hào)被周邊樓群遮擋或被室內(nèi)墻壁屏蔽,或者任務(wù)執(zhí)行完成,移動(dòng)機(jī)器人將根據(jù)所建立的環(huán)境地圖規(guī)劃出一條最優(yōu)路徑,實(shí)現(xiàn)移動(dòng)機(jī)器人的自主返航。

小型移動(dòng)機(jī)器人系統(tǒng)構(gòu)架主要由傳感器系統(tǒng)、控制系統(tǒng)和運(yùn)載系統(tǒng)組成。傳感器系統(tǒng)使用激光雷達(dá)與捷聯(lián)慣導(dǎo)組合方式,進(jìn)行環(huán)境地圖創(chuàng)建與定位。激光雷達(dá)型號(hào)為單線UTM-30LX;微機(jī)電捷聯(lián)慣導(dǎo)型號(hào)為3DM-GX3-45,該慣導(dǎo)重量為23 g,適合安裝在微小型移動(dòng)機(jī)器人上進(jìn)行導(dǎo)航定位?？刂葡到y(tǒng)采用NI sbRIO-9626嵌入式控制板,該控制板采用Freescale的MPC5125微處理器,內(nèi)嵌VxWorks操作系統(tǒng)。本文所設(shè)計(jì)的自主返航路徑規(guī)劃方法在該控制板上實(shí)現(xiàn)。運(yùn)載系統(tǒng)采用NI Single-Board RIO機(jī)器人,該移動(dòng)機(jī)器人機(jī)構(gòu)及相應(yīng)系統(tǒng)部件安裝如圖1所示。

圖1 小型移動(dòng)機(jī)器人平臺(tái)

3 路徑網(wǎng)創(chuàng)建及返航路徑優(yōu)化

移動(dòng)機(jī)器人在探索環(huán)境時(shí)建立了與之對(duì)應(yīng)的柵格地圖,通過(guò)對(duì)柵格地圖的處理得到了小型移動(dòng)機(jī)器人自主返航路徑,其方法流程如圖2所示。首先,利用數(shù)學(xué)形態(tài)學(xué)中的膨脹算子對(duì)柵格地圖所描述的障礙物進(jìn)行膨脹運(yùn)算,生成了柵格Voronoi圖,形成了一組返航路徑網(wǎng);其次,對(duì)路徑網(wǎng)進(jìn)行雙邊界路徑矢量化得到矢量路徑網(wǎng),便于移動(dòng)機(jī)器人運(yùn)動(dòng)控制系統(tǒng)執(zhí)行;再次,為了減少數(shù)據(jù)存儲(chǔ)空間,提高路徑規(guī)劃效率,將矢量路徑進(jìn)行拓?fù)浠?最終,通過(guò)Dijkstra算法對(duì)拓?fù)渎窂竭M(jìn)行路徑規(guī)劃選出一條最優(yōu)返航路徑。

圖2 路徑規(guī)劃方法流程

3.1 結(jié)構(gòu)元素選擇方法

結(jié)構(gòu)元素是用于探測(cè)當(dāng)前柵格地圖的一個(gè)集合,在進(jìn)行形態(tài)學(xué)運(yùn)算時(shí)需要首先選擇結(jié)構(gòu)元素才可以進(jìn)行形態(tài)學(xué)運(yùn)算,如圖3所示3種結(jié)構(gòu)元素分別為正方形、鉆石形和線段形,其原點(diǎn)在結(jié)構(gòu)元素的幾何中心位置。結(jié)構(gòu)元素的形狀和尺寸必須適合于待處理目標(biāo)障礙的幾何性質(zhì),方形結(jié)構(gòu)元素適合處理建筑物等方形障礙物目標(biāo),線段結(jié)構(gòu)元素適合處理線形目標(biāo)[9]。本文所需處理的目標(biāo)對(duì)象為樓道、房屋等室內(nèi)環(huán)境地圖,所以選擇正方形作為結(jié)構(gòu)元素。

圖3 結(jié)構(gòu)元素形狀

3.2 數(shù)學(xué)形態(tài)學(xué)基本運(yùn)算

腐蝕算子以數(shù)學(xué)形態(tài)學(xué)為數(shù)學(xué)基礎(chǔ),利用結(jié)構(gòu)元素B對(duì)集合X進(jìn)行腐蝕可表示為εB(X),其定義為當(dāng)B的原點(diǎn)在x,B包含于X內(nèi)的x的所有軌跡點(diǎn),則:

其中,εB(X)為在移動(dòng)結(jié)構(gòu)元素的過(guò)程中,可以填入X內(nèi)部的結(jié)構(gòu)元素的所有原點(diǎn)組成,并具有收縮柵格地圖中障礙物的作用。

膨脹為腐蝕運(yùn)算的逆運(yùn)算,利用結(jié)構(gòu)元素B對(duì)集合X進(jìn)行膨脹表示為δB(X),δB(X)是腐蝕結(jié)果的補(bǔ)集,可表示為:

在利用結(jié)構(gòu)元素對(duì)集合X進(jìn)行膨脹,結(jié)果使集合X擴(kuò)大,該性質(zhì)具有膨脹柵格地圖中障礙物的作用。

3.3 基于膨脹算子的柵格Voronoi圖創(chuàng)建

為了明確膨脹邊界與原點(diǎn)之間的距離,使其更容易進(jìn)行邊界提取,采用一種基于正方形結(jié)構(gòu)的距離結(jié)構(gòu)元素,如圖4所示。該結(jié)構(gòu)元素原點(diǎn)為其幾何中心,周邊8個(gè)柵格表示距離原點(diǎn)距離為 1,第2層16個(gè)柵格表示距離原點(diǎn)距離為2,同時(shí)也表示為膨脹算子膨脹目標(biāo)柵格的層數(shù),該距離結(jié)構(gòu)元素?cái)?shù)學(xué)模型為:

其中,i,j為柵格編號(hào);a,b為柵格距離參數(shù)。

圖4 距離結(jié)構(gòu)元素

基于膨脹運(yùn)算使用距離結(jié)構(gòu)元素對(duì)柵格地圖進(jìn)行處理,通過(guò)循環(huán)遍歷地圖上的每一個(gè)柵格,當(dāng)柵格為空時(shí)使用式(3)對(duì)周圍8個(gè)柵格進(jìn)行掃描,如果周圍有障礙物則根據(jù)式(3)計(jì)算值對(duì)該空柵格進(jìn)行賦值,否則不對(duì)當(dāng)前柵格進(jìn)行操作,進(jìn)行下一個(gè)柵格的運(yùn)算。如下一個(gè)柵格已經(jīng)有初始值,則不做處理繼續(xù)掃描下一柵格。對(duì)柵格地圖進(jìn)行一次遍歷,所涉及的障礙物都均勻膨脹一圈,再進(jìn)行多次遍歷后,整張地圖無(wú)空閑柵格則膨脹運(yùn)算結(jié)束。提取出每個(gè)障礙物的膨脹邊界,從而組成了柵格Voronoi圖[10]。

由于Voronoi圖自身的數(shù)學(xué)屬性,所確定的路徑使移動(dòng)機(jī)器人與障礙物之間的距離最大化,因此該路徑對(duì)于移動(dòng)機(jī)器人運(yùn)動(dòng)控制具有較高的可執(zhí)行性。

3.4 雙邊界路徑矢量化方法

2個(gè)相鄰障礙物利用膨脹算子進(jìn)行處理后,生成了2個(gè)并行的邊界構(gòu)成了柵格Voronoi圖的路徑,所以稱該路徑為雙邊界路徑。所得到的邊界移動(dòng)機(jī)器人運(yùn)動(dòng)控制系統(tǒng)還無(wú)法識(shí)別,需要對(duì)其進(jìn)行矢量化處理。

雙邊界路徑矢量化方法采用2×2的柵格陣列作為檢測(cè)窗口,對(duì)生成的柵格Voronoi圖沿行、列方向進(jìn)行掃描。掃描方式如圖5所示,該圖中柵格為柵格Voronoi圖形成的雙邊界路徑。i,j為柵格序號(hào);x,y為柵格的長(zhǎng)寬距離;柵格中的數(shù)字為距離結(jié)構(gòu)元素膨脹障礙物時(shí)對(duì)柵格所賦的值。當(dāng)2×2的柵格陣列中4個(gè)窗口均有值,則確定一個(gè)矢量坐標(biāo)。而窗口有值數(shù)量小于等于3時(shí),表明該點(diǎn)不是所求路徑。當(dāng)窗口掃描完整張柵格Voronoi圖后,雙邊界路徑矢量化結(jié)束。

圖5 雙邊界路徑矢量化方法

移動(dòng)機(jī)器人運(yùn)動(dòng)控制系統(tǒng)在已知平臺(tái)自身的位置后,輸入目的地坐標(biāo)來(lái)實(shí)現(xiàn)平臺(tái)的運(yùn)動(dòng)。通過(guò)掃描整張柵格Voronoi圖,并將柵格自身的橫縱編號(hào)與預(yù)定的柵格長(zhǎng)寬距離分別相乘,即得到了路徑點(diǎn)橫縱坐標(biāo),實(shí)現(xiàn)了路徑矢量化。圖5的雙邊界路徑矢量化結(jié)果如圖6所示。

圖6 路徑矢量化結(jié)果

3.5 矢量路徑拓?fù)浠?/p>

拓?fù)渎窂剿璧拇鎯?chǔ)空間小,路徑規(guī)劃執(zhí)行效率高,適合大規(guī)模與高精度地圖環(huán)境下應(yīng)用。由于所得到的矢量路徑是以柵格地圖為基礎(chǔ),因此在其點(diǎn)集的橫縱方向上滿足直線方程:

在地圖中分別以行列方向進(jìn)行掃描,在確定路徑起始點(diǎn)后依次對(duì)后續(xù)點(diǎn)進(jìn)行計(jì)算。柵格距離參數(shù)已知,當(dāng)下一點(diǎn)距離小于等于該值時(shí),則表示與上一點(diǎn)連續(xù);當(dāng)下一點(diǎn)距離大于該值時(shí),則表示上一點(diǎn)為線段結(jié)束點(diǎn),此點(diǎn)為下一線段的起始點(diǎn)。全圖掃描結(jié)束后,記錄所有直線端點(diǎn)坐標(biāo)及起始點(diǎn)與結(jié)束點(diǎn)的連接關(guān)系,計(jì)算每條路徑的長(zhǎng)度,并對(duì)每一個(gè)節(jié)點(diǎn)重新編號(hào),供后續(xù)路徑規(guī)劃使用。矢量路徑拓?fù)浠Y(jié)果如圖7所示,該方法去除了多余點(diǎn),減少了數(shù)據(jù)冗余,實(shí)現(xiàn)了矢量路徑的拓?fù)浠痆11]。

圖7 拓?fù)渎窂?/p>

3.6 基于Dijkstra算法的路徑規(guī)劃

Dijkstra算法采用構(gòu)造最小生成樹(shù)的方法來(lái)進(jìn)行路徑規(guī)劃,以起始點(diǎn)為中心向外搜索路徑,直至到達(dá)終點(diǎn)為止,即計(jì)算出路徑規(guī)劃最優(yōu)解。根據(jù)拓?fù)渎窂剿峁┑臄?shù)據(jù)建立了路徑網(wǎng)模型為:

其中,S為起始節(jié)點(diǎn)向量;E為終止節(jié)點(diǎn)向量;W為邊權(quán)值向量,權(quán)值大小由所對(duì)應(yīng)的邊長(zhǎng)度決定。將該三組向量保存為關(guān)聯(lián)矩陣的稀疏矩陣形式,從而節(jié)省了地圖存儲(chǔ)空間。在路徑網(wǎng)G中,存在的n個(gè)節(jié)點(diǎn)與m條邊且每條邊的權(quán)值為Wi,通過(guò)尋找從起始點(diǎn)到結(jié)束點(diǎn)的路徑,使其各個(gè)邊所對(duì)應(yīng)的權(quán)值相加最小,則路徑規(guī)劃完成。路徑規(guī)劃算法步驟如下[12]:

(1)確定路徑規(guī)劃起始點(diǎn)與結(jié)束點(diǎn);

(2)通過(guò)對(duì)路徑網(wǎng)模型G的搜索,找到所有與待計(jì)算點(diǎn)直接連接的節(jié)點(diǎn),并分別與之前計(jì)算的邊權(quán)值進(jìn)行累加,得到從起始點(diǎn)到所有找到點(diǎn)的權(quán)值集合:

(3)從權(quán)值集合中尋找最小值di=min{W1,W2,…},所得最小值點(diǎn)作為下一次搜索的待計(jì)算點(diǎn)。

(4)循環(huán)步驟(2)和步驟(3),直至所有節(jié)點(diǎn)計(jì)算完畢。

當(dāng)路徑規(guī)劃結(jié)束后,得到一條由多個(gè)節(jié)點(diǎn)組成的最優(yōu)路徑。在矢量路徑拓?fù)浠^(guò)程中已經(jīng)對(duì)節(jié)點(diǎn)的坐標(biāo)進(jìn)行了記錄與編號(hào),通過(guò)查表形式將各個(gè)節(jié)點(diǎn)的坐標(biāo)按順序發(fā)送給移動(dòng)機(jī)器人運(yùn)動(dòng)控制系統(tǒng),即完成了移動(dòng)機(jī)器人的自主返航。

4 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文提出的自主返航路徑規(guī)劃方法的可行性,建立二維15×15的柵格環(huán)境地圖,地圖中模擬了真實(shí)環(huán)境中的點(diǎn)、線和面等障礙物。圖8所示是基于形態(tài)學(xué)膨脹算子的Voronoi圖,圖中黑色表示為障礙物。以障礙物為中心其邊緣柵格依次變淺,可以看出每進(jìn)行一次膨脹操作,所有障礙物都均勻膨脹一層,最終填滿整張地圖。

圖8 基于形態(tài)學(xué)膨脹算子的Voronoi圖

圖9為基于方形距離結(jié)構(gòu)元素的Voronoi圖,圖中柵格內(nèi)的數(shù)據(jù)表示為該柵格距離障礙物的大小。

圖9 基于方形距離結(jié)構(gòu)元素的Voronoi圖

圖10為柵格Voronoi圖邊界及雙邊界路徑矢量化的結(jié)果,圖中有數(shù)字的柵格為Voronoi圖的邊界,可以看出每一個(gè)障礙物周圍都由有一組完整的邊界包圍,2個(gè)相鄰障礙物之間形成了雙邊界路徑。利用雙邊界路徑矢量化方法對(duì)邊界進(jìn)行處理,得到了圖中的若干圓點(diǎn),由于柵格距離參數(shù)為已知,因此每個(gè)圓點(diǎn)的坐標(biāo)通過(guò)計(jì)算可以求得,從而生成了矢量路徑網(wǎng)。

圖10 柵格Voronoi圖邊界及雙邊界路徑矢量化結(jié)果

圖11為矢量路徑的拓?fù)浠奥窂揭?guī)劃結(jié)果,利用所提出的矢量路徑拓?fù)浠椒▽?duì)圖10中的若干數(shù)據(jù)點(diǎn)進(jìn)行處理,可以看出該方法去除多余圓點(diǎn),并且保證了移動(dòng)機(jī)器人運(yùn)行軌跡不發(fā)生變化。圖中圓圈數(shù)字是在拓?fù)浠^(guò)程中對(duì)所提取的節(jié)點(diǎn)進(jìn)行編號(hào),Dijkstra算法需使用此編號(hào)進(jìn)行路徑規(guī)劃。路徑上的數(shù)字為該條路徑的權(quán)值,也就是該路徑的長(zhǎng)度?；贒ijkstra算法的路徑規(guī)劃結(jié)果為①-②-⑥-⑦-⑨節(jié)點(diǎn),規(guī)劃出的路徑由圖中粗線表示。每個(gè)節(jié)點(diǎn)的坐標(biāo)已知,則通過(guò)計(jì)算可以將該坐標(biāo)直接發(fā)送給移動(dòng)機(jī)器人運(yùn)動(dòng)控制系統(tǒng),使機(jī)器人沿著預(yù)定路徑行駛。觀察路徑所處位置可以看出該路徑是機(jī)器人與障礙物之間的距離最大化,所以該路徑對(duì)于移動(dòng)機(jī)器人的運(yùn)動(dòng)具有較高的可執(zhí)行性,減少了因定位精度問(wèn)題發(fā)生碰撞的幾率。

圖11 矢量路徑拓?fù)浠吐窂揭?guī)劃結(jié)果

圖12為Dijkstra算法的加權(quán)圖,該圖中每條邊關(guān)聯(lián)一個(gè)權(quán)值,由若干節(jié)點(diǎn)與邊權(quán)值組成了圖模型。Dijkstra算法規(guī)劃出從節(jié)點(diǎn)1-節(jié)點(diǎn)2-節(jié)點(diǎn)6-節(jié)點(diǎn)7-節(jié)點(diǎn)9的最小生成樹(shù)。

圖12 Dijkstra算法的加權(quán)圖

5 結(jié)束語(yǔ)

遙控小型移動(dòng)機(jī)器人在室內(nèi)執(zhí)行任務(wù)時(shí)需具有自主返航能力,但由于自身體積與載重能力限制使其自身定位能力較差,易與周圍障礙物發(fā)生碰撞。本文提出了一種小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法,介紹小型移動(dòng)機(jī)器人的任務(wù)流程,并設(shè)計(jì)了移動(dòng)機(jī)器人的硬件系統(tǒng)。利用數(shù)學(xué)形態(tài)學(xué)中的膨脹算子對(duì)柵格地圖中的障礙物進(jìn)行膨脹運(yùn)算得到了柵格Voronoi圖。提出一種雙邊界路徑矢量化方法對(duì)柵格Voronoi圖進(jìn)行處理,從柵格地圖中提取出了矢量路徑,并對(duì)該矢量路徑進(jìn)行拓?fù)鋬?yōu)化,減少其冗余數(shù)據(jù)。通過(guò)Dijkstra算法對(duì)拓?fù)渎窂骄W(wǎng)進(jìn)行路徑規(guī)劃并進(jìn)行算法驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,該方法所規(guī)劃的路徑使機(jī)器人與障礙物之間距離最大化,使移動(dòng)機(jī)器人的運(yùn)動(dòng)軌跡具有較高的可執(zhí)行性,減少了因定位精度問(wèn)題發(fā)生碰撞的幾率,實(shí)現(xiàn)了小型移動(dòng)機(jī)器人在遙控信號(hào)丟失情況下的自主返航。

[1] 宋建梅,李 侃.基于A?算法的遠(yuǎn)程導(dǎo)彈三維航跡規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào),2007,27(7): 613-617.

[2] 粱金泉,周之平,黎 明,等.基于關(guān)鍵鏈遺傳操作的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程,2012,38(9): 166-169.

[3] 宋 勇,李貽斌,李彩虹.遞歸神經(jīng)網(wǎng)絡(luò)的進(jìn)化機(jī)器人路徑規(guī)劃方法[J].哈爾濱工程大學(xué)學(xué)報(bào),2009, 30(8):898-902.

[4] 于振中,鄭為湊,劉 鑫,等.基于Kinect的移動(dòng)機(jī)器人實(shí)時(shí)局部路徑規(guī)劃[J].計(jì)算機(jī)工程,2013,39(4): 243-247.

[5] 劉利強(qiáng),汪相國(guó),范志超.基于小生境粒子群優(yōu)化的船舶多路徑規(guī)劃方法[J].計(jì)算機(jī)工程,2013,39(9): 227-232.

[6] Roberge V,Tarbouchi M,Labonte G.Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-time UAV Path Planning[J]. IEEE Transactionson IndustrialInformatics,2013, 9(1):132-141.

[7] 周 波,錢 來(lái),孟正大,等.基于蟻群算法的噴圖機(jī)器人路徑排序優(yōu)化[J].計(jì)算機(jī)工程,2012,38(1): 192-194.

[8] Birattari M,Pellegrini P,Dorigo M.On the Invariance of Ant Colony Optimization[J].IEEE Transactions on Evolutionary Computation,2007,11(6):732-742.

[9] Soile P.MorphologicalImage Analysis Principles and Applications[M].Berlin,Germany:Springer-Verlag,2002.

[10] Li C,Chen J,LiZ.A Raster-based Method for Computing Voronoi Diagrams of Spatial Objects Using Dynamic Distance Transformation[J].International Journal of Geographical Information Science,1999, 13(3):209-225.

[11] Thrun S.Learning Metric-topological Maps for Indoor Mobile Robot Navigation[J].Artificial Intelligence, 1998,99(1):21-71.

[12] 馮欣欣.Dijkstra算法在嵌入式 GIS中的優(yōu)化實(shí)現(xiàn)[J].北京理工大學(xué)學(xué)報(bào),2009,29(10):873-876.

編輯 金胡考

Path Planning Method in Autonomous Returning for Mini-mobile Robot

JIANG Tao,WANG Jianzhong,SHI Jiadong
(State Key Laboratory of Explosion Science and Technology,Beijing Institute of Technology,Beijing 100081,China)

Aiming at the existing problem of low locating accuracy of teleoperation mini-mobile robot in the actual application of autonomous returning,a path planning method in autonomous returning for mini-mobile robot is proposed. The task process and hardware system for mobile robot is introduced.The obstacle in grid map by dilation operator is calculated,and the grid Voronoi diagram is acquired.From the grid map extracts the vector path by method of double boundary,and the vector path based on topology optimization is optimized.The topology path employing the Dijkstra algorithm is planned.The experiments of path planning are carried out.The experimental results show that the path maximizes the distance between mobile robot and obstacle,and the motion trajectory of mobile robot has higher executability.The success rates of autonomous returning for mini-mobile robot are enhanced.

mobile robot;mathematical morphology;path planning;Voronoi diagram;topological optimization;Dijkstra algorithm

1000-3428(2015)01-0164-05

A

TP242

10.3969/j.issn.1000-3428.2015.01.030

國(guó)家部委基金資助項(xiàng)目。

姜 濤(1984-),男,博士研究生,主研方向:智能控制,無(wú)人作戰(zhàn)平臺(tái);王建中,教授、博士生導(dǎo)師;施家棟,講師。

2014-02-25

2014-03-30 E-mail:eli_jiang@126.com

中文引用格式:姜 濤,王建中,施家棟.小型移動(dòng)機(jī)器人自主返航路徑規(guī)劃方法[J].計(jì)算機(jī)工程,2015,41(1):164-168.

英文引用格式:Jiang Tao,Wang Jianzhong,Shi Jiadong.Path Planning Method in Autonomous Returning for Minimobile Robot[J].Computer Engineering,2015,41(1):164-168.