基于改进人工鱼群算法的车辆轨迹规划方法

袁 娜,史 昕,赵祥模

(长安大学 信息工程学院,西安 710064)(*通信作者电子邮箱1782709730@qq.com)

0 引言

近年来,车联网的研究热潮推动了交通行业的推陈革新,现代交通逐渐向高效、安全、环保方向发展。文献[1]中提出轨迹规划作为车联网环境中的一项重要技术,被广泛地应用到智能车的轨迹选择、智能机器人等领域。文献[2]中提出一种对于交通路网中车辆轨迹规划算法是建立在非线性预测算法的基础上的观点。文献[3]中应用模糊逻辑控制方法来提高“智能绳”系统,实现区分小的非自愿力量和预定的航行运动,利用智能手机摄像头作为机器人视觉,完成导盲犬机器人的跟踪、导航和避障。文献[4]中提出了一种基于向前预测的局部路径规划算法,在不依赖全局定位的情况下实现规划时间的一致性,同时用通行区域取代原有不具有宽度的路径规划进行避障分析。文献[5]中提出了一种利用时间状态控制形式的车辆的新轨迹控制方法,并进行了旋转和扩张坐标变换,进而实现任意期望的曲线轨迹的控制方法。文献[6]中利用时间尺度变换和精确的线性化设计一个铰接式车辆的轨迹跟踪控制器，该控制器沿着任意轨迹运动,实现车辆的轨迹跟踪。文献[7]中根据车辆换道时的期望横摆角、横摆角速度和横摆角加速度,利用车辆侧向动力学模型,提出了一种弯道上车辆换道轨迹的规划方法。文献[8]中提出一种根据泊车终点环境障碍约束、泊车终点位置约束等,以泊车终点车辆与车位夹角最小为目标建立多约束的车辆泊车轨迹函数。文献[9]中基于弹性带理论的轨迹规划方法,提出了一种自主车辆紧急机动的轨迹规划方法。文献[10]中提出了一种最大最小萤光素值人工萤火虫算法,通过对荧光素的变化范围加以限定,给出最大最小萤光素值范围,从而避免算法陷入局部最优。文献[11]中在人工鱼群算法的寻优策略上提出了适时调整自身视野和步长的优化改进,对鱼群的收敛速度和局部极值方面均有所提高。关于车辆轨迹规划的文献研究在车辆轨迹规划中对周围车辆的信息利用较少,导致为车辆规划的轨迹并不适用于道路车辆数目较多的场景。在多车轨迹融合的场景,车辆很容易陷入自身轨迹最优,而个体之间轨迹最优值差异较大的情况,导致车辆的安全性以及道路整体通行效率降低。

车联网环境下道路车辆数目较多,车辆在行驶过程中受到来自周围车辆以及行驶环境中其他因素的影响较大,为提高道路交通的高效性和安全性,本文提出一种以专用短程通信(Delicated Short Range Communications, DSRC)技术通信的车联网应用场景为基础,引入万有引力模型与避障模式控制,利用改进人工鱼群算法实现车辆轨迹规划的方法。对车联网环境下的车辆探测区域进行重新规划,设计车辆在不同探测区域对目标车辆的作用力,对车辆行驶环境进行受力分析,利用改进的人工鱼群算法找到车辆的全局最优轨迹,结合避障模式控制,计算车辆的局部轨迹中可安全驾驶最优速度,并通过仿真实验验证算法的可行性和优越性。

1 人工鱼群算法

人工鱼群算法是根据鱼群在水中的运动规律所提出的一种用于解决轨迹规划的算法。在一片水域中,单只鱼找到食物的能力较低,但是当鱼以群体出现时,往往更加容易找到营养物质较多的地方,因此鱼生存数目较多的地方一般也是水域中营养较为丰富的地方。人工鱼群算法根据这一特点,通过构造人工鱼来模仿鱼群的觅食。人工鱼群算法的核心思想是人工鱼在群体活动时,人工鱼的下一刻行为取决于上一刻自身和周围鱼的状态和环境的影响。人工鱼群有四类行为:随机行为、觅食行为、聚群行为和追尾行为[11]。

随机行为是指单独的人工鱼Fishi在水中是随机移动一步,到达一个新的状态,公式如下:

(1)

觅食行为是指人工鱼循着食物多的方向游动的一种行为。人工鱼Fishi在视线范围内随机寻找一个人工鱼Fishj作为目标,若目标人工鱼Fishj周围的食物密度更大,人工鱼Fishi就会游向目标人工鱼Fishj；否则,人工鱼会放弃该目标,寻找新的目标。公式如下:

