0 引言

为提高矿井事故的救援效率，减少煤矿灾难造成的人员伤亡，可使用煤矿搜救机器人代替救险人员，完成环境探测、搜索和救援任务[1]。但矿井灾后环境复杂，煤矿搜救机器人需要在地形复杂、黑暗、通信不畅且需要防爆的环境中开展工作[2]，要顺利实现救援，首先必须能够抵达灾难现场。目前,国内外学者所研制的煤矿搜救机器人都具备一定的越障能力，但是对于危险区域和大障碍区域，机器人依靠自身条件无法跨越，只能选择避开这些区域。因此，煤矿搜救机器人移动路径的可行性、最优化及安全性对救援效率有着至关重要的影响[3-5]。

近年来，大量学者针对煤矿搜救机器人路径规划算法进行了研究，如对瓦斯分布区域避障的Dijkstra算法[6]、粒子群并行优化算法[7-8]、人工鱼群算法[9]、Q-learning算法[10]、分级扩展式快速扩展随机树法[11]、人工势场法[12]、遗传算法[13]等。这些机器人路径规划算法基本解决了在避开障碍的前提下，从起始点到目标点的可行性路径规划问题。但对于机器人移动路径最优问题，部分学者仅以机器人局部运动路径最优为目标进行算法改进，而忽略了全局路径最优问题[14-15]。

在煤矿搜救机器人路径规划中，要求机器人在不碰撞障碍物的前提下规划出从出发点到目标点的可行路径，使周围环境对搜救机器人正常工作的影响降到最小；同时所规划的路径要达到全局路径最优的目标，提高搜救机器人的运动效率。本文结合优化设计方法中的梯度法和坐标轮换法，提出了基于梯度-坐标轮换法的煤矿搜救机器人最优路径规划算法，在避开障碍区间的前提下，实现了从出发点到目标点的最优路径规划，从而提高了机器人运动路径的合理性和高效性。

1 最优路径规划算法理论基础

1.1 梯度法

梯度方向是函数变化率最大的方向，在求目标函数极大值和极小值时，函数的梯度方向和负梯度方向是最快接近目标函数极大值和极小值的搜索方向。

假设在k-1次迭代中，已取得x(k)点，目标函数在这一点的梯度为

(1)

第k次迭代的搜索方向s(k)取负梯度的单位向量，即

(2)

式中为梯度向量的模。

第k次迭代的新点x(k+1)为

x(k+1)=x(k)+α(k)s(k)

(3)

式中α(k)为迭代的最优步长。

如此继续迭代，直至达到收敛准则取得f(x)的最优点x*。

由于梯度法每次迭代的搜索方向都是取函数的最速下降方向，所以又称为最速下降算法。这种算法迭代过程简单，要求的存储量小，而且在远离极小点时，函数值下降比较快。

1.2 坐标轮换法

坐标轮换法又称降维法，是一种不用求目标函数导数的最优化设计方法。以f(x1,x2)为目标函数，从点出发，先固定不变，改变x1，使目标函数下降到最小值，即求得然后固定不变，改变x2，使其目标函数降至最小值，即求得至此完成一轮计算。然后再开始第2轮，重复前面的过程求得点。如此继续下去，直至目标函数收敛到最优点为止。

2 最优路径规划算法设计

2.1 梯度-坐标轮换法

梯度-坐标轮换法流程如图1所示。

图1 梯度-坐标轮换法流程
Fig.1 Flow of gradient-coordinate rotation method

首先在二维坐标系中确定机器人运动的起点坐标A(x1,y1)和目标点坐标B(x2,y2)。由于机器人的运动环境中存在障碍区域，导致机器人的运动路径具有不确定性，无法建立机器人最优运动路径的目标函数，所以，不能通过对目标函数进行数学转换处理的方式直接计算出从A点运动到B点的梯度方向。由于两点之间直线距离最短，在不考虑机器人运动环境中存在障碍区域的情况下，搜救机器人沿负梯度方向运动所经过的路程最短。A点到B点的负梯度方向为

s=[(x2-x1),(y2-y1)]

(4)

由于机器人在运动之前无法确定运动到何处会与障碍物碰撞，所以，先按照梯度法的算法准则，沿A点到B点的负梯度方向以步长α运动。机器人步长的确定：令Δx=x2-x1，Δy=y2-y1，如果Δx≥Δy，则x轴方向步长|x|=Δx/Δy,y轴方向步长|y|=1；否则|y|=Δy/Δx,|x|=1。机器人的运动方向和运动步长分别为

s=x+y

(5)

(6)

机器人避障运动路径如图2所示。当机器人沿梯度方向运动，下一步将会与障碍区间发生碰撞时(图2中C点)，借助坐标轮换法的思想，让机器人沿着某一个方向进行避障运动。

图2 机器人避障运动路径
Fig.2 Robot obstacle avoidance path

