CN112356031B - 一种基于Kernel采样策略在不确定性环境下的在线规划方法 - Google Patents

Abstract

本发明提出一种基于Kernel采样策略在不确定性环境下的在线规划方法，用于对机器人执行任务时的规划，在该不确定性环境中，表示为POMDP模型的不确定性是制约机器人可靠运行的主因；所述POMDP模型中，机器人可观测自身的部分状态，机器人通过不断的与环境进行交互来获得回报最大的策略；在所述在线规划方法中，处理可观测部分时，把机器人的状态表示为一个信念，记为belief，其属于一个状态的集合，以POMDP算法通过构建信念树的方式执行前向搜索，以此来获得当前信念下的最优策略；所述信念树的每一个节点代表一个信念，父节点与子节点通过行为‑观测分支连接；所述POMDP算法是在线POMDP规划算法Kernel‑DESPOT；本发明算法性能优于DESPOT和POMCP，在收敛速度以及质量上具有优势。

Description

一种基于Kernel采样策略在不确定性环境下的在线规划方法

技术领域

本发明涉及机器人技术领域，尤其是一种基于Kernel采样策略在不确定性环境下的在线规划方法。

背景技术

随着信息技术的快速发展，机器人已经逐步的融入了日常生活。而运动规划作为机器人研究的重要领域，得到了广泛的关注。

基于采样的运动规划方法将连续模型转换成离散的模型，传统的基于采样的运动规划算法有RRT、PRM以及随机势场法等。RRT算法的特点是在较为复杂的环境下能够快速的找到路径，但存在路径质量差、在狭窄通道环境下效率低以及探索“盲目性”等问题。PRM和RRT都是概率完备且不最优的，PRM在随机点的布置及搜索方式上与PRM存在本质的区别，但同时存在离散点布置不完善和碰撞检测造成时间上的消耗。随机势场法可以很好的克服传统势场法引力与斥力相等时存在的局部最优解问题，但还是不可避免的存在当物体离目标点较远或目标点附近有障碍物时造成的与障碍物发生碰撞或难以到达目的地的问题。上诉算法中都避开了模型的不确定性问题，但现实环境下模型常常是不确定的，决策论规划对于解决存在不确定性下的规划具有重要意义，因此基于强化学习的运动规划研究是很好的研究课题。

强化学习是一个多领域的交叉学科，比如：机器人、深度学习以及控制工程等。在一个强化学习系统中，智能体通过不断的与一个不确定环境进行交互来获得最优策略使得长期奖励最大化。因此，强化学习是解决最优决策问题的重要方法。对于一个强化学习系统，智能体和环境不确定性一般可以表示为马尔可夫决策过程(MDP)和部分可观测马尔可夫决策过程(POMDP)。区别在于智能体在POMDP模型中，对于自身的状态是部分可观测的，但在MDP模型中，状态是完全可观测的。

在早期研究MDP问题主要关注于离散的状态和动作空间。但是在现实任务或者连续状态空间当中，算法的学习效率和适用性有待提高。近似强化学习方法能够有效的改善上述问题，比如价值函数近似、近似策略迭代以及演员-评价算法等。强化学习算法不仅关注于单一的长期奖励目标，而且在多目标的强化学习问题上也有很大的发展，如以多目标学习改善自主陆地车辆纵向控制的柔性等。

POMDP框架已经能够很好的解决现实世界的序列决策问题。当机器人在执行任务时，不确定性是制约机器人可靠运行的重要因素，不确定性包括：机器人控制误差、传感器噪声以及快速变化的环境等。因此，机器人在具有较大状态和观测空间的不确定性环境下实现规划是机器人领域重要的课题。POMDP提出了在不确定性环境下规划的基本框架。处理部分可观测的一个基本方法是将不确定性表示为一个信念(Belief)，为了更具体化，规划算法在信念树中执行前向搜索，信念树的每一个节点代表一个信念，父节点与子节点通过行为-观测分支连接起来。然而规划在一些最坏情况下是无法计算的，近似模拟的POMDP算法已经被广泛应用于许多任务中，如资源管理、无人驾驶、导航以及机械臂等。但是，POMDP规划任然存在由于“维度灾难”和“历史信息灾难”造成的计算难度问题。

最新的在线POMDP算法如DESPOT和POMCP都使用蒙特卡洛方法进行信念更新和树搜索，以此来处理维度灾难问题。这些算法将信念表示为一个采样状态集来克服状态空间较大造成的计算难度，DESPOT进一步通过采样行为-观测轨迹实现快速近似的计算当前信念不同策略的近似价值。在具有较大状态空间的POMDP任务中，最新的在线算法可以计算一个近似最优的策略。理论分析表明，少量的采样序列就可以保证近似最优的在线规划。在实际应用中，采样策略在概率采样算法中具有重要的作用，对于算法的性能影响很大。DESPOT和POMCP都采用随机采样的方式构建状态集，然而随机采样存在盲目性，不能很好的代表整个信念空间的收敛方向，因此基于该状态集计算的近似最优策略很有可能是局部近似最优的。

