基于改进人工势场法的救灾机器人路径规划

田子建，　高学浩

(中国矿业大学(北京) 机电与信息工程学院， 北京　100083)



实验研究

基于改进人工势场法的救灾机器人路径规划

田子建，高学浩

(中国矿业大学(北京) 机电与信息工程学院， 北京100083)

针对矿井障碍物复杂多变、救灾机器人采用传统人工势场法进行路径规划易陷入局部极小点的问题，提出一种基于改进人工势场法的救灾机器人路径规划方法。该方法通过在引力场中加入扰动场来改变引力场函数，使救灾机器人在陷入局部极小点时自主走出局部极小点；结合障碍填充法，通过对凹障碍物进行虚拟填充，形成新的障碍物并产生相应的斥力场函数，避免救灾机器人再次陷入局部极小点。仿真及测试结果验证了该方法的可行性及有效性。

救灾机器人； 路径规划； 人工势场法； 扰动场； 势场函数； 障碍物填充法

网络出版地址：http://www.cnki.net/kcms/detail/32.1627.TP.20160902.1012.009.html

0　引言

煤矿井下发生矿难时，采用机器人进行探测和救援是可靠、有效的途径，针对井下机器人供电、防爆、机器人步履机械柔性等关键问题的研究，通过科研人员长期不懈的努力，已取得了长足进步[1-2]。煤矿井下环境特殊，巷道相互交叉，空间狭小封闭，机器人路径规划一直是制约机器人在煤矿井下应用的难题。救灾机器人作为一种移动机器人，其路径规划的水平一定程度上决定了救灾效率。矿井救灾机器人的任务是在具有一定动态和静态障碍物的未知环境中，寻找一条没有碰撞的最佳路径，同时要实现最短路径、最短时间、最低能耗[3-4]等相应参数的优化。人工势场法是传统路径规划方法中较为成熟且简洁高效的算法，其主要思路是通过目标位置对机器人产生引力，障碍物对机器人产生斥力，以及机器人之间产生相互作用力，形成一个智能的人工势场，对机器人进行实时的路径规划[5-7]。但传统的人工势场法存在局部极小点问题，当障碍物在目标位置附近时，还会出现机器人在目标位置周围震荡、无法到达目标位置的情况。

简单地用传统人工势场法很难完成路径规划任务，因此需要对传统人工势场法进行改进，或与其他方法结合来避免路径规划失败。参考文献[8]提出了Laplace势场法，其基本着眼点是通过数学上合理地定义势场方程，保证势场中不存在局部极值，但没有考察路径是否最优。参考文献[9]提出了基于Fellow_wall的路径规划技术，可以帮助机器人逃离局部极小点，但算法收敛速度慢，鲁棒性差，需要耗费很长时间来完成路径规划，且无法选择最优路径。参考文献[10]提出了基于重力链方法来解决局部极小点问题，将起始点与目标位置用虚拟的橡皮筋连接起来，通过橡皮筋来代替人工势场产生转向角，解决了局部极小点和目标不可达的问题，但缺乏实际应用条件，难以实现。

本文针对传统人工势场法存在的局部极小点问题，提出了扰动场概念，通过在引力场中增加扰动场，使机器人陷入局部极小点时能自主逃离；结合障碍物填充法[11]，通过填充凹障碍物，形成新的斥力场函数，使机器人在逃离局部极小点的同时，避免再次陷入局部极小点，重新规划机器人路径，最终完成救灾任务。仿真结果验证了基于改进人工势场法的救灾机器人路径规划方法能够很好地解决矿井救灾机器人路径规划中的局部极小点问题。

1　传统人工势场法在矿井巷道中应用存在的问题

传统的人工势场法是由Khabit[12]在1986年提出的一种虚拟牛顿引力方法，起初是为了使机器人在抓取物体时，其手臂可以不触及工作台，后来运用到机器人运动避障中。其主要思想是将机器人、目标位置和障碍物简化成点，目标位置对机器人产生引力，障碍物对机器人产生斥力，在整个环境中，通过合力的作用控制机器人运动，进行路径规划。传统人工势场定义如下。

假设机器人的位置X=(x，y)，则目标位置与机器人之间的引力场为

(1)

式中：Katt为引力场常数；Xg为机器人的目标位置。

定义引力场的负梯度为

(2)

定义斥力场为

(3)

