实用POMDP近似求解算法的研究

摘要

在人工智能领域，动态的、不确定性的序列决策问题是研究Agent与环境交互的策略的核心问题。在实际应用领域，随着系统的复杂化，大量的问题都可抽象为动态的、不确定性的序列决策问题，因而对这些问题的研究具有广泛而深远的意义。POMDP作为求解满足 Markov假设的动态的、不确定性的序列决策问题的一种强大而灵活的框架，成为研究的焦点。
　　本文从实用性角度出发，研究了获得最优POMDP策略的算法。
　　从对实际应用的广泛适用性出发，本文研究了基于实例的算法，包括NNI，LWI和ENNI。此算法结合使用了基于实例学习和增强学习的技术。通过实例学习，可获取Agent的准确的交互数据，由于它对模型没有特殊要求，因此使得最终的算法具有广泛的适用性，不仅可在离散的Markov环境下应用，更可以应用于连续状态的情况和非Markov环境的情况。通过增强学习，不断地搜索策略空间，寻找更优的策略。通过学习获得了与策略相关的数据，然后使用启发式的求解方法来获得优化的策略。实验表明，在没有模型参数的情况下，它可获得优于Q-MDP算法的策略。
　　为了解决POMDP求解算法的复杂性问题，开发高效的求解算法，本文研究了基于核信念的求解算法 KBVI。KBVI通过采样从初始信念状态可达的信念状态获得与具体问题结构相关的信息，基于这些数据通过值迭代求解POMDP来获得最优策略。KBVI把求解POMDP的复杂性降低到多项式级，与其他的基于信念点的算法相比，它可以更高效的获得同等的甚至更优的策略。
　　为了获得求解POMDP的相关数据，使用某种算法求解POMDP和运行某种POMDP策略来对它的性能进行测试，本文开发了一个 Agent运行平台，它由Agent模型和运行环境模型组成。在这个平台上获得了使用基于实例的算法和KBVI算法求解典型的POMDP问题的性能数据，并与其他算法的性能进行了对比，验证了本文算法具有良好的性能。本文也试图通过开发此Agent运行平台来建立POMDP应用的框架和基础组件。

目录

实用POMDP 近似求解算法的研究

RESEARCH ON APPLICABLE APPROXIMATEPOMDP SOLUTION ALGORITHM

摘 要

Abstract

目 录

第1章 绪 论

1.1 研究背景

1.2 POMDP问题研究的发展现状

1.2.1 POMDP问题求解算法的发展

1.3 相关技术的发展现状

1.3.1 基于采样的方法

1.3.2 POMDP模型的因子化表示

1.3.3 POMDP策略的层级表示

1.4 本课题研究的意义及主要研究内容

1.4.1 本课题研究的意义

1.4.2 应用背景

1.4.3 主要研究内容

第2章 POMDP模型描述与求解算法

2.1 MDP模型

2.2 POMDP模型

2.3 本章小结

第3章 基于实例的POMDP问题的近似求解

3.1 引言

3.2 基于实例的方法

3.3启发式算法

3.4增强学习

3.5 基于实例的近似求解算法

3.6 本章小结

第4章 基于核信念的值迭代算法

4.1 引言

4.2 基于信念点的算法

4.3 基于核信念的值迭代算法

4.4 本章小结

第5章 POMDP模型运行平台与算法的性能测试

5.1 POMDP模型运行平台概述

5.2 性能测试的模型

5.3 基于实例的算法的性能分析

5.4 基于核信念的值迭代算法的性能分析

5.5 本章小结

结 论

参考文献

攻读硕士学位期间发表的论文及其它成果

哈尔滨工业大学硕士学位论文原创性声明

致 谢