本发明涉及智能驾驶，尤其涉及一种基于图结构和强化学习的车辆路径规划方法。
背景技术：
1、随着国民经济的快速发展，居民汽车拥有量不断急剧攀升，城市堵车现象越来越严重，研究如何对车辆行驶路径进行合理规划，避免拥堵，也变得越来越重要。将强化学习的方法应用到车辆路径规划当中是这个领域一个主要的研究方向，城市车辆路径规划面临多个难题，早晚上下班高峰、突发交通事故等情况都会极大的影响现有的城市拥堵情况，进而影响实时车辆路径，其次大量的道路与城市使得规划问题规模庞大，解决较为困难。
2、强化学习作为机器学习的一种，可以学会如何解决各种复杂的任务，随着城市车辆的不断增多，对车辆进行合理的路径规划是解决城市拥堵的关键一环，目前常用的车辆路径规划算法包括收缩层级算法、基于模型预测的路径规划算法等。但是以上方法都存在一些缺点，一是使用时计算量较为庞大，计算复杂；二是没有将实时的城市道路交通情况纳入考虑。
技术实现思路
1、为了解决上述问题，本发明提出了一种基于图结构和强化学习的车辆路径规划方法，通过交通道路图与增强的实时数据训练强化学习模型，从而得到一个高效的、可以获得最优路径的模型对车辆进行实时路径规划。
2、一种基于图结构和强化学习的车辆路径规划方法，包括以下步骤：
3、步骤s1：地图数据处理，包括道路数据处理和道路路段划分，统一规范道路信息，对道路路段进行划分，在地图当中标识信号灯，然后按照道路依次连接这些信号灯，两个信号灯之间的道路作为一个单独的路段；
4、步骤s2：通过道路信息，以信号灯为节点，引入时间因素，构建多个时效交通图，首先构建基准交通图，基准交通图构建以信号灯作为节点，构建出节点矩阵存储图，信号灯之间的距离作为图的边的权值，再分析建筑位置，以信号灯为中心通过聚类进行划归；然后构建时效交通图，通过现实数据进行统计，得到不同时段不同路段的平均通过时间，计算得到不同时段的路段实际通过长度，更新图的边，得到时效交通图；
5、步骤s3：训练强化学习模型，在时效图当中随机选择起点和终点，模拟现实车辆行驶，根据距离将起点和终点划归到最近的信号灯，然后使用狄杰斯特拉算法，在各个时效交通图间得到最短路径作为次优路径，训练强化学习模型，在起点和终点间找到最优路径，并利用次优路径加快训练速度，不断重复该过程，最终得到能够规划出最优路径的强化学习模型；
6、步骤s4：利用训练好的强化学习模型进行路径规划，将用户输入的数据转换为模型的输入，以通过强化学习模型获取最优路径，并根据用户的实时位置对最优路径进行更新。
7、进一步地，步骤s1包括：
8、道路数据处理，针对不同道路信息的存储格式进行格式的统一，包括道路标注，针对不同格式道路地图，构建所需的基准道路地图，设置基准道路地图单位长度，通过人工识别或智能识别的方法，对道路进行识别，记录到基准道路地图当中，若出现道路重叠的情况，则根据道路的标号区分不同道路；
9、道路路段划分，针对后续构建交通图所需的道路路段长度数据，对基准道路地图当中的道路进行分段，具体包括信号灯位置标注和路段构建与记录；信号灯位置标注，通过信号灯的经纬度地址，在基准道路地图当中，以点的形式标注信号灯的位置；路段构建与记录，依次连接道路当中的信号灯，将两个信号灯之间的道路路段记为一个单独的路段，并记录该路段的长度、起始信号灯、最低限速、最高限速和路段类型，其中最低限速、最高限速和路段类型与路段所在的道路保持一致，对于相邻但是不在同一条道路上的信号灯不连接。
10、进一步地，步骤s2包括：
11、首先构建基准交通图节点，图中的一个节点表示一个集合，其具体为一个以信号灯为中心加上其附近多个建筑的集合，为了得到这样的集合，采用dis聚类算法在经纬度的差异上进行聚类，聚类结果保证不同集合当中距离建筑最近的信号灯就是聚类中心所表示的信号灯；
12、其次构建基准交通图，根据上述得到的聚类集合作笛卡尔积，将该结果作为矩阵，置矩阵当中所有点的初始值为-1，根据路段信息，当对应信号灯直接存在路径时就置矩阵对应位置的值为路段长度；
13、最后构建时效交通图，根据实际统计数据，划分城市的早晚高峰、平常时段和深夜时段，然后通过现实数据进行统计，得到不同时段不同路段的平均通过时间，最后通过平均通过时间乘以对应路段最高限速，将得到的结果作为额外的距离加到对应路段的边的权值上，以此得到不同时段的交通图，即时效交通图。
14、进一步地，采用dis聚类算法进行聚类，包括：
15、初始化：选择k个初始质心，这些质心是所有信号灯，每一个信号灯作为一个质心；
16、计算间隔距离：对于信号灯中的每个点，计算它与每个直接连接的信号灯之间的距离，设两个信号灯的经纬度分别表示为traffic(lat1，lon1),traffic(lat2,lon2)，间隔距离diff计算公式如下：
17、
18、划分建筑物：对于每个信号灯以其为中点，计算划分范围，设信号灯的经纬度表示为traffic(lat1,lon1)，则划分范围计算如下：
19、latitude＝lat1+sin(θ)*diff
20、longtitude＝lon1+sin(θ)*diff
21、其中，θ表示角度，范围是0°-360°；
22、对于所有的建筑，如果其经纬度处在(latitude，longtitude)的范围内，它就是属于以这个信号灯作为中心的距离范围内；
23、对于剩下的不在划分范围内的建筑，计算它们和所有信号灯的距离，然后把它们依次划分到距离最近的信号灯所对应的聚类。
24、进一步地，步骤s3包括：
25、首先模拟现实车辆导航，选择建筑作为起始点，构建路径规划任务以及次优路径，包括：
26、建筑映射，在选取起始点时，需要满足选择的建筑所属的聚类不是相邻的，避免过短路程，然后对起始点进行处理，映射到构建的基准交通图的节点当中，具体为将输入的建筑经纬度用对应聚类中心的信号灯的经纬度进行替换；
27、次优路径构建，在各个时段的时效交通图当中，采取狄杰斯特拉算法，计算最短路径，作为次优路径，次优路径记录如下：
28、p＝{nodestart，node1,...,nodeend，{时段t}}
29、其中，node是路径当中的信号灯，具体表示为信号灯的编号，时段t表示该路径是从哪个时效交通图获得的，是一个枚举类型的值；
30、然后进行强化学习模型训练，在训练强化学习模型时，将以构建的次优路径进行辅助，加速模型训练，首先构建模型输入，模型的输入是一个集合，集合包括路径起点和终点建筑经纬度以及当前时段的编号。
31、进一步地，通过构建的次优路径引导模型训练，包括：
32、模型输入转换，先对模型输入进行处理，将输入的建筑经纬度通过聚类模型进行分类，找到对应的距离，然后用对应聚类中心的信号灯编号进行替换，以满足次优路径的使用条件，替换后，模型输入表示为：{信号灯编号1，信号灯编号2，时段编号}，其中，信号灯编号1对应起点，信号灯编号2对应终点；
33、通过次优路径进行模型训练，模型在训练过程当中，以1-α的概率使用次优路径给出下一个期望的信号灯编号，以α的概率使用模型预测的输出作为下一个期望的信号灯编号，α随着训练轮次的增加逐渐上升，具体计算公式为：
34、α＝α+α*β
35、其中，β是增长参数，控制α的上升速率，每训练一轮，就通过该公式增加α的大小；
36、输出路径构建，模型获得输入后，会给出下一个期望的信号灯编号，记录该期望信号灯编号，作为路径的中继点，然后以给出的期望信号灯编号重构模型输入，具体操作为替换输入的第一项，再次输入模型，计算下一个期望的信号灯编号，直到到达终点，将所有的期望信号灯在地图上连接起来，就得到模型输出的路径。
37、进一步地，步骤s4包括：
38、获取输入，根据用户选择的起点和终点，采用训练好的聚类模型，找到对应的信号灯，再依据当前时间选择对应的时间段，构造模型初始输入；
39、最优路径实时更新，系统会实时获取用户当前位置经纬度，然后采用训练好的聚类模型找到当前对应的信号灯，同时重新获取时间，构造新的输入，再输入模型，获取模型给出的最新最优路径。
40、与现有技术相比，本发明的有益技术效果如下：
41、本发明通过对地图信息进行处理，构造所需的图结构，使之满足后续步骤的输入结果，车辆起始点可能是任何建筑，而大量建筑位置会扩大问题解决难度，因此本发明采取聚类的方法，以信号灯来表示多个建筑，有效降低训练难度。然后通过结合时间段，分析不同时间段的具体交通状况，构造出不同的时效交通图，进而可以更加符号现实车辆行驶状况。在训练模型时，通过在构建的时效交通图当中构造次优路径，在训练前期引导训练，有效避免了前期模型训练不足时输出错误较多，降低训练效率和模型能力不足的情况的出现。在实际使用时，本发明通过定时获取最新位置信息，更新当前模型输出，使得输出构建更加灵活，符合现实驾驶情况；
42、本发明将强化学习引入到路径规划当中，从而避免了传统路径规划面临的计算成本大、计算时间长的问题，实际使用时，利用训练好的神经网络模型，可以及时的输出所需路径，计算量与计算成本更低；同时，本发明方案结合了时间因素，能够更加符合城市道路现状，训练的强化学习模型能够在不同时间根据不同的道路状况给出最优的路径，同时考虑了距离、道路交通情况等因素，使得规划的路径更加准确和优化。
1.一种基于图结构和强化学习的车辆路径规划方法，其特征在于，所述方法包括：
2.根据权利要求1所述的方法，其特征在于，所述步骤s1进一步包括：
3.根据权利要求1所述的方法，其特征在于，所述步骤s2进一步包括：
4.根据权利要求3所述的方法，其特征在于，采用dis聚类算法进行聚类，包括：
5.根据权利要求1所述的方法，其特征在于，所述步骤s3进一步包括：
6.根据权利要求5所述的方法，其特征在于，通过构建的次优路径引导模型训练，包括：
7.根据权利要求1所述的方法，其特征在于，所述步骤s4进一步包括：
