15 end //while 16 end algrithm VI
LOGO
实验结果
设立阈值THRESHOLD为0.0001，算 法经过12轮迭代结束；
LOGO
结果分析
方格中显示对应状态的V值。
LOGO
算法改进
1 algrithm Q - offline learing 2 3 4 5 6 for each s in StateSpacedo for each a in ActionSpac do e Q(s, a) : 0 end ..// inner foreach end // outer foreach
a
一轮迭代后，当各状 态的V值变化量小于 阀值时，我们称此时 找到问题的最优策略；
P
s'
s'|s,a
V(s' )
DeltaOneIteration (VHistory(s) V(s)) 2 end // foreach if ( DeltaOneIteration THRESHOLD) return end //if
回报函数 动作值函数：
Q(s, a) : Ps'|s,a R(s'| s,a) γ max Ps'|s,a Q(s', a' )
s' a' s'
7 while ( true ) 8 9 10 11 12 13 14 15 16 17 18 DeltaOneIteration : 0 for each s in StateSpacedo for each a in ActionSpac do e QHistory(s, a) : Q(s, a) Q(s, a) : Ps'|s,a R(s' | s, a) γ max
19 end //while 20 end algrithm Q - offline learning
LOGO
实验结果
LOGO
实验结果
LOGO
结果分析
ML
LOGO
值函数
值函数：指对于特定策略和某一状态，执行该策 略直到达到吸收状态，所获得的累计回报的期望。
V(s) 值函数为： : R(s) γ max Ps'|s,a V(s' ) a
s'
其中γ为折扣因子，其目标是让期望值有界．
LOGO
问题陈述
(1)状态空间 S：小机器人有11个活动状态，编号 0~10； (2)动作空间 A：{ N, E, S, W }，小机器人有北， 东，南，西四个可选动作。 (3)状态转移概率模型 { P }：每个动作以0.8的概 率到达动作期望状态，分别以0.1的概率到达动作 的两个侧向状态。 (4)状态转移回报模型R：R((10)) = +1.0， R((9)) = -1.0，R(其他状态) = -0.02。 (5)γ=0.99 (6)定义状态10和9为吸收状态，第一次到达吸收 状态时，获得对应吸收状态回报；
鲁庆，基于栅格法的移动机器人路径规划研究， 电脑与信息Fra bibliotek术，2007年
LOGO
问题背景描述
利用栅格法对空间划分，搜索一条从起始栅格到 终点栅格的路径，构成机器人运动的可行路径。
目标、 吸收状态 禁止、 吸收状态 障碍 物 实验内容： 基于值迭代的MDP 算法，找出从某状 态到达目标状态时， 使状态值函数达到 最大值的最优策略。
LOGO
问题陈述
目标、 吸收状态 禁止、 吸收状态
例如P(6)|(5),N = 0.8，P(8)|(5),N = 0.1,P(3)|(5),N = 0.1， P（其他状态）|(5),N = 0.0。
LOGO
算法设计
0 algrithm Value Iteratin 1 for each s in StateSpacedo 2 V(s) : 0 3 end // foreach 4 initialize V[9] : 1.0，V[10] : 1.0 5 while ( true ) 6 7 8 9 10 11 12 13 14 DeltaOneIteration : 0 for each s except state9 and 10 in StateSpacedo VHistory(s) : V(s) V(s) : R(s) γ max
LOGO
马尔可夫决策过程(MDP)
基本的MDP模型是一个四元组：< S, A, { P } ,R >。 例如P(s’|s,a)，显然 0≤P(s’|s,a)≤1，并且 P(s'| s,a) 1 s'S 策略 Π：指决策者对于特定状态，应选择的动作。 MDP决策的策略是将状态映射到动作，同时满足 使Agent选择的动作能够获得环境报酬的累计值最 大。
s' a'
P
s'
s'|s,a
Q(s' , a' )
DeltaOneIteration (QHistory(s, a) Q(s, a)) 2 end // inner foreach end // outer foreach if ( DeltaOneIteration THRESHOLD) return end //if
ML
基于值迭代的MDP算法求解最优 策略
姓名：陈丽 学号：E13301110
LOGO
参考文献
石轲，基于马尔可夫决策过程理论的Agent决策问 题研究，中国科学技术大学，2010 孙湧，仵博， 冯延蓬，基于策略迭代和值迭代的 POMDP算法，计算机 研究与发展，2008年
刘克，实用马尔可夫决策过程[M] ．北 京 ：清华 大学出版社 ，2004