本文關(guān)鍵詞：基于部分可觀察馬爾科夫決策過程的序列規(guī)劃問題的研究

  更多相關(guān)文章： 部分可觀測馬爾科夫決策過程 基于點的值迭代 策略迭代 啟發(fā)式在線算法 蒙特卡羅法

【摘要】：智能規(guī)劃(AI planning)是傳統(tǒng)人工智能最重要的研究領(lǐng)域之一。隨著問題規(guī)模不斷增大,復(fù)雜程度不斷提高,如何在大規(guī)模不確定環(huán)境下設(shè)計出高效智能的決策算法是當(dāng)前智能規(guī)劃非常重要的研究課題。由于POMDP能夠很好地對環(huán)境、動作及觀察的不確定性進(jìn)行建模,因而在不確定性環(huán)境下基于POMDP模型來進(jìn)行規(guī)劃是目前自動規(guī)劃研究的重要內(nèi)容。而在無限視野下精確求解POMDP問題是NP難問題,在過去的十多年里,基于點的POMDP問題啟發(fā)式求解成為了大規(guī)模POMDP問題求解的研究熱點。但是在離線求解POMDP問題的研究中,大多數(shù)基于點的近似求解方法都是基于單一的啟發(fā)式標(biāo)準(zhǔn),難以適用于不同的問題場景；在在線求解POMDP問題的研究中,且近幾年的啟發(fā)式方法都是只以最優(yōu)上界作為探索標(biāo)準(zhǔn),降低了收斂效率。本文圍繞如何設(shè)計高效的啟發(fā)式POMDP求解算法來展開研究。本文的研究內(nèi)容主要有三個方面,首先,研究了目前主流的基于點的POMDP近似求解啟發(fā)式標(biāo)準(zhǔn),雜合密度分布的標(biāo)準(zhǔn)和值函數(shù)的標(biāo)準(zhǔn)設(shè)計HHVI算法來提高探索信念點集的質(zhì)量；其次,研究了基于聚類構(gòu)造可達(dá)信念點集最小覆蓋的方法,并設(shè)計了基于點的策略迭代算法來求解POMDP司題；最后改進(jìn)了最優(yōu)可達(dá)信念空間的探索標(biāo)準(zhǔn),設(shè)計了基于概率的最優(yōu)可達(dá)空間近似方法,從而改進(jìn)了POMDP在線求解的效率。具體來說,論文的主要內(nèi)容和創(chuàng)新點如下：1. 目前基于點的POMDP離線近似求解啟發(fā)式標(biāo)準(zhǔn)主要是基于密度分布的標(biāo)準(zhǔn)、基于值函數(shù)的標(biāo)準(zhǔn)和基于MDP的標(biāo)準(zhǔn)。但是基于MDP的近似解法沒有考慮部分可觀察性,會退化為隨機策略；單一基于密度標(biāo)準(zhǔn)的算法無法控制探索點集的規(guī)模難以保證收斂質(zhì)量；單一基于值函數(shù)的算法復(fù)雜度較高難以保證收斂效率。本文提出了雜合的啟發(fā)式值迭代算法來離線求解POMDP問題,該算法基于值函數(shù)啟發(fā)式標(biāo)準(zhǔn)評價已探索點集內(nèi)信念點的被擴價值,結(jié)合信念點分布和值函數(shù)選擇合理的后繼點,通過雜合值函數(shù)和密度的標(biāo)準(zhǔn)避免了單一標(biāo)準(zhǔn)的局限性,增強了對不同POMDP問題的適應(yīng)性。2.最近的研究說明δ-覆蓋數(shù)是刻畫基于點的POMDP問題求解的有效度量,但精確計算可達(dá)信念空間的δ-覆蓋數(shù)是一個NP-難的問題。本文分析了可達(dá)信念空間的聚類特性,基于可達(dá)信念空間的分布特征來高效地構(gòu)造其δ-覆蓋,由此獲得分散分布于可達(dá)信念空間的探索信念點集,通過策略迭代來離線求解POMDP問題。3. 當(dāng)前的啟發(fā)式在線算法大多基于最高上界的行動分支搜索探索信念點,從理論上保證算法最終能找到信念點上的最優(yōu)行動,但上界的收斂較慢,且下界能夠保證策略的質(zhì)量,在線規(guī)劃算法在執(zhí)行時以最優(yōu)下界對應(yīng)的行動作為決策行動。本文提出了選擇最優(yōu)動作的新標(biāo)準(zhǔn),以所有動作的函數(shù)值在其上界和下界之間的概率分布為基礎(chǔ),計算每個動作的值函數(shù)取值最大的概率,再選擇概率值最大的動作。算法更準(zhǔn)確地探索到最優(yōu)可達(dá)信念空間附近的區(qū)域,從而提高在線求解的迭代效率。
【關(guān)鍵詞】：部分可觀測馬爾科夫決策過程 基于點的值迭代 策略迭代 啟發(fā)式在線算法 蒙特卡羅法
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O225
【目錄】：

