基于A*算法在蜂巢柵格地圖中的路徑規(guī)劃研究

陶 哲， 高躍飛， 鄭天江， 李俊杰， 李保在

(1. 中北大學(xué) 機(jī)電工程學(xué)院， 山西 太原 030051； 2. 中國(guó)科學(xué)院大學(xué) 寧波材料技術(shù)與工程研究所， 浙江 寧波 315201；3. 山西北方機(jī)械制造有限責(zé)任公司， 山西 太原 030009)

0 引 言

移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題是當(dāng)前移動(dòng)機(jī)器人領(lǐng)域所研究的熱點(diǎn)問(wèn)題[1]， 其主要目標(biāo)是在已知、 未知或者部分未知的環(huán)境中規(guī)劃出從起始點(diǎn)到目標(biāo)點(diǎn)的安全無(wú)碰撞路徑.

針對(duì)已知的靜態(tài)環(huán)境[2]， 所用的全局路徑規(guī)劃算法通常有柵格法[3]、 RRT算法[4]、 A*算法[5]、 Dijkstra算法、 神經(jīng)網(wǎng)絡(luò)算法[6]、 遺傳算法[7]、 蟻群算法[8]等等. 其中， 柵格法因結(jié)構(gòu)簡(jiǎn)單， 計(jì)算量小的特點(diǎn)， 廣泛應(yīng)用于靜態(tài)已知環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題， 并且取得了較好的效果. 但是， 傳統(tǒng)柵格法在構(gòu)建環(huán)境過(guò)程中使用的是正方形柵格， 會(huì)造成總路徑過(guò)長(zhǎng)， 繞行障礙物過(guò)于困難等問(wèn)題， 不少學(xué)者對(duì)此做出了一些改進(jìn)工作， 并取得了一定的成果. 謝昆霖等[9]對(duì)傳統(tǒng)柵格地圖進(jìn)行了分區(qū)， 然后逐個(gè)區(qū)域規(guī)劃路徑， 最后進(jìn)行路徑拼接， 與直接進(jìn)行規(guī)劃的路徑相比， 其規(guī)劃的路徑更具有優(yōu)勢(shì). 分區(qū)是為了更細(xì)致地描述障礙物的信息， 將全局問(wèn)題轉(zhuǎn)化為子區(qū)域問(wèn)題， 但最后的路徑拼接過(guò)程不能保證一次性成功， 在一定程度上減小了路徑規(guī)劃效率. 王陳等[10]根據(jù)帶球球員(移動(dòng)機(jī)器人)以及防守球員(障礙物)的影響力對(duì)球場(chǎng)(傳統(tǒng)柵格地圖)進(jìn)行了區(qū)域劃分， 并為每個(gè)區(qū)域設(shè)置風(fēng)險(xiǎn)值(閾值)， 然后進(jìn)行路徑規(guī)劃， 路徑長(zhǎng)度與安全性比無(wú)分區(qū)的規(guī)劃效果更好. 區(qū)域劃分、 設(shè)置閾值都是為了更好地描述障礙物信息， 但卻沒(méi)有在區(qū)域形狀、 大小及數(shù)量上進(jìn)行分析和闡述， 不能保障所得到的路徑是最優(yōu)解. 曾辰等[11]提出一種蜂巢柵格方法對(duì)環(huán)境建模， 采用蟻群算法對(duì)移動(dòng)機(jī)器人在復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃， 對(duì)比傳統(tǒng)柵格方法得到了較好的路徑. 姚成信等[12]將樹(shù)生長(zhǎng)模擬算法(TGSA)引入蜂巢柵格環(huán)境地圖中， 規(guī)劃路徑的效率相比于傳統(tǒng)柵格地圖更加有優(yōu)勢(shì). 武凌宇[13]通過(guò)對(duì)蜂巢柵格地圖重新進(jìn)行編碼， 提高了的遺傳-蟻群的算法效率. 盡管以上研究都使用蜂巢柵格環(huán)境地圖來(lái)增加路徑規(guī)劃的效率， 但其規(guī)劃僅僅基于正六邊形結(jié)構(gòu)， 并未考慮其它結(jié)構(gòu)， 規(guī)劃出的路徑并不是最優(yōu)的.

