基于GIS地圖的移動機器人路徑規劃

張麗娟，畢德學

(天津科技大學機械工程學院，天津 300222)

基于GIS地圖的移動機器人路徑規劃

張麗娟，畢德學

(天津科技大學機械工程學院，天津 300222)

針對移動機器人路徑規劃實現條件的限制，提出基于GIS(geographic information system)地圖的移動機器人路徑規劃．該方法應用改進A*算法，較好地實現了移動機器人的最優路徑規劃．在任意給定的地圖中，只要確定了機器人的起點和終點，就可以找到該機器人在實際工作環境中符合需求的路徑規劃軌跡．應用VC++編程進行實驗，證明了該方法的有效性．

機器人路徑規劃；GIS地圖；改進A*算法；估價函數

機器人路徑規劃是智能機器人研究領域中的一個核心問題，其研究的目的是希望未來的智能機器人具有感知、規劃和控制等高層能力，即它們能從周圍的環境中收集信息，構建一個關于所在環境的模型，并且利用這個模型來規劃和執行高層任務．路徑規劃的核心是，在給定全局信息的地圖中機器人能夠躲避障礙物，并且按照一定的評價標準找到一條從起點到終點的可行路徑[1–2]．

典型的機器人路徑規劃方法有可視圖法、自由空間法、柵格法、人工勢場法等．因為各種方法在環境信息完全已知的情況下，均對地域地形、障礙物形狀有嚴格要求，所以對移動機器人的應用環境有一定的局限性．A*算法是人工智能中的一種典型的啟發式搜索算法，它引入了啟發函數的概念，加入了全局信息[2]．可以將傳統A*算法用于機器人路徑規劃，尋求最短路徑[3]．但是在實際應用中，還需要根據實際情況進行道路的選擇，即對于不同的環境信息(例如：公路、房屋、草坪、操場等)，要權衡各種路況信息，進行綜合評價后決策．

本文應用改進A*算法提出基于GIS(geographic information system)地圖的移動機器人路徑規劃，可以實現在任意地圖中綜合考慮環境中的所有信息，按照一定的評價標準找到相對評價標準的最優路徑，而并非可行走意義上的最短路徑．

1 A*算法

1.1 A*算法原理

A*算法廣泛應用于最優路徑求解和一些策略設計的問題中，其關鍵元素是啟發函數，記為f(n)，f(n)為起點到達節點的耗散g(n)和從該節點到目標節點的耗散h(n)的綜合評價，即：f(n)＝g(n)＋h(n)．其中，g(n)給出了從起始節點到節點n的路徑耗散，而h(n)是啟發式搜索中最為重要的一部分，是從節點n到目標節點的最低耗散路徑的估計耗散值．因此，f(n)等于經過節點n的最低耗散解的估計耗散[4]．當啟發函數f(n)＝g(n)，即h(n)＝0時，A*算法退化為廣度優先搜索算法；當啟發函數f(n)＝h(n)，即g(n)＝0時，A*算法退化為貪心算法[5]．

1.2 A*算法核心過程

在每次選擇下一個當前搜索點時，是從所有已探知的但未搜索過的點中選取最有希望到達終點的點(f最小的點)進行展開，其中“所有已探知的但未搜索過的點”可通過一個按f升序排列的表獲得．在f升序排列的表中，取表頭節點，對其可能子節點計算g、h和f的數值，直到表為空或找到終點為止[6]．

2 改進A*算法

2.1 改進A*算法思想

改進A*算法的思想是通過改變代價函數的權值來處理不同的環境信息．針對不同的路況和不同的需求信息，選擇不同的權值進行代價函數的優化處理，改進的A*算法提高了機器人路徑規劃的智能化程度．

在一些情況下，還需要對可行路徑進行優化，即減少不必要的路過點．假設機器人路徑規劃中記錄的可行點為(n1，n2，…)，那么可通過計算其中兩點間是否有障礙物來進行篩選，如果兩點間無障礙物，則直接保存這兩點，忽略中間的可行路徑點，達到優化可行路徑的目的．另外，某些情況還需要進行路徑平滑．此時，可通過對可行路徑節點的代價值進行加權處理得到，如果下一可行路徑點相對于之前所走路徑有轉角，則增加此下一可行節點的代價值，使其所選節點走出的路徑盡量平滑[7]．

2.2 改進A*算法的實現

(1)創建列表Open，初始化為只包含起始點．(2)創建列表Close，初始化為空．

(3)從Open表中選擇f數值最小的節點nmin，將其從Open表中刪除，并插入到Close表的表頭．

(4)如果nmin是目標節點，停止搜索．

(5)對于nmin的8個相鄰節點：如果m在Close表中，則跳過此節點；如果m在Open表中且當前g(m)更小，更新節點m的g(m)，并使其父節點指向nmin；如果m不在Open和Close兩表中，根據具體情況，區分出道路、房屋、草坪、操場等，按照給定的具體情況的不同權值分別計算f，將m插入到Open表中，插入的同時排序，使得Open表中f數值始終都為從小到大排列，計算m點的f，并將其父節點指向nmin．

(6)返回(3)，繼續搜索．

(7)從終點向上回溯到起始點，記錄柵格路徑．

3 實 驗

為驗證算法用于機器人路徑規劃的有效性，將本文算法與A*算法進行對比．實驗用的計算機配置：處理器Inel(R)Pentium(R)Dual E2160 @ 1.80,GHz 1.79,GHz，內存1,GB 266.0,MHz．

3.1 地圖的基本處理

