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

基于环境状态分布优化的POMDP值迭代求解算法

基于点的值迭代算法是一类解决POMDP问题的有效算法,PBVI是基于点集的经典算法,但是其算法效率较为低下。FSVI使用内在的MDP最优策略来降低算法复杂度,但求解大规模问题的效果较差。为解决上述问题,提出了基于环境状态分布优化的前向搜索值迭代算法（PBVI-OSD）,通过基于权重值的Q^MDP选出最佳的动作,基于信念状态和转换函数选取最大可能的状态,基于动作和状态从观察中随机选取一个观察概率大于阈值的观察,由此获得更具探索价值的后继信念点集,提升值迭代收敛的质量。在四个基准问题上的实验表明,相比于FSVI和PBVI,PBVI-OSD能保证收敛效率,特别是在大规模问题上能收敛到更好的全局最优解。     

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

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

基于采样的POMDP近似算法

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

基于信念点裁剪策略树的POMDP求解算法

针对大规模部分可观察马尔可夫决策过程(POMDP)算法中策略树规模指数级增长、已证信念点(witness point,WP)求解困难的问题,根据策略树值函数是分段线性凸函数的特点,提出一种基于信念点的策略树增量裁剪和值迭代求解算法.在策略树生成过程中,利用边界点进行无损裁剪,利用中间点进行有损裁剪,并利用实时信念状态分布求取近似最优解.对比实验结果表明,该算法能快速收敛,以更少的时间获得相当精度的奖赏值.     

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

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

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

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

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

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

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

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

一种基于独立任务的POMDP问题的解决方法*

部分可观测马尔可夫决策过程(POMDP)是马尔可夫决策过程(MDP)的扩展。通常利用POMDPs来模拟在部分可观测的随机环境中决策的Agents。针对完整POMDP的求解方法扩展能力弱的问题,提出把一个多元的POMDP分解成一组受限制的POMDPs,然后分别独立地求解每个这样的模型,获得一个值函数并将这些受限制的POMDPs的值函数结合起来以便获得一个完整POMDP的策略。该方法主要阐述了识别与独立任务相关的状态变量的过程,以及如何构造一个被限制在一个单独任务上的模型。将该方法应用到两个不同规模的岩石采样问题中,实验结果表明,该方法能够获得很好的策略。     

顺序价值迭代算法求解不确定规划

基于Markov决策过程(MDP)的规划方法可以处理多种不确定规划问题,价值迭代算法(VI)是求解MDP的经典算法,但VI需要计算更新每个状态的值,求解过程相当缓慢。在分析了MDP状态图本身的因果依赖关系的基础上,提出一种改进的价值迭代算法,称为顺序价值迭代算法(SVI)。它先将一个MDP分解成多个拓扑有序的强连通分量,然后应用价值迭代算法顺序求解各个分量,这样处理可以避免对大量无用状态的计算并使得可用状态排成拓扑序列。对比实验结果证明了该算法的有效性及优异性能。     

基于FPOMDP的无线传感器网络动态调度算法

针对无线传感器网络节点能量有限、数据采集易受环境影响的问题,提出一种基于可分解部分可观察Markov决策过程FPOMDP( Factored Partially Observable Markov Decision Process )的节点休眠调度算法.通过节点空时相关模型求取休眠节点数据,利用网络数据准确性和节点能量间的条件独立关系,构造状态转移函数、观察函数和奖赏函数,采用值迭代求解算法求取最优策略,实现节点动态调度.仿真结果表明,该算法能够在保证数据准确性的前提下,有效降低节点能量消耗,延长网络生存时间.     

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

求解POMDP的动态合并激励学习算法

把POMDP作为激励学习（Reinforcement Leaming）问题的模型,对于具有大状态空间问题的求解有比较好的适应性和有效性。但由于其求解的难度远远地超过了一般的Markov决策过程（MDP）的求解,因此还有许多问题有待解决。该文基于这样的背景,在给定一些特殊的约束条件下提出的一种求解POMDP的方法,即求解POMDP的动态合并激励学习算法。该方法利用区域的概念,在环境状态空间上建立一个区域系统,Agent在区域系统的每个区域上独自并行地实现其最优目标,加快了运算速度。然后把各组成部分的最优值函数按一定的方式整合,最后得出POMDP的最优解。     