在进行坐标轮换时，机器人有4个可供选择的运动方向，即x轴正方向、y轴正方向、x轴负方向和y轴负方向。机器人能否在这4个运动方向中选择一个最佳的运动方向，对机器人能否准确避开障碍及避障效率起着至关重要的影响。因此，为了使机器人在遇到障碍时能够准确地选取避障方向，提高避障效率，对机器人可选择的4个方向确立优先级。

首先确定机器人遇到的障碍点位置与目标点x，y轴方向的距离，即Δx和Δy，然后用以下方法确定优先级：① 当Δx≥Δy时，x轴负梯度方向>y轴负梯度方向>y轴梯度方向>x轴梯度方向；② 当Δx<Δy时，y轴负梯度方向>x轴负梯度方向>x轴梯度方向>y轴梯度方向。即当机器人在x和y轴负梯度方向均满足运动条件时，优先向着距离目标点最远的坐标轴负梯度方向运动，其次选择另外一个坐标轴的负梯度方向，这样能够尽可能缩短在避开障碍后机器人距离目标点的直线距离。

假设机器人沿y轴正方向运动，则其运动方向可表示为s1=y，其运动步长为机器人每运动一步到达新的位置时，都要对下一步在梯度方向上运动的可行性进行判断，若不会与障碍区间发生碰撞，则以机器人所处位置为起始点重新初始化梯度方向。

2.2 路径优化

由坐标轮换法所确定的路径比由梯度法所确定的路径效率低，而在路径规划过程中，采用坐标轮换法的直接原因是机器人路径中存在障碍区间。若机器人直接选择与障碍区间无交点的路径，即从梯度法运动路径的开始点以梯度法运动到下一个坐标轮换法运动路径的结束点，则可直接避开障碍区，提高运动效率。局部路径优化如图3所示，梯度法的开始点为A点，坐标轮换法的结束点为D点，若机器人直接按照梯度法从A点沿直线运动到D点，则最短路程为

f(x,y)=|AD|+|DB|

(7)

图3 局部路径优化
Fig.3 Local path optimization

机器人所规划的最短路径AD段并没有实际走过，无法确知AD段是否有其他障碍区间。因此，需要对所确定的路径进行验证，判断是否存在障碍区间。如果不存在，则可确定该路径可行；如果存在，则要对存在障碍的路段进行局部路径规划。

对AD段进行局部路径最优规划时，起点坐标为A点，目标点为D点，按照从A点到B点同样的方法进行路径规划。机器人从A点开始，先以梯度法向目标点D运动；当遇到障碍区间时，转换为坐标轮换法；完全避开障碍区域后，再转换为梯度法，直至运动到满足终止运算条件时结束运算。对已有路径进行优化时，新的路径均需要进行验证，直至所规划的路径符合到达目标点的终止条件且不存在任何障碍区间。算法的终止条件是机器人与目标点的最短距离小于机器人的最小步长。

3 仿真分析

在二维运动空间中对最优路径规划算法进行仿真验证，结果如图4所示。在图4(a)中，机器人从起始坐标点A(0,0)向目标点B(100,100)运动，机器人首先按照梯度法沿AB连线的负梯度方向向B点运动，在运动过程中首先受到障碍区间10的阻碍，转用坐标轮换法进行避障运动。在坐标轮换法的4个可行方向中，机器人根据方向选择优先级选择沿y轴负梯度方向运动；运动到C点后，机器人完全避开障碍区间10，再转用梯度法以CB两点连线的负梯度方向向着目标点B运动。

(a) 示例1

(b) 示例2

(c) 示例3

(d) 示例4

图4 最优路径规划算法仿真
Fig.4 Simulation of optimal path planning algorithm

当机器人受到障碍区间8的阻碍时，转用坐标轮换法，根据方向选择优先级选择避障运动方向，运动到D点后完全避开障碍区间8，结束坐标轮换法，转用梯度法。

机器人依照无障碍时使用运动效率最高的梯度法、遇到障碍时选择坐标轮换法的原则向目标点B点运动。依照此次运动轨迹中的梯度法运动路径开始点和坐标轮换法运动路径结束点确定一条最短路径，然后判断所确定的局部最优路径中是否存在障碍区间，若不存在则输出所规划的最优可行路径，若存在则对该路段进行局部最优路径规划，并对所规划的局部最优路径进行可行性判断，直到路径中不存在障碍区间为止。规划的机器人运动全局最优路径为A—C—D—E—F—B。

图4(a)中机器人目标点B的方位在x、y轴的正方向上。在图4(b)、图4(c)和图4(d)中，机器人从不同的起始坐标点A向着方位处于x轴负方向或y轴负方向的目标点B运动，以验证坐标轮换法中方向优先级选择的合理性和所设计路径规划算法的可靠性。通过多次仿真可知，经过多次避障运动和局部路径优化后，机器人能够在避开障碍区域的基础上准确地找到从出发点到目标点的全局最优路径。

4 结论

