張麗娟，畢德學(xué)

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

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

張麗娟，畢德學(xué)

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

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

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

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

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

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

1 A*算法

1.1 A*算法原理

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

1.2 A*算法核心過程

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

2 改進(jìn)A*算法

2.1 改進(jìn)A*算法思想

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

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

2.2 改進(jìn)A*算法的實(shí)現(xiàn)

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

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

(4)如果nmin是目標(biāo)節(jié)點(diǎn)，停止搜索．

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

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

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

3 實(shí) 驗(yàn)

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

3.1 地圖的基本處理

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

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

圖1 實(shí)驗(yàn)用基本地圖Fig. 1 Basic map for the experiment

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

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

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

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

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

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

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

3.4 結(jié)果分析

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

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

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

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

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

4 結(jié) 語

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

［1］ 黎紅. 自主移動(dòng)機(jī)器人路徑規(guī)劃中的主要方法[J]. 中國(guó)電力教育，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ìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用，2010，30(8)：2021–2023.

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

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

［6］ 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(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ìn)策略研究[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.