机器人的运动规划经过长久的发展，形成了基于人工势场的方法、基于数学模型的方法、基于图搜索的方法、基于节点的方法和基于采样的方法等众多不同的规划方法。为增加机械臂的灵活性和可操纵性，人们发明了冗余机械臂甚至超冗余机械臂，它们的自由度都大于6，由于机械臂运动规划的复杂程度随着机械臂自由度的增加而显著增大，因此冗余机械臂的运动规划通常需要考虑“维度灾难”的问题。基于采样的方法因在多维空间中具有显著优势而在机械臂运动规划领域中得到了广泛的关注。

我们在DESPOT基本框架上引入Kernel采样策略，提出Kernel-DESPOT在线规划算法。核方法已经被广泛的用于提高许多著名算法的实用性，如感知器网络、支持向量机以及自然语言处理等。虽然对于在线POMDP规划算法，机器人的状态或者环境信息是部分可观测的，但是机器人的状态是可以被分为部分可观测成分和可观测成分的。POMCP基于历史行为观测信息制定一个更好的策略用于指导行为选择。我们将历史观测信息是当前机器人可观测信息的重要成分之一。Kernel采样策略的核心在于把当前状态下机器人可观测的信息成分作为采样的重要影响因素。我们通过核函数计算机器人可观测信息与信念空间中状态信息的相关性，并以此作为采样的依据。Kernel采样策略获得的状态集避免了随机采样的盲目性，能够更好的代表信念空间，降低了相关性较差状态造成局部最优问题的概率。DESPOT在构建信念树时每一个采样状态的权重是均匀分布的，但对于当前机器人而言，随着环境不确定性的逐渐降低，状态的重要性应该是不同的。所以每一次采样我们都对状态依相关性程度进行权重分配。

发明内容

本发明提出一种基于Kernel采样策略在不确定性环境下的在线规划方法，该方法克服了现有强化学习运动规划算法的不足，算法性能优于DESPOT和POMCP，在收敛速度以及质量上具有优势。

本发明采用以下技术方案。

一种基于Kernel采样策略在不确定性环境下的在线规划方法，用于对机器人在不确定性环境下执行任务时的规划，在该不确定性环境中，表示为POMDP模型的不确定性是制约机器人可靠运行的主因；所述POMDP模型中，机器人可观测自身的部分状态，机器人通过不断的与环境进行交互来获得回报最大的策略；在所述在线规划方法中，处理可观测部分时，把机器人的状态表示为一个信念，记为belief，其属于一个状态的集合，以POMDP算法通过构建信念树的方式执行前向搜索，以此来获得当前信念下的最优策略；所述信念树的每一个节点代表一个信念，父节点与子节点通过行为-观测分支连接；

所述POMDP算法是在线POMDP规划算法Kernel-DESPOT，包括以下步骤；

步骤S1、在机器人当前信念空间b中，依据Kernel采样策略采样K个状态构建采样状态集合Φ_b，并对每一个状态进行权重的分配；

步骤S2、通过Kernel-DESPOT算法以b作为根节点构建信念树D；

步骤S3、初始化机器人当前信念b经验价值

的上界U(b)和下界L(b)，以及RK-WDU最优价值V^*(b)的上界μ(b)和下界l(b)；

步骤S4、定义机器人当前信念的不确定性为ε(b)←μ(b)-l(b)；

步骤S5、如果不确定性ε(b)大于理想值ò₀，并且算法的总运行时间小于T_max，则对根节点b₀进行扩展；

步骤S6、当信念树停止扩展时，执行BACKUP(D,b)；

在BACKUP(D,b)执行完毕之后，会更新跟节点的不确定性ε(b)，重新判断不确定性是否小于ò₀或者运行时间是否大于T_max，如果条件满足，则Kernel-DESPOT法返回b的l(b)值；

步骤S7、最终对于根节点b，算法会选择一个最优行为a^*使得信念树返回的l(b)最大，即a^*←max_a∈Al(b,a)；

比较信念树计算的最优行为a^*对应的价值l(b,a^*)和通过默认策略π₀初始化的价值L(b)的大小，如果L(b)更大，则将最优行为修改为默认策略，即a^*←π₀(b)；

步骤S8、机器重复以上的过程，直到最终到达目标点。

步骤S1具体实现方式为：Kernel采样策略核函数定义

其中，x表示当前机器人状态可观测信息，x_i表示信念空间中状态可观测信息，||x||为x的范数，

