差分进化算法在煤矿井下移动设备路径规划的应用研究

韩国国，范柄尧

（1.山西天地王坡煤业有限公司，山西 晋城 043300；2.中国煤炭科工集团太原研究院，陕西 太原 030006）

1 前言

近年来，各大煤矿对井下安全生产的要求越来越高，设备自动化、智能化替代人力已成为重要的解决办法。井下移动设备移动频繁，一直以来都是安全生产的隐患，为保证移动设备的安全运行，确保人员及设备的安全，需要对可移动设备的运动规划问题进行探讨和研究。

移动设备包括综采设备，连采设备和辅助运输车辆和井下移动机器人，其中各大学者针对辅助运输车辆和自主移动机器人在煤矿井下这一复杂环境下的运动规划问题研究的较多，文献[4]采用人工鱼群算法对井下救援机器人进行路径规划，通过将环境模型中威胁区域距离检测的与算法相结合，实现了在较短的时间内得到目前环境下的最优路径。但是路径点数量的选择对算法效果的影响较大；文献[5]通过改进人工势场法对矿井中障碍物密集且移动较多的导航装置进行路径避障处理；文献[6]通过局部到全局的梯度-坐标轮换法进行煤矿搜救机器人最优路径规划。另外，还有采用各类传感器、视频辅助等方法进行辅助运输和避障处理，均取得了不错的效果。本文主要采用差分进化算法针对辅助运输车辆在煤矿井下这一复杂环境下的运动规划问题进行探索。

差分进化(Differential Evolution，DE)算法是由Storn和Price提出的一种基于种群的智能优化算法，该算法能够用来解决连续领域的优化问题。优点是在全局、并行搜索过程中具有鲁棒性强，操作原理简单以及寻优性能良好等，现在已经成为进化领域的研究热点。

鉴于差分进化算法在连续域的突出表现，本文将其用于解决煤矿井下可移动设备的无碰撞最短路径规划问题。

2 煤矿井下移动设备路径规划问题模型

针对煤矿井下可移动设备路径规划问题，设计使可移动设备从起始点到目标点的路径模型。本文将可移动设备缩小为一个质点，将各个障碍物设置成不同半径的圆，煤矿井下可移动设备运行的最短无碰撞路径模型如下：

式中，f表示可移动设备运行的最短无碰撞路径；设起始位置坐标为目标坐标为x2，…xn为将x0和xn+1关于x轴n+1等分后的n个点，b为x0和xn+1的n+1等分值。y1，y2，…yn为x1，x2，…

xn所对应的路径点；考虑到相邻两路径点连线可能与障碍物相交而形成不可行路径，使用惩罚函数ωi处理这种情况。ε＞1为惩罚因子，可以使不可行路径变长；表示障碍物k的圆心到相邻两路径点yi yi-1所在直线的垂直距离；表示第k个障碍物的影响范围，Rk为第k个障碍物的半径，为一个较小的数；Sk表示线段yi yi-1是否与第k个障碍物相交，相交Sk=0，否则Sk=1。

3 基于差分进化算法的路径规划

3.1 种群初始化

差分进化算法的初始化种群设置如下为：

式中，NP为种群规模，D为维数。

3.2 变异操作

DE算法有很多变异策略，本文采用的变异方式为DE/rand/1，此变异操作具体是指在每一代种群中选择三个互异的个体yr1,g、yr2,g和yr3,g，把其中两个个体yr2,g和yr3,g进行差分处理并经过缩放因子F( 1 0＜F＜ )缩放后，与第三个个体yr1,g相加得到变异向量vi,g，如式(6)所示。

3.3 交叉操作

本文采用二项式交叉方式进行操作，试验向量中至少有一个分量由变异向量产生。具体操作如式（7）所示：

式中，j=1,2,…,D, CR∈(0,1)为交叉率，jrand为[1,D]内随机选择的整数。

3.4 选择操作

为产生下一代的目标向量yi,g+1，根据目标向量yi,g和试验向量ui,g的适应值f()⋅来选择最优个体，具体步骤如式(8)所示：

4 实验仿真

4.1 环境参数设置

针对煤矿井下可移动设备无碰撞最短路径规划问题，本文将差分进化算法(DE/rand/1/bin)进行仿真实验，为了保证试验的公平性，针对算法的参数进行如下设置：

移动设备的环境条件设置如下：将移动设备在以下两个环境中进行仿真试验，其中环境1中有两个障碍物，障碍物的情况如下：半径都为1，坐标原点分别为(-15，-10)、（15，10）的圆；环境2中有三个障碍物，障碍物的情况如下：半径为1，坐标原点分别为（20，5)、(-20，-5)和(0，0)的圆。

参数设置：针对差分进化算法，种群规模NP=15D，终止条件为，CR与F设置如下：CR=0.8，Fmin=0.1，Fmax=0.8。

通过差分进化算法完成移动设备的路径规划时，算法的每一次循环矩阵的维数D和可移动设备路径点的数量有密切关系，本文使用不包括开始点和目标点的路径点n来表示数量(D=n)，由此得到本文的路径点数量n和路径点间隔d有关，关系式如下：

式中，x0为出发点横坐标，xn+1为目标点横坐标。

4.2 实例分析

图1为DE的最优路径，针对环境1和2，算法都能找到从开始点到目标点的最短路径。如图1(a)、(b)所示，特别是针对环境2这种障碍物较多的情形，DE算法也能够找到最短路径。

图1 最优路径图

差分进化算法能够针对不同环境和路径点间隔得到到高质量的解，是一种有效的路径规划方法。

5 结语

本文提出将差分进化算法用于解决煤矿井下可移动设备在复杂环境下的无碰撞最短路径规划问题。实验结果显示，差分进化算法可以获得高质量的解，有效解决煤矿井下可移动设备在复杂环境下的路径寻优问题。