分享到:

研發圖
聯絡我們 | 訪客留言 |
論 文 專 利 著 作 項 目 ZigBee 與 Uwb動態 技術FAQ
 
 

 

基于室內環境智能機器人路徑規劃算法的研究

尹 遠 陽1,金 純1 2, 王升剛1
(1.重慶郵電大學 通信與信息工程學院,重慶 400065;2.重慶金甌科技發展有限責任公司,重慶 400041;)
該論文發表于《通信技術》2013年第33卷第251期
刊號為:ISSN 1006-6403

摘要:隨著無線傳感器及家庭服務機器人的出現,而現有的路徑規劃算法中大多不能滿足實時性要求。本文提出一種針對室內環境的路徑規劃算法。該算法中通過采用柵格模型建立地圖,設定新的啟發函數,仿真結果表明該算法簡單實用、且計算速度快,且在已知家庭地圖的情況下該算法搜索時間有明顯的優勢,同時該算法能適用多障礙物的室內環境。

關鍵詞:智能機器人;無線傳感器;柵格法;路徑規劃; 中圖法分類號:TP 301







Intelligent robot path planning algorithm based on indoor environment
YIN Yuan-yang1,JIN Chun1、2,WANG Sheng-gang1

(1. Wireless Transmission Key Laboratory, School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China; 2. Chongqing Jinou Science & Technology Development Co., Ltd., Chongqing 400041, China)


Abstract:With the appearance of wireless sensor and family service robot, the existing path planning algorithm can’t meet the real-time requirements. This paper presents a path planning algorithm for indoor environment. The algorithm by using grid model map, setting new heuristic function, the simulation results show that the algorithm is simple and practical, and the calculation speed is fast. Under the condition of known family map the algorithm search time has obvious advantages, and the algorithm can be applied to many obstacles indoor environment.

Keywords:intelligent robot;wireless sensor;grid method;path planning;

1.引言

隨著物聯網、計算機技術、智能機器人的發展,移動機器人的應用場合也越來越受到人類的關注。移動機器人是集監測傳感器、動態決策和控制于一體的復雜控制系統。在這過程中,路徑規劃是移動機器人控制系統的核心技術之一[1]。上個世紀的60年代開始,國內外的學者就開對移動機器人的路徑規劃[2、3]進行了相關的研究,主要的路徑搜索算法有Dijkstra算法、A*算法[4]、人工勢場法,以及最近研究較多的神經網絡算法[5]、蟻群優化算法[6、7]、遺傳算法[8]等搜索技術。Dijkstra算法是荷蘭計算機科學家艾茲格?迪科斯徹發現的,是一種比較經典的求最短路徑的算法,采用的是廣度優先的遍歷算法,時間復雜度為O(n2),當在大地圖中使用該方法時,搜索時間明顯增加。蟻群算法、神經網絡算法、遺傳算法[5、6、7、8]等智能算法已經應用到機器人足跡規劃中。這些算法本身存在著一些缺陷,如局部尋優能力差、早熟現象等問題就很突出,嚴重影響路徑規劃的計算效率和可靠性。 本文結合服務機器人越來越多的在智能家居中應用,而提出在復雜的室內環境中運用機器人輔助完成各項任務的路徑規劃研究,該過程中機器人采用事件驅動工作模式。通過路徑算法機器人可以快速到達事發現場進行拍照和指令操作。這就要就機器人路徑規劃要有實時性,因此本文提出了一種基于柵格模型下的機器人實時路徑規劃算法。

2. 機器人的工作環境建模

在移動機器人工作環境中可以通過建立一個坐標系來具體描述,并將建好的坐標系分割成一個個小單元,形成柵格[9]。柵格邊的大小可以根據機器人一步行走的距離來劃分,這樣可以更精確地規劃出行走路徑,再通過放縮因子就可以準確得到現實中的距離。劃分的柵格分為兩種,自由柵格和障礙物柵格。自由柵格:柵格位置是可達的,機器人可以沒有約束地行走;障礙物柵格:機器人不能通過的場所。為了保證柵格的劃分,只要所分柵格中存在障礙物,該柵格就抽象為一個滿柵格塊。在MATLAB2009版中編程建立機器人工作的環境模型如圖所示。圖中每個柵格大小為一個單位長度的正方形,其中黑色部分表示的是環境中的障礙物,白色柵格表示為自由柵格。該模型近似于室內的家居環境。

