水下機器人任務(wù)流程建模與管理

張鴻皓，姜大鵬，龐永杰，李金龍

(哈爾濱工程大學(xué)智能水下機器人技術(shù)國防科技重點實驗室，黑龍江哈爾濱150001)

自主機器人的作業(yè)流程總是可以在某一層次上劃分成多個子過程.宏觀的過程可以由子過程、子過程的發(fā)生次序以及決定這種次序的條件構(gòu)成.人們創(chuàng)造了各式各樣的規(guī)則，用來描述和管理自然發(fā)生或人為控制的過程.應(yīng)用在機器人上的作業(yè)流程主要體現(xiàn)人的智能(操控者或機器本身的智能).在機器人相關(guān)領(lǐng)域內(nèi)，對機器細微動作的精確控制早已實現(xiàn)，但針對體現(xiàn)高度智能的宏觀任務(wù)流程的描述與自動管理，尚缺乏成熟的理論和實例.

自治式水下機器人由于工作環(huán)境與人隔絕，特別需要一套能完整表述任務(wù)規(guī)劃者意愿，并能交由計算機自動執(zhí)行管理的理論模型及實用化的方法.傳統(tǒng)的Petri網(wǎng)和工作流模型雖能部分解決上述問題，但多少存在建模困難、編程實現(xiàn)復(fù)雜及描述能力受限等問題［1］，尚未出現(xiàn)一套成功而方便實用的解決方案.

任務(wù)工作流模型較大幅度地改進了傳統(tǒng)的工作流理論，在增強了模型描述能力的同時，也大幅簡化了模型的復(fù)雜度，能以圖形化方式建模并方便地轉(zhuǎn)換為計算機可以理解的文本描述方式，為理論模型的編程實現(xiàn)提供了良好的條件.在此理論基礎(chǔ)上構(gòu)建的水下機器人任務(wù)建模與管理系統(tǒng)已經(jīng)過實踐檢驗，能為復(fù)雜邏輯流程的快速建模與自動管理提供極大的便利.

1 Petri網(wǎng)

Petri網(wǎng)由表示狀態(tài)的元素“庫所”(place)和表示變化的元素“變遷”(transition)組成.聯(lián)系S和T的是兩者間的流關(guān)系，用F表示.庫所可以容納標記(token)，標記代表網(wǎng)路中流動的資源，資源的流動由流關(guān)系規(guī)定.Petri網(wǎng)結(jié)構(gòu)是固定的，而庫所中標記的分布是可變的，標記因變遷而形成的不同分布表征了Petri網(wǎng)的不同狀態(tài).

水下機器人的任務(wù)建模并不困難，只需用到Petri網(wǎng)的基本概念［2-3］，如圖 1及表1中的例子所示.

圖1 水下機器人任務(wù)示例(Petri網(wǎng))Fig.1 An example of AUV task flow(Petri net)

表1 庫所與變遷的含義Table 1 Meanings of places and transition

圖1中的一些庫所會產(chǎn)生沖突，例如當(dāng)S2得到一個標記時，T2、T3不能同時發(fā)生.解決沖突的辦法是由環(huán)境提供信息，決定由誰來占用資源.所以，決定了任務(wù)路由的一些重要條件實際是無法在Petri網(wǎng)中直接表示的，它需要對Petri網(wǎng)進行擴展，使標記和網(wǎng)路能夠攜帶和處理更多的環(huán)境信息.環(huán)境信息的獲取和處理往往相當(dāng)抽象和復(fù)雜，通常只能由高級程序語言編程實現(xiàn).如果要用Petri網(wǎng)來描述，由于Petri網(wǎng)過于嚴謹和形式化，將不得不增加一系列的擴展，增加了網(wǎng)系統(tǒng)的復(fù)雜程度，使得建模和理解都變得更加困難.

