可視化析取時(shí)態(tài)推理器的設(shè)計(jì)與實(shí)現(xiàn)*

劉越暢，林曉駿，湯 庸

(1.嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院，廣東 梅州 514015；2.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510631；3.華南理工大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

人工智能規(guī)劃(或稱自動(dòng)規(guī)劃：automated planning)是人工智能領(lǐng)域一個(gè)重要的研究子領(lǐng)域。經(jīng)典的智能規(guī)劃依賴于幾個(gè)理想化假設(shè)[1]，如：動(dòng)作的效果是確定的，系統(tǒng)是靜態(tài)、完全可觀察的，動(dòng)作是瞬時(shí)發(fā)生的(動(dòng)作沒(méi)有持續(xù)時(shí)間)，等等。隨著解決實(shí)際問(wèn)題的需要和智能規(guī)劃技術(shù)研究的深入，這些理想化假設(shè)不再是必需的。例如，現(xiàn)實(shí)中的動(dòng)作或者活動(dòng)極少是瞬間發(fā)生的，往往具有一定的持續(xù)時(shí)間；另外，動(dòng)作發(fā)生的前提條件不一定非得在動(dòng)作開(kāi)始執(zhí)行時(shí)成立，同時(shí)動(dòng)作的效果也不一定都發(fā)生在動(dòng)作完成之時(shí)。再如，系統(tǒng)的初始條件和目標(biāo)命題也可以賦以時(shí)間上的意義：初始條件命題可以發(fā)生在某個(gè)時(shí)間段內(nèi)，而目標(biāo)命題之間也可以有時(shí)間上的關(guān)系(時(shí)態(tài)擴(kuò)展目標(biāo))，等等。此外，引入時(shí)間元素還可以對(duì)經(jīng)典規(guī)劃進(jìn)行進(jìn)一步的擴(kuò)展，如引入外部事件等。時(shí)態(tài)規(guī)劃便是經(jīng)典智能規(guī)劃對(duì)命題和動(dòng)作在時(shí)間的維度上進(jìn)行擴(kuò)展的產(chǎn)物。析取時(shí)態(tài)問(wèn)題(Disjunctive Temporal Problem, DTP)是Kostas Stergiou和Manolis Koubarakis提出的基于時(shí)間點(diǎn)的定量時(shí)態(tài)模型[2]。使用DTP作為時(shí)態(tài)規(guī)劃中的時(shí)態(tài)模型的優(yōu)勢(shì)是可以將規(guī)劃階段的決策推遲到調(diào)度(時(shí)態(tài)推理)階段解決，這樣平衡兩方面計(jì)算量的同時(shí)提高了規(guī)劃靈活性[3]。自DTP問(wèn)題提出以來(lái)，研究者陸續(xù)提出了DTP求解算法(如局部搜索DTP算法[4]、基于電路編碼的SAT算法[5])、基于拓?fù)湫畔⒌膯l(fā)式技術(shù)[6]，以及DTP問(wèn)題的擴(kuò)展(如動(dòng)態(tài)DTP[7]、基于偏好的DTP[8]、多智能體DTP[9])。DTP豐富的表達(dá)力和應(yīng)用潛力使得人們對(duì)它的研究持續(xù)升溫，短短時(shí)間內(nèi)國(guó)際著名的人工智能研究雜志《人工智能》已有多篇專門(mén)研究DTP的論文誕生。

基于結(jié)構(gòu)信息在DTP問(wèn)題求解中的重要性，在析取時(shí)態(tài)網(wǎng)絡(luò)(Disjunctive Temporal Network, DTN)[10]的基礎(chǔ)上，本文提出了DTP弱蘊(yùn)含性和弱演化析取時(shí)態(tài)網(wǎng)絡(luò)(Weakly Evolutional DTN, WEDTN)，設(shè)計(jì)了基于WEDTN的可視化DTP求解器TRSE(Temporal Reasoning Solution Environment)。系統(tǒng)演示可以看出，與常用的基于搜索樹(shù)的可視化求解系統(tǒng)不同，基于WEDTN的DTP求解器可視化更有利于人們直觀了解DTP的結(jié)構(gòu)特征及其與求解過(guò)程的影響。

