基于值迭代MDP算法求解最优策略

1、 ML基于值迭代的基于值迭代的MDP算法求解最优算法求解最优策略策略姓名：陈丽 学号：E13301110LOGO参考文献v 石轲，基于马尔可夫决策过程理论的Agent决策问题研究，中国科学技术大学，2010v 孙湧，仵博， 冯延蓬，基于策略迭代和值迭代的POMDP算法，计算机 研究与发展，2008年v 刘克，实用马尔可夫决策过程M 北 京 ：清华大学出版社 ，2004 v 鲁庆，基于栅格法的移动机器人路径规划研究，电脑与信息技术，2007年LOGO问题背景描述v 利用栅格法对空间划分，搜索一条从起始栅格到终点栅格的路径，构成机器人运动的可行路径。目标、吸收状态障碍物禁止、吸收状态实验内容：基于

2、值迭代的MDP算法，找出从某状态到达目标状态时，使状态值函数达到最大值的最优策略。LOGO马尔可夫决策过程(MDP)v 基本的MDP模型是一个四元组：。v 例如P(s|s,a)，显然 0P(s|s,a)1，并且v 策略 ：指决策者对于特定状态，应选择的动作。v MDP决策的策略是将状态映射到动作，同时满足使Agent选择的动作能够获得环境报酬的累计值最大。1a)s,|P(sSsLOGO值函数v 值函数：指对于特定策略和某一状态，执行该策略直到达到吸收状态，所获得的累计回报的期望。v 值函数为：v 其中为折扣因子，其目标是让期望值有界 )V(sP R(s) :V(s)sas, | samaxLO

3、GO问题陈述v (1)状态空间 S：小机器人有11个活动状态，编号010；v (2)动作空间 A： N, E, S, W ，小机器人有北，东，南，西四个可选动作。v (3)状态转移概率模型 P ：每个动作以0.8的概率到达动作期望状态，分别以0.1的概率到达动作的两个侧向状态。v (4)状态转移回报模型R：R(10) = +1.0， R(9) = -1.0，R(其他状态) = -0.02。v (5)=0.99v (6)定义状态10和9为吸收状态，第一次到达吸收状态时，获得对应吸收状态回报；LOGO问题陈述v 例如P(6)|(5),N = 0.8，P(8)|(5),N = 0.1,P(3)|(5

4、),N = 0.1， P（其他状态）|(5),N = 0.0。目标、吸收状态禁止、吸收状态LOGO算法设计VI algrithm end 16 /whileend 15 /ifend 14return 13THRESHOLD) eration DeltaOneIt ( if 12foreach / end 11V(s)s)(VHistory(eration DeltaOneIt 10)V(sP R(s) :V(s) 9V(s): )VHistory(s 8do StateSpacein 10 and 9 stateexcept seach for 70 :eration DeltaOneIt

5、6) true( while51.0:V100 . 1: V9 initialize 4foreach / end 30 : V(s) 2do StateSpacein seach for 1Iteratin Value algrithm 02sas,| samax，一轮迭代后，当各状态的V值变化量小于阀值时，我们称此时找到问题的最优策略；LOGO实验结果v设立阈值THRESHOLD为0.0001，算法经过12轮迭代结束；LOGO结果分析v 方格中显示对应状态的V值。LOGO算法改进learning offline-Q algrithm end 20 /whileend 19 /ifend 1

6、8return 17THRESHOLD) eration DeltaOneIt ( if 16foreachouter / end 15foreachinner / end 14a)Q(s,a)s,(QHistory(eration DeltaOneIt 13)a,Q(sP a)s,|R(sP :a)Q(s, 12a)Q(s,: a),QHistory(s 11do eActionSpacin aeach for 10do StateSpacein seach for 90 :eration DeltaOneIt 8) true( while7foreachouter / end 6foreachinner ./ end 50 : a)Q(s, 4do eActionSpacin aeach for 3do StateSpacein seach for 2learing offline-Q algrithm 12sas,| sasas,