MDP表示及解决方法的分析

目录
摘要 3
Abstract 4
1.引言 5
2.MDP的框架与基本表示 6
2.1状态和状态转移 6
2.2事件 7
2.3观察 8
2.4系统状态与观察的历史 9
2.5报酬和函数值 9
2.6范围与值函数定义标准 10
2.7解决标准 11
2.8策略 12
2.9小结 12
3.动态规划算法分析 15
4.因子化描述方法 18
4.1 2TBN 18
4.2 PSO 20
5.状态集合与MDP分解 23
5.1状态抽象与集合 23
5.2可达性分析和连续问题的分解 25
6.结论 27
参考文献： 29

摘要

在不确定条件下做规划是自主式连续决策的一大核心问题。在人工智能的规划、决策分析、OR、控制理论和经济等领域都对此有所研究。虽然这些领域中的假设都有很大不同，其中很多规划问题都可以用马尔可夫过程来建模，用决策论的方法来分析。
近些年来，贝叶斯网推理将计算（或近似计算）在不确定条件下规划的效用值变为可能；马尔可夫方法在诸如自然语言识别之类领域内的成功，以及强化学习技术的成功，推动了运用马尔可夫决策过程的规划工作。尽管决策论规划机制一般而言比与之相应的经典规划有复杂的多的搜索空间，但更快的计算机使建立它变为可能。
本文考察了马尔可夫过程框架的组成和基本表示，然后分析了它的解决算法动态规划和简洁表示方法――因子化表示和状态抽象与集合。

Abstract

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these fields often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory.
The recent advances in Bayesian inference have made it feasible to compute (or approximate) the expected utility of a plan under conditions of uncertainty. The success of Markovian approaches in areas such as speech recognition and the closely-related reinforcement learning techniques have encouraged work in planning using Markov decision processes. Faster computers have made it feasible to build decision-theoretic planners, which in general have more complicated search spaces than their classical counterparts.
In this paper we first investigate the component and representation of the frame of the Markov processes. Then we analyze the solution algorithms – dynamic programming. At last we analyze the compact representations – factored representation and state abstraction and aggregation.

1.引言
人工智能的规划算法就是要找出一个行动序列使得agent能达到目标状态。经典的规划都是在确定的情况下进行的。而当行动结果不确定，或要依据行动的开销来判定一个规划的好坏时，决策论就显示出它的优越性了。它比经典规划更吸引人之处在于他允许对不确定问题建模。
从GPS和STRIPS以来，大多数的AI规划模型都由以下三个假设：
1）规划者的目标是一个用逻辑描述的世界状态；
2）仅有规划者的行为能改变世界的状态；
3）每个行为可以用它的前提条件和结果来描述，这些结果由行为执行后，世界状态事实的增加或删除来描述。
在不确定问题中，行动有不确定的效果，主体掌握着不完整的环境信息，而环境中的不确定因素又使得存在带有不同效用值的解决方法，以致可能不存在绝对的目标状态。
在DTP中，首先，如果我们将行为的结果描述成一个可能结果的集合，而不是一个单一的结果，那么我们就可以描述不确定的行为。
然后，我们放弃上述第一个假设，给每个世界状态加上效用值以描述它的地位或者说倾向性，这样不是所有的规划都是成功的，如果效用值代表了倾向程度的话，我们可以取效用值最大的那个规划。
因此，DTP可看做经典规划地扩展；粗略的说，它的目标与其说是要形式化一个保证能达到某个目标的规划，不如说是要形式化具有效用高期望值的规划。也就是说，决策论可以看做是概率论和效用论的结合，是要在不确定情况下找出最优解。