Petri網(wǎng)只描述事物間的依賴關(guān)系，沒有更高層的控制流程和其他的人為因素影響，更適合用來描述符合自然規(guī)律的自然過程.然而水下機器人作為人類智能乃至機器智能的執(zhí)行者，其作業(yè)過程無疑更接近人為過程.故雖然有人將Petri網(wǎng)引入水下機器人的任務(wù)管理，但描述和理解困難，不易編程實現(xiàn)，不適合作為抽象任務(wù)的建模工具.

2 工作流模型

工作流模型是對工作業(yè)務(wù)過程的抽象表示.工作流的應(yīng)用通常需要完成業(yè)務(wù)過程的計算機化，其模型不僅要讓人(不僅是專家，還包括普通用戶)容易讀懂，也必須讓計算機能夠理解.

在庫所與變遷的基礎(chǔ)上，為了定義出順序、并行、選擇、循環(huán)等常用的過程邏輯，工作流網(wǎng)構(gòu)造了相應(yīng)的結(jié)構(gòu)化組件，為其規(guī)定了特殊的符號，供用戶在建模時直接使用［4］.每一組件均可給出對應(yīng)的Petri網(wǎng)建模方法:1)順序;2)并行，它需要2個基本的工作流執(zhí)行原語:“與分支”(AND_split)和“與連接”(AND_join)，也可將其當(dāng)做特殊的任務(wù).AND_split能同時發(fā)起多個任務(wù)，而AND_join能對多個并行的流程進行同步;3)選擇，根據(jù)具體的執(zhí)行情況進行“多選一”或“多選多”，構(gòu)造選擇路由需要“或分支”(OR_split)和“或連接”(OR_join);4)循環(huán).

對于 AND_split、AND_join、OR_split、OR_join 這樣經(jīng)常使用的結(jié)構(gòu)，采用圖2中特定的符號來表示.

圖2 工作流邏輯構(gòu)件Fig.2 Logical components of workflow

圖3中的例子與圖1中的流程大體相似［5-6］.盡管保留了庫所、標記等元素，但它并不使用復(fù)雜的路徑、資源的沖突等技巧來表達邏輯上的意義，而是用固有的邏輯組件來構(gòu)造路由，將Petri網(wǎng)構(gòu)造的邏輯結(jié)構(gòu)隱藏在邏輯組件之下.

圖3 任務(wù)示例(工作流模型)Fig.3 Example of AUV task flow(workflow)

雖然Petri網(wǎng)能夠構(gòu)造出一些精妙而準確的邏輯結(jié)構(gòu)，但在多數(shù)時候，這種極其苛求洞察力和智力的建模方式并不適合面向普通人的、需要迅速作出靈活更改的任務(wù)建模.與經(jīng)典的Petri網(wǎng)相比，工作流模型更靈活，更接近人類語言和人抽象的思維方式.但同時，由于缺乏標準、精確和成熟的理論基礎(chǔ)，雖然市面上的工作流模型及基于工作流的應(yīng)用軟件種類繁多，但每種模型都或多或少存在明顯的缺陷，例如OR_join任務(wù)同步時出現(xiàn)的邏輯問題［1］等，尚未見到理論上完美的解決方案［7］.然而總的說來，在適當(dāng)?shù)母倪M和處理之后，工作流模型能夠更好地服務(wù)于機器人抽象任務(wù)建模.

3 任務(wù)工作流

任務(wù)工作流由工作流模型改進而來.定義任務(wù)工作流網(wǎng)為有向網(wǎng)N=(T，F(xiàn))，其中T為任務(wù)，F(xiàn)為流關(guān)系，且需滿足:

1)存在惟一的起始任務(wù)Tstart∈T作為網(wǎng)路的起始點，其前驅(qū)為空;

2)每個任務(wù)t∈T都位于連接到Tstart的一條通路上，不存在孤立的任務(wù);

3)每一任務(wù)結(jié)束時必處于成功或失敗2種狀態(tài)之一，2種狀態(tài)可分別指向不同的后繼任務(wù);

4)任務(wù)間的依賴關(guān)系F可分為2類:發(fā)起一個尚未執(zhí)行的任務(wù)，或終止一個正在執(zhí)行的任務(wù).

