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

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

基于后验信念聚类的在线规划算法

在连续状态的部分可观察马尔可夫决策过程中,在线规划无法同时满足高实时性与低误差的要求.为此,提出一种基于后验信念聚类的在线规划算法.使用KL散度分析连续状态下后验信念之间的误差,根据误差分析结果对后验信念进行聚类,利用聚类后验信念计算报酬值,并采用分支界限裁剪方法裁剪后验信念与或树.实验结果表明,该算法能够有效降低求解问题的规模,消除重复计算,具有较好的实时性和较低的误差.     

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

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

基于杂合标准的POMDP值迭代求解算法*

基于点的值迭代方法是求解部分可观测马尔科夫决策过程(POMDP)问题的一类有效算法.目前基于点的值迭代算法大都基于单一启发式标准探索信念点集,从而限制算法效果.基于此种情况,文中提出基于杂合标准探索信念点集的值迭代算法(HHVI),可以同时维持值函数的上界和下界.在扩展探索点集时,选取值函数上下界差值大于阈值的信念点进行扩展,并且在值函数上下界差值大于阈值的后继信念点中选择与已探索点集距离最远的信念点进行探索,保证探索点集尽量有效分布于可达信念空间内.在4个基准问题上的实验表明,HHVI能保证收敛效率,并能收敛到更好的全局最优解.     

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

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

优化初始边集提高分支裁剪法求解TSP效率

概要地叙述了NP完全问题的复杂性,并简述了分支裁剪法求解NP问题最优解的策略.以求解欧氏空间的TSP问题为例,分析了利用分支裁剪法求解问题中主要影响算法求解效率的原因在于初始边集中存在大量无用信息,针对该类问题,提出了通过化简初始边集提高算法求解效率的策略,实验验证了这种方法的有效性.     

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算法很大程度地提高了基于试探的算法计算信念状态轨迹的效率.     

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近似算法

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

功能树的EFVM求解算法

为了解决与或非功能树求解中经常出现的方案数量巨大的问题,提出一种基于四值矩阵(FVM)的功能树求解算法.从与或非功能树的特点出发构造了四值矩阵、扩展四值矩阵(EFVM)和FVM系统;分析了FVM系统与经典命题逻辑中范式系统的同构关系及FVM的扩展与展开,给出EFVM直接求解算法;在考虑约简的基础上,提出EFVM约简求解算法.实例结果说明:EFVM约简求解算法在冗余较多的情况下可有效降低解的规模,有力地推动了产品概念设计.