本文組織如下：第1節(jié)首先給出必要的問(wèn)題定義；第2節(jié)介紹DTP問(wèn)題求解的基本算法及TRSE系統(tǒng)設(shè)計(jì)；第3節(jié)是系統(tǒng)演示部分；第4節(jié)介紹相關(guān)結(jié)論和未來(lái)工作。

1 問(wèn)題定義

定義1 一個(gè)簡(jiǎn)單時(shí)態(tài)問(wèn)題(Simple Temporal Problem, STP)[11]是一個(gè)二元組，其中：X={x1,x2, …,xn}稱為時(shí)態(tài)變量集合；C={c1,c2, …,cm}是簡(jiǎn)單時(shí)態(tài)約束集合，每個(gè)ci是形如xi-xj≤c(xi,xj∈X，c∈Z)的二元約束1。

由定義可知，一個(gè)STP與一個(gè)所有變量定義在整數(shù)域上的約束滿足問(wèn)題(Constraint Satisfaction Problem, CSP)是等價(jià)的。正如CSP可以使用約束圖來(lái)表示那樣，STP也可以使用時(shí)態(tài)約束網(wǎng)絡(luò)來(lái)表示，下面給出具體定義。

定義2 給定一個(gè)STP，其簡(jiǎn)單時(shí)態(tài)網(wǎng)絡(luò)是一個(gè)有向邊標(biāo)號(hào)圖，其中：V={vi|xi∈X}，E={|xi-xj≤c∈C}，W是一個(gè)權(quán)重函數(shù)W:E→Z，使得：任意xi-xj≤c∈C則W()=c。

定義3 一個(gè)析取時(shí)態(tài)問(wèn)題是一個(gè)二元組P=，其中：X={x1,x2, …,xn}是一個(gè)變量集合；C={C1,C2, …,Cm}是一個(gè)約束集合，每個(gè)Ci是一個(gè)形如ci1∨ci1∨…∨cik的析取式(也稱為子句)，可以表示為集合{ci1,ci1, …,cik}，其中的cij是一個(gè)形如xu-xv≤c的簡(jiǎn)單時(shí)態(tài)約束(xu,xv∈X；xu,xv,c∈Z)。

定義4 給定一個(gè)析取時(shí)態(tài)問(wèn)題P=，它相應(yīng)的析取時(shí)態(tài)網(wǎng)絡(luò)是一個(gè)五元組N=，其中：V(N)={v1,v2,…,vn}是頂點(diǎn)集合；E(N)={|vi,vj∈V(N),k∈L,w∈W}是一個(gè)四元組邊集合；L={k|Ck∈C}是一個(gè)標(biāo)號(hào)集合；W是一個(gè)權(quán)重符號(hào)集合；PRJ是個(gè)映射函數(shù)，使得：PRJ(xi)=vi(xi∈X)，PRJ(ck=xi-xj≤c)=。

由DTN的定義可以看出，一個(gè)DTN實(shí)際上是一個(gè)有向、多重標(biāo)號(hào)圖。

性質(zhì)1 給定一個(gè)DTP=，其中：X={x1,x2, …,xn}，C={C1,C2, …,Cm},P是一致的，當(dāng)且僅當(dāng)存在一個(gè)一致的STP, (C’={c1,c2, …,cm},ci∈Ci)。這樣的STP通常稱為析取時(shí)態(tài)問(wèn)題的解STP。

圖1給出了DTP及其DTN的示例[10]。

性質(zhì)2 給定DTPP=和P’=,稱P’弱蘊(yùn)含P，如果X=X’ ,C’?C，且P’是一致的?P是一致的。DTN之間的弱蘊(yùn)含關(guān)系等價(jià)于它們相應(yīng)的DTP的弱蘊(yùn)含關(guān)系。

