一种基于最优策略概率分布的POMDP值迭代算法

刘　峰,王崇骏,骆　斌

(1.南京大学软件学院,江苏南京 210093;2.南京大学计算机科学与技术系,江苏南京 210093;3.南京大学软件新技术国家重点实验室,江苏南京 210093)



一种基于最优策略概率分布的POMDP值迭代算法

刘峰1,3,王崇骏2,3,骆斌1,3

(1.南京大学软件学院,江苏南京 210093;2.南京大学计算机科学与技术系,江苏南京 210093;3.南京大学软件新技术国家重点实验室,江苏南京 210093)

随着应用中POMDP问题的规模不断扩大,基于最优策略可达区域的启发式方法成为了目前的研究热点.然而目前已有的算法虽然保证了全局最优,但选择最优动作还不够精确,影响了算法的效率.本文提出一种基于最优策略概率的值迭代方法PBVIOP.该方法在深度优先的启发式探索中,根据各个动作值函数在其上界和下界之间的分布,用蒙特卡罗法计算动作最优的概率,选择概率最大的动作作为最优探索策略.在4个基准问题上的实验结果表明PBVIOP算法能够收敛到全局最优解,并明显提高了收敛效率.

部分可观测马尔科夫决策过程;基于最优策略概率的值迭代算法;蒙特卡罗法

1　引言

规划问题,即“设计合理的行动计划以达到个体目标”[1],是人工智能研究里的重要领域.序列决策问题(Sequential Decision Making)是规划问题的一个重要子领域.而动态不确定性环境下的行动规划是其中的热点,其动态性和不确定性是在这种环境下进行行动规划的主要难点.

部分可观察马氏决策过程(Partially Observable Markov Decision Process,POMDP)是一个强大的数学框架,可以用来描述并解决很多实……