周俊輝，孫曉光

（通號(hào)城市軌道交通技術(shù)有限公司，北京 100070）

軌道交通運(yùn)營(yíng)模式中的互聯(lián)互通全自動(dòng)駕駛系統(tǒng)（FAO）是一種將列車駕駛員執(zhí)行的工作，完全自動(dòng)化的、高度集中的控制系統(tǒng)所替代的列車運(yùn)行模式。其中列車自動(dòng)監(jiān)控系統(tǒng)直接與調(diào)度員交互，其自動(dòng)化程度在列車運(yùn)行過程中起著關(guān)鍵的作用。列車自動(dòng)監(jiān)控系統(tǒng)可以實(shí)現(xiàn)列車全自動(dòng)駕駛系統(tǒng)中線路監(jiān)控、列車監(jiān)控、時(shí)刻表管理、現(xiàn)地控制、模擬培訓(xùn)和維護(hù)支持等功能。每一個(gè)功能都包含眾多的需求點(diǎn)，這些不同的需求點(diǎn)又能組成不同的運(yùn)營(yíng)場(chǎng)景。所以每一個(gè)場(chǎng)景都是由一系列關(guān)聯(lián)的順序功能節(jié)點(diǎn)組合完成的。為保障系統(tǒng)的正常運(yùn)轉(zhuǎn)，確保乘客和工作人員的生命安全，聯(lián)動(dòng)模塊將這一系列關(guān)聯(lián)的順序執(zhí)行功能節(jié)點(diǎn)劃分為各不相同的職責(zé)范圍，但是他們之間存在著緊密和必要的聯(lián)系，一個(gè)功能節(jié)點(diǎn)的變化往往需要其他功能節(jié)點(diǎn)做出調(diào)整或以其他功能節(jié)點(diǎn)的完成作為輸入。尤其是系統(tǒng)運(yùn)營(yíng)過程中經(jīng)常性的人工操作（如每天早間上電、列車喚醒、列車出入庫等），列車運(yùn)行過程中的情況（如通信車在軌道上運(yùn)行的發(fā)車停車折返、列車清客、車輛段內(nèi)轉(zhuǎn)線等），更有各種各樣的突發(fā)事件（如車輛火災(zāi)、運(yùn)行狀態(tài)丟失、車輛欠標(biāo)過大等）。目前各鐵路運(yùn)營(yíng)單位一方面通過應(yīng)急預(yù)案作為有效處置突發(fā)事件的基本手段。另一方面則通過借鑒學(xué)習(xí)或者系統(tǒng)經(jīng)驗(yàn)制定需求，以需求方案來限定設(shè)備廠商該怎么做。不論哪一方面，都是以文本為主要形式，這些文本規(guī)定了事件發(fā)生時(shí)處置的方法和步驟，明確各個(gè)模塊的職責(zé)，使各模塊在事件發(fā)生后按照文本科學(xué)高效的協(xié)調(diào)工作。但是不論是文本預(yù)案還是文本系統(tǒng)需求，在使用過程中存在很大的缺陷，需要相關(guān)人員熟悉文本的具體內(nèi)容。而文本本身通常又不夠直觀，不容易記憶，在處理過程中瀏覽不方便，不能快速提取有效元素，無法讓現(xiàn)場(chǎng)人員明確自動(dòng)運(yùn)行是否正常，所有問題完全依賴于現(xiàn)場(chǎng)人員對(duì)文本的把握程度。有向無環(huán)圖技術(shù)可以在一定程度上解決聯(lián)動(dòng)模塊將文本數(shù)字化的難題。

1 有向無環(huán)圖技術(shù)分析

有向無環(huán)圖技術(shù)（DAG），廣泛用于數(shù)據(jù)庫建模和工程設(shè)計(jì)等領(lǐng)域。例如工程設(shè)計(jì)上用DAG 可以清晰的表達(dá)工程的進(jìn)度等。

有向指的是有方向，準(zhǔn)確的說應(yīng)該是同一方向。無環(huán)則指構(gòu)不成閉環(huán)。要想完成當(dāng)前頂點(diǎn)，必須驗(yàn)證前面的頂點(diǎn)完成，這種策略最終構(gòu)成一種拓?fù)錁錉罱Y(jié)構(gòu)，能夠極大地提高擴(kuò)展性。之所以不允許有環(huán)的出現(xiàn)，是因?yàn)镈AG 可以保證各個(gè)頂點(diǎn)之間的順序，通過頂點(diǎn)的屬性知道本圖中的所有路徑。如果有環(huán)出現(xiàn)容易導(dǎo)致系統(tǒng)紊亂，進(jìn)入死循環(huán)。