杂合启发式在线POMDP 规划

许多不确定环境下的自主机器人规划任务都可以用部分可观察的马氏决策过程(partially observableMarkov decision process,简称POMDP)建模.尽管研究者们在近似求解技术的设计方面已经取得了显著的进展,开发高效的POMDP 规划算法依然是一个具有挑战性的问题.以前的研究结果表明:在线规划方法能够高效地处理大规模的POMDP 问题,因而是一类具有研究前景的近似求解方法.这归因于它们采取的是“按需”作决策而不是预前对整个状态空间作决策的方式.旨在通过设计一个新颖的杂合启发式函数来进一步加速POMDP 在线规划过程,该函数能够充分利用现有算法里一些被忽略掉的启发式信息.实现了一个新的杂合启发式在线规划(hybrid heuristiconline planning,简称HHOP)算法.在一组POMDP 基准问题上,HHOP 有明显优于现有在线启发式搜索算法的实验性能.     

无线传感器网络目标跟踪动态簇成员调度策略

通过分析目标跟踪无线传感器网络监测精度、节点能量消耗与簇成员唤醒/休眠之间的内在联系,针对网络节点能量有限、密集部署节点监测数据存在冗余、传感器节点的自身位置估计误差和目标监测估计误差等问题,引入部分可观察Markov决策过程(POMDP)理论,提出一种基于目标跟踪准确度和节点能量消耗加权回报率的动态簇成员调度模型;针对动态簇成员调度算法复杂度偏高的问题,采用基于信念点的值迭代在线策略求解算法,实现传感器簇成员节点协作策略的动态生成和在线调整。仿真结果表明:该算法能够提高目标跟踪准确性,降低节点能量消耗,延长网络生存时间。     

输出图的全部Hamiltonian回路的新算法

为求出图的全部哈密顿回路,本文提出了H集合、连接积、H矩阵和通路矩阵等概念。给出了基于这些概念下的一些哈密顿回路的存在性判定定理和通过构造通路矩阵序列Mk=Mk-1*M(k=2,...,n)的办法输出简单图（无向或有向）的全部哈密顿回路的算法和实例。本算法特别适合寻找图的最短哈密顿回路,较其它算法更为简单直观。     

基于微重启和部分客观马尔可夫决策模型的智能水下机器人软件自修复方法

针对智能水下机器人(AUV)软件故障修复过程中存在的修复代价过高和系统环境只有部分可观察的问题,提出了一种基于微重启技术和部分客观马尔可夫决策(POMDP)模型的AUV软件故障修复方法。该方法结合AUV软件系统分层结构特点,构建了基于微重启的三层重启结构,便于细粒度的自修复微重启策略的实施;并依据部分可观马尔可夫决策过程理论,给出AUV软件自修复POMDP模型,同时采用基于点的值迭代(PBVI)算法求解生成修复策略,以最小化累积修复代价为目标,使系统在部分可观环境下能够以较低的修复代价执行修复动作。仿真实验结果表明,基于微重启技术和POMDP模型的AUV软件故障修复方法能够解决由软件老化及系统调用引起的AUV软件故障,同与两层微重启策略和三层微重启固定策略相比,该方法在累积故障修复时间和运行稳定性上明显更优。     

复合凸优化问题的一个非精确多层梯度镜面下降算法

本文提出一个求解复合凸优化问题的非精确多层梯度镜面下降算法.该算法允许目标函数中光滑部分梯度计算和非光滑部分邻近算子计算都存在误差,在适当条件下分析了该算法函数值误差序列的O(1/k²)收敛速度,这里k表示迭代次数.最后关于Lasso问题和Logistic问题的数值结果表明该算法是有效的.     

部分可观环境中AUV软件自修复模型研究

针对AUV软件在部分可观环境中的故障修复问题,依据部分可观马尔科夫决策过程理论,提出基于POMDP模型和微重启技术的AUV软件故障修复方法。根据AUV 分层结构特点设计了多层次的微重启修复方法,构建了AUV软件自修复POMDP模型,同时采用基于点的值迭代算法求解生成修复策略使系统在部分可观环境下能够以较低的修复代价执行修复动作。仿真实验验证了算法有效性和模型适用性。