为克罗内克符号。K(x,x_i)表示x与x_i的相似程度，因此可以依据K(x,x_i)采样跟当前状态信息高度相关的K个状态；Kernel-DESPOT信念树每一个节点b都含有一个集合Φ_b，该集合表示经过节点b的所有序列。每个序列的起始状态构成采样状态集合；对于当前信念b，序列φ的起始状态s₀的权重为

其中，φ∈Φ_b，x_i为状态s₀的可观测部分信息；

定义σ_n ²为测量噪声方差，表示上一个采样周期中信念空间所有状态的K(x,x_i)值的方差；定义σ_f ²为信号方差。

步骤S2的具体实现形式为：通过经验价值的计算形式

其中V_π,φ表示通过模拟策略π计算每一个采样序列_φ∈Φb的总折扣奖励之和。U(b)是通过假设所有状态是完全可观测的，也就是将POMDP问题转换成MDP问题，然后计算MDP环境下的最优价值V_MDP

经验价值下界的计算是通过给定一个默认策略π₀，对于DESPOT中的每一个节点b的每一个序列Φ_b模拟默认策略进行有限次时步的探索，计算每一个序列的总折扣奖励再求平均值获得。

而RK-WDU的上下界μ(b)和l(b)可以通过U(b)和L(b)求得：

其中，γ是一个折扣因子，Δ(b)表示节点b略树π中的深度，π_b是b处的子树，|π_b|表示π_b的大小，加权

到达b概率的经验估计。

步骤S5的具体实现形式为：定义b′＝τ(b,a,z)为b采取行为a和获得观测z到达的子节点。所以当对节点b执行扩展树操作时，首先会初始化所有b的所有子节点b′的值U(b′),L(b′),μ(b′),andl(b′)，如步骤S3所示；然后每一次的探索都在致力于将根节点b处的当前差值ε(b)减小至目标差值ξε(b)，其中ξò(0,1)是一个常量；在探索的过程中，每一个节点b的最优行为选择都依赖于b的上界μ(b)：

在执行a^*之后，通过选择使多余不确定最大的观测z^*来获得子节点b′＝τ(b,a^*,z)：

上述扩展树的过程会一直重复，直到Δ(b)＞D表示扩展到了信念树的最大深度；或者节点b的不确定性已经降到预期值，即E(b)＜0，继续探索对b没有意义；还存在一种情况扩展树会停止前向探索，即b′的父节点b已经没有足够的采样序列：

l(b,b′)表示从b到b′路径上节点的数量；如果父节点b采样序列不够，那么继续扩展b会增加b′子策略树的数量可能会造成过拟合并且降低b′正则化的效果。如果在扩展树的过程中如果满足上式，则需要执行剪枝PRUNE(D,b)操作。

步骤操作PRUNE(D,b)的具体实现形式是：在因为父节点b采样序列不够停止前向搜索之后，对于父节点b价值计算分别将初始下界赋值给上界，也就是表明当前节点b的不确定性已经满足要求，即：

U(b)←L(b)

μ(b)←l(b)

之后同样执行BACKUP(D,b)。

步骤操作BACKUP(D,b)具体实现方式为：当需要执行BACKUP(D,b)时，Kernel-DESPOT遵循贝尔曼规则沿着路径自下而上的更新信念树中节点的价值：

其中b'为b的子节点，b′＝τ(b,a,z)。

相较于现有技术，本发明具有以下有益效果：

相比于最新的在线POMDP规划算法DESPOT和POMCP算法，本发明提出的算法有如下优势：

(1)本发明提出的算法是近似最优的；

(2)Kernel采样策略的核心在于把当前状态下机器人可观测的信息成分作为采样的重要影响因素。我们通过核函数计算机器人可观测信息与信念空间中状态信息的相关性，并以此作为采样的依据。Kernel采样策略获得的状态集避免了随机采样的盲目性，能够更好的代表信念空间，降低了相关性较差状态造成局部最优问题的概率；

(3)DESPOT在构建信念树时每一个采样状态的权重是均匀分布的，但对于当前机器人而言，随着环境不确定性的逐渐降低，状态的重要性应该是不同的。所以每一次采样Kernel-DESPOT都对状态依相关性程度进行权重分配；

(4)Kernel采样策略和权重分配都提分别提高了算法性能。

附图说明

下面结合附图和具体实施方式对本发明进一步详细的说明：

附图1是本发明的流程示意图；

附图2是本发明的信念树的扩展形式示意图(实线圆表示信念节点，黑色的正方形表示信念-行为节点；树，不同的实心圆表示依据采样策略采样的状态，不同大小的实心三角形表示状态的权重，不同的轨迹表示采样状态对应的采样序列)；

