摘 要：运用MATLAB建立车道障碍模型，通过各种算法，在MATLAB环境下设计车辆避障预警系统早已成为各大汽车厂商和研究所的核心，其规划路径的算法却大相径庭。通过对比3种常用算法在相同环境下路径规划，对其时间和空间上的特性进一步分析，得出规划算法是否最优。通过对比算法，可最大程度上减少路径规划的时间，得出最优的规划路径。最后通过对群智能算法的设置参数进行改进，从而优化传统算法，并通过设定函数验证论证结果。

TN966；TP202.7

A

10.16157/j.issn.0258-7998.166484

中文引用格式：唐焱，肖蓬勃，李发琴，等. 避障最优路径系统研究[J].电子技术应用，2017，43(11)：128-131，135.

英文引用格式：Tang Yan，Xiao Pengbo，Li Faqin，et al. Research of urban traffic obstacle avoidance and early warning system[J].Application of Electronic Technique，2017，43(11)：128-131，135.

0 引言

随着城市繁华区域车辆行驶密度的增加，行车过程车道上阻碍行车的各类移动、固定障碍物出现频数不断增多，严重影响行车速度，这是导致区域交通拥堵的主要因素之一。有关研究表明：驾驶者从观测、判断到驾驶动作的执行，以及车辆控制系统的反应，所需总时间在1.87 s以上，其中人员生理反应时间约占60%～70%[1]。因此在一定车速条件下，人工操作避障极易发生车辆与障碍物之间的碰撞，导致在车道障碍物较多的交通环境中难以实现自动驾驶。利用安装于车辆前方的超声波等探测系统进行路障信息采集，由车载电脑作数字化处理并及时反馈和视频预警[2]，将有效保证繁华市区行车安全和提高行车速度。

1 避障系统核心算法

1.1 人工势场法

车辆行驶速度受行驶目的地、车道障碍物两方面的因素影响。在繁华城区的行驶要求所有车辆能安全、迅速通过，从而对交通环境影响程度达到最小。人工势场法原理表明，动态物体在设定的空间按预期目的地运动时，存在两种物理势场的影响，即预期目的地吸引力和运动过程沿途障碍物的排斥力。运用多目标优化处理的方法，合理解决上述吸引和排斥的矛盾，能获得安全高效的运动方案[3]。

1.2 A*搜寻算法

A*搜寻算法是一种探测性的算法，其是一种在平面图形中求出最低成本的算法。规划合理的行车路径，减少拥堵，降低运营成本是A*搜寻算法应用的重要领域之一。A*算法基本思想是通过划分网格，计算起点到当前点的距离G和目标点到当前点的距离H的和，通过比较大小，把可能通过的点储存进open列表，而不会考虑的点则储存进closed列表。

1.3 粒子群算法(ACO)

粒子群算法（PSO）是一种群智能算法，其基本思想是模拟鸟群觅食的行为，通过鸟类之间的集体协作使群体飞行路线最优的算法[4]。在粒子群算法中，用无质量无体积的粒子作个体，并且为每个粒子规定一定的运动规则，从而使整个群体表现出一定的复杂特性。PSO概念简明，无需复杂的调整、收敛速度快，收敛准确、设置参数少、实现简单，且其数学基础相对薄弱，没有系统的数学基础。

1.4 矩阵实验室（MATLAB）

MATLAB是适用于数值计算、数据分析及可视化、算法开发等场合的高级技术计算语言，具有矩阵运算、绘制函数、数据图像等功能，本研究即在交互式环境中对算法进行编程，进行特定算法计算，实现动态仿真和数据输出。

2 路径规划算法原理

2.1 人工势场法原理

2.1.1 人工势场法函数

经典势能函数将运动物体（汽车）作为一个运动质点置于虚拟人工势场之中：运动终点与汽车相互作用产生的引力场用式(1)表示，障碍物与汽车相互作用产生的斥力场用式(2)表示[5-10]，即：

输入初始条件、汽车信息等参数，实时采集并更新车道环境参数，建立动态势场分布，在虚拟力的作用下完成路径规划。

2.1.2 人工势场法程序设计及仿真结果

基于人工市场法在MATLAB环境进行设计。

初始条件为：起始点为(10.5，10.5)，终点(1.5，1.5)。系统参数为：引力的增益系数k=20；斥力增益系数m=20；障碍影响距离P=1；障碍个数n=8；步长a=0.5；l=0.4；循环迭代次数j=200。

基于人工势场法设计的路径规划如图1，障碍物为实心圆圈，空心圆圈代表障碍物的大小是障碍物半径和障碍物的斥力之和，因此路径会进入障碍物范围；将信息数据输入式(1)、式(2)运算行车终点引力和障碍斥力总和，获得安全避障行驶的相关数据。

2.2 A*搜寻算法（a星算法）

路径优化的第一步是把地图简化成容易控制的搜索形式，即通过划分网格，把本文的地图划分为10×10的小网格。

2.2.1 A*算法的相关参数

(1)Open列表和Closed列表

①一个记录下所有被考虑来寻找最短路径方块的列表，被称为OPEN列表。