虛擬柵格[9、10]是在機器人探知未知環境的同時所建立起來的環境信息,能通過編程實現的模擬環境。本文是通過以下假設實現:1>機器人能對室內的二維環境進行全覆蓋感知。2>當機器人進入某一柵格時,恰好是對該柵格的全覆蓋。3>機器人在環境中運動時忽略自身因機械損耗和摩擦帶來的誤差。4> 機器人在每個自由柵格中的移動選擇是以當前柵格為中心的其它八個相鄰自由柵格,且每次一步運動為一個柵格,具體運動關系如圖所示。

3.啟發式算法理論及分析

3.1 路徑規劃

家庭服務機器人運用在智能家居環境中,是為了能在家庭幫助戶主管理家庭內部設備的控制。而這就要求該家庭服務機器人對事件處理要有實時性,操作簡單性。因此針對室內環復雜境研究出一種實時快速的室內機器人路徑規劃是十分必要的。在眾多路徑規劃算法中,蟻群算法、遺傳算法等雖然能取得較好的最優路徑或次優路徑,但這些算法都是以時間為代價來取得好的效果,這不符合室內機器人快速達到現場查看的要求,因此本文選擇一種啟發函數[12]并結合柵格設定的室內地圖來實現機器人路徑規劃,工作流程如圖所示。

3.2 A*算法的思想和啟發函數的設計

A*算法[5、12]是對傳統的Dijkstra算法的有效改進,Dijkstra算法只是對路徑進行深度或廣度搜索后,選擇代價函數值最小的鏈路,因此對于節點數量多的網絡連通圖,計算量會明顯增加。為了解決這樣一個問題,A*算法中引入了估價函數,減少節點選擇搜索的盲目性,通過計算結果來選擇候選節點,這樣在某種程度上能減少對節點的搜索范圍,增加節點的選擇效率。 A*算法搜索過程中涉及到的每個節點的估價函數f(n)其形式如公式(1)所示[5]:
在式(1)中,其中f(n)代表A*算法中從起點(S)經過中間節點N到終點(T)的最短路徑的成本估計值;g(n)表示從起點S到當前節點N的實際消費值,h(n)則表示從當前節點N到達目標T點所需要的消費的預估值。而A*算法比Dijkstra算法優越性就體現在h(n)這個啟發函數上,因此啟發函數h(n)設計越好,所得的路徑規劃就越優越。 當室內設備發生故障時,機器人可通過無線傳感網絡收到警報信息確定故障的具體位置(因為機器人對室內環境已知)設為目標T,其坐標為( , ),為了進一步確認事故現場的情況及進行有效操作,機器人需要快速爬到故障位置處進行初步(主人通過終端發機器指令)。因此本文對啟發函數h(n)進行了精心設計。 傳統的A*算法所采用的啟發函數有曼哈頓距離、歐氏距離信息作為路徑搜索節點的信息,如果當前節點的坐標為( , )曼哈頓距離計算公式如式(2)所示:
由歐氏距離作為啟發函數h(n)的計算公式如式(3)所示:
這種節點的選擇作為評估方式存在一定的弊端,因為實際距離遠遠會比所估計的距離相差很大,其實在搜索過程中要得到快速且又近的路徑,不僅與所選擇的距離函數作為預測有關,還受到很多其他因素的影響,但傳統的方法只對距離因素進行了約束。本文就是在這基礎上不但選擇距離作為約束條件,還增加了機器人對目標搜索的方向函數作為約束條件,新設計的啟發函數如式(4)所示:
其中 為提高節點角度信息的一個權重因子,表示該節點的重要程度, 的具體取值是根據地圖的實際大小來確定, 是當前節點與目標節點組成的矢量與起始節點和目標節點組成的矢量的夾角,表示當前節點方向選擇,如果所得角度越小,則預估價函數的方向性選擇越強,越容易趨向目標節點,具體表示如圖所示。
由式(5)可以求得 的取值,且可以知道 的取值范圍為[0,90]度之間:
通過(5)式求得 的值后,結合式(4)可知 在[0,90]內是單調遞增的函數,這樣可以進一步保證代價函數f(n)取得最小,而使路徑搜索方向更明確,時間更快。