附图3是本发明在四种常见POMDP评价仿真环境的示意图(四个主要环境分别是(a)Tag。机器人追逐想要逃离的目标。(b)LaserTag。机器人在随机散布障碍物的网格中追逐目标，机器人搭载着雷达用于搜寻目标和发现障碍物。(c)RockSample。机器人漫游车可以检测岩石，以识别"好"的岩石并对其进行采样。完成后，从最右边边界退出。(d)原始Pocman游戏)；

附图4是本发明中不同采样序列对算法性能影响示意图((a)Tag。(b)LaserTag。(c)RockSample。)；

附图5是本发明运行时间在归一化后的示意图(不同任务算法平均运行时间对比)；

附图6是本发明收敛性能归一化后的示意图(不同任务算法收敛程度对比)；

附图7是本发明在常见POMDP评价仿真环境下的算法性能表示意图(表示了两个算法在六个不同任务中的平均折扣奖励)；

附图8是本发明对算法性能表的影响示意图(kernel-Despot包含主要的两部分：依据Kernel采样策略和对采样状态集每一个状态进行权重分配。Reweighted表示仅依据Kernel进行采样而不进行权重分配；Kernel Sampling Strategy表示采取随机采样的采样策略，但是对随机采样的状态集进行权重分配)。

具体实施方式

如图所示，一种基于Kernel采样策略在不确定性环境下的在线规划方法，用于对机器人在不确定性环境下执行任务时的规划，在该不确定性环境中，表示为POMDP模型的不确定性是制约机器人可靠运行的主因；所述POMDP模型中，机器人可观测自身的部分状态，机器人通过不断的与环境进行交互来获得回报最大的策略；

在所述在线规划方法中，处理可观测部分时，把机器人的状态表示为一个信念，记为belief，其属于一个状态的集合，以POMDP算法通过构建信念树的方式执行前向搜索，以此来获得当前信念下的最优策略；所述信念树的每一个节点代表一个信念，父节点与子节点通过行为-观测分支连接；

所述POMDP算法是在线POMDP规划算法Kernel-DESPOT，包括以下步骤；

步骤S1、在机器人当前信念空间b中，依据Kernel采样策略采样K个状态构建采样状态集合Φ_b，并对每一个状态进行权重的分配；

步骤S2、通过Kernel-DESPOT算法以b作为根节点构建信念树D；

步骤S3、初始化机器人当前信念b经验价值

的上界U(b)和下界L(b)，以及RK-WDU最优价值V^*(b)的上界μ(b)和下界l(b)；

步骤S4、定义机器人当前信念的不确定性为ε(b)←μ(b)-l(b)；

步骤S5、如果不确定性ε(b)大于理想值ò₀，并且算法的总运行时间小于T_max，则对根节点b₀进行扩展；

步骤S6、当信念树停止扩展时，执行BACKUP(D,b)；

在BACKUP(D,b)执行完毕之后，会更新跟节点的不确定性ε(b)，重新判断不确定性是否小于ò₀或者运行时间是否大于T_max，如果条件满足，则Kernel-DESPOT法返回b的l(b)值；

步骤S7、最终对于根节点b，算法会选择一个最优行为a^*使得信念树返回的l(b)最大，即a^*←max_a∈Al(b,a)；

比较信念树计算的最优行为a^*对应的价值l(b,a^*)和通过默认策略π₀初始化的价值L(b)的大小，如果L(b)更大，则将最优行为修改为默认策略，即a^*←π₀(b)；

步骤S8、机器重复以上的过程，直到最终到达目标点。

步骤S1具体实现方式为：Kernel采样策略核函数定义

其中，x表示当前机器人状态可观测信息，x_i表示信念空间中状态可观测信息，||x||为x的范数，

为克罗内克符号。K(x,x_i)表示x与x_i的相似程度，因此可以依据K(x,x_i)采样跟当前状态信息高度相关的K个状态；Kernel-DESPOT信念树每一个节点b都含有一个集合Φ_b，该集合表示经过节点b的所有序列。每个序列的起始状态构成采样状态集合；对于当前信念b，序列φ的起始状态s₀的权重为

其中，φ∈Φ_b，x_i为状态s₀的可观测部分信息；

定义σ_n ²为测量噪声方差，表示上一个采样周期中信念空间所有状态的K(x,x_i)值的方差；定义σ_f ²为信号方差。

步骤S2的具体实现形式为：通过经验价值的计算形式

其中V_π,φ表示通过模拟策略π计算每一个采样序列_φ∈Φb的总折扣奖励之和。U(b)是通过假设所有状态是完全可观测的，也就是将POMDP问题转换成MDP问题，然后计算MDP环境下的最优价值V_MDP

