本发明公开了一种基于强化学习的路径导航方法及系统，包括：根据城市的地图数据，构建城市的道路邻接关系图；根据车辆轨迹数据和道路邻接关系图，预测城市不同路段不同时段的拥塞指数；以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；基于强化学习生成导航路径，强化学习的状态空间包括所述道路拥塞概率图。本发明将城市道路拥塞情况在数值化的基础上概率化，更直观易可视化；道路拥塞计算只利用了道路状况和历史车辆轨迹数据，便于实践；区别于一般的有障碍寻路方法，概率寻路数值更加精确，会发现一般寻路算法找不到的路线；强化学习作为启发式算法考虑寻路的耗时和通畅，以此获得全局最优解，增加了寻路算法的准确性。
1.一种基于强化学习的路径导航方法，其特征在于，该方法包括以下步骤：S1.根据城市的地图数据，构建所述城市的道路邻接关系图；
S2.根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
S3.以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
S4.基于强化学习生成导航路径，所述强化学习的状态空间包括所述道路拥塞概率图；
S401.规定状态空间为包括城市道路拥塞概率图和时间的三维空间，规定动作为从当前所在顶点选择一条相邻边到达下一个顶点，规定奖励函数为从起始点到当前顶点的路径所耗时间的期望；
S402.选取动作的策略为对于某一顶点，选取到达该点耗时期望最小的边作为到达该点的方向；
S403.扩展到终点后，访问其父节点直到回到起始点，起始点到终点的路线即为导航路径。
2.如权利要求1所述路径导航方法，其特征在于，所述道路邻接关系图中，顶点为道路的公共端点，边为道路，每个顶点都保存了它能到达的其他顶点的集合。
3.如权利要求1所述的路径导航方法，其特征在于，步骤S2包括以下步骤：S201.将车辆的轨迹数据映射到道路邻接关系图中，建立车辆轨迹数据与道路的对应关系；
S202.根据当前道路的道路类型计算当前道路的拥塞指数。
4.如权利要求3所述的路径导航方法，其特征在于，所述步骤S201具体包括以下步骤：(1)提取车辆轨迹的拐点；
(2)计算拐点与道路邻接关系图中边的垂直距离，求得距离最小的边作为当前边；
(4)按时间顺序，利用前后拐点间的距离和拐点间的时间差，计算轨迹拐点间的速度，作为出租车在当前小时在该路段的速度。
5.如权利要求3所述的路径导航方法，其特征在于，步骤S202具体包括以下步骤：(1)设定不同道路类型的对应权重；
(2)利用在当前路段的每个小时的平均车速和通过的车辆数目、所在道路类型对应权重、行程时间比，预测当前道路在不同时段的拥塞指数。
6.如权利要求1所述的路径导航方法，其特征在于，步骤S3包括以下步骤：S301.将拥塞指数通过Logistic函数转换成当前时刻拥塞概率；
S302.将拥塞概率映射到道路邻接关系图的边进行加权，生成每个小时的城市道路拥塞概率图。
7.一种基于强化学习的路径导航系统，该系统包括服务端和客户端，其特征在于，所述服务端包括：道路邻接关系图构建模块、拥塞指数预测模块、道路拥塞概率图构建模块和导航路径生成模块；
所述道路邻接关系图构建模块，用于根据城市的地图数据，构建所述城市的道路邻接关系图；
所述拥塞指数预测模块，用于根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
所述道路拥塞概率图构建模块，用于以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
所述导航路径生成模块，用于基于强化学习生成导航路径，并发送给客户端进行路径导航，所述强化学习的状态空间包括所述道路拥塞概率图；
所述客户端包括：导航模块、指南模块和轨迹数据提取模块；
所述指南模块，用于根据导航路径和轨迹数据，指示车主当前位置和前进方向；
(1)规定状态空间为包括城市道路拥塞概率图和时间的三维空间，规定动作为从当前所在顶点选择一条相邻边到达下一个顶点，规定奖励函数为从起始点到当前顶点的路径所耗时间的期望；
(2)选取动作的策略为对于某一顶点，选取到达该点耗时期望最小的边作为到达该点的方向；
(3)扩展到终点后，访问其父节点直到回到起始点，起始点到终点的路线即为导航路径。
8.如权利要求7所述的路径导航系统，其特征在于，所述客户端的轨迹数据提取模块还用于将获取到的轨迹数据实时反馈给所述服务端的拥塞指数预测模块。
9.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至6任一项所述的路径导航方法。
一种基于强化学习的路径导航方法及系统
技术领域
[0001] 本发明属于路径导航技术领域，更具体地，涉及一种基于强化学习的路径导航方法及系统。
背景技术
[0002] 手机导航寻找有效的驾车路线已成为日常。好的行驶路线不仅可以节省驾驶员的时间，还可以节省能源消耗。GPS设备的广泛使用让我们可以很容易的获取城市的道路详细信息如汽车流量，速度等。这些数据对路径导航有着极其重要的指导作用。
[0003] 现有技术中，专利CN108847037A公开了一种面向非全局信息的城市路网路径规划方法，其通过强化学习使得路网对车流量的分配具有自适应调整的能力，因此路网状态处于流量均衡状态。然而该方法中的A*R寻路算法在估价函数中对当前位置到目标位置的所用时间的估计所用方法比较粗糙，精度不足，同时时空复杂度很高。严丽平等人提出城市交通路网动态实时多路口路径选择模型，结合车辆对前方可选路线的偏好及可选路线的实时交通状态，并利用自适应学习算法进行博弈，以使得各行驶车辆的动态路线选择策略达到Nash均衡。然而，该方法存在应用场景需要多种假设(如每个车辆都是按照某一个固定概率彼此独立进行路径选择，并且每个车辆都可以观察到其他车辆的路径选择)，考虑的因素过多(如道路照明，道路平坦程度等难以衡量的指标)，在实践中存在困难的缺陷。
[0004] 综上所述，现有的基于强化学习的路径导航方法均存在算法的应用场景需要多种假设作为前提，时空复杂度太高的问题。
发明内容
[0005] 针对现有技术的缺陷，本发明的目的在于优化现有技术在寻路算法上前置条件多，决策函数不够完善的问题。
[0006] 为实现上述目的，第一方面，本发明实施例提供了一种基于强化学习的路径导航方法，该方法包括以下步骤：
[0007] S1.根据城市的地图数据，构建所述城市的道路邻接关系图；
[0008] S2.根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
[0009] S3.以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
[0010] S4.基于强化学习生成导航路径，所述强化学习的状态空间包括所述道路拥塞概率图。
[0011] 具体地，所述道路邻接关系图中，顶点为道路的公共端点，边为道路，每个顶点都保存了它能到达的其他顶点的集合。
[0012] 具体地，步骤S2包括以下步骤：
[0013] S201.将车辆的轨迹数据映射到道路邻接关系图中，建立车辆轨迹数据与道路的对应关系；
[0014] S202.根据当前道路的道路类型计算当前道路的拥塞指数。
[0015] 具体地，所述步骤S201具体包括以下步骤：
[0016] (1)提取车辆轨迹的拐点；
[0017] (2)计算拐点与道路邻接关系图中边的垂直距离，求得距离最小的边作为当前边；
[0018] (3)将拐点映射到与当前边最靠近的顶点；
[0019] (4)按时间顺序，利用前后拐点间的距离和拐点间的时间差，计算轨迹拐点间的速度，作为出租车在当前小时在该路段的速度。
[0020] 具体地，步骤S202具体包括以下步骤：
[0021] (1)设定不同道路类型的对应权重；
[0022] (2)利用在当前路段的每个小时的平均车速和通过的车辆数目、所在道路类型对应权重、行程时间比，预测当前道路在不同时段的拥塞指数。
[0023] 具体地，步骤S3包括以下步骤：
[0024] S301.将拥塞指数通过Logistic函数转换成当前时刻拥塞概率；
[0025] S302.将拥塞概率映射到道路邻接关系图的边进行加权，生成每个小时的城市道路拥塞概率图。
[0026] 具体地，步骤S4包括以下步骤：
[0027] S401.规定状态空间为包括城市道路拥塞概率图和时间的三维空间，规定动作为从当前所在顶点选择一条相邻边到达下一个顶点，规定奖励函数为从起始点到当前顶点的路径所耗时间的期望；
[0028] S402.选取动作的策略为对于某一顶点，选取到达该点耗时期望最小的边作为到达该点的方向；
[0029] S403.扩展到终点后，访问其父节点直到回到起始点，起始点到终点的路线即为导航路径。
[0030] 为实现上述目的，第二方面，本发明实施例提供了一种基于强化学习的路径导航系统，该系统包括服务端和客户端，
[0031] 所述服务端包括：道路邻接关系图构建模块、拥塞指数预测模块、道路拥塞概率图构建模块和导航路径生成模块；
[0032] 所述道路邻接关系图构建模块，用于根据城市的地图数据，构建所述城市的道路邻接关系图；
[0033] 所述拥塞指数预测模块，用于根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
[0034] 所述道路拥塞概率图构建模块，用于以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
[0035] 所述导航路径生成模块，用于基于强化学习生成导航路径，并发送给客户端进行路径导航，所述强化学习的状态空间包括所述道路拥塞概率图；
[0036] 所述客户端包括：导航模块、指南模块和轨迹数据提取模块；
[0037] 所述导航模块，用于从服务端获取导航路线；
[0038] 所述轨迹数据提取模块，用于获取车辆的轨迹数据；
[0039] 所述指南模块，用于根据导航路线和轨迹数据，指示车主当前位置和前进方向。
[0040] 具体地，所述客户端的轨迹数据提取模块还可以将获取到的轨迹数据实时反馈给所述服务端的拥塞指数预测模块。
[0041] 为实现上述目的，第三方面，本发明实施例提供了一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，该计算机程序被处理器执行时实现上述第一方面所述的路径导航方法。
[0042] 总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下有益效果：
[0043] 1.本发明将城市道路拥塞情况在数值化的基础上进行概率化。在客户端展示道路情况时，城市道路是否拥塞的概率比起数值给人更直观的理解，便于可视化。同时本发明的道路拥塞情况计算只利用了道路状况和历史车辆轨迹数据，便于实践。
[0044] 2.本发明设计了基于强化学习的寻路算法。作为一种概率寻路方式，区别于一般的有障碍寻路除了能走和不能走没有其他选项，概率寻路因为数值更加精确，会发现一般寻路算法找不到的路线。强化学习作为启发式算法会从总体的角度考虑寻路的耗时和通畅程度，以此获得全局最优解，而不像A*算法需要对当前位置到目标位置进行估计，因此增加了寻路算法的准确性。
附图说明
[0045] 图1为本发明实施例提供的一种基于强化学习的路径导航方法流程图；
[0046] 图2为本发明实施例提供的一种基于强化学习的路径导航系统结构示意图。
具体实施方式
[0047] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0048] 如图1所示，一种基于强化学习的路径导航方法，该方法包括以下步骤：
[0049] S1.根据城市的地图数据，构建所述城市的道路邻接关系图；
[0050] S2.根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
[0051] S3.以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
[0052] S4.基于强化学习生成导航路径，所述强化学习的状态空间包括所述道路拥塞概率图。
[0053] 步骤S1.根据城市的地图数据，构建所述城市的道路邻接关系图。
[0054] 本发明实施例使用的地图数据为OpenStreetMap。地图数据包含：道路id、道路类型、是否可以双向行驶及当前道路包含的端点集合。每个端点都有经纬度信息。每个端点能被多条道路共用。通过端点我们可以获得道路的邻接关系，也可以计算道路的长度。构建道路邻接关系图的目的是获得路网信息，以便将车辆的轨迹数据映射到真实的道路上，以此进行道路交通情况的预测和导航。
[0055] S101.从地图数据中提取道路信息。
[0056] 从OpenStreetMap中提取道路信息，所述道路信息包括道路邻接信息、道路类型和道路长度。其中，道路类型包括：高速公路，支路，一级道路，二级道路，三级道路，居民区。
[0057] S102.根据道路信息，构建道路邻接关系图。
[0058] 根据道路端到端邻接关系，构建道路邻接关系图。所述道路邻接关系图中，顶点为道路的公共端点，边为道路，每个顶点都保存了它能到达的其他顶点的集合。这是一个有向图。
[0059] 步骤S2.根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数。
[0060] 车辆轨迹数据既可以是实时采集，也可以是离线数据集。所述轨迹数据包括：轨迹id、车辆id、车辆当前所在经度、车辆当前所在纬度、当前时间信息。车辆可以是出租车、私家车等等。
[0061] 在预测拥塞指数之前，可以对收集到的轨迹数据进行数据清洗。所述数据清洗是指剔除重复或缺失的轨迹数据。由于存在GPS信号中断或车辆行驶到交叉路口等情形，GPS接收器在某时刻会短时间内持续收集大量相同或相近的冗余数据。这些冗余数据会直接降低了算法运行的效率。当车辆在在建筑物、树林中活动或者GPS信号中断，使用基站定位等其他定位方法时，车辆的定位会出现漂移，产生大量的噪声点，造成轨迹的失真。因此，需要去除冗余数据和漂移数据，从而修正轨迹数据。
[0062] S201.将车辆的轨迹数据映射到道路邻接关系图中，建立车辆轨迹数据与道路的对应关系。具体包括以下步骤：
[0063] (1)提取车辆轨迹的拐点。
[0064] 车辆轨迹的拐点即为车辆的特征点。
[0065] (2)计算拐点与道路邻接关系图中边的垂直距离，求得距离最小的边作为当前边。
[0066] (3)将拐点映射到与当前边最靠近的顶点。
[0067] 拐点对应的图的顶点确定后，出租车轨迹段对应的边也就确定了。
[0068] (4)按时间顺序，利用前后拐点间的距离和拐点间的时间差，计算轨迹拐点间的速度，作为出租车在当前小时在该路段的速度。
[0069] S202.根据当前道路的道路类型计算当前道路的拥塞指数。
[0070] (1)设定不同道路类型的对应权重。
[0071]道路类型 高速公路、支路 一级公路 二级公路 三级公路 居民区
权重 5 4 3 1 0.5
[0072] (2)利用在当前路段的每个小时的平均车速和通过的车辆数目、所在道路类型对应权重、行程时间比(路段长度除以当前车辆走完该路段的时间)，预测当前道路在不同时段的拥塞指数。
[0073] 预测模型可以是神经网络模型、决策树或者Logistic回归。同一路段在不同时段的拥塞情况是不同的，比如，工作日和休息日，上下班高峰期和其他时间段。对当前城市的每条道路都进行预测，实现预测全城的时间粒度为一小时的道路拥塞指数。拥塞指数用于反映道路环境。
[0074] 步骤S3.以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图。
[0075] 在预测道路拥塞指数后，我们得到了未来一段时间内城市道路的交通情况，以此生成城市道路拥塞概率图，包括以下步骤：
[0076] S301.将拥塞指数通过Logistic函数转换成当前时刻拥塞概率。
[0077] S302.将拥塞概率映射到道路邻接关系图的边进行加权，生成每个小时的城市道路拥塞概率图。
[0078] 所述城市道路拥塞概率图包括以下内容：顶点表示路段与路段的交叉点，边表示路段，每条边包含拥塞概率，道路长度。城市道路拥塞概率图以道路邻接关系图为基础，增加了以下内容：当前时间，每条边在当前时间的拥塞概率。
[0079] 步骤S4.基于强化学习生成导航路径，所述强化学习的状态空间包括所述道路拥塞概率图。
[0080] S401.规定状态空间为包括城市道路拥塞概率图和时间的三维空间，规定动作为从当前所在顶点选择一条相邻边到达下一个顶点，规定奖励函数为从起始点到当前顶点的路径所耗时间的期望。
[0081] S402.选取动作的策略为对于某一顶点，选取到达该点耗时期望最小的边作为到达该点的方向。
[0082] 对于顶点来说，有多个方向可以到达该点。选取到达该点耗时期望最小的方向作为该顶点的父节点。经过贪心价值迭代，对于任意一点来说，从起始点到该点的路径都是耗时最短的路径。
[0083] S403.扩展到终点后，访问其父节点直到回到起始点，起始点到终点的路线即为导航路径。
[0084] 如图2所示，一种基于强化学习的路径导航系统，该系统包括服务端和客户端，[0085] 所述服务端包括：道路邻接关系图构建模块、拥塞指数预测模块、道路拥塞概率图构建模块和导航路径生成模块；
[0086] 所述道路邻接关系图构建模块，用于根据城市的地图数据，构建所述城市的道路邻接关系图；
[0087] 所述拥塞指数预测模块，用于根据车辆轨迹数据和道路邻接关系图，预测所述城市不同路段不同时段的拥塞指数；
[0088] 所述道路拥塞概率图构建模块，用于以道路邻接关系图为基础，根据拥塞指数构建所述城市的道路拥塞概率图；
[0089] 所述导航路径生成模块，用于基于强化学习生成导航路径，并发送给客户端进行路径导航，所述强化学习的状态空间包括所述道路拥塞概率图。
[0090] 所述客户端包括：导航模块、指南模块和轨迹数据提取模块。
[0091] 所述导航模块，用于从服务端获取导航路线；
[0092] 所述轨迹数据提取模块，用于获取车辆的轨迹数据；
[0093] 所示指南模块，用于根据导航路线和轨迹数据，指示车主当前位置和前进方向。
[0094] 所述服务端还可以包括数据清洗模块，用于在预测拥塞指数之前，对轨迹数据进行数据清洗，剔除重复或缺失的轨迹数据。
[0095] 所述客户端的轨迹数据提取模块还可以将获取到的轨迹数据实时反馈给所述服务端的拥塞指数预测模块。
[0096] 仅为本申请较佳的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应该以权利要求的保护范围为准。