本文結(jié)合前人的研究成果， 對(duì)柵格地圖采用不同柵格類型進(jìn)行表示與構(gòu)建等方面進(jìn)行研究， 并采用全局路徑規(guī)劃算法進(jìn)行了驗(yàn)證. 結(jié)果表明， 蜂巢柵格在柵格地圖中的使用會(huì)減少路徑規(guī)劃的迭代次數(shù)， 節(jié)省路徑規(guī)劃的時(shí)長(zhǎng)， 減少路徑的總長(zhǎng)， 可提高路徑規(guī)劃的效率.

1 模型構(gòu)建

1.1 環(huán)境建模

柵格法是最常用的環(huán)境建模方法， 在室內(nèi)和室外的環(huán)境建模中均被廣泛應(yīng)用， 其原理是將整個(gè)地圖的二維環(huán)境空間進(jìn)行細(xì)化， 形成一組網(wǎng)格， 網(wǎng)格包含人為指定的信息， 這些含有信息的網(wǎng)格被稱為環(huán)境單元. 單元格中含有0、 1的二值信息， 1表示該單元格與障礙物相交， 0表示該單元格不與障礙物相交. 用這種方式將整個(gè)環(huán)境進(jìn)行抽象建模， 并采用相應(yīng)的路徑搜索方法在該空間內(nèi)進(jìn)行搜索.

1.2 柵格構(gòu)建

1.2.1 傳統(tǒng)柵格構(gòu)建

通過(guò)激光掃描得到環(huán)境的全局地圖， 在地圖中設(shè)定坐標(biāo)原點(diǎn)o， 并建立坐標(biāo)系xoy， 規(guī)定水平向右為x軸正方向， 豎直向上為y軸正方向. 根據(jù)移動(dòng)機(jī)器人自身的大小規(guī)劃出對(duì)應(yīng)的單位柵格， 設(shè)定坐標(biāo)軸上的單位長(zhǎng)度為單位柵格大小， 細(xì)化后即可形成正方形柵格地圖， 并對(duì)應(yīng)實(shí)際環(huán)境將柵格分為白色柵格和黑色柵格. 如圖 1 所示， 白色柵格為自由柵格， 移動(dòng)機(jī)器人可自由通過(guò)； 黑色柵格為障礙物柵格， 該柵格部分或者全部有障礙物占據(jù)， 移動(dòng)機(jī)器人不可通過(guò).

圖 1 傳統(tǒng)柵格地圖Fig.1 Traditional grid map

1.2.2 菱形柵格構(gòu)建

菱形柵格構(gòu)建與傳統(tǒng)柵格構(gòu)建相同， 都需要通過(guò)激光數(shù)據(jù)獲取到全局的環(huán)境信息， 確定障礙物的相對(duì)位置. 為了構(gòu)建菱形柵格， 以內(nèi)角為60°的菱形為單個(gè)柵格為例， 如圖 2 所示， 將直角坐標(biāo)系“擠壓”為斜60°坐標(biāo)系， 即x軸和y軸分別位于菱形內(nèi)角兩邊， 并按照先前設(shè)定的菱形柵格大小進(jìn)行平鋪， 使其充滿整個(gè)全局地圖. 然后從原點(diǎn)位置開(kāi)始對(duì)實(shí)際環(huán)境中的障礙物進(jìn)行編碼和標(biāo)記， 即可得到柵格地圖中障礙物和自由空間的位置. 最后， 經(jīng)過(guò)擴(kuò)張得到整個(gè)環(huán)境的菱形柵格地圖， 如圖 3 所示.

圖 2 直角坐標(biāo)系“擠壓”過(guò)程Fig.2 Cartesian coordinate system “squeeze” process

圖 3 內(nèi)角60°的菱形柵格地圖Fig.3 Diamond-shaped grid map with an inner angle of 60 °

1.2.3 蜂巢柵格構(gòu)建

正六邊形柵格俗稱蜂巢柵格， 其構(gòu)建方法可分為3步， 如圖 4 所示.

