張希聞, 肖本賢

(1.合肥工業(yè)大學(xué) 電氣工程與自動(dòng)化學(xué)院,安徽 合肥 230009；2.合肥工業(yè)大學(xué) 裝備與技術(shù)工程學(xué)院，安徽 合肥 230009)

0 引 言

可移動(dòng)機(jī)器人的路徑規(guī)劃在當(dāng)下具有重要的意義。智能算法有D*算法[1]、蟻群算法[2]、F*算法[3]、強(qiáng)化學(xué)習(xí)[4]等，依據(jù)具體問題具體分析的原則，本文采用柵格法[5]對(duì)倉庫進(jìn)行建模，使用改進(jìn)的D*算法對(duì)路徑進(jìn)行規(guī)劃。采用D*算法的主要原因是由于本文的路障存在動(dòng)態(tài)路障，且能綜合算法搜索時(shí)間和路徑長度統(tǒng)籌規(guī)劃，而不是單一的形成最優(yōu)路徑或最快算法。本文提出了一種優(yōu)化路徑的方法，即拓展Moore型元胞鄰居結(jié)構(gòu)[6,7]，使得路徑較原D*算法進(jìn)一步優(yōu)化。在搜索時(shí)間上本文提出一種較為簡捷的辦法，即跳點(diǎn)法，使得搜索過程較原D*算法進(jìn)一步加快。能更符合、更貼切當(dāng)下的快捷物流標(biāo)準(zhǔn)。但本文提供了更快的搜索時(shí)間的同時(shí)，由于加大了路徑建模的空間復(fù)雜度，對(duì)于計(jì)算機(jī)內(nèi)存的占用也成比例提高。使用D*算法進(jìn)行規(guī)劃時(shí)，只有當(dāng)移動(dòng)機(jī)器人遇到障礙時(shí)才會(huì)重新生成可行線路，因此當(dāng)下對(duì)于D*算法的改進(jìn)，主要發(fā)生在路徑長度和運(yùn)算時(shí)間上。就D*算法的路徑長度問題，本文提出了拓展Moore型元胞結(jié)構(gòu)，對(duì)原D*算法的路徑進(jìn)一步縮短,將八點(diǎn)拓展到十六點(diǎn)，進(jìn)行進(jìn)一步的路徑縮短。與此同時(shí)，采用跳點(diǎn)搜索算法對(duì)原D*算法的運(yùn)算速度進(jìn)行一定幅度的提高。算法不僅有更快的速度，同時(shí)具有更高的空間復(fù)雜度。跳點(diǎn)搜索算法可以大量節(jié)約內(nèi)存，有效提高運(yùn)算效率。

1 相關(guān)算法

本文采用拓展Moore型元胞鄰居結(jié)構(gòu)[8]和跳點(diǎn)搜索算法[9]來改進(jìn)D*算法進(jìn)行動(dòng)態(tài)路徑規(guī)劃。

1.1 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)由元胞、元胞空間、鄰居和規(guī)則四個(gè)部分組成?？梢杂靡粋€(gè)四元數(shù)組表示

A=(Ld,S,N,f)

(1)

式中A為元胞自動(dòng)機(jī)模型；d為維度；S為元胞有限離散狀態(tài)，元胞可以是二進(jìn)制形式{0,1}或者是實(shí)數(shù)形式離散集{m1,m2,…mn}；N為一個(gè)領(lǐng)域內(nèi)所有元胞的集合，記為N=(s1,s2,…sn)，其中n為元胞鄰居個(gè)數(shù)，si∈Z，Zi∈{1,2,…,n}；f為演化規(guī)則。

1.2 D*算法

D*算法是可以規(guī)劃動(dòng)態(tài)避障的路徑算法，可以用于多種領(lǐng)域包括航空、游戲、物流等。一般D*算法的路徑搜索包括八種位置分別為：上、下、左、右、左上、左下、右上、右下。引入估價(jià)函數(shù)的概念，對(duì)算法進(jìn)行一種二維的估價(jià)，即

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

