基于柵格法與改進(jìn)A*算法的掘進(jìn)機(jī)截割軌跡規(guī)劃

沈顯慶， 王 賀， 馬志鵬， 楊 瑩， 張 恒

(黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022)

0 引 言

懸臂式掘進(jìn)機(jī)的主要功能是截割出預(yù)定形狀的巷道以便后續(xù)采煤工作等，在懸臂式掘進(jìn)機(jī)截割軌跡要避開夾矸的前提下，使懸臂式掘進(jìn)機(jī)截割頭走遍所有需要截割的位置，即對(duì)已知平面環(huán)境的全覆蓋軌跡規(guī)劃。張士勇等[1]建立了懸臂式掘進(jìn)機(jī)在截割作業(yè)時(shí)主要工作機(jī)構(gòu)參數(shù)與巷道斷面尺寸之間的數(shù)學(xué)模型，并針對(duì)實(shí)際生產(chǎn)中幾種常見的巷道斷面形狀，對(duì)相應(yīng)的工作機(jī)構(gòu)參數(shù)進(jìn)行了計(jì)算。徐楠等[2]利用Matlab軟件模擬懸臂式掘進(jìn)機(jī)截割頭截割運(yùn)動(dòng)與軌跡仿真，針對(duì)懸臂式掘進(jìn)機(jī)傾斜時(shí)的狀態(tài)，推導(dǎo)出了懸臂式掘進(jìn)機(jī)截割頭的空間位置。季厭浮等[3]提出了根據(jù)不同煤巖分布調(diào)整懸臂式掘進(jìn)機(jī)截割臂擺動(dòng)速度的方法。王蘇彧等[4]采用柵格法對(duì)環(huán)境模型進(jìn)行建模，構(gòu)建了柵格地圖，針對(duì)自動(dòng)截割及自動(dòng)擴(kuò)幫等過(guò)程，分別規(guī)劃了截割軌跡。筆者在將實(shí)際巷道斷面進(jìn)行幾何投影后，通過(guò)二值化實(shí)際巷道斷面圖像，分析其煤巖大致分布規(guī)律，采用柵格法進(jìn)行多種巷道斷面情況建模，將傳統(tǒng)A*算法所規(guī)劃截割軌跡的截割覆蓋率和改進(jìn)A*算法所規(guī)劃截割軌跡的截割覆蓋率進(jìn)行對(duì)比，以驗(yàn)證改進(jìn)A*算法在巷道斷面截割軌跡規(guī)劃方面的優(yōu)勢(shì)。

1 巷道斷面數(shù)字化

1.1 巷道斷面

常見的巷道斷面包括矩形斷面、梯形斷面、拱形斷面等，掘進(jìn)過(guò)程中巷道斷面的形狀對(duì)截割軌跡規(guī)劃并無(wú)影響，因此，文中選取矩形斷面作為掘進(jìn)機(jī)截割對(duì)象進(jìn)行截割軌跡規(guī)劃[5]。

由于在截割過(guò)程中懸臂式掘進(jìn)機(jī)截割臂要通過(guò)圍繞回轉(zhuǎn)臺(tái)進(jìn)行升降或擺動(dòng)實(shí)現(xiàn)斷面截割，實(shí)際截割所形成的斷面為矩形的內(nèi)凹曲面，文中通過(guò)將內(nèi)凹曲面進(jìn)行平面投影處理，使其坐標(biāo)一一對(duì)應(yīng)，如圖1所示。達(dá)到僅需通過(guò)對(duì)矩形平面進(jìn)行截割軌跡規(guī)劃，實(shí)現(xiàn)實(shí)際斷面的軌跡規(guī)劃。

圖1 實(shí)際巷道斷面與投影關(guān)系Fig. 1 Relationship between actual roadway section and projection

1.2 巷道斷面柵格化

文中將柵格地圖劃分為兩種狀態(tài)區(qū)域：白色柵格區(qū)域代表自由狀態(tài)，為截割頭可截割區(qū)域；黑色柵格區(qū)域代表障礙狀態(tài)，為截割頭需避開區(qū)域[6]。為了簡(jiǎn)化建模過(guò)程，以地圖的左下角點(diǎn)為起點(diǎn)，按一定順序?qū)Φ貓D進(jìn)行編號(hào)，如圖2所示。序號(hào)i的坐標(biāo)為