定義5 給定一個(gè)初始DTN，N0，和另一個(gè)DTN，N1，N1是N0關(guān)于邊e的弱演化DTN(Weakly Evolutional DTN, WEDTN)，如果N1=N0-{e’|N0(L)(e’)=N0(L)(e)}且N1弱蘊(yùn)含N0。

圖2是弱演化DTN序列的示意圖。

圖2 弱演化DTNFig.2 Weakly evolutional DTN

弱演化DTN實(shí)際上考察了在搜索過(guò)程中DTN隨著變量賦值的進(jìn)行對(duì)原變量未選值從原DTN中刪除后的演變過(guò)程。也就是說(shuō)，DTP求解問(wèn)題變?yōu)閷ふ乙粋€(gè)原問(wèn)題DTN的弱演化DTN的解STP的過(guò)程。

2 算法及系統(tǒng)設(shè)計(jì)

2.1 DTP一致性判定算法

根據(jù)性質(zhì)1，一個(gè)DTP是否是一致的，可以應(yīng)用搜索算法查找解STP來(lái)求解。此時(shí)相當(dāng)于將原問(wèn)題看作一個(gè)CSP：每個(gè)變量對(duì)應(yīng)于DTP中的每個(gè)析取約束，而變量的取值范圍是該析取約束中的所有析取肢(即簡(jiǎn)單時(shí)態(tài)約束)；而約束則要求所有變量的取值構(gòu)成一個(gè)一致的簡(jiǎn)單時(shí)態(tài)問(wèn)題(即解STP)。

圖3給出了該CSP求解算法的大體框架[12]。該算法每次選擇一個(gè)變量(第2行)進(jìn)行嘗試賦值，若當(dāng)前賦值與當(dāng)前部分解一致(第4行)則進(jìn)行下一輪迭代(第5行)；否則嘗試其它的值。

圖3 DTP求解搜索算法Fig.3 Search algorithm for DTP solution

2.2 啟發(fā)式(Heuristics)技術(shù)

DTP的求解與CSP的求解一樣，實(shí)際應(yīng)用中必須使用一些啟發(fā)式技術(shù)，否則必定遭遇狀態(tài)爆炸的問(wèn)題。當(dāng)前研究文獻(xiàn)中提出的求解DTP的啟發(fā)式技術(shù)主要有前向檢查技術(shù)、最少剩余值變量排序、語(yǔ)義分枝、被吸收變量移除、遞增前向檢查技術(shù)、基于拓?fù)涞淖兞俊⒅颠x擇策略等。以下對(duì)這些技術(shù)的基本思想作簡(jiǎn)要介紹。

2.2.1 前向檢查(Forward Check, FC) 前向檢查技術(shù)的核心思想在于：在嘗試賦值之前，首先從未賦值元變量的取值域中刪除那些與當(dāng)前部分解不一致的元值。這種技術(shù)的優(yōu)點(diǎn)在于可以在進(jìn)行下一輪迭代之前首先發(fā)現(xiàn)搜索的死點(diǎn)(如果前向檢查過(guò)程中某個(gè)元變量的取值域?yàn)榭?，從而可以提前回溯，避免進(jìn)行下一輪迭代。

2.2.2 最少剩余值(Minimal Remaining Values, MRV) 最少剩余值策略的主要思想在于：在當(dāng)前節(jié)點(diǎn)選擇變量(FC_DTP中的select_var函數(shù))進(jìn)行當(dāng)前賦值的時(shí)候，優(yōu)先選擇那些具有最少候選元值的元變量。MRV策略是一種最常使用的基于“失敗優(yōu)先(FF)”原則[13]的變量選擇策略。與前向檢查技術(shù)配合使用時(shí)，由于元變量的取值域隨著搜索的進(jìn)行不斷地發(fā)生變化，因此MRV實(shí)現(xiàn)了動(dòng)態(tài)的變量選擇功能。實(shí)驗(yàn)證明FC與MRV的組合具有顯著的剪枝能力[14]。

