小型移動機器人自主返航路徑規劃方法

姜 濤,王建中,施家棟

(北京理工大學爆炸科學與技術國家重點實驗室,北京100081)

小型移動機器人自主返航路徑規劃方法

姜 濤,王建中,施家棟

(北京理工大學爆炸科學與技術國家重點實驗室,北京100081)

針對遙控小型移動機器人在自主返航實際應用中定位精度低等問題,提出一種小型移動機器人自主返航路徑規劃方法。介紹小型移動機器人的任務流程及硬件系統,利用膨脹算子對柵格地圖中的障礙物進行運算得到柵格Voronoi圖。使用雙邊界路徑矢量化方法從柵格Voronoi圖中提取出矢量路徑,并對該路徑進行拓撲優化。通過Dijkstra算法對拓撲路徑進行路徑規劃并進行算法驗證。實驗結果表明,該方法所得路徑可使環境中的機器人與障礙物之間的距離最大化,并使移動機器人的運動軌跡具有較高的可執行性,提高了小型移動機器人自主返航的成功率。

移動機器人;數學形態學;路徑規劃;Voronoi圖;拓撲優化;Dijkstra算法

1 概述

小型移動機器人主要用于城市巷戰執行偵察任務,通常采用遙控方式進入偵察區域,在樓宇間或房屋樓道內進行情報搜集。在實際使用過程中,遙控信號在樓群或室內極易被遮擋與屏蔽,所以需要移動機器人在失去控制時進行路徑規劃使其具有自主返航能力。

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

本文針對小型移動機器人在自主返航實際應用中所存在的問題,提出一種小型移動機器人自主返航路徑規劃方法。介紹偵察類小型移動機器人的任務流程,設計移動機器人的硬件系統。對所建立的柵格地圖進行障礙物膨脹運算,使用雙邊界路徑矢量化方法提取矢量路徑,并對該路徑進行拓撲優化。利用Dijkstra算法進行路徑規劃,通過實驗驗證該算法的可行性。

2 小型移動機器人任務流程及系統結構

在遙控偵察的過程中機器人除了執行任務外,自身所攜帶的多種傳感器自動對周圍環境進行地圖創建與定位。當遙控信號被周邊樓群遮擋或被室內墻壁屏蔽,或者任務執行完成,移動機器人將根據所建立的環境地圖規劃出一條最優路徑,實現移動機器人的自主返航。

小型移動機器人系統構架主要由傳感器系統、控制系統和運載系統組成。傳感器系統使用激光雷達與捷聯慣導組合方式,進行環境地圖創建與定位。激光雷達型號為單線UTM-30LX;微機電捷聯慣導型號為3DM-GX3-45,該慣導重量為23 g,適合安裝在微小型移動機器人上進行導航定位。控制系統采用NI sbRIO-9626嵌入式控制板,該控制板采用Freescale的MPC5125微處理器,內嵌VxWorks操作系統。本文所設計的自主返航路徑規劃方法在該控制板上實現。運載系統采用NI Single-Board RIO機器人,該移動機器人機構及相應系統部件安裝如圖1所示。

圖1 小型移動機器人平臺

3 路徑網創建及返航路徑優化

移動機器人在探索環境時建立了與之對應的柵格地圖,通過對柵格地圖的處理得到了小型移動機器人自主返航路徑,其方法流程如圖2所示。首先,利用數學形態學中的膨脹算子對柵格地圖所描述的障礙物進行膨脹運算,生成了柵格Voronoi圖,形成了一組返航路徑網;其次,對路徑網進行雙邊界路徑矢量化得到矢量路徑網,便于移動機器人運動控制系統執行;再次,為了減少數據存儲空間,提高路徑規劃效率,將矢量路徑進行拓撲化;最終,通過Dijkstra算法對拓撲路徑進行路徑規劃選出一條最優返航路徑。

圖2 路徑規劃方法流程

3.1 結構元素選擇方法

