基于非负矩阵分解更新规则的部分可观察马尔可夫决策过程信念状态空间降维算法

针对求解部分可观察马尔可夫决策过程(POMDP)规划问题时遭遇的"维数诅咒",该文提出了一种基于非负矩阵分解(NMF)更新规则的POMDP信念状态空间降维算法,分两步实现低误差高维降维。第1步,利用POMDP的结构特性,将状态、观察和动作进行可分解表示,然后利用动态贝叶斯网络的条件独立对其转移函数进行分解压缩,并去除概率为零的取值,降低信念状态空间的稀疏性。第2步,采用信念状态空间值直接降维方法,使降维后求出的近似最优策略与原最优策略保持一致,使用NMF更新规则来更新信念状态空间,避免Krylov迭代,加快降维速度。该算法不仅保证降维前后值函数不发生改变,又保留了其分段线性凸特性。实验结果表明,该算法具有较低误差率和较高收敛性。

基于信念状态空间的水声传感器网络MAC协议

为解决由水声传感器网络信道带宽小、传输延迟长等特性引起节点使用信道时出现的时—空不确定性问题,提出一种基于信念状态空间的水声传感器网络MAC协议(BSPMDP-MAC)。该协议将传感器的接收节点时间轴平均划分n个时隙,按照每个节点的链路质量和剩余能量的等级划分传感器发送节点的动作状态信息,接收节点依据信道占用的历史观测和动作信息的联合概率分布,得出传感器发送节点竞争信道使用权的决策策略序列;根据决策策略序列,发送节点在所分配时隙内依次向接收节点发送数据包,根据当前的信念状态和动作,接收节点对信道的占用进行预测,感知下一个周期的信念状态和接入动作。实验仿真结果表明,该协议可以降低数据包冲突率,提高网络吞吐量与数据包传输成功率,从而降低网络的能量开销。

基于动态贝叶斯网络的可分解信念状态空间压缩算法

针对部分可观察马尔可夫决策过程(POMDP)的信念状态空间规模"维数灾"问题,根据信念状态变量存在可分解和独立关系的特性,提出一种基于动态贝叶斯网络(DBN)的可分解信念状态空间压缩算法(factoredbelief states space compression,FBSSC).该算法通过构建变量间依赖关系图,根据独立关系检验去除多余边,将转移函数联合概率分解成若干个条件概率的乘积,实现信念状态空间的无损压缩.对比实验和RoboCupRescue仿真结果表明,本文算法具有较低误差率、较高收敛性和普遍适用性等特性.

一种优化的一致性规划状态变量选择算法

研究了一致性规划任务信念状态空间的表示方法。针对一致性有限域表示(CPT-FDR)算法在任务生成阶段选择状态变量的不足,提出了一种基于初始状态中文字相容互斥的状态变量选择算法——MECV算法。CPT-FDR未考虑初始信念状态中文字的互斥性,产生冗余的编码信息,降低了编码的效率。MECV算法利用有用正负文字构造新的未覆盖事实集,提取初始信念状态中处于不同世界状态的文字组成互斥组,再编码状态变量。实验结果表明该算法能有效地压缩信念状态空间。

POMDPs算法复杂度对比分析研究

部分可观察马尔可夫决策过程(Partially Observable Markov Decision Processes,POMDPs)是动态不确定环境下序贯决策的理想模型,但是现有算法都陷入"维数灾"和"历史灾"问题,造成理想的POMDPs模型无法在实际工程中得到应用.本文首先详细分析了POMDPs精确算法的复杂度,阐述问题求解的难点;然后比较分析现有基于点的离线算法和在线算法两类算法的算法思想和时间复杂度,指出两类算法的优缺点;最后简介POMDPs实际应用情况和未来的研究方向.