一种求解多智能体路径规划问题的轻量化方法

1.本发明数据多智能体路径规划、多智能体强化学习领域，尤其涉及一种多智能体路径规划问题的轻量化方法。


背景技术：

2.近年来，随着科学技术的不断发展，自动化设施在各种场景的运用日渐频繁，其中部分场景需要自动化设施频繁来往于各种地区以执行不同的任务，如物流领域的物流机器人、仓储系统的货运小车以及自动化港口的运输车等，一般可以将此种自动化设施统称为自动运输车(automated guided vehicle，简称agv)，若存在多个agv共同完成同一项任务可以称为agv群。agv群组成的系统一般具有数量众多、任务频次高且时效性要求高的特点。庞大的agv数量致使运作过程中，各个agv需要避免在行进路径上与其他agv相撞；高强度的调度频次需要一种保证agv群彼此不相撞的前提下，尽可能为每个agv规划较短的路径，以尽快完成任务；时效性要求所用方法能针对各种场景进行快速反应。针对上述三个要求，需要一种通用的算法模型完成agv群系统的路径规划问题，以求安全、高效的完成各种场景下的复杂任务。
3.其中一种现有技术为基于冲突检测的多智能体路径规划算法，该算法的底层以a*算法为每个智能体进行路径规划，顶层进行冲突检测，子在放生冲突的位置为对应智能体重新进行路径规划，直至完成目标或陷入循环。但是，该方案对环境的适应性较弱，处于稍复杂的环境则效果明显减弱：随智能体数量增多及障碍物分布变密，智能体最优路径相交逐渐频繁，需要耗费大量时间进行最优路径求解，且重新进行路径规划时经常陷入循环，导致无法求解。
4.另一种现有技术为结合强化学习与模仿学习求解多智能体路径规划，该算法采用强化学习算法，搭建以cnn为主的深度神经网络，运用训练后的神经网络模型对各个智能体进行动作选择指导，以其他算法进行多智能体路径规划所得结果作为专家数据，以此进行模仿学习。但是，该方案对数据需求量过大：需要耗费大量时间运行其他算法获取专家数据，且性能上很难超越该算法，深度神经网络自身训练同样需要大量数据，环境发生变化则需要重新进行数据获取。
5.现有技术中的局部观测状态获取方式一般以四个矩阵存储环境信息，分别为障碍物信息、智能体位置信息、其他智能体位置信息与各智能体目标信息，以0/1形式存储，实际过程中，四种矩阵中含有大量的0元素，而0元素在神经网络前向传播过程中会导致大量参数无效化，增大了达到拟合目的对应的神经网络规模。
6.现有技术中的一般均采用actor-critic模型作为算法基本框架，其中actor模型一般直接采用局部观测作为输入，有助于物理实现与快速反应；而critic模型用于指导actor模型训练，且仅在训练过程中起到重大作用，故而对critic模型进行改进既有利于提高模型的训练效果，而不影响实际操作时模型的快速反应能力。考虑多智能体系统的联合状态，其一般为多维度的、种类复杂的，若直接采用全局状态作为输入，则神经网络模型的
训练时间复杂度随智能体数量增多而呈指数增长，其训练难度过大；若仅采用各个智能体状态的简单拼合，则会存在大量重复且无用的环境信息，且当智能体数量改变时，模型接口同样需要适当改变。


技术实现要素：