(2)

聚群行为是指人工鱼Fishi搜索视线范围内的周围鱼群并找到中心位置Fishc,当中心位置Fishc的周围拥堵情况优于Fishi当前位置的周围拥堵情况时,人工鱼Fishi就会向中心位置Fishc移动,否则就执行觅食行为。人工鱼在聚群时会遵守三个规则,包括分割规则、对准规则和内聚规则,公式如下:

(3)

追尾行为是指当人工鱼Fishi视线范围内的人工鱼Fishj周围的食物密度Yj大于人工鱼Fishi的食物密度Yi时,人工鱼Fishi会尾随Fishj快速找到食物,公式如下:

(4)

其中：Fishi和Fishj为人工鱼的个体状态；Yi和Yj为人工鱼Fishi和Fishj周围的食物密度；Visual为视野；Step为步长；Rand为随机数。

2 人工鱼群算法在车联网中的改进

在车联网环境下,车车和车路间通过无线通信来实现信息之间的实时通信及传递,车车之间可以通过位置共享,结合先进的传感器技术,互相感知对方。在车联网中基于鱼群算法的车辆轨迹规划,主要包括四种控制方法：车辆自组织行为控制、车辆速度控制、障碍物避撞控制和道路边缘避撞控制。

2.1 车辆自组织行为控制

2.1.1 目标车辆感知区域定义

将目标车辆的探测区域与人工鱼群个体的感知区域类比,标记目标车辆为V0, 以V0几何中心为圆心、R为半径的范围Scom为V0的有效通信区域,R为车载设备的通信半径;Rentity为半径的范围Scol为V0的碰撞检测区域,L为V0的长度,Rentity=L/2，且Rentity

Sattr=Scom-Scol

(5)

车辆正前方左右两边各45°的扇形范围作为V0的前方探测区域Sfrnt;车辆正后方左右两边各45°的扇形范围作为V0的后方探测区域Srear。Sleft为V0的左探测区域,Srigh为V0的右探测区域,其中

Sleft+Srigh+Sfrnt+Srear=Sattr+Seol=Scom

(6)

定义d(i, j)为车辆Vi到车辆Vj之间的距离,计算公式如下:

d(i, j)=‖Vi-Vj‖

(7)

定义车辆Vi探测区域内的车辆Vj为车辆Vi的邻居,满足在Area区域内的车辆Vj为Vi的正常邻居,Area计算公式如下:

Area={Vj|r

(8)

将车辆V0与人工鱼进行类比分析,V0在下一时刻的最佳行驶状态应具有以下特征:

1)速度大小和方向尽可能与邻居保持基本一致；2)与邻居保持安全距离。

为满足条件(1),设定V0会受到的作用力,为保证V0在下一时刻的速度与周围邻居在速度的大小和方向上保持一致,较为合理的设定是,V0在下一时刻的速度在大小和方向上都趋于所有邻居的平均值,计算公式如下:

(9)

其中:vj为Vj当前时刻的速度；N为V0在Scom内的邻居的数目。此时V0所产生的加速度计算公式如下:

a=vave-v0

(10)

其中:v0为V0当前时刻的速度。根据式(9)～(10)整理得到所产生的加速度计算公式如下:

(11)

由于周围车辆所在探测区域以及与V0之间距离的不同,进而对车辆的影响权重也不同。因此对式(6)进行改造,对不同的速度取不同的权重,权重的大小代表了它在该区域中对V0产生的影响大小。通过对万有引力F引的分析，任何两个物体之间的引力都是两者之间距离r的平方的倒数成正比,根据这个启示,对式(11)中的平均值进行修正。万有引力公式为公式(12)，平均值修正结果为公式(13)：

F引=GM1M2/r2

(12)

(13)

将式(13)代入式(9)中,就得到V0受到周围所有邻居的合力作出合理的假设,公式如下:

(14)

其中:C2是计算V0受到作用产生加速度时1/(Nm)所产生的数量级的弥补；m为V0的质量；k为Vj对V0所产生作用力的系数因子。

此时,V0在F0的作用下轨迹坐标变化为:

F(t)=ma

(15)

(16)