2.2.3 語(yǔ)義分枝策略(Semantic Branching, SB)

語(yǔ)義分枝策略也是DTP求解中的一個(gè)剪枝能力很強(qiáng)的啟發(fā)式技術(shù)。它的核心思想是：在針對(duì)某個(gè)變量賦值的搜索節(jié)點(diǎn)，若一個(gè)值(cij:x-y≤c)嘗試后到達(dá)一個(gè)死點(diǎn)，該值將被拋棄并將嘗試其它的值；此時(shí)，根據(jù)該不等式的語(yǔ)義，在當(dāng)前DTP和部分解下，x-y≤c為假意味著～(x-y≤c)即x-y>c為真，在時(shí)態(tài)變量取值為整數(shù)的情況下有y-x≤-c-1為真，將y-x≤-c-1顯式地加入到當(dāng)前部分解中并將該約束傳播不會(huì)改變?cè)瓎?wèn)題的一致性，并將有助于更早地剪枝。

2.2.4 被吸收變量移除技術(shù)(Removal of Subsumed Values, RSV) 被吸收變量移除技術(shù)的思想是：假設(shè)當(dāng)前部分解STP的距離圖中，有x、y之間的最短距離distance(x,y)=c，如果對(duì)于某個(gè)未賦值的元變量Ck其取值域中具有一個(gè)候選元值ckj：y-x≤c’且有c≤c’，則稱Ck被該解STP所吸收；此時(shí)可直接將ckj：y-x≤c’賦值給Ck而不需要進(jìn)行一致性判定和嘗試其它的值(因?yàn)榇藭r(shí)ckj：y-x≤c’的加入不會(huì)使最短距離發(fā)生任何變化，因此它與當(dāng)前部分解STP必然是一致的。

2.2.5 基于拓?fù)涞淖兞亢椭颠x擇策略(Topology-based Variable/Value Ordering, TVO) TVO的基本思想是：從DTN中計(jì)算每條邊的沖突系數(shù)，通過(guò)多種組合函數(shù)，計(jì)算每個(gè)變量的沖突系數(shù)。根據(jù)沖突系數(shù)和“失敗優(yōu)先”(Fail-First)原則，優(yōu)先選擇那些沖突系數(shù)較大的變量和沖突系數(shù)較小的值。雖然同樣是變量選擇策略，實(shí)驗(yàn)證明TVO比MRV具有更強(qiáng)的剪枝能力[6]。

2.3 系統(tǒng)設(shè)計(jì)

TRSE系統(tǒng)架構(gòu)如圖4所示。其中：Script模塊主要是DTP問(wèn)題的表示腳本。該腳本傳遞給系統(tǒng)的Model(建模)模塊，生成問(wèn)題的內(nèi)部表示。Model模塊將問(wèn)題信息分別與Engine和Visulisation模塊交互，完成問(wèn)題的求解及可視化。以下分別闡述各模塊的設(shè)計(jì)。

圖4 TRSE系統(tǒng)架構(gòu)Fig.4 TRSE architecture

2.3.1 建模(Model)和引擎(Engine)模塊 將DTP問(wèn)題放在CSP的框架下求解最大的優(yōu)勢(shì)是，可以使用大量現(xiàn)有的CSP研究成果應(yīng)用到DTP的求解中。其次，應(yīng)用現(xiàn)有優(yōu)秀的CSP求解框架能夠使整個(gè)求解器結(jié)構(gòu)清晰，易于使用和維護(hù)。為了達(dá)到這個(gè)目的，本文使用Gecode作為建模和求解引擎。Gecode是瑞典皇家理工學(xué)院Christian Schulte開(kāi)發(fā)的開(kāi)放、免費(fèi)、可移植、易使用、有效率的用于開(kāi)發(fā)基于約束系統(tǒng)及應(yīng)用的環(huán)境約束求解框架，它提供一個(gè)模塊化和可拓展的約束求解器。圖5展示了Gecode的系統(tǒng)架構(gòu)[15]。

