智能车自主避障路径规划研究综述

2017-11-02 11:22任子玉
软件导刊 2017年10期
关键词:智能算法智能控制

任子玉

摘要:避障路径规划是智能车技术的关键部分,避障路径规划具有重大研究意义与应用前景。对智能车辆自主避障路径规划进行了综述,分析了人工势场法、智能优化算法、强化学习等避障算法,指出任何一种有效的智能车避障系统均不能只依靠单一算法操作,因此结合多种避障路径规划算法应用于实际,是未来的研究热点与难点。

关键词:智能控制;避障规划;人工势场法;强化学习;智能算法

DOIDOI:10.11907/rjdk.171628

中图分类号:TP301

文献标识码:A文章编号:16727800(2017)010020904

0引言

1950年初,美国生产的第一台自动引导车辆开启了智能车辆(Intelligent Vehicle IV)发展之路[1]。1960年,通用汽车就已经测试了汽车自动驾驶测试轨道、车道跟踪、车道变换和自动跟踪功能。现今,美国卡内基梅隆Navlab、德国慕尼黑大学、意大利帕尔玛大学VisLab以及谷歌的无人驾驶汽车都在智能车辆领域取得了突破性进展。,由国防科技大学自主研制的红旗HQ3无人车也完成了从长沙到武汉286公里的高速全程无人驾驶试验。智能车辆的发展需要经历两个阶段,初级阶段是生产具有辅助驾驶系统ADAS及各类自动驾驶系统的智能车辆,终极阶段则是实现完全的无人驾驶。

研究智能车辆可以有效地提升车辆行驶安全性,降低交通事故发生的概率。避障问题是智能车领域的关键环节与研究热点,由于复杂的周围环境及智能车本身是一个非线性实变系统,整个控制系统无法用简单的数学模型来描述,根据车辆行驶坏境实现有效避障的难度很大,所以智能车需要安装避障路径规划系统。避障规划又叫局部路径规划,是一种动态路径规划,主要用于探测障碍物,并跟踪障碍物移动轨迹推算下一步可能位置,最终绘制出一幅障碍物地图[2]。避障规划不仅要考虑空间还要考虑时间序列,这是智能车难度最高的环节。避障规划的重点在于避障算法的设计,避障规划算法主要有传统算法、图形法、仿生学算法以及智能算法等。本文将介绍智能车自主避障路径规划的多种方法,其中包括人工势场法、智能优化算法及强化学习,并针对不同算法的缺点提出相应的改进措施。

1人工势场法(APF)

人工势场法(Artificial Potential Field,简称APF)是由Khatib于1986年提出的一种虚拟力法,它是传统算法的代表,由目标引力与周围障碍物斥力共同作用控制智能车的运动轨迹[3]。人工势场法的最终目的是找到一个连续路径可以使智能车从初始位置到目标位置,同时避免与障碍物碰撞。

1.1传统人工势场法

传统人工势场法中,障碍物是具有正势能的排斥力,而目标是具有负势能的吸引力。人工势场的定义是:

智能车与目标的引力函数:

Uatt(q)=12ερ2(q,qgoal)(1)

式(1)中,ε是尺度因子,ρ(q,qgoal)表示物体当前状态与目标的距离。引力就是引力场对距离的导数,所以这时负梯度为:

Fatt(q)=-Uatt(q)=ξ(qgoal-q)(2)

智能車对障碍物的斥力场为:

Urep(q)=12η1ρ(q,qobs)-1ρ\-0,if ρ(q,qobs)≤ρ\-00,if ρ(q,qobs)>ρ\-0(3)

式(3)中的η代表斥力因子,ρ(q,qobs)代表智能车和障碍物之间的距离,ρ0代表每个障碍物的影响半径。斥力就是斥力场的负梯度:

Frep(q)=-Urep(q)=

η1ρ(q,qobs)-1ρ\-01ρ2(q,qobs)ρ(q,qobs),if ρ(q,qobs)≤ρ\-00,if ρ(q,qobs)>ρ\-0(4)

