改进栅格地图的煤矿救援机器人路径规划研究

路子佩，姜媛媛,2，李宏伟

(1.安徽理工大学 电气与信息工程学院，安徽 淮南 232001;2.安徽理工大学 环境友好材料与职业健康研究院(芜湖)，安徽 芜湖 241003)

煤矿事故后的救援工作充满了挑战和危险，考虑到救援人员的安全以及救援任务的紧迫性，有必要使用煤矿救援机器人来执行救援任务[1-2].

煤矿救援机器人在进行路径规划过程中，算法选择与地图构建是两个基本问题.按照机器人路径规划过程中对周围环境感知的水平，可以划分为全局和局部路径规划算法.地图的构建方法主要包括三角网格剖分法[3]和栅格法[4].这些路径规划算法和地图构建方法虽然在某一方面有独特优势，但是也存在着一些局限性，因此学者们对此做出了许多改进工作，并得到了一定的成果.王小平等[5]提出了改进的定角度初始路径规划算法，避免了传统参数化求解过程的无解和多解情况.娄安东等[6]提出一种将图搜索与栅格搜索相结合的二叉树路径规划算法，该算法通过逆向搜索优化局部路径，剪枝优化二叉树，从而得到最佳路径.陶哲等[7]提出一种基于A*算法[8]的蜂巢栅格地图方法，该算法在障碍物信息描述方面具有较大优势，规划出的路径长度相比传统栅格法要短.上述研究虽然取得了一些优势，但是还存在着一些不足.

该文结合前人的研究成果，提出一种改进栅格地图的煤矿救援机器人路径规划方法.首先构建障碍物的改进栅格地图模型；其次，采用Dijkstra算法实现在地图模型中的路径规划，验证该地图模型的可行性；在此基础之上，运用A*算法实现在改进栅格地图上的运行，得到最终的优化路径.

1 改进栅格地图建模

现实中物体的表面从直观上看是由许多曲面所构成，这些曲面包括三角形、四边形及多边形等，由于任意的多边形网格实际上也能细分为三角形，且三角形简单而更容易操作，因此本文采用三角网格剖分改进栅格地图.

采用三角剖分将测试地图构建成三角网格地图，该地图可以用单元连接矩阵C及节点矩阵P表示.设三角剖分后的地图中有m个节点和k个单元，则单元连接矩阵可以表示为：

(1)

将第i个节点的坐标表示为Pi(xi,yi,zi)，则节点矩阵可以表示为：

(2)

(3)

(4)

节点连接矩阵T和S的节点为网格节点号.T中的第i个元素ti与S中的第i个si是相关联的，且表示节点ti与节点si连接.由于节点之间的距离不同，因此将相关矩阵T与S之间的距离矩阵定义为D：

(5)

其中:di表示节点关联矩阵T中第i个节点ti与S的第i个节点与节点si的距离.文中引入加权系数，定义

(6)

其中:hi为节点si与节点ti的差;di为节点si与节点ti的距离.由距离矩阵及加权系数，可以定义权重矩阵：

(7)

因此，节点关联矩阵T、S和权重矩阵W可以构成稀疏矩阵表示的赋权无向连通图矩阵：

G=sparse(T,S,W).

(8)

而矩阵中基于三角形网格的映射矩阵map可以表示为节点矩阵和无向连通图矩阵组成的关联矩阵：

map=(P,G).

(9)

2 改进栅格地图路径规划算法

2.1 Dijkstra算法

Dijkstra算法是一种寻找从一个源节点(即起点)到图构造中任何其他节点最短路径的技术.它采用了贪心的思想搜索全局，求取最优解.Dijkstra算法的主要步骤为：

Step1：运行开始，K中只包括初始点，设初始点为v1，即K={v1}，v1的距离为0.U中包含除v1之外的其余顶点，即U={v2,v3,...,vi}.若v1与U中顶点vi是邻接点，则〈vi，v1〉正常有权值，表示能通过，若vi不是v1的邻接点，则〈vi，v1〉的权值为0，表示不能通过；

Step2：从U中选取一个距离v1最小的顶点s，把s加入K中(该选定的距离就是v1到s的最短路径长度)；

Step3：以s为新考虑的中间点，修改U中各顶点的距离；若从源点v1到顶点vi的距离(经过顶点s)比原来距离(不经过顶点s)短，则修改顶点vi的距离值，修改后的经过顶点s的最短距离则为该边的权值；

