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

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

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

【學位級別】：碩士

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


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



本文編號：3120076