1、 ML基于值迭代的基于值迭代的MDP算法求解最優(yōu)算法求解最優(yōu)策略策略姓名：陳麗 學(xué)號(hào)：E13301110LOGO參考文獻(xiàn)v 石軻，基于馬爾可夫決策過程理論的Agent決策問題研究，中國科學(xué)技術(shù)大學(xué)，2010v 孫湧，仵博， 馮延蓬，基于策略迭代和值迭代的POMDP算法，計(jì)算機(jī) 研究與發(fā)展，2008年v 劉克，實(shí)用馬爾可夫決策過程M 北 京 ：清華大學(xué)出版社 ，2004 v 魯慶，基于柵格法的移動(dòng)機(jī)器人路徑規(guī)劃研究，電腦與信息技術(shù)，2007年LOGO問題背景描述v 利用柵格法對(duì)空間劃分，搜索一條從起始柵格到終點(diǎn)柵格的路徑，構(gòu)成機(jī)器人運(yùn)動(dòng)的可行路徑。目標(biāo)、吸收狀態(tài)障礙物禁止、吸收狀態(tài)實(shí)驗(yàn)內(nèi)容：基于

2、值迭代的MDP算法，找出從某狀態(tài)到達(dá)目標(biāo)狀態(tài)時(shí)，使?fàn)顟B(tài)值函數(shù)達(dá)到最大值的最優(yōu)策略。LOGO馬爾可夫決策過程(MDP)v 基本的MDP模型是一個(gè)四元組：。v 例如P(s|s,a)，顯然 0P(s|s,a)1，并且v 策略 ：指決策者對(duì)于特定狀態(tài)，應(yīng)選擇的動(dòng)作。v MDP決策的策略是將狀態(tài)映射到動(dòng)作，同時(shí)滿足使Agent選擇的動(dòng)作能夠獲得環(huán)境報(bào)酬的累計(jì)值最大。1a)s,|P(sSsLOGO值函數(shù)v 值函數(shù)：指對(duì)于特定策略和某一狀態(tài)，執(zhí)行該策略直到達(dá)到吸收狀態(tài)，所獲得的累計(jì)回報(bào)的期望。v 值函數(shù)為：v 其中為折扣因子，其目標(biāo)是讓期望值有界 )V(sP R(s) :V(s)sas, | samaxLO

3、GO問題陳述v (1)狀態(tài)空間 S：小機(jī)器人有11個(gè)活動(dòng)狀態(tài)，編號(hào)010；v (2)動(dòng)作空間 A： N, E, S, W ，小機(jī)器人有北，東，南，西四個(gè)可選動(dòng)作。v (3)狀態(tài)轉(zhuǎn)移概率模型 P ：每個(gè)動(dòng)作以0.8的概率到達(dá)動(dòng)作期望狀態(tài)，分別以0.1的概率到達(dá)動(dòng)作的兩個(gè)側(cè)向狀態(tài)。v (4)狀態(tài)轉(zhuǎn)移回報(bào)模型R：R(10) = +1.0， R(9) = -1.0，R(其他狀態(tài)) = -0.02。v (5)=0.99v (6)定義狀態(tài)10和9為吸收狀態(tài)，第一次到達(dá)吸收狀態(tài)時(shí)，獲得對(duì)應(yīng)吸收狀態(tài)回報(bào)；LOGO問題陳述v 例如P(6)|(5),N = 0.8，P(8)|(5),N = 0.1,P(3)|(5

4、),N = 0.1， P（其他狀態(tài)）|(5),N = 0.0。目標(biāo)、吸收狀態(tài)禁止、吸收狀態(tài)LOGO算法設(shè)計(jì)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，一輪迭代后，當(dāng)各狀態(tài)的V值變化量小于閥值時(shí)，我們稱此時(shí)找到問題的最優(yōu)策略；LOGO實(shí)驗(yàn)結(jié)果v設(shè)立閾值THRESHOLD為0.0001，算法經(jīng)過12輪迭代結(jié)束；LOGO結(jié)果分析v 方格中顯示對(duì)應(yīng)狀態(tài)的V值。LOGO算法改進(jìn)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,