7.本发明通过对现有以强化学习，或多智能体强化学习为基本算法原理的多智能体路径规划求解方法进行改进，包括简化其网络结构、改进局部信息存储方式、改进探索机制、降低其对专家数据的依赖程度。因此本发明提出以下技术方案：
8.一种求解多智能体路径规划问题的轻量化方法，该方法具体包括以下步骤，
9.(1)初始化各模型以及target网络参数，清空经验池，初始化探索机制参数、全局计数清零、成功完成以及完成单次探索计数清零；各模型包括预处理模型、actor模型、critic模型；
10.(2)与环境交互，进行单次探索；
11.(3)探索步数计数清零，更新探索机制参数；
12.(4)依据探索机制进行联合动作获取与执行；
13.(5)根据联合动作进行状态转移，并获取行动奖励；
14.(6)探索步数计数增加一次；
15.(7)确定是否智能体均到达目标点或者探索步数计数达到设定最大步数；
16.(8)如果是，则时序差分更新各步动作行动奖励获得累计奖励，如果否，则回到步骤(4)；时序差分更新各步动作行动奖励是用本步的即时行动奖励与后续预估行动奖励之和代替本步行动奖励，即为累加奖励；
17.(9)确定是否成功完成单次探索目标，也就是是否智能体均到达目标点；
18.(10)如果是，将本次探索数据存入经验池，且成功完成单次探索计数增加一次，如果否，则完成单次探索计数增加一次；所述探索数据包括各智能体各步的局部观测信息、探索过程中的动作与累加奖励记录、是否成功完成单次探索的标识；
19.(11)判断完成单次探索计数是否达到设定值；
20.(12)如果是，重置预处理模型、actor模型、critic模型梯度；如果否，回到步骤(2)；
21.(13)从经验池批量获取数据分别累计各网络梯度进行梯度反向传播，更新target网络参数；
22.(14)全局计数增加一次；
23.(15)进行各模型测试；
24.(16)平均奖励是否收敛；平均奖励为各模型测试中所有智能体每一步动作获取的累加奖励之和除以智能体数量，再除以步数；
25.(17)如果是，则记录模型参数数据，如果否，则回到步骤(2)；
26.(18)结束。
27.本发明具有以下有益技术效果：
28.1)简化神经网络规模，改进局部信息存储方式，用更少的参数求解问题；
29.2)改进探索机制，使模型训练不依赖专家数据，不参照其他算法；
30.3)对输入数据进行维度控制，避免随智能体数量增多导致维度灾难；
31.4)神经网络模型易于搭建，局部信息存储利用率高，且无需其他算法所得数据作为参考，训练易于实现，实际训练时耗时极低；
32.5)采用注意力机制对神经网络的输入数据进行维度控制，既做到综合考虑全局信息，又无需随智能体数量变化修改网络模型，提高了泛用性；
33.本发明通过对现有以强化学习，或多智能体强化学习为基本算法原理的多智能体路径规划求解方法进行改进，包括简化其网络结构、改进局部信息存储方式、改进探索机制、降低其对专家数据的依赖程度。
附图说明
34.图1一种求解多智能体路径规划问题的轻量化方法算法流程图；
35.图2探索机制可行动作示意图；
36.图3局部观测信息示意图；
37.图4critic模型的采用注意力机制构建价值评估模型建模方法示意图。
具体实施方式
38.为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本发明的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。
39.图1其示出了一种求解多智能体路径规划问题的轻量化方法的流程图。如图1所示，该方法具体包括以下步骤，
40.(1)初始化各模型以及target网络参数，清空经验池，初始化探索机制参数、全局计数、成功完成以及完成单次探索次数计数清零；各模型包括预处理模型、actor模型、critic模型；
41.(2)与环境交互，进行单次探索；具体为：在路径规划中所有智能体与工作环境交互，各个智能体分别向其目标点进发，在经过一定步数后，若智能体均到达目标点，称为一次成功单次探索；若仍有智能体未到达目标点，且步数已经达到设置最大值，成为一次失败单次探索；
42.(3)探索步数计数清零，更新探索机制参数；每一次探索中，每进行一步动作都需要记一次数，如果成功，该步数可以作为探索数据质量好坏的评估标准，再进行下一次探索前，需要清零，探索机制参数需要重新更新；
43.(4)依据探索机制进行联合动作获取与执行；在每一步，每个智能体需要采取一种动作，动作选取标准由探索机制决定，每个智能体依次按照该机制得到一个动作，将这些动作组合起来形成联合动作，即为联合动作获取；
44.(5)根据联合动作进行状态转移并获取行动奖励；按照智能体序号顺序依次执行根据探索机制获得的动作，如智能体1动作为“上”，若新位置，如上方位置无障碍物，则将智能体1的位置上移；否则智能体1仍然保持原位置，之后继续执行智能体2的动作，直到所有智能体执行完其对应动作，每个智能体的每个动作对应一次行动奖励；
45.(6)探索步数计数增加一次；
46.(7)确定是否智能体均到达目标点或者探索步数计数达到设定最大步数；
47.(8)步骤(7)中，如果是，则时序查分更新各步动作行动奖励获得累加奖励，如果否，则回到步骤(4)；时序差分更新各步动作行动奖励即是用本步的即时行动奖励与后续预估行动奖励之和代替本步行动奖励，即为累加奖励，累加奖励的计算方式如下，
48.r(t)＝r(t)+γr(t+1)，
49.r(t)为t时刻行动步即时行动奖励，γ为奖励折扣系数，是(0,1)间的实数，可以根据实际情况设定，用以衡量后续行动的累加奖励对本时刻行动步累加奖励的影响，r(t)为t时刻行动步的累加奖励，累加的含义在于，将其展开可以得到：
[0050][0051]
即本步的累加奖励实际考虑了后续路径的所有即时奖励值，用这种时序差分的方法，则不需要保留一整条路径信息，而只需要本时刻信息与下一个时刻的状态；
[0052]
(9)确定是否成功完成单次探索，也就是是否智能体均到达目标点；
[0053]
(10)如果是，将本次探索数据存入经验池，且成功完成单次探索计数增加一次，如果否，则完成单次探索计数增加一次；所述探索数据包括各智能体各步的局部观测信息、探索过程中的行动奖励与累加奖励记录、是否完成探索的标识；
[0054]
(11)判断完成单次探索计数是否达到设定值；
[0055]
(12)如果是，重置预处理模型、actor模型、critic模型梯度；如果否，回到步骤(2)；
[0056]
(13)从经验池批量获取数据分别累计各网络梯度进行梯度反向传播，更新target网络参数；
[0057]
(14)全局计数增加一次；全局计数是记录总共训练了多少次；
[0058]
(15)进行各模型测试；
[0059]
(16)平均奖励是否收敛；平均奖励为所有智能体每一步动作获取的累加奖励之和除以智能体数量，再除以步数；
[0060]
(17)如果是，则记录模型参数数据，如果否，则回到步骤(2)；
[0061]
(18)结束。
[0062]
另一方面，本发明还提出一种探索机制，具体实施方式如下：
[0063]
将原始动作空间设置为{“上”，“下”，“左”，“右”，与“停止”}，智能体小车根据探索机制可以选择上下左右以及停止，探索机制采用以下公式：
[0064][0065]
其中，a(s)是状态s下的动作空间也就是原始动作空间，而a(s)则是状态s下实际选择的动作，p是(0,1)之间的随机生成数，ε1，ε1+ε2是0-1之间的随机数，根据实际情况设
定，random a(s)表示从动作空间a(s)中随机选择动作，random a
free
(s)表示从动作空间a
free
(s)中随机选择动作，a
free
(s)是状态s下的可行动作区间，π
θ
是数学函数，在本实施例中，π
θ
函数采用actor模型进行拟合，argmax表示选择使函数π
θ
达到最大值对应的输入，a|s的含义是状态s下的动作a，a∈a(s)表示动作a的可选范围是a(s)。
[0066]
该公式是每个智能体在探索阶段动作获取所用的公式，首先随机生成p，p为一个0到1间的随机数，根据这个p的大小采用对应的公式生成动作，这里总共有三种可选的动作生成方式，ε1与ε2组合隔开了三种动作获取方式的区间，调节ε1，ε2相当于调整三种公式的选择概率。探索机制采用的公式的具体含义为：当随机数p位于[0,ε1)中时，从状态s下的动作空间a(s)随机选择动作；当随机数p位于[ε1，ε1+ε2)中时，在状态s下选择动作a，动作a使得π
θ
函数取值最大；当随机数p位于[ε1+ε2，1)区间时，从状态s下的动作空间a
free
(s)随机选择动作。
[0067]afree
(s)是状态s下的可行动作区间，也就是在原始动作空间a(s)中，去除会导致冲突的动作，以及回到上个位置的动作，从而减少其无效动作，如图2所示，智能体采取“下”动作会碰到障碍物，采用“右”动作会碰到其他智能体，最终还是保持留在原地；采用“上”动作会导致其回到上次的位置，相当经过两步还是回到了原地，这些动作都不利于其快速找寻终点，去掉这些动作可以减少探索过程的时间，提高数据质量。
[0068]
再次，本发明还提出一种局部观测信息获取方式，具体方法如下：
[0069]
将局部观测信息浓缩为两个矩阵，分别存储智能体及障碍物信息与目标点信息。第一个矩阵称为地图矩阵，其中本智能体信息记为1，对单个智能体而言，其行进过程中，其他智能体同样可以看作障碍物，将其他智能体与障碍物均记为-1，若智能体间种类存在明显区分也可以对其他智能体进行异种标记；同样，第二个矩阵称为目标点矩阵，对本智能体目标位置记为1，其他智能体目标位置记为-1，其他无标识位置均为0，此法既保留了观测范围内的全部环境信息，同时简化了局部信息存储形式，如图3所示。
[0070]
最后，本发明还提出一种结合注意力机制构建价值评估模型的方法，其是critic模型采用的建模方法，具体为一种以注意力机制实现联合状态降维方法，具体包括以下步骤：
[0071]
(1)对各个智能体的状态输入进行信息拓展，得到延展信息向量query,key,value：
[0072]
queryi＝es(o(si))*wq[0073]
keyi＝e
sa
(o(si，ai))*wk[0074]
valuei＝leakyrelu(e
sa
(o(si，ai))*wv)
[0075]
其中，i∈{1，2，...，n}，n为系统内智能体数量，o(si)与o(si，ai)分别为智能体i经预处理的状态向量及动作-状态向量，es，e
sa
分别为状态拓展与动作-状态拓展网络，wq，wk，wv为对应转换矩阵，leakyrelu为激活函数；
[0076]
(2)对每个智能体，其最终状态输入由自身观测数据以及其他智能体观测数据的加权聚合形式获取，以智能体i为例，最终状态输入获取过程如下：
[0077]
1.智能体i与智能体j的关联程度由以下公式衡量，称为注意力权重：
[0078]
[0079]
这里α
i，j
为智能体i对智能体j的注意力权重，qi，为智能体i的query特征向量，kj，vj依次为智能体j的key、value特征向量，dk为key向量的输出维度，是与智能体数量无关的维度；
[0080]
2.对智能体i而言，根据计算其他智能体特征聚合，其中e为智能体观测数据：
[0081][0082]
α
i，j
为步骤1中给出的注意力权重，ej为智能体h的观测数据，对智能体i，将除了它自身的其他智能体信息进行聚合，保证了状态输入维度不随智能体数量改变；
[0083]
3.采用拼合方式将自身输入与其他环境信息进行综合：
[0084]ci
＝ei||xi，i∈{1，2，...，n}
[0085]
步骤2中提到，对智能体i，其他智能体的信息被整合到了一个固定维度，即xi，而ei为该智能体本身的观测数据，||为张量拼合，将自身信息与其他智能体信息融合，保证在自身信息无损耗的前提下，包含其他智能体信息，从而近似代替全局信息，如身信息无损耗的前提下，包含其他智能体信息，从而近似代替全局信息，如则
[0086]
(3)根据上述步骤得到的延展信息，采用加权聚合的方式对其他智能体信息进行综合降维，同时与编码后的原状态输入进行拼合，步骤如下图4所示。
[0087]
在保留重要环境信息的前提下，将输入维度控制在一个固定范围，便于拓展其环境情况。此外，考虑本模型所采用网络均为全连接层，其数学含义较为直观。
[0088]
本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种求解多智能体路径规划问题的轻量化方法，其特征在于，该方法具体包括以下步骤：(1)初始化各模型以及target网络参数，清空经验池，初始化探索机制参数、全局计数清零、成功完成以及完成单次探索计数清零；各模型包括预处理模型、actor模型、critic模型；(2)与环境交互，进行单次探索；(3)探索步数计数清零，更新探索机制参数；(4)依据探索机制进行联合动作获取与执行；(5)根据联合动作进行状态转移，并获取行动奖励；(6)探索步数计数增加一次；(7)确定是否智能体均到达目标点或者探索步数计数达到设定最大步数；(8)如果是，则时序差分更新各步动作行动奖励获得累计奖励，如果否，则回到步骤(4)；时序差分更新各步动作行动奖励是用本步的即时行动奖励与后续预估行动奖励之和代替本步行动奖励，即为累加奖励；(9)确定是否成功完成单次探索目标，也就是是否智能体均到达目标点；(10)如果是，将本次探索数据存入经验池，且成功完成单次探索计数增加一次，如果否，则完成单次探索计数增加一次；所述探索数据包括各智能体各步的局部观测信息、探索过程中的动作与累加奖励记录、是否成功完成单次探索的标识；(11)判断完成单次探索计数是否达到设定值；(12)如果是，重置预处理模型、actor模型、critic模型梯度；如果否，回到步骤(2)；(13)从经验池批量获取数据分别累计各网络梯度进行梯度反向传播，更新target网络参数；(14)全局计数增加一次；(15)进行各模型测试；(16)平均奖励是否收敛；平均奖励为各模型测试中所有智能体每一步动作获取的累加奖励之和除以智能体数量，再除以步数；(17)如果是，则记录模型参数数据，如果否，则回到步骤(2)；(18)结束。2.根据权利要求1所述的一种求解多智能体路径规划问题的轻量化方法，其特征在于，所述探索机制采用以下公式：其中，a(s)是状态s下的动作空间，而a(s)则是该状态s下实际选择的动作，p是(0,1)之间的随机生成数，ε1，ε1+ε2是0-1之间的随机数，random a(s)表示从动作空间a(s)中随机选择动作，random a
free
(s)表示从动作空间a
free
(s)中随机选择动作，a
free
(s)是状态s下的可
行动作区间，π
θ
是数学函数，argmax表示选择使函数π
θ
达到最大值对应的输入，a|s的是状态s下的动作a，a∈a(s)表示动作a的可选范围是a(s)。3.根据权利要求1所述的一种求解多智能体路径规划问题的轻量化方法，其特征在于，局部观测信息为两个矩阵，分别存储智能体及障碍物信息与目标点信息，存储智能体及障碍物信息的矩阵称为地图矩阵，其中本智能体信息记为1，对单个智能体而言，其行进过程中，其他智能体同样可以看作障碍物，将其他智能体与障碍物均记为-1，若智能体间种类存在明显区分也可以对其他智能体进行异种标记；存储目标点信息的矩阵称为目标点矩阵，对本智能体目标点位置记为1，其他智能体目标位置记为-1，其他无标识位置均为0。4.根据权利要求1所述的一种求解多智能体路径规划问题的轻量化方法，其特征在于，步骤1中的critic模型采用结合注意力机制构建的价值评估模型，其建模方法具体包括以下步骤：(1)对各个智能体的状态输入进行信息拓展，得到延展信息向量query,key,value：query
i
＝e
s
(o(s
i
))*w
q
key
i
＝e
sa
(o(s
i
,a
i
))*w
k
value
i
＝leakyrelu(e
sa
(o(s
i
,a
i
))*wv)其中，i∈{1,2,
…
,n}，n为系统内智能体数量，o(s
i
)与o(s
i
,a
i
)分别为智能体i经预处理的状态向量及动作-状态向量，e
s
,e
sa
分别为状态拓展与动作-状态拓展网络，w
q
,w
k
,wv为对应转换矩阵，leakyrelu为激活函数；(2)对每个智能体，其最终状态输入由自身观测数据以及其他智能体观测数据的加权聚合形式获取，以智能体i为例，最终状态输入获取过程如下：
ⅰ
.智能体i与智能体j的关联程度由以下公式衡量，称为注意力权重：α
i,j
为智能体i对智能体j的注意力权重，q
i
为智能体i的query特征向量，k
j
,v
j
为智能体j的key、value特征向量，d
k
为key向量的输出维度；
ⅱ
.对智能体i而言，根据计算其他智能体特征聚合，其中e为智能体观测数据：e
j
为智能体j的观测数据；
ⅲ
.采用拼合方式将自身输入与其他环境信息进行综合：c
i
＝e
i
||x
i
,i∈{1,2,
…
,n}对智能体i，其他智能体的信息被整合到了一个固定维度，即x
i
，而e
i
为该智能体本身的观测数据，||为张量拼合，将自身信息与其他智能体信息融合；(3)根据上述步骤得到的延展信息，采用加权聚合的方式对其他智能体信息进行综合降维，同时与编码后的原状态输入进行拼合。

技术总结
本发明提出一种求解多智能体路径规划问题的轻量化方法，具体包括以下步骤：初始化，清零；依据探索机制获取并执行动作；获取行动奖励；判断是否完成单次探索，存储探索数据，成功单次探索计数，判断数据收敛，记录模型数据。通过对现有数据以强化学习，或多智能体强化学习为基本算法原理，对多智能体路径规划求解方法进行改进，包括简化其网络结构、改进局部信息存储方式、改进探索机制、降低其对专家数据的依赖程度。依赖程度。依赖程度。


技术研发人员：凌强 金靖昆
受保护的技术使用者：中国科学技术大学
技术研发日：2023.05.26
技术公布日：2023/8/24