宋晓琳,潘鲁彬,曹昊天

(湖南大学，汽车车身先进设计制造国家重点实验室，长沙 410082)

2016030

基于改进智能水滴算法的汽车避障局部路径规划*

宋晓琳,潘鲁彬,曹昊天

(湖南大学，汽车车身先进设计制造国家重点实验室，长沙 410082)

智能水滴算法是群落智能算法的一种新型算法，它模拟水流与泥沙相互作用而形成水道的机制，可应用于计算科学领域中求解复杂问题。针对原智能水滴算法在求解路径规划问题时，因启发性不足而导致所规划的路径不理想的缺陷，通过改变原算法的概率选择和更新机制，提出了改进的智能水滴算法。与其他算法对比仿真的结果表明，该改进算法的求解能力明显提高。运用于汽车局部路径规划的结果表明，汽车在障碍规避过程中横摆角速度和侧向加速度值均符合稳定性要求，进一步验证了该算法的可行性。

智能水滴算法；智能群落算法；路径规划；避障

前言

根据各种路径规划算法基本原理与时序，目前主要的路径规划算法可归纳为传统算法和智能算法两类[1]。传统的路径规划算法有人工势场法，模糊逻辑算法，启发式搜索算法等。人工势场法[2]是模拟力场的算法，其优点是所规划的路径平滑，但存在容易陷入局部最优解的问题。模糊逻辑算法[3]，其模糊规则的归纳和在线调整比较困难，应变性差。启发类的A*算法[4]在复杂的环境中能够快速地规划出路径，但所规划的路径不很理想。另外，在智能汽车的局部路径规划领域中，弹绳算法[5-6]能够规划出面向公路环境的理想路径，但模型描述比较复杂。智能算法主要有神经网络算法、遗传算法和群智能算法等。神经网络算法[7]是一种学习能力强的优秀算法，但较难描述复杂多变的环境。遗传算法[8]是模拟达尔文生物进化论的自然选择和遗传学机理的计算模型，其优点是易于与其他算法结合，发挥其迭代的优势，但实时性差。群智能算法[9]是一种结合概率选择和启发搜索的新型仿生算法，具有良好的自组织性和鲁棒性，且对复杂问题的适应性较强，已受到越来越多学者们的重视。

智能水滴算法(IWD)[10]是由Hamed Shah Hosseini学者提出的一种新型群智能算法，它模拟水流与泥沙相互作用而形成水道的原理，可应用在计算科学领域中复杂问题的求解。该算法已被成功应用在旅行商问题(TSP)[10]、多重背包问题(MKP)[11]和车辆路径问题(VRP)[12]等问题中。但对路径规划问题，由于原算法的启发性不足，导致所规划的路径不理想。于是，本文中旨在对原算法进行改进，并验证其在路径规划领域中的有效性与可行性。

1 智能水滴算法基本原理

在自然界中，水流对地面的冲刷作用会在地面形成一条能够绕开障碍物并成功到达某低势地点的沟壑。水流可看作由单位水滴组成的群体，而且每个水滴都带有速度变量属性和泥沙杂质成分。研究发现，当水滴流经某区域时，水滴更可能选择含泥沙量少的河床经过，如此在重力的作用下，水滴将获得更大的速度增量，冲刷掉更多的泥沙。如图1所示，当两个属性相同的水滴分别流经区域(a)与区域(b)时，图1(b)中的水滴将获得更大的速度增量，带走更多的泥沙。

在抽象的模型中，水滴按照离散步骤运动，并含有两个属性：运动速度veliwd与泥沙含量soiliwd。假设水滴的当前位置为i，在运动到下一位置j的过程中，将发生以下变化。

(1) 智能水滴在选择路径时会倾向于选择泥沙量更少的路径，为此以p(i,j)表示智能水滴在位置i选择j作为下一位置的概率，它与路径(i,j)的泥沙量soil(i,j)成反比关系，选择概率为