(2)

式中h(n)為啟發(fā)函數(shù)，代表這段路徑規(guī)劃的估價(jià)最小值；g(n)為從初始位置到目標(biāo)位置n的實(shí)際代價(jià)。比較常見的啟發(fā)函數(shù),如歐幾里德函數(shù)、曼哈頓函數(shù)等。

1.3 跳點(diǎn)搜索算法

跳點(diǎn)搜索算法基本思想為省略傳統(tǒng)D*算法在搜索過程中對(duì)于一些不必要點(diǎn)的遍歷，如圖1所示，即從a～b點(diǎn)有3種可執(zhí)行路徑，分別為a-m-b，a-n-b，a-l-b。而算法會(huì)在估值過程中對(duì)所得節(jié)點(diǎn)進(jìn)行估價(jià)，即m,n,l,挑出最優(yōu)節(jié)點(diǎn)，即l。但從圖中易知，對(duì)于m和n點(diǎn)的估價(jià)，本身并沒有太大意義路徑a-l-b始終為最優(yōu)解，那么此時(shí)，即可使用跳點(diǎn)搜索算法，對(duì)于m和n節(jié)點(diǎn)直接采取跳點(diǎn)，不予以估價(jià)。跳點(diǎn)搜索算法的根本目的就是對(duì)于D*算法生成的眾多節(jié)點(diǎn)中進(jìn)行有效篩選，有別于傳統(tǒng)意義上的節(jié)點(diǎn)遍歷，省去大量的計(jì)算時(shí)間。其中，這些被省去節(jié)點(diǎn)即為跳點(diǎn),均有效減少了內(nèi)存和算法的計(jì)算量。

圖1 3條路徑

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

2.1 倉庫建模

根據(jù)實(shí)際倉庫中障礙以及動(dòng)態(tài)障礙擺放的位置，使用柵格法對(duì)倉庫進(jìn)行建模[10，11]，將二維的平面分為多個(gè)正方形網(wǎng)格，根據(jù)元胞法，將每一個(gè)網(wǎng)格都定義為一個(gè)元胞。移動(dòng)機(jī)器人工作的環(huán)境由行列柵格構(gòu)成，將倉庫用一個(gè)二維數(shù)組矩陣表示為map(p,q)，即

(3)

倉庫建模實(shí)際參考圖2。

圖2 倉庫

2.2 拓展Moore型鄰居結(jié)構(gòu)

一般,路徑規(guī)劃，移動(dòng)機(jī)器人下一次行動(dòng)選擇有8種，分別為上、下、左、右、左上、左下、右上、右下[12]。而本文采用的元胞邊長為原元胞邊長的2倍，本文元胞鄰胞定義為

{vi=(xi,yi)||xi-x0|+|yi-y0|≤2,xi,yi∈Z}

(4)

式中vi為其鄰胞集合,(x0,y0)為其坐標(biāo)。將圖3中元胞分為2種，元胞周圍的8個(gè)鄰胞為x1,x2,…,xn；外層的16個(gè)元胞為y1,y2,…,yn。有如圖3規(guī)則，當(dāng)x1有障礙物時(shí)，不能移動(dòng)到y(tǒng)1,y2,y16；當(dāng)x2有障礙物時(shí)，不能移動(dòng)到y(tǒng)2,y3,y4。其他以此類推。通過以上的障礙值輸入，進(jìn)一步完善了移動(dòng)機(jī)器人的位移路徑，保證了生成路徑的可行性。

圖3 拓展Moore型鄰居結(jié)構(gòu)

2.3 跳點(diǎn)搜索算法對(duì)于跳點(diǎn)的選擇

情況1節(jié)點(diǎn)周圍不存在障礙物