(1) 提出了基于梯度-坐标轮换法的煤矿搜救机器人最优路径规划算法。首先对障碍区间的形状和位置进行参数化处理，其次对梯度法和坐标轮换法的执行条件、转换条件及循环条件，坐标轮换法中方向优先级的确立，以及整个算法循环的终止条件进行定义和处理。

(2) 通过对所规划机器人路径的多次局部最优化处理，实现了机器人全局最优路径规划。仿真结果表明，机器人能够在多障碍区间内准确规避障碍区间的同时选择最优路径。

参考文献(References)：

[1] 柳玉龙.煤矿搜救机器人的研究现状及关键技术分析[J].矿山机械,2013,41(3):7-12.

LIU Yulong.Analysis on current research status and key technologies of mine search and rescue robots[J].Mining & Processing Equipment,2013,41(3):7-12.

[2] 李雨潭,李猛钢,朱华.煤矿搜救机器人履带式行走机构性能评价体系[J].工程科学学报,2017,39(12):1913-1921.

LI Yutan,LI Menggang,ZHU Hua.Performance evaluation system of the tracked walking mechanism of a coal mine rescue robot[J].Chinese Journal of Engineering,2017,39(12):1913-1921.

[3] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.

ZHU Daqi,YAN Mingzhong.Survey on technology of mobile robot path planning[J].Control and Decision,2010,25(7):961-967.

[4] 张广林,胡小梅,柴剑飞,等.路径规划算法及其应用综述[J].现代机械,2011(5):85-90.

ZHANG Guanglin,HU Xiaomei,CHAI Jianfei,et al.Summary of path planning algorithm and its application[J].Modern Machinery,2011(5):85-90.

[5] 张国亮.动态环境中移动机器人路径规划研究综述[J].机床与液压,2013,41(1):157-162.

ZHANG Guoliang.Survey on path planning for mobile robot under dynamic environment[J].Machine Tool & Hydraulics,2013,41(1):157-162.

[6] 马西良,朱华.对瓦斯分布区域避障的煤矿机器人路径规划方法[J].煤炭工程,2016,48(7):107-110.

MA Xiliang,ZHU Hua.Path planning method for obstacle-avoiding of coal mine robot in gas hazard area[J].Coal Engineering,2016,48(7):107-110.

[7] 赵少林,程杰.基于粒子群并行优化的煤矿井下机器人路径规划[J].计算机测量与控制,2014,22(5):1600-1602.

ZHAO Shaolin,CHENG Jie.Coal mine underground robot path planning based on parallel particle swarm optimization[J].Computer Measurement & Control,2014,22(5):1600-1602.

[8] 梁昔明,李德生.嵌入共轭梯度法的混合粒子群优化算法[J].小型微型计算机系统,2014,35(4):835-839.

LIANG Ximing,LI Desheng.Hybrid PSO algorithm with conjugate gradient methods[J].Journal of Chinese Computer Systems,2014,35(4):835-839.

[9] 姚正华,任子晖,陈艳娜.基于人工鱼群算法的煤矿救援机器人路径规划[J].煤矿机械,2014,35(4):59-61.

YAO Zhenghua,REN Zihui,CHEN Yanna.Path planning for mine rescue robot based on AFSA[J].Coal Mine Machinery,2014,35(4):59-61.

[10] 任艳斐,张军锋.煤矿井下移动机器人路径规划的算法优化[J].煤炭技术,2013,32(7):80-82.

REN Yanfei,ZHANG Junfeng.Algorithm optimization of coal mine underground mobile robot path planning[J].Coal Technology,2013,32(7):80-82.

[11] 侯媛彬,郝利波.煤矿救援机器人自主避障方法研究[J].煤炭科学技术,2011,39(10):90-92.

HOU Yuanbin,HAO Libo.Study on automatic avoiding obstacle method of mine rescue robot based on CERRT algorithm[J].Coal Science and Technology,2011,39(10):90-92.

[12] 田子建,高学浩.基于改进人工势场法的救灾机器人路径规划[J].工矿自动化,2016,42(9):37-42.

TIAN Zijian,GAO Xuehao.Path planning of rescuing robot based on improved artificial potential field method[J].Industry and Mine Automation,2016,42(9):37-42.

[13] 王雄.一种煤矿井下救灾机器人路径规划方法[J].信息技术,2014(4):69-71.

WANG Xiong.A method of path planning of coal mine rescue robot[J].Information Technology,2014(4):69-71.

[14] 杨俊成,李淑霞,蔡增玉.路径规划算法的研究与发展[J].控制工程,2017,24(7):1473-1480.

YANG Juncheng,LI Shuxia,CAI Zengyu.Research and development of path planning algorithm[J].Control Engineering of China,2017,24(7):1473-1480.

[15] 杜映峰,陈万米,范彬彬.群智能算法在路径规划中的研究及应用[J].电子测量技术,2016,39(11):65-70.

DU Yingfeng,CHEN Wanmi,FAN Binbin.Research and application of swarm intelligence algorithm in path planning[J].Electronic Measurement Technology,2016,39(11):65-70.