(1)

(2)

式中：ε为极小正实数，且

(3)

(2) 水滴的速度增量Δveliwd非线性反比于路径(i,j)的泥沙量soil(i,j)，即

(4)

式中：av，bv和cv是用户自定义的系数。

(3) 水滴冲刷带离的泥沙量Δsoiliwd非线性反比于水滴经过路径(i,j)所需的时间变量time(i,j;veliwd)，并且与路径(i,j)的泥沙减少量Δsoil(i,j)相等，即

Δsoil(i,j)=Δsoiliwd

(5)

(6)

式中：as，bs和cs为用户自定义的系数。另外，time(i,j;veliwd)水滴从位置i到位置j所需时间为

(7)

式中HUD(i,j)为关于路段(i,j)的启发函数。

(4) 当水滴从位置i到达位置j后，路段(i,j)所含泥沙量将被更新，以对其他水滴的路径规划形成反馈机制。泥沙量局部更新为

soil(i,j)=(1-ρ)·soil(i,j)-ρ·Δsoil(i,j)

(8)

式中ρ为0～1之间的系数。

(5) 当所有水滴按照步骤(1)～(4)从初始点到达目标点后，每个水滴都有着不同的路径解TIWD，然后根据评价函数q(·)可以选择出迭代最优的路径解TIB为

(9)

式中arg(·)函数用于获得最优解的元素。

当前最优路径解TTB依据式(10)进行最优路径解的更新。

(10)

(6) 为提高下一群水滴搜索最优路径的能力，需要形成如式(11)所示的反馈机制对迭代最优解TIB的路径进行全局泥沙量的更新。

(11)

式中：ρ为0～1之间的更新系数；NIB为路径的节点数。

2 智能水滴算法的改进

针对原算法规划路径时存在启发性不足的问题，本文中提出了以下几方面的改进。

2.1 变量更换

为避免原算法在迭代求解过程中泥沙量正负乱秩的不良现象，改进算法以相对地平面缺失的泥沙量(负值)为变量，从而提高算法的收敛特性。

2.2 概率选择策略

改进后概率选择策略为

(12)

(13)

式中:Eta(i,j)为位置j距目的地的距离；Q为与距离有关的启发强度指数。原算法的选择策略只与泥沙量soil(i,j)成负相关；而改进算法的选择策略与相对地平面缺少的泥沙量成正相关，与Eta(i,j)成负相关，这样可以提高算法的收敛性与启发性。

2.3更新机制

将式(7)中关于路段(i,j)的启发函数HUD(i,j)用Eta(i,j)替代，这样可对更优路段的泥沙量进行有效的更新，即

(14)

泥沙量的局部更新与全局更新分别为

soil(i,j)=soil(i,j)-ρ·Δsoil(i,j)

(15)

(16)

改进算法实现路径规划的流程如图2所示。

3 算法的仿真对比实验

为验证智能水滴算法在路径规划应用中的有效性，本文中建立一个模拟环境，运用该算法完成路径规划，并与原智能水滴算法、蚁群算法、人工鱼群算法和粒子群算法进行对比分析。

3.1 环境建模

环境建模的方法可概括为栅格法、几何特征法和拓扑法3种表示法[13]。其中，栅格地图直接与环境信息对应，容易创建与维护，既可用于全局路径规划也可用于局部路径规划[14]，是目前最常用的一种环境地图。所以本算法也采用栅格地图的方法表达环境信息。在自定义的25×25的二维栅格环境模型中，单位栅格的边长为4m×4m，如图3所示，黑色区域表示的是实际大小的静止障碍物，其余白色空间是可以安全行驶的区域。另外，根据汽车外形尺寸将障碍物做相应的膨胀处理，并将汽车视为质心处的一点，以便于安全地规划路径。

3.2 初始参数设置