圖 4 “蜂巢柵格”轉(zhuǎn)化過(guò)程Fig.4 “Honeycomb grid” transformation process

第1步， 將傳統(tǒng)柵格中每列逐個(gè)進(jìn)行半個(gè)柵格長(zhǎng)度的偏移； 第2步， 將每個(gè)傳統(tǒng)柵格的兩邊進(jìn)行打斷， 并在中間部分彎曲， 即形成六邊形柵格； 第3步， 將形成的六邊形柵格大小和形狀進(jìn)行調(diào)整， 形成單位長(zhǎng)度的蜂巢柵格， 并對(duì)全局地圖進(jìn)行覆蓋， 形成整個(gè)蜂巢柵格地圖. 同理也可以將傳統(tǒng)柵格中每行進(jìn)行一定的偏移， 得到蜂巢柵格地圖.

通過(guò)以上的行、 列兩種方式偏移， 形成圖 5 所示的兩種蜂巢柵格排布方式， 分別為尖頂排布和平頂排布.

圖 5 蜂巢柵格排布圖Fig.5 Honeycomb grid layout

由于每個(gè)蜂巢柵格都有6個(gè)相鄰的柵格， 即移動(dòng)機(jī)器人在每個(gè)柵格的位置都會(huì)存在6個(gè)預(yù)運(yùn)動(dòng)方向， 為了更好地描述運(yùn)動(dòng)， 采用圖 6 描述柵格位置的坐標(biāo)系. 圖 6 的三系數(shù)坐標(biāo)系雖然在柵格構(gòu)建時(shí)會(huì)提供很大的便利， 卻在對(duì)實(shí)際環(huán)境進(jìn)行描述時(shí)， 造成了較大的困擾. 假如地圖環(huán)境輪廓約為正方形、 長(zhǎng)方形、 圓形等類似圖形， 用此坐標(biāo)系對(duì)其進(jìn)行描述， 存儲(chǔ)空間會(huì)產(chǎn)生極大的浪費(fèi)， 尤其是在x軸與水平線的夾角部分； 假如地圖環(huán)境輪廓約為平行四邊形、 長(zhǎng)橢圓等類似圖形， 用此坐標(biāo)系可更加貼合實(shí)際環(huán)境， 表達(dá)較為合適. 而在實(shí)際仿真環(huán)境下， 基本環(huán)境輪廓為正方形或長(zhǎng)方形， 為了避免該坐標(biāo)系對(duì)地圖環(huán)境空間存儲(chǔ)造成很大的占據(jù)及浪費(fèi)， 為此進(jìn)行了改進(jìn).

圖 6 蜂巢柵格二維三系數(shù)坐標(biāo)系Fig.6 Honeycomb grid two-dimensional three-factor coordinate system

蜂巢柵格地圖的尖頂排布如圖 7 所示， 轉(zhuǎn)換為傳統(tǒng)xoy坐標(biāo)系， 可以為單、 雙行進(jìn)行位置標(biāo)記， 即奇數(shù)行右偏置或偶數(shù)行右偏置.

圖 7 尖頂排布坐標(biāo)標(biāo)記Fig.7 Coordinate markers on pointy top

蜂巢柵格地圖的平頂排布如圖 8 所示， 轉(zhuǎn)換為傳統(tǒng)xoy坐標(biāo)系， 可以為單、 雙列進(jìn)行位置標(biāo)記， 即奇數(shù)列下偏置或偶數(shù)列下偏置.

圖 8 平頂排布坐標(biāo)標(biāo)記Fig.8 Coordinate markers on flat top

以上4種方式在構(gòu)建蜂巢柵格地圖的原理相通， 最終表達(dá)類似， 所以選擇以偶數(shù)列下偏置為例進(jìn)行柵格標(biāo)記的轉(zhuǎn)換討論， 轉(zhuǎn)換結(jié)果如圖 9 所示.

三系數(shù)斜坐標(biāo)系中表示每個(gè)柵格位置為(x,y,z)， 經(jīng)過(guò)式(1)， 每個(gè)柵格的位置在直角坐標(biāo)系中可表示為(x′,y′).

