(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111571020.0 (22)申请日 2021.12.21 (71)申请人 中国人民解 放军国防科技大 学 地址 410073 湖南省长 沙市开福区德雅路 109号 (72)发明人 陆丽娜　张万鹏　谷学强　冯志峰　 罗俊仁　曾诚逸　袁唯淋　 (74)专利代理 机构 长沙国科天河知识产权代理 有限公司 432 25 代理人 彭小兰 (51)Int.Cl. G06N 5/00(2006.01) G06F 30/20(2020.01) (54)发明名称 基于混合采样策略的多智能体在线动作决 策方法 (57)摘要 本发明涉及在 线决策领域， 公开了一种基于 混合采样策略的多智能体在 线动作决策方法， 本 发明首先将多智能体对抗环境下的在线动作决 策问题建模成组合多臂赌博机问题， 维护更新搜 索树上每个节点索引的组合动作的累积回报的 后验分布， 然后使用基于ε贪婪策略和汤普森采 样的混合采样策略选择和扩展节 点。 本发明中的 混和采样方法避免了在大规模问题中扩展每个 节点下的所有子节点， 同时， 本发明可 以处理带 先验和后验知识的信息模型， 具有更快的收敛速 度。 本发明结合了两种采样方法， 可以加快采样 收敛速度， 提高采样效率， 从而扩大MCTS可应用 问题的规模， 在大规模问题中， 当分支因子大的 时候， 本发明的效果更加显著。 权利要求书4页 说明书12页 附图4页 CN 114239827 A 2022.03.25 CN 114239827 A 1.一种基于混合采样策略的多智能体在线动作决策 方法， 其特 征在于， 所述方法包括： 针对多智能体对抗环境下的在线动作 决策问题， 获取当前待决策的局面， 并将该待决 策局面建模成组合多臂赌 博机问题； 从当前待决策的局面开始执行预设动作 策略， 根据获得的回报以建模成参数未知的正 态分布； 将所述未知参数( μ， τ )的联合分布建模成Normal ‑Gamma分布， 所述参数( μ， τ )的后 验分 布也服从Normal‑Gamma分布； 将所述参数( μ， τ )的联合分布建模成服从超 参数为 μ0， λ0， α0， β0的Normal ‑Gamma分布， 则 参数( μ， τ )的后验分布也服从Normal ‑Gamma分布； 根据组合多臂赌博机问题和蒙特卡洛树 搜索(MCTS)原理构建一棵不对称的搜索树； 根据混合采样策略中的ε贪婪策略以及 当前节点状态判断在 当前节点下是选择节点探 索还是节点利用； 如果选择节点利用， 针对当前节点下的所有子节点， 利用混合采样策略中的汤普森采 样方法， 根据每个子节点维护的贝叶斯后验分布对所有子节点的一组后验参数( μ， τ )进行 采样， 并根据当前节点类型， 选择 具有最大或最小后验参数值 μ 的子节点； 如果选择节点探索， 则根据朴素假设为每个智能体独立选择动作以生成联合动作， 如 果由生成的联合动作索引的节点不存在搜索树上时， 创建新的节点并初始化该节点的 Normal‑Gamma分布超参数； 根据返回的叶子节点， 从该叶子节点出发进行蒙特卡洛仿真， 根据仿真结果， 通过回溯 更新搜索路径上所有节点的统计值以及分布超参数， 用以将来的动作策决策， 以返回当前 局面下的可能最优动作。 2.如权利要求1所述的方法， 其特征在于， 所述针对多智能体对抗环境下的在线动作决 策问题， 获取当前待决策的局面， 并将该待决策局面建模成组合多臂赌博机问题的步骤， 包 括： 获取当前待决策的局面， 将当前局面下的决策问题建模成组合多臂赌博机问题， 其中 所述组合多臂赌博机问题用三元组 来表示， X是一组变量的集合， X＝{X1， X2， ...， Xn}， Xi是一个变量， 每个单元Xi具有Ki个不同的动作， 是指 X中所有变量的取值的可能组合， R是回报 函数： 它取决于每 个变量的取值； 在智能体对抗环境下， X表示所有智能体的集合， 是指针对X集合中 的每一个智能体， 在当前状态下 可执行的所有动作的集 合。 3.如权利要求1所述的方法， 其特征在于， 所述从当前待决策的局面开始执行预设动作 策略， 根据获得的回报以建模成参数 未知的正态分布的步骤， 包括： 从当前待决策的局面开始， 执行预设动作策略， 将获得的回报Q建模成参数( μ， τ )未知 的正态分布， Q～N( μ， 1/τ )， 其中μ是正态分布的均值， τ为正态分布的精度， 为方差的倒 数， 即τ ＝1/σ2。 4.如权利要求1所述的方法， 其特征在于， 所述将所述参数( μ， τ )的联合分布建模成服 从超参数为μ0， λ0， α0， β0的Normal ‑Gamma分布， 则参数( μ， τ)的后验分布也服从Normal ‑权　利　要　求　书 1/4 页 2 CN 114239827 A 2Gamma分布的步骤， 包括： μ和 τ 的联合分布服从超 参数为 μ0， λ0， α0， β0的Normal ‑Gamma分布， τ 的边缘分布服从形状 (shape)参数为α0和rate参数为β0的Gamma分布， 即τ～Gamma( α0， β0)， 给定τ之后 μ的条件分 布服从均值 为 μ0， 精度为 λ0τ 的正态分布， 即 μ～N ormal( μ0， 1/( λ0τ ))； 根据贝叶斯推理， 参数( μ， τ )的后验分布服从超参数为( μn， λn， αn， βn)的Normal ‑Gamma分 布， 其中： λn＝ λ0+n 5.如权利要求1所述的方法， 其特征在于， 所述根据组合多臂赌博机问题和蒙特卡洛树 搜索(MCTS)原理构建一棵不对称的搜索树， 构建搜索树的步骤， 包括： 选择(Selection)， 从根节点开始， 递归运用本发明的混合采样策略， 直到一个叶子节 点； 扩展(Expansion)， 根据当前节点状态下， 组合多臂赌博机问题中的可用 动作集， 添加 子节点扩展搜索树； 仿真(Simulati on)， 从当前叶子节点 开始， 运行仿真策略直到结束， 产生仿真结果； 回溯(Backpropagation)， 通过反向传播更新路径上每个节点的统计信息和参数值， 用 以将来的动作策决策。 6.如权利要求1所述的方法， 其特征在于， 所述如果选择节点利用， 针对当前节点下的 所有子节点， 利用混合采样策略中的汤普森采样方法， 根据每个子节点维护的贝叶斯后验 分布对所有子节 点的一组后验参数( μ， τ )进行采样， 并根据当前节 点类型， 选择具有最大或 最小后验参数值 μ 的子节点， 包括： 针对当前局面， Thompson采样根据每个节点上的累积回报的后验分布参数， 选择具有 最大期望累积回报的节点索引的动作， 即： 在贝叶斯设定下， 动作a被选中的概 率为 其中 是指示函数， 当{}中的条件满足时为1， 否则为0。 D是累积回报Q的一组观测样 本， D＝{q1， q2，…， qn}独立同分布于正态分布， 即qi～N( μ， 1/ τ )。 7.如权利要求1所述的方法， 其特征在于， 所述如果选择节点探索， 则根据朴素假设为 每个智能体独立选择动作以生成联合动作， 如果由生成的联合动作索引的节点不存在搜索权　利　要　求　书 2/4 页 3 CN 114239827 A 3