原水滴算法(IWD)[15]、蚁群优化算法(ACO)[16]、粒子群优化算法(PSO)[17]和鱼群优化算法(AFSA)[18]的内容皆由编程实现。应用经验试算法得到的改进水滴算法(IWD-P)和原水滴算法(IWD)的初始参数如表1所示。蚁群优化算法和鱼群优化算法的初始参数则分别如表2和表3所示。

3.3 路径光顺

基于栅格环境模型规划出的路径难免出现曲折变向的现象，即路径曲线的1阶导数不连续，这显然不满足汽车高速运动下在动力学与运动学方面对安全稳定性的要求。所以，算法还需要对以上所规划的路径进行光顺。由于B样条曲线[19]的初点和末点保持不变，因此，采用此方法对原生路径进行处理，以获得光滑路径。

3.4 有效性分析

仿真实验的软件平台是MATLAB R2014a，硬件平台是Win7@64bit+core2@2.53GHz+RAM@4G。各算法仿真结果路径如图3所示，将各算法分别运行32次，统计各算法的路径长度(其中，剔除最长路径和最短路径)和平均耗时，结果如表4所示。

表1 两种水滴算法的参数

表2 蚁群优化算法的参数

表3 鱼群优化算法的参数

由图3和表4可知，IWD算法无论在规划的路径还是实时性方面都很不理想；PSO和AFSA算法虽然实时性表现出明显的优势，但规划出的路径不光顺且长度较长；IWD-P和ACO的路径都较平顺且距离最短，但从表4中方差对比可知，IWD-P算法的实时性与ACO的相差不大，但IWD-P的方差值明显要小于ACO算法，说明IWD-P算法稳定性好。

名称路径长度/m平均值最小值方差平均用时/s原水滴算法315 11238 40667 8712 09改进水滴算法153 62152 170 655 63蚁群算法158 14152 174 175 74粒子群算法164 55159 203 680 35鱼群算法171 05162 511 920 56

4 在汽车避障局部路径规划中的仿真

为说明改进水滴算法应用的可行性，将算法用于无人驾驶汽车的局部路径规划中。长度为260m、宽度为7m的平直同向双车道可表达为65×6的二维栅格模型，单位栅格的边长为4m×1.17m。为验证算法对速度的鲁棒性，仿真时，无人驾驶汽车分别以中速20m/s和高速30m/s行驶。当汽车探测到前方40m内有障碍时，系统将触发局部路径规划程序以0.5s的时间间隔实时探测周边环境，并据此进行路径规划。其中，算法的参数按表5设置。实验场景主要分为以下3种。

4.1 对静态障碍车的超车仿真

假设无人驾驶汽车分别以20和30m/s恒速在车道行驶，障碍汽车在无人驾驶汽车初始位置的前方40m处固定不动，场景如图4(a)所示。用改进水滴算法规划的路径动态显示如图4(b)与图4(c)所示，其中t0～t7各处的白色矩形分别表示无人驾驶汽车每隔0.5s时间的位置，黑色矩形表示障碍汽车。

表5 改进水滴算法的参数

为进一步研究汽车在跟随路径过程中的运动学特性，基于PRESCAN平台搭建了环境模型，并将所规划的路径数据用PRESCAN的动力学模型进行仿真，结果如图5所示。图5(a)中的虚线是汽车跟随目标路径过程中所产生的运动轨迹，可见在两种速度模式下，汽车的跟随效果良好。图5(b)与图5(c)分别描述汽车运动过程中的侧向加速度与横摆角速度的变化情况，由图可知，在静态避障过程中汽车侧向加速度的峰值均低于0.65m/s2，横摆角速度峰值低于17(°)/s。因此，在此路况下，改进的水滴算法所规划出的局部路径能够保证汽车稳定行驶。

4.2 对动态障碍车的超车仿真