(1)

式中：x′為蜂巢柵格的列數(shù)；y′為蜂巢柵格的行數(shù)； %表示取余.

通過(guò)以上轉(zhuǎn)化， 就能以任意蜂巢柵格的中心為坐標(biāo)原點(diǎn)， 建立出二維xoy直角坐標(biāo)系， 即可便捷地描述出各個(gè)障礙物和自由空間的位置， 并且更適合描述形狀規(guī)則的地圖環(huán)境， 大大節(jié)約了地圖信息的儲(chǔ)存.

圖 9 坐標(biāo)系轉(zhuǎn)換結(jié)果圖Fig.9 Plot of coordinate system transformation

1.2.4 三角形柵格構(gòu)建

針對(duì)三角形柵格地圖， 本文以正三角形柵格為例進(jìn)行構(gòu)建， 可以將正三角形柵格的構(gòu)建看成60°菱形柵格的細(xì)化， 過(guò)程如圖 10 所示.

圖 10 三角形柵格構(gòu)建過(guò)程Fig.10 Triangular grid construction process

首先， 對(duì)傳統(tǒng)的正方形柵格進(jìn)行壓縮， 使其變成60°菱形柵格地圖； 其次， 將每個(gè)60°菱形柵格短對(duì)角線相連， 使1個(gè)菱形劃分為2個(gè)正三角形； 然后用劃分成的正三角形對(duì)環(huán)境進(jìn)行擴(kuò)充， 使其充滿整個(gè)環(huán)境地圖， 并且對(duì)環(huán)境地圖中的障礙物位置信息進(jìn)行描述； 最后即得到正三角形柵格地圖所描述的地圖環(huán)境.

反過(guò)來(lái)看， 正三角形柵格地圖中的每個(gè)頂點(diǎn)都會(huì)連接6個(gè)正三角形， 恰好這6個(gè)三角形拼成了1個(gè)正六邊形， 從而可以認(rèn)為正三角形柵格地圖也是正六邊形柵格地圖的細(xì)化.

由此可知， 這些柵格地圖從構(gòu)建方法上都存在著密切的關(guān)系， 下文將對(duì)以上柵格進(jìn)行分析， 從而找出最適合構(gòu)建柵格地圖的柵格類型.

2 柵格分析

2.1 路徑規(guī)劃策略分析

傳統(tǒng)柵格地圖的柵格形狀為正方形， 大小與移動(dòng)機(jī)器人大小相對(duì)應(yīng)， 一般采樣的規(guī)劃策略為四叉樹(shù)和八叉樹(shù). 四叉樹(shù)策略規(guī)劃的路徑是經(jīng)過(guò)每個(gè)柵格中心點(diǎn)的， 如圖 11 所示； 而八叉樹(shù)策略規(guī)劃的路徑不僅會(huì)經(jīng)過(guò)每個(gè)柵格中心點(diǎn)， 而且會(huì)經(jīng)過(guò)每個(gè)柵格的頂點(diǎn)， 如圖 12 所示. 各種柵格不同策略對(duì)比如表 1 所示.

圖 11 各種柵格在四叉樹(shù)策略下的運(yùn)動(dòng)方向Fig.11 Movement direction of various grids under quadtree strategy

圖 12 各種柵格在八叉樹(shù)策略下的運(yùn)動(dòng)方向Fig.12 Movement direction of various grids under octree strategy

表 1 策略柵格對(duì)比

Tab.1 Strategy grid comparison

柵格類型四叉樹(shù)策略八叉樹(shù)策略運(yùn)動(dòng)方向改變方向的轉(zhuǎn)角/(°)運(yùn)動(dòng)方向改變方向的轉(zhuǎn)角/(°)傳統(tǒng)柵格49084560°菱形柵格460或120830或60蜂巢柵格6601230正三角形柵格3120660

