一种最大熵部分可观测蒙特卡洛规划方法

技术领域

本发明属于人工智能领域，尤其涉及一种部分可观测马尔可夫决策过程问题的解决方法。

背景技术

在现实应用中，许多问题可以表示为不确定环境中的序贯决策问题。部分可观测马尔科夫决策过程(POMDP)是解决不确定环境中序贯决策问题的一个常见模型。部分可观测蒙特卡洛规划(POMCP)方法则是求解部分可观测马尔可夫决策过程(POMDP)问题的一种在线规划方法。该方法通过从一个游戏历史序列开始进行数次的模拟，试图找到最高收益的模拟序列，从而决定在该历史序列上的决策。然而，该方法中选择模拟轨迹所使用的UCT策略的性能高度依赖于结点价值函数的估计，何况价值估计的收敛速度会影响树中更远的价值估计的收敛速度，随着传播轨迹的增长，价值估计的误差也一定会增大。如果在某一次模拟中因为估计的误差导致某个真实价值比较高的结点的价值估计值偏低，将可能导致将来很长的一段时间内UCT都将以较低的频率访问这个实际很有价值的结点，直到模拟的数量足够多将该结点的价值估计矫正为止。

发明内容

为了解决上述问题，本公开提出一种最大熵部分可观测蒙特卡洛规划方法，构建了一种在POMCP方法之上的POMDP问题的解决方法，改善了方法高度依赖于价值估计准确性的问题。

本发明提供了一种最大熵部分可观测蒙特卡洛规划方法，包括：

步骤S101：开始一个序贯决策过程，到达过程中的一个待决策历史结点；

步骤S201：从该历史结点开始进行n次模拟；

步骤S301：选择待决策历史结点上价值估计最高的动作作为决策；

步骤S401：环境接收动作后转移到新的历史结点，若过程未终止则跳转到步骤S201。

在本发明的一些实施例中，所述步骤S201包括：子步骤S201a：将待决策历史结点h

在本发明的一些实施例中，E2W策略的表达式为：