引力场与斥力场矢量相加后就是合力的场,合力也是引力与斥力的叠加,所以合势场为[4]:

U(q)=Uatt(q)+Urep(q)(5)

相应智能车在运动中的合力为:

F(q)=-U(q)=Fatt(q)+Frep(q)(6)

人工势场法有助于控制智能车实时避障,并且规划相对安全的路径。但是当遇到引力与斥力刚好大小相等、方向相反的某一个点时,智能车会陷入局部最优解或者产生震荡摆动现象;当目标位置附近有障碍物时,斥力远远大于引力,智能车就会很难到达目标位置;当物体离目标位置相对较远时,引力远远大于斥力,此时可能忽略相对较小的斥力,智能车就有可能碰到障碍物。

1.2改进方法

对于人工势场法避障规划存在的问题有以下改进方法:

1.2.1局部最优改进方法

局部最优问题是人工势场法的重要问题,一种解决方法是改变力的方向,将斥力旋转固定的角度;另一种解决方法是加一个随机扰动,避免智能车产生局部最优值。

1.2.2碰到障碍物改进方法

由于引力远大于斥力,智能车有可能与障碍物产生碰撞。针对此问题,可以通过增大智能车受到的斥力避免碰撞,具体做法就是扩大斥力的作用范围[5];此外也可以通过修正引力函数解决,避免由于离目标位置太远导致引力过大。将引力场增加一个范围限定,如式(7)所示。

Uatt(q)=12ερ2(q,qgoal),ρ(q,qgoal)≤d*goald*goalερ(q,qgoal)-12ε(d*goal)2,ρ(q,qgoal)>d*goal (7)

式(7)中,d*goal 给定一个阈值限制智能车与目标位置间的距离,相应的引力负梯度也就是引力相应变成:

Fatt(q)=ε(qgoal-q),ρ(q,qgoal)≤d*goal

d*goalε(qgoal-q)ρ(q-qgoal),ρ(q,qgoal)>d*goal(8)endprint

1.2.3达不到目标点改进方法

当目标位置附近有障碍物时,斥力将远远大于引力,智能车辆会很难到达目标位置,可以通过引入一种新的斥力函数解决问题。考虑到目标及智能车距离的影响,新的斥力函数为:

Urep(q)=12η(1ρ(q,qobs)-1ρ\-0)2ρn(q,qgoal),if ρ(q,qobs)≤ρ\-00,if ρ(q,qobs)>ρ\-0 (9)

增加一个斥力函数后,智能车靠近目标时斥力场会增大,但是此时两者间距离逐渐减少,所以在一定程度上可以起到对斥力场的拖拽作用,从而避免了智能车与障碍物碰撞。

1.2.4无法避开动态障碍物改进方法[6]

为了使智能车能够同时避开静态障碍物与动态障碍物,可以在式(3)的斥力函数中增加速度因子,并且在验证过程中设置3种情况:障碍物从侧面靠近智能车、障碍物从侧面远离智能车、智能车超过障碍物。基于速度的改进算法成功避免了人工势场法存在的问题,并且能够规划出完整平滑的路径。

此外,还有很多人工势场改进方法:区域隔离法、高斯组合隶属函数法、人为随机波动引入法等[7]。

2智能优化算法

传统算法无法处理未知障碍物的避障问题,随着智能技术的日益发展,人们发现模糊逻辑算法、神经网络法、遗传算法等各种智能优化算法是可以解决智能车的避障问题的。智能优化算法是一种启发式优化算法,包括模糊逻辑算法、遗传算法、蚁群算法、粒子群算法、模拟退火算法、神经网络算法、禁忌搜索算法等。

2.1模糊逻辑算法

模糊逻辑(Fuzzy Logic,简称FL)算法是将模糊控制中感知与动作智能结合起来[8]。关键在于建立合适的模糊控制器,有3个主要特点:①用语言变量代替数学变量;②用模糊控制条件语句描述变量之间的关系;③用模糊算法描述复杂关系[9]。