Step4：重复步骤Step2和Step3直到所有顶点都包含在K中.

2.2 A*算法

A*算法是在Dijkstra算法的基础上加入启发式函数，利用启发信息寻找最优路径.A*算法需要在地图中搜索节点，并设定适合的启发函数进行指导.通过评价各个节点的代价值，获取下一需要拓展的最佳节点，直至到达最终目标点位置.其公式为：

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

(10)

其中，g(n)表示从起始点到当前节点n的最小工作代价，h(n)表示当前节点n到终点的最小估计代价.当h(n)为0时，A*算法也就变成了Dijkstra算法.A*算法优点在于对环境反应迅速，是一种直接的路径搜索算法，因此被广泛应用于路径规划问题.

3 实验与分析

整体实验步骤如下：

Step 1：建立虚拟井下复杂地形的栅格地图及改进栅格地图模型，并对程序进行初始化；

Step 2：在模型中选定搜索路径的起始点和终点，确定路径规划方向；

Step 3：将Dijkstra算法分别运用到栅格地图及改进栅格地图中，对网格中的节点进行搜索，分别计算工作代价，进行比较并得出结论；

Step 4：将A*算法运用到改进栅格地图中，计算工作代价，与原算法进行比较得出结论；

Step 5：得出最终实验结果.

该文采用Matlab R2018b软件进行仿真，工作环境为70×70的二维地图模型，并随机分布障碍物，用“O”号表示.在该环境之上分别建立栅格地图及改进栅格地图模型，如图1所示.

图1 建立地图模型

首先，采用Dijkstra算法分别在栅格地图和改进栅格地图上进行路径规划，结果如图2所示.

图2 Dijkstra算法在两种地图上的路径规划

由图2(a)可知，使用Dijkstra算法虽然能够让机器人在栅格地图上完成从起始点到终点的路径规划，但是它仅仅考虑了如何避开障碍物，而忽略了路径规划过程中搜索的区域及路径的长短问题，因此路径规划的时间较长，规划出的路径存在冗余，导致机器人工作代价很大.由图2(b)可知,将Dijkstra算法运用在改进栅格地图上进行路径规划时，虽然机器人也对全局进行了搜索，但是在行进过程中，综合考虑了三角网格和栅格共同检测出的障碍物信息，使得机器人规划出来的路线相比于栅格地图上规划出的路线减少了很多.

改变机器人路径规划的起点与终点位置，重复进行实验来验证上述结论.随机选取其中的4组实验数据作比较，结果如表1所列，可以看出机器人在改进后的地图模型上规划的路线长度相比栅格地图减少了近四分之一.

表1 两种地图模型上规划路线的长度比较

考虑到Dijkstra算法的完全泛化特点，其计算精度很高，能够避免局部最优陷阱，100%求解最优路径.由于需要对所有节点进行检查，导致计算速度大大降低，因此，为了优化路径规划的时间及长度，进一步验证该改进地图的可行性及正确性，运用A*算法实现在改进栅格地图上的路径规划，实验结果如图3所示.

图3 两种算法路径规划结果

通过图3两种路径规划算法的结果图来看，Dijkstra算法遍历了地形中从起点到终点的所有节点，在不考虑规划时间的情况下得到了一条最优路径.与此相比，A*算法则考虑了工作代价，在得到最优路径的情况下大大缩短了规划时间，说明在综合考虑路径规划时间和工作代价的情况下，A*算法规划出来的路径更加符合实际需要.改变机器人路径规划起点与终点位置，重复进行实验来验证结论，并随机选择4组实验数据进行对比，如表2所列.

表2 两种算法路径规划时间结果比较

最终结果表明，A*算法能有效运用到改进栅格地图中，获得最优路径，充分考虑两点之间路径的可通过性，有效降低了运行时间，提高了对最优路径的搜索能力，验证了改进栅格地图的可行性及正确性.

4 结论

针对Dijkstra算法在栅格地图上的路径规划过程中存在规划路线长、工作代价大等问题，提出一种改进栅格地图的煤矿救援机器人路径规划方法.采用三角网格地图与栅格地图相结合的地图构建方法，综合考虑障碍物信息，实现了对机器人规划路线的优化.针对上述两种地图中出现的遍历时间过长的问题，采用A*算法进一步解决，很大程度上减小了工作代价.实验结果表明改进的栅格地图能有效处理复杂的煤矿井下环境，减少路径规划长度及时间，针对各种算法都具有一定的效果.