其中:Δt为系统更新速度频率的倒数；X(t)为t时刻V0位置的横坐标；Y(t)为t时刻V0位置的纵坐标；vx(t)为t时刻V0速度的横向分量；vy(t)为t时刻V0速度的纵向分量；ax为t时刻V0在作用力F(t)下产等的加速度的横向分量；ay为t时刻V0在作用力F(t)下产等的加速度的纵向分量。在式(10)和式(11)中k的值是动态的,计算公式如下:

k=k1×ω

(17)

其中:ω是探测区域影响因子,根据Sfrnt、Srear、Sleft、Srigh的不同,ω会对应取ω1、ω2、ω3、ω4进行计算;k1会根据Sexcl、Sattr的不同,对应取-1和1进行计算。

根据式(9)可以得到,由于速度为矢量,车辆在每一时刻所得到的车速都具有一定的大小和方向,故可以得到车辆在众多车辆中的每一时刻与其他车辆保持协同的最佳轨迹。

2.1.2 探测区域影响因子

根据Scom中Vj的位置及行驶信息的不同,确定对V0的影响程度,将Vj对V0的影响因子记为ω。对ω进行分类：ω1为Sfrnt区域中Vj对V0的影响因子；ω2为Srear区域中Vj对V0的影响因子；ω3为Sleft区域中Vj对V0的影响因子；ω4为Srigh区域中Vj对V0的影响因子,其中比重大小为ω1>ω2>ω3=ω4。根据城市道路设计规范、车辆的尺寸以及车辆之间安全距离的计算规则,设定取值范围如下:

ω1∈[0.875 0,1.043 4)

(18)

ω2∈[0.437 5,0.521 7)

(19)

ω3=ω4∈[0.182 3,0.198 0)

(20)

当Scom中Vj发生了不同程度的紧急制动时,相应的ω会有所变动,公式如下:

Δω=0.1×ω

(21)

根据加速度变化前后大小及方向的不同可以分为以下六种情况：

情形一:ah与at方向一致与车辆行驶方向相同,且|ah|≥|at|;

情形二:ah与at方向一致与车辆行驶方向相同,且|ah|<|at|;

情形三:ah方向与车辆行驶方向相同,at方向与车辆行驶方向相反;

情形四:ah与at方向一致与车辆行驶方向相反,且|ah|≥|at|;

情形五:ah与at方向一致与车辆行驶方向相反,且|ah|<|at|;

情形六:ah方向与车辆行驶方向相反,at方向与车辆行驶方向相同。

其中:ah代表变化前的加速度；at代表变化后的加速度。根据对ah和at的分析,当ah和at方向一致的情况为正常驾驶行为的概率较高,当ah和at的方向不一致的情况为车辆的异常驾驶行为的概率较高。

根据采集到的所有车辆行驶数据,对所有车辆的加速度a做分解,以道路的延伸方向为纵向,垂直于道路方向为横向,分别计算车辆的横向加速度ax和纵向加速度ay,计算公式如下：

a=ax+ay

(22)

(a)2=(ax)2+(ay)2

(23)

假定在Sfrnt中Vj的纵向加速度为情形三时,则Vj采取急刹车措施,为保证V0和Vj两车之间的相对安全,此时Vj所对应的ω1会有所提高;在Srear中Vj的纵向加速度为情形六时,则认为Vj采取了急加速措施,为保证V0和Vj两车之间的相对安全,此时Vj所对应的ω2会有所提高;在Sleft中Vj的横向加速度为情形三时,认为Vj采取了转弯制动措施,为保证V0和Vj两车之间的相对安全,此时Vj所对应的ω3会有所提高;在Srigh中Vj的横向加速度为情形六时,认为Vj采取了急转弯措施,为保证V0和Vj两车之间的相对安全,此时Vj所对应的ω4会有所提高。

2.2 车辆速度控制

在实际场景中,道路一般都对车辆有限速要求,为保证车辆在道路环境中的安全性,引入车辆速度控制模式。为保证车辆在道路中行驶的速度在道路要求的最小限速和最大限速之间,要求当车辆在沿道路的横向和纵向上的分量小于最小限速或者大于最大限速时,具有相反方向速度分量的车辆的K系数会相应的提高,这样就保证了车辆在某一方向上车速低于最小限速或者高于最大限速的情况出现时,车辆在道路行驶中速度安全。

2.3 障碍物避碰控制