圖5 Gecode系統(tǒng)架構(gòu)Fig.5 Gecode architecture

從Gecode架構(gòu)設(shè)計(jì)可見(jiàn)，除了提供預(yù)先定義的常見(jiàn)類型變量(整數(shù)、實(shí)數(shù)、集合類型)及相關(guān)約束，Gecode還提供了豐富的自定義編程(Programming)功能，使用戶可以根據(jù)自己的需要對(duì)用戶領(lǐng)域的約束滿足問(wèn)題進(jìn)行靈活建模。對(duì)DTP的可視化約束滿足建模要對(duì)其中的變量、傳播器和分枝器、搜索引擎分別進(jìn)行自定義編程。由于約束建?？梢杂卸喾N靈活的方式，對(duì)同一個(gè)DTP，Gecode同樣提供多種建模方法。在本系統(tǒng)中，為方便起見(jiàn)，我們?nèi)匀粦?yīng)用整數(shù)變量類型處理。使用Map數(shù)據(jù)結(jié)構(gòu)將每個(gè)整數(shù)值與相應(yīng)的簡(jiǎn)單時(shí)態(tài)約束聯(lián)系起來(lái)。

根據(jù)這一架構(gòu)，在TRSE系統(tǒng)中設(shè)計(jì)了以下的分枝、傳播器。

1) 分枝(Brancher)策略。

根據(jù)以上對(duì)應(yīng)用的啟發(fā)式策略分析，其中的MRV和TVO分別可以作為不同的分枝器。連同最簡(jiǎn)單的變量隨機(jī)選擇方法，系統(tǒng)中設(shè)計(jì)了三種分枝器：BaseBrancher、MRVBrancher、TVOBrancher。需要注意的是，這三種分枝器是互斥的，即每次約束求解進(jìn)行的時(shí)候，只能應(yīng)用其中一種分枝器。

其結(jié)構(gòu)如圖6。

圖6 分枝器類設(shè)計(jì)Fig.6 Brancher classes design

2) 傳播器(Propagator)。

在Gecode框架中，傳播器可以對(duì)兩種元素進(jìn)行描述：一種是約束，以判定當(dāng)前值選擇的一致性；另一種是約束的傳播，以進(jìn)行搜索的剪枝。本系統(tǒng)設(shè)計(jì)了以下傳播器：FWPropgat/DPCPropgat/PC3Propgat是第一種傳播器，用以判斷當(dāng)前部分解STP的一致性(分別對(duì)應(yīng)FloydWarshall算法、DPC算法[11]、P3C算法[16])，這三個(gè)有且僅有一個(gè)在運(yùn)行中起作用；FCPropgat/RSVPropgat/SBPropgat是第二種傳播器，對(duì)應(yīng)于前面描述的三種啟發(fā)式：前向檢查、被吸收變量移除、語(yǔ)義分枝，此三種傳播器可以在約束求解前任意選擇是否在求解中應(yīng)用。傳播器的設(shè)計(jì)如圖7所示。

圖7 傳播器類設(shè)計(jì)Fig.7 Propagator class design

③ 引擎編程(Engine programming)

通過(guò)分枝器和傳播器，利用Gecode缺省的算法引擎已經(jīng)能夠處理大多數(shù)的約束求解及應(yīng)用。在TRSE中，可視化模塊要求跟蹤引擎的運(yùn)行過(guò)程，以便將求解過(guò)程(主要是變量賦值信息)進(jìn)行圖形化展示。因此，需要對(duì)引擎進(jìn)行變量選擇并賦值后，將該信息傳遞給可視化模塊進(jìn)行圖形展示。這主要在Status()函數(shù)中調(diào)用choice()函數(shù)獲得。