由表 1 可知， 雖然在八叉樹(shù)策略下移動(dòng)機(jī)器人在柵格的運(yùn)動(dòng)方向得到了增加， 改變方向的轉(zhuǎn)角也大大減少， 可以使規(guī)劃的路徑總長(zhǎng)較小， 但由圖 12 可知， 當(dāng)移動(dòng)機(jī)器人在對(duì)角線方向行駛時(shí)， 會(huì)產(chǎn)生對(duì)相鄰兩個(gè)柵格的占據(jù)， 假如相鄰柵格恰好是障礙物， 則很大概率會(huì)與其發(fā)生碰撞， 安全性難以保障. 因此， 這樣規(guī)劃出的路徑會(huì)伴隨很高的危險(xiǎn)性， 使得地圖的保守性較大. 由于在使用柵格地圖路徑規(guī)劃的過(guò)程中， 安全性是第一選擇， 加之八叉樹(shù)策略目前只能通過(guò)柵格的細(xì)化提高安全性能， 大大增加了柵格的計(jì)算數(shù)量和規(guī)劃的運(yùn)行時(shí)間， 所以， 現(xiàn)階段為保證最大安全性， 選擇四叉樹(shù)策略規(guī)劃路徑比較合適.

在四叉樹(shù)策略條件下， 通過(guò)表 1 可知， 蜂巢柵格相對(duì)于其他類型的柵格， 擁有最多的運(yùn)動(dòng)方向和較小的改變方向轉(zhuǎn)角， 使其不僅適用于全向移動(dòng)機(jī)器人的運(yùn)動(dòng)， 而且可增加規(guī)劃路徑的靈活性， 減少規(guī)劃路徑的總長(zhǎng). 路徑轉(zhuǎn)向角越小， 可緩解移動(dòng)機(jī)器人運(yùn)動(dòng)的慣性加速度問(wèn)題， 在一定程度上提高了運(yùn)動(dòng)的準(zhǔn)確性和運(yùn)動(dòng)過(guò)程中的安全性， 為之后的路徑平滑處理提供了很好的基礎(chǔ).

2.2 柵格占據(jù)分析

柵格地圖的每個(gè)單位柵格都是與移動(dòng)機(jī)器人的外輪廓尺寸相對(duì)應(yīng)的. 假定移動(dòng)機(jī)器人是一個(gè)半徑為α的圓， 則對(duì)應(yīng)的不同類型的單位柵格如圖 13 所示， 占據(jù)比公式為

(2)

圖 13 不同類型柵格的柵格占據(jù)比Fig.13 Occupancy ratio of different types of grids

由圖 13 可知， 蜂巢柵格的柵格占據(jù)比最大， 為0.906 9， 正三角形柵格的柵格占據(jù)比最小， 為 0.604 6， 而傳統(tǒng)柵格的柵格占據(jù)比為0.785 4. 相比較之下， 在同樣尺寸大小的地圖中， 蜂巢柵格對(duì)地圖面積的利用率最高， 平鋪柵格數(shù)量最多， 即可更加細(xì)致地描述地圖環(huán)境信息.

2.3 路徑比分析

在柵格地圖路徑規(guī)劃過(guò)程中， 最常見(jiàn)的情況是當(dāng)前運(yùn)動(dòng)方向存在障礙物， 此時(shí)移動(dòng)機(jī)器人會(huì)沿軌跡選擇繞行， 完全繞過(guò)障礙物后繼續(xù)向目標(biāo)點(diǎn)前進(jìn). 為了更有效率地規(guī)劃路徑， 繞障礙物的路徑比成了重要的參考標(biāo)準(zhǔn). 圖 14 為不同類型柵格情況下繞障礙物的路徑圖， 表 2 為各類型柵格路徑比對(duì)比.

圖 14 不同類型柵格繞障圖Fig.14 Different types of grid obstacle maps

表 2 不同類型柵格路徑比

Tab.2 Different types of grid path ratio

路徑參數(shù)正方形柵格60°菱形柵格蜂巢柵格正三角形柵格路徑比(公式)AB+BCACDE+DFDFGH+HIGIJK+KL+LMJM路徑比值1.414 21.154 71.154 71.5

