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

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

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

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

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

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