摘要：經(jīng)典智能規(guī)劃問題是人工智能研究領(lǐng)域里最為重要的問題之一。但是由于其時(shí)間復(fù)雜度上的不可跟蹤性,使得這項(xiàng)技術(shù)在實(shí)際應(yīng)用中的范圍十分受限,所以一直以來,與智能規(guī)劃有關(guān)的計(jì)算復(fù)雜性問題備受關(guān)注。本文試圖從形式描述的角度探究智能規(guī)劃的計(jì)算復(fù)雜性。本文提出一種全新的方法：使用形式邏輯語言來描述經(jīng)典智能規(guī)劃問題,并提供相應(yīng)的算法來將這種描述“解釋”為傳統(tǒng)的基于動(dòng)作的規(guī)劃問題描述。在本文的算法之前,還沒有能夠完全實(shí)現(xiàn)該功能的方法,達(dá)到使任何一種泛化描述的PSPACE類問題轉(zhuǎn)化為基于動(dòng)作的智能規(guī)劃問題。該方法是基于二階傳遞閉包邏輯（SO（TC））的。首先,本文提出一種SO（TC）的范式,并證明其完全性,根據(jù)這個(gè)證明,可以容易的得到一種可以針對(duì)SO（TC）范圍內(nèi)的任何表達(dá)式的規(guī)范化方法。在此基礎(chǔ)上,提出一個(gè)算法,可以直接將這種范式“解釋”成一個(gè)PDDL語言描述的智能規(guī)劃問題,于是就得到了一個(gè)完整的算法。生成結(jié)果編碼使用PDDL這種功能豐富的語言。本問提出的這個(gè)方法,價(jià)值可以體現(xiàn)在兩個(gè)方面：一方面,這個(gè)算法使得使用智能規(guī)劃求解器來求解邏輯化描述的模型檢測(cè)問題成為可能。這種邏輯描述,既可以來自手工編制的... 

【文章來源】：中南大學(xué)湖南省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：57 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
目錄
1 緒論
    1.1 研究意義
    1.2 相關(guān)研究工作
    1.3 本文提出的基于傳遞閉包邏輯的描述方法
    1.4 本文的主要內(nèi)容和組織
2 智能規(guī)劃理論及相關(guān)技術(shù)
    2.1 智能規(guī)劃模型
    2.2 智能規(guī)劃的計(jì)算復(fù)雜性分析
        2.2.1 與之相關(guān)的計(jì)算復(fù)雜性理論基礎(chǔ)
        2.2.2 智能規(guī)劃的復(fù)雜性結(jié)論
    2.3 智能規(guī)劃問題的建模語言
        2.3.1 STRIPS描述方法
        2.3.2 PDDL語言及其主要版本
    2.4 本章小結(jié)
3 描述復(fù)雜性理論及其與智能規(guī)劃的聯(lián)系
    3.1 描述復(fù)雜性理論
        3.1.1 一階和二階謂詞邏輯
        3.1.2 傳遞閉包邏輯
        3.1.3 邏輯推論
        3.1.4 描述復(fù)雜性理論及其重要結(jié)論
    3.2 智能規(guī)劃的描述復(fù)雜性分析
    3.3 本章小結(jié)
4 智能規(guī)劃的邏輯化描述及相關(guān)算法
    4.1 傳遞閉包邏輯表達(dá)式的規(guī)范形式
        4.1.1 一階傳遞閉包邏輯的范式和規(guī)范化方法
        4.1.2 二階傳遞閉包邏輯的范式的提出
    4.2 從規(guī)范化形式到PDDL語言描述
        4.2.1 域定義（Domain）
        4.2.2 基動(dòng)作翻譯（Action）
        4.2.3 問題實(shí)例生成（Problem Instance）
    4.3 實(shí)驗(yàn)實(shí)現(xiàn)及其結(jié)果
    4.4 本章小結(jié)
5 論性質(zhì)方面的結(jié)論
    5.1 可靠性和完全性
    5.2 復(fù)雜性
    5.3 轉(zhuǎn)化過程對(duì)NP的復(fù)雜度保持
    5.4 本章小結(jié)
6 總結(jié)與展望
參考文獻(xiàn)
附錄：部分實(shí)驗(yàn)結(jié)果
攻讀學(xué)位期間主要的研究成果
致謝


【參考文獻(xiàn)】：
期刊論文
[1]從規(guī)劃解中學(xué)習(xí)一階派生謂詞規(guī)則[J]. 饒東寧,蔣志華,姜云飛,劉強(qiáng).  計(jì)算機(jī)學(xué)報(bào). 2010(02)
[2]基于規(guī)劃圖的蟻群規(guī)劃算法[J]. 柴嘯龍,姜云飛,陳藹祥.  計(jì)算機(jī)研究與發(fā)展. 2009(09)
[3]智能規(guī)劃器StepByStep的研究和開發(fā)[J]. 吳向軍,姜云飛,凌應(yīng)標(biāo).  軟件學(xué)報(bào). 2008(09)



本文編號(hào)：3120076