式中：Krep为斥力场常数；X0为障碍物的位置；X-X0为机器人到障碍物的距离；ρ0为障碍物产生的斥力场影响距离范围。

定义斥力场的负梯度为

Frep(X)=-gradUrep(X)=

(4)

则机器人在人工势场中的总势场为

(5)

人工势场对机器人的作用合力为

(6)

传统人工势场法原理简单，算法简洁，易于实现，适用于较广阔的地面场所，但在煤矿井下狭小区域[13-17]应用时，由于机器人大部分是沿巷道直线行走，很容易产生局部极小点和震荡等问题。如图1(a)所示，当障碍物、机器人和目标位置在同一条直线上时，机器人接近目标位置，引力变小，斥力变大，机器人会在某段路径上产生震荡，导致目标位置不可达。如图1(b)所示，当障碍物斥力与引力的合力为0时，机器人将陷入局部极小点，此时还没有到达目标位置，最终导致避障失败。为了解决该问题，本文提出基于改进人工势场法的救灾机器人路径规划。

(a)机器人震荡(b)机器人陷入局部极小点

图1传统人工势场法在井下应用存在的问题

2　基于改进人工势场法的救灾机器人路径规划

2.1扰动场的引入

当机器人在路径规划中陷入局部极小点时，增加扰动场来使机器人逃离局部极小点。定义扰动场为

(7)

式中：Kdis为扰动场常数；ρ(X,Xg)为机器人与目标位置的距离；ρa为机器人是否到达目标位置的评判距离。

引入扰动场后，当机器人陷入局部极小点时，环境模型的总势场为

Utotal(X)=Uatt(X)+Urep(X)+Udis(X)

(8)

救灾机器人进行避障时，在每个采样周期探测其可以到达的范围，寻找整个可探范围内的势场最低点，将该点称为子目标位置。采用矢量法对机器人所受引力和斥力进行合成，判断机器人是否处于局部极小点，如果是，则在总势场中加入扰动场。

2.2基于障碍物填充法的机器人路径规划

[11]提出了一种通过填充凹障碍物来避免局部极小点的方法。在现实避障过程中，机器人一般不能及时发现凹障碍物，发现时可能已经陷入局部极小点中，再通过填充障碍物并不一定能走出局部极小点。对于井下救灾机器人来说，巷道本身并不是障碍物，而移动救生舱、矿车、机械设备等是需要避开的障碍物。图2展示了3种在井下巷道中的障碍物。当机器人碰到类似图2(a)或图2(b)所示的3段或2段凹障碍物时，很难及时判别前方是否存在局部极小点，即使运用了障碍物填充法，也未必能逃出局部极小点。当救灾机器人遇到图2(c)所示的普通障碍物时，不会陷入局部极小点。

救灾机器人探测凹障碍物过程如图3所示。救灾机器人装有探测装置，探测到障碍物时会产生相应的探测角α。图3(a)中，救灾机器人探测到前方为2个障碍物，此时探测角α<180°。当救灾机器人运动到图3(b)位置时，已陷入凹障碍物中，探测角α>180°，机器人探测到凹障碍物的另一端，通过探测装置监测到该障碍物与之前探测的障碍物相连，从而判断为同一障碍物，但此时机器人已逐步陷入局部极小点，导致目标点不可达。

考虑到煤矿井下障碍物多变的情况，本文将扰动场和参考文献[11]提出的凹障碍物填充法相结合，提出一种新的救灾机器人路径规划方法。该方法主要思想：当救灾机器人陷入局部极小点后，通过扰动场使机器人逃离局部极小点，并运用凹障碍物填充法来填充产生局部极小点的障碍物，构造填充后的障碍物斥力函数，使救灾机器人在逃离局部极小点的同时，避免再次陷入局部极小点，如图4所示。

(a) 3段凹障碍物

(b) 2段凹障碍物

(c) 普通障碍物

(a)机器人未进入凹障碍物(b)机器人进入凹障碍物

图3救灾机器人探测凹障碍物过程

图4　基于改进人工势场法的救灾机器人路径规划方法

采用该救灾机器人路径规划方法后，可能产生局部极小点的区域被填充，形成一个面积更大的障碍物。被填充区域的斥力场为

(9)

式中：klocal为填充区域斥力场比例系数；x-xlocal为救灾机器人退出局部极小点时与局部极小点的距离；ρl为填充区域的影响范围。