假设无人驾驶汽车的车速分别以20和30m/s恒速在车道行驶，障碍汽车以16m/s恒速在同一车道上同向行驶，障碍汽车的初始位置在无人驾驶汽车初始位置的正前方40m处，场景如图6(a)所示。改进水滴算法规划出的路径动态显示如图6(b)与图6(c)所示，图6(b)中t0～t17各处的白色与黑色矩形分别表示无人驾驶汽车与障碍汽车每隔0.5s时间的位置；图6(c)中t0～t9各处的白色矩形与黑色矩阵分别表示无人驾驶汽车与障碍汽车每隔0.5s时间的位置。

图7为汽车动态超车的动力学特性。图7(a)中的虚线是汽车跟随目标路径过程中所产生的运动轨迹，在两种速度模式下，汽车的跟随效果良好。图7(b)与图7(c)分别描述汽车运动过程中的侧向加速度与横摆角速度的变化情况，由图可知，在动态避障过程中汽车侧向加速度的峰值均低于0.65m/s2，横摆角速度峰值低于18(°)/s。因此，在此路况下，本算法所规划出的局部路径能够保证汽车稳定行驶。

4.3 对动态障碍车的避障仿真

假设无人驾驶汽车以20m/s恒速向前行驶，障碍汽车在无人驾驶汽车初始位置的后方16m处以24m/s恒速向前方行驶，场景如图8(a)所示。当障碍车对无人驾驶汽车超车时突然出现车道偏离现象，避障路径动态显示如图8(b)所示，其中t0～t7各处的白色矩形分别表示无人驾驶汽车每隔0.5s时间的位置，t0～t7各处的黑色矩形分别表示障碍汽车每隔0.5s时间的位置。

图9为汽车动态避障的动力学特性。图9(a)中的虚线是汽车跟随目标路径过程中所产生的运动轨迹，可见汽车的跟随效果良好。图9(b)与图9(c)分别描述汽车运动过程中的侧向加速度与横摆角速度的变化情况，由图可知，在动态避障过程中汽车侧向加速度的峰值低于0.6m/s2，横摆角速度峰值低于16(°)/s。因此，在此路况下，本算法所规划出的局部路径能够保证汽车稳定行驶。

5 结论

针对原智能水滴算法规划路径时启发性不足的问题，分别对原算法的概率选择策略和更新机制做了改进。通过与原算法和其他群落算法对比分析，结果表明：改进的水滴算法的求解能力显著提高，且所规划的路径接近最优。

将改进的智能水滴算法用于汽车超车和避障局部路径规划中，并在两种车速、3种交通场景下分别进行了仿真。结果表明：汽车按照规划出的路径行驶能够实现安全避障，并且在运动过程中其侧向加速度和横摆角速度值均符合稳定性要求，说明采用改进的智能水滴算法求解汽车局部路径规划问题是可行的。

今后将对比研究不同环境模型下，本算法规划路径效果的差异，并将该算法应用于更复杂的路径规划问题，以求得到更好的效果。

致谢：感谢上海天欧TNO公司为本研究提供Prescan仿真软件的支持。

[1] 张颖,吴成东,原宝龙.机器人路径规划方法综述[J].控制工程,2008(z1):152-155.

[2] KHATIB O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research,1986,5(1):90-98.

[3] WANG M, LIU J N K. Fuzzy Logic Based Robot Path Planning in Unknown Environment[C]. Machine Learning and Cybernetics. Proceedings of 2005 International Conference on. IEEE,2005,2:813-818.

[4] YAO J, LIN C, XIE X, et al. Path Planning for Virtual Human Motion Using Improved A*Star Algorithm[C]. Information Technology: New Generations (ITNG), 2010 Seventh International Conference on. IEEE,2010:1154-1158.

[5] SONG X, CAO H, HUANG J. Influencing Factors Research on Vehicle Path Planning Based on Elastic Bands for Collision Avoidance[J]. SAE International Journal of Passenger Cars-electronic and Electrical Systems,2012,5(2):625-637.

