智能規(guī)劃的一種邏輯化描述.pdf

1、經(jīng)典智能規(guī)劃問題是人工智能研究領(lǐng)域里最為重要的問題之一。但是由于其時(shí)間復(fù)雜度上的不可跟蹤性，使得這項(xiàng)技術(shù)在實(shí)際應(yīng)用中的范圍十分受限，所以一直以來，與智能規(guī)劃有關(guān)的計(jì)算復(fù)雜性問題備受關(guān)注。本文試圖從形式描述的角度探究智能規(guī)劃的計(jì)算復(fù)雜性。本文提出一種全新的方法:使用形式邏輯語(yǔ)言來描述經(jīng)典智能規(guī)劃問題，并提供相應(yīng)的算法來將這種描述“解釋”為傳統(tǒng)的基于動(dòng)作的規(guī)劃問題描述。在本文的算法之前，還沒有能夠完全實(shí)現(xiàn)該功能的方法，達(dá)到使任何一種泛化描述

2、的PSPACE類問題轉(zhuǎn)化為基于動(dòng)作的智能規(guī)劃問題。
　　該方法是基于二階傳遞閉包邏輯(SO(TC))的。首先，本文提出一種SO(TC)的范式，并證明其完全性，根據(jù)這個(gè)證明，可以容易的得到一種可以針對(duì)SO(TC)范圍內(nèi)的任何表達(dá)式的規(guī)范化方法。在此基礎(chǔ)上，提出一個(gè)算法，可以直接將這種范式“解釋”成一個(gè)PDDL語(yǔ)言描述的智能規(guī)劃問題，于是就得到了一個(gè)完整的算法。生成結(jié)果編碼使用PDDL這種功能豐富的語(yǔ)言。本問提出的這個(gè)方法，價(jià)值可以體

3、現(xiàn)在兩個(gè)方面:一方面，這個(gè)算法使得使用智能規(guī)劃求解器來求解邏輯化描述的模型檢測(cè)問題成為可能。這種邏輯描述，既可以來自手工編制的代碼，也可以由其它形式描述轉(zhuǎn)化而來;另一方面，本文提出的這種二階邏輯的傳遞閉包范式，可以看成是一種緊湊的，統(tǒng)一的智能規(guī)劃問題描述，本文認(rèn)為這種描述方法可以促進(jìn)智能規(guī)劃理論的進(jìn)一步研究。
　　該算法由兩個(gè)主要過程連接組成。本文使用C++編程語(yǔ)言實(shí)現(xiàn)了這個(gè)算法，該程序能夠生成標(biāo)準(zhǔn)的PDDL代碼，可以直接作為智能