其中，π(a|h

在本发明的一些实施例中，所述初始化h

其中，N(h

在本发明的一些实施例中，所述初始化

{N(h

其中，N(h

在本发明的一些实施例中，所述对轨迹中的结点进行更新的表达式为：

N(h

B(h

N(h

其中，h

有益效果：

本发明的优点在于在保持了POMCP方法的基本框架的同时，将UCT策略替换为E2W策略，使该策略在最大化总回报的同时还最大化了策略的熵，从而降低了策略对价值估计准确性的依赖，增加了容错率，最终又确实能收敛到柔性最优策略。

附图说明

图1是本发明实施例最大熵部分可观测蒙特卡洛规划方法的流程图；

图2是本发明实施例最大熵部分可观测蒙特卡洛规划方法的步骤S201的子步骤流程示意图；

图3是本发明实施例最大熵部分可观测蒙特卡洛规划方法与原始POMCP方法在Tiger序贯决策过程中的平均总收益随双方同步变化的模拟次数n的曲线图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例仅为本发明的一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域的普通技术人员在不付出创造性劳动的前提下所获得的所有其他实施例，都属于本发明的保护范围。

POMDP模型的核心假设在于智能体不能直接地观察到当前状态，它只能观察到一系列提供了当前状态的一个不完全信息的观测值。因此智能体只能基于从序贯决策过程开始到现在的所有动作和观测值的历史序列进行决策，并在该历史上推导当前所属的实际状态的概率分布。POMDP问题就是在这样的条件下，让智能体学习一个策略，希望该策略能在游戏中获得尽量高的累积收益。

本发明提供了一种利用一种POMDP问题的解决方法——最大熵部分可观测蒙特卡洛规划方法。该方法基于经典的POMCP方法的框架，通过引入最大熵策略体系，替换其中的UCT策略以及价值回溯更新的方式，使得该方法在收敛性能上有更高的保障。

下面将结合实施例和实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述。显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明一实施例提供了一种POMDP问题的解决方法，如图1和图2所示，本发明的一种最大熵部分可观测蒙特卡洛规划方法，包括以下步骤：

步骤S101：开始一个序贯决策过程，该方法的实施要求计算机中存在一个与该过程基本无异的模拟模型，预先设定模拟次数n与两个探索常数τ，∈的值。之后输入在过程中遇到的等待决策的场景(即历史结点)，该方法将返回从该场景出发模拟得到的最优决策(即序贯决策过程中选择的动作)。

步骤S201：从输入的历史结点开始进行n次模拟，如图2所示，该步骤包括：

子步骤S201a：将待决策历史结点h

将待决策历史结点h

子步骤S201b：采样一个可能状态s

对于树中的每个历史结点都维护了一个置信状态的粒子集合B，集合中每个粒子都表示该历史下可能的一个状态，可以同时存在多个粒子表示同一个状态。在模拟开始时将从根结点的置信状态粒子集合B(h

子步骤S201c：从根结点h

E2W策略的表达式为：

其中，π(a|h

首先，本发明希望在搜索过程刚开始时，先有足够多的探索来保证对每个动作的Q

子步骤S201d：将新结点h

初始化h

其中，N(h

初始化

{N(h

其中，N(h

子步骤S201e：估计结点h

该步骤在h

子步骤S201f：更新树中所经过轨迹中的所有结点。

对轨迹中的结点进行更新的表达式为：

N(h

B(h

N(h

其中，h

在该步骤中，对N(h

子步骤S201g：已完成模拟次数+1，若次数未达到终止条件则跳转到步骤S201b。

步骤S301：选择待决策历史结点上价值估计最高的动作作为决策。

n次模拟已经结束，对于根结点h

步骤S401：环境接收动作后转移到新的历史结点，若游戏未终止则选择下一个待决策历史结点为输入并跳转到步骤S201。

Tiger是一个简单的部分可观测的序列决策过程，过程开始时决策智能体被放置在两扇门前，已知其中一扇门的背后有一只老虎，智能体若选择开启了有老虎的门则可能遇到危险，在实验中体现为-100的收益；另一扇的背后则是一些财宝，智能体获得财宝时在实验中体现为+20的收益。智能体在门前随时都可以选择“开门”或“听”的动作，但其中“听”的动作有一定的开销，在实验中体现为-1的收益。在选择“听”时，智能体有75％的概率能够正确地听到老虎在哪一扇门后，但由于环境的不确定性，剩余25％的概率则会错误地听到老虎在相反的方向。该序列决策过程需要智能体把控听的次数，并结合听的结果来权衡在什么阶段去打开哪扇门。本实验分别使用POMCP方法以及本发明提出的最大熵部分可观测蒙特卡洛规划方法去进行Tiger过程的决策，纵坐标的总收益取1000次决策过程的平均值。在不同的模拟次数n的设定下，最大熵部分可观测蒙特卡洛规划方法始终优于POMCP方法。

图3是本发明实施例最大熵部分可观测蒙特卡洛规划方法与原始POMCP方法在Tiger序贯决策过程中的平均总收益随双方同步变化的模拟次数n的曲线图。

至此，已经结合附图对本发明进行了详细描述。依据以上描述，本领域技术人员应当对本发明有了清楚的认识。

需要说明的是，在附图或说明书正文中，未绘示或描述的实现方式，均为所属技术领域中普通技术人员所知的形式，并未进行详细说明。此外，上述对各元件的定义并不仅限于实施例中提到的各种具体结构、形状或方式，本领域普通技术人员可对其进行简单地更改或替换，例如：

(1)上述实施例中使用Rollout过程对新结点h

(2)上述实施例可基于设计及可靠度的考虑，彼此混合搭配使用或与其他实施例混合搭配使用，即不同实施例中的技术特征可以自由组合形成更多的实施例。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本公开的保护范围之内。