②一个记录下所有不会再考虑来寻找最短路径方块的列表，其中包括起点和边界，被称为Closed列表。

(2)路径增量

G值是从开始点到当前点所在的方块的移动量，即规定从开始点到相邻方块的移动量为1，其值会随着距离开始点越来越远而增大。

H值是从当前点靠目标点的移动量的估计值，在算法中常被称为探视，而估计值越接近真实值，最终的路线会更加精确。如果估计值停止作用，则规划的路径很大概率不是最短，通常使用的是“曼哈顿距离方法”，其仅仅是计算出当前点距离目标点剩下的方块总数，除去障碍物的总数。

2.2.2 A*搜寻算法的规划流程

(1)将地图划分为n×n的网格；

(2)计算G+H的和F；

(3)将方块提价到open列表中，本列表中有最小的F值，将此值称为S。

(4)将S从open列表中移除，添加到closed列表中；

(5)对于与S相邻的四周方块T可进行如下运算：

①如果T在closed列表中，删除，不考虑；

②如果T不在open列表中，计算其和值并添加进open列表中；

③如果T在open列表中，当使用当前生成的路径到达T时，检查F值是否更小，如果是，更新和值F并前进[11-12]。

2.2.3 A*星算法程序设计及仿真结果

基于A*星搜索算法在MATLAB中进行路径仿真，结果如图2，其中障碍物的布置同人工势场法，边界的限定为[1，11]。

如图2，其中黑色粗线条代表从起点到终点的直线距离，之后用于比较规划路径距离的长短，细线条为A*算法的实际路径。

2.3 粒子群算法（PSO算法）

2.3.1 粒子群算法参数的选取

粒子群算法主要确定如下各项参数[13-14]：

(1)粒子数目：粒子数越大，则粒子的搜索的空间范围越大，但相应的搜索所需时间也越大。一般的粒子数取20～40，由于本文的问题比较特殊，本文的粒子数目取200。

(2)粒子长度：大小决定于具体问题。

(3)粒子范围：大小取决于具体优化问题，且粒子的每一维度可设置不同的取值范围。

(4)粒子最大速率：大小决定了粒子在一次运行中可以移动的最大距离，如果不限定粒子的极限速率，粒子可能会在一次运行中超出搜索空间，而粒子最大速率的设定取决于粒子范围的最大宽度。

(5)学习因子（加速常数）：固定常数，一般取2。当没有惯性权重时，引入收敛因子，其取值也不一定取2，C1+C2=4.1时，收敛因子取0.729。部分实验研究表明两个因子相等且都等于0.2时效果更好，部分实验也表明C1大于C2且其和小于4时效果更好。

(6)算法终止条件：最大的迭代次数和在一定的误差范围内都可作为终止条件。

(7)适应度函数：目标函数或目标函数的变换。

2.3.2 粒子群算法的具体步骤

算法的流程可以描述如下：

(1)初始化一群粒子（种群规模为M），其中包括随机位置X和随机速度V；通常是在范围内随机产生。设定学习因子C1、C2，最大迭代次数Gmax。

(2)评价每个粒子的适应度；

(3)对每个粒子的适应值和其经过的历史最好位置Pbest作对比，如果较好，则选择其作为当前最优位置，即更新个体极值。

(4)对每个粒子的适应值和种群经过的历史最好位置Gbest作对比，如果较好，则选择其作为当前最优位置，即更新全局极值。

(5)根据式(1)、式(2)对粒子位置和速度进行更新，产生新的种群。

(6)如果迭代次数达到终止条件，则停止迭代，算法终止；未达到约束条件时转到步骤(2)，且粒子数加1。

根据上述步骤得出如图3所示流程图[15-16]。

2.3.3 仿真结果

基于PSO算法在MATLAB中进行路径仿真，结果如图4，其中障碍物的布置同人工势场法，边界的限定为[1，11]。

3 3种算法的特性对比

通过tic和t=toc得出算法运行时间，通过对坐标进行统计运算计算出距离的大小，结果如表1。

从表中可得出如下结论：

(1)地图相同的前提下，粒子群算法由于需要进行多次迭代，因此所用的时间相对于其他两种算法很大，而由其得到的路径非最短路径。

(2)地图相同的前提下，A*搜索算法仅进行其局部范围的最优规划，因此得出的路径不是最短，而其时间相对于粒子群算法也小很多。

(3)人工势场法在路径长短和时间上最优。

4 粒子群算法的改进

由于粒子群算法是群智能算法的一种，相对于其他两种算法虽然存在一定缺陷，但也是未来智能行业的一大支点，因此作为一种智能算法，提升空间很大。本文通过一种改进方法来提升粒子群算法的仿真时间，同时优化其路径。

通过对其各个程序的调用发现，仿真时间与粒子群算法自身处理程序有关，仿真时间占所有时间的15%，仿真时间主要是在调用算法的过程中，因此需要对算法参数进行改进。