模糊逻辑算法成功地处理了定位精度差的问题,但是不能够自主学习且缺乏灵活性,确定了模糊规则与隶属度后无法更改。

2.2神经网络法

神经网络(Neural Network,简称NN)是一种模仿生物结构与功能的模型,也是一种非线性数据建模工具[10]。神经网络算法在模糊规则与隶属度确定上具有较强灵活性。神经网络可以将传感器收集到的信息数据看作输入,智能车下一位置的运动方向看作输出,剔除冗余与对立样本,得到最终的样本集[11]。神经网络的学习规则简单、自主学习能力强,但若从传感器得到的数据不完整,神经网络就无法进行下去,而且泛化能力差,所以在避障规划应用上并不成功[12]。

2.3遗传算法

遗传算法(Genetic Algorithm,简称GA)是借鉴了达尔文进化论与孟德尔遗传学说的一种随机化搜索方法[13]。遗传算法使用的是适者生存原则,它通过复制或选择算子、交叉算子、变异算子等一步步进化后,输出当下最优值。遗传算法具有并行计算能力、群体搜索特性与可扩展性,一般不需要辅助信息,但是效率比其它智能优化算法低,而且在利用选择交叉算子时,会丢失一些优秀的基因片段,从而导致过早收敛。此外,在编码环境中会有较长的计算时间与很大的数据存储空间需求[14]。

2.4模糊逻辑算法、神經网络法与遗传算法结合

为了提高智能车避障路径规划效率,可将多种智能优化算法相结合,形成新的优化方法,从而实现高效率避障[1519]。

2.4.1模糊逻辑与遗传算法结合

经研究,可运用模糊逻辑与遗传算法两种智能算法实现智能车的安全避障。设计模糊控制器,如图1所示,将超声波传感器获取的目标方向与距离综合信息作为输入,智能车的速度、转角作为输出,分别建立速度与转角的模糊规则。因遗传算法能得到全局最优解且不需要辅助信息,可将避障模糊控制器完善到最优,从而实现避障优化[20]。

2.4.2模糊逻辑与神经网络结合

针对智能车避障过程中影响因素复杂及难以建立精确模型的问题,可采用超声波传感器与定位传感器获取智能车所处环境的输入信息,利用同时具有模糊逻辑与神经网络优点的神经网络记忆模糊控制规则,建立起多层BP神经网络。经过测试发现该算法具有很强适应性,能够帮助智能车完成安全避障[21]。

2.4.3神经网络与遗传算法结合

针对智能车避开动态障碍物,采用一种基于神经网络与遗传算法的避障结合方法[22],提出一种神经网络模型,通过简化编码方式并确定动态环境的适应度函数,利用遗传算法中复制或选择算子、交叉算子、变异算子等一步步进化后,寻找出最优解,使智能车在动态环境中也能完成有效避障。

3强化学习算法

强化学习是指智能车利用本身的传感器不断与环境相互作用来获得之前未知的环境知识,是一种仿生算法[23]。智能车感知到环境中的一个状态并根据上一次的状态转移过程获得一个奖赏,利用学习到的策略知识,将当前环境状态映射到自身动作,并作用于环境,环境产生一个状态转移过程,使得智能车感知到一个新状态,如此循环往复。

强化学习的4个要素为:策略、奖赏、值函数及非必需的环境模型[24]。①策略是从周围环境感知的形态到在此环境下可采用一种映射;②奖赏,也就是立即回报,表示智能车的眼前目标;③值函数是智能车获得的所有奖赏累加的期望值,可以看作智能车的长期回报,指明了智能车在长期运行过程中动作选择的标准;④环境模型给出了状态转移过程中详细的概率分布。在经典强化学习算法中,Sarsa算法与QLearning算法都能在有限时间内解决智能车避障问题,并给出最优解[25]。强化学习具有在线学习与自主学习的特点。

3.1基于神经网络的强化学习

强化学习在一定程度上会占用大量内存,而且要经过层层收敛,学习速度较慢。因此,神经网络的Qlearning算法可以改善存储空间不足问题,通过神经网络来逐渐逼近Q函数,在获得智能车的状态后不断更新Q值[26]。根据BP算法训练神经网络,最后使智能车完成避障[27]。endprint

