基于策略迭代和值迭代的POMDP算法

部分可观察Markov决策过程是通过引入信念状态空间将非Markov链问题转化为Markov链问题来求解,其描述真实世界的特性使它成为研究随机决策过程的重要分支.介绍了部分可观察Markov决策过程的基本原理和决策过程,提出一种基于策略迭代和值迭代的部分可观察Markov决策算法,该算法利用线性规划和动态规划的思想,解决当信念状态空间较大时出现的"维数灾"问题,得到Markov决策的逼近最优解.实验数据表明该算法是可行的和有效的.     

一种基于信念状态压缩的实时POMDP算法

针对求解部分可观察马尔可夫决策过程（POMDP）信念状态空间是NP难问题．提出一种信念状态空间压缩（BSSC）算法．将信念状态空间的高维压缩到低维，利用动态贝叶斯网络对状态转移函数、观察函数和报酬函数进行压缩。降低求解规模，达到实时决策的目的．对比实验表明，所提出的算法可以快速求解最优策略和最优值函数．     

基于Monte Carlo 粒子滤波的POMDPs 在线算法

针对部分可观察马尔可夫决策过程(POMDPs)的信念状态空间是一个双指数规模问题,提出一种基于 Monte Carlo 粒子滤波的 POMDPs 在线算法.首先,分别采用粒子滤波和粒子映射更新和扩展信念状态,建立可达信念状态与或树;然后,采用分支界限裁剪方法对信念状态与或树进行裁剪,降低求解规模.实验结果表明,所提出算法具有较低的误差率和较快的收敛性,能够满足系统实时性的要求.     

基于点的POMDPs在线值迭代算法

部分可观察马尔可夫决策过程(partially observable Markov decision processes,简称POMDPs)是动态不确定环境下序贯决策的理想模型,但是现有离线算法陷入信念状态“维数灾”和“历史灾”问题,而现有在线算法无法同时满足低误差与高实时性的要求,造成理想的POMDPs模型无法在实际工程中得到应用.对此,提出一种基于点的POMDPs在线值迭代算法(point-based online value iteration,简称PBOVI).该算法在给定的可达信念状态点上进行更新操作,避免对整个信念状态空间单纯体进行求解,加速问题求解;采用分支界限裁剪方法对信念状态与或树进行在线裁剪;提出信念状态结点重用思想,重用上一时刻已求解出的信念状态点,避免重复计算.实验结果表明,该算法具有较低误差率、较快收敛性,满足系统实时性的要求.     

基于马尔可夫决策过程的群体动画运动轨迹生成

近些年来,群体动画在机器人学、电影、游戏等领域得到了广泛的研究和应用,但传统的群体动画技术均涉及复杂的运动规划或碰撞避免操作,计算效率较低.本文提出了一种基于马尔可夫决策过程（MDPs）的群体动画运动轨迹生成算法,该算法无需碰撞检测即可生成各智能体的无碰撞运动轨迹.同时本文还提出了一种改进的值迭代算法用于求解马尔可夫决策过程的状态-值,利用该算法在栅格环境中进行实验,结果表明该算法的计算效率明显高于使用欧氏距离作为启发式的值迭代算法和Dijkstra算法.利用本文提出的运动轨迹生成算法在三维（3D）动画场景中进行群体动画仿真实验,结果表明该算法可实现群体无碰撞地朝向目标运动,并具有多样性.     

WSN中一种目标追踪在线节点调度算法

针对目标追踪无线传感器网络节点能量有限、感知信息存在不确定性等问题,提出一种基于部分可观察马尔可夫决策过程的在线节点调度算法。通过状态转移函数和观察函数描述移动目标的不确定性,根据奖赏函数平衡追踪性能和节点能量消耗,并构造有限深度的可达信念与或树降低运算复杂度,实现调度策略在线求解。实验结果表明,该算法能平衡目标追踪质量与节点能量消耗,且满足实时性 要求。     

SHP-Ⅵ:一种基于最短哈密顿通路的POMDP值迭代算法