4 本文算法設計步驟

通過上述分析,可以知道啟發函數的好壞是路徑搜索的關鍵,在此詳細介紹本文的算法步驟。 Step1 算法初始化。建立柵格地圖,為地圖中的每個柵格分配好坐標,確定目標點位置(T),起點位置就為機器人當時所在位置(S)。 Step2 建立兩個列表。一個為CLOSED列表,用來儲存已搜索的節點和障礙物節點;另一個為OPEN列表,用來儲存當前節點的相鄰自由柵格。 Step3 設定估價函數初始值。將step1中的起點位置S放入OPEN中,并設估價函數初始值f(n)=0,g(n)=0。 Step4 確定搜索方向。以機器人最原始位置S到目標點T的矢量作為參考方向,計算當前節點的可選自由柵格(N)到目標節點組成的矢量與參考矢量的夾角,同時計算相應的歐氏距離,確定h(n)。 Step5 更新搜索節點。通過根據建立好的移動策略,機器人移動到下一柵格并更新g(n)、f(n)。選擇最小的f(n)值點作為當前選擇的點,并將該點放入CLOSED列表中。 Step6 判斷是否達到目標節點。如果達到則進入step7,否則跳入step4。 Step7 輸出路徑,算法結束。 該算法的具體流程如圖所示。

5 仿真實驗與分析

本文是在matlab2009版本軟件,CPU(AMD)處理頻率為2.5GHz,內存2GB的環境下進行的仿真,并結合了蟻群算法的路徑規劃進行了對比,針對不同的情況分別進行了三種不同的仿真分析。 仿真分析1:針對室內環境進行了柵格地圖的創建,該環境是20*20的柵格地圖,并在建好的地圖中隨機設置目標點和機器人的起始位置(這樣設置的目的是更能真實的反應機器人在巡邏時收到跌倒報警信息時,可以自由的從室內任何一個位置快速到達跌倒位置進行查看),在系統中是把跌倒處理事件設置為優先級最高,通過這樣的規定能確保機器人第一反應的是對跌倒進行檢測工作。在該環境下的仿真結果如圖6 所示,其中圖中(a)表示本文算法,(b、c)分別表示蟻群算法的仿真圖。

由仿真可知本文算法能較好的得到一條通往目標點的路徑,相對蟻群算法能得到更好短的路徑,雖然蟻群算法經過多次迭代最終也能尋找到一條相對較優的路徑,但本文算法更能滿足實時性的路徑規劃要求。 仿真分析2 :為了驗證本文算法對不同柵格數地圖在路徑搜索的實時性,分別針對柵格數為10*10、15*15、20*20、30*30的地圖進行仿真分析,每一種相同柵格地圖中障礙物相同,并對每種柵格地圖隨機設置障礙物經過10次統計每種地圖中路徑搜索時間和再求均值,10次平均搜索耗時如表1所示,列出了本文算法同傳統的A*算法以及蟻群算法在不同環境下的時間統計平均耗時。
仿真2通過對不同柵格數的地圖下進行了分析,從表1可以看到隨著柵格數目的增加,這幾種算法在障礙物相同的情況下搜索時間都在不斷變大,但本文算法的搜索時間變化不是特別明顯,能很好的滿足時間效率。這對機器人用于突發事件的實時性處理的路徑規劃非常有意義。 仿真分析3:為了討論在固定柵格地圖中障礙物所占比例不同,對機器人路徑規劃搜索的影響。該仿真在同一種柵格地圖(20*20)中,隨機設置障礙物比例分別為10%、20%、30%、50%四種情形,仿真結果如圖7a、7b、7c、7d所示。為了統計搜索時間,每種情形通過10次仿真后對搜索時間進行統計平均,搜索時間如表所示。
通過仿真3可知,在同一種柵格地圖中,隨著障礙物的不斷增大,雖然都能找到一條到目標點的路徑,但蟻群算法的搜索時間在增大。由于本文算法中對設置的障礙物直接放入了不需要搜索的鏈表中,從而保證了搜索節點相應減少,因此搜索時間反而變快(且這種情況在更大的柵格地圖中更能體現這種優勢),這更能說明本文算法能適用已知地圖環境中更復雜、障礙物多的環境,當然遺傳算法、蟻群算法等在路徑規劃中也有它獨特的優勢。