圖2 編號(hào)處理后柵格地圖Fig. 2 Raster map after numbering processing

Xi=((i-1)modM)+1，

Yi=int((i-1)/M)+1，

式中：mod——求余運(yùn)算；

M——行柵格數(shù)；

int——取整運(yùn)算。

將巷道斷面劃分成為20×20的柵格地圖區(qū)域，設(shè)置截割頭進(jìn)入斷面的截割直徑約為100 mm，斷面寬和高設(shè)置成為2 000 mm×2 000 mm，將柵格大小規(guī)定為懸臂式掘進(jìn)機(jī)截割直徑。與此同時(shí)，在巷道斷面的柵格地圖中建立直角坐標(biāo)系，其橫坐標(biāo)代表巷道寬度

式中，ci——柵格寬度。

縱坐標(biāo)代表巷道高度

式中，dj——柵格高度。

1.3 巷道斷面圖像處理

由于掘進(jìn)機(jī)工作環(huán)境復(fù)雜，采集的圖像受巷道亮度和粉塵等影響，圖像會(huì)出現(xiàn)光照不均勻的現(xiàn)象，清晰度較差，影響圖像分析煤巖的屬性[7]。巷道斷面圖像進(jìn)行灰度化處理，處理后巷道斷面圖像如圖3所示。

圖3 灰度化處理后巷道斷面圖像Fig. 3 Image of roadway section after grayscale processing

為了更直觀反映灰度圖像的特征，建立了三維灰度特征圖，如圖4所示。巷道斷面中的煤巖受反射光線的影響，煤和夾矸反射率不同，導(dǎo)致其表現(xiàn)出灰度值不同，因此，圖像灰度特征圖具有呈現(xiàn)出空間三維地形的能力。特征圖中的波峰對(duì)應(yīng)斷面內(nèi)夾矸，波谷對(duì)應(yīng)斷面內(nèi)煤層。

圖4 巷道的三維灰度特征Fig. 4 3D grayscale feature map of roadway

通過(guò)Matlab分析灰度化處理后巷道斷面圖像，獲得該圖像是由M×N=478×475個(gè)像素點(diǎn)組成的，將夾矸和煤層的二值化分割閾值記為T，N0為灰度值小于T的像素點(diǎn)個(gè)數(shù)，N1為灰度值大于T的像素點(diǎn)個(gè)數(shù)，總像素點(diǎn)中夾矸占比為ω0=N0/M×N，煤層占比為ω1=N1/M×N。由于斷面圖像僅由煤層和夾矸兩部分組成，有ω0+ω1=1，夾矸平均灰度記為μ0，煤層平均灰度記為μ1，總平均灰度記為μ，圖像的類間方差記為g。則有

(1)

式中：μ——總平均灰度；

μ0——夾矸平均灰度；

μ1——煤層平均灰度；

g——類間方差。

整理式(1)得

g=ω0ω1(μ0-μ1)2。

經(jīng)Matlab計(jì)算求解，當(dāng)T=47時(shí)，類間方差g取最大值，如圖5所示。因此，T=47為二值化最佳閾值。

圖5 Matlab求解最大閾值Fig. 5 Matlab maximum value solution

確定閾值后通過(guò)Matlab對(duì)巷道圖像進(jìn)行二值化處理，得到二值化巷道斷面圖像，如圖6所示，白色表示夾矸位置，黑色表示煤層位置。

圖6 二值化處理后巷道斷面圖像Fig. 6 Image of tunnel cross section after binarization treatment

1.4 夾矸膨脹化處理

由圖6可見，實(shí)際巷道斷面圖像中夾矸的形狀和分布均是不規(guī)則的，因此，需要采用膨脹的方法確定夾矸覆蓋的柵格，將不規(guī)則夾矸所在的柵格視為地圖障礙點(diǎn)，夾矸覆蓋區(qū)域不滿一個(gè)柵格單元的膨脹成一個(gè)柵格單元，同時(shí)，對(duì)于較小的夾矸，由于截割時(shí)對(duì)截割頭負(fù)載變化影響較小，故不對(duì)其進(jìn)行膨脹化處理。

