基于分层PSO的智能车辆超车路径规划

尹 华，吴君华

（1.江苏农林职业技术学院，江苏 句容 212400；2.南京林业大学，江苏 南京 210037）

1 引言

弗吉尼亚理工大学的在自动驾驶方面的研究报告表明[1]，如今智能车辆的安全性和舒适性超过人类平均驾驶水平，未来智能车辆的应用将越来越广泛，智能车辆的研究需求越来越高。而超车问题是自动驾驶的重要环节，这里针对超车过程的路径规划展开研究。

在已有的路径规划方法中，著名的经典方法包括单元格分解法[2]，人工势场法[3]，道路图法[4]和子目标法[5]。经典方法能够生成路径规划，但是路径的评价函数与路径生成本身关联不紧密，需要研究人员根据实际情况调整路径规划的方案。相比而言，启发式方法能够将路径的评价指标同路径的生成过程紧密连接起来，其包括神经网络方法[6]，模糊逻辑[7]以及遗传算法[8]和粒子群算法[9]。当路径的适用环境改变时，可通过改变约束函数组或者目标函数生成新的规划路径。

超车换道的路径规划本质上可以转化为是一个带有约束的目标优化问题。由于车辆本身具有不同特性，道路约束，法规约束和安全等级等影响因素很多，因此没有限定的“最佳路径”是一个不精确的表达方式。但它可以集中体现在几个方面，例如安全性、超车路程和能量消耗等方面。

到目前为止，纯粹优化的方法并不能完美地解决智能车辆路径规划问题。有的耗时太长，有的不能计算出规划路径。因此，研究人员需要综合不同的方法，提高算法的可靠性。几位研究学者[10-12]已经探讨了采用分层结构来解决这一类问题的思路。在不同的层级中应用多种算法，不仅可有效地降低算法的复杂度，而且所得出的轨迹更加可靠。

针对智能车超车问题，提出了多层粒子群优化的路径规划方法。首先，深入分析了智能车辆超车变道过程中的各个影响因素，进而建立数学模型。其次，基于模型构造出粒子群优化方法需要的约束函数和优化目标。再次，针对粒子群优化方法存在的问题，设计分层结构提高初始粒子的准确性，并采用Pareto优先原则加速收敛过程。最后，通过CarSim和Matlab混合仿真验证了该方法优化路径的可行性。第二节通过分析各个影响要素建立双车道车辆超车模型，第三节构造了分层结构的路径规划粒子群优化方法，第四节介绍了CarSim和Matlab的仿真效果。最后一节总结全文并提出了几点展望。

2 双车道车辆超车模型

超车换道的基本动作流程共有五种[3]，超车准备，前超车过渡，超车实施，后超车过渡，超车结束阶段。通过分析超车换道的基本动作流程，得知超车准备中超车换道空间是超车规划中的关键，如图1所示。超车空间的确定需要考虑的安全、车辆、道路等基本要素，以及各个要素的相互约束关系。规划的路径不仅要符合车辆动力学的基础上，而且确保安全避开其他车辆，还能够满足实际道路的约束。在后面的讨论中，统一道路的坐标方向，其中前进方向设为X方向，侧向设为Y。

图1 超车换道空间示意图Fig.1 Schematic Diagram of Overtaking Lane Change

2.1 约束条件分析

车辆自身动力学约束在确保安全、平稳同时，车辆加速度波动越低，乘客的舒适性体验越高。

式中：—M1的质点在横向的加速度—M1和M2的质点处纵向速度；Vmax—道路限速；ɑy，max—车辆最大侧向加速度。

2.2 超车安全距离分析

超车车辆M1在行驶过程中，当因前方车辆M2速度低而采取超车换道行为时，两者可能发生的碰撞为斜向碰撞。保证两车不发生碰撞的条件[13]为：

式中：xM1(t)、x M2(t)—车辆M1、M2经过时间t的纵向位移；c—车辆M1的宽度；θ—t时刻车辆M1车身与车道线之间的夹角；t≤tɑdj为时间；tɑdj—车辆M1侧向转弯的时刻。

由可知，确保M1和M2不发生任何情况下的碰撞的最小安全距离Dmin为：

式中：(0)、(0)—换道开始时车辆M1和M2的纵向速度；(t)、(t)—换道过程中车辆M1和M2在t时刻的纵向加速度；η—时间。

3 分层粒子群的超车路径规划

多目标粒子群优化的基础思想来源于单目标粒子群优化方法，两者都关心的核心问题是初值和更新算法。

3.1 单目标粒子群优化