基于试探(trial-based)的值迭代算法是求解部分可观察Markov决策过程(partially observable Markov decision process,POMDP)模型的一类有效算法,其中FSVI算法是目前最快的算法之一.然而对于较大规模的POMDP问题,FSVI计算MDP值函数的时间是不容忽视的.提出一种基于最短哈密顿通路(shortest Hamiltonian path)的值迭代算法(shortest Hamiltonian path-based value iteration,SHP-VI).该方法用求解最短哈密顿通路问题的蚁群算法计算一条最优信念状态轨迹,然后在这些信念状态上反向更新值函数.通过与FSVI算法的实验比较,结果表明SHP-VI算法很大程度地提高了基于试探的算法计算信念状态轨迹的效率.     

基于观测的POMDP 优化算法及其仿真

在分析马尔可夫决策过程（Markov Decision Process, MDP）性能灵敏度的基础上,讨论了部分可观 测马尔可夫决策过程（Partially Observable Markov Decision Process, POMDP）的性能优化问题．给出了POMDP 性能灵敏度分析公式,并以此为基础提出了两种基于观测的POMDP 优化算法：策略梯度优化算法和策略迭 代优化算法．最后以准许控制问题为仿真实例,验证了这两个算法的有效性．     

SHP-VI:一种基于最短哈密顿通路的POMDP值迭代算法

基于试探(trial-based)的值迭代算法是求解部分可观察Markov决策过程(partially observable Markov decision process,POMDP)模型的一类有效算法,其中FSVI算法是目前最快的算法之一.然而对于较大规模的POMDP问题,FSVI计算MDP值函数的时间是不容忽视的.提出一种基于最短哈密顿通路(shortest Hamiltonian path)的值迭代算法(shortest Hamiltonian path-based value iteration,SHP-VI).该方法用求解最短哈密顿通路问题的蚁群算法计算一条最优信念状态轨迹,然后在这些信念状态上反向更新值函数.通过与FSVI算法的实验比较,结果表明SHP-VI算法很大程度地提高了基于试探的算法计算信念状态轨迹的效率.     

动态影响图模型研究

部分可观察马尔可夫决策过程在策略空间和状态空间上的计算复杂性,使求解其一个最优策略成为NP-hard难题.为此,提出一种动态影响图模型来建模不确定环境下的Agent动态决策问题.动态影响图模型以有向无环图表示系统变量之间的复杂关系.首先,动态影响图利用动态贝叶斯网络表示转移模型和观察模型以简化系统的状态空间;其次,效用函数以效用结点的形式清晰地表示出来,从而简化系统效用函数的表示;最后,通过决策结点表示系统的行为来简化系统的策略空间.通过实例从3个方面和POMDP模型进行了比较,研究的结果表明,动态影响图模型为大型的POMDP问题提供了一种简明的表示方式,最后在Robocup环境初步验证了该模型.     

A Modified Memory-Based Reinforcement Learning Method for Solving POMDP Problems

Partially observable Markov decision processes (POMDP) provide a mathematical framework for agent planning under stochastic and partially observable environments. The classic Bayesian optimal solution can be obtained by transforming the problem into Markov decision process (MDP) using belief states. However, because the belief state space is continuous and multi-dimensional, the problem is highly intractable. Many practical heuristic based methods are proposed, but most of them require a complete POMDP model of the environment, which is not always practical. This article introduces a modified memory-based reinforcement learning algorithm called modified U-Tree that is capable of learning from raw sensor experiences with minimum prior knowledge. This article describes an enhancement of the original U-Tree’s state generation process to make the generated model more compact, and also proposes a modification of the statistical test for reward estimation, which allows the algorithm to be benchmarked against some traditional model-based algorithms with a set of well known POMDP problems.     

An online multi-agent co-operative learning algorithm in POMDPs