由表 2 可知， 傳統(tǒng)柵格地圖的路徑比為1.414 2， 60°菱形柵格和蜂巢柵格的路徑比都為1.154 7， 正三角形柵格的路徑比為1.5. 路徑比越小， 移動(dòng)機(jī)器人行走路徑的總長(zhǎng)和路徑規(guī)劃運(yùn)行時(shí)間就越少， 所以60°菱形柵格和蜂巢柵格的路徑在越障方面比傳統(tǒng)柵格的路徑更加優(yōu)秀.

3 仿真實(shí)驗(yàn)分析

為了驗(yàn)證蜂巢柵格相對(duì)于傳統(tǒng)柵格在全局路徑規(guī)劃方面的優(yōu)勢(shì)， 本文采用MATLAB軟件進(jìn)行了仿真. 實(shí)驗(yàn)地圖環(huán)境尺寸大小為20 m×20 m， 分別建立在傳統(tǒng)柵格構(gòu)建的二維平面、 蜂巢柵格構(gòu)建的二維平面和普通的障礙物地圖中. 圖 15～圖 20 中， 左下角正方形表示移動(dòng)機(jī)器人的起始位置， 右上角正方形表示移動(dòng)機(jī)器人的目標(biāo)位置， 黑色部分為障礙物(已進(jìn)行膨脹處理).

地圖環(huán)境a(圖15)和地圖環(huán)境b(圖18)分別代表兩種不同類型的環(huán)境， 在傳統(tǒng)柵格下的表示分別為圖 16 和圖 19， 蜂巢柵格下的表示分別為圖 17 和圖 20. 地圖環(huán)境a表示具有一定數(shù)量的較大型障礙物的場(chǎng)景， 與大面積較空曠的室外環(huán)境相類似； 地圖環(huán)境b表示具有多數(shù)量大小障礙物的復(fù)雜場(chǎng)景， 與復(fù)雜的室內(nèi)測(cè)試環(huán)境相類似.

圖 15 地圖aFig.15 Map a

圖 16 地圖環(huán)境a在傳統(tǒng)柵格下的表示Fig.16 Representation of map a in traditional grid

圖 17 地圖環(huán)境a在蜂巢柵格下的表示Fig.17 Representation of map a in honeycomb grid

圖 18 地圖 bFig.18 Map b

圖 19 地圖環(huán)境b在蜂巢柵格下的表示Fig.19 Representation of map b in honeycomb grid

圖 20 地圖環(huán)境b在蜂巢柵格下的表示Fig.20 Representation of Map b in honeycomb grid

本文主要針對(duì)全局路徑規(guī)劃算法A*算法、 Dijkstra算法和BFS算法進(jìn)行研究.

相比于其他兩種算法， A*算法的代價(jià)函數(shù)帶有問(wèn)題自身的啟發(fā)性信息， 因此， A*算法又稱啟發(fā)式搜索算法， 其搜索流程如下.

A*算法在進(jìn)行搜索之前(已知起始點(diǎn))， 首先創(chuàng)建啟發(fā)式函數(shù)

f(n)=g(n)+h(n),

(3)

式中：f(n)為起點(diǎn)到終點(diǎn)的總代價(jià)；g(n)為從起點(diǎn)到某個(gè)中間點(diǎn)的代價(jià)；h(n)為從上述中間點(diǎn)到終點(diǎn)的代價(jià). 其次創(chuàng)建兩個(gè)數(shù)據(jù)表， open表和close表. 其中， open表存放待搜索的節(jié)點(diǎn)， close表存放計(jì)算后代價(jià)最小的節(jié)點(diǎn). A*算法核心是從open表中選擇最優(yōu)的節(jié)點(diǎn)移到close表中， 然后將未探索節(jié)點(diǎn)放入open表中， 重復(fù)操作選取最優(yōu)節(jié)點(diǎn)(f值最小的點(diǎn))， 直到到達(dá)目標(biāo)或者open表為空. 此時(shí)， close表中的節(jié)點(diǎn)可以將起始點(diǎn)串聯(lián)起來(lái)， 這些節(jié)點(diǎn)的排序即為最優(yōu)路徑或次最優(yōu)路徑.

表 3 為以上3種傳統(tǒng)算法的分析對(duì)比.

表 3 傳統(tǒng)全局路徑規(guī)劃算法分析