6. 結 論

本文針對智能家居環境中服務機器人的發展,從而針對室內服務機器人情形研究了一種運用柵格模型建立地圖和采用啟發函數作為搜索因子的快速路徑規劃算法。通過上述的三種仿真結果可以知道,本文算法能有效的解決室內障礙物的影響,并能快速針對目標位置進行搜索,具有很好的魯棒性。由于機器人是集成多傳感器的一個整體,機器人通過搜索的路徑到達事發地點,啟用相應的設備完成檢測任務。同時本文算法還可以應用到其他復雜環境,特別是在已知環境地圖、同時也有大量障礙物的路徑搜索的情況下更能體現它的優勢。

參考文獻
[1] SOULIGNAC M. Feasible and optimal path planning in strong current fileds[J].IEEE Transactions on Robotics, 2011,27(1): 89-98.
[2] ALEXOPOULOS C, GRIFFIN P M. Path planning for a mobile robot[J].IEEE Trans on System Man and Cybemetics,1992, 22(2): 318-322.
[3]TSAI C C,HUANG H C,CHAN C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[C].In Proceedings of IEEE international Conference on Computer Applications,Shipbuilding, 2011, : 4813-4821.
[4] 漆陽華,楊戰平,黃清華. A*的改進路徑規劃算法[J].信息與電子工程,2009, 7(4): 326-329.
[5] 宋勇,李貽斌,栗春等.基于神經網絡的移動機器人路徑規劃方法[J].系統工程與電子技術,2008, 30(2):316-319.
[6] 張美玉,黃翰,郝志峰等.基于蟻群算法的機器人路徑規劃[J].計算機工程與應用,2005, 25: 34-37.
[7] 潘杰,王雪松,程玉虎. 改進蟻群算法的移動機器人路徑規劃[J].中國礦業大學學報, 2012, 41(1): 108-113.
[8] 崔瑾娟. 基于遺傳算法的機器人路徑規劃[J].洛陽師范學院學報,2013, 32(2):35-42.
[9] 吳 鋒, 楊宜民. 一種基于柵格模型的機器人路徑規劃算法[J].現代計算機,2012, 02: 7-13.
[10] 周郭許,唐西林. 基于柵格模型的機器人路徑規劃快速算法[J]. 計算機工程與應用, 2006, 21: 197-199.
[11] ZHOU FENGYU, SONG BAOYE, TIAN Guohui. Bezier Curve Based Smooth Path Planning for Mobile Robot[J].Journal of Information & Computational Science, 2011, 12(8): 2441–2450.
[12] 賈振華,斯慶巴拉,王慧娟.基于啟發式機器人路徑規劃仿真研究[J].計算機仿真,2012,29(1):135-138.

作者簡介:
尹遠陽 (1986—) 碩士研究生 研究方向:無線通信、智能算法等
金純 (1966—) 博士、教授、研究生導師 主要研究方向:無線通信、 計算機軟件、物聯網、數字電視等
王升剛 (1986-)碩士研究生 研究方向:無線傳感器網絡、機器人定位等

 

北京南城搬家公司