PSO算法首先由文献［14］提出来解决单目标优化问题。假设维数为N的搜索空间D⊂RN中，第i个粒子的位置和速度分别为xi=(xi1，xi2，…，xiN)∈D和vi=(vi1，vi2，…，viN)∈D。根据两个因素，激励粒子更新位置，并朝全局最优值收敛的因素有两个：（1）该粒子本身最优位置（Pb）和（2）全体粒子群的最佳位置（Gb）。第一项为局部极值，表示为Pbi(t)=[Pbi1(t)，Pbi2(t)，…，PbiN(t)第二项为全局极值，并表示为Gb(t)=[Gb1(t)，Gb2(t)，…，GbN(t)在第t+1次搜索中，速度和位置的更新关系为：

式中：w—惯性重量；c1、c2—两个非负常数，通称为加速因子；r1、r2—［0，1］中的随机数。

基本的PSO算法只能解决连续解空间的单目标优化问题，并且算法本身收敛比较慢。因此，基本粒子群算法不适用于解决这里的问题。针对上述两个问题，设计多层结构，通过在不同的层级中单独解决问题，从而实现多目标粒子群快速优化，最终完成超车路径规划的任务。

3.2 多层路径规划设计

为实现路径规划的目的，对实际问题分解为三个层面的小问题。第一层主要是确定障碍的边界。对M2而言，根据车辆的危险等级系数ζ，对超车最小车距ζDmin适当调整。对道路而言，根据车辆自身的宽度c确定，确定边界宽度。应用三角分解法快速得到智能汽车安全运行的空间。第二层是采用Dijkstra算法在第一层的得到的空间中获取一条轨迹。第三层则是采用基于Pareto原则加速的多目标PSO算法，寻找最优路径。具体处理步骤，如图2所示。

图2 多层PSO路径规划的结构Fig.2 Structure of Multi-Layer PSO Path Planning

3.2.1 三角分解

单元分解法是路径规划中常用的方法[10]，其具体是将可活动空间划分为相同几何类型的多边形区域。典型的形状主要有梯形、三角形、多边形和矩形。该文献研究了单元分解中不同几何类型的实现路径规划的效果和计算复杂度，指出三角分解方法具有高鲁棒性，低复杂度，并且可行路径比例高等优点。因此在第一层应用三角分解法取得一个可行路径。

通常三角分解法的输入为可行空间C［28］，而输出为三角形单元集合C={c1，c2，…cm}和各个单元相临边的集合。与一般的静态路径规划不同，超车变道路径规划的三角分解与所规划路径具有耦合关系，虚线的M1是指最终达到的位置。具体，如图3所示。

图3 规划路径与三角分解方法耦合Fig.3 Coupling of Planning Path and Triangulation Method

3.2.2 Dijkstra算法

Dijkstra算法的核心思想[29]是根据三角分解的结果，规划出M1经历的所有的相连三角单元，在每三角单元中选取距离最近两个点（也即是边的中点）作为轨迹，各点连接起来作为总体的轨迹。

3.2.3 基于约束的多目标PSO

前文已经假设，每一个粒子的状态就代表了一条路径。第三层的主要目标就是通过设计PSO算法，在迭代更新中，求出在约束条件下目标函数的最优值。通过分析双车道车辆超车模型，提出一种基于模型约束的多目标PSO。关于约束和算法的详情说明在第四节中。

3.3 多目标粒子群算法

多目标粒子群的基本要素也是粒子空间和目标函数。与单目标粒子群算法的不同之处有两点，第一是考虑约束条件。实际上，通过超车模型的分析得出的约束有多种类型，比如边界约束，不可以作为目标函数进行优化，只能单独在粒子状态更新中作为零和条件，避免规划的路径出现在边界以外。第二是需要优化的目标函数不仅有多个，而且在不同阶段之间还要变化。

3.3.1 搜索空间

假定车辆前进的速度是保持不变的，那么在每一个时刻核心的控制因素就是转角。于是可以考虑每一个粒子是一组不同时刻的转角序列θ={θ1，θ2，…θN}。一个粒子中，每一个元素θi，就可以确定当前时刻的车辆速度：

进而通过速度的积分求解路径各个位置的坐标可以表达为：

式中：Δt—时刻间隔；—M1的速度。由上可知，这样的粒子定义可以完全表达路径。

3.3.2 目标函数

对智能车辆而言，规划路径距离车辆和道路边界的距离越远，车辆就越安全，出现意外发生故障的概率也就越低。在此基础上，还需要追求规划路径具有最短的路径长度，从而提高行车效率，缩短车辆占用超车道路的时间。此外，在考虑外部环境意外，还需要提高乘客的体验，规划的路径加速度需要满足平滑性的要求，越平稳越好。综合上述考虑，将安全性、路径长度和舒适性作为优化的目标函数。

为了避免矩形模型的复杂计算过程，将障碍车模型构造为椭圆形状，如图4所示。这样计算过程可以通过椭圆的性质得以简化。根据超车模型，椭圆的长边距为安全距离ζDmin。根据道路安全法规，M1应该在与M2不同的车道超车，则短边距为M2与车道边的宽度1/2(H-c)。在超车过渡时间段内，t∈(t0，t0+tɑdj)，其中，超车起始时刻满足的条件为-ζDmin，M1与M2平行的时刻满足条件为＜ε，ε为给定的一个小正数。轨迹的避障目标函数为：

图4 M2的椭圆距离模型Fig.4 Elliptical Distance Model of M2

其中，椭圆焦点的位置分别M2平行质心的(-，0)和(-d2，0)处，且M2的位置为：

路径的长度与时刻有关系，那么对于超车结束过渡阶段t∈(t0+tɑdj，NΔt)：

3.3.3 约束函数

如图5所示，在分析三角分解方法给出的可行轨迹空间，得到粒子空间的上边界序列UB和下边界序列LB。

图5 路径的上下边界Fig.5 Upper and Lower Boundaries of the Path

另外从安全分析，在t∈(t0+tɑdj，t1)时，强制要求：

才进入超车结束过渡阶段。

3.4 生成规划轨迹

一般的多目标优化方案通常采用各个目标加权的线性组合方式，但是这样的方式常常使目标优化的结果很大程度依赖于加权系数，造成计算的优化结果与真实的最优存在很大差别。而在这里的优化中，采用帕累托最优方法，通过计算违约函数确定方案的优先顺序。违约函数为：

粒子群的进化公式为：

其中，局部优化参数c0∈[0.1，0.5]，收敛底数γ∈(0，1)，rand(LB，UB)为随机参数，全局优化参数c2∈[0.1，0.7]，Gb(t)为当前粒子群中优先级最高的粒子状态。

4 路径跟踪仿真模型

利用CarSim的模型检验这里方法获得的优化路径。在Car-Sim8.10软件中构建模型，详细参数，如表1所示。利用Matlab2014a的Simulink将模型导入，同时在Simulink控制器模块编写分层PSO算法生成路径和目标函数的代码，如图6所示。使用Simulink的函数模块和常数生成器为CarSim的Simulink模块提供M1、M2速度和M1的转角序列。CarSim模块计算的位移等情况，通过示波器显示出来。其中，M1、M2位置和转动角度作为控制器的输入送入Simulink控制器中，通过目标函数判断当前路径的优先级，并生成新的路径进入下一轮循环。这样的循环一直持续到全部粒子都收敛进入稳定状态。

表1 CarSim详细参数Tab.1 The Detailed Parameters of CarSim

图6 Simulink联合仿真平台Fig.6 The Co-Simulation Platform for Simulink

在双车道建模分析过程中，道路通畅，宽度设为3m，附着系数μ=0.75。基于对安全距离的约束，假设两辆车均为匀速行驶，M1速度为72km/h，拐弯不削减路径上的速度。M2速度为50km/h，并且在超车过程中车辆方向基本在纵向。反映了优化后的路径下，M1超车的情况，如图7、图8所示。

图7 换道超车路径仿真图Fig.7 Simulation Diagram of Lane Change Overtaking Path

图8 几处关键节点的超车路径Fig.8 The Overtaking Path of Several Key Nodes

为了表达清楚，所有图片都在Y方向2m处绘制虚线表示行车道和超车道的分界线。整体过程的轨迹变化图，如图7所示。图中一种框和另一种框位置重合的部分是处于不同的时间，这一点在图8的三张图中表现更加清晰。图8为在几处关键时间点上的超车情况图。图8（a）为超车过渡阶段，图8（b）为超车并行阶段，图8（c）为超车后过渡阶段。

角度变化，如图9所示。Y方向的加速度，其变化幅度最大为±3m/s2＜0.67μg，车辆最大转角0.3rad，符合车辆动力学，能够为乘客提供一个舒适的乘车环境，如图10所示。

图9 优化路径的转角Fig.9 Corner of the Optimized Path

图10 优化路径的Y方向加速度Fig.10 Acceleration of the Y-Direction of the Optimized Path

仿真结果表明，通过设计多层粒子群，采用多目标优化的方法得到的规划路径是可行的，智能车辆可以在符合运动学，动力学条件下，安全的完成超车任务。

5 结束语

针对自动驾驶智能车辆超车问题，采用多层粒子群加速优化方法规划出最优路径。首先，通过对驾驶员超车操作的分析建立超车换道模型，从而得到优化问题的约束条件和目标函数。其次，如果直接采用传统的粒子群算法，由于初始条件对算法具有一定的影响，存在计算量大，容易陷入局部极小的问题。对此，设计分层结构，采用三角分解和Dijkstras算法确定车辆的可运行空间，为粒子群算法提供了较好的初始条件。在研究的背景中，涉及优化的问题和约束条件比较多，一定程度上提高了算法的复杂程度。针对该问题，通过引入Parote优先规则，可以加快算法的计算速度，降低算法的计算复杂度。最后，Simulink仿真结果表明，粒子群算法计算出的路径能够使智能车辆安全、稳定、高效、舒适地完成超车过程，满足实际需求。

此外，主要考虑了超车车辆和被超车车辆的超车变道方案，理论分析和仿真部分是在比较理想的情况下进行的。下一步，可以讨论更加复杂的情况，例如障碍车辆有多个，超车过程需要应急控制，路况不够理想等问题。