膨脹化方法特指二值膨脹，其數(shù)學(xué)表達(dá)式為O=U⊕I=[(x,y)[Ixy∩U]≠?]。夾矸膨脹化后的圖像O由柵格單元U對(duì)巷道斷面內(nèi)各原始圖像I進(jìn)行膨脹所得。

文中以圖6二值化處理后巷道斷面圖像為例，建立夾矸膨脹化后的柵格地圖，如圖7所示。

圖7 夾矸膨脹化后的柵格地圖Fig. 7 Expanded raster map of gangue

2 截割軌跡規(guī)劃與算法仿真

典型的巷道斷面成型軌跡可分為：對(duì)于硬度較小的煤巖巷道斷面，懸臂式掘進(jìn)機(jī)截割頭可沿巷道中心鉆入，然后掃幫四周；對(duì)于中硬度的煤巖巷道斷面，懸臂式掘進(jìn)機(jī)截割頭一般從巷道左下角鉆進(jìn)，然后自下向上的類S型截割；對(duì)于硬度大的煤巖巷道斷面，為了避免大塊煤巖脫落，采用從巷道左上角鉆進(jìn)，自上向下的類S型截割。以中硬度的矩形煤巖巷道斷面為例進(jìn)行懸臂式掘進(jìn)機(jī)截割軌跡規(guī)劃。因此，進(jìn)行規(guī)劃懸臂式掘進(jìn)機(jī)截割軌跡時(shí)，截割路徑規(guī)劃示意如圖8所示。

圖8 截割路徑規(guī)劃示意Fig. 8 Cutting path planning schematic

2.1 A*算法

文中通過(guò)計(jì)算懸臂式掘進(jìn)機(jī)截割頭可擴(kuò)展位置與起點(diǎn)位置間的實(shí)際代價(jià)與當(dāng)前截割點(diǎn)到目標(biāo)截割點(diǎn)的估計(jì)代價(jià)之和，將其記為代價(jià)評(píng)估函數(shù)，對(duì)下一步可選擇截割的節(jié)點(diǎn)進(jìn)行對(duì)比篩選，確定下一步所要經(jīng)過(guò)的路徑[8]。

A*算法評(píng)估函數(shù)為

F(n)=G(n)+H(n)，

式中：F(n)——代價(jià)評(píng)估函數(shù)；

G(n)——實(shí)際代價(jià)；

H(n)——估計(jì)代價(jià)。

應(yīng)用A*算法規(guī)劃巷道斷面截割軌跡，通過(guò)對(duì)巷道斷面圖像進(jìn)行柵格法建模，將巷道斷面劃分成為等距離的20行待截割區(qū)域，將各行起點(diǎn)和終點(diǎn)2個(gè)網(wǎng)格點(diǎn)之間依次通過(guò)A*算法求解最短路徑，規(guī)劃好路徑后按照?qǐng)D8的截割路徑規(guī)劃進(jìn)行截割。

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

在傳統(tǒng)A*算法進(jìn)行截割軌跡規(guī)劃方法的基礎(chǔ)上，為了進(jìn)一步地提高巷道斷面截割覆蓋率，通過(guò)將歐幾里德距離度量法應(yīng)用于傳統(tǒng)A*算法評(píng)估函數(shù)中G(n)的計(jì)算過(guò)程，將曼哈頓距離估計(jì)法應(yīng)用于H(n)的計(jì)算過(guò)程[9]。以實(shí)現(xiàn)斷面截割覆蓋率更高的截割軌跡規(guī)劃，達(dá)到更好的斷面截割成型。

二維空間內(nèi)歐幾里德距離為

式中：xe、ye——當(dāng)前截割點(diǎn)e的坐標(biāo)；

xs、ys——目標(biāo)截割點(diǎn)s的坐標(biāo)。

曼哈頓距離為

H(n)=a(|xn-xg|+|yn-yg|)，

式中：N——當(dāng)前截割點(diǎn)的坐標(biāo)，(xn,yn)；