模型中只存在任務(wù)極其依賴的關(guān)系，雖然沒有庫所和標記這樣的元素，但類似的功能已被整合到任務(wù)中.默認情況下任何任務(wù)必須等到所有前驅(qū)任務(wù)全部結(jié)束才能執(zhí)行，相當(dāng)于AND_join型;任務(wù)結(jié)束后其對應(yīng)的所有后繼流程也都會被執(zhí)行，相當(dāng)于AND_split型.其他的邏輯關(guān)系，如OR_split和OR_join，將由特殊的任務(wù)來實現(xiàn).不同之處在于區(qū)分出了“成功”和“失敗”2種互斥的結(jié)束狀態(tài)，且流關(guān)系也包括“發(fā)起”和“終止”2種.對任務(wù)首尾邏輯結(jié)構(gòu)的處理不像Petri網(wǎng)那樣顯式地建模表示，而是用一個“工作流管理程序”來進行管理，這在編程實現(xiàn)時更加方便.

任務(wù)工作流有自己的圖形語言，如圖4所示，所有任務(wù)采用相同的圖形樣式.任務(wù)圖形的頭部可接納多個前驅(qū)任務(wù);圖形的尾部分成2個區(qū)域，空白的一半表示執(zhí)行成功，帶叉的一半表示執(zhí)行失敗，從2個區(qū)域流出的箭頭分別代表了2種狀態(tài)下任務(wù)工作流網(wǎng)不同的路徑.水下機器人任務(wù)流程中最為常見的成功或失敗的分支流程在這里成為任務(wù)的內(nèi)置屬性.實箭頭表示發(fā)起一個尚未運行的任務(wù)，虛箭頭表示終止一個正在運行的任務(wù).網(wǎng)絡(luò)中的每個任務(wù)都有惟一的名稱(稱之為標號，以“#”開頭)，同類型的不同任務(wù)的名稱也必須不重復(fù).每個任務(wù)都有內(nèi)置的超時值，默認情況下其值為無窮大，超時后任務(wù)會被判定為失敗，網(wǎng)路流程轉(zhuǎn)向其失敗后的路由.

圖4 任務(wù)工作流圖形描述方式Fig.4 Graphic description of task workflow

每個任務(wù)都是不可分割的原子任務(wù)，要擴展某一任務(wù)，只能在相應(yīng)的流程處插入子網(wǎng).任務(wù)的具體內(nèi)容由高級編程語言編寫，任務(wù)獲取環(huán)境信息、判斷任務(wù)成功執(zhí)行或失敗的代碼都在其實現(xiàn)代碼中.任務(wù)工作流模型只關(guān)注任務(wù)網(wǎng)絡(luò)及流關(guān)系，并不規(guī)定任務(wù)的細節(jié)及具體實現(xiàn)方式.

OR_split結(jié)構(gòu)的實現(xiàn)有2種方式［8］.其一如圖5所示，在T4、T5前添加T2、T32個起著開關(guān)作用的判斷任務(wù)，如果T4執(zhí)行的條件滿足而T5的條件不滿足，則T2任務(wù)成功而T3任務(wù)失敗，于是T4執(zhí)行而T5不執(zhí)行.另一種方式與具體的編程實現(xiàn)有關(guān).在任務(wù)內(nèi)部，可以訪問并更改指向后繼任務(wù)的流程.在上例中，T1內(nèi)部本來保留有 T2、T3的名稱作為后繼，如果在某種條件下刪除其中T3的名稱，那么T1完成后就只能執(zhí)行T2.這2種方式皆可在后繼中任選數(shù)個任務(wù)來執(zhí)行.

圖5 任務(wù)工作流中OR_split結(jié)構(gòu)Fig.5 OR_split structure in task workflow

圖6中T1是一個OR_join任務(wù)，這是任務(wù)工作流模型中惟一特殊的任務(wù)，注意OR_join后面的參數(shù)，第1個參數(shù)2表示T1的前驅(qū)任務(wù)中任有2個結(jié)束后，T1就能以成功的狀態(tài)執(zhí)行完畢.為了避免無止境的等待，OR_join任務(wù)也有超時值.當(dāng)?shù)?個前驅(qū)任務(wù)結(jié)束時，OR_join任務(wù)就被激活，處于等待狀態(tài).如果超過時限后，前驅(qū)條件仍未完全達成，此OR_join會被當(dāng)作失敗.

