| POMDPs算法复杂度对比分析研究 |
| |
| 引用本文： | 仵博,郑红燕,冯延蓬.POMDPs算法复杂度对比分析研究[J].深圳职业技术学院学报,2013,12(1):3-10. |
| |
| 作者姓名： | 仵博 郑红燕 冯延蓬 |
| |
| 作者单位： | 深圳职业技术学院教育技术与信息中心,广东深圳,518055 |
| |
| 基金项目： | 广东省自然科学基金资助项目 |
| |
| 摘 要： | 部分可观察马尔可夫决策过程（ Partially Observable Markov Decision Processes, POMDPs ）是动态不确定环境下序贯决策的理想模型，但是现有算法都陷入“维数灾”和“历史灾”问题，造成理想的POMDPs模型无法在实际工程中得到应用．本文首先详细分析了POMDPs精确算法的复杂度，阐述问题求解的难点；然后比较分析现有基于点的离线算法和在线算法两类算法的算法思想和时间复杂度，指出两类算法的优缺点；最后简介POMDPs实际应用情况和未来的研究方向．
|
| 关 键 词： | 部分可观察马尔可夫决策过程 序贯决策 信念状态空间 在线算法 维数灾 |
Algorithm Complexity for POMDPs: A Comparative Study |
| |
| WU Bo
,
ZHENG Hongyan
,
FENG Yanpeng.Algorithm Complexity for POMDPs: A Comparative Study[J].Journal of Shenzhen Polytechnic,2013,12(1):3-10. |
| |
| Authors: | WU Bo ZHENG Hongyan FENG Yanpeng |
| |
| Institution: | (Education Technology and Information Center,Shenzhen Polytechnic,Shenzhen,Guangdong 518055,China) |
| |
| Abstract: | Partially Observable Markov Decision Processes （POMDPs） offers a framework for sequential decision-making under uncertainty in stochastic domains. However, the conventional algorithms are plagued with two curses, dimensionality and history, which makes the ideal POMDPs model inapplicable in practical projects. This paper analyzes the complexity of exact algorithm of POMDPs, and presents the key points in solving this problem. Besides, the ideas and complexity of point-based offiine algorithms and online algorithms were analyzed respectively, and their advantages and disadvantages discussed. Finally, applications of POMDPs and research trends of POMDPs are pointed out. |
| |
| Keywords: | POMDPs sequential decision-making belief states space online algorithms dimensionalitycurses |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
