劉越暢，林曉駿，湯 庸

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

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

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

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

1 問題定義

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

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

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

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

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

由DTN的定義可以看出，一個DTN實際上是一個有向、多重標號圖。

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

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

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

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

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

圖2 弱演化DTNFig.2 Weakly evolutional DTN

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

2 算法及系統(tǒng)設計

2.1 DTP一致性判定算法

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

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

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

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

DTP的求解與CSP的求解一樣，實際應用中必須使用一些啟發(fā)式技術，否則必定遭遇狀態(tài)爆炸的問題。當前研究文獻中提出的求解DTP的啟發(fā)式技術主要有前向檢查技術、最少剩余值變量排序、語義分枝、被吸收變量移除、遞增前向檢查技術、基于拓撲的變量、值選擇策略等。以下對這些技術的基本思想作簡要介紹。

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

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

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

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

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

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

2.3 系統(tǒng)設計

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

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

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

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

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

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

1) 分枝(Brancher)策略。

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

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

圖6 分枝器類設計Fig.6 Brancher classes design

2) 傳播器(Propagator)。

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

圖7 傳播器類設計Fig.7 Propagator class design

③ 引擎編程(Engine programming)

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

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

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

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

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

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

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

示例：假設輸入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之外任何傳播器進行問題求解，可視化模塊將按圖10形式動態(tài)顯示DTN演化過程。

4 結(jié) 語

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

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

參考文獻：

[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] 劉越暢，姜云飛，錢紅. 基于問題結(jié)構(gòu)的啟發(fā)式策略在析取時態(tài)問題求解中的應用 [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] 劉越暢. 基于約束的時態(tài)推理和時態(tài)規(guī)劃[D]. 廣州: 中山大學, 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.