圖6 任務(wù)工作流中OR_join結(jié)構(gòu)Fig.6 OR_join structure in task workflow

為避免OR_join結(jié)構(gòu)可能產(chǎn)生的邏輯錯誤，OR_join任務(wù)在執(zhí)行結(jié)束后會將其所有可能導(dǎo)致重復(fù)執(zhí)行的前驅(qū)任務(wù)全部刪除，以達到同步的效果.圖6中，若T3、T4結(jié)束，T1成功，工作流管理程序應(yīng)將其直接的前驅(qū)T2、T3、T4一并刪除(刪除即令運行中的任務(wù)停止，不考慮這些任務(wù)的任何后續(xù)影響).

然而OR_join運行時的前驅(qū)條件并不總是如此簡單，上例中，OR_join任務(wù)的標記中還有另一串參數(shù)，顯式指定給工作流管理程序并將其刪除.于是T1結(jié)束后會將圖6中所有6個前驅(qū)任務(wù)全部刪除(默認刪除 T2、T3、T4，顯式刪除 T5、T6、T7).這種方式強調(diào)對建模者意圖的直接表述和利用，就模型本身而言并不嚴謹.然而在相關(guān)理論尚不完善之時，不失為一種簡便有效的方案，相比更改或限制模型，以及用復(fù)雜的算法計算路徑可達性的方法［9-10］，往往有著更好的實現(xiàn)效果.

循環(huán)結(jié)構(gòu)的建模方式如圖7所示，只需在其前方加入一個OR_join任務(wù).

圖7 任務(wù)工作流循環(huán)結(jié)構(gòu)Fig.7 Circulation structure in task workflow

在精簡了邏輯元素，整合了冗余的邏輯結(jié)構(gòu)后，任務(wù)工作流能以更簡潔的方式實現(xiàn)與其他任務(wù)模型相似的功能;而一些新特性的增加，如內(nèi)置的成功或失敗2種完成狀態(tài)和超時值的應(yīng)用，以及對OR_join結(jié)構(gòu)邏輯問題的解決方案，不僅增加了模型的功能，也使得模型更加完善，更適合于水下機器人任務(wù)的建模.

4 任務(wù)工作流的建模流程

首先以圖形化的方式對任務(wù)進行描述，如圖8所示.對照圖8可直接寫出任務(wù)模型的文字描述:

#START{StartMission();;#ToTarget;;NULL;NULL;NEVER}

#ToTarget{ToTarget();#START;#Join1，#Record;;#Join2;;}

#Join1{OrJoin(1);#ToTarget，#Rearrange;#Work;;;;}

#Rearrange{Rearrange();#Work;#Join1;;;;}

#Record{Record();#ToTarget;;;;;}

#Work{Work();#Join1;#Join2;#Record;#Rearrange;;}

#Join2{OrJoin(1);#Work，#ToTarget;#Return;;;;}

#Return{Return();#Join2;#TakeBack;;#Move-Up;;3 600}

#TakeBack{TakeBack();#Return;#Join3;;;;}

#MoveUp{MoveUp();#Return;#Join3;;;;}

#Join3{OrJoin(1);#MoveUp，#TakeBack;#END;;;;}

#END{EndMission();#Join3;;;;;}

每一條描述語句的格式是相同的:

任務(wù)標號{任務(wù)類型及參數(shù);前驅(qū)任務(wù)標號;成功執(zhí)行后發(fā)起的任務(wù)標號;成功后終止的任務(wù)標號;失敗后發(fā)起的任務(wù)標號;失敗后終止的任務(wù)標號;超時值}.

