基于栅格法与改进A*算法的掘进机截割轨迹规划 [PDF全文]
(黑龙江科技大学 电气与控制工程学院, 哈尔滨 150022)
针对传统A*算法在有夹矸巷道断面内所规划截割轨迹覆盖率较低的问题,采用最大类间方差法处理巷道断面图像,根据煤岩分布特征进行栅格法建模,通过改进的A*算法规划截割轨迹,对比改进A*算法与传统A*算法各自实现的断面截割覆盖率。结果表明,改进A*算法所规划的截割轨迹将截割覆盖率提高了1.837 2%,可有效提高掘进机的工作效率和巷道断面截割成型效果。
掘进机; 截割轨迹; OSTU算法; 栅格法建模; 改进A*算法
Cutting trajectory planning of roadheader based on raster method and improved A* algorithm
Shen Xianqing, Wang He, Ma Zhipeng, Yang Ying, Zhang Heng
(School of Electrical & Control Engineering, Heilongjiang University of Science & Technology, Harbin 150022, China)
This paper is intended to address a lower coverage of the cut-off trajectory inherent in traditional A* algorithm in the dirt band roadway section. The study involves applying the maximum inter-class variance method to process the roadway section image; modeling the coal and rock distribution characteristics using the raster method, and planning the cut-off trajectory using improved A* algorithm; and comparing the coverage of the section cut by the improved A* algorithm with that by the traditional A* algorithm. The results show that, the improved A* algorithm could plan the cut-off trajectory featuring a maximum cut-off coverage improvement by 1.837 2%, contributing to effectively improving the efficiency of the roadheader and the effect of cutting the roadway section.
引言

悬臂式掘进机的主要功能是截割出预定形状的巷道以便后续采煤工作等,在悬臂式掘进机截割轨迹要避开夹矸的前提下,使悬臂式掘进机截割头走遍所有需要截割的位置,即对已知平面环境的全覆盖轨迹规划。张士勇等[1]建立了悬臂式掘进机在截割作业时主要工作机构参数与巷道断面尺寸之间的数学模型,并针对实际生产中几种常见的巷道断面形状,对相应的工作机构参数进行了计算。徐楠等[2]利用Matlab软件模拟悬臂式掘进机截割头截割运动与轨迹仿真,针对悬臂式掘进机倾斜时的状态,推导出了悬臂式掘进机截割头的空间位置。季厌浮等[3]提出了根据不同煤岩分布调整悬臂式掘进机截割臂摆动速度的方法。王苏彧等[4]采用栅格法对环境模型进行建模,构建了栅格地图,针对自动截割及自动扩帮等过程,分别规划了截割轨迹。笔者在将实际巷道断面进行几何投影后,通过二值化实际巷道断面图像,分析其煤岩大致分布规律,采用栅格法进行多种巷道断面情况建模,将传统A*算法所规划截割轨迹的截割覆盖率和改进A*算法所规划截割轨迹的截割覆盖率进行对比,以验证改进A*算法在巷道断面截割轨迹规划方面的优势。

1 巷道断面数字化1.1 巷道断面

常见的巷道断面包括矩形断面、梯形断面、拱形断面等,掘进过程中巷道断面的形状对截割轨迹规划并无影响,因此,文中选取矩形断面作为掘进机截割对象进行截割轨迹规划[5]

由于在截割过程中悬臂式掘进机截割臂要通过围绕回转台进行升降或摆动实现断面截割,实际截割所形成的断面为矩形的内凹曲面,文中通过将内凹曲面进行平面投影处理,使其坐标一一对应,如图1所示。达到仅需通过对矩形平面进行截割轨迹规划,实现实际断面的轨迹规划。

图1 实际巷道断面与投影关系<br/>Fig.1 Relationship between actual roadway section and projection

图1 实际巷道断面与投影关系
Fig.1 Relationship between actual roadway section and projection

1.2 巷道断面栅格化

文中将栅格地图划分为两种状态区域:白色栅格区域代表自由状态,为截割头可截割区域; 黑色栅格区域代表障碍状态,为截割头需避开区域[6]。为了简化建模过程,以地图的左下角点为起点,按一定顺序对地图进行编号,如图2所示。序号i的坐标为

Xi=((i-1)mod M)+1,

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

式中:mod——求余运算;

M——行栅格数;

int——取整运算。

图2 编号处理后栅格地图<br/>Fig.2 Raster map after numbering processing

图2 编号处理后栅格地图
Fig.2 Raster map after numbering processing