圖8展示了以上設(shè)計(jì)的分枝器和傳播器交替執(zhí)行的迭代過(guò)程。一個(gè)基于CSP的DTP求解過(guò)程主要就是分枝和傳播的迭代過(guò)程，在這個(gè)過(guò)程中，首先進(jìn)行分枝(即：變量和值選擇)，然后根據(jù)分枝結(jié)果進(jìn)行約束的傳播為下一次分枝做準(zhǔn)備。此過(guò)程也考慮了多個(gè)分枝器和傳播器的相容性問(wèn)題：MRVBrancher、TVOBrancher和BaseBrancher每次需要且只能選擇其中之一，F(xiàn)CPropogat默認(rèn)使用，RSV和SB傳播器可同時(shí)使用，用于STP簡(jiǎn)單約束傳播的P3C、DPC、FW傳播器次需要且只能選擇其中之一。

圖8 分枝器和傳播器交替執(zhí)行過(guò)程Fig.8 Iterative execution of branchers and propagators

2.3.2 可視化(visualisation)模塊 與Gecode現(xiàn)有的Gist可視化模塊(僅表達(dá)搜索過(guò)程中節(jié)點(diǎn)選擇的搜索樹(shù))不同，TRSE中的可視化模塊使用DTN表達(dá)問(wèn)題的拓?fù)浣Y(jié)構(gòu)，并在此結(jié)構(gòu)上動(dòng)態(tài)展示搜索中的動(dòng)態(tài)值選擇過(guò)程。內(nèi)部圖結(jié)構(gòu)使用JGraphT[17]，而圖形展示使用開(kāi)源的JUNG庫(kù)[18]實(shí)現(xiàn)。

3 系統(tǒng)實(shí)現(xiàn)及演示

圖9是TRSE系統(tǒng)界面。該系統(tǒng)分為四大模塊。一是輸入模塊，可以通過(guò)文本框鍵盤(pán)輸入、選擇一個(gè)DTP文件或者選擇目錄順序求解該目錄下所有DTP文件三種方式輸入求解對(duì)象。二是選項(xiàng)設(shè)置模塊，用于進(jìn)行求解前的設(shè)置選項(xiàng)(使用的分枝器、傳播器、超時(shí)設(shè)置、可視化設(shè)置)。三是可視化顯示模塊，用于通過(guò)演化DTN動(dòng)態(tài)展示求解過(guò)程。四是結(jié)果輸出模塊，展示DTP求解結(jié)果。

圖9 TRSE主界面Fig.9 TRSE graphical user interface

示例：假設(shè)輸入DTP：P=,X={x1,x2,x3,x4,x5},C={C1,C2,C3}。C1≡x1-x2≤2 ∨x3-x2≤-1；C2≡x2-x3≤2 ∨x1-x2≤4；C3≡x2-x1≤-3 ∨x3-x1≤-5。

選擇BaseBrancher分枝器，不選擇除FCPropgat之外任何傳播器進(jìn)行問(wèn)題求解，可視化模塊將按圖10形式動(dòng)態(tài)顯示DTN演化過(guò)程。

4 結(jié) 語(yǔ)

由于析取時(shí)態(tài)問(wèn)題在智能規(guī)劃和調(diào)度領(lǐng)域中廣泛得到應(yīng)用，近年來(lái)成為該領(lǐng)域的研究熱點(diǎn)，已產(chǎn)生了多篇國(guó)際《人工智能》雜志上發(fā)表的研究論文。本文闡述了一個(gè)以DTP為模型的通用時(shí)態(tài)推理系統(tǒng)TRSE的設(shè)計(jì)和實(shí)現(xiàn)。TRSE的設(shè)計(jì)充分采用軟件設(shè)計(jì)模式和基于演化DTN的可視化設(shè)計(jì)，運(yùn)用現(xiàn)有的高效CSP求解器Gecode和圖可視化庫(kù)JUNG，將重點(diǎn)放在各種啟發(fā)式技術(shù)的設(shè)計(jì)和動(dòng)態(tài)可視化上。雖然DTP的理論研究已經(jīng)取得了較大進(jìn)展，目前尚未有此類通用推理系統(tǒng)的研發(fā)，基于WEDTN的可視化技術(shù)解釋了DTP求解中的結(jié)構(gòu)特性，對(duì)于DTP乃至?xí)r態(tài)推理的學(xué)習(xí)、研究有重要的價(jià)值。進(jìn)一步的工作將擴(kuò)展對(duì)其他DTP求解技術(shù)的集成和已探索DTN和未探索DTN空間[12]等更細(xì)致的結(jié)構(gòu)特征的展示支持。