车辆在运动过程中会遇到各种不同的交通环境,这些环境中有可能出现行人、摩托车、电动车等一些实体,将这些实体都称为障碍物[12-14]。当障碍物出现在车辆的通信排斥区域中,为保证车辆在整个行驶中不与障碍物发生碰撞并安全通过,假设车辆会受到来自障碍物的排斥力,受力分析如图1所示。

图1 车辆和障碍物之间分布示意图Fig. 1 Schematic diagram of distribution between vehicles and obstacles

障碍物排斥力F的方向为远离障碍物,F的大小定义为:

|F|=

(24)

其中:L为车辆质心与障碍物质心之间的距离;r1是车辆的实体半径;r2是障碍物的实体半径;P1是车辆的质心位置,P2是障碍物的质心位置,两者质心与车辆行驶方向所成角度为α;vx为此刻车辆的横向速度；vy为车辆的纵向速度。

当障碍物进入车辆的通信排斥区域中时,车辆会计算两者之间是否会有碰撞的可能性,当L×sin(α)>r1+r2时,车辆以当前速度且保持方向不变继续行驶不会发生碰撞,当L×sin(α)≤r1+r2时,车辆以当前速度且保持方向不变继续行驶会与障碍物发生剐蹭或碰撞,此时车辆与障碍物纵向为可行驶距离s,计算公式如下:

s=L×cos(α)-r1-r2

(25)

在以当前速度行驶且不采取任何措施的情况下,可行驶时间为t,计算公式如下:

t=s/|vy|

(26)

由此可以得出,要保证车辆在t时刻后不与障碍物发生碰撞,此时所需的加速度a的计算公式如下:

|a|=

(27)

要产生大小为|a|的加速度,且方向与车辆横向速度方向相反,此时车辆应该受到障碍物的力F的大小应为：

|F|=m×|a|

(28)

此时,车辆在受到障碍物的作用力F,Δt时刻后,车辆的轨迹坐标为:

(29)

2.4 道路边缘避碰控制

道路边缘与障碍物对车辆的约束类似,区别在于,障碍物可以当作质点,而道路边缘是直线,当在车辆的通信排斥区中检测到道路边缘时,为保证车辆在行驶中不与道路边缘发生碰撞并能够安全通过,假设车辆会受到来自道路边缘的排斥力,如图2所示。

图2 车辆与道路边缘的分布示意图Fig. 2 Schematic diagram of the distribution between vehicles and road edges

道路边缘的排斥力F方向为远离通信排斥区检测到的道路边缘的方向,F的大小定义为:

(30)

其中:车辆的行驶方向与道路边缘之间的夹角为α;车辆质心与道路边缘的垂直距离为L;车辆的实体半径为r;车辆的质心位置为P;道路边缘位置为l;车辆质心与道路边缘位置的距离为d(P,l);车辆的车载设备通信半径为R;车辆的横向速度为vx;车辆的纵向速度为vy。

当在车辆的通信排斥区中检测到道路边缘时,若车辆在不采取任何措施的情况下,车辆所能保持的最长安全时间为t=(L-r)/|vx|,之后车辆就会与道路边缘发生碰撞。要保证车辆与道路边缘不发生碰撞,车辆要横向上采取的最小加速度为a,应满足式(31)～(32):

|vx|t+|a|t2/2=L-r

(31)

|vx|+|a|t=0

(32)

由式(25)～(26)整理可得加速度a的大小为:

(33)

要产生大小为|a|的加速度,且方向与车辆横向速度方向相反的加速度,此时车辆应该受到道路边缘的作用力F为:

(34)

当车辆在受到道路边缘的作用力F,Δt时刻后,车辆的轨迹坐标为:

(35)

3 实验

本文应用Matlab对车联网环境下的改进人工鱼群算法进行验证,如图3～6所示,分别对车辆的自组织行为、速度控制以及障碍物避障控制进行仿真验证。依据改进的人工鱼群算法,随机选取4辆车和8辆车作仿真验证,在道路所在平面建立直角坐标系,以道路横向位移为x坐标,以道路纵向位移为y坐标。

图3 车辆数目为4时车辆的轨迹Fig. 3 Vehicle trajectory for 4 vehicles

图4 车辆数目为8时车辆的轨迹Fig. 4 Vehicle trajectory for 8 vehicles

图5 车辆速度-时间变化图Fig. 5 Vehicle speed-time change chart