A1,A2為柵格中的兩個(gè)節(jié)點(diǎn)，Apred表示A1的父節(jié)點(diǎn)，如圖4所示Apred到A2有很多條路徑可行，比如其中Apred-1-2-3-4-A2，然而此法明顯遜于Apred-A1-0-A2，易知，從Apred～A2最短路徑一定經(jīng)過A1，經(jīng)過A1的路徑明顯優(yōu)于不經(jīng)過A1的路徑，因此，此類重復(fù)計(jì)算毫無意義，故使用跳點(diǎn)搜索算法，刪除這些不必要的節(jié)點(diǎn)。篩選條件如下

L({Apred,…,n|A})≤L({Apred,A,n})

(5)

式中L()為該段路徑的長度，n為x的相鄰接點(diǎn)，{Apred,…,n|A}為一個(gè)不經(jīng)過節(jié)點(diǎn)A且分別以Apred和n為起始點(diǎn)和終點(diǎn)的路徑，{Apred,A,n}為經(jīng)過A節(jié)點(diǎn)的分別以Apred和n為起始點(diǎn)和終點(diǎn)的路徑。

圖4 路徑對(duì)比

情況2節(jié)點(diǎn)周圍存在障礙物

這種情況不能繼續(xù)按照上面的情況進(jìn)行參考。本文以向右上的位移為基準(zhǔn)[13]，即如圖5所示，A作為強(qiáng)制鄰節(jié)點(diǎn)生成，篩選條件如下[14]：

1)節(jié)點(diǎn)A的自然鄰節(jié)點(diǎn)不包含n；

2)L({Apred,…,n|A})≥L({Apred,A,n})

圖5 節(jié)點(diǎn)周圍存在障礙

2.4 改進(jìn)D*算法的動(dòng)態(tài)路徑規(guī)劃

找到所有符合上述條件的必要節(jié)點(diǎn)，刪除所有不必要的節(jié)點(diǎn)，從而實(shí)現(xiàn)跳點(diǎn)搜索算法，過程如下：將出發(fā)點(diǎn)A放入Open-list中，優(yōu)先以上方和右方進(jìn)行路線的擴(kuò)展，直到遇到障礙物后，向?qū)蔷€方向擴(kuò)展，當(dāng)沿著對(duì)角線方向擴(kuò)展到新的障礙物時(shí)，再重新回到上方和右方進(jìn)行擴(kuò)展，直到一個(gè)方向出現(xiàn)倉庫的邊緣，另一個(gè)方向出現(xiàn)強(qiáng)制鄰節(jié)點(diǎn)，此時(shí)將強(qiáng)制鄰節(jié)點(diǎn)添加到OpenList中，繼續(xù)向出現(xiàn)強(qiáng)制鄰節(jié)點(diǎn)的方向擴(kuò)展。直到發(fā)現(xiàn)終點(diǎn)位置。此時(shí)跳點(diǎn)搜索算法結(jié)束，繼續(xù)采用拓展Moore型元胞法。定義OpenList2和CloseList2，將可擴(kuò)展的元胞和成為最有路徑的元胞存放其中。并且定義tmpcloseList表存放外圍16個(gè)元胞中不可擴(kuò)展的部分。將目標(biāo)元胞A0放入CloseList中，搜索當(dāng)前8個(gè)鄰居元胞，判定其是否存在障礙，若存在，則判斷其較遠(yuǎn)的16個(gè)元胞是否可擴(kuò)展，把不可擴(kuò)展的元胞放入tmpcloseList中。判定當(dāng)前元胞的24個(gè)鄰居元胞，如果不在OpenList2和tmpcloseList中，則將其放入OpenList2中。然后計(jì)算f值，將其設(shè)為帶擴(kuò)展元胞的父元胞，若帶擴(kuò)展元胞不在OpenList2和tmpcloseList中，則計(jì)算新f值，與舊的f值相比較。且將帶擴(kuò)展元胞的父元胞改為當(dāng)前元胞。遍歷OpenList2中的所有元胞， 找到f值較小的元胞并放入CloseList2中并清空tmpcloseList，直到當(dāng)前元胞為起始元胞，結(jié)束。

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

