煤矿机械CoalMineMachineryVol.35No.04Apr.2014第35卷第04期2014年04月0引言煤矿救援机器人路径规划是在有障碍区域的环境中，寻找一条从起点到目标点的有效路径，要求所走路径安全性最高、路程最短。路径规划功能的强弱在一定程度上反映了煤矿救援机器人的智能水平，机器人路径规划算法正在向智能算法、仿生算法方向发展。1环境建模首先确定执行任务的区域范围，并由环境信息构建地图模型，这是一个二维平面运动模型，只需考虑二维平面的相关信息。路径起点为救援机器人开始进入灾害危险区域的起始点，终点为救援机器人通过障碍区域开始进行救援作业的位置。根据起点和终点位置，建立二维坐标系统，设为救援机器人的整个路径规划区域。在此范围内存在一定数量的威胁区域，可以用一个圆来近似表示。如图1所示，整个威胁区域为D，威胁点个数为k，第i个威胁点中心位置为（xRi，yRi），威胁范围用半径Ri表示，则每个威胁区域可表示为｛Di|Di=πRi2｝，整个威胁区域表示为｛D｜D＝D1∪D2∪…∪Dk｝。2路径表示规划区域是一个二维平面，在起点和终点之间找到一条距离最短且不能碰到任何障碍的路径，因此必须在此区域内寻找一系列参考点，机器人沿着参考点运动直到终点。如图1所示，设起点为S，终点为T，点S、T连线平行于X轴，平行于Y轴作n-1条平行直线，将ST连线平分成n段，在每条平行线上取一个点作为路径参考点，连接起点S、参考点和终点T，就得到一条路径P=｛S，（x1，y1），（x2，y2），…，（xi，yi），…，（xn-1，yn-1），T｝（1）且P∈D，其中点（xi，yi）表示第i条平行线上的参考点坐标。图1环境模型*国家自然科学基金项目(61105063)基于人工鱼群算法的煤矿救援机器人路径规划*姚正华1,2，任子晖1，陈艳娜3（1.中国矿业大学信电学院，江苏徐州221008；2.长江师范学院机电学院，重庆408000；3.重庆理工大学汽车学院，重庆400050）摘要：根据煤矿救援环境特点，采用人工鱼群算法对救援路径进行规划，在二维平面内建立环境模型，并采用威胁区域距离检测的方式处理优化约束条件。对不同数目参考点选取进行对比研究，增加参考点数目，路径长度增加，算法复杂程度提高，迭代时间延长，算法性能下降；参考点过少会导致路径规划成功率降低。仿真结果表明，设置合理的参考点数目，人工鱼群算法能在较短的迭代时间内成功规划得到最优路径。关键词：人工鱼群算法；路径规划；煤矿救援；机器人中图分类号：TP301.6文献标志码：A文章编号：1003－0794（2014）04－0059－03PathPlanningforMineRescueRobotBasedonAFSAYAOZheng-hua1,2，RENZi-hui1，CHENYan-na3(1.CollegeofMechanicalandElectrical，ChinaUniversityofMiningandTechnology,Xuzhou221008,China;2.CollegeofMechanicalandElectrical，YangziNormalUniversity,Chongqing408000,China;3.CollegeofAutomobile，ChongqingUniversityofTechnology,Chongqing400050,China）Abstract:Accordingtotheminerescueenvironmentalcharacteristics,theartificialfishswarmalgorithmwasusedforminerescuerobotpathplanning.Theenvironmentmodelwasestablishedontwo-dimensionalplane,andtheoptimizationconstraintsconditionsweredisposedbythemannerofthreatsregionaldistancedetection.Thedifferentnumberofreferencepointsselectedforcomparativestudies,thepathlengthincreased,thecomplexityofthealgorithmimproved,andtheiterativetimeofalgorithmprolongedwiththenumberofreferencepointsincreasedthatleadedthealgorithmperformancedegenerated.Thenumberofreferencepointswastoofewwouldleadtolowpathplanningsuccessrate.Thesimulationresultsindicatedthattheartificialfishswarmalgorithmcouldplantheoptimalpathwithareasonablenumberofthereferencepointssuccessfullyinashortperiodofiterativetime.Keywords:AFSA;pathplanning;minerescue;robot1009080706050403020100ST123n-220n-1406080100…Ddoi:10.13436/j.mkjx.20140402659

3基于人工鱼群算法的路径规划（1）人工鱼群算法人工鱼群算法通过模拟鱼群的相互社会行为，实现集群智能的一种优化算法。它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，有着较快的收敛速度，对搜索空间具有一定的自适应能力，对鱼群参数的选择也不很敏感。人工鱼群算法模型的核心思想为觅食算子、聚群算子和追尾算子。设在一个D维搜索空间中，有N条人工鱼，其中第i条人工鱼的位置向量为Xi，i=1，2，…，N。人工鱼当前位置食物浓度（目标函数适应值）为Y=f（X），其中人工鱼状态X为寻优变量。2条人工鱼个体之间的距离表示为｜｜Xi-Xj｜｜；δ为拥挤度因子；visual表示人工鱼感知范围；step表示人工鱼移动最大步长；try_number表示觅食算子中人工鱼最大试探次数。每个参考点位于将ST连线n段等分的n-1条垂线上，在算法执行过程中，只改变各个参考点的纵坐标，横坐标不变，因此路径可用各个参考点的纵坐标来表示。每条人工鱼的状态Xi＝｛x1，x2，…，xn-1｝（2）表示一条路径，xi为第i个参考点，纵坐标yi的值，i=1，2，…，n-1。人工鱼随机行动一次，自身状态改变一次，即产生一条新路径，若新路径的适应值高于原路径，则更新该条人工鱼状态。（2）约束条件处理由环境模型可知，路径约束条件为｛D｜D＝D1∪D2∪…∪Dk｝（3）即路径不能与障碍区域有任何交集。由路径表示可知，各参考点之间的连线、起点与参考点的连线以及参考点与终点的连线不经过障碍区域，即满足了约束条件。设第i个中心为（xRi，yRi）的障碍区域｛Di｜Di＝πRi2｝（4）与第j个参考点（xj，yj）满足（xj-xRi）2+（yj-yRi）2姨≥Ri+Δ（5）即可满足参考点在障碍区域外，其中，i=1，2，…，k；j=1，2，…，n-1；Δ为可设定安全距离裕量，机器人被抽象成移动质点，设定一定的裕量保证机器人行走路径与威胁区域有一定的安全距离。当参考点均处于威胁区域外时，路径连线仍可能有部分处于威胁区域内。当参考点均在安全区域内时，对起点、参考点和终点2个相邻点之间的路径连线，若任意威胁点中心到该连线的垂足不在该连线上，则该段路径必不经过该威胁区域。若垂足处于该段路径内，对第j段路径上的垂足（xj，yj）满足（xj-xRi）2+（yj-yRi）2姨≥Ri+Δ（6）即可满足该段路径在威胁区域外。其中i=1，2，…，k，j=1，2，…，n，Δ为可设定安全裕量，（xRi，yRi）为第i个障碍区域中心。（3）适应值评价函数煤矿发生灾害时，救援机器人在行进时必须躲避威胁区域，尽快到达救灾作业点。因此以路径长度为主要评判依据，以威胁区域为约束条件。总路径距离可表示为从起点开始，经过每个参考点到终点各段路径距离之和，即Y=（x1-xS）2+（y1-yS）2姨+n-2i=1Σ（xi+1-xi）2+（yi+1-yi）2姨+（xT-xn-1）2+（yT-yn-1）2姨（7）式中（xS，yS）———路径起点坐标；（xT，yT）———终点坐标；（xi，yi）———第i个参考点坐标，i=1，2，…，n-1。（4）算法步骤①输入原始数据，生成环境模型；②设置人工鱼群初始参数（包括鱼群规模N、最大迭代次数IT、人工鱼视野visual、最大移动步长step、拥挤度因子δ、尝试次数trynumber等）；③当前迭代次数ITtimes=0，生成N条人工鱼，形成初始鱼群；④各条人工鱼分别执行觅食算子、聚群算子和追尾算子，评价执行结果，选择最优行为执行；⑤每条人工鱼行动一次后，检验自身状态，若优于公告牌状态，则更新公告牌；⑥判断ITtimes是否已达最大迭代次数IT，若达到最大迭代次数，则输出最优路径，否则ITtimes=ITtimes+1，转步骤④。4仿真结果及分析在内存为2G，CPU为i3-2330M2.2Hz，操作系统为Windows7的计算机上，采用Matlab_R2012a对算法进行仿真实验。设置机器人路径优化区域为100×100，起点S（0，50），终点T（100，50），鱼群规模N=5，最大迭代次数IT=200，人工鱼个体视野距离visual=20，人工鱼移动步长step=2，觅食尝试次数try_number=100，拥挤度因子δ=0.618。20次规划中对不同参考点个数进行仿真对比，参考点数目n=7时得到的最优路径和最差路径如图2所示。（a）最优路径（b）最差路径图2参考点n=7时最优、最差路径第35卷第04期Vol.35No.04基于人工鱼群算法的煤矿救援机器人路径规划———姚正华，等1009080706050403020100020406080100xy1009080706050403020100y020406080100x60

避免路径陷入威胁区域，是路径规划成功的关键，在路径规划过程中参考点越多，路径避免威胁的可能性就越大，但在鱼群算法执行过程中依靠增加参考点来避免威胁，人工鱼状态维数将增大，鱼群个体编码长度增加，算法计算复杂度提高，反而会降低搜索效果。图3为参考点增加1倍后算法规划的最优路径和最差路径。（a）最优路径（b）最差路径图3参考点n=14时最优、最差路径表1为不同参考点个数分别执行20次仿真时的结果对比。由表1可知，参考点过少，路径距离较短，但规划成功率过低，算法需要较长的时间才可能规划出可行路径，因此迭代时间较长，成功率较低；参考点数过多，路径距离增加，人工鱼编码变长，算法复杂度提高，算法迭代时间自然也增加，算法性能明显降低。因此需根据仿真结果，比较性能指标，合理选择参考点数目。表1不同参考点个数仿真对比5结语依据救援机器人路径规划范围内的环境特点，采用人工鱼群算法对矿井救援机器人进行路径规划研究。（1）采用一维坐标参数表示二维参考点的方式对人工鱼进行编码，简化了人工鱼个体的编码方式，提高算法执行效率；（2）在二维平面内，对各段路径与威胁区域进行威胁距离检测，当各段路径与威胁区域的距离均大于威胁半径时，满足规划约束条件，规划路径有效；（3）增加路径参考点，路径长度增大，人工鱼个体状态维数增加，人工鱼编码变长，算法复杂程度提高，迭代时间延长，导致算法整体性能下降；参考点过少会导致无法成功规划出有效路径，规划成功率较低。参考文献：［1］孙继平.煤矿安全生产理念研究［J］.煤炭学报,2011,36(2):313-316．［2］王忠民，刘军，窦智，等．矿难救援机器人的研究应用现状与开发［J］.煤矿机械,2007,28(11):6-8．［3］马千知，雷秀娟．改进粒子群算法在机器人路径规划中的应用［J］.计算机工程与应用，2011,47(25)：241-242．［4］张小艳，周筱媛，魏娟．煤矿救援机器人全局路径规划［J］.西安科技大学学报，2008,28(2):323-326．［5］王俭，赵鹤鸣，陈卫东．移动机器人全覆盖任务的研究进展［J］.工矿自动化，2006(3):26-30．［6］雷秀娟.群智能优化算法及其应用［M］.北京：科学出版社，2012．［7］李晓磊.一种新型的智能优化方法—人工鱼群算法［D］.杭州:浙江大学，2003．［8］李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法［J］.系统工程理论与实践，2002(11):33－34．［9］江铭炎，袁东风．人工鱼群算法及其应用［M］.北京：科学出版社，2012．作者简介：姚正华（1982-），江苏盐城人，讲师，博士研究生，主要研究方向为智能优化与控制、计算机测控技术等，电子信箱：emscto@qq.com.责任编辑：卢盛春收稿日期：2013－11－04参考点数n=5n=7n=14最优值103.5121104.5534117.5469时间/s3.63061.719976.8870最差值113.8093116.2062158.9788时间/s3.86193.342012.0042成功率/%35100100000000000000000000000000000000000000000000000第35卷第04期Vol.35No.04基于人工鱼群算法的煤矿救援机器人路径规划———姚正华，等1009080706050403020100y20406080100x1009080706050403020100y20406080100x1980年1～2期为第1卷1981年1～6期为第2卷1982年1～6期为第3卷1983年1～6期为第4卷1984年1～6期为第5卷1985年1～6期为第6卷1986年1～6期为第7卷1987年1～6期为第8卷1988年1～6期为第9卷1989年1～12期为第10卷1990年1～12期为第11卷1991年1～6期为第12卷1992年1～6期为第13卷1993年1～6期为第14卷1994年1～6期为第15卷1995年1～6期为第16卷1996年1～6期为第17卷1997年1～6期为第18卷1998年1～12期为第19卷1999年1～12期为第20卷2000年1～12期为第21卷2001年1～12期为第22卷2002年1～12期为第23卷2003年1～12期为第24卷2004年1～12期为第25卷2005年1～12期为第26卷2006年1～12期为第27卷2007年1～12期为第28卷2008年1～12期为第29卷2009年1～12期为第30卷2010年1～12期为第31卷2011年1～12期为第32卷2012年1～12期为第33卷2013年1～12期为第34卷2014年1～12期为第35卷文章参考文献以出版年、卷、期、文章页码进行引用。本刊声明《煤矿机械》月刊从2006年第1期开始，以每1期为相应的期次、卷期记录出版次序。1980年创刊至今已有35年，每年划为1卷，2014年为第35卷。61