描述語句中各項用分號隔開，若某一項任務(wù)標號為空，可以不寫或?qū)懮稀癗ULL”;若在超時值處為空或?qū)懮稀癗EVER”，則超時值為無窮.

圖8 任務(wù)示例(任務(wù)工作流)Fig.8 An example of AUV task flow(task workflow)

網(wǎng)路中任一表示流程的箭頭，將既被發(fā)起它的前驅(qū)任務(wù)描述，又被接納它的后繼任務(wù)描述，任務(wù)間的依賴關(guān)系便由此銜接起來.對單個任務(wù)的簡單疊加就得到了整個任務(wù)網(wǎng).每一條語句就是對模型中一個任務(wù)及其外延的流關(guān)系的直接描述，故圖中任務(wù)方框的個數(shù)與描述語句數(shù)相同.描述語句沒有先后順序可言，任務(wù)流程描述文件的格式是相當(dāng)靈活的.規(guī)定這樣的描述語言，是為了計算機能直接讀取任務(wù)文本，自動按流程發(fā)起任務(wù)并對任務(wù)進行操作和管理.由于此描述語言格式規(guī)范，因此完全可以開發(fā)相應(yīng)的應(yīng)用軟件，讓建模者直接以圖形方式建模，而由程序自動生成模型的文本描述.

在程序?qū)崿F(xiàn)中，每個任務(wù)類對應(yīng)一個C++類，且每個任務(wù)類都繼承統(tǒng)一的基類，在其中定義通用的數(shù)據(jù)類型和方法，包括對結(jié)束狀態(tài)的判斷，以及與外界通信的手段.如上例中，#Join1、#Join2、#Join3都屬于OrJoin類型，它們都會采用一份相同的代碼來實現(xiàn).

5 任務(wù)管理程序的實現(xiàn)

作為實驗室水下機器人模塊化軟件系統(tǒng)的一部分，基于上述原理與實現(xiàn)方式的水下機器人任務(wù)建模與管理系統(tǒng)已經(jīng)成功開發(fā)，并在仿真平臺和陸地機器人實驗中得到了驗證.這里僅簡述此系統(tǒng)的幾個特點:

1)所有的任務(wù)類型需提前編寫(用C++語言)并編譯完成.任務(wù)流程的描述由文本化的任務(wù)描述文件提供，系統(tǒng)讀取文本中的任務(wù)類型名，自動生成對應(yīng)的C++類的實例并執(zhí)行此任務(wù).任務(wù)只有在需要時才動態(tài)生成，執(zhí)行完成后銷毀，以節(jié)約內(nèi)存空間.這涉及到C++中用字符串動態(tài)生成對象的技巧.

2)此系統(tǒng)提供任務(wù)流程更改的全套接口.無論任務(wù)位于文本描述文件中，還是正在內(nèi)存中執(zhí)行，都有標準的接口用于更改任務(wù)的流關(guān)系及類型，以便在不更換描述文件的情況下更改任務(wù)流程.

3)除起始任務(wù)、OR_join任務(wù)等少數(shù)內(nèi)置任務(wù)外，所有任務(wù)類型都由用戶定義并編寫，任務(wù)管理系統(tǒng)只是按照前文所述的方式自動讀取并管理任務(wù)的執(zhí)行流程.同一任務(wù)類型可以被多次使用，也可以給任務(wù)傳遞參數(shù)，使同一份任務(wù)代碼完成不同的工作.由于任務(wù)可重用，故已經(jīng)存在的任務(wù)越完善，建模的過程就越方便快捷.

4)基于任務(wù)工作流的系統(tǒng)只關(guān)注任務(wù)間的流程關(guān)系，對系統(tǒng)的應(yīng)用范圍并不做規(guī)定.但相對而言，此模型更適合宏觀抽象的任務(wù)流程建模，在機器人的自主智能尚不完善之時，將人類設(shè)計的抽象任務(wù)轉(zhuǎn)換為機器可以理解的方式.