為了證明本文思路，本文分別進(jìn)行了傳統(tǒng)D*算法的路徑規(guī)劃和本文改進(jìn)后的跳點(diǎn)擴(kuò)展Moore型元胞D*算法進(jìn)行規(guī)劃，對(duì)比了路徑長度、搜索時(shí)間和擴(kuò)展的節(jié)點(diǎn)等。分別在15×15和30×30兩種柵格中的倉庫中進(jìn)行路徑規(guī)劃，使用的計(jì)算機(jī)設(shè)備：Window10操作系統(tǒng)。CPU為i7-7200U，內(nèi)存為4 GB。

圖6為15×15仿真實(shí)驗(yàn)，其中線條左下起始點(diǎn)為路徑起始點(diǎn)，線條右上終止點(diǎn)為路徑終點(diǎn)，黑色方格為靜態(tài)障礙，淺色方格為遍歷的節(jié)點(diǎn)。線為規(guī)劃出的路徑，可以看出，規(guī)劃出的路徑遍歷的節(jié)點(diǎn)數(shù)目明顯減少，并且規(guī)劃出的路徑較原D*算法更為合理。具體為：D*算法遍歷節(jié)點(diǎn)數(shù)為56，路徑長度為22.37，改進(jìn)算法遍歷節(jié)點(diǎn)數(shù)為8，路徑長度為22.73。

圖6 算法對(duì)比

圖7為30×30仿真實(shí)驗(yàn)，其中格子的顏色同上15×15柵格規(guī)定。具體結(jié)果為：D*算法遍歷節(jié)點(diǎn)數(shù)為181，路徑長度為48.62；改進(jìn)算法遍歷節(jié)點(diǎn)數(shù)為12，路徑長度為46.84。

圖7 算法對(duì)比

移動(dòng)機(jī)器人實(shí)驗(yàn)如圖8所示。

圖8 移動(dòng)機(jī)器人

為了驗(yàn)證本文改進(jìn)后的算法產(chǎn)生的結(jié)論，實(shí)驗(yàn)建立在機(jī)器人操作系統(tǒng)ROS上進(jìn)行。移動(dòng)機(jī)器人具有通過相機(jī)采集外界數(shù)據(jù)功能，可以準(zhǔn)確獲取環(huán)境因素和障礙因素。經(jīng)過計(jì)算生成一種具有三個(gè)維度的點(diǎn)云數(shù)據(jù)，然后轉(zhuǎn)換為激光模擬的數(shù)據(jù)，依靠amcl和gmapping模塊建模二維地圖柵格。接下來使用move_base里面的global planner以及l(fā)ocal planner共同協(xié)作完成全局和部分路徑生成。

4 結(jié) 論

綜合實(shí)驗(yàn)、數(shù)據(jù)和大量的理論知識(shí)，本文改進(jìn)后的D*算法，即通過跳點(diǎn)搜索算法減少運(yùn)算時(shí)間和拓展Moore型元胞法減少路徑長度，一定程度上優(yōu)化了原先的D*算法，提高了效率，節(jié)約了內(nèi)存。多種柵格法建模后的倉庫作為實(shí)驗(yàn)對(duì)象，發(fā)現(xiàn)或多或少均有優(yōu)化，無論是路徑上還是運(yùn)算時(shí)間上。較大的倉庫跳點(diǎn)搜索算法運(yùn)算時(shí)間優(yōu)化越明顯，較小的倉庫拓展Moore型元胞法路徑長度優(yōu)化的越明顯。后續(xù)希望在三維空間中對(duì)這一方法進(jìn)行驗(yàn)證，預(yù)計(jì)會(huì)得到和二維類似的結(jié)論。