有向圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，圖中某個(gè)頂點(diǎn)與其他頂點(diǎn)的直連邊條數(shù)稱為該頂點(diǎn)的度。有向圖中，指向其他頂點(diǎn)的邊稱為出度，出度表示由一個(gè)頂點(diǎn)出發(fā)的邊的總數(shù)。被其他頂點(diǎn)指向的邊稱為入度，入度表示指向一個(gè)頂點(diǎn)的邊的總數(shù)。正是因?yàn)閳D可以有多個(gè)出度和入度，可以同時(shí)處理多個(gè)出度連接的頂點(diǎn)。所以，有向無環(huán)圖流向清晰，可拓展性強(qiáng)。

2 FAO中有向無環(huán)圖技術(shù)應(yīng)用實(shí)現(xiàn)

軌道交通FAO 系統(tǒng)列車自動(dòng)監(jiān)控系統(tǒng)中的聯(lián)動(dòng)模塊將不同的運(yùn)營(yíng)場(chǎng)景進(jìn)行提煉，可以得到一系列不同的隨事件演化過程而順序執(zhí)行的操作程序，該程序可以提示相關(guān)人員何時(shí)應(yīng)該做什么，怎么做。每個(gè)操作程序?qū)?yīng)圖中的一個(gè)頂點(diǎn)，一系列的操作程序構(gòu)成一個(gè)完整的有向無環(huán)圖。而演化順序則表明了該有向無環(huán)圖的鄰接關(guān)系。不同的有向無環(huán)圖共同實(shí)現(xiàn)了特定的場(chǎng)景。有向無環(huán)圖的應(yīng)用是列車自動(dòng)監(jiān)控系統(tǒng)聯(lián)動(dòng)模塊的邏輯處理和執(zhí)行平臺(tái)，是聯(lián)動(dòng)模塊的重要組成部分。

2.1 有向無環(huán)圖頂點(diǎn)和邊的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

有向無環(huán)圖頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如圖1 所示，一個(gè)頂點(diǎn)表示一個(gè)操作程序的一個(gè)步驟，其數(shù)據(jù)結(jié)構(gòu)定義了一個(gè)可用于查找的唯一識(shí)別號(hào)和唯一名稱。超時(shí)時(shí)間設(shè)置決定當(dāng)前頂點(diǎn)步驟在條件不滿足需要繼續(xù)輪詢時(shí)停止輪詢需要消耗的時(shí)間。一個(gè)頂點(diǎn)步驟同時(shí)也可以是一個(gè)只有一個(gè)頂點(diǎn)的有向無環(huán)圖，所以要求一個(gè)頂點(diǎn)步驟有輸入條件，也有結(jié)束條件，用xml 格式的字符串實(shí)現(xiàn)該需求。頂點(diǎn)步驟類型分為可選類型和不可選類型，用于區(qū)分每條分支的路徑。當(dāng)父頂點(diǎn)輸出互斥的結(jié)果時(shí)，需要明確分支的流向，保證互斥路徑的執(zhí)行。當(dāng)存在分支路徑時(shí)，頂點(diǎn)是否默認(rèn)步驟決定了該圖正常狀態(tài)時(shí)的關(guān)鍵路徑。

有向無環(huán)圖的邊的數(shù)據(jù)結(jié)構(gòu)是由當(dāng)前頂點(diǎn)及其父頂點(diǎn)的鄰接關(guān)系組成的map 表。

2.2 有向無環(huán)圖的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

圖1 頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)Fig.1 Vertex data structure

一張有向無環(huán)圖對(duì)應(yīng)一個(gè)完整的處置預(yù)案，其數(shù)據(jù)結(jié)構(gòu)用于描述該有向無環(huán)圖的詳細(xì)內(nèi)容，如圖2所示。數(shù)據(jù)結(jié)構(gòu)中同樣有用于查找的唯一識(shí)別號(hào)和唯一名稱。為了區(qū)別不同的觸發(fā)情況，加入圖序號(hào)來處理。審核狀態(tài)表示如果有向無環(huán)圖尚處于未審核通過階段，則該圖暫為不可執(zhí)行的處置預(yù)案。自動(dòng)類型分為全自動(dòng)、半自動(dòng)和手動(dòng)3 種類型。有向無環(huán)圖全自動(dòng)執(zhí)行是實(shí)時(shí)觸發(fā)該圖后，立即按照鄰接關(guān)系順序執(zhí)行每一個(gè)頂點(diǎn)。有向無環(huán)圖手動(dòng)執(zhí)行是觸發(fā)該圖后，圖的執(zhí)行以及每個(gè)頂點(diǎn)步驟的執(zhí)行都需要人工參與。有向無環(huán)圖半自動(dòng)執(zhí)行指的是觸發(fā)該圖后，人工決定該圖是否執(zhí)行，如果人工執(zhí)行后其頂點(diǎn)步驟由系統(tǒng)自動(dòng)運(yùn)行（例如車輛火災(zāi)可能存在誤報(bào)，需要人工確認(rèn)），之后決定是否響應(yīng)該圖所有頂點(diǎn)步驟。有向無環(huán)圖執(zhí)行后即從根頂點(diǎn)開始判斷每個(gè)頂點(diǎn)的輸入條件是否滿足，輸出條件是否滿足。