3.2基于强化学习的HSIC算法

仿人智能控制(HSIC)是在功能与结构上模拟对人的控制,是接近于人的思维方式[28]。它可以实现在线特征辨识与特征记忆,并且达到分层递阶信息处理效果,广泛应用于启发式及直接推理逻辑方面。仿人智能控制的算法是:

u=Kpe+kKp∑n-1i=1em,i, e·e·>0∪ e=0∩e·≠0kKp∑n-1i=1em,i, e·e·<0∪ e·=0(10)

式(10)中,u为控制输出,Kp、k分别为比例系数与抑制系数,e为误差。

仿人智能控制可以实现多模态控制,因而能适用于有多性能指标要求的控制系统,并可应用于各种复杂控制过程。伴随着控制问题复杂性的不断增加,控制参数在不确定因素的影响下无法在运行过程中保持恒定,加入强化学习模块,有利于实现实时控制。基于强化学习的仿人智能控制器如图2所示。强化学习在环境作用下优化控制器参数包括以下6个步骤:①获取当前学习系统状态,随机初始化各参数;②调整状态值,计算调整后的Q值;③找到Q值中最大值;④计算相应的评价函数值;⑤若此时r=0,停止学习,更新Q,输出调整后的参数结果;⑥若此时r≠0,重复上述过程[29]。当得到最适合的控制器参数时,便停止学习优化参数,整个基于强化学习的仿人智能控制就此结束。

图2仿人智能控制器

4结语

人工势场法、智能优化算法与强化学习算法等都可在一定程度上解决智能车自主避障路径规划问题,每种算法都有其优缺点:人工势场法是模拟力场的算法,它计算简明、应用广泛,但会产生局部最优、达不到目标位置及碰到障碍物问题;遗传算法具有并行计算能力、群体搜索特性及可扩展性,一般不需要辅助信息,但它的效率比其它智能优化算法低;模糊逻辑算法成功处理了定位精度差的问题,但该算法不能够自主学习且缺乏灵活性,确定了模糊规则与隶属度后无法更改;神经网络算法学习规则简单、自主学习能力强,但很难应用于复杂多变的环境。此外智能水滴算法[30]、基于粒子群算法[31]等同样可以应用于智能车避障问题。任何一种有效的智能车避障系统均不能依靠单一方法进行路径规划,因此利用多种算法进行避障路径规划,是未来该领域的研究重点与难点。

参考文献参考文献:

[1]孙玉辉.面向自主驾驶的智能车辆导航平台技术研究[D].南京:东南大学,2014.

[2]FUJIMORI A,NIKIFORUK P N,GUPTA M M. Adaptive navigation of mobiie robots with obstacie avoidance[J]. IEEE Transactions on Robotics and Automation,1997,134:596601.

[3]SABER R O,MURRAY R M.Flocking with obstacle avoidance:cooperation with limited communication in mobile networks[C].Proc of IEEE Conf on Decision and Contr01.Piscataway:IEEE Press,2003:20222028.

[4]修彩靖,陈慧.基于改进人工势场法的无人驾驶车辆局部路径规划的研究[J].汽车工程,2013,39(9):808811.

[5]GP MIN,JH JEON,CL MIN. Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing[C]. IEEE International Symposium on Industrial Electronics,2001(3):15301535.

[6]杜,郭达,张新锋.智能车避障路径规划方法研究[J].汽车节能,2016(3):1722.

[7]刘琨,张永辉,任佳.基于改进人工势场法的无人船路径规划算法[J].海南大学学报:自然科学版,2016,34(2):99104.

[8]冯冬青,谢宋和.模糊智能控制[M].北京:化学工业出版社,1998.

[9]李鸿明.基于模糊控制的规则化描述方法研究[D].合肥:合肥工业大学,2010.

[10]郭琦,洪炳熔.基于人工神经网络实现智能机器人的避障轨迹控制[J].机器人,2002,24(6):508512.

