本发明涉及自动驾驶技术领域，尤其涉及一种基于协同演化的自动驾驶车辆决策涌现方法。
背景技术：
目前，城市交通规模大，动态多，变化大的特点导致交通运输系统和交通规则几乎无法应对瞬息万变的交通状况，并且无法及时对单个车辆进行合理的规划和调度。
在现有技术中，中心化调度方法通常适用于小规模的情况。例如，中心化调度模型可以解决交通灯调度的最优性，提高交通吞吐量，并减少交叉路口的等待时间。然而，中心化优化算法(包括强化学习，神经网络和模糊逻辑等)的计算复杂度将随着路口数量，车辆数量和道路长度的增加而呈指数增长。而且，城市车辆网络的动态和瞬时变化的特点使得难以通过中心化优化调度算法及时响应各个车辆和各种交通状况。
目前的进化算法(例如遗传算法等)和一些智能优化算法(例如蚁群算法，粒子群算法，模拟退火算法等)对于具有固有特征分布的大规模问题比较有效。然而，这些传统的进化算法未能将个体之间以及环境之间竞争与合作的影响结合在一起，随着个体车辆与环境之间v2x技术的发展，这种影响变得更加明显和突出。
技术实现要素：
本发明的目的在于克服上述现有技术的缺陷，提供一种基于协同演化的自动驾驶车辆决策涌现方法，通过模拟竞争与合作的协同进化过程，以观察在不同环境下最优驾驶策略的涌现。
根据本发明的第一方面，提供了一种基于协同演化的自动驾驶车辆决策涌现方法。该方法包括以下步骤：
构建道路模型，并确定车辆在道路模型中的初始位置分布和行驶目的地；
设置多个候选驾驶策略用于限定车辆的行驶速度以及前车与后车的交互关系，并根据所述多个候选驾驶策略将车辆划分到不同的种群；
根据车辆运动学模型、预设的交通信号灯调度策略以及车辆对应的候选驾驶策略运行车辆；
以控制车辆的多个行驶指标为优化目标，探索所述多个候选驾驶策略的优劣。
在一个实施例中，所述构建道路模型，并设置车辆在道路模型中的初始位置分布和行驶目的地包括：
构建带交叉口的双向四车道道路模型，其中道路由栅格组成，每个栅格都是一个矩形，栅格长度被设置为等于车辆长度；
将随机设置车辆的初始分布并随机设置车辆目的地，当车辆中心点落入道路模型的网格中时，认为网格被占据。
在一个实施例中，所述多个候选驾驶策略包括：
保守策略：用于限定车辆以最大速度行驶，当前车的速度较慢时减速，不要超车；
理性策略：用于限定以最大的速度行驶，当前车的速度较慢并且变道相关20米区域内没有车辆汇入时超车；
贪婪策略：用于限定以最高速度行驶，始终超车。
在一个实施例中，所述交通信号灯调度策略是固定时间片轮转，每个时间片为8秒。
在一个实施例中，所述多个行驶指标包括平均通行时间、事故率，平均排放、平均能耗中的至少两项。
根据本发明的第二方面，提供一种计算机可读存储介质，其上存储有计算机程序，其中，该程序被处理器执行时实现本发明上述方法的步骤。
根据本发明的第三方面，提供一种计算机设备，包括存储器和处理器，在所述存储器上存储有能够在处理器上运行的计算机程序，所述处理器执行所述程序时实现本发明上述的方法的步骤。
与现有技术相比，本发明的优点在于：针对大规模全局车辆优化问题，提出引入协同演化方法，通过协作和竞争来实现多个用于全局优化的对象，例如平均速度和事故率等，通过实现多个全局目标的优化，使得最优驾驶策略自发涌现。
附图说明
以下附图仅对本发明作示意性的说明和解释，并不用于限定本发明的范围，其中：
图1是根据本发明一个实施例的基于协同演化的自动驾驶车辆决策涌现方法的流程图；
图2是根据本发明一个实施例的道路模型示意图；
图3是根据本发明一个实施例的正态分布邻域示意图；
图4是根据本发明一个实施例的基于协同演化的自动驾驶车辆决策涌现方法的实现流程图；
图5是根据本发明一个实施例的道路环境示意图；
图6是根据本发明一个实施例的种群随繁衍代数的变化趋势示意图；
图7是根据本发明一个实施例的种群事故数量示意图；
图8是根据本发明一个实施例的平均速度示意图；
附图中，lane-车道；centerpoint-中心点；vehicle-车辆；conservativepolicy-保守策略；radicalpolicy-贪婪策略；rationalpolicy-理性策略；generation代；ratioofthesubgrouppopulation-子代种群比例；numberofaccidents-事故数；averagespeed-平均速度。
具体实施方式
为了使本发明的目的、技术方案、设计方法及优点更加清楚明了，以下结合附图通过具体实施例对本发明进一步详细说明。应当理解，此处所描述的具体实施例仅用于解释本发明，并不用于限定本发明。
在本文示出和讨论的所有例子中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它例子可以具有不同的值。
对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为说明书的一部分。
本发明提出了一种用于大规模自动驾驶车辆集群的多目标协同进化方法，以研究从长远来看哪种驾驶策略将实现总体良好的性能。在本发明中，首先，将大规模城市自动驾驶汽车的驾驶策略制定为一个多目标优化问题。然后，建立网格道路模型和车辆动力学模型，其中各个车辆之间相互间接交互，从而将交互复杂度从o(n！)(n是要交互的车辆数)降低到o(n)。本发明模拟了竞争与合作的协同进化过程，以观察在不同环境下最优驾驶策略的涌现。
经研究，目前的中心化优化算法的计算复杂度过高，无法处理大规模的交通优化问题。另一方面，传统的进化算法和群体智能算法仅包含一个单一的种群，这对于竞争和合作的多样化环境是不够的。针对这些问题，本发明提出一种将协同进化与群体智能相结合的方法，以构造多个合作竞争群体，在车路协同网络中协同进化，并观察最优驾驶策略的涌现。
参见图1所示，本发明实施例提供的基于协同演化的自动驾驶车辆决策涌现方法包括以下步骤：
步骤s110，构建车辆模型和车辆运动学模型。
参见图2所示，将车辆建模为长为l且宽度为w的矩形，记为ck，车辆的中心点表示为(xk，t，yk，t)，即有：
ck，t:(xk，t，yk，t)(1)
其中，ck，t表示第k辆车在t时刻的几何中心，xk，t表示第k辆车在t时刻的几何中心的横坐标，yk，t表示第k辆车在t时刻的几何中心的纵坐标。
在本发明中，引入车辆运动学模型来描述车辆的行为，特别是它如何影响实际情况并促进群体之间的竞争和协同作用。
具体地，变道表示为：
xt 1＝xt vt 1*cos(αt θt)*δt(3)
yt 1＝yt vt 1*sin(αt θt)*δt(4)
xt 2＝xt 1 vt 1*cos(αt)*δt(5)
yt 2＝yt 1 vt 1*sin(αt)*δt(6)
转弯表示为：
xt 1＝xt vt 1*cos(αt θt)*δt(8)
yt 1＝yt vt 1*sin(αt θt)*δt(9)
xt 2＝xt 1 vt 1*cos(αt θt θt 1)*δt(10)
yt 2＝yt 1 vt 1*sin(αt θt θt 1)*δt(11)
路口减速表示为：
其中：
vt表示车辆t时刻的速度；
δt表示时间步长；
xt表示车辆t时刻几何中心的横坐标；
yt表示车辆t时刻几何中心的纵坐标；
αt表示车辆t时刻车姿角度；
θt表示车辆t时刻方向盘转角；
xc表示交通灯几何中心的横坐标；
yc表示交通灯几何中心的纵坐标；
dt表示车辆在t时刻与交通灯的距离；
步骤s120，构建道路模型。
在一个实施例中，本发明建立一个带交叉口的双向四车道道路模型。道路由栅格组成，每个栅格都是一个矩形，宽度gw和长度gl相同。路网中第i行第j列的栅格gri,j有四个坐标为
栅格长度gl被设置为等于车辆长度，从而在一个单一栅格中将不多于一辆具有其中心点的车辆。仍参见图2所示，车辆a的中心位于一个网格gr3,2中，车辆b的中心位于另一个网格gr3,3中。然后，在公式(15)中定义状态gi,j(t)的二进制状态。在图2中，当车辆中心点落入网格中时，网格被占据，并且其状态为1，而当内部没有车辆时状态为0，栅格占用状态表示为：
利用所构建的道路模型和车辆模型，单个车辆仅与相邻车辆间接交互。因此，在每个时间步长将交互复杂度从n：n(n表示车辆数量)降低到1：1，大大降低了模型的复杂性，并增强了可扩展性。
步骤s130，对于车辆集群设置多目标优化问题。
公式(16)提出了大规模城市车辆集群的多目标优化问题，其中f1(x)＝∑i∑jgi，j(t)*gi，j 1(t)指两个连续栅格都被占用，gi，j(t)*gi，j 1(t)将为1，而f2(x)＝-e(v(t))表示所有车辆的总体平均速度。
使得：
f1(x)＝∑i∑jgi，j(t)*gi，j 1(t)(17)
f2(x)＝-e(v(t))(18)
αk，t＝αk，t-1 θk，t(23)
vk，t≤vmax(24)
θk，t≤θmax(26)
其中：
vk，t表示第k辆车t时刻的速率；
αk，t表示第k辆车t时刻的车姿角度；
θk，t表示第k辆车t时刻的方向盘转角；
δt表示时间步长；
||·||表示二范数。
步骤s140，设置候选驾驶策略集合，以限定车辆的行驶速度以及前车与后车的交互关系。
驾驶策略用于限定车辆的行驶情况以及与周边车辆的交互关系，可设置多种候选驾驶策略。例如候选驾驶策略集合包括三种驾驶策略，分别是保守策略：以最大速度行驶，当前车的速度较慢时减速，不要超车；理性策略：以最大的速度行驶，当前车的速度较慢并且变道相关一定区域(例如20米)内没有车辆汇入时超车；贪婪策略：以最高速度行驶，始终超车。
进一步地，可根据不同的候选驾驶策略将车辆划分到不同的种群。
步骤s150，根据车辆运动学模型、预设的交通信号灯调度策略以及车辆对应的候选驾驶策略运行车辆，以探索候选驾驶策略集合。
具体地，在一个实施例中，探索候选驾驶策略集合的步骤如下：
步骤s1，初始化道路和车辆种群。
例如，设置车辆数量和初始分布区域，并随机设置车辆的初始位置并随机设置车辆目的地等。
步骤s2，根据车辆运动学模型运行车辆和交通信号灯仿真，直到所有车辆到达目的地。在每个时间步骤更新道路环境(即网格状态)。
例如，交通信号灯的调度采用固定时间片轮转算法，每个时间片为8秒或10秒等。
步骤s3，记录单个车辆的状态，例如速度和事故率，然后，根据以下奖励函数评估车辆：
其中：
r(k)表示第k辆车的奖励函数；
η表示第k辆车引起的事故数量；
tk表示第k辆车的生命周期；
δv表示所有车辆的速度的标准差；
β1,β2表示各项权重；
步骤s4，计算车辆总体得分的均值μ和标准差δ并根据子代规则确定每个个体的子代数，完成繁衍后开始下一代的模拟运行。
在一个实施例中，结合图3所示，后代的繁衍规则设置为：
1)、车辆得分落在平均值右侧或区域右侧的两个标准偏差邻域(2σ)内，繁殖两个后代；
2)、车辆得分落在平均值右侧的标准偏差邻域(1σ)内，繁殖两个后代；
3)、车辆得分落在平均值的左侧，没有后代。
需说明的是，奖励函数的设计，除考虑平均通行时间、事故率，还可以考虑平均排放、平均能耗等因素。
步骤s5，在种群分布趋于收敛时终止。
应理解的是，上述车辆模型、道路模型、车辆运动学模型、交通信号灯调度等仅用于解释本发明，在不违背本发明精神的情况下，本领域技术人员可对上述模型或参数作适当的修改或变型，例如，采用动态地交通信号灯调度，根据现实的车道状态设计为其他的道路模型等。
为进一步验证本发明的效果，按照本发明设置的上述模型和算法构建实验环境如下(实现流程可参见图4所示)：
(1)道路模型
在城市交通中，一个具有代表性的交通场景是十字路口，其中包含城市驾驶行为的大多数元素，包括变道，转弯，超车，超速等。在不失一般性的前提下，建立了一条双向四车道道路模型，如图5所示。道路的每个部分长1000米，每个车道宽3.75米，这种设置符合道路建设标准。
(2)车辆
将测试中的车辆总数设置为400，最初随机分布在道路模型描述的区域内，然后根据不同的候选驾驶策略分为多个种群。每个车辆的目的地是随机设置的。在生命周期中，每辆车都会根据自己的驾驶策略与其他个体以及道路交互，从而影响其他个体并促进整体发展。
(3)交通信号灯调度
交通信号灯在城市交通中使用最常见的固定时间片轮转算法，每个时间片为8秒。
(4)候选驾驶策略
候选驾驶策略包括保守策略、理性策略、贪婪策略等，也可设置其他类型的驾驶策略。
具体实验参数参见下表1所示。
表1实验参数
在本地使用python开发的模拟环境中，在2公里长的道路上进行了400辆汽车的实验。
通过协同进化和优胜劣汰的繁衍规律，不同子种群(采用不同驾驶策略)的种群分布发生了显着变化。优胜劣汰在30代后出现。如图6至图8所示，实验结果表明：具有保守的驾驶策略的分组表现最差，平均速度最低，因此种群规模迅速减少；在所有事故率中，采取理性策略的子种群表现最好，平均速度与最高事故率相差无几，因此种群规模迅速增加；采取激进策略的子种群产生的事故率最高，平均速度略高。研究结果对未来的智能交通系统和智能车辆的设计驾驶政策具有启发性。
在处理器为2ghz，8gb内存的macbookpro上，仿真时间为3分钟。由于计算复杂度仅与车辆数量成线性关系并且可以并行处理，因此本发明提供的方法可以扩展为探索包含数百万辆自动驾驶汽车的城市的驾驶策略。例如，对于某些超级计算机来说，计算一百万辆汽车仅需要几十秒。
需要说明的是，虽然上文按照特定顺序描述了各个步骤，但是并不意味着必须按照上述特定顺序来执行各个步骤，实际上，这些步骤中的一些可以并发执行，甚至改变顺序，只要能够实现所需要的功能即可。
本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。
计算机可读存储介质可以是保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以包括但不限于电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、静态随机存取存储器(sram)、便携式压缩盘只读存储器(cd-rom)、数字多功能盘(dvd)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。
以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。
1.一种基于协同演化的自动驾驶车辆决策涌现方法，包括以下步骤：
构建道路模型，并确定车辆在道路模型中的初始位置分布和行驶目的地；
设置多个候选驾驶策略用于限定车辆的行驶速度以及前车与后车的交互关系，并根据所述多个候选驾驶策略将车辆划分到不同的种群；
根据车辆运动学模型、预设的交通信号灯调度策略以及车辆对应的候选驾驶策略运行车辆；
以控制车辆的多个行驶指标为优化目标，探索所述多个候选驾驶策略的优劣。
2.根据权利要求1所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，所述构建道路模型，并设置车辆在道路模型中的初始位置分布和行驶目的地包括：
构建带交叉口的双向四车道道路模型，其中道路由栅格组成，每个栅格都是一个矩形，栅格长度被设置为等于车辆长度；
将随机设置车辆的初始分布并随机设置车辆目的地，当车辆中心点落入道路模型的网格中时，认为网格被占据。
3.根据权利要求1所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，在探索所述多个候选驾驶策略的优劣的过程中，采用以下奖励函数评估车辆k：
其中：
r(k)表示第k辆车的奖励函数；
η表示第k辆车引起的事故数量；
tk表示第k辆车的生命周期；
δv表示所有车辆的速度的标准差；
β1,β2表示各项权重；
δt表示时间步长。
4.根据权利要求3所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，在探索所述多个候选驾驶策略的优劣的过程中，后代的繁衍规则设置为：
当车辆得分落在平均值右侧或区域右侧的两个标准偏差邻域内时，繁殖两个后代；
当车辆得分落在平均值右侧的标准偏差邻域内时，繁殖两个后代；
车辆得分落在平均值的左侧时，不繁殖后代。
5.根据权利要求4所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，将所述优化目标表示为：
使得：
f1(x)＝∑i∑jgi,j(t)*gi,j 1(t)
f2(x)＝-e(v(t))
αk,t＝αk,t11 θk,t
vk,t≤vmax
θk,t≤θmax
其中：
vk,t表示第k辆车t时刻的速率；
αk,t表示第k辆车t时刻的车姿角度；
θk,t表示第k辆车t时刻的方向盘转角；
δt表示时间步长；
||·||表示二范数；
amax表示最大加速度；
vmax表示最大速度；
θmax表示最大方向盘转角；
gi,j(t)表示路网中第i行第j列的栅格在t时刻的占用状态；
ck,t表示第k辆车在t时刻的几何中心；
f2(x)＝-e(v(t))表示所有车辆的总体平均速度。
6.根据权利要求1所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，所述多个候选驾驶策略包括：
保守策略：用于限定车辆以最大速度行驶，当前车的速度较慢时减速，不要超车；
理性策略：用于限定以最大的速度行驶，当前车的速度较慢并且变道相关20米区域内没有车辆汇入时超车；
贪婪策略：用于限定以最高速度行驶，始终超车。
7.根据权利要求1所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，所述交通信号灯调度策略是固定时间片轮转，每个时间片为8秒。
8.根据权利要求1所述的基于协同演化的自动驾驶车辆决策涌现方法，其特征在于，所述多个行驶指标包括平均通行时间、事故率，平均排放、平均能耗中的至少两项。
9.一种计算机可读存储介质，其上存储有计算机程序，其中，该程序被处理器执行时实现根据权利要求1至8中任一项所述方法的步骤。
10.一种计算机设备，包括存储器和处理器，在所述存储器上存储有能够在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现权利要求1至8中任一项所述的方法的步骤。
技术总结