一种基于强化学习策略迭代技术的城市路网路径规划方法

1.本发明涉及智能交通技术领域，具体来说是一种基于强化学习策略迭代技术的城市路网路径规划方法。


背景技术：

2.随着我国经济的不断发展与城市化的进程不断加快，城市交通拥堵已经是一件非常严重的问题，随之而来的是越来越严重的环境污染、额外的出行时间、不必要的能源消耗等严重问题。对车辆进行分流以及进行高效完整的路径规划来解决交通拥堵具有十分重要的意义。路径规划算法在国内外早已深入研究，如基于图的启发式算法(a*)、基于适应度函数的智能仿生学算法(遗传算法)、蚁群算法等。但在复杂城市路网环境下，这些算法往往存在启发函数设计与初始解空间生成困难等缺点，从而影响算法的执行效率。
3.基于强化学习策略迭代路径规划方法在环境状态信息(路网结构)已知的条件下进行路径探索，智能体无需对环境信息进行采样，通过与路网环境的交互直接对两种价值函数(状态价值函数和动作价值函数)与行为策略进行迭代求解和优化，因此具有执行效率高、收敛性好的特点，非常适合于城市路网环境下的路径规划研究与实际应用。
4.现有技术中，《ieee transactions on intelligent transportation system》涉及一篇基于强化学习策略迭代方法的路径规划论文：urban multiple route planning model using dynamic programming in reinforcement learning，但是原方法在极端路网环境下的收敛性存在一定问题，导致路径探索失败。
5.针对这一问题，如何使方法在极端路网环境下(道路通行压力为0)能够收敛，如何揭示关键超参数的取值及其相互关系的规律，从根本上解决路径规划问题的稳定性，已经成为急需解决的技术问题。


技术实现要素：

