基于規(guī)劃圖的時態(tài)推理與時態(tài)規(guī)劃.pdf

1、智能規(guī)劃是人工智能的一個重要研究領(lǐng)域，智能規(guī)劃的主要思想是根據(jù)預(yù)定實現(xiàn)的目標，對若干可供選擇動作及所提供的資源限制進行推理，得到實現(xiàn)目標的動作序列。近幾年來，為了表示規(guī)劃過程中產(chǎn)生的條件因素和動態(tài)信息，大量的研究工作圍繞條件效果、不確定性和時態(tài)規(guī)劃等情況展開，同時，一些高效算法的提出也大大推動了智能規(guī)劃的研究從經(jīng)典問題向?qū)嶋H規(guī)劃問題的轉(zhuǎn)移，智能規(guī)劃研究的課題不斷地由理論研究領(lǐng)域走向?qū)嶋H應(yīng)用領(lǐng)域。 在時態(tài)規(guī)劃方面，由于許多現(xiàn)實世界

2、中的規(guī)劃問題通常希望規(guī)劃目標能在盡可能短的時間內(nèi)實現(xiàn)，并且規(guī)劃過程中存在大量能并發(fā)執(zhí)行的持續(xù)性動作，這些動作的執(zhí)行需要考慮時間、資源的消耗。這類規(guī)劃問題，用經(jīng)典規(guī)劃中帶瞬間動作的STRIPS模型是無法進行表示的，因此，為表示實際規(guī)劃問題，需要對時間信息進行有效表示，并能進行時序約束推理。國際標準規(guī)劃語言PDDL2.1版本即是在原來規(guī)劃語言基礎(chǔ)上增加了對持續(xù)性動作和數(shù)值量詞的支持，這方面的規(guī)劃領(lǐng)域問題在歷屆國際規(guī)劃大賽中非常受重視。但目前

3、現(xiàn)有的時態(tài)規(guī)劃算法的效率以及規(guī)劃過程中時態(tài)推理的技術(shù)及其運用都難以令人滿意。為此，本文在時態(tài)推理技術(shù)和時態(tài)規(guī)劃問題的求解方法兩個方面進行了研究。 在時態(tài)推理技術(shù)研究部分，本文首先介紹了經(jīng)典規(guī)劃的概念模型，以及其受限和擴展模型，指出了時態(tài)規(guī)劃所需要解決的技術(shù)問題。規(guī)劃圖是圖規(guī)劃技術(shù)中的數(shù)據(jù)結(jié)構(gòu)，傳統(tǒng)規(guī)劃領(lǐng)域中難以處理的動作和狀態(tài)之間可能存在的互斥關(guān)系均能簡潔地表示在規(guī)劃圖上，本文在規(guī)劃圖框架下，定義了動作圖，并進一步擴展為時態(tài)動作

4、圖，使之能體現(xiàn)時態(tài)規(guī)劃問題中的時態(tài)信息。在此基礎(chǔ)上，提出了一種對時態(tài)信息進行表示與管理，并且能夠進行時態(tài)約束推理的時態(tài)一致性賦值方法；約束可滿足問題(CSP)是一個通用的且功能強大的問題求解的范例，在規(guī)劃問題中，時態(tài)關(guān)系可以用CSP技術(shù)和方法方便地表示和處理。本文利用CSP技術(shù)對時序約束進行處理，包括過濾、約減及時態(tài)信息的一致性檢驗，使時態(tài)推理技術(shù)能更好地應(yīng)用于時態(tài)規(guī)劃的求解過程中。 在求解時態(tài)規(guī)劃問題實現(xiàn)部分，本文首先綜述了經(jīng)

5、典時態(tài)規(guī)劃的技術(shù)方法，對目前比較受關(guān)注的、性能較好的時態(tài)規(guī)劃器從技術(shù)方法上進行了研究分析；對PDDL2.1語言所描述的支持持續(xù)動作的規(guī)劃領(lǐng)域問題，利用遺傳算法實現(xiàn)求解時態(tài)規(guī)劃的算法。算法針對基于規(guī)劃圖的遺傳規(guī)劃技術(shù)存在局部搜索能力不足的缺點，提出了在原有遺傳操作算子的基礎(chǔ)上，引入局部修復(fù)算子的混合規(guī)劃技術(shù)，這種方法的優(yōu)點在于能夠在規(guī)劃求解中對時態(tài)信息進行處理，減少冗余和不一致的時態(tài)信息，提高了求解效率，同時利用遺傳規(guī)劃算法能夠避免局部搜