(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111401793.4 (22)申请日 2021.11.24 (71)申请人 福州大学 地址 350108 福建省福州市闽侯县福州大 学城乌龙江北 大道2号福州大 学 (72)发明人 陈彦杰　刘江蒋　张智星　兰立民　 陈敏俊　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 代理人 丘鸿超　蔡学俊 (51)Int.Cl. G06N 20/00(2019.01) G06F 16/903(2019.01) G06F 16/901(2019.01) B25J 9/16(2006.01) (54)发明名称 基于高效搜索策略在不确定性环境下的在 线规划方法 (57)摘要 本发明提出一种基于高效搜索策略在不确 定性环境下的在线规划方法， 将 机器人的状态视 为一个信念， 以POMDP算法初始化 当前信念的上、 下边界后， 通过折扣化上下限表 示当前信念的全 部信息进而执行前向搜索构建信念树， 以此获得 当前信念下的最优策略； 所述信念树的每一个节 点代表一个信念， 父节点与子节点通过行为 ‑观 测分支连接。 本发明提供的DESPOT ‑DULB算法性 能优于DESPOT和POMCP， 在收敛速度以及策略质 量上具有优势。 权利要求书3页 说明书12页 附图3页 CN 114118441 A 2022.03.01 CN 114118441 A 1.一种基于高效搜索策略在不确定性环境下的在线规划方法， 其特征在于： 将机器人 的状态视为一个信念， 以POMDP算法初始化当前信念的上、 下边界后， 通过折扣化上下限表 示当前信念的全部信息进而执行前向搜索构建信念树， 以此获得当前信念下 的最优策略； 所述信念树的每一个节点代 表一个信念， 父节点与子节点 通过行为‑观测分支连接 。 2.根据权利要求1所述的基于高效搜索策略在不确定性环境下的在线规划方法， 其特 征在于， 所述POMD P算法采用在线POMD P规划算法DES POT‑DULB， 包括以下步骤： 步骤S1： 智能体在当前信念空间中随机采样K个 状态以构建状态集 合Φb； 步骤S2： 以信念b作为根节点b0构建信念树D， 初始化当前信念b经验价值 的上界U (b)、 下界L(b)和RWDU最优值V*(b)的上界 μ(b)、 下界l(b)； 步骤S3： 定义智能体的当前信念b的不确定性为∈(b)＝ μ(b) ‑l(b)， 并进一步判断当前 不确定性是否满足∈(b)＜∈0或运行时间是否大于Tmax， 如果条件满 足， 执行步骤S5， 否则， 执行步骤S4； 步骤S4： 对作为 根节点b0的信念b进行 前向搜索以扩展信念树； 步骤S5： 当扩展的作为子节点的信念b满足要求， 信念树停止扩展并自下而上对节点执 行备份BACKUP(D， b)， 若遇 到受阻节点， 则执 行剪切操作PRUNE(D， b)； 步骤S6： 对于作为根节点b0的信念b， 选择信念树返回的最大的l(b)对应的最优行为a*， 即 并与默认策略π0的值L(b)比较， 以选择最优行为； 步骤S7： 智能体重复以上的过程， 直到 到达目标点。 3.根据权利要求2所述的基于高效搜索策略在不确定性环境下的在线规划方法， 其特 征在于： 步骤S2具体包括以下 过程： 利用经验值的计算形式 其中Vπ， φ表示模拟策略π， 计算每一个采样 序列φ∈Φb的折扣奖励； 其中对于U(b)的计算通过假设状态是完全可观测的， 将在线 POMDP问题转换成在线MD P问题， 然后计算MD P环境下的最优价 值VMDP： 经验值 下界的计算利用一个默认策略π0来获取， 默认策略为固定行为或随机行 为， 对于每一个节点b的每一个序列Φb模拟默认策略进行有限次数的探索， 计算每一个序 列的折扣奖励再求平均值获得； 对应的RWDU的上限μ(b)和下限l(b)通过U(b)和L(b)依据正规化加权折扣效用函数 RWDU： 求得： 权　利　要　求　书 1/3 页 2 CN 114118441 A 2其中， γ是一个折扣因子， |Φb|是通过节点b的场景数量， Δ(b)表示节点b在策略π 中的 深度， πb是节点b处的子 树， | πb|表示πb的大小， | πb|＝0， λ是正规化因子； 指的是在b处 执行默认策略π0的正规化加权折扣效用值。 4.根据权利要求3所述的基于高效搜索策略在不确定性环境下的在线规划方法， 其特 征在于： 步骤S4具体包括以下 过程： 定义b′＝τ(b， a， z)为节点b采取某一行为 a和获得观测z到达的子节点； 当对节点b执行 扩展更深节点的信念树操作时， 首先通过步骤S2初始化所有节点b的所有子节点b ′的值U (b)， L(b)， μ(b)和l(b)； 然后每一次的前向探索都为更快地将根节点b0处的当前上下限差 值∈(b)减小至目标差值ξ∈(b)， 其中ξ∈(0， 1)是一个常量； 在探索的过程中， 节点b的最优 行为选择都依据节点b的折扣上 下限信息( μ(b)+ωl(b) )/β： 其中， ω是占比因子， ρ(b， a)表示在节点b处执行行为a的带有正规化因子的平均折扣 回报； 具体定义 为： K表示采样的场景数， sφ表示场景φ的初始状态， Δ(b)表示节点b的深度， R(sφ， a)表示 在初始状态sφ执行行为a的回报， γ是折扣因子， λ是正 规化因子； 在执行a*之后， 通过选择使过度不确定性最大的观测z*来获得子节点b ′＝τ(b， a*， z)， 以最大限度的减少不确定性： 其中， β 是基于深度的函数， 用于调整当前信念的不确定性， 进一步保证信念树的搜索 深度； β 的定义： β ＝κΔ(b)    公式八； 其中， κ 为常数， κ ＞1， Δ(b)表示信念节点b的深度； 将以上信念树的扩展过程不断重 复， 直到出现下列情况： (1)信念树扩展到最大深度D， 即Δ(b)＞D； (2)节点b的不确定性已经降到预期值， 即E(b)＜0， 继续探索对凸没有意义； (3)节点b ′的父节点b已经没有足够的采样序列： 其中， l(b ′， b)表示从b到b ′路径上节点的数量； 如果父节点b采样序列不够， 则继续扩 展b会增加b ′子策略树的数量可能会造成过拟合并且降低b ′正则化的效果； 如果在信念树 扩展的过程中某些信念节点满足上式， 则需要执 行剪枝PRUNE(D， b)操作。 5.根据权利要求3或4所述的基于 高效搜索策略在不确定性环境下的在线规划方法， 其 特征在于： 剪切操作PRUNE(D， b)的具体实现形式是： 如果父节点b采样序列不能满足前向搜索停权　利　要　求　书 2/3 页 3 CN 114118441 A 3