一种基于自动机和强化学习的铁路交通系统调度优化方法

1.本发明涉及铁路交通调度技术领域，尤其是涉及一种基于自动机和强化学习的铁路交通系统调度优化方法。


背景技术：

2.随着经济的发展、生活节奏的加快，人们的日常出行变得愈加频繁。长距离、跨区域的物质流动需求不断的提升，使得铁路运输的发展进入了一个新的时期。为了避免行车秩序混乱、突发事故的潜在隐患，保障旅客和货物运输安全，做好铁路交通系统的调度工作至关重要。
3.车辆优化调度是一类典型的组合优化问题，并已证明是np难问题，常用的方法有传统数学优化方法、启发式方法、机器学习方法。传统数学优化方法通过建立铁路交通调度问题的数学模型和约束条件进行求解，建模过程十分复杂和困难；启发式方法需要设计人员拥有较为完备的专业知识并且专用性比较强。此外，启发式方法往往不能得到最优解。目前，普遍认为基于机器学习方法的调度决策方案比传统数学优化方法和启发式方法更具有实用性。机器学习不需要先验知识，直接从数据中发现规律构造模型来逼近铁路运输生产实际情况。机器学习可分为监督学习、无监督学习和强化学习。监督学习需要在训练中为每个样本提供预测量值的真实值，这在有些应用场合是有困难的。在无监督学习中，所有的数据没有被标记，但是这些数据会呈现出聚群的结构，也只适用于一些特定的场景。强化学习适用于描述和解决智能体在与环境的交互过程中通过学习策略以达到回报最大化或实现特定目标的问题。通过试错的方式总结每一步的最佳行为决策，能够很好的适用于铁路交通系统调度这种动态环境。
4.因此，针对铁路交通系统调度所存在的建模复杂、求解困难的问题，有必要提出一种灵活高效的铁路交通系统调度优化方法。


技术实现要素：