[6] SONG X, CAO H, HUANG J. Vehicle Path Planning in Various Driving Situations Based on the Elastic Band Theory for Highway Collision Avoidance[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering,2013,227(12):1706-1722.

[7] JUNG I K, HONG K B, HONG S K, et al. Path Planning of Mobile Robot Using Neural Network[C]. Industrial Electronics. ISIE’99. Proceedings of the IEEE International Symposium on. IEEE,1999,3:979-983.

[8] HU Y, YANG S X. A Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot[C]. Robotics and Automation. Proceedings. ICRA’04. 2004 IEEE International Conference on. IEEE,2004,5:4350-4355.

[9] 冯翔,马美怡,施尹,等.基于社会群体搜索算法的机器人路径规划[J].计算机研究与发展,2013,50(12).

[10] SHAH-HOSSEINI H. Problem Solving by Intelligent Water Drops[C]. Evolutionary Computation,2007. CEC 2007.IEEE.

[11] SHAH-HOSSEINI H. Intelligent Water Drops Algorithm: A New Optimization Method for Solving the Multiple Knapsack Problem[J]. International Journal of Intelligent Computing and Cybernetics,2008,1(2):193-212.

[12] KAMKAR I, AKBARZADEH-T M R, YAGHOOBI M. Intelligent Water Drops a New Optimization Algorithm for Solving the Vehicle Routing Problem[C]. Systems Man and Cybernetics (SMC),2010 IEEE International Conference on. IEEE,2010:4142-4146.

[13] 时丕芳,赵永瑞.移动机器人行走路径环境建模方法综述与解析[J].现代制造技术与装备,2010(1):1-2.

[14] 马兆青,袁曾任.基于栅格方法的移动机器人实时导航和避障[J].机器人,1996,18(6):344-348.

[15] DUAN H, LIU S, WU J. Novel Intelligent Water Drops Optimization Approach to Single UCAV Smooth Trajectory Planning[J]. Aerospace Science and Technology,2009,13(8):442-449.

[16] HSIAO Y T, CHUANG C L, CHIEN C C. Ant Colony Optimization for Best Path Planning[C]. Communications and Information Technology. ISCIT 2004.IEEE International Symposium on. IEEE,2004,1:109-113.

[17] 宫金超,李晓明.基于粒子群优化算法的小型足球机器人路径规划[J].机电工程,2010(12):116-120.

[18] 徐晓晴,朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报,2012,40(8).

[19] 宋金泽,戴斌,单恩忠,等.一种改进的 RRT 路径规划算法[J].电子学报,2010,38(2A):225-228.

Local Path Planning for Vehicle Obstacle Avoidance Based onImproved Intelligent Water Drops Algorithm

Song Xiaolin, Pan Lubin & Cao Haotian

HunanUniversity,StateKeyLaboratoryofAdvancedDesignandManufacturingforVehicleBody,Changsha410082

Intelligent water drops (IWD) algorithm is a new swarm intelligent algorithm. It simulates the mechanism of water path forming by the interaction between water and soil, suitable for solving the complicated problems in computation science field. In view of the inadequate heuristic nature of original IWD algorithm, resulting in its incapacity to get an ideal path in solving routing problem, an improved IWD algorithm is proposed through the modifications of probability selection and updating mechanism in original IWD algorithm. The results of simulation on the improved IWD algorithm with comparison to other algorithms indicate that the improved IWD algorithm has its problem solving capability enhanced, and the results of its application to local path planning show that both the yaw rate and lateral acceleration of vehicle meet the requirements of stability in its obstacle avoidance maneuver, further verifying the feasibility of improved algorithm.

intelligent water drops algorithm; intelligent swarm algorithm; path planning; obstacle avoidance

*国家自然科学基金(51175159)、湖南省科技计划项目(2013WK3024)和湖南省研究生科研创新项目(CX2013B146)资助。

原稿收到日期为2014年4月9日，修改稿收到日期为2014年12月10日。