[11]沈显庆,汪才杰.智能机器人的模糊神经网络避障算法[J].黑龙江科技学院学报,2012,22(6):613616.

[12]汪明磊.智能车辆自主导航中避障路径规划与跟踪控制研究[D].合肥:合肥工业大学,2013.

[13]SC YUN,V GANAPATHY,LO CHONG.Improved genetic algorithms based optimum path planning for mobile robot[J].International Conference on Control Automation Robotics & Vision,2011,20(1):15651570.

[14]周嘉,賈丽媛.改进的遗传算法在全局优化中的应用与研究[J].科学时代,2011(12):139140.

[15]YANG S X,LUO C. A neurai network approach to compiete coverage path pianning[C]. IEEE Transactions on Systems,Man and Cybernetics,2004(34):718724.endprint

[16]ZARATE L E,BECKER M,GARRIDO B D M,et al. An artificiai neurai network structure abie to obstacie avoidance behavior used in mobiie robots [C]. IEEE 28th Annuai Conference of the Industriai Eiectronics Society,2002(3):24572461.

[17]DEI H A R,MEDRANO M N,MARTIN D B B. A simple approach to robot navigation based on cooperative neurai networks[C]. IEEE 28th Annuai Conference of the Industriail Eiectronics Society,2002(3):24212426.

[18]WOONGGIE H,SEUNGMIN B,TAEYONG K. Genetic aigorithm based path pianning and dynamic obstacie avoidance of mobiie robots [C]. IEEE Internationai Conference on ComputationaiCybernetics and Simuiation,1997(3):27472751.

[19]SADATI N,TAHERI J. Genetic aigorithm in robot path pianning probiem in crisp and fuzzified environments[C]. IEEE Internationai Conference on Industriai Technoiogy,2002(1):1114.

[20]胡永仕,張阳.基于遗传模糊算法的智能车辆避障路径规划研究[J].福州大学学报:自然科学版,2015,43(2):219224.

[21]丁吉,段锁林,任富强,等.基于模糊规划器的轮式移动机器人避障研究[J].常州大学学报:自然科学版,2010,22(4):3438.

[22]陈华华,杜歆,顾伟康.基于神经网络和遗传算法的机器人动态避障路径规划[J].传感技术学报,2004(4):551555.

[23]KAELBLING L P,LITTMAN M L,MOORE A W.Reinforcement learning:a survey[J].Intelligence Research,1996,4(3):237285.

[24]胡裕靖.多智能体强化学习中的博弈、均衡和知识迁移[D].南京:南京大学,2015.

[25]刘忠,李海红,刘全.强化学习算法研究[J].计算机工程与设计, 2008,29(22):58055809.

[26]乔俊飞,侯占军,阮晓钢.基于神经网络的强化学习在避障中的应用[J].清华大学学报:自然科学版,2008,48(S2):17471750.

[27]唐鹏,李小坚.强化学习在移动机器人避障上的应用[J].科学家,2016,4(5):58.

[28]李祖枢.仿人智能控制[M].北京:国防工业出版社,2003.

[29]C YE,NC YUNG,D WANG.A fuzzy controller with supervised learning assisted reinforcement learning algorithm for obstacle avoidance[J]. Systems Man & Cybernetics Part B Cybernetics IEEE Transactions on,2003,33(1):1727.

[30]宋晓琳,潘鲁彬,曹昊天.基于改进智能水滴算法的汽车避障局部路径规划[J].汽车工程,2016,38(2):185191.

[31]黄神,孙德宝,秦元庆.基于粒子群算法的移动机器人路径规划[J].测控技术,2006,25(4):4950.

责任编辑(责任编辑:何丽)endprint

猜你喜欢
智能算法智能控制
神经网络智能算法在发电机主绝缘状态评估领域的应用
基于超像素的图像智能算法在矿物颗粒分割中的应用
从鸡群算法看群体智能算法的发展趋势
基于物联网的智能控制项目实践教学设计
应用型人才培养导向下智能控制教学改革探讨
浅谈开关式电梯IC卡系统及展望