Solving partially observable Markov decision processes (POMDPs) is a complex task that is often intractable. This paper examines the problem of finding an optimal policy for POMDPs. While a lot of effort has been made to develop algorithms to solve POMDPs, the question of automatically finding good low-dimensional spaces in multi-agent co-operative learning domains has not been explored thoroughly. To identify this question, an online algorithm CMEAS is presented to improve the POMDP model. This algorithm is based on a look-ahead search to find the best action to execute at each cycle. Thus the overwhelming complexity of computing a policy for each possible situation is avoided. A series of simulations demonstrate this good strategy and performance of the proposed algorithm when multiple agents co-operate to find an optimal policy for POMDPs.     

基于采样的POMDP近似算法

部分可观察马尔科夫决策过程（POMDP）是一种描述机器人在动态不确定环境下行动选择的问题模型。对于具有稀疏转移矩阵的POMDP问题模型，该文提出了一种求解该问题模型的快速近似算法。该算法首先利用QMDP算法产生的策略进行信念空间采样，并通过点迭代算法快速生成POMDP值函数，从而产生近似的最优行动选择策略。在相同的POMDP试验模型上，执行该算法产生的策略得到的回报值与执行其他近似算法产生的策略得到的回报值相当，但该算法计算速度快，它产生的策略表示向量集合小于现有其他近似算法产生的集合。因此，它比这些近似算法更适应于大规模的稀疏状态转移矩阵POMDP模型求解计算。     

口语对话系统的POMDP模型及求解

许多口语对话系统已进入实用阶段，但一直没有很好的对话管理模型，把对话管理看做随机优化问题，用马尔科夫决策过程（MDP）来建模是最近出现的方向，但是对话状态的不确定性使MDP不能很好地反映对话模型，提出了一种新的基于部分可观察MDP（POMDP）的口语对话系统模型，用部分可观察特性来处理不确定问题，由于精确求解算法的局限性，考察了许多启发式近似算法在该模型中的话用性，并改进了部分算法，如对于格点近似算法，提出了两种基于模拟点的格点选择方法。     

基于点的POMDP算法的预处理方法

基于点的算法是部分可观察马尔可夫决策过程(partially observable Markov decision processes,简称POMDP)的一类近似算法.它们只在一个信念点集上进行Backup操作,避免了线性规划并使用了更少的中间变量,从而将计算瓶颈由选择向量转向了生成向量.但这类算法在生成向量时含有大量重复和无意义计算,针对于此,提出了基于点的POMDP算法的预处理方法(preprocessing method for point-based algorithms,简称PPBA).该方法对每个样本信念点作预处理,并且在生成α-向量之前首先计算出该选取哪个动作和哪些α-向量,从而消除了重复计算.PPBA还提出了基向量的概念,利用问题的稀疏性避免了无意义计算.通过在Perseus上的实验,表明PPBA很大地提高了算法的执行速度.     

Aircraft Collision Avoidance Using Monte Carlo Real-Time Belief Space Search

The aircraft collision avoidance problem can be formulated using a decision-theoretic planning framework where the optimal behavior requires balancing the competing objectives of avoiding collision and adhering to a flight plan. Due to noise in the sensor measurements and the stochasticity of intruder state trajectories, a natural representation of the problem is as a partially-observable Markov decision process (POMDP), where the underlying state of the system is Markovian and the observations depend probabilistically on the state. Many algorithms for finding approximate solutions to POMDPs exist in the literature, but they typically require discretization of the state and observation spaces. This paper investigates the introduction of a sample-based representation of state uncertainty to an existing algorithm called Real-Time Belief Space Search (RTBSS), which leverages branch-and-bound pruning to make searching the belief space for the optimal action more efficient. The resulting algorithm, called Monte Carlo Real-Time Belief Space Search (MC-RTBSS), is demonstrated on encounter scenarios in simulation using a beacon-based surveillance system and a probabilistic intruder model derived from recorded radar data.     

Reasoning and predicting POMDP planning complexity via covering numbers

Partially observable Markov decision processes (POMDPs) provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l ₁-metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the l _n-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.