根据图3～4可以发现,车辆之间经过一段时间的迭代,车辆轨迹之间趋于一致,这说明了车辆之间的自组织行为。车辆在行驶初期,车辆轨迹之间相互交错,波动性比较大,这主要受车辆之间的影响较大,也体现出人工鱼在群体内的活动。由于初始化时车辆的位置、速度和方向都是随机设定的,车辆轨迹在从不稳定到稳定的过程中,会出现不同的轨迹情况,但根据算法中公式的设定,各个车辆之间会在最终趋于稳定。

根据城市道路交通中车辆的运行状况分析可知,车辆在群体中行驶时所能感知的最多车辆数目大约为40。仿真实验以车辆数目为2、4、8、16、32和40时,分别实验300次,记录车辆轨迹趋于一致时的迭代次数,通过计算可以得到在300次实验中的平均迭代次数、迭代次数方差、最少迭代次数和最多迭代次数,相关数据如表1所示。

表1 车辆数目变化时对应的迭代次数(300次实验)Tab. 1 Number of iterations when the number of vehicles changes (300 experiments)

根据表1可知,当改变车辆数目时,车辆轨迹趋于一致所经过的迭代次数会有所不同,车辆数目增加时所需要的迭代次数会增加,这是由于车辆的初始状态的不同会导致车辆的相互影响变大。

图5为3辆不同车辆在不同限速要求下车辆速度随时间的变化情况。在仿真实验中,首先对三辆车的安全驾驶速度设定为10～30 m/s进行一次实验，再将三辆车的安全驾驶设定为10～25 m/s进行一次实验,且车辆的初始速度在该范围内随机生成。在行驶初期,车辆会受到道路边缘、障碍物或者其他车辆的吸引力或斥力作用,所以车辆的速度会处于波动中,经过一段时间的相互作用后,车速基本稳定在实验设定的最高安全驾驶速度处，即在30 m/s和25 m/s处。

图6为以道路右侧45°为横坐标,以道路左侧45°为纵坐标时,车辆在两次遇到障碍物的情况下,避撞控制下的车辆轨迹图。当车辆遇到障碍物时,车辆会受到来自障碍物的排斥力,在排斥力的作用下,车辆会根据障碍物的位置,调整车辆的轨迹,避免发生碰撞。

图6 避障控制下车辆轨迹Fig. 6 Vehicle trajectory under obstacle avoidance control

表2 轨迹融合中三种算法的迭代次数Tab. 2 Number of iterations of three algorithms in trajectory fusion

在实验环境中,车辆的初始位置及初始状态随机生成,设定车辆数目依次为2、4、8、16、32和40,在每种车辆数目情况下，依次采用萤火虫算法、传统人工鱼群算法以及改进后的人工鱼群算法,分别进行300次实验,记录不同车辆数目在采用三种算法后实现轨迹融合所经过的最大迭代次数、最少迭代次数以及平均迭代次数。算法比较时参数均取多次实验得到最佳收敛性的相关值。传统人工鱼群算法中,设定最大迭代次数为300,最大试探次数为100,拥挤度因子为0.8,初始化视野为5;萤火虫算法中,荧光素更新率为0.004 8,荧光素消失率为0.9,动态决策域更新率为1,迭代次数为300;改进后的人工鱼群算法中,更新频率为1 Hz,前后左右区域因子大小分别为ω1=0.9,ω2=0.5,ω3=ω4=0.19。表2为三种算法在车辆轨迹融合中所需要的迭代次数,通过表2可发现,采用改进后的人工鱼群算法,相对于原人工鱼群算法和萤火虫算法,车辆轨迹融合时经过的平均迭代次数最少,测试车辆数为2～40时,平均迭代次数大大减少，迭代效率分别提高3～7、4～8倍,且平均迭代次数受车辆数量的影响较小,验证了改进后的人工鱼群算法在实现车辆轨迹融合时较萤火虫算法和传统人工鱼群算法有更好的效果。

4 结语

利用人工鱼群算法的收敛性与车联网相结合,提出了一种对人工鱼群算法的优化改进策略,使其适用于车联网环境,引入万有引力模型与避障模式控制,通过对车辆探测区域进行细化,并对车辆与障碍物、道路边缘以及周围车辆之间的数据进行分析,从而对车辆的行驶速度和轨迹作出合理的规划,实现多车轨迹融合时的全局最优,同时对目标车辆在不同方向上是否有异常行为的出现进行判断和有效预防,从而保证车辆的安全驾驶。仿真实验结果表明,本文方法具有一定的可行性和合理性,能为行车安全以及提高道路通行效率起到良好的辅助作用。