結構元素是用于探測當前柵格地圖的一個集合,在進行形態學運算時需要首先選擇結構元素才可以進行形態學運算,如圖3所示3種結構元素分別為正方形、鉆石形和線段形,其原點在結構元素的幾何中心位置。結構元素的形狀和尺寸必須適合于待處理目標障礙的幾何性質,方形結構元素適合處理建筑物等方形障礙物目標,線段結構元素適合處理線形目標[9]。本文所需處理的目標對象為樓道、房屋等室內環境地圖,所以選擇正方形作為結構元素。

圖3 結構元素形狀

3.2 數學形態學基本運算

腐蝕算子以數學形態學為數學基礎,利用結構元素B對集合X進行腐蝕可表示為εB(X),其定義為當B的原點在x,B包含于X內的x的所有軌跡點,則:

其中,εB(X)為在移動結構元素的過程中,可以填入X內部的結構元素的所有原點組成,并具有收縮柵格地圖中障礙物的作用。

膨脹為腐蝕運算的逆運算,利用結構元素B對集合X進行膨脹表示為δB(X),δB(X)是腐蝕結果的補集,可表示為:

在利用結構元素對集合X進行膨脹,結果使集合X擴大,該性質具有膨脹柵格地圖中障礙物的作用。

3.3 基于膨脹算子的柵格Voronoi圖創建

為了明確膨脹邊界與原點之間的距離,使其更容易進行邊界提取,采用一種基于正方形結構的距離結構元素,如圖4所示。該結構元素原點為其幾何中心,周邊8個柵格表示距離原點距離為 1,第2層16個柵格表示距離原點距離為2,同時也表示為膨脹算子膨脹目標柵格的層數,該距離結構元素數學模型為:

其中,i,j為柵格編號;a,b為柵格距離參數。

圖4 距離結構元素

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

由于Voronoi圖自身的數學屬性,所確定的路徑使移動機器人與障礙物之間的距離最大化,因此該路徑對于移動機器人運動控制具有較高的可執行性。

3.4 雙邊界路徑矢量化方法

2個相鄰障礙物利用膨脹算子進行處理后,生成了2個并行的邊界構成了柵格Voronoi圖的路徑,所以稱該路徑為雙邊界路徑。所得到的邊界移動機器人運動控制系統還無法識別,需要對其進行矢量化處理。

雙邊界路徑矢量化方法采用2×2的柵格陣列作為檢測窗口,對生成的柵格Voronoi圖沿行、列方向進行掃描。掃描方式如圖5所示,該圖中柵格為柵格Voronoi圖形成的雙邊界路徑。i,j為柵格序號;x,y為柵格的長寬距離;柵格中的數字為距離結構元素膨脹障礙物時對柵格所賦的值。當2×2的柵格陣列中4個窗口均有值,則確定一個矢量坐標。而窗口有值數量小于等于3時,表明該點不是所求路徑。當窗口掃描完整張柵格Voronoi圖后,雙邊界路徑矢量化結束。

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

移動機器人運動控制系統在已知平臺自身的位置后,輸入目的地坐標來實現平臺的運動。通過掃描整張柵格Voronoi圖,并將柵格自身的橫縱編號與預定的柵格長寬距離分別相乘,即得到了路徑點橫縱坐標,實現了路徑矢量化。圖5的雙邊界路徑矢量化結果如圖6所示。

圖6 路徑矢量化結果

3.5 矢量路徑拓撲化

拓撲路徑所需的存儲空間小,路徑規劃執行效率高,適合大規模與高精度地圖環境下應用。由于所得到的矢量路徑是以柵格地圖為基礎,因此在其點集的橫縱方向上滿足直線方程:

在地圖中分別以行列方向進行掃描,在確定路徑起始點后依次對后續點進行計算。柵格距離參數已知,當下一點距離小于等于該值時,則表示與上一點連續;當下一點距離大于該值時,則表示上一點為線段結束點,此點為下一線段的起始點。全圖掃描結束后,記錄所有直線端點坐標及起始點與結束點的連接關系,計算每條路徑的長度,并對每一個節點重新編號,供后續路徑規劃使用。矢量路徑拓撲化結果如圖7所示,該方法去除了多余點,減少了數據冗余,實現了矢量路徑的拓撲化[11]。

圖7 拓撲路徑

3.6 基于Dijkstra算法的路徑規劃