完成凹障碍物填充后，填充后的势场强度为

(10)

当机器人完全退出可能产生局部极小点的凹障碍物区域，即凹障碍物区域被填充完毕时，机器人受到的总势场为

(11)

3　仿真研究

为了验证基于改进人工势场法的救灾机器人路径规划方法的性能，选用2种3段凹障碍物，在Matlab7.0.4环境下，分别对机器人路径轨迹和算法的空间复杂度进行了仿真。

3.1救灾机器人运行轨迹

首先采用增加扰动场的机器人路径规划方法(简称扰动场法)，对救灾机器人在障碍物a和障碍物b中的路径规划进行仿真，结果如图5所示。图5(a)中目标位置坐标为(0.45,0.2)，图5(b)中目标位置坐标为(0.45,0.05)。图5(a)中，救灾机器人陷入局部极小点后，机器人受到的总势场为0，但并未到达目标位置，此时在势场函数中加入扰动场，并重新规划路径。经过2次路径重新规划，机器人并没有逃离局部极小点，而是陷入了另一个局部极小点，最终没能走出凹障碍物区域。图5(b)中，救灾机器人经历了2次局部极小点，最终走出了局部极小点，成功避开了凹障碍物。可看出图5(a)中救灾机器人陷入局部极小点时，机器人与目标位置的距离远小于图5(b)中机器人与目标位置的距离，即图5(b)情况下的值更大，扰动场产生的斥力更大，更容易偏离原来的轨迹，便于重新规划路径。但图5(b)中机器人避障花费了更多的时间和路程，增加了算法难度，导致算法可靠性下降。

接下来采用基于扰动场和障碍物填充法的机器人路径规划方法(简称扰动场结合填充法)，对救灾机器人在障碍物a的路径规划进行仿真，结果如图6所示。目标位置坐标为(0.45,0.05)。可看出当救灾机器人陷入局部极小点时，扰动场结合填充法通过扰动场使机器人逃离局部极小点；由于填充了凹障碍物，势场函数中斥力场增大，使机器人的轨迹更为陡峭，且随着填充面积的增大，机器人逐渐逃离凹障碍物，重新规划路径后很快到达了目标位置。

(a) 障碍物a

(b) 障碍物b

图6　基于扰动场结合填充法的救灾机器人运行轨迹

3.2算法的空间复杂度

在全属性运行状态下，对扰动场法和扰动场结合填充法进行空间复杂度对比，以获得算法的运行时间、算法运行时内存占用率等。仿真结果如图7所示。可看出2种算法在样本数不大于500 000时，算法运行时间和系统内存占用率差别不大。随着样本数量的增加，扰动场结合填充法在运行时间和系统内存占用率上体现出很大优势：当仿真样本数目一定时，扰动场结合填充法的算法时间比单一的扰动场法少很多；扰动场法的内存使用率逼近59.5%，而扰动场结合填充法的内存使用率逼近43.5%，后者内存占用率更低。

(a) 运行时间

(b) 系统内存占用率

4　实验研究

采用ZY08-C-G型避障小车，结合VisualC++编程进行现场模拟避障实验。避障小车运行流程如图8所示。

图8　避障小车运行流程

现场设置及实验结果如图9所示。可看出小车很好地完成了避障任务，并最终到达设定的目标位置，验证了基于改进人工势场法的救灾机器人路径规划方法的可行性和有效性。

图9　现场设置及实验结果

5　结语

基于改进人工势场法的救灾机器人路径规划方法在救灾机器人陷入井下凹障碍物的局部极小点时，通过在势场函数中增加扰动场，能够使救灾机器人成功逃离局部极小点；结合障碍物填充法形成新的斥力场函数，使救灾机器人重新规划路径，避免再次陷入同一障碍物的其他局部极小点。仿真和实测验证了该方法的可行性和有效性。

参考文献：

[1]王忠民,刘军,窦智,等.矿难救援机器人的研究应用现状与开发[J].煤矿机械,2007,28(11):6-8.

[2]TIANZijian,ZHANGLiya,CHENWei.Improvedalgorithmfornavigationofrescuerobotsinundergroundmines[J].ComputersandElectricalEngineering,2013,39(4):1088-1094.

[3]朱磊,樊继壮,赵杰,等.基于栅格法的矿难搜索机器人全局路径规划与局部避障[J].中南大学学报(自然科学版),2011,42(11):3421-3428.