经验价值下界的计算是通过给定一个默认策略π₀，对于DESPOT中的每一个节点b的每一个序列Φ_b模拟默认策略进行有限次时步的探索，计算每一个序列的总折扣奖励再求平均值获得。

而RK-WDU的上下界μ(b)和l(b)可以通过U(b)和L(b)求得：

其中，γ是一个折扣因子，Δ(b)表示节点b略树π中的深度，π_b是b处的子树，|π_b|表示π_b的大小，加权

到达b概率的经验估计。

步骤S5的具体实现形式为：定义b′＝τ(b,a,z)为b采取行为a和获得观测z到达的子节点。所以当对节点b执行扩展树操作时，首先会初始化所有b的所有子节点b′的值U(b′),L(b′),μ(b′),andl(b′)，如步骤S3所示；然后每一次的探索都在致力于将根节点b处的当前差值ε(b)减小至目标差值ξε(b)，其中ξò(0,1)是一个常量；在探索的过程中，每一个节点b的最优行为选择都依赖于b的上界μ(b)：

在执行a^*之后，通过选择使多余不确定最大的观测z^*来获得子节点b′＝τ(b,a^*,z)：

上述扩展树的过程会一直重复，直到Δ(b)＞D表示扩展到了信念树的最大深度；或者节点b的不确定性已经降到预期值，即E(b)＜0，继续探索对b没有意义；还存在一种情况扩展树会停止前向探索，即b′的父节点b已经没有足够的采样序列：

l(b,b′)表示从b到b′路径上节点的数量；如果父节点b采样序列不够，那么继续扩展b会增加b′子策略树的数量可能会造成过拟合并且降低b′正则化的效果。如果在扩展树的过程中如果满足上式，则需要执行剪枝PRUNE(D,b)操作。

步骤操作PRUNE(D,b)的具体实现形式是：在因为父节点b采样序列不够停止前向搜索之后，对于父节点b价值计算分别将初始下界赋值给上界，也就是表明当前节点b的不确定性已经满足要求，即：

U(b)←L(b)

μ(b)←l(b)

之后同样执行BACKUP(D,b)。

步骤操作BACKUP(D,b)具体实现方式为：当需要执行BACKUP(D,b)时，Kernel-DESPOT遵循贝尔曼规则沿着路径自下而上的更新信念树中节点的价值：

其中b'为b的子节点，b′＝τ(b,a,z)。

实施例：

本实施例中，采用的算法的完整伪代码，具体如下：

以下用具体的实验对本发明的实施方式进行详细说明，本发明提供一种基于Kernel采样策略的在不确定性环境下规划方法，对于POMDP规划问题，有一些标准POMDP仿真评价环境，所以主要通过常见的仿真评价环境测试Kernel-DESPOT算法的性能，并与最新的POMDP算法进行比较。具体实验设置如下：

仿真实验：

仿真实验在Ubuntu系统中进行。

我们在六个仿真任务中评估Kernel-DESPOT算法的性能(表格1)，这六个任务是评价POMDP算法常见的评价基准。在环境Tag、LaserTag以及RockSample中设置采样序列K＝500，环境Pocman中设置K＝100，并根据不同的环境具体要求设置初始上下界的计算方法作为启发。所有的算法都在统一的平台上进行仿真，并且设置在线POMDP算法的最大运行时间为1秒钟。Kernel-DESPOT主要包含两个部分：基于Kernel的相关性采样和采样状态集的权重再分配。我们通过表格2说明这两部分分别对算法性能的影响。为了进一步说明Kernel-DESPOT算法的性能，我们从图4：本发明中不同采样序列对算法性能影响示意图、图5：是本发明运行时间在归一化后的示意图、图6：是本发明收敛性能归一化后的示意图这三个角度说明Kernel-DESPOT的优越性。根据

的定义可知，变量x即当前机器人状态可获得的信息是计算核函数的关键。对于每一个不用的ROMDP环境，机器人当前状态下可获得的信息是不同的，所以变量x是取决于环境的特性的。但是我们都将机器人当前状态可获得的信息转换成位置关系，因此x实际上是一个位置向量。然后用该位置向量与信念空间中的状态进行相关性计算。

(1)仿真环境一：TAG

Tag是Pineau等人于2003年提出的标准POMDP基准。一个机器人和一个目标物在29个可能的网格位置中行走(图3a)。机器人的目标是找到并抓住目标物，而目标物始终想要逃离机器人。他们的启示位置是随机的，机器人知道自己的位置，但是只有与目标物在同一位置时才能观测到目标的位置。机器人可以不动或者向相邻的四个位置移动，每一次移动将消耗-1的奖励。除此之外，机器人可以执行“tag”的行为，如机器人与目标物在同一个位置那么获得+10的奖励，否则奖励值为-10。