将巷道断面划分成为20×20的栅格地图区域,设置截割头进入断面的截割直径约为100 mm,断面宽和高设置成为2 000 mm×2 000 mm,将栅格大小规定为悬臂式掘进机截割直径。与此同时,在巷道断面的栅格地图中建立直角坐标系,其横坐标代表巷道宽度

式中,ci——栅格宽度。

纵坐标代表巷道高度

式中,dj——栅格高度。

1.3 巷道断面图像处理

由于掘进机工作环境复杂,采集的图像受巷道亮度和粉尘等影响,图像会出现光照不均匀的现象,清晰度较差,影响图像分析煤岩的属性[7]。巷道断面图像进行灰度化处理,处理后巷道断面图像如图3所示。

为了更直观反映灰度图像的特征,建立了三维灰度特征图,如图4所示。巷道断面中的煤岩受反射光线的影响,煤和夹矸反射率不同,导致其表现出灰度值不同,因此,图像灰度特征图具有呈现出空间三维地形的能力。特征图中的波峰对应断面内夹矸,波谷对应断面内煤层。

图3 灰度化处理后巷道断面图像<br/>Fig.3 Image of roadway section after grayscale processing

图3 灰度化处理后巷道断面图像
Fig.3 Image of roadway section after grayscale processing

图4 巷道的三维灰度特征<br/>Fig.4 3D grayscale feature map of roadway

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

通过Matlab分析灰度化处理后巷道断面图像,获得该图像是由M×N=478×475个像素点组成的,将夹矸和煤层的二值化分割阈值记为T,N0为灰度值小于T的像素点个数,N1为灰度值大于T的像素点个数,总像素点中夹矸占比为ω0=N0/M×N,煤层占比为ω1=N1/M×N。由于断面图像仅由煤层和夹矸两部分组成,有ω01=1,夹矸平均灰度记为μ0,煤层平均灰度记为μ1,总平均灰度记为μ,图像的类间方差记为g。则有

式中:μ——总平均灰度;

μ0——夹矸平均灰度;

μ1——煤层平均灰度;

g——类间方差。

整理式(1)得

g=ω0ω101)2

经Matlab计算求解,当T=47时,类间方差g取最大值,如图5所示。因此,T=47为二值化最佳阈值。

图5 Matlab求解最大阈值<br/>Fig.5 Matlab maximum value solution

图5 Matlab求解最大阈值
Fig.5 Matlab maximum value solution

确定阈值后通过Matlab对巷道图像进行二值化处理,得到二值化巷道断面图像,如图6所示,白色表示夹矸位置,黑色表示煤层位置。

图6 二值化处理后巷道断面图像<br/>Fig.6 Image of tunnel cross section after binarization treatment

图6 二值化处理后巷道断面图像
Fig.6 Image of tunnel cross section after binarization treatment

1.4 夹矸膨胀化处理

图6可见,实际巷道断面图像中夹矸的形状和分布均是不规则的,因此,需要采用膨胀的方法确定夹矸覆盖的栅格,将不规则夹矸所在的栅格视为地图障碍点,夹矸覆盖区域不满一个栅格单元的膨胀成一个栅格单元,同时,对于较小的夹矸,由于截割时对截割头负载变化影响较小,故不对其进行膨胀化处理。

膨胀化方法特指二值膨胀,其数学表达式为。夹矸膨胀化后的图像O由栅格单元U对巷道断面内各原始图像I进行膨胀所得。

文中以图6二值化处理后巷道断面图像为例,建立夹矸膨胀化后的栅格地图,如图7所示。

图7 夹矸膨胀化后的栅格地图<br/>Fig.7 Expanded raster map of gangue

图7 夹矸膨胀化后的栅格地图
Fig.7 Expanded raster map of gangue

2 截割轨迹规划与算法仿真

典型的巷道断面成型轨迹可分为:对于硬度较小的煤岩巷道断面,悬臂式掘进机截割头可沿巷道中心钻入,然后扫帮四周; 对于中硬度的煤岩巷道断面,悬臂式掘进机截割头一般从巷道左下角钻进,然后自下向上的类S型截割; 对于硬度大的煤岩巷道断面,为了避免大块煤岩脱落,采用从巷道左上角钻进,自上向下的类S型截割。以中硬度的矩形煤岩巷道断面为例进行悬臂式掘进机截割轨迹规划。因此,进行规划悬臂式掘进机截割轨迹时,截割路径规划示意如图8所示。

图8 截割路径规划示意<br/>Fig.8 Cutting path planning schematic