5.本发明的目的是提供一种基于自动机和强化学习的铁路交通系统调度优化方法，采用自动机建立铁路交通系统调度问题的数学模型，使用强化学习算法求解最优调度方案，得到铁路交通系统的最优调度方案，同时满足安全性和活性控制规范，有效降低车辆调度成本。
6.为实现上述目的，本发明提供了一种基于自动机和强化学习的铁路交通系统调度优化方法，包括以下步骤：
7.s1、根据铁路交通系统调度问题，使用自动机建立车辆的数学模型gi，安全性和活性控制规范模型ej，i＝1,...,n表示车辆数量，j＝1,...,m表示控制规范的自动机模型个数；
8.s2、基于s1的车辆数学模型gi，建立铁路交通系统调度问题的自动机模型g；结合s1的控制规范模型ej，求解出铁路交通系统调度问题的目标模型t；
9.s3、根据s2的目标模型t，结合事件发生所需的成本和事件的控制成本，为目标模型t中的事件赋予相应的执行成本；
10.s4、基于s2的自动机模型g和s3的目标模型t，利用tct软件求解出铁路交通系统调度问题的监控器模型v＝supc(g,t)；
11.s5、将s4中的监控器模型v转换为确定性马尔可夫决策过程mdp，利用q学习算法求解铁路交通系统调度问题，实验并进行结果分析。
12.优选的，所述s1中，使用自动机建立车辆的数学模型gi,安全性和活性控制规范模型ej分别为：
13.gi＝(hi,∑i,δi,h
i0
,h
im
)，
14.ej＝(hj,∑j,δj,h
j0
,h
jm
)，
15.其中，i＝1,...,n,j＝1,...,m；hi表示有限状态集合，代表车辆所处的位置状态集合；∑i表示有限事件集合，划分为可控事件集合∑
ic
和不可控事件集合∑
iuc
，且可控事件一般是指控制器发出的指令，而不可控事件一般是指传感器的反馈信号或扰动信号(如发生故障)；
16.δi:hi×
∑i→hi
表示状态转移函数；h
i0
表示初始状态，代表车辆的初始位置；h
im
表示标记状态集合，代表希望车辆到达的位置状态；
17.安全性和活性控制规范模型ej的含义与模型gi中的含义相同。
18.优选的，所述s3中，执行成本的函数c:z
×
σ
→r+
，其中r
+
表示正实数集，满足
[0019][0020]
其中，σ(x)表示状态x下允许发生的事件集合，c(x,σ)表示在状态x下执行事件σ的成本，它是事件σ的发生成本和控制成本之和。
[0021]
事件的发生成本具有实际的物理意义。例如，在柔性汽车制造系统中，事件的发生成本可表示机械的耗电、磨损、维修等成本；在铁路交通系统调度的应用中，事件的发生成本可表示为距离、时间等因素。事件的控制成本为禁止该状态下其他可控事件的成本。根据成本函数为目标模型中的每个事件赋予相应的执行成本。
[0022]
优选的，所述s5中，监控器模型v转换为等效的确定性mdp，通过奖惩因子和成本函数构建奖励函数，从而求解铁路交通系统调度问题的最优调度方案。
[0023]
本发明所述的一种基于自动机和强化学习的铁路交通系统调度优化方法的优点和积极效果是：根据铁路交通系统调度问题建立对应的自动机模型，然后将自动机模型转换为等效的确定性mdp，最后利用q学习算法对该问题进行求解，找到铁路交通系统调度的最优方案。该方法不仅能够快速找到铁路交通系统调度的最优方案，同时满足安全性和活性控制规范，能有效降低铁路交通系统调度成本，具有良好的应用前景。
[0024]
下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。
附图说明
[0025]
图1为本发明一种基于自动机和强化学习的铁路交通系统调度优化方法实施例的流程图；
[0026]
图2为铁路交通系统调度示意图；
[0027]
图3为本发明一种基于自动机和强化学习的铁路交通系统调度优化方法实施例的自动机建立的车辆数学模型；
[0028]
图4为本发明一种基于自动机和强化学习的铁路交通系统调度优化方法实施例的铁路交通系统调度问题的自动机模型；
[0029]
图5为本发明一种基于自动机和强化学习的铁路交通系统调度优化方法实施例的铁路交通系统调度问题的监控器模型；
[0030]
图6为本发明一种基于自动机和强化学习的铁路交通系统调度优化方法实施例的铁路交通系统调度问题的最优调度方案。
具体实施方式
[0031]
以下通过附图和实施例对本发明的技术方案作进一步说明。
[0032]
如图1所示，一种基于自动机和强化学习的铁路交通系统调度优化方法，包括以下步骤：
[0033]
s1、根据铁路交通系统调度问题，使用自动机建立车辆的数学模型gi，安全性和活性控制规范模型ej，i＝1,...,n表示车辆数量，j＝1,...,m表示控制规范的自动机模型个数。
[0034]
使用自动机建立车辆的数学模型gi,安全性和活性控制规范模型ej分别为：
[0035]gi
＝(hi,∑i,δi,h
i0
,h
im
)，
[0036]ej
＝(hj,∑j,δj,h
j0
,h
jm
)，
[0037]
其中，i＝1,...,n,j＝1,...,m；hi表示有限状态集合，代表车辆所处的位置状态集合；∑i表示有限事件集合，划分为可控事件集合∑
ic
和不可控事件集合∑
iuc
，且可控事件一般是指控制器发出的指令，而不可控事件一般是指传感器的反馈信号或扰动信号(如发生故障)；
[0038]
δi:hi×
∑i→hi
表示状态转移函数；h
i0
表示初始状态，代表车辆的初始位置；h
im
表示标记状态集合，代表希望车辆到达的位置状态；
[0039]
安全性和活性控制规范模型ej的含义与模型gi中的含义相同。
[0040]
当系统增加控制车辆时，不需对整个系统重新建模，只需增加对应车辆的自动机模型和改变控制规范的自动机模型即可。
[0041]
s2、基于s1的车辆数学模型gi，建立铁路交通系统调度问题的自动机模型g；结合s1的控制规范模型ej，求解出铁路交通系统调度问题的目标模型t。
[0042]
s3、根据s2的目标模型t，结合事件发生所需的成本和事件的控制成本，为目标模型t中的事件赋予相应的执行成本。
[0043]
执行成本的函数c:z
×
σ
→r+
，其中r
+
表示正实数集，满足
[0044][0045]
其中，σ(x)表示状态x下允许发生的事件集合，c(x,σ)表示在状态x下执行事件σ的成本，它是事件σ的发生成本和控制成本之和。
[0046]
事件的发生成本具有实际的物理意义。例如，在柔性汽车制造系统中，事件的发生
成本可表示机械的耗电、磨损、维修等成本；在铁路交通系统调度的应用中，事件的发生成本可表示为距离、时间等因素。事件的控制成本为禁止该状态下其他可控事件的成本。根据成本函数为目标模型中的每个事件赋予相应的执行成本。
[0047]
s4、基于s2的自动机模型g和s3的目标模型t，利用tct软件求解出铁路交通系统调度问题的监控器模型v＝supc(g,t)。
[0048]
s5、将s4中的监控器模型v转换为确定性马尔可夫决策过程mdp，利用q学习算法求解铁路交通系统调度问题，实验并进行结果分析。
[0049]
监控器模型v转换为等效的确定性mdp，通过奖惩因子和成本函数构建奖励函数，从而求解铁路交通系统调度问题的最优调度方案。
[0050]
实施例
[0051]
如图2所示，两辆列车c1和c2分别位于轨道区域1和轨道区域2，列车c1可在轨道区域1～8之间行驶，列车c2可在轨道区域2，4～8之间行驶。通过5个交通信号灯分别控制列车驶入驶出轨道。为防止碰撞的事故发生，多轨道列车控制案例的安全规范为确保列车c1和c2不会同时处于同一个轨道上。
[0052]
表1为铁路交通系统调度问题中事件的可控性、发生成本和控制成本说明。
[0053]
表1事件的可控性和成本
[0054]
事件可控性发生成本控制成本事件可控性发生成本控制成本110不可控2.0\121可控2.01.0111可控3.01.5123可控2.01.0112不可控3.0\210不可控4.0\113可控4.02.0212不可控4.0\115可控4.02.0215可控4.02.0 117可控3.01.5217可控2.01.0 119可控2.01.0221可控3.01.5
[0055]
基于自动机和强化学习的铁路交通系统调度优化方法，包括以下步骤：
[0056]
s1、根据铁路交通系统调度问题，使用自动机建立车辆的数学模型gi，安全性和活性控制规范模型ej，i＝1,...,n表示车辆数量，j＝1,...,m表示控制规范的自动机模型个数。
[0057]
使用自动机建立列车c1和c2的模型，如图3所示。
[0058]
为满足安全性规范，使用tct中的mutex()操作创建控制规范自动机模型e＝mutex(c1,c2,[(2,2),(4,4),(5,5),(6,6),(7,7)])。其中，状态对(2,2),(4,4),(5,5),(6,6),(7,7)表示列车c1和c2位于同一个轨道区域，违背了安全性规范。
[0059]
s2、基于s1的车辆数学模型gi，建立铁路交通系统调度问题的自动机模型g；结合s1的控制规范模型ej，求解出铁路交通系统调度问题的目标模型t。
[0060]
s2中建立的铁路交通系统调度问题模型g和目标模型t如下：
[0061]
g＝g1||g2＝(h,∑,δ,h,hm)。其中，||表示将多个独立允许的模块自动机模型合成为一个完整系统模型，称为同步积操作。其中h＝h1×
h2,∑＝∑1∪∑2,h＝(h
10
,h
20
),hm＝h
1m
×h2m
，令h1∈h1,h2∈h2,σ∈∑,
[0062][0063]
目标模型t＝g||e＝(z,σ,τ,z0,zm)；
[0064]
铁路交通系统调度问题模型g如附图4所示。
[0065]
s3、根据s2的目标模型t，结合事件发生所需的成本和事件的控制成本，为目标模型t中的事件赋予相应的执行成本。
[0066]
执行成本的函数c:z
×
σ
→r+
，其中r
+
表示正实数集，满足
[0067][0068]
其中，σ(x)表示状态x下允许发生的事件集合，c(x,σ)表示在状态x下执行事件σ的成本，它是事件σ的发生成本和控制成本之和。
[0069]
根据成本函数为目标模型t中的每个事件赋予相应的执行成本。
[0070]
从初始状态到标记状态的路径其成本定义如下：
[0071][0072]
s4、基于s2的自动机模型g和s3的目标模型t，利用tct软件求解出铁路交通系统调度问题的监控器模型v＝supc(g,t)，如图5所示。
[0073]
s5、将s4中的监控器模型v转换为确定性马尔可夫决策过程mdp，利用q学习算法求解铁路交通系统调度问题，实验并进行结果分析。
[0074]
确定性mdp为五元组(s,a,t,r,γ)，其中，s为状态空间；a为动作空间；t：s
×a→
s为确定性转移概率矩阵；r:s
×a→
r为奖励函数，r为实数集；γ∈[0,1]为折扣因子，表示对未来奖励的考虑情况，γ越大表示越注重未来动作的奖励。
[0075]
对于监控器其被转换成等效的确定性mdp的过程为：令s≡x,a≡σ,因为∑分为可控事件集合和不可控事件集合，故动作集合a划分为可控动作集合ac≡σc和不可控动作集合a
uc
≡σ
uc
，且奖励函数定义如下：
[0076]
r(s,a)＝-(c,a)+p
[0077]
其中，c(s,a)为成本函数，表示监控器中状态s∈x执行事件a∈∑的成本，p∈r为奖惩因子。当p为负数时，表示对动作的惩罚，用于以下两种情况：1.对进入不可控回路动作的惩罚；2.在且时，选择可控动作的惩罚。当p为正数时，表示对到达标记状态的奖励。
[0078]
当监控器模型v转换为等效的确定性mdp后，使用q学习算法求解最优调度方案。令costvalue＝0，表示铁路交通系统调度成本。从初始状态s开始，若该状态下没有不可控动作，则选择q(s,a)中q值最大的动作，costvalue＝c(s,a)；若该状态下有不可控动作，则选择所有的不可控动作，并标记q值最小的不可控动作a，costvalue＝c(s,a)，并将该状态存入列表d
*
中，根据选择的动作到达下一个状态s
′
，进行同样的选择，直到s
′
为标记状态。
[0079]
当训练结束后，根据q值表选择d
*
中每个状态下的可控动作到达标记状态的转移
路径，若该路径成本不大于costvalue，则保留该路径。
[0080]
对于图2的铁路交通系统调度问题，求解的最优调度方案如图6所示：
[0081][0082]
结果分析如下：当列车c1和c2分别位于轨道区域1和轨道区域2时，通过最优调度方案进行控制，能够避免车辆发生碰撞，并且其控制成本为23，小于方案(1,2)
→
(1,4)
→
(1,6)
→
(2,6)
→
(5,6)
→
(7,6)
→
(8,6)
→
(8,7)的控制成本24.5。
[0083]
因此，本发明采用上述基于自动机和强化学习的铁路交通系统调度优化方法，采用自动机建立铁路交通系统调度问题的数学模型，使用强化学习算法求解最优调度方案，得到铁路交通系统的最优调度方案，同时满足安全性和活性控制规范，有效降低车辆调度成本。
[0084]
最后应说明的是：以上实施例仅用以说明本发明的技术方案而非对其进行限制，尽管参照较佳实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对本发明的技术方案进行修改或者等同替换，而这些修改或者等同替换亦不能使修改后的技术方案脱离本发明技术方案的精神和范围。