在Tag环境中，由于机器人的观测值仅包含自身的位置信息，所以在构建向量x时我们考虑历史观测信息的作用。我们将当前机器人位置与历史观测信息中机器人位置构成相对位置向量x，随着历史观测信息的增加，为了减少计算量我们只考虑三个时步内的历史信息，如果当前机器人位置分别与三个时步内的历史信息构建的位置向量x存在很大的偏差，那么我们以临近时步的信息为准。上述方法主要是为了避免机器人在短时间内重复探索相同的区域。

(2)仿真场景二：LaserTag

LaserTag是Tag环境的延伸版本，特点是具有较大的观测空间。在LaserTag环境中，机器人在7×11的矩形方格中移动，并且随机放置8个障碍物(图3b)。机器人和目标物的行为保持一样，不同的是机器人并不确切的知道自己的位置，初始的时候位置信息在网格中呈均匀分布。为了实现定位，机器人搭载一个雷达可以测量8个方向的距离。每个方向上的雷达读数是以机器人在该方向上距离最近障碍物真实距离为中心的标准正太分布，标准方差是2.5。

在LaserTag环境中，我们通过雷达的观测值来构建向量x。机器人可以通过雷达识别八个方向上与障碍物或者目标物的最近距离，但是这个最近距离是以标准正太分布呈现的。所以当目标物出现在当前机器人雷达观测的八个方向上时，我们以目标物所在的方向概率最大的最近距离构建一个相对位置向量x。然后依据核函数进行信念空间状态与当前机器人状态的相似度计算构建采样状态集。即时机器人不知道当前位置，并且它的观测存在误差，但是我们依然可以近似构建一个目标与机器人的相对位置矢量x。虽然依据观测结果判断目标物的位置与真实目标物所在位置存在误差，但是它提供了目标物重要的大致方向信息，那么在采样时就会很大程度上避免采样到与该方向背离程度很大的状态。

(3)仿真环境三：RockSample

RockSample(Smith&Simmons，2004)是一个具有较大状态空间的成熟评价基准(图3c)。RS(n，k)，表示机器人漫游车在一个n×n并包含k个石头的网格中探寻，期中k个石头可能是“好的”或者“坏的”。机器人的目的是探寻这些石头并采样当中好的石头，当完成所有的探寻之后从网格的最右边退出。每一步，机器人可以采取的行为包括：向邻近的网格移动、感知一个石头的好坏以及采样一个石头。执行采样行为时，如果石头是好的则获得+10的奖励，否则奖励值为-10。执行移动或者感知的行为不会有任何的奖励，移动或者采样行为不产生观察值，只有感知行为会产生一个观察：好或者坏，观察的准确度随着机器人与石头的距离呈指数下降。为了获得更高的奖励，机器人在网格中导航并感知石头的好坏，与此同时利用获得的信息访问并采样好的石头。

在RockSample环境中，我们构建位置向量x的思路很简单，就是如果上一个行为是感知，并且获得观测值是好的，那么我们以这个石头所在的位置与当前机器人所在的位置构建位置向量x，然后在信念空间中采样与x相关性较高的状态。该位置向量将保持不变，直到下一次执行感知行为。如果机器人连续执行感知行为，获得的观测值都是好的，那么以准确度最高的观测作为依据构建位置向量x。上述方法的核心思想在于让机器人相信观测的结果，以观测信息引导采样，而把与观测信息相似度不高的状态当作是无用状态，这些状态对策略的计算不起积极作用，反而会造成局部最优问题。

(4)仿真环境四：Pocman

Pocman(Silver&Veness，2010)一款流行同名视频游戏的部分可观测变体(图3d)。智能体和四个精灵在17×19的迷宫中行走，迷宫中分布着食物。智能体的每一次移动会有-1的惩罚，每一个食物代表+10的奖励，如果智能体被精灵捕获游戏终止并造成-100的惩罚。另外，迷宫中还存在四个强力食物，智能体吃了强力食物之后的15步内可以追捕精灵，成功追捕到精灵可获得+25的奖励。精灵与智能体的曼哈顿距离在5之内，精灵将会追捕智能体；但是如果智能体吃了强力食物，那么精灵将会远离智能体。智能体并不知道精灵的具体位置，但是可以获取如下信息：智能体的主要方向上是否有精灵，曼哈顿距离为2的范围内是否有精灵，智能体的主要方向上是否有墙壁，在相邻或者对角线相邻的位置上是否有食物。Pocman具有非常大的状态空间，接近10⁵⁶个状态。

在Pocman环境中，由于智能体可以知道相邻或者对角线相邻的位置上是否有食物，所以位置向量x的构建是容易的。如果相邻或者对角相邻位置上存在食物，那么以该食物的位置与当前智能体位置构建向量x，并且以相邻位置作为优先级。依据上述方法，可以有效避免由随机采样造成的智能体行走的盲目性。