G——目標(biāo)截割點(diǎn)的坐標(biāo)，(xg,yg)；

a——單位長(zhǎng)度代價(jià)。

改進(jìn)A*算法評(píng)估函數(shù)搜索簡(jiǎn)化模型如圖9所示，在計(jì)算前假定，從截割起點(diǎn)向截割終點(diǎn)水平或垂直移動(dòng)一格代價(jià)為10，通過(guò)歐幾里德距離度量公式得到對(duì)角線移動(dòng)一格代價(jià)為14[9]。

圖9 改進(jìn)A*算法評(píng)估函數(shù)搜索示意 Fig. 9 Improved A* algorithm evaluation function search schematic

由圖9可見，G(n)的計(jì)算方法為首先取其父節(jié)點(diǎn)G(n)值，然后判斷當(dāng)前節(jié)點(diǎn)相對(duì)于父節(jié)點(diǎn)的方向，按方向增加代價(jià)值。H(n)的計(jì)算方法為將當(dāng)前節(jié)點(diǎn)至終點(diǎn)所經(jīng)柵格乘相應(yīng)代價(jià)值后進(jìn)行求和，在考慮截割完整性以及截割路徑長(zhǎng)度盡可能短的前提下，僅在需避開夾矸時(shí)進(jìn)行對(duì)角線移動(dòng)，最終通過(guò)依次比較評(píng)估函數(shù)大小進(jìn)行下一步截割路徑的選取。

2.3 仿真對(duì)比驗(yàn)證

通過(guò)觀察圖7實(shí)際巷道斷面中煤巖分布情況，仿照實(shí)際巷道斷面對(duì)柵格中障礙物進(jìn)行隨機(jī)定位，生成3張夾矸位置不同的巷道斷面柵格地圖，圖中五角星為截割起始標(biāo)記點(diǎn)，圓圈為截割結(jié)束標(biāo)記點(diǎn)，紅色線段代表截割頭截割軌跡，綠色柵格代表重復(fù)遍歷路徑[10]。采用傳統(tǒng)A*算法進(jìn)行截割軌跡規(guī)劃，Matlab仿真結(jié)果如圖10所示。

圖10 傳統(tǒng)A*算法截割軌跡規(guī)劃仿真Fig. 10 Simulation of cutting trajectory planning with traditional A* algorithm

針對(duì)3張夾矸位置不同的巷道斷面柵格地圖所實(shí)現(xiàn)的截割覆蓋率依次為98.895%、97.900 3%和97.878%。采用改進(jìn)A*算法在相同巷道斷面柵格地圖內(nèi)進(jìn)行截割軌跡規(guī)劃，Matlab仿真結(jié)果如圖11所示，所實(shí)現(xiàn)的截割覆蓋率依次為99.723 8%、99.737 5%和99.469 5%。

圖11 改進(jìn)A*算法的截割軌跡規(guī)劃仿真Fig. 11 Simulation of cutting trajectory planning based on improved A* algorithm

由圖10和11可以看出，在煤巖分布特征完全相同的巷道斷面環(huán)境下，2種方法能夠生成近似的截割路徑和重復(fù)遍歷路徑，但改進(jìn)A*算法所規(guī)劃截割軌跡對(duì)斷面的截割覆蓋率相較于傳統(tǒng)A*算法有較為顯著的提升。

3 結(jié) 論

(1)利用柵格法與最大類間方差法對(duì)實(shí)際煤巖巷道斷面圖像進(jìn)行處理，將斷面圖像中煤巖分布位置呈現(xiàn)在柵格地圖中，仿照其煤巖分布特征，隨機(jī)夾矸位置構(gòu)建多組巷道斷面柵格地圖。

(2)針對(duì)傳統(tǒng)A*算法所規(guī)劃截割軌跡的截割覆蓋率較低問(wèn)題，提出了改進(jìn)的A*算法，規(guī)劃了截割軌跡，仿真實(shí)驗(yàn)表明，采用改進(jìn)A*算法進(jìn)行截割軌跡規(guī)劃能夠使截割覆蓋率產(chǎn)生顯著的提高，達(dá)到了更好的巷道斷面成型效果。