资源描述：
《马尔可夫决策基础理论.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、马尔可夫决策基础理论内容提要本章介绍与研究背景相关的几类决策模型及算法。模型部分，首先是最基本的马尔可夫决策模型，然后是在此基础上加入观察不确定性的部分可观察马尔可夫决策模型，以及进一步加入多智能体的分布式部分可观察马尔可夫决策模型和部分可观察的随机博弈模型。算法部分，针对上述几类模型，我们均按照后向迭代和前向搜索两大类进行对比分析。最后，我们介绍了半马尔可夫决策模型及Option理论，这一理论为我们后面设计分等级的大规模多智能体系统的决策模型及规划框架提供了重要基础。2.1MDP基本模型及概念马尔可夫决策过程适用的系统有三大特点：一是状态转移的无后效性；二是状态转移可以有不确定性；三是智能体
2、所处的每步状态完全可以观察。下面我们将介绍MDP基本数学模型，并对模型本身的一些概念，及在MDP模型下进行问题求解所引入的相关概念做进一步解释。2.1.1基本模型马尔科夫决策过程最基本的模型是一个四元组S,A,T,R(PutermanM,1994)：♦状态集合S：问题所有可能世界状态的集合；♦行动集合A：问题所有可能行动的集合；♦状态转移函数T:S×A×S’→[0,1]:用T(s,a,s’)来表示在状态s，执行动作a，而转移到状态s’的概率Pssa('
3、,)；♦报酬函数R:S×A→R:我们一般用R(s,a)来表示在状态s执行动作a所能得到的立即报酬。虽然有针对连续参数情况的MDP模型及算法，然
4、而本文在没有特殊说明的情况都只讨论离散参数的情况，如时间，状态及行动的参数。图2.1描述的是在MDP模型下，智能体(Agent)与问题对应的环境交互的过程。智能体执行行动，获知环境所处的新的当前状态，同时获得此次行动的立即收益。环境当前状态行动立即收益智能体图0.1MDP的基本模型2.1.2状态状态是对于在某一时间点对该世界（系统）的描述。最一般化的便是平铺式表示[]，即对世界所有可能状态予以标号，以s1,s2,s3,…这样的方式表示。这种情况下，标号状态的数目也就代表了状态空间的大小。而一种更加自然的方式是因子化表示，因子化是一种面向对象的思想，这种状态表示方式我们会在结合Robocup的高
5、层设计章节详细讨论。不同的应用中，人们对状态的具体定义是不一样的，但一般来说，在MDP中定义的状态必须包括所有当前世界中Agent能够掌握利用，会对Agent决策产生影响的信息，这也可做为建模过程中，某些因素要不要加入问题状态表示的依据。事实上，这些因素，又对应为一些概念，或者说状态变量。要不要将这些变量加入问题的状态表示中，再或者要不要对概念对应的状态量进行某种拆分或合并，这些问题在建模时都是需要考虑的。处理的不好，便可能引入大量冗余信息。目前，也有专门针对这些问题所作的工作，如识别无关状态(JongNK,StoneP,2005)，聚类等等(GivanR,etal,2003;LiLH,eta
6、l,2006)。大多数情况，智能体对自己所处的当前世界的状态不可能有一个完整的认识。因此，我们引入概率的方法来处理这类信息的不确定性。我们引入随机变量ttS，随机变量从状态集合S中取值。变量S并非由未来时刻的状态所决定，而是由过去状态影响，如图2.2所示。012k-2k-1kSSSSSS图0.2马尔可夫链图2.2所表示的是一离散的、随机的动态系统，图中的每个节点表示在某一tt01t−1tt−1时刻的某一状态。对于随机变量S,有Pr(S
7、S,S,...,S)=Pr(S
8、S)，为一条件tt−1概率。它也同时体现了马尔科夫性质，即S只是概率依赖于S。任何两个状态间的关系可以只用两个状态来表示。同时，
9、我们引入吸收状态这一概念，如果对于某一状态s，执行任何行动，过程都以概率1转移到s本身，则该状态s被称为吸收状态(absorbstate)。2.1.3行动Agent的行动会参与改变当前世界的状态。MDP的一个关键部分是提供给Agent的用于做决策的行动集合。当某一行动被执行，世界状态将会发生改变，根据一个已知的概率分布转换为另一状态，这个概率分布也和所执行的动作有关。不加说明的情况下，我们讨论的是时齐马尔可夫过程，即所有行动的执行时间是相同的，状态转移的时间间隔一致。这种行动有时也可以被称为系统的原子动作。在该系统内，行动已对应最小的时间划分，原子动作不可再分割。比如，在一个棋盘类游戏中，每一
10、步所有的走子方式构成了原子动作的集合。再比如，在一个实时的机器人运动控制中，离散的最小时间片内，机器人可以选择以一定的离散的角度转向，或者以一定的离散的加速度进行速度控制，这些也构成了在该系统下的原子动作集合。2.1.4状态转移函数状态转移函数描述了系统的动态特性，我们可以做以下比较：0.5s1s20.20.30.40.60.80.2s6s31.00.50.51.0s5s4图0.3对给定行动的状态