(5)Kernel Sample Strategy和StateReweighting对算法性能影响比较Kernel-DESPOT的主要贡献在于提出了基于核函数

的采样策略和采样状态集的权重分配。为了更好说明这两部分对算法性能的影响，我们依据控制变量法测试了六个环境下平均折扣奖励。如果一个POMDP环境的观测空间较大的，那么与之对应的信念树规模也是比较大的，在这种环境下随机采样造成的过拟合现象就更加明显，过拟合现象表现在机器人容易陷入局部最优。Kernel-DESPOT利用信念空间状态与当前状态相似度作为采样依据构建采样状态集，并且依据相似程度分配采样状态权重。我们希望依据上述方法可以改善过拟合造成的局部最优问题。从表格2可知，在具有较大观测空间的Tag、LaserTag以及Pocman环境中，无论是仅依据

进行采样还是随机采样但是对采样状态集进行权重分配对算法性能的提升都是显著的，而且在RockSample环境中随着状态数量的增加，Kernel-DESPOT的优越性在逐步凸显。

(6)Kernel-DESPOT运行时间以及收敛性能比较

对于每一个节点b，假设初始上界U₀是以误差δ近似的：

如果初始上界的误差δ＝0，那么它为

的真实上界。

假设T_max是有限的，实时DESPOT算法构建一个部分信念树DESPOT

根节点b₀上下界差距为ε(b₀)。那么源自

的正则化最优策略

满足：

v^*(b₀)是完整Kernel-DESPOT信念树计算出的正则化最优策略。ε(b₀)随着T_max增加而单调递减，因此

随着时间的增加会逐渐逼近最优正则化策略。而且初始上界的误差对最终结果的影响程度最多δ。

依据Kernel-DESPOT获得的采样状态集更符合信念空间的收敛方向，所以在有限时间内ε(b₀)减小的更快，