通過(guò)以上分析， 在僅有單一目標(biāo)點(diǎn)時(shí)， A*算法更適合于柵格地圖的路徑規(guī)劃， 即實(shí)驗(yàn)仿真采用A*算法進(jìn)行柵格地圖的驗(yàn)證. 在地圖a的環(huán)境中， 仿真結(jié)果如圖 21、 圖 22 所示； 在地圖b環(huán)境中， 仿真結(jié)果如圖 23、 圖 24 所示. 仿真結(jié)果的總結(jié)對(duì)比如表 4 所示.

圖 21 地圖環(huán)境a在傳統(tǒng)柵格下的規(guī)劃路徑Fig.21 Map a planned path under traditional grid

圖 22 地體環(huán)境a在蜂巢柵格下的路徑規(guī)劃Fig.22 Map a planned path under honeycomb grid

圖 23 地圖環(huán)境b在傳統(tǒng)柵格下的規(guī)劃路徑Fig.23 Map b planned path under traditional grid

圖 24 地體環(huán)境b在蜂巢柵格下的路徑規(guī)劃Fig.24 Map b planned path under honeycomb grid

表 4 仿真結(jié)果對(duì)比

Tab.4 Comparison of simulation results

地圖環(huán)境規(guī)模/m規(guī)劃路徑長(zhǎng)度/m規(guī)劃時(shí)間/s迭代次數(shù)地圖a蜂巢柵格20×202915.568537傳統(tǒng)柵格20×203411.915600地圖b蜂巢柵格20×202913.276424傳統(tǒng)柵格20×203411.785482

通過(guò)以上仿真分析可以看出， 同樣基于啟發(fā)式的A*算法， 在具有一定數(shù)量較大障礙物的地圖a中， 蜂巢柵格地圖下規(guī)劃的路徑總長(zhǎng)比傳統(tǒng)柵格地圖下規(guī)劃的路徑總長(zhǎng)少14.7%， 消耗時(shí)間增加了30.8%， 迭代次數(shù)減少了10.5%； 在較大障礙物之中具有一定數(shù)量的小障礙物的地圖b中， 蜂巢柵格地圖下規(guī)劃的路徑總長(zhǎng)比傳統(tǒng)柵格地圖下規(guī)劃的路徑總長(zhǎng)少14.7%， 消耗時(shí)間增加了12.6%， 迭代次數(shù)減少了12%. 因此， 在相同環(huán)境和算法的情況下， 蜂巢柵格的使用相對(duì)于傳統(tǒng)柵格會(huì)大大提高路徑規(guī)劃的效率和規(guī)劃路徑總長(zhǎng). 通過(guò)以上實(shí)驗(yàn)可以發(fā)現(xiàn)， 但凡起始點(diǎn)和目標(biāo)點(diǎn)之間客觀存在一條通道， 不管環(huán)境多復(fù)雜， 運(yùn)用蜂巢柵格地圖都可以搜尋到一條安全的路徑.

4 結(jié) 論

為了解決全局路徑規(guī)劃算法在傳統(tǒng)正方形柵格地圖中規(guī)劃效率較低的問(wèn)題， 本文從柵格地圖的構(gòu)建、 信息編碼、 規(guī)劃策略等方面對(duì)不同種類柵格的柵格地圖進(jìn)行了分析對(duì)比， 得出了蜂巢柵格的柵格地圖比傳統(tǒng)正方形柵格的柵格地圖在全局路徑規(guī)劃方面更具有優(yōu)越性. 文中以A*算法、 Dijkstra算法和BFS算法這3種傳統(tǒng)路徑規(guī)劃為示例， 經(jīng)過(guò)對(duì)比分析， 最終以A*算法進(jìn)行最后的實(shí)驗(yàn)仿真. 實(shí)驗(yàn)結(jié)果表明， 蜂巢柵格地圖在地圖信息表示、 路徑規(guī)劃效率、 路徑規(guī)劃總長(zhǎng)和迭代次數(shù)等方面相對(duì)于傳統(tǒng)柵格表現(xiàn)更加優(yōu)秀.