6 結(jié)束語

通過引入并改進工作流的相關(guān)理論，基于任務(wù)工作流的模型不僅建模簡單(可完全依賴圖形描述)、容易理解，更重要的是模型能直接轉(zhuǎn)化為規(guī)范的文本描述供計算機讀取，利于計算機編程實現(xiàn).任務(wù)工作流對傳統(tǒng)的工作流模型做了較多改進，在減少了模型組成元素的同時增強了模型的表述能力，并以合理的方式彌補了理論上的不足.在此基礎(chǔ)上開發(fā)的水下機器人任務(wù)建模與管理系統(tǒng)已有實際使用的實例，其性能穩(wěn)定可靠.隨著機器人任務(wù)流程進一步復(fù)雜化，專用的任務(wù)建模及管理系統(tǒng)必將發(fā)揮愈發(fā)重要的作用.

［1］袁崇義.Petri網(wǎng)原理與應(yīng)用［M］.北京:電子工業(yè)出版社，2005.

［2］鄒海，邊信黔，熊華勝.AUV控制系統(tǒng)規(guī)劃層使命與任務(wù)協(xié)調(diào)方法研究［J］.機器人，2006，28(6):651-655.ZOU Hai，BIAN Xinqian，XIONG Huasheng.Research on the mission and task coordination method of AUV control system at planning layer［J］.Robot，2006，28(6):651-655.

［3］韓麗潔.水下機器人任務(wù)規(guī)劃技術(shù)研究［D］.哈爾濱:哈爾濱工程大學(xué)，2010:36-56.

［4］VAN DER AALST W，VAN HEE K M.Workflow management:models，methods，and systems［M］.Cambridge，USA:The MIT Press，2002.

［5］張亮，姚淑珍.基于Petri網(wǎng)的工作流模式研究［J］.計算機集成制造系統(tǒng)，2006，12(1):54-58.ZHANG Liang，YAO Shuzhen.Research on workflow patterns based on Petri nets［J］.Computer Integrated Manufacturing Systems，2006，12(1):54-58.

［6］王斌，章云，王曉紅.基于Petri網(wǎng)的工作流模式建模及應(yīng)用［J］.計算機工程與應(yīng)用，2008，44(13):238-241.WANG Bin，ZHANG Yun，WANG Xiaohong.Modeling research and application of workflow patterns based on Petri nets［J］.Computer Engineering and Application，2008，44(13):238-241.

［7］VAN DER AALST W M P，TER HOFSTEDE A H M.YAWL:yet another workflow language［R］.Brisbane，Australia:Queensland University of Technology，2003.

［8］陳榮輝，陳新度，陳新.基AND_OR圖深度優(yōu)先搜索的工作流模型驗證［J］.機電工程技術(shù)，2008，37(6):56-71.CHEN Ronghui，CHEN Xindu，CHEN Xin.Workflow model verification based on AND_OR graph depth-first searching［J］.Mechanical ＆ Electrical Engineering Technology，2008，37(6):56-71.

［9］孫玲芳，方錦烽，汲錚，等.YAWL中OR_join任務(wù)使能判斷的改進及形式化說明［J］.江蘇科技大學(xué)學(xué)報:自然科學(xué)版，2007，21(5):64-68.SUN Lingfang，F(xiàn)ANG Jinfeng，JI Zheng，et al.Improvement in enabling of OR-join in yet another workflow language［J］.Journal of Jiangsu University of Science and Technology:Natural Science Edition，2007，21(5):64-68.

［10］曹國榮，譚慶平，吳浩，等.規(guī)范流網(wǎng)中OR-join任務(wù)的語義及使能判定算法［J］.計算機科學(xué)與探索，2010，4(6):542-551.CAO Guorong，TAN Qingping，WU Hao，et al.Semantics and implementation of the OR-join in regular flow nets［J］.Journal of Frontiers of Computer Science and Technology，2010，4(6):542-551.