能够更快的收敛到最优策略，Kernel-DESPOT在整体计算时间上更快。图5展示了不同任务算法运行时间的对比，纵坐标表示同一个任务不同算法在归一化处理之后运行时间的占比。整体上，Kernel-DESPOT算法的计算速度是有优势的。由于Kernel-DESPOT是在线POMDP规划算法，算法每一时步的最大运算时间是1s，所以在有限时间内算法很难将当前信念的不确定性降低至0，也就是说通常情况下ε(b₀)＞0。而ε(b₀)的大小反应了算法的收敛程度，所以我们以每一时步的平均ε(b₀)值作为衡量算法收敛性能的指标，如图6所示。Kernel-DESPOT和在不同任务中收敛程度展示，纵坐标表示同一个任务不同算法在归一化处理后的平均ε(b0₎占比。

Claims (5)

1.一种基于Kernel采样策略在不确定性环境下的在线规划方法，用于对机器人在不确定性环境下执行任务时的规划，其特征在于：在该不确定性环境中，表示为POMDP模型的不确定性是制约机器人可靠运行的主因；所述POMDP模型中，机器人可观测自身的部分状态，机器人通过不断的与环境进行交互来获得回报最大的策略；

在所述在线规划方法中，处理可观测部分时，把机器人的状态表示为一个信念，记为belief，其属于一个状态的集合，以POMDP算法通过构建信念树的方式执行前向搜索，以此来获得当前信念下的最优策略；所述信念树的每一个节点代表一个信念，父节点与子节点通过行为-观测分支连接；

所述POMDP算法是在线POMDP规划算法Kernel-DESPOT，包括以下步骤；

步骤S1、在机器人当前信念空间b中，依据Kernel采样策略采样K个状态构建采样状态集合Φ_b，并对每一个状态进行权重的分配；

步骤S2、通过Kernel-DESPOT算法以b作为根节点构建信念树D；

步骤S3、初始化机器人当前信念b经验价值

的上界U(b)和下界L(b)，以及RK-WDU最优价值V^*(b)的上界μ(b)和下界l(b)；

步骤S4、定义机器人当前信念的不确定性为ε(b)←μ(b)-l(b)；

步骤S5、如果不确定性ε(b)大于理想值

并且算法的总运行时间小于T_max，则对根节点b₀进行扩展；

步骤S6、当信念树停止扩展时，执行BACKUP(D,b)；

在BACKUP(D,b)执行完毕之后，会更新根节点的不确定性ε(b)，重新判断不确定性是否小于ò₀或者运行时间是否大于T_max，如果条件满足，则Kernel-DESPOT算法返回b的l(b)值；

步骤S7、最终对于根节点b，算法会选择一个最优行为a^*使得信念树返回的l(b)最大，即a^*←max_a∈Al(b,a)；

比较信念树计算的最优行为a^*对应的价值l(b,a^*)和通过默认策略π₀初始化的价值L(b)的大小，如果L(b)更大，则将最优行为修改为默认策略，即a^*←π₀(b)；

步骤S8、机器重复以上的步骤，直到最终到达目标点；

步骤S1具体实现方式为：Kernel采样策略核函数定义

其中，

在核函数中表示的是向量的转置；x表示当前机器人状态可观测信息，x_i表示信念空间中状态可观测信息，||x||为x的范数，

为克罗内克符号；K(x,x_i)表示x与x_i的相似程度，因此可以依据K(x,x_i)采样跟当前状态信息高度相关的K个状态；Kernel-DESPOT信念树每一个节点b都含有一个集合Φ_b，该集合表示经过节点b的所有序列；每个序列的起始状态构成采样状态集合；对于当前信念b，序列φ的起始状态s₀的权重为

其中，φ∈Φ_b，x_i为状态s₀的可观测部分信息；

定义σ_n ²为测量噪声方差，表示上一个采样周期中信念空间所有状态的K(x,x_i)值的方差；定义σ_f ²为信号方差。

2.根据权利要求1所述的一种基于Kernel采样策略在不确定性环境下的在线规划方法，其特征在于：步骤S3的具体实现形式为：通过经验价值的计算形式

其中V_π,φ表示通过模拟策略π计算每一个采样序列φ∈Φ_b的总折扣奖励之和；因此

表示在当前信念b执行策略π所获得的经验价值；U(b)是通过假设所有状态是完全可观测的，也就是将POMDP问题转换成MDP问题，然后计算MDP环境下的最优价值V_MDP

经验价值下界的计算是通过给定一个默认策略π₀，对于DESPOT中的每一个节点b的每一个序列Φ_b模拟默认策略进行有限次时步的探索，计算每一个序列的总折扣奖励再求平均值获得，s_φ是序列φ中的起始状态s₀；

而RK-WDU的上下界μ(b)和l(b)可以通过U(b)和L(b)求得：

其中，γ是一个折扣因子，Δ(b)表示节点b略树π中的深度，加权

到达b概率的经验估计，λ＞0，为正则化项，能够有效避免信念树构建过程中的过拟合问题，

为核权重折扣效果，公式四和公式五是RK-WDU想法在算法中的体现。

3.根据权利要求2所述的一种基于Kernel采样策略在不确定性环境下的在线规划方法，其特征在于：步骤S5的具体实现形式为：定义b′＝τ(b,a,z)为b采取行为a和获得观测z到达的子节点；所以当对节点b执行扩展树操作时，首先会初始化所有b的所有子节点b′的值U(b′)，L(b′)，μ(b′)和l(b′)，如步骤S3所示；然后每一次的探索都在致力于将根节点b处的当前差值ε(b)减小至目标差值ξε(b)，其中ξò(0,1)是一个常量；

在探索的过程中，每一个节点b的最优行为选择都依赖于b的上界μ(b)：

ρ(b,a)表示将正则化项引入信念树的构建过程；在执行a^*之后，通过选择使多余不确定最大的观测z^*来获得子节点b′＝τ(b,a^*,z)：

上述扩展树的过程会一直重复，直到Δ(b)＞D表示扩展到了信念树的最大深度；或者节点b的不确定性已经降到预期值，即E(b)＜0，继续探索对b没有意义；还存在一种情况扩展树会停止前向探索，即b′的父节点b已经没有足够的采样序列：

l(b,b′)表示从b到b′路径上节点的数量；如果父节点b采样序列不够，那么继续扩展b会增加b′子策略树的数量可能会造成过拟合并且降低b′正则化的效果；如果在扩展树的过程中如果满足上式，则需要执行剪枝PRUNE(D,b)操作。

4.根据权利要求3所述的一种基于Kernel采样策略在不确定性环境下的在线规划方法，其特征在于：步骤操作PRUNE(D,b)的具体实现形式是：在因为父节点b采样序列不够停止前向搜索之后，对于父节点b价值计算分别将初始下界赋值给上界，也就是表明当前节点b的不确定性已经满足要求，即：

U(b)←L(b)

μ(b)←l(b)

之后同样执行BACKUP(D,b)。

5.根据权利要求4所述的一种基于Kernel采样策略在不确定性环境下的在线规划方法，其特征在于：步骤操作BACKUP(D,b)具体实现方式为：当需要执行BACKUP(D,b)时，Kernel-DESPOT遵循贝尔曼规则沿着路径自下而上的更新信念树中节点的价值：

其中b'为b的子节点，b′＝τ(b,a,z)。

Images