[4]张志超,郑之增,方海峰,等.矿井救灾机器人的导航定位研究[J].煤矿机械,2008,29(11):41-43.

[5]MINGP,JEONJH,MINCL.Obstacleavoidanceformobilerobotsusingartificialpotentialfieldapproachwithsimulatedannealing[C]//ProceedingsofIEEEInternationalSymposiumonIndustrialElectronics,Pusan,2001:1530-1535．

[6]KITAMURAY,TANAKAT,KISHINOF,etal. 3-Dpathplanninginadynamicenvironmentusinganoctreeandanartificialpotentialfield[C]//ProceedingsofIEEEInternationalConferenceonIntelligentRobotsandSystems,Piscataway，1995:2474-2481．

[7]JANABI-SHARIFIF,VINKED.Integrationoftheartificialpotentialfieldapproachwithsimulatedannealingforrobotpathplanning[C]//ProceedingsofIEEEInternationalSymposiumonIntelligentControl,Piscataway,1993:536-541．

[8]SATOK.Deadlock-freemotionplanningusingtheLaplacepotentialfield[J].AdvancedRobotics,1993,7(5): 449-461.

[9]谭民,王硕,曹志强.多机器人系统[M].北京:清华大学出版社,2005:42-46.

[10]TANGL,DIANS,GUG,etal.Anovelpotentialfieldmethodforobstacleavoidanceandpathplanningofmobilerobot[C]//ProceedingsofIEEEInternationalConferenceonComputerScienceandTechnology,Chengdu,2010:633-637.

[11]王佳，吴晓蓓，徐志良.避免人工势场中一类局部极小值的规划方法[J].计算机仿真,2007,24(11):151-154.

[12]KHATIBO.Real-timeobstacleavoidanceformanipulatorsandmo-bilerobots[C]//ProceedingsofIEEEInternationalConferenceonRoboticsandAutomation,Washington, 1990:500-505．

[13]石为人，黄兴华，周伟.基于改进人工势场法的移动机器人路径规划[J],计算机应用,2010, 30(8):2021-2023.

[14]肖本贤,余雷,李善寿,等.逃逸人工势场法局部极小值策略的研究[J].系统仿真学报，2007，19(19):4495-4503.

[15]孙继平.现代化矿井通信技术与系统[J].工矿自动化,2013,39 (3):1-5.

[16]庄晓东,孟庆春,高云,等.复杂环境中基于人工势场优化算法的最优路径规划[J].机器人,2003,25(6):531-535.

[17]方华京,魏然.人工势场法在多机器人运动中的研究[J].控制工程,2007,14(3):115-118.

Path planning of rescuing robot based on improved artificial potential field method

TIAN Zijian,GAO Xuehao

(SchoolofMechanicalElectronicandInformationEngineering,ChinaUniversityofMiningandTechnology(Beijing),Beijing100083,China)

Foraproblemthatrescuingrobotwaseasilystackedintolocalminimalpointbyusingtraditionalartificialpotentialfieldmethodtoplanpathincoalmineundergroundwithcomplexobstacles,apathplanningmethodofrescuingrobotbasedonimprovedartificialpotentialfieldmethodwasproposed.Inthemethod,perturbationfieldisaddedintogravitationfieldtochangegravitationfieldfunction,soastomakerescuingrobotgooutoflocalminimumpointautonomouslywhentherobotstacksintothelocalminimumpoint.Meanwhile,obstacleisfilledvirtuallythroughanobstaclefillingmethod,thusanewobstacleisformedandacorrespondingrepulsivepotentialfieldfunctionisgeneratedtoavoidrescuingrobottostackintolocalminimalpointagain.Thesimulationandtestresultsverifyfeasibilityandvalidityofthemethod.

rescuingrobot;pathplanning;artificialpotentialfieldmethod;perturbationfield;potentialfieldfunction;obstaclefillingmethod

1671-251X(2016)09-0037-06DOI:10.13272/j.issn.1671-251x.2016.09.009

2016-03-25；

2016-07-19；责任编辑：李明。

国家自然科学基金重点资助项目(51134024)；国家自然科学基金资助项目(U1261125)。

田子建(1964-)，男，湖南望城人，教授,博士，主要从事煤矿井下安全检测方面的研究工作，E-mail:tianzj0726@126.com。

TD67

A网络出版时间：2016-09-02 10:12

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