6.本发明的目的是为了解决现有技术中极端路网环境下难以保证路径规划方法稳定收敛的缺陷，提供一种基于强化学习策略迭代技术的城市路网路径规划方法来解决上述问题。
7.为了实现上述目的，本发明的技术方案如下：
8.一种基于强化学习策略迭代技术的城市路网路径规划方法，包括以下步骤：
9.11)城市路网数据模型的构建：获取路网数据并进行预处理，建立路网数据与路网环境的拓扑关系，构建出城市路网数据模型；
10.12)路网环境中强化学习模型要素的设计：基于城市路网数据模型中的路网环境，根据智能体是否到达终点对奖励函数进行详细设计；
11.13)正常状态下城市路网最优路径的生成：基于奖励函数要素引导智能体向终点探索，并利用强化学习策略迭代方法生成最优路径；
12.14)城市极端路网环境下最优路径的生成：在路网通行压力全为0的极端路网环境
下，由于基于强化学习策略迭代的路径规划方法存在收敛性问题，故分析强化学习策略迭代方法收敛的充分条件以及关键超参数，即折扣因子γ和finalreward的取值及其相互关系对收敛性的影响，以此收敛充分条件和超参数取值关系对强化学习策略迭代的路径规划方法进行优化，在极端路网环境下生成最优路径。
13.所述城市路网数据模型的构建包括以下步骤：
14.21)利用城市路网矢量图，将所有道路在交汇处进行打断，并在打断处添加结点；
15.22)设定结点crossing代表路口、每两个结点之间的弧段代表路段link，并将路网通行压力考虑在内，将城市路网数据模型抽象为无向图；
16.23)设定城市路网数据模型包括：
17.结点集合v：v＝{crossing1，crossing2，crossing3，...，crossingn}，
18.路段集合e：e＝{link1，link2，link3，...，linkn}；
19.其中，路段集合的属性包括：路段编号、路段通行压力指数、路段里程；结点集合属性包括：路口编号、相连路段编号、相关联路口编号；
20.将路网通行压力设置为0、1、2、3、4这五个等级，分别代表通畅、基本通畅、缓行、拥堵、严重拥堵。
21.所述路网环境中强化学习模型组成要素的设计包括以下步骤：
22.31)设计城市路网环境中的强化学习模型组成要素，设定如下：
23.智能体指路网环境中车辆的驾乘人员，其行为目标是从起点以最短的通勤时间抵达终点：状态空间s表示城市路网中的各个路口；动作空间a为驾驶员采取的行动，即智能体在每个路口的可行驶方向，动作空间a个数为3-6个；状态转移概率p是智能体在某个路口选择一个行驶方向动作时跳转到下一个路口的概率；在城市道路路径规划这一场景条件下，状态转移概率均为1，即当在某个路口选定一个方向行驶后，下个路口也随之确定；奖励函数r是指智能体对从始点到终点所获得的奖励；
24.32)进行奖励函数r的设计，奖励函数r根据智能体是否到达终点分为两种情况：
25.321)当智能体到达终点时设计的奖励函数为：
26.r＝move_utility*linklength+congestion_penalty*pressure+finalreward，
27.其中，move_utility是智能体移动单位距离付出的代价，congestion_penalty是道路拥堵惩罚，finalreward是到达终点的奖励，linklength表示路段长度，pressure表示路段通行压力；
28.322)当智能体到达某一路口时，奖励函数设计为：
29.r＝move_utility*linklength+distance_reward*dci+congestion_penalty*pressure，
30.其中，distance_reward用于判断智能体有无向终点目标前进，其取值分为两种：
[0031][0032]
dci表示距离贡献指数，用来衡量智能体通过某一路段后对缩短当前路口与终点距离的贡献，是当前路口与终点的直线距离和下个路口与终点的直线距离差的绝对值与路段长度的比值；
[0033]
其中，设定move_utility取值-0.00002，congestion_penalty取值-3.2，折扣因子γ为1，finalreward取值20。
[0034]
所述正常状态下城市路网最优路径的生成包括以下步骤：
[0035]
41)借助贝尔曼方程，重复利用策略评估和策略优化两个步骤，得到收敛的最优路径，其中贝尔曼方程表示如下：
[0036][0037][0038]
其中，v(s)表示状态价值函数，即智能体从状态s开始所能获得的未来收益的期望；q(s,a)状态动作价值函数，表示智能体从状态s开始，执行动作a之后所能获得的未来收益的期望；
[0039]
其中，s表示所有的状态集合，a为所有的动作集合，s0指初始状态，s’是指下一个状态，a’表示下一个动作；
[0040]
其中r(s'|s,a)为当前状态s采取动作a后到达下个状态s’的奖励，即为步骤32)所设计的及时奖励函数r，π(a|s)表示状态s下智能体的策略，表示采取动作a后从当前状态s到下一状态s’的概率，由于从当前路口选择行为a之后到达下个路口是确定的，故γ为折扣因子，表示对未来奖励的折扣度，γ∈[0,1]；故上述两个方程简写为：
[0041]
v(s)＝r(s'|s,a)+γv(s')，
[0042]
q(s,a)＝r(s'|s,a)+γq(s'|a')；
[0043]
42)设定策略迭代具体步骤如下：
[0044]
421)对策略迭代的参数进行初始化，
[0045]
初始化所有路口的状态价值函数v(s)＝0，设置所有路口各个方向的动作价值q(s,a)＝0，并且所有状态转移概率p＝1，折扣因子γ＝1，初始化随机策略π(a1|s)＝π(a2|s)＝
…
＝π(an|s)＝1/n,n∈{1,2,3,4,5,6}；
[0046]
422)对所有状态即路口利用贝尔曼方程进行策略评估：对当前执行策略进行一次简单评估，并选择当前路口各个方向q(s,a)的最大值来更新该路口的状态价值函数v(s)，其表达式如下：
[0047]
v(s)＝maxq(s,a)；
[0048]
423)进行策略优化：根据智能体有无到达终点选择奖励函数r并赋值贝尔曼方程中r(s'|s,a)来计算所有路口各个方向的动作价值函数q(s,a)；对于所有路口，选择动作价值函数q(s,a)最大值对应的方向作为新的策略π(a|s)；
[0049]
424)重复步骤422)、423)步骤，对所得的新策略再次进行评估，并在此基础上再进行策略优化，直至方法收敛；
[0050]
425)从起点开始，将每个路口最大动作价值函数q(s,a)所对应的方向依次连接起来，所得的路径即为最优路径。
[0051]
所述城市极端路网环境下最优路径的生成包括以下步骤：
[0052]
51)路网结点分层级设计与层级结点的状态动作价值函数q(s,a)取值设计：
[0053]
设计一级连接点表示为从终点所连接的第一个最短路径结点，二级连接点是一级连接点的下个结点且非终点，除一级连接点外，其他结点都表示一般结点；
[0054]
其中，一级连接点q(s,a)表示为：
[0055][0056]
一般连接点q(s,a)表示为：
[0057][0058]
令r
t_directopti
＝move_utility*linklength+distance_reward*dci；
[0059]
其中，r
t_directopti
表示方向最优路口，它是指distance_reward*dci取值最大的路口，即越朝向终点的路口；其中distance_reward作用是判断智能体有无向终点目标前进，dci表示距离贡献指数；move_utility是智能体移动单位距离所要付出的代价，congestion_penalty是道路拥堵惩罚，finalreward是到达终点的奖励，linklength表示路段长度，pressure表示路网通行压力，γ表示折扣因子，v(s)为状态价值函数；
[0060]
52)根据51)各层级结点q(s,a)的设计，设定算法的收敛类型以及路网通行压力为0时，即将pressure取值为0的情况下各类型收敛的充分条件设计：
[0061]
521)严格收敛：
[0062]
若当前路口为一级连接点，该结点的状态价值函数v(s)满足下式，
[0063]
v(s)＝maxq(s,a)＝linklength*move_utility+finalreward《finalreward；
[0064]
若当前路口为一般连接点，该结点的状态价值函数v(s)满足下式，
[0065]
v(s)＝maxq(s,a)＝r
t_directopti
+γ*v(s’)《v(s’)《finalreward；
[0066]
其中，maxq(s,a)表示最大动作价值函数，move_utility是智能体移动单位距离所要付出的代价，finalreward是到达终点的奖励，linklength表示路段长度,γ表示折扣因子，v(s’)为下个状态s’的状态价值函数；r
t_directopti
表示方向最优路口，即越朝向终点的路口的奖励；
[0067]
在迭代过程中所有路口在任何一个回合都满足上述条件时，方法严格收敛；
[0068]
522)一般收敛：
[0069]
若当前路口为一级连接点，该结点的状态价值函数v(s)满足下式，
[0070]
v(s)＝maxq(s,a)＝linklength*move_utility+finalreward《finalreward；
[0071]
若当前路口为一般连接点，该结点的状态价值函数v(s)满足下式，
[0072]
v(s’)max
–
v(s’)
t_directopti
《r
t_directopti
；
[0073]
即当前路口有若干个下一路口，s’表示下一路口；
[0074]
在这些下一路口中，v(s’)最大路口与方向最优路口v(s’)的差要小于r
t_directopti
；
[0075]
其中，maxq(s,a)表示最大动作价值函数，move_utility是智能体移动单位距离所要付出的代价，finalreward是到达终点的奖励，v(s’)
max
为下一状态的最大状态价值函数，v(s’)
t_directopti
为下一状态方向最优的状态价值函数，rt_
directopti
表示方向最优路口，即越朝向终点的路口的奖励；
[0076]
在迭代过程中所有路口在任何一个回合都满足上述条件时，方法一般收敛；
[0077]
523)无法收敛：
[0078]
即无法探索到一条从起点到终点的最优路径，在迭代过程中，一般连接点的状态价值函数v(s)在任何一个回合都不满足一般收敛的表达式，一级连接点在迭代若干回合后亦无法满足严格收敛的表达式；
[0079]
53)在极端路网环境下，即路段通行压力为0时，各结点的状态价值函数v(s)来源于finalreward；同时，在上述环境下，根据332)对奖励函数超参数的取值导致基于策略迭代的路径规划方法无法收敛；
[0080]
利用52)中设计的方法收敛的充分条件，对finalreward与折扣因子γ的取值重新进行设计；设定在收敛条件满足的前提下，
[0081]
当move_utility与distance_reward保持不变时，finalreward值越大，折扣因子取值也相应增大，折扣因子γ无限趋近于1，但不等于1；
[0082]
54)设move_utility取值为-0.00002，distance_reward在智能体朝向终点行驶取值为0.8、否则为-0.8；设finalreward为20、γ为0.98或finalreward为100、γ为0.99，以此为满足收敛条件的超参数组合；该超参数取值的组合能够确保在极端状态下生成一条从起点到终点的最优路径。
[0083]
有益效果
[0084]
本发明的一种基于强化学习策略迭代技术的城市路网路径规划方法，与现有技术相比通过对极端路网环境下(通行压力为0)路径规划方法的收敛性问题进行改进与优化，探索了方法在上述环境下的收敛条件和关键超参数取值的相互关系，利用启发性知识减少了奖励函数要素取值设计的随机性，保证了在任何路网环境下都能够迅速地探索到最优路径。
[0085]
本发明对原始策略迭代路径规划方法鲁棒性上的缺陷进行改进与优化，探索了方法的严格收敛条件，揭示方法中关键超参数取值的相互关系，从根本上提升了强化学习策略迭代路径规划方法的稳定性。
附图说明
[0086]
图1为本发明的方法顺序图；
[0087]
图2为本发明所涉及的策略迭代方法实现的路径规划图；
[0088]
图3为本发明所涉及的一二级连接点示意图；
[0089]
图4为本发明所涉及的研究区部分路网图。
具体实施方式
[0090]
为使对本发明的结构特征及所达成的功效有更进一步的了解与认识，用以较佳的实施例及附图配合详细的说明，说明如下：
[0091]
如图1所示，本发明所述的一种基于强化学习策略迭代技术的城市路网路径规划方法，包括以下步骤：
[0092]
第一步，城市路网数据模型的构建：获取路网数据并进行预处理，建立路网数据与路网环境的拓扑关系，构建出城市路网数据模型。
[0093]
所述城市路网数据模型的构建包括以下步骤：
[0094]
(1)利用城市路网矢量图，将所有道路在交汇处进行打断，并在打断处添加结点。
[0095]
(2)设定结点crossing代表路口、每两个结点之间的弧段代表路段link，并将路网通行压力考虑在内，将城市路网数据模型抽象为无向图。
[0096]
(3)设定城市路网数据模型包括：
[0097]
结点集合v：v＝{crossing1,crossing2,crossing3,...，crossingn}，
[0098]
路段集合e：e＝{link1,link2,link3,...，linkn}；
[0099]
其中，路段集合的属性包括：路段编号、路段通行压力指数、路段里程；结点集合属性包括：路口编号、相连路段编号、相关联路口编号；
[0100]
将路网通行压力设置为0、1、2、3、4这五个等级，分别代表通畅、基本通畅、缓行、拥堵、严重拥堵。
[0101]
第二步，路网环境中强化学习模型要素的设计：基于城市路网数据模型中的路网环境，根据智能体是否到达终点对奖励函数进行详细设计。
[0102]
基于城市路网环境中强化学习模型要素设计，
[0103]
1、智能体：环境内车辆的驾乘人员，其行为目标是从起点以最短的通勤时间抵达终点；
[0104]
2、状态空间s：状态空间s表示城市路网中的各个路口；
[0105]
3、动作空间a：驾驶员采取的行动，即智能体在每个路口的可行驶方向。一般而言，动作空间个数一般为3-6个；
[0106]
4、状态转移概率p：智能体在某个路口选择一个动作时(行驶方向)，跳转到下一个路口的概率。在城市道路路径规划这一场景条件下，状态转移概率均为1，即当在某个路口选定一个方向行驶后，下个路口也随之确定。
[0107]
5、奖励函数r：路径规划任务中的奖励函数是指智能体对从始点到终点所获得的奖励，本发明利用研究人员的研究经验以及专业知识对奖励函数进行详细设计。
[0108]
在奖励函数r具体设计中，本发明对奖励函数进行详细设计来提升智能体对路径的探索能力。在第一步构建的路网环境下，奖励函数根据智能体是否到达终点分为两种情况：
[0109]
(1)当智能体到达终点时设计的奖励函数为：
[0110]
r＝move_utility*linklength+congestion_penalty*pressure+finalreward
ꢀꢀꢀ
(1)
[0111]
(2)当智能体到达某一路口时设计的奖励函数：
[0112]
r＝move_utility*linklength+distance_reward*dci+congestion_penalty*pressure
ꢀꢀꢀ
(2)
[0113]
其中move_utility表示行驶单位距离惩罚数，linklength表示路段长度，congestion_penalty表示道路拥堵惩罚，pressure表示通行压力，finalreward为智能体到达终点时的奖励。
[0114]
其中distance_reward作用是判断智能体有无向终点目标前进，其取值分为两种：
[0115]
[0116]
dci(distance_contribution_index)表示距离贡献指数，用来衡量智能体通过某一路段后对缩短当前路口与终点距离的贡献，是当前路口与终点的直线距离和下个路口与终点的直线距离差的绝对值与路段长度的比值。
[0117]
根据以有经验对以上奖励函数要素进行初始化：基于强化学习策略迭代路径规划方法超参数的取值，上述要素的取值如表1所示。
[0118]
表1超参数的取值表
[0119][0120]
第三步，正常状态下城市路网最优路径的生成：基于奖励函数要素引导智能体向终点探索，并利用强化学习策略迭代方法生成最优路径。
[0121]
本发明采用强化学习策略迭代方法进行路径规划，其主要思想就是借助贝尔曼方程，具体表现形式为(式3和式4)，重复使用策略评估和策略优化两个步骤，最终得到收敛的最优路径的过程。
[0122][0123][0124]
所述s表示所有的状态集合，a为所有的动作集合，s0指初始状态，s’是指下一个状态，a’表示下一个动作。其中r(s'|s,a)为当前状态s采取动作a后到达下个状态s’的奖励，即为第二步骤设计的奖励函数r，π(a|s)表示表示状态s下智能体的策略，，表示采取动作a后从当前状态s到下一状态s’的概率，由于从当前路口选择行为a之后到达下个路口是确定的，故γ为折扣因子，表示对未来奖励的折扣度，γ∈[0,1]；所以上述两个方程可以简写为：
[0125]
v(s)＝r(s'|s,a)+γv(s')
ꢀꢀꢀ
(5)
[0126]
q(s,a)＝r(s'|s,a)+γq(s'|a')
ꢀꢀꢀ
(6)
[0127]
强化学习策略迭代实现路径规划具体步骤如下：
[0128]
1、对策略迭代的相关参数进行初始化
[0129]
初始化所有路口的状态价值函数v(s)＝0；设置所有路口各个方向的动作价值q(s,a)＝0；并且所有状态转移概率p＝1；折扣因子γ＝1；初始化随机策略π(a1|s)＝π(a2|s)＝
…
＝π(an|s)＝1/n,n∈{1,2,3,4,5,6}。
[0130]
2、对所有状态(路口)利用贝尔曼方程进行策略评估：对当前执行策略进行一次简单评估，并选择当前路口各个方向q(s,a)的最大值来更新该路口的状态价值函数v(s)。
[0131]
v(s)＝maxq(s,a)
ꢀꢀꢀ
(7)
[0132]
3、策略优化：根据智能体有无到达终点选择奖励函数r并赋值式(3)中r(s'|s,a)来计算所有路口各个方向的动作价值函数q(s,a)。对于所有路口，选择动作价值函数q(s,a)最大值对应的方向作为新的策略π(s|a)。
[0133]
4、重复以上步骤2、步骤3，对所得的策略再次进行评估，并在此基础上再进行策略优化，直至方法收敛。
[0134]
5、从起点开始，将每个路口最大动作价值函数q(s,a)所对应的方向依次连接起来，所得的路径即为最优路径，如图2所示。
[0135]
第四步，极端路网环境下城市路网最优路径的优化生成：在路网通行压力全为0的极端路网环境下，基于强化学习策略迭代的路径规划方法存在收敛性问题，分析强化学习策略迭代方法收敛的充分条件以及关键超参数，即折扣因子γ和finalreward的取值及其相互关系对收敛性的影响，以此收敛充分条件和超参数取值关系对强化学习策略迭代的路径规划方法进行优化，在极端路网环境下生成最优路径。具体步骤如下：
[0136]
(1)路网结点分层级设计与层级结点q(s,a)取值设计，
[0137]
路径探索结果与智能体在路口处动作(行驶方向)的选择密切相关，因此需要重点计算动作价值函数q(s,a)在不同情况下的取值。为表示清楚表示结点之间的层级关系，设计一级连接点表示为从终点所连接的第一个最短路径结点，二级连接点是一级连接点的下个结点(非终点)以此类推，除一级连接点外，其他结点都表示一般连接点。如下图3所示。
[0138]
其中一级连接点q(s,a)表示为：
[0139][0140]
一般连接点q(s,a)表示为：
[0141][0142]
令r
t_directopti
＝move_utility*linklength+distance_reward*dci。其中，r
t_directopti
表示方向最优路口，它是指distance_reward*dci取值最大的路口，即越朝向终点的路口。distance_reward作用是判断智能体有无向终点目标前进，dci表示距离贡献指数。
[0143]
其中v(s)为状态价值函数，move_utility是智能体移动单位距离所要付出的代价，congestion_penalty是道路拥堵惩罚，finalreward是到达终点的奖励，linklength表示路段长度，pressure表示路段通行压力,γ表示折扣因子。
[0144]
(2)所述方法的收敛类型以及路网拥堵压力为0时各类型收敛的充分条件设计。
[0145]
严格收敛：
[0146]
若当前路口为一级连接点，该节点的状态价值函数v(s)需要满足式(10)；若当前路口为一般连接点，该节点的状态价值函数v(s)需要满足式(11)。在迭代过程中所有路口在任何一个回合都满足上述条件时，方法严格收敛。
[0147]
v(s)＝maxq(s,a)＝linklength*move_utility+finalreward《finalreward
ꢀꢀꢀ
(10)
[0148]
v(s)＝maxq(s,a)＝r
t_directopti
+γ*v(s’)《v(s’)《finalreward
ꢀꢀꢀ
(11)。
[0149]
一般收敛：
[0150]
若当前路口为一级连接点，该节点的状态价值函数v(s)需要满足式(12)；若当前路口为一般连接点，该节点的状态价值函数v(s)需要满足式(13)。在迭代过程中所有路口在任何一个回合都满足上述条件时，方法一般收敛。
[0151]
v(s)＝maxq(s,a)＝linklength*move_utility+finalreward《finalreward
ꢀꢀꢀ
(12)
[0152]
v(s’)max
–
v(s’)
t_directopti
《r
t_directopti
ꢀꢀꢀ
(13)
[0153]
注：上式的含义是：当前路口有若干个下一路口，在这些下一路口中，v(s’)最大路口与方向最优路口v(s')的差要小于r
t_directopti
。
[0154]
其中v(s’)
max
为下个路口最大的状态价值函数，v(s’)
t_directopti
为下个路口最优的状态价值函数，move_utility是智能体移动单位距离所要付出的代价，finalreward是到达终点的奖励，linklength表示路段长度，γ表示折扣因子。
[0155]
无法收敛：
[0156]
方法无法收敛，即无法探索到一条从起点到终点的最优路径。在迭代过程中，一般连接点的状态价值函数v(s)在任何一个回合都不满足式(13)，一级连接点在迭代若干回合后亦无法满足式(12)。
[0157]
(3)奖励函数超参数finalreward与折扣因子γ组合取值优化设计
[0158]
在极端路网环境下(路段通行压力为0)，各节点的状态价值函数v(s)主要来源于finalreward。同时，由于在上述环境下，第二步中对奖励函数超参数的取值会导致原方法无法收敛。因此，以下将利用(1)提出的方法收敛的充分条件，对finalreward与折扣因子γ的取值重新进行设计。
[0159]
选取路网中一个实例(起始点：22.558n,114.111e，终点：22.706n,113.816e)进行说明，图4是截取的距离终点较近的部分路网，且假设智能体当前位置在路口crossing1233，其下一个节点为crossing1236(一级连接点)或crossing1266(一般连接点)。
[0160]
利用第二步奖励函数超参数初始化时的取值，并将折扣因子γ取值为0.95,0.98,0.99，当方法迭代20次后分别统计crossing1236或crossing1266的状态价值函数，并验证是否满足收敛条件，具体结果如表2所示。
[0161]
其中，
[0162]rt_directopti
＝linklength*-move_utility+distance_reward*dci＝0.701。
[0163]
表2不同折扣因子γ取值的方法测试结果对比表
[0164][0165][0166]
上述案例的结果表明，当奖励函数中超参数的为初始化值时，折扣因子γ≤0.98(精确到两位小数)，方法才能在路网通行压力为全为0这一极端下收敛。
[0167]
同样分别取finalreward为20,100,300,500，其它超参数取值不变，且折扣因子设为0.99。当方法迭代20次后分别统计crossing1236或crossing1266的状态价值函数，并验证是否满足收敛条件，具体结果如表3所示。
[0168]
表3 finalreward与折扣因子γ的关系对比表
[0169][0170]
可以得出在收敛条件满足的条件下，当move_utility与distance_reward保持不
变时，finalreward值越大，折扣因子取值也可以相应增大，折扣因子γ无限趋近于1(但不能等于1)。
[0171]
通过强化学习策略迭代路径规划方法中超参数对模型收敛性的实验分析，可知超参数折扣因子γ与finalreward对上述方法的收敛起到了决定性作用，并在收敛条件的约束下不再盲目对参数进行取值，而是利用相关发明规律进行取值以保证方法收敛，具体参数值设置如下：
[0172]
所述move_utility取值为-0.00002，所述distance_reward在智能体朝向终点行驶取值为0.8，否则为-0.8，所述finalreward与折扣因子γ取值是紧密相关的，因此可以设置为finalreward为20、γ为0.98或finalreward为100、γ为0.99等一些满足收敛条件的组合。
[0173]
实验结果分析如下：
[0174]
通过仿真实验表明，通过对参数组合取值优化设计，故本发明可以给出一些参数组合finalreward＝20,γ＝0.98；finalreward＝100,γ＝0.99均能在大型复杂路网环境下从起点到终点生成一条最优路径。
[0175]
由上述技术方案可知，
[0176]
本发明面向城市路网环境，利用强化学习策略迭代方法进行路径规划，并对奖励函数进行详细设计，包括：move_utility,congestion_penalty,distance_reward,finalreward等要素，使得智能体在一般路网环境下(存在道路通行压力)能够快速收敛。
[0177]
本发明为保证基于强化学习策略迭代的路径规划方法在任何路网环境中均能收敛，设计了该方法收敛的充分条件，并具体讨论了奖励函数中超参数finalreward和折扣因子γ的取值及其相互关系对方法收敛性的影响，最终归纳出该方法在收敛时各超参数的取值规律，避免了盲目取值对方法收敛性带来的负面影响，从而提高了该路径规划方法的鲁棒性。
[0178]
以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是本发明的原理，在不脱离本发明精神和范围的前提下本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明的范围内。本发明要求的保护范围由所附的权利要求书及其等同物界定。

技术特征：
1.一种基于强化学习策略迭代技术的城市路网路径规划方法，其特征在于，包括以下步骤：11)城市路网数据模型的构建：获取路网数据并进行预处理，建立路网数据与路网环境的拓扑关系，构建出城市路网数据模型；12)路网环境中强化学习模型要素的设计：基于城市路网数据模型中的路网环境，根据智能体是否到达终点对奖励函数进行详细设计；13)正常状态下城市路网最优路径的生成：基于奖励函数要素引导智能体向终点探索，并利用强化学习策略迭代方法生成最优路径；14)城市极端路网环境下最优路径的生成：在路网通行压力全为0的极端路网环境下，由于基于强化学习策略迭代的路径规划方法存在收敛性问题，故分析强化学习策略迭代方法收敛的充分条件以及关键超参数，即折扣因子γ和finalreward的取值及其相互关系对收敛性的影响，以此收敛充分条件和超参数取值关系对强化学习策略迭代的路径规划方法进行优化，在极端路网环境下生成最优路径。2.根据权利要求1所述的一种基于强化学习策略迭代技术的城市路网路径规划方法，其特征在于，所述城市路网数据模型的构建包括以下步骤：21)利用城市路网矢量图，将所有道路在交汇处进行打断，并在打断处添加结点；22)设定结点crossing代表路口、每两个结点之间的弧段代表路段link，并将路网通行压力考虑在内，将城市路网数据模型抽象为无向图；23)设定城市路网数据模型包括：结点集合v：v＝{crossing1，crossing2，crossing3，...，crossingn}，路段集合e：e＝{link1，link2，link3，...，linkn}；其中，路段集合的属性包括：路段编号、路段通行压力指数、路段里程；结点集合属性包括：路口编号、相连路段编号、相关联路口编号；将路网通行压力设置为0、1、2、3、4这五个等级，分别代表通畅、基本通畅、缓行、拥堵、严重拥堵。3.根据权利要求1所述的一种基于强化学习策略迭代技术的城市路网路径规划方法，其特征在于，所述路网环境中强化学习模型组成要素的设计包括以下步骤：31)设计城市路网环境中的强化学习模型组成要素，设定如下：智能体指路网环境中车辆的驾乘人员，其行为目标是从起点以最短的通勤时间抵达终点：状态空间s表示城市路网中的各个路口；动作空间a为驾驶员采取的行动，即智能体在每个路口的可行驶方向，动作空间a个数为3-6个；状态转移概率p是智能体在某个路口选择一个行驶方向动作时跳转到下一个路口的概率；在城市道路路径规划这一场景条件下，状态转移概率均为1，即当在某个路口选定一个方向行驶后，下个路口也随之确定；奖励函数r是指智能体对从始点到终点所获得的奖励；32)进行奖励函数r的设计，奖励函数r根据智能体是否到达终点分为两种情况：321)当智能体到达终点时设计的奖励函数为：r＝move_utility*linklength+congestion_penalty*pressure+finalreward，其中，move_utility是智能体移动单位距离付出的代价，congestion_penalty是道路拥堵惩罚，finalreward是到达终点的奖励，linklength表示路段长度，pressure表示路段
通行压力；322)当智能体到达某一路口时，奖励函数设计为：r＝move_utility*linklength+distance_reward*dci+congestion_penalty*pressure，其中，distance_reward用于判断智能体有无向终点目标前进，其取值分为两种：dci表示距离贡献指数，用来衡量智能体通过某一路段后对缩短当前路口与终点距离的贡献，是当前路口与终点的直线距离和下个路口与终点的直线距离差的绝对值与路段长度的比值；其中，设定move_utility取值-0.00002，congestion_penalty取值-3.2，折扣因子γ为1，finalreward取值20。4.根据权利要求1所述的一种基于强化学习策略迭代技术的城市路网路径规划方法，其特征在于，所述正常状态下城市路网最优路径的生成包括以下步骤：41)借助贝尔曼方程，重复利用策略评估和策略优化两个步骤，得到收敛的最优路径，其中贝尔曼方程表示如下：方程表示如下：其中，v(s)表示状态价值函数，即智能体从状态s开始所能获得的未来收益的期望；q(s,a)状态动作价值函数，表示智能体从状态s开始，执行动作a之后所能获得的未来收益的期望；其中，s表示所有的状态集合，a为所有的动作集合，s0指初始状态，s’是指下一个状态，a’表示下一个动作；其中r(s'|s,a)为当前状态s采取动作a后到达下个状态s’的奖励，即为步骤32)所设计的及时奖励函数r，π(a|s)表示状态s下智能体的策略，表示采取动作a后从当前状态s到下一状态s’的概率，由于从当前路口选择行为a之后到达下个路口是确定的，故γ为折扣因子，表示对未来奖励的折扣度，γ∈[0,1]；故上述两个方程简写为：v(s)＝r(s'|s,a)+γv(s')，q(s,a)＝r(s'|s,a)+γq(s'|a')；42)设定策略迭代具体步骤如下：421)对策略迭代的参数进行初始化，初始化所有路口的状态价值函数v(s)＝0，设置所有路口各个方向的动作价值q(s,a)＝0，并且所有状态转移概率p＝1，折扣因子γ＝1，初始化随机策略π(a1|s)＝π(a2|s)＝
…
＝π(a
n
|s)＝1/n,n∈{1,2,3,4,5,6}；
422)对所有状态即路口利用贝尔曼方程进行策略评估：对当前执行策略进行一次简单评估，并选择当前路口各个方向q(s,a)的最大值来更新该路口的状态价值函数v(s)，其表达式如下：v(s)＝maxq(s,a)；423)进行策略优化：根据智能体有无到达终点选择奖励函数r并赋值贝尔曼方程中r(s'|s,a)来计算所有路口各个方向的动作价值函数q(s,a)；对于所有路口，选择动作价值函数q(s,a)最大值对应的方向作为新的策略π(a|s)；424)重复步骤422)、423)步骤，对所得的新策略再次进行评估，并在此基础上再进行策略优化，直至方法收敛；425)从起点开始，将每个路口最大动作价值函数q(s,a)所对应的方向依次连接起来，所得的路径即为最优路径。5.根据权利要求1所述的一种基于强化学习策略迭代技术的城市路网路径规划方法，其特征在于，所述城市极端路网环境下最优路径的生成包括以下步骤：51)路网结点分层级设计与层级结点的状态动作价值函数q(s,a)取值设计：设计一级连接点表示为从终点所连接的第一个最短路径结点，二级连接点是一级连接点的下个结点且非终点，除一级连接点外，其他结点都表示一般结点；其中，一级连接点q(s,a)表示为：一般连接点q(s,a)表示为：令r
t_directopti
＝move_utility*linklength+distance_reward*dci；其中，r
t_directopti
表示方向最优路口，它是指distance_reward*dci取值最大的路口，即越朝向终点的路口；其中distance_reward作用是判断智能体有无向终点目标前进，dci表示距离贡献指数；move_utility是智能体移动单位距离所要付出的代价，congestion_penalty是道路拥堵惩罚，finalreward是到达终点的奖励，linklength表示路段长度，pressure表示路网通行压力，γ表示折扣因子，v(s)为状态价值函数；52)根据51)各层级结点q(s,a)的设计，设定算法的收敛类型以及路网通行压力为0时，即将pressure取值为0的情况下各类型收敛的充分条件设计：521)严格收敛：若当前路口为一级连接点，该结点的状态价值函数v(s)满足下式，v(s)＝maxq(s,a)＝linklength*move_utility+finalreward<finalreward；若当前路口为一般连接点，该结点的状态价值函数v(s)满足下式，v(s)＝maxq(s,a)＝r
t_directopti
+γ*v(s’)<v(s’)<finalreward；其中，maxq(s,a)表示最大动作价值函数，move_utility是智能体移动单位距离所要付出的代价，finalreward是到达终点的奖励，linklength表示路段长度,γ表示折扣因子，v(s’)为下个状态s’的状态价值函数；r
t_directopti
表示方向最优路口，即越朝向终点的路口的奖励；
在迭代过程中所有路口在任何一个回合都满足上述条件时，方法严格收敛；522)一般收敛：若当前路口为一级连接点，该结点的状态价值函数v(s)满足下式，v(s)＝maxq(s,a)＝linklength*move_utility+finalreward<finalreward；若当前路口为一般连接点，该结点的状态价值函数v(s)满足下式，v(s’)max
–
v(s’)
t_directopti
<r
t_directopti
；即当前路口有若干个下一路口，s’表示下一路口；在这些下一路口中，v(s’)最大路口与方向最优路口v(s’)的差要小于r
t_directopti
；其中，maxq(s,a)表示最大动作价值函数，move_utility是智能体移动单位距离所要付出的代价，finalreward是到达终点的奖励，v(s’)
max
为下一状态的最大状态价值函数，v(s’)
t_directopti
为下一状态方向最优的状态价值函数，r
t_directopti
表示方向最优路口，即越朝向终点的路口的奖励；在迭代过程中所有路口在任何一个回合都满足上述条件时，方法一般收敛；523)无法收敛：即无法探索到一条从起点到终点的最优路径，在迭代过程中，一般连接点的状态价值函数v(s)在任何一个回合都不满足一般收敛的表达式，一级连接点在迭代若干回合后亦无法满足严格收敛的表达式；53)在极端路网环境下，即路段通行压力为0时，各结点的状态价值函数v(s)来源于finalreward；同时，在上述环境下，根据332)对奖励函数超参数的取值导致基于策略迭代的路径规划方法无法收敛；利用52)中设计的方法收敛的充分条件，对finalreward与折扣因子γ的取值重新进行设计；设定在收敛条件满足的前提下，当move_utility与distance_reward保持不变时，finalreward值越大，折扣因子取值也相应增大，折扣因子γ无限趋近于1，但不等于1；54)设move_utility取值为-0.00002，distance_reward在智能体朝向终点行驶取值为0.8、否则为-0.8；设finalreward为20、γ为0.98或finalreward为100、γ为0.99，以此为满足收敛条件的超参数组合；该超参数取值的组合能够确保在极端状态下生成一条从起点到终点的最优路径。

技术总结
本发明涉及一种基于强化学习策略迭代技术的城市路网路径规划方法，与现有技术相比解决了极端路网环境下难以保证路径规划方法稳定收敛的缺陷。本发明包括以下步骤：城市路网数据模型的构建；路网环境中强化学习模型要素的设计；正常状态下城市路网最优路径的生成；城市极端路网环境下最优路径的生成。本发明通过对极端路网环境下(通行压力为0)路径规划方法的收敛性问题进行改进与优化，探索了方法在上述环境下的收敛条件和关键超参数取值的相互关系，利用启发性知识减少了奖励函数要素取值设计的随机性，保证了在任何路网环境下都能够迅速地探索到最优路径。够迅速地探索到最优路径。够迅速地探索到最优路径。


技术研发人员：梁栋 王慧敏 席宇亮
受保护的技术使用者：安徽大学
技术研发日：2022.10.24
技术公布日：2023/1/6