圖2 圖數(shù)據(jù)結(jié)構(gòu)Fig.2 Graph data structure

2.3 有向無環(huán)圖應(yīng)用實(shí)現(xiàn)

實(shí)際運(yùn)營(yíng)場(chǎng)景的有向無環(huán)圖利用QtGui 繪制相應(yīng)的頂點(diǎn)和邊，通過外層容器的信號(hào)槽實(shí)現(xiàn)頂點(diǎn)的點(diǎn)擊、拖拽和連接。

有向無環(huán)圖繪制完畢后需實(shí)時(shí)加載所有頂點(diǎn)和所有邊，檢查該有向無環(huán)圖根頂點(diǎn)是否唯一，結(jié)束頂點(diǎn)是否唯一，是否有環(huán)。

如何監(jiān)測(cè)有向無環(huán)圖是否有環(huán)，這個(gè)依賴于DFS 深度優(yōu)先搜索算法。遍歷有向無環(huán)圖時(shí)如果有頂點(diǎn)被第二次訪問到，那么該圖有環(huán)，不是DAG。實(shí)現(xiàn)流程如圖3 所示。

圖3 檢測(cè)是否有環(huán)Fig.3 Check whether there is ring

有向無環(huán)圖的狀態(tài)轉(zhuǎn)換如圖4 所示。實(shí)際場(chǎng)景中每一個(gè)頂點(diǎn)都可能是一個(gè)獨(dú)立的運(yùn)營(yíng)場(chǎng)景，故設(shè)計(jì)時(shí)每個(gè)頂點(diǎn)都有輸入輸出條件，每個(gè)頂點(diǎn)的狀態(tài)轉(zhuǎn)換和整圖的狀態(tài)轉(zhuǎn)換機(jī)制相同。所以在具體實(shí)現(xiàn)中，單個(gè)頂點(diǎn)有向無環(huán)圖的情形與多頂點(diǎn)圖的實(shí)現(xiàn)一致。

圖4 狀態(tài)圖Fig.4 State diagram

聯(lián)動(dòng)模塊通過設(shè)置同一個(gè)觸發(fā)條件會(huì)觸發(fā)同一張圖，會(huì)在這張圖上多次更改狀態(tài)記錄。這種情況與實(shí)際不符，故實(shí)現(xiàn)有向無環(huán)圖時(shí)，首先檢查實(shí)時(shí)緩存中是否存在該圖，若存在且狀態(tài)已完成則清理緩存重新加載。此時(shí)的圖為不同時(shí)機(jī)觸發(fā)的同一張圖，故設(shè)置圖序號(hào)來區(qū)分這種情況。圖啟動(dòng)后先加載圖序號(hào)，確保圖序號(hào)從1 開始，若圖序號(hào)已存在，則首先獲取當(dāng)前圖的最大序號(hào)，加1 后得到實(shí)時(shí)觸發(fā)圖的序號(hào)。

根據(jù)實(shí)際運(yùn)營(yíng)場(chǎng)景繪制有向無環(huán)圖時(shí)存在一個(gè)頂點(diǎn)步驟的完成狀態(tài)不同時(shí)流向的分支不同，且另外的分支不執(zhí)行也不影響其他頂點(diǎn)的狀態(tài)。故實(shí)現(xiàn)有向無環(huán)圖時(shí)加入頂點(diǎn)類型，用于區(qū)分有分支路徑的情況。當(dāng)頂點(diǎn)響應(yīng)后首先得確認(rèn)頂點(diǎn)是否是分支頂點(diǎn)，根據(jù)響應(yīng)類型決定所走路徑，并屏蔽掉另外的分支路徑。

2.4 數(shù)據(jù)流設(shè)計(jì)

