本文關(guān)鍵詞：不確定規(guī)劃中帶權(quán)值的強(qiáng)規(guī)劃算法研究

  更多相關(guān)文章： 不確定規(guī)劃 多agent規(guī)劃 模型檢測(cè) 強(qiáng)規(guī)劃

【摘要】：基于模型檢測(cè)的方法因其能夠解決很多現(xiàn)實(shí)世界中的不確定規(guī)劃問(wèn)題,已成為研究不確定規(guī)劃的主要方法之一。當(dāng)使用基于模型檢測(cè)的方法來(lái)對(duì)不確定規(guī)劃問(wèn)題進(jìn)行求解時(shí),可以得到三種不同類型的解:弱規(guī)劃解、強(qiáng)循環(huán)規(guī)劃解、強(qiáng)規(guī)劃解;其中,執(zhí)行強(qiáng)規(guī)劃解能夠確保不確定轉(zhuǎn)移系統(tǒng)在有限的步長(zhǎng)內(nèi)從初始狀態(tài)到達(dá)目標(biāo)狀態(tài),在一些要求絕對(duì)滿足安全的規(guī)劃中,強(qiáng)規(guī)劃解是唯一滿足要求的解,而在實(shí)際應(yīng)用中,執(zhí)行規(guī)劃動(dòng)作需要耗費(fèi)一定的時(shí)間、金錢(qián)等,這些代價(jià)可以用動(dòng)作權(quán)值來(lái)表示,所以研究動(dòng)作權(quán)值之和最小的強(qiáng)規(guī)劃解是很有意義的。本文主要研究了完全可觀察條件下單agent帶權(quán)值的不確定規(guī)劃問(wèn)題和完全可觀察條件下多agent帶權(quán)值的不確定規(guī)劃問(wèn)題。針對(duì)完全可觀察下單agent帶權(quán)值的不確定規(guī)劃問(wèn)題,目前已有對(duì)最小權(quán)值強(qiáng)規(guī)劃解的研究,但算法的效率欠佳,有必要繼續(xù)研究新的方法,進(jìn)一步提高求解的效率。本文通過(guò)引入基于模型檢測(cè)的強(qiáng)規(guī)劃分層法,對(duì)系統(tǒng)進(jìn)行分層,然后利用得到的分層信息,能夠快速排除那些無(wú)強(qiáng)規(guī)劃解的情況;當(dāng)存在強(qiáng)規(guī)劃解時(shí),設(shè)計(jì)了一種利用分層信息反向搜索最小權(quán)值的算法,該算法通過(guò)動(dòng)態(tài)確定搜索上界和搜索下界的策略,避免了許多無(wú)用的搜索。通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可知,本文的算法能夠較快的求出最小權(quán)值強(qiáng)規(guī)劃解,且效率高于已有的直接搜索的算法。目前,對(duì)不確定規(guī)劃問(wèn)題的研究主要是針對(duì)單agent的,而對(duì)于多agent的研究則側(cè)重于確定規(guī)劃。針對(duì)這一現(xiàn)狀,本文首次提出了完全可觀察下多agent帶權(quán)值的不確定規(guī)劃問(wèn)題,并設(shè)計(jì)了使所求解的強(qiáng)規(guī)劃解所需的動(dòng)作權(quán)值總和近似最小的算法SPSMNPW。在算法SPSMNPW中,先利用基于模型檢測(cè)的強(qiáng)規(guī)劃分層方法對(duì)每個(gè)agent進(jìn)行強(qiáng)規(guī)劃分層,然后利用規(guī)劃問(wèn)題中agent的初始狀態(tài)集合等信息來(lái)合并所有agent的分層信息,并在合并的過(guò)程中得到同層狀態(tài)之間的沖突表,再使用正向搜索方法,在保證沖突最小的情況下,以最小動(dòng)作權(quán)值優(yōu)先的貪心方法,求出強(qiáng)規(guī)劃解。通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的分析可知,本文所設(shè)計(jì)的算法能夠較快的求解出使所選擇的動(dòng)作權(quán)值總和近似最小的強(qiáng)規(guī)劃解。
【關(guān)鍵詞】：不確定規(guī)劃 多agent規(guī)劃 模型檢測(cè) 強(qiáng)規(guī)劃
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O221
【目錄】：

• 摘要4-5
• Abstract5-9
• 第1章 引言9-12
• 1.1 課題的背景和意義9-10
• 1.2 本文的主要內(nèi)容和組織結(jié)構(gòu)10-12
• 1.2.1 主要內(nèi)容10-11
• 1.2.2 組織結(jié)構(gòu)11-12
• 第2章 背景知識(shí)12-20
• 2.1 智能規(guī)劃12-13
• 2.2 不確定規(guī)劃與基于模型檢測(cè)的不確定規(guī)劃13-17
• 2.3 多agent規(guī)劃17-19
• 2.4 本章小結(jié)19-20
• 第3章 完全可觀察下單agent帶權(quán)值的強(qiáng)規(guī)劃算法20-36
• 3.1 問(wèn)題描述20-21
• 3.2 相關(guān)定義21-24
• 3.3 算法24-32
• 3.3.1 強(qiáng)規(guī)劃分層算法25-26
• 3.3.2 最小權(quán)值強(qiáng)規(guī)劃解搜索算法26-28
• 3.3.3 正確性分析28-29
• 3.3.4 算法示例分析29-32
• 3.4 實(shí)驗(yàn)32-34
• 3.5 本章小結(jié)34-36
• 第4章 完全可觀察下多agent帶權(quán)值的強(qiáng)規(guī)劃算法36-54
• 4.1 問(wèn)題描述36-37
• 4.2 相關(guān)定義37-41
• 4.3 算法41-52
• 4.3.1 多agent強(qiáng)規(guī)劃分層算法42-43
• 4.3.2 強(qiáng)規(guī)劃算法43-46
• 4.3.3 沖突處理算法46-47
• 4.3.4 正確性分析47
• 4.3.5 算法示例分析47-52
• 4.4 實(shí)驗(yàn)52-53
• 4.5 本章小結(jié)53-54
• 第5章 總結(jié)與展望54-55
• 參考文獻(xiàn)55-59
• 致謝59-60
• 附錄A （攻讀碩士學(xué)位期間發(fā)表的論文）60-61
• 附錄B （攻讀碩士學(xué)位期間參與的科研項(xiàng)目）61
• 附錄C （攻讀碩士學(xué)位期間獲獎(jiǎng)情況）61

，

本文編號(hào)：929616