有向無環(huán)圖技術(shù)在列車自動監(jiān)控系統(tǒng)聯(lián)動模塊中的應(yīng)用實現(xiàn)

周俊輝，孫曉光

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果分析

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

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

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

圖6 實際場景圖示例Fig.6 Example of actual scene

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

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

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

4 結(jié)語

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