图1 三维空间模型
实验研究
李晓静1,2， 余东满1,2
(1.河南工业职业技术学院 机械工程学院， 河南 南阳 473009；2.柔性制造河南省工程实验室， 河南 南阳 473009)
摘要：为了解决三维环境中的煤炭勘探及救援机器人路径规划问题，提出了一种基于改进蚁群算法的煤炭勘探及救援机器人最优路径规划方法。利用栅格法创建了三维空间环境模型，建立了煤炭勘探及救援机器人的路径规划目标函数；通过引入新的启发函数因子、节点随机选择机制、局部更新和全局更新相结合的策略分别对算法的节点转移概率设计、节点选择策略和信息素更新策略进行了优化改进。Matlab仿真结果表明，在三维空间环境模型中，传统蚁群算法和改进蚁群算法均能为煤炭勘探及救援机器人搜索出一条最优路径；在不同任务要求下，改进蚁群算法能有效缩短搜索路径长度和降低路径搜索时间，且具有较强的决策能力和较好的收敛性能。
关键词：煤炭开采； 煤炭勘探； 救援机器人； 路径规划； 蚁群算法
煤炭资源勘探作为煤炭资源开采和煤炭工业建设的基础和前提，其勘探信息的准确与否将会对煤炭资源储备评估和国家煤炭工业建设布局设计产生直接的影响[1]。因此，在煤炭资源勘探过程中，如何获取人无法到达或不适宜到达及无人机或其他智能设备不易监测到的区域的详细地质信息是亟待解决的难题。煤炭勘探及救援机器人的出现很好地解决了这一难题。煤炭勘探及救援机器人是一种集计算机、无线网络通信、图像处理、人工智能、机械设计、机械电子及仿生学等为一体的智能机械移动装置，其主要作用是利用自身配置的雷达传感器、红外传感器、CCD摄像机及其他智能仪器装置，代替勘探人员进入指定工作区域，完成环境侦查、煤炭资源勘探和人员搜索救援等任务[2]。在复杂多变的三维运行环境中，煤炭勘探及救援机器人如何在已知起点和目标点的前提下，快速进入指定工作区完成煤炭资源勘探和人员搜索任务，涉及到机器人三维空间路径规划问题。针对三维空间路径规划问题，目前常用的有效方法主要有A*算法[3]、遗传算法[4]、粒子群算法[5]、蝙蝠算法[6]及蚁群算法[7]等。
蚁群算法是一种启发式智能群体仿生优化算法，由于该算法具有较强的鲁棒性、优良的分布式计算机制，所以，其在优化组合、NP难题、二次分配、机器人路径规划、车间调度及通信网络路由等领域得到广泛应用[8-11]。针对煤炭勘探及救援机器人三维空间路径规划问题，在传统蚁群算法基础上，通过引入新的启发函数因子对节点转移概率进行了重新设计；为了增加节点选择多样性、增强算法全局搜索能力和改善算法收敛性能，通过引入节点随机选择机制和信息素局部和全局相结合的更新策略分别对节点选择策略和信息素更新策略进行了优化改进。
1.1 问题描述
环境模型是研究路径规划问题的基础和前提，因此，在对煤炭勘探及救援机器人三维路径规划问题进行研究前，需对其运行环境作如下处理[12]：① 将煤炭勘探及救援机器人工作环境简化为三维有限空间。② 机器人工作环境中的障碍物可用不规则的多边形表示。③ 假设机器人的运行速度恒定，忽略其启动、转向和制动等操作。④ 为便于仿真，将机器人视为一质点，另外，对环境中的障碍物也要作适当的膨化处理，并允许机器人沿着障碍物边界行走。
1.2 环境建模
针对三维空间环境模型，目前常用的建模方法主要有栅格法、几何法和高程法。其中，几何法存在所需数据存储数量大且无法对环境进行有效描述等缺陷；高程法虽然能有效降低数据存储空间和提高建模速度，但存在信息缺失的缺陷。基于此，选用栅格法创建煤炭勘探及救援机器人的三维空间运行环境模型，其建模思想可描述如下[13]：① 根据现实环境信息构建煤炭勘探及救援机器人的三维空间模型，如图1所示。② 将三维空间模型划分成二维平面。③ 选用栅格法将二维平面分割成多个大小相等的栅格，并提取三维路径规划所需网格节点。④ 根据现实环境信息，连接三维空间模型各网格节点，即可得到所需的三维路径规划空间环境模型，如图2所示。
图1 三维空间模型
图2 三维路径规划空间环境模型
图1中O点为三维空间坐标原点，x轴为经度方向，y轴为纬度方向，z轴为海拔高度方向。三维地图在x轴方向的最大长度取值为OA，y轴方向的最大长度取值为OC，z轴方向的最大长度取值为OO′。采用栅格法划分二维平面的目的是将三维空间模型离散化为一系列点集合，为后续采用蚁群算法进行路径搜索提供数据支持。三维路径规划空间环境模型区域跨度为21 km×21 km×2 km，其中S1，S2和S3表示煤炭勘探及救援机器人的起始位置，其三维空间坐标分别为(1,3,600)，(1,9,800)和(1,17,400)，T1，T2和T3表示煤炭勘探及救援机器人的目标点位置，其空间坐标分别为(21,10,1 000)，(21,7,1 200)和(21,17,1 200)。
1.3 目标函数建立
研究煤炭勘探及救援机器人三维空间路径规划问题的目的是在已知有障碍物存在的运行环境中，在已知机器人起点和目标点位置的前提下，以评价指标最优为准则，采用特定搜索策略，为机器人规划出一条从起点到目标点的安全最优路径，并确保机器人能够沿着该优化路径，在较短的时间内快速完成环境侦查、煤炭资源勘探和人员搜索救援等任务。设节点i，j表示可行路段上的2个端点，建立煤炭勘探及救援机器人的路径规划目标函数[14]：
(1)
(2)
式中：L为机器人从起点到目标点所走过的总路径长度；(xi,yi,zi)和(xj,yj,zj)分别为节点i，j的空间几何坐标；Lshort_road为机器人从起点到目标点所走过的最短路径长度；L(m,k)为蚂蚁k在第m次路径迭代搜索中所走过的总路段长度。
2.1 启发函数因子设计
启发函数因子是蚁群算法中节点转移概率的重要组成部分，它在某种程度上会对算法的收敛性能、稳定性及全局搜索能力产生一定的影响。在传统蚁群算法中，在三维空间路径规划条件下，启发函数因子一般用两相邻节点(a,a+1)间的空间几何距离的倒数来表示，如式(3)所示。传统算法的启发函数因子只考虑了当前节点a和下一节点a+1的空间几何关系，而并未考虑当前节点a和目标节点e的空间几何关系，因此，采用此启发函数因子对搜索路径进行诱导时，会致使算法因缺乏目标性而导致路径搜索效率降低或路径搜索结果出现偏差，从而形成局部最优解或无效解。基于此，在充分考虑当前节点a、下一节点a+1及目标节点e的基础上，通过引入安全因子S，重新对启发函数因子η进行设计，具体如式(4)—式(6)所示[15]。
(3)
(4)
(5)
(6)
式中：η(i,j,k)为传统蚁群算法的启发函数因子；d(i,j,k)为当前节点a和下一节点a+1间的空间几何距离；(xa,ya,za),(xa+1,ya+1,za+1)和(xe,ye,ze)分别为当前节点a、下一节点a+1和目标节点e的空间几何坐标；
为重新设计的启发函数因子；D(i,j,k)为当前节点a到目标节点e的空间几何距离；S(i,j,k)为节点选择安全因素，当选择节点不可到达时，该值可取0，其作用是促使蚂蚁在路径搜索中选择安全点，并确保规划的路径尽可能远离障碍点；λ1，λ2，λ3分别为d(i,j,k)，D(i,j,k)和S(i,j,k)的相对重要程度因子，λ1，λ2，λ3∈[0,1]；N为点(i,j,k)的可视节点总数；NU为可视节点中不可到达节点总数。
2.2 节点转移概率设计
节点转移概率是蚁群算法的重要组成部分，它直接影响着蚂蚁在路径搜索中节点的选择概率，也影响着蚂蚁的行进路线。为了使算法在路径搜索中更具指导性和目的性，在传统节点转移概率计算公式(式(7))的基础上，通过引入新的启发函数因子，对节点转移概率进行了重新设计，具体如式(8)所示。
Pa,a+1(t)=
(7)
(8)
式中：Pa,a+1为传统算法下蚂蚁由节点a转移到节点a+1的概率；
为改进算法下蚂蚁由节点a转移到节点a+1的概率；τa,a+1为路径(a,a+1)上的信息素量；α为信息素启发式因子；β为节点间的期望启发因子；W为蚂蚁下一步可选择的可达节点集合。
2.3 节点选择策略
在建立最优路径的过程中，蚂蚁必须不断地从相邻节点选择下一节点，因此，为增加节点选择多样性和避免算法陷入局部最优，在采用概率选择路径节点的基础上，通过引入随机选择机制对节点选择策略进行了改进[16]，改进后的节点选择公式为
a+1=
(9)
式中：q为[0,1]区间上的一个随机数；q0为可调参数，q0∈[0,1]，其作用是使节点选择更具倾向性。
分析式(9)可知，当q≤q0时，可达节点a+1可直接由
确定；当q>q0时，可达节点a+1可由节点转移概率和轮盘赌法联合确定。
2.4 信息素更新策略
信息素浓度的强弱决定了蚂蚁在搜索路径上节点的选择。为了增强算法全局搜索能力和改善算法收敛性能，避免搜索路径因信息素浓度过高或过低而致使算法出现停滞或早熟问题，通过引入信息素局部和全局相结合的更新策略对基本蚁群算法进行了优化改进。
2.4.1 局部信息素更新
局部信息素更新目的是通过减少蚂蚁已访问节点的信息素来增加未访问节点被访问的概率，以此增加节点选择多样性，避免蚂蚁在路径搜索中收敛到同一路径。在三维路径搜索中，当蚂蚁由节点a移动到节点a+1时，需要完成一次局部信息素更新，局部信息素更新规则为
(10)
式中：τijk为点(i,j,k)上的信息素值；ε为信息素衰减系数；τ0为初始信息素值。
2.4.2 全局信息素更新
全局信息素更新目的是使算法搜索更具指导性，且将蚂蚁搜索范围集中在最优解附近，以此增强算法的全局搜索能力和改善算法的收敛性能。全局信息素更新只有在所有蚂蚁完成各自的路径搜索后才会执行，全局信息素更新规则为
(11)
(12)
式中：ρ为信息素挥发系数，ρ∈[0, 1]；1-ρ为信息素持久性系数；Δτijk为信息素增量；Q为常数；Lh为目前为止所有蚂蚁所能搜索到的全局最优路径。
2.5 算法实施步骤
在山区三维空间环境模型中，利用改进蚁群算法进行煤炭勘探及救援机器人三维路径规划的具体实施步骤如下：
(1) 在Matlab平台上，利用栅格法创建煤炭勘探及救援机器人的山区三维空间运行环境模型，并确定机器人在环境模型中的起点和目标点位置。
(2) 初始化算法参数，分别设置蚂蚁的起始点S和目标点T、蚂蚁数量m、信息素挥发系数ρ、期望启发因子β、算法初始迭代次数C和最大迭代次数Cmax等参数。
(3) 开始搜索，根据节点选择策略，按照不同条件约束，确定蚂蚁的下一可行路径节点。
(4) 根据局部信息素更新方程，对蚂蚁刚访问节点的信息素进行局部更新。
(5) 判断所有蚂蚁的路径搜索任务是否完成，若是，则按照全局信息素更新方程，对目前为止所有蚂蚁所能搜索到的最优路径的信息素进行全局更新；否则，搜索过程转至步骤(3)。
(6) 根据算法终止条件C≤Cmax，判断算法搜索过程是否结束，若C>Cmax，则算法路径搜索过程结束，输出最优路径；否则，算法搜索过程转至步骤(3)。
3 仿真实验及分析
在如图2所示的环境模型下，以安全避障和路径最短为评价指标，选用所设计的改进蚁群算法作为搜索策略，在Matlab平台上对煤炭勘探及救援机器人三维路径规划过程进行了仿真测试。在测试前，设置如下参数：蚂蚁起点坐标S1，S2和S3分别为(1,3,600)，(1,9,800)和(1,17,400)；蚂蚁目标点坐标T1，T2和T3分别为(21,10,1 000)，(21,7,1 200)和(21,17,1 200)；蚂蚁数量m=15；算法初始迭代次数C=1；最大迭代次数Cmax=80；信息素挥发系数ρ=0.6；常数Q=150。
为了便于对路径搜索过程和搜索结果进行观察和分析，给出了在不同任务要求下，传统蚁群算法和改进蚁群算法为煤炭勘探及救援机器人规划的最短路径可视化图，如图3—图5所示。在图3—图5中，种群最佳适应度迭代曲线主要用于评价算法在路径搜索过程中的决策能力和收敛性能，其评估规则是种群适应度取值大小与算法的决策能力和收敛性能成负相关，即种群适应度值越小，算法的环境适应能力和决策能力越强，收敛性能越好。
(a) 最短路径轨迹
(b) 种群最佳适应度迭代曲线
图3 煤炭勘探及救援机器人从起点S1到目标点T1的最短路径可视化图
(a) 最短路径轨迹
(b) 种群最佳适应度迭代曲线
图4 煤炭勘探及救援机器人从起点S2到目标点T2的最短路径可视化图
(a) 最短路径轨迹
(b) 种群最佳适应度迭代曲线
图5 煤炭勘探及救援机器人从起点S3到目标点T3的最短路径可视化图
2种算法的路径搜索结果见表1。由图3—图5所示路径搜索结果，综合表1数据分析可知，在避障路径规划方面，在山区三维空间环境模型中，传统蚁群算法和改进蚁群算法均能为煤炭勘探及救援机器人搜索出一条最优路径，且在不同任务(即S1→T1，S2→T2和S3→T3)要求下，改进蚁群算法搜索的最优路径长度小于传统蚁群算法。在种群最佳适应度取值和收敛代数方面，在S1→T1条件下，传统蚁群算法的种群适应度最佳值在第43代取得，改进蚁群算法在第27代取得，且改进蚁群算法的适应度最佳值小于传统蚁群算法；在S2→T2条件下，传统蚁群算法的种群适应度最佳值在第45代取得，改进蚁群算法在第33代取得，且改进蚁群算法的适应度最佳值小于传统蚁群算法；在S3→T3条件下，传统蚁群算法的种群适应度最佳值在第33代取得，改进蚁群算法在第19代取得，且改进蚁群算法的适应度最佳值小于传统蚁群算法。根据种群适应度取值大小与算法的决策能力和收敛性能成负相关的特性可知，在S1→T1，S2→T2和S3→T3条件下，改进蚁群算法的种群适应能力、决策能力以及收敛性能均优于传统蚁群算法。在程序运行时间方面，在3种条件下，传统蚁群算法耗时均大于改进蚁群算法，表明改进蚁群算法的路径搜索效率明显高于传统蚁群算法。
表1 2种算法的路径搜索结果
针对煤炭勘探及救援机器人三维空间路径规划问题，提出了一种基于改进蚁群算法的三维路径规划方法。利用栅格法创建了山区三维空间环境模型，建立了煤炭勘探及救援机器人的路径规划目标函数；具体介绍了启发函数因子设计、节点转移概率设计、节点选择策略和信息素更新策略。Matlab仿真结果表明，在山区三维空间环境模型中，传统蚁群算法和改进蚁群算法均能为煤炭勘探及救援机器人搜索出一条最优路径；在不同任务要求下，与传统蚁群算法相比，改进蚁群算法能有效缩短搜索路径长度和降低路径搜索时间，且在路径搜索中表现出较强的决策能力和较好的收敛性能。
参考文献：
[1] DZ/T 0215—2002煤、泥炭地质勘查规范[S].
[2] 刘建,葛世荣,朱华,等.基于多目标优化的矿用救援机器人动力匹配[J].机械工程学报,2015(3):18-28.
[3] ZHAO Junwei, ZHAO Jianjun. Path planning of multi-UAVs concealment attack based on new A*method[C]//Sixth International Conference on Intelligent Human-Machine Systems and Cybernetics, 2014.
[4] WANG Honglun, LYU Wentao, YAO Peng, et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[J]. Chinese Journal of Aeronautics, 2015, 28(1):
229-239.
[5] ZENG Nianyin, ZHANG Hong, CHEN Yanping, et al. Path planning for intelligent robot based on switching local evolutionary PSO algorithm[J]. Assembly Automation, 2016, 36(2):120-126.
[6] WANG G G, CHU H E, MIRJALILI S. Three-dimensional path planning for UCAV using an improved bat algorithm[J]. Aerospace Science and Technology, 2016, 49: 231-238.
[7] WANG Chao, HE Chaonan. Three-dimensional planning of arrival and departure route network based on improved ant-colony algorithm[J]. Transaction of Nanjing University of Aeronautics and Astronautics, 2015, 32(6): 654-664.
[8] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[9] 刘利强,于飞,戴运桃.基于蚁群算法的水下潜器三维空间路径规划[J].系统仿真学报,2008,20(14):3712-3716.
[10] XIAO Qinkun, WANG Yi, GAO Song, et al. 3D path planning based on elevation model and ant colony algorithm[C]//5th International Conference on Intelligent Human-Machine Systems and Cybernetics,2013.
[11] TAN Jianhao, WANG Chu, WANG Yaonan, et al. Three-dimensional path planning based on ant colony algorithm with potential field for rotary-wing flying robot[C]//IEEE International Conference on Information and Automation, 2015.
[12] 何少佳,史剑清,王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报,2014,34(4):765-770.
[13] 李向军,霍艳丽,曾勍炜,等.三维机器人路径规划的一种变异算子蚁群算法[J].计算机仿真,2015,32(2):364-368.
[14] 黄月,吴成东,董晶晶,等.基于WSN的灾难现场最优逃生路径规划[J].东北大学学报(自然科学版),2013,34(2):162-165.
[15] LIU Liqiang, DAI Yuntao. 3D space path planning of complex environmental underwater vehicle[C]//International Joint Conference on Computational Sciences and Optimization,2009.
[16] 肖秦琨,王弋,罗艺闯.偏微分高程图环境蚁群算法的三维路径规划[J].系统工程与电子技术,2015(7):1551-1561.
Research on the optimal path planning of coal exploration and rescue robot
LI Xiaojing1,2, YU Dongman1,2
(1.College of Mechanical Engineering, Henan Polytechnic Institute, Nanyang 473009, China;2.Henan Engineering Laboratory of Flexible Manufacture, Nanyang 473009, China)
Abstract：In order to solve path planning problem of coal exploration and rescue robots in three-dimentional environment, an optimal path planning method for coal exploration and rescue robot based on improved ant colony algorithm was proposed. Three-dimensional space environment model is established by using grid method, and path planning objective function of coal exploration and rescue robot is established. Node transition probability design, node selection strategy and pheromone update strategy are optimized and improved by introducing new heuristic function factor, random selection mechanism of node and combining strategy of local updating and global updating. Matlab simulation results show that both the traditional ant colony algorithm and the improved ant colony algorithm can find an optimal path for the coal exploration and rescue robot in the three-dimensional environment model. Under different task requirements, the improved ant colony algorithm can effectively shorten the length of search path and reduce time of path search, and has strong decision-making ability and good convergence performance.
Key words：coal mining; coal exploration; rescue robot; path planning; ant colony algorithm
文章编号：1671-251X(2017)03-0024-06
DOI：10.13272/j.issn.1671-251x.2017.03.006
收稿日期：2016-09-05；
修回日期：2017-01-15；责任编辑：胡娴。
基金项目：河南省青年骨干教师资助计划项目(2012GGJS-248)。
作者简介：李晓静(1980-)，女，河南邓州人，实验师，主要研究方向为算法流程、公差配合等，E-mail:hnpilxj@126.com。通信作者：余东满(1977-)，男，河南邓州人，副教授，博士，主要研究方向为机构设计、仿真分析等，E-mail:yudongman@126.com。
中图分类号：TD67
文献标志码：A
网络出版：时间：2017-02-28 16:47
网络出版地址：http://kns.cnki.net/kcms/detail/32.1627.TP.20170301.1514.006.html
李晓静，余东满.煤炭勘探及救援机器人最优路径规划研究[J].工矿自动化，2017,43(3)：24-29.