基于GIS地圖的移動機器人路徑規(guī)劃

張麗娟，畢德學(xué)

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

基于GIS地圖的移動機器人路徑規(guī)劃

張麗娟，畢德學(xué)

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

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

機器人路徑規(guī)劃；GIS地圖；改進A*算法；估價函數(shù)

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

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

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

1 A*算法

1.1 A*算法原理

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

1.2 A*算法核心過程

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

2 改進A*算法

2.1 改進A*算法思想

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

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

2.2 改進A*算法的實現(xiàn)

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

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

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

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

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

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

3 實 驗

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

3.1 地圖的基本處理

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

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

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

3.2 基于A*算法的機器人路徑規(guī)劃

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

2中路徑規(guī)劃的節(jié)點個數(shù)為258，耗時1.844,s．

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

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

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

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

3.4 結(jié)果分析

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

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

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

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

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

4 結(jié) 語

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

［1］ 黎紅. 自主移動機器人路徑規(guī)劃中的主要方法[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］ 石為人，黃興華，周偉. 基于改進人工勢場法的移動機器人路徑規(guī)劃[J]. 計算機應(yīng)用，2010，30(8)：2021–2023.

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

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

［6］ 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J]. 計算機系統(tǒng)應(yīng)用，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]. 科學(xué)技術(shù)與工程，2007，7(15)：3731–3736.

責(zé)任編輯：常濤

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—），女，天津人，碩士研究生；通信作者：畢德學(xué)，教授，dexue@tust.edu.cn.