技术特征：
1.一种基于自动机和强化学习的铁路交通系统调度优化方法，其特征在于，包括以下步骤：s1、根据铁路交通系统调度问题，使用自动机建立车辆的数学模型g
i
，安全性和活性控制规范模型e
j
，i＝1,...,n表示车辆数量，j＝1,...,m表示控制规范的自动机模型个数；s2、基于s1的车辆数学模型g
i
，建立铁路交通系统调度问题的自动机模型g；结合s1的控制规范模型e
j
，求解出铁路交通系统调度问题的目标模型t；s3、根据s2的目标模型t，结合事件发生所需的成本和事件的控制成本，为目标模型t中的事件赋予相应的执行成本；s4、基于s2的自动机模型g和s3的目标模型t，利用tct软件求解出铁路交通系统调度问题的监控器模型v＝supc(g,t)；s5、将s4中的监控器模型v转换为确定性马尔可夫决策过程mdp，利用q学习算法求解铁路交通系统调度问题，实验并进行结果分析。2.根据权利要求1所述的一种基于自动机和强化学习的铁路交通系统调度优化方法，其特征在于：所述s1中，使用自动机建立车辆的数学模型g
i
,安全性和活性控制规范模型e
j
分别为：g
i
＝(h
i
,∑
i
,δ
i
,h
i0
,h
im
)，e
j
＝(h
j
,∑
j
,δ
j
,h
j0
,h
jm
)，其中，i＝1,...,n,j＝1,...,m；h
i
表示有限状态集合，代表车辆所处的位置状态集合；∑
i
表示有限事件集合，划分为可控事件集合∑
ic
和不可控事件集合∑
iuc
，且δ
i
:h
i
×
∑
i
→
h
i
表示状态转移函数；h
i0
表示初始状态，代表车辆的初始位置；h
im
表示标记状态集合，代表希望车辆到达的位置状态；安全性和活性控制规范模型e
j
的含义与模型g
i
中的含义相同。3.根据权利要求1所述的一种基于自动机和强化学习的铁路交通系统调度优化方法，其特征在于：所述s3中，执行成本的函数c:z
×
σ
→
r
+
，其中r
+
表示正实数集，满足其中，σ(x)表示状态x下允许发生的事件集合，c(x,σ)表示在状态x下执行事件σ的成本，它是事件σ的发生成本和控制成本之和。4.根据权利要求1所述的一种基于自动机和强化学习的铁路交通系统调度优化方法，其特征在于：所述s5中，监控器模型v转换为等效的确定性mdp，通过奖惩因子和成本函数构建奖励函数，从而求解铁路交通系统调度问题的最优调度方案。

技术总结
本发明公开了一种基于自动机和强化学习的铁路交通系统调度优化方法，包括以下步骤：S1、建立车辆的数学模型G


技术研发人员：王德光 胡瑜洪 杨明
受保护的技术使用者：贵州大学
技术研发日：2022.12.22
技术公布日：2023/4/25