設(shè)計(jì)數(shù)據(jù)流如圖5 所示，狀態(tài)實(shí)時(shí)監(jiān)測(cè)模塊持續(xù)不間斷的監(jiān)視從各個(gè)接口獲取的信息，包括表示信息、列車信息、計(jì)劃信息和報(bào)警信息等。當(dāng)滿足頂點(diǎn)的觸發(fā)條件后通過相應(yīng)的狀態(tài)源處理器檢查數(shù)據(jù)，通過圖處理器觸發(fā)有向無環(huán)圖，并實(shí)時(shí)更新有向無環(huán)圖和頂點(diǎn)的狀態(tài)變化，最終在圖執(zhí)行界面上提示相關(guān)處置人員當(dāng)前處在什么階段，何時(shí)該做什么，該怎么做。圖處理器同時(shí)將實(shí)時(shí)變化的狀態(tài)通過數(shù)據(jù)庫處理模塊存儲(chǔ)于數(shù)據(jù)庫中。

3 結(jié)果分析

根據(jù)列車監(jiān)控系統(tǒng)聯(lián)動(dòng)模塊實(shí)際場(chǎng)景繪制的有向無環(huán)圖示例如圖6 所示，表示按照出庫計(jì)劃喚醒列車出庫。

按照休眠喚醒計(jì)劃，聯(lián)動(dòng)模塊自動(dòng)觸發(fā)該圖，且無需人工干預(yù)，觸發(fā)后各頂點(diǎn)自動(dòng)執(zhí)行。

喚醒1 車作為一個(gè)頂點(diǎn)，本身就會(huì)經(jīng)過準(zhǔn)備、開始、接收、暫停、恢復(fù)、中止、完成和超時(shí)等狀態(tài)的遷移。所以喚醒1 車頂點(diǎn)可以作為單獨(dú)的一個(gè)頂點(diǎn)的圖存在。

圖6 實(shí)際場(chǎng)景圖示例Fig.6 Example of actual scene

實(shí)際運(yùn)營(yíng)場(chǎng)景中通常會(huì)有七八輛備用車，本圖例僅作參考。因?yàn)閭溆密嚨拇嬖?，頂點(diǎn)設(shè)計(jì)時(shí)，喚醒1 車的輸出需要進(jìn)行分支，成功直接開庫門，失敗喚醒備車。這兩個(gè)分支路徑是互斥的。所以喚醒1 車需要在觸發(fā)并下達(dá)列車喚醒命令后，設(shè)置一個(gè)合理的超時(shí)時(shí)間。在超時(shí)時(shí)間內(nèi)未收到回執(zhí)，則認(rèn)為失敗，進(jìn)行喚醒備車。由于喚醒備車和開庫門是喚醒1 車的分支子頂點(diǎn)，所以需將這兩個(gè)頂點(diǎn)設(shè)為可選頂點(diǎn)，且開庫門為默認(rèn)頂點(diǎn)。

圖6 中喚醒1 車狀態(tài)為超時(shí)狀態(tài)，進(jìn)入喚醒備車的分支。喚醒2 車狀態(tài)為成功狀態(tài)，開庫門頂點(diǎn)進(jìn)入開始狀態(tài)。當(dāng)開庫門以中止、超時(shí)或完成狀態(tài)結(jié)束后，整個(gè)圖的狀態(tài)即結(jié)束。

聯(lián)動(dòng)模塊可以查看有向無環(huán)圖詳細(xì)的描述內(nèi)容，也可以查看各頂點(diǎn)的詳細(xì)內(nèi)容。運(yùn)行過程中還可以隨時(shí)查看頂點(diǎn)當(dāng)前狀態(tài)的觸發(fā)條件信息，哪些條件滿足，哪些條件不滿足，便于相關(guān)人員進(jìn)行人工干預(yù)處理。

4 結(jié)語

實(shí)現(xiàn)有向無環(huán)圖的關(guān)鍵前提是初期識(shí)別并抽象聯(lián)動(dòng)預(yù)案，而有向無環(huán)圖技術(shù)作為聯(lián)動(dòng)模塊的有力補(bǔ)充，能高效便捷的實(shí)現(xiàn)系統(tǒng)運(yùn)行，它配置化程度高，可拓展性高，便于不同線路的移植和實(shí)際線路的更新。值得注意的是，DAG 并不是一個(gè)新的發(fā)現(xiàn)，而是一個(gè)古老的問題解決機(jī)制。但同時(shí)也是年輕的數(shù)據(jù)結(jié)構(gòu)。隨著技術(shù)發(fā)展，有向無環(huán)圖技術(shù)將會(huì)在今后的項(xiàng)目應(yīng)用中更廣泛更普及。