實驗中機器人實時提取信息，故地圖采用灰度圖像. 灰度圖像只包含亮度信息，通常劃分成0～255共256個級別，0最暗，255最亮．灰度圖像具有以下優點：(1)灰度圖像是將彩色圖像的RGB值通過一定的算法量化得到，其同一像素的RGB值相等；(2)圖像數據即調色板索引值，也就是實際的RGB亮度值；(3)灰度圖像使用256色的調色板，圖像數據中一個字節代表一個像素，便于計算機處理．

圖1為應用于機器人路徑規劃的基本地圖，圖中的環境信息中包含房屋、道路、草坪、樹木等．為滿足需要，在實驗前已對地圖進行必要的處理，包括灰度轉化、直方圖均衡化等處理．

圖1 實驗用基本地圖Fig. 1 Basic map for the experiment

3.2 基于A*算法的機器人路徑規劃

實驗中設置：房屋、草坪、樹木為機器人不可達區域，道路、平地為機器人可行走區域．對圖1采用A*算法進行機器人路徑規劃，其結果如圖2所示．圖

2中路徑規劃的節點個數為258，耗時1.844,s．

圖2 基于A* 算法的機器人路徑規劃軌跡Fig. 2 Path of the robot based on A* algorithm

3.3 基于改進A*算法的機器人路徑規劃

路徑規劃采用的評價標準為在安全性的情況下，路徑最短，耗能和時間最少．實驗中設置：房屋墻壁、樹木不可通行，即權值為無窮大；因為公路摩擦力小，耗能少，時間短，則相應選取的權值小；草坪在路過時摩擦力大，耗能大，則相應選取的權值較大．

分別取不同的權值進行機器人路徑規劃．設置在道路的權值為0.8，草坪的權值為1.4，路徑規劃結果如圖3(a)所示．圖3(a)中路徑規劃的節點個數為205，耗時0.172,s．設置道路的權值為0.8，草坪的權值為1.8，路徑規劃結果如圖3(b)所示．圖3(b)路徑規劃的節點個數為214，耗時0.109,s．

3.4 結果分析

由圖2可以看出應用A*算法找到了一條可行的最短路徑．對于兩點間求解最優路徑問題，只要有解，A*算法一定可以求得最優解，在圖2也得到證明.

由圖3可以看出，機器人找到一條由起點通向終點的最優路徑．與圖2不同的是，在圖3中機器人選擇穿過草坪到達目的地．出現圖3中路徑規劃結果的原因是，在給定的評價標準中，草坪并非嚴格不可行，只是相對道路而言不是優先選擇．應用改進A*算法的機器人路徑規劃相比應用A*算法的機器人路徑規劃而言，實現了自主選擇通過草坪而到達終點的目的，并且可以通過改變道路或者草坪的權值來實現不同的路徑規劃，可滿足實際應用的需求．

對比圖3(a)和圖3(b)可知，在不改變道路的權值，而增大草坪權值的情況下，機器人選擇盡量避開草坪．在實際生活中，如果發生緊急事件，要求綜合考慮整體評價標準，且對時間性要求很高時，可以像基于改進A*算法實驗中所選擇的一樣，通過草坪而到達目的地，此時A*算法不能實現．

圖3 基于改進A*算法的機器人路徑規劃軌跡Fig. 3 Path of the robot based on improved A* algorithm

綜上可以看出，改進A*算法的機器人路徑規劃方法通過綜合評價，選擇對整體更有利的路線，達到整體效果最優，可得到實際應用中的最優路徑．

4 結 語

本文基于改進A*算法實現基于GIS地圖的移動機器人路徑規劃，并進行實驗．通過實驗結果可以看出，該方法考慮更多實際因素，能實現符合實際需求的最優路徑規劃，而并非只是可行走意義上的最短路徑規劃，從而更符合實際需求.

［1］ 黎紅. 自主移動機器人路徑規劃中的主要方法[J]. 中國電力教育，2010(s1)：814–816.

［2］ Masehian E，Amin-Naseri M R. A voronoi diagramvisibility graph-potential field compound algorithm for robot path planning[J]. Journal of Robotic Systems，2004，21(6)：275–300.

［3］ 石為人，黃興華，周偉. 基于改進人工勢場法的移動機器人路徑規劃[J]. 計算機應用，2010，30(8)：2021–2023.

［4］ 周毅，崔剛. 基于機器視覺和A*算法的迷宮機器人路徑規劃[J]. 微計算機信息，2010，26(3-2)：155–156.

［5］ 朱耿青. A*算法實現及其應用[J]. 福建電腦，2008 (2)：74–75.

［6］ 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統中的應用[J]. 計算機系統應用，2007(4)：14–17.

［7］ Russell S，Norvig P. Artificial Intelligence：A Modern Approach[M]. 3,rd. Upper Saddle River：Prentice Hall Press，2009.

［8］ 陳剛，付少鋒，周利華. A*算法在游戲地圖尋徑中的幾種改進策略研究[J]. 科學技術與工程，2007，7(15)：3731–3736.

責任編輯：常濤

Path Planning of Mobile Robot Based on GIS Map

ZHANG Lijuan，BI Dexue
(College of Mechanical Engineering，Tianjin University of Science & Technology，Tianjin 300222，China)

The realization of the mobile robot path planning has certain restrictions. To deal with this problem, a novel mobile robot path planning method based on GIS(geographic information system)map was proposed. The optimal path planning was realized through improved A*algorithm. If the starting and ending points in any given map are given to a mobile robot，the path of the robot can be traced. The proposed path planning has been proved optimal and can satisfy the requirement of the practical environment. The experiments were based on VC++ and the effectiveness of this method has been proved.

robot path planning；GIS map；improved A*algorithm；estimable function

TP242

A

1672-6510(2012)03-0068-03

2011–11–29；

2012–02–22

張麗娟（1986—），女，天津人，碩士研究生；通信作者：畢德學，教授，dexue@tust.edu.cn.