• 摘要4-6
• abstract6-15
• 第一章 緒論15-21
• 1.1 引言15-16
• 1.2 POMDP問題求解研究現(xiàn)狀16-18
• 1.3 目前POMDP求解中存在的問題18-19
• 1.4 本文的主要工作和論文結(jié)構(gòu)19-21
• 第二章 研究背景21-36
• 2.1 規(guī)劃問題研究的發(fā)展21-25
• 2.1.1 經(jīng)典規(guī)劃21-24
• 2.1.2 不確定環(huán)境中的規(guī)劃24-25
• 2.2 MDP模型及其求解25-30
• 2.2.1 模型定義26-27
• 2.2.2 策略27-28
• 2.2.3 值函數(shù)和值迭代28-30
• 2.3 POMDP模型及其求解30-35
• 2.3.1 模型定義31
• 2.3.2 決策和信念31-32
• 2.3.3 值向量和精確值迭代32-34
• 2.3.4 向量裁剪34-35
• 2.4 本章小結(jié)35-36
• 第三章 一種基于雜合標(biāo)準(zhǔn)的POMDP值迭代求解方法36-61
• 3.1 引言36-37
• 3.2 基于點的值迭代方法37-38
• 3.3 主流基于點的信念空間探索方法38-47
• 3.3.1 PBVI算法(基于點的值迭代算法)38-39
• 3.3.2 PEMA算法(基于點的最小誤差算法)39-40
• 3.3.3 類MDP的近似解法40-42
• 3.3.4 FSVI算法42
• 3.3.5 HSVI算法42-43
• 3.3.6 SARSOP算法(最優(yōu)策略可達(dá)空間的連續(xù)近似法)43-45
• 3.3.7 GapMin算法45-46
• 3.3.8 基于點的值迭代算法的分析46-47
• 3.4 HHVI算法47-51
• 3.4.1 算法思想47-48
• 3.4.2 算法描述48-50
• 3.4.3 算法分析50-51
• 3.5 實驗和分析51-59
• 3.5.1 基準(zhǔn)問題51-57
• 3.5.2 實驗57-59
• 3.6 本章小結(jié)59-61
• 第四章 一種基于聚類的POMDP策略迭代求解方法61-78
• 4.1 引言61-62
• 4.2 基于點的策略迭代62-66
• 4.2.1 POMDP的策略迭代求解62-64
• 4.2.2 基于點的策略迭代算法PBPI64-66
• 4.3 可達(dá)信念空間聚類特性的分析66-72
• 4.3.1 可達(dá)信念空間獲取方法66-68
• 4.3.2 可達(dá)信念空間聚類分析68-70
• 4.3.3 基于密度的信念點聚類算法70-72
• 4.4 CBPI算法72-75
• 4.4.1 算法思想72-73
• 4.4.2 算法描述73-75
• 4.5 實驗和分析75-77
• 4.6 本章小結(jié)77-78
• 第五章 一種基于概率最優(yōu)可達(dá)空間迭代的POMDP在線求解方法78-93
• 5.1 引言78-80
• 5.2 在線規(guī)劃算法概述80-83
• 5.3 最優(yōu)可達(dá)信念空間的求解方法83-85
• 5.3.1 最優(yōu)可達(dá)信念空間83-84
• 5.3.2 基于概率的最優(yōu)可達(dá)空間近似方法84-85
• 5.4 PBORSI算法85-88
• 5.4.1 算法思想85-86
• 5.4.2 算法描述86-88
• 5.5 實驗和分析88-92
• 5.6 本章小結(jié)92-93
• 第六章 總結(jié)與展望93-95
• 6.1 論文總結(jié)93-94
• 6.2 下一步的工作94-95
• 致謝95-96
• 參考文獻(xiàn)96-104
• 附錄104-105

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 周傲英,周水庚,曹晶,范曄,胡運發(fā);Approaches for Scaling DBSCAN Algorithm to Large Spatial Databases[J];Journal of Computer Science and Technology;2000年06期

2 章宗長;陳小平;;雜合啟發(fā)式在線POMDP規(guī)劃[J];軟件學(xué)報;2013年07期

，

本文編號：989185