图8 截割路径规划示意
Fig.8 Cutting path planning schematic

2.1 A*算法

文中通过计算悬臂式掘进机截割头可扩展位置与起点位置间的实际代价与当前截割点到目标截割点的估计代价之和,将其记为代价评估函数,对下一步可选择截割的节点进行对比筛选,确定下一步所要经过的路径[8]

A*算法评估函数为

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

式中:F(n)——代价评估函数;

G(n)——实际代价;

H(n)——估计代价。

应用A*算法规划巷道断面截割轨迹,通过对巷道断面图像进行栅格法建模,将巷道断面划分成为等距离的20行待截割区域,将各行起点和终点2个网格点之间依次通过A*算法求解最短路径,规划好路径后按照图8的截割路径规划进行截割。

2.2 改进A*算法

在传统A*算法进行截割轨迹规划方法的基础上,为了进一步地提高巷道断面截割覆盖率,通过将欧几里德距离度量法应用于传统A*算法评估函数中G(n)的计算过程,将曼哈顿距离估计法应用于H(n)的计算过程[9]。以实现断面截割覆盖率更高的截割轨迹规划,达到更好的断面截割成型。

二维空间内欧几里德距离为

式中:xe、ye——当前截割点e的坐标;

xs、ys——目标截割点s的坐标。

曼哈顿距离为

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

式中:N——当前截割点的坐标,(xn,yn);

G——目标截割点的坐标,(xg,yg);

a——单位长度代价。

改进A*算法评估函数搜索简化模型如图9所示,在计算前假定,从截割起点向截割终点水平或垂直移动一格代价为10,通过欧几里德距离度量公式得到对角线移动一格代价为14[9]

图9 改进A*算法评估函数搜索示意<br/>Fig.9 Improved A* algorithm evaluation function search schematic

图9 改进A*算法评估函数搜索示意
Fig.9 Improved A* algorithm evaluation function search schematic

图9可见,G(n)的计算方法为首先取其父节点G(n)值,然后判断当前节点相对于父节点的方向,按方向增加代价值。H(n)的计算方法为将当前节点至终点所经栅格乘相应代价值后进行求和,在考虑截割完整性以及截割路径长度尽可能短的前提下,仅在需避开夹矸时进行对角线移动,最终通过依次比较评估函数大小进行下一步截割路径的选取。

2.3 仿真对比验证

通过观察图7实际巷道断面中煤岩分布情况,仿照实际巷道断面对栅格中障碍物进行随机定位,生成3张夹矸位置不同的巷道断面栅格地图,图中五角星为截割起始标记点,圆圈为截割结束标记点,红色线段代表截割头截割轨迹,绿色栅格代表重复遍历路径[10]。采用传统A*算法进行截割轨迹规划,Matlab仿真结果如图 10所示。

图 10 传统A*算法截割轨迹规划仿真<br/>Fig.10 Simulation of cutting trajectory planning with traditional A* algorithm

图 10 传统A*算法截割轨迹规划仿真
Fig.10 Simulation of cutting trajectory planning with traditional A* algorithm

针对3张夹矸位置不同的巷道断面栅格地图所实现的截割覆盖率依次为98.895%、97.900 3%和97.878%。采用改进A*算法在相同巷道断面栅格地图内进行截割轨迹规划,Matlab仿真结果如图 11所示,所实现的截割覆盖率依次为99.723 8%、99.737 5%和99.469 5%。

图 11 改进A*算法的截割轨迹规划仿真<br/>Fig.11 Simulation of cutting trajectory planning based on improved A* algorithm

图 11 改进A*算法的截割轨迹规划仿真
Fig.11 Simulation of cutting trajectory planning based on improved A* algorithm

图 10和11可以看出,在煤岩分布特征完全相同的巷道断面环境下,2种方法能够生成近似的截割路径和重复遍历路径,但改进A*算法所规划截割轨迹对断面的截割覆盖率相较于传统A*算法有较为显著的提升。

3 结 论

(1)利用栅格法与最大类间方差法对实际煤岩巷道断面图像进行处理,将断面图像中煤岩分布位置呈现在栅格地图中,仿照其煤岩分布特征,随机夹矸位置构建多组巷道断面栅格地图。

(2)针对传统A*算法所规划截割轨迹的截割覆盖率较低问题,提出了改进的A*算法,规划了截割轨迹,仿真实验表明,采用改进A*算法进行截割轨迹规划能够使截割覆盖率产生显著的提高,达到了更好的巷道断面成型效果。

参考文献