Dijkstra算法采用構造最小生成樹的方法來進行路徑規劃,以起始點為中心向外搜索路徑,直至到達終點為止,即計算出路徑規劃最優解。根據拓撲路徑所提供的數據建立了路徑網模型為:

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

(1)確定路徑規劃起始點與結束點;

(2)通過對路徑網模型G的搜索,找到所有與待計算點直接連接的節點,并分別與之前計算的邊權值進行累加,得到從起始點到所有找到點的權值集合:

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

(4)循環步驟(2)和步驟(3),直至所有節點計算完畢。

當路徑規劃結束后,得到一條由多個節點組成的最優路徑。在矢量路徑拓撲化過程中已經對節點的坐標進行了記錄與編號,通過查表形式將各個節點的坐標按順序發送給移動機器人運動控制系統,即完成了移動機器人的自主返航。

4 實驗結果及分析

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

圖8 基于形態學膨脹算子的Voronoi圖

圖9為基于方形距離結構元素的Voronoi圖,圖中柵格內的數據表示為該柵格距離障礙物的大小。

圖9 基于方形距離結構元素的Voronoi圖

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

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

圖11為矢量路徑的拓撲化及路徑規劃結果,利用所提出的矢量路徑拓撲化方法對圖10中的若干數據點進行處理,可以看出該方法去除多余圓點,并且保證了移動機器人運行軌跡不發生變化。圖中圓圈數字是在拓撲化過程中對所提取的節點進行編號,Dijkstra算法需使用此編號進行路徑規劃。路徑上的數字為該條路徑的權值,也就是該路徑的長度。基于Dijkstra算法的路徑規劃結果為①-②-⑥-⑦-⑨節點,規劃出的路徑由圖中粗線表示。每個節點的坐標已知,則通過計算可以將該坐標直接發送給移動機器人運動控制系統,使機器人沿著預定路徑行駛。觀察路徑所處位置可以看出該路徑是機器人與障礙物之間的距離最大化,所以該路徑對于移動機器人的運動具有較高的可執行性,減少了因定位精度問題發生碰撞的幾率。

圖11 矢量路徑拓撲化和路徑規劃結果

圖12為Dijkstra算法的加權圖,該圖中每條邊關聯一個權值,由若干節點與邊權值組成了圖模型。Dijkstra算法規劃出從節點1-節點2-節點6-節點7-節點9的最小生成樹。

圖12 Dijkstra算法的加權圖

5 結束語

遙控小型移動機器人在室內執行任務時需具有自主返航能力,但由于自身體積與載重能力限制使其自身定位能力較差,易與周圍障礙物發生碰撞。本文提出了一種小型移動機器人自主返航路徑規劃方法,介紹小型移動機器人的任務流程,并設計了移動機器人的硬件系統。利用數學形態學中的膨脹算子對柵格地圖中的障礙物進行膨脹運算得到了柵格Voronoi圖。提出一種雙邊界路徑矢量化方法對柵格Voronoi圖進行處理,從柵格地圖中提取出了矢量路徑,并對該矢量路徑進行拓撲優化,減少其冗余數據。通過Dijkstra算法對拓撲路徑網進行路徑規劃并進行算法驗證。實驗結果表明,該方法所規劃的路徑使機器人與障礙物之間距離最大化,使移動機器人的運動軌跡具有較高的可執行性,減少了因定位精度問題發生碰撞的幾率,實現了小型移動機器人在遙控信號丟失情況下的自主返航。

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

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

[3] 宋 勇,李貽斌,李彩虹.遞歸神經網絡的進化機器人路徑規劃方法[J].哈爾濱工程大學學報,2009, 30(8):898-902.

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

[5] 劉利強,汪相國,范志超.基于小生境粒子群優化的船舶多路徑規劃方法[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] 周 波,錢 來,孟正大,等.基于蟻群算法的噴圖機器人路徑排序優化[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中的優化實現[J].北京理工大學學報,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

國家部委基金資助項目。

姜 濤(1984-),男,博士研究生,主研方向:智能控制,無人作戰平臺;王建中,教授、博士生導師;施家棟,講師。

2014-02-25

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

中文引用格式:姜 濤,王建中,施家棟.小型移動機器人自主返航路徑規劃方法[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.