圖10 DTN弱演化過(guò)程((a)→(b)→(c)→(d))Fig.10 Weak evolution process((a)→(b)→(c)→(d))

參考文獻(xiàn)：

[1] GHALLAB M, NAU D, TRAVERSO P. Automated planning: theory and practice [M]. San Francisco: Morgan Kaufmann Publishers, 2004.

[2] STERGIOU K, KOUBARAKIS M. Backtracking algorithms for disjunctions of temporal constraints [J]. Artificial Intelligence, 2000, 120(1): 81-117.

[3] LIU Y, FANG Y. Boost the Integration of planning and scheduling: a heuristics approach [J]. Procedia Engineering, 2012, 29: 3348-3352.

[4] MOFFITT M D, POLLACK M E. Applying local search to disjunctive temporal problems [C]// IJCAI, 2005: 242-247.

[5] BLAINE NELSON T K S K. CircuitTSAT: a solver for large instances of the disjunctive temporal problem [C]//The Eighteenth International Conference on Automated Planning and Scheduling, ICAPS 2008, Sydney, Australia, 2008: 232-239.

[6] LIU Y, JIANG Y, QIAN H. Topology-based variable ordering strategy for solving disjunctive temporal problems[C]//In 15th International Symposium on Temporal Representation and Reasoning, 2008. TIME ’08, 2008: 129-136.

[7] SCHWARTZ PETER J, POLLACK MARTHA E. Two approaches to semi-dynamic disjunctive temporal problems[C]//ICAPS Workshop on Constraint Programming for Planning and Scheduling, Monterey, California, USA. June 2005.

[8] MOFFITT M D. On the modelling and optimization of preferences in constraint-based temporal reasoning [J]. Artificial Intelligence, 2011, 175(7/8): 1390-1409.

[9] BOERKOEL JR J C, DURFEE E H. A distributed approach to summarizing spaces of multiagent schedules [C]//In Proceedings of the 26th National Conference on Artificial Intelligence (AAAI-12), Toronto, Canada, 2012: 1742-1748.

[10] 劉越暢，姜云飛，錢(qián)紅. 基于問(wèn)題結(jié)構(gòu)的啟發(fā)式策略在析取時(shí)態(tài)問(wèn)題求解中的應(yīng)用 [J]. 計(jì)算機(jī)研究與發(fā)展，2008, 45(11): 1840-1849.

[11] DECHTER R, MEIRI I, PEARL J. Temporal constraint networks[J]. Artificial Intelligence,1991,49:61-95.

[12] 劉越暢. 基于約束的時(shí)態(tài)推理和時(shí)態(tài)規(guī)劃[D]. 廣州: 中山大學(xué), 2008：75-99.

[13] HARALICK R M, ELLIOTT G L. Increasing tree search efficiency for constraint satisfaction problems [J]. Artificial Intelligence, 1980, 14: 26-31.

[14] TSAMARDINOS IOANNIS, POLLACK MARTHA E. Efficient solution techniques for disjunctive temporal reasoning problems [J]. Artificial Intelligence， 2003, 151(1/2): 43-89.

[15] SCHULTE C, TACK G, LAGERKVIST M Z. Modeling and programming with Gecode [EB/OL]. [2010] http://www.gecode.org/doc/4.2.0/MPG.pdf.

[16] PLANKEN L, WEERDT M D, KROGT ROMAN VAN DER. P3c: a new algorithm for the simple temporal problem [C]//In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2008), 2008: 256-263.

[17] JgraphT.A free Java graph library [EB/OL]. [2013] http://jgrapht.org.

[18] JUNG. Java universal network/graph framework [EB/OL]. [2013] http://jung.sourceforge.net.