采用中期随机的惯性权重，把w分为分段函数的判断形式进行粒子全局寻优，弥补了传统的后期随机的惯性权重的缺陷。提出在搜索中期采用（0.2，0.8）均匀分布的随机惯性权重，使用中期随机的惯性权重。

当it<0.2·MaxIt时，惯性权重取值：

式中，MaxIt为最大迭代次数，It为当前迭代次数，wmax=0.9为最大惯性权重，wmin=0.4为最小惯性权重。

中期随机的惯性权重具有一定优势，当前期搜索不到最优解时，在搜索中期时不至于陷入局部最优，因此减弱粒子群算法对迭代次数的依赖，弱化了最大迭代次数对算法的过度依赖。当最大迭代次数过大或过小时，对算法的早熟收敛和最优解的准确度的影响减弱。改善粒子群惯性权重的选择方式，减少搜索中期出现的过早收敛或者陷入早熟的陷阱中。因此中期随机即保证了随机搜索的能力，又保证了收敛速度。

决定粒子群算法的参数还有学习因子C1、C2，粒子群在搜索过程中，需要前段速度大，防止其过早成熟而陷入局部收敛，因此C1取大值，C2取小值。在搜索后期，由于其逐渐向全局最优靠近，因此需要弱化其全局搜索的能力，增强局部搜索的能力，从而减少仿真时间，因此C1取小值，C2取大值。

其分段公式如下：

其中，x=Itπ/MaxIt。当1≤It≤0.47MaxIt时，C1>C2；当0.47MaxIt≤It≤MaxIt时，C1<C2。

通过对惯性权重和学习因子参数进行改进，仿真时间为119.62 s，规划路径长度为12.55 m，在提升仿真时间和路径上有一定的效果。通过双重参数的调节，保证局部搜索和全局搜索能力的均衡，也保证自身认知和社会认知的均衡化。相比于传统固定参数和仅仅改变一种参数的结果，本仿真效果有很大的改善。

本文通过求Shubert函数的最小值对以上理论进行验证对比，选择Shubert函数的原因是由于其具有很多局部最优解，这里把多元多峰函数变成单元多峰函数进行其最小值的求解，通过此函数得出最小值的验证更能证明改进后的粒子群算法的效果，其具体数据如表2所示。从表中可看出，经过两种参数改进后的粒子群算法在收敛到极小值时的收敛速度更快、更准确。

5 结论

自动规划路径的核心是选取最优算法，在复杂地图中，智能算法不一定比普通搜索算法强，而是要通过具体的地图进行判断。当然智能算法是人类科技发展的方向，通过对其各项参数进行改进后得出的路径长度有了很大的提高，其路径通过不断迭代得出的结果非常理想。其他智能算法，如遗传算法[17]、蚁群算法[18]等也各具特性。

参考文献

[1] 吴初娜.驾驶人应激反应能力评估研究[D].西安：长安大学，2011：30-40.

[2] 胡爱军，王朝晖.汽车主动安全技术[J].机械设计与制造，2010，48(7)：97-99.

[3] 季荣涛，周献中，王慧平，等.基于Lyapunov法和势场法的对峙跟踪研究[J].火力与指挥控制，2016，54(4)：66-69.

[4] 许源.结合粒子群算法和改进人工势场法的移动机器人混合路径规划[D].杭州：浙江大学，2013.

[5] 钱森，訾斌.多起重协作吊装避障路径规划研究[J].机械设计与制造，2015(10)：260-263.

[6] 祝雪芬，涂刚毅.基于轨迹安全性评价的免疫遗传路径规划算法[J].计算机应用研究，2013，30(2)：354-356.

[7] 何海洋.工业机器人无碰轨迹规划算法研究[D].广州：华南理工大学，2014.

[8] 杨龙祥.基于反应式的人工势场发机器人路径规划[D].成都：西华大学，2014.

[9] 张煌辉.基于动态人工势场的路径规划研究与应用[D].长沙：长沙理工大学，2010.

[10] 刘秀松.车辆避障驾驶控制方法研究[J].计算机工程与应用，2012，48(2)：230-234.

[11] 邓顺平，张艳军，刘会平.一种基于威胁势场的A星路径规划算法[J].科技视界，2014，4(3)：6，22.

[12] 郭强.基于改进的A星算法和B样条函数的仿生机器鱼路径规划研究[D].天津：天津大学，2012.

[13] 张万绪，张向兰，李莹.基于改进粒子群算法的智能机器人路径规划[J].计算机应用，2014，34(2)：510-513.

[14] 吴斌.车辆路径问题的粒子群算法研究与应用[D].杭州：浙江工业大学，2008.

[15] 刘关俊.基于粒子群算法的移动机器人路径规划研究[D].长沙：中南大学，2007.

[16] 王亚春.移动机器人路径规划算法研究[D].天津：天津理工大学，2015.

[17] 禹建丽，成元洋之,Valeri.Kroumov.无人驾驶农用运输车路径规划研究[J].拖拉机与农用运输车，2002，29(4)：22-24.

[18] 卜新苹，苏虎，邹伟，等.基于复杂环境非均匀建模的蚁群路径规划[J].机器人，2016，38(3)：276-284.