基于A*搜索算法的城軌聯(lián)鎖系統(tǒng)仿真研究

張銘瑤 ，向美柱

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756）

計算機聯(lián)鎖系統(tǒng)是城市軌道交通控制系統(tǒng)的重要子系統(tǒng)，它控制著站場進路中信號機、道岔和軌道電路之間的安全關(guān)系，以確保行車安全。隨著城市軌道交通控制系統(tǒng)的智能化發(fā)展，對聯(lián)鎖系統(tǒng)的要求越來越高，聯(lián)鎖軟件中進路搜索方法和效率也成為重要的研究課題?，F(xiàn)有的計算機聯(lián)鎖系統(tǒng)采用的進路搜索方法主要有進路表式搜索方法[1]、帶導(dǎo)向標志的搜索方法[2]、深度優(yōu)先搜索算法[3]、廣度優(yōu)先搜索算法[4]以及二叉樹遍歷[5]等，這些方法相對成熟，但搜索效率卻不高。基于進路表的搜索方法由人工編制聯(lián)鎖表，工作繁復(fù)，容易出錯；基于算法的進路搜索可以用于進路表自動生成工具，幫助自動生成進路表，再人工校對，從而提高進路表生成效率[6]?；趥鹘y(tǒng)算法的搜索多數(shù)情況會遍歷進路上所有分支，在站場復(fù)雜時會搜索到很多擴展節(jié)點，增加了程序執(zhí)行時間。本文將A*搜索算法應(yīng)用到聯(lián)鎖進路搜索過程中，利用啟發(fā)信息指導(dǎo)搜索，使搜索沿著目標方向進行，避免盲目性搜索，從而提高搜索效率。

1 聯(lián)鎖數(shù)據(jù)結(jié)構(gòu)

1.1 城軌站場的圖結(jié)構(gòu)

圖1是西南交通大學(xué)城市軌道交通控制實驗室地鐵1號線的局部信號平面布置圖，軌道電路、信號機和道岔這3類信號設(shè)備是聯(lián)鎖進路上的主要設(shè)備。

如果把信號機、軌道電路和道岔看成一個個設(shè)備節(jié)點，那么根據(jù)它們之間的位置關(guān)系就可以將各設(shè)備節(jié)點連接起來，構(gòu)成設(shè)備節(jié)點圖[7]，拓撲結(jié)構(gòu)圖，如圖2所示。

圖1 157站-西山梁站信號平面布置圖

圖2 拓撲結(jié)構(gòu)圖

拓撲結(jié)構(gòu)圖是由頂點（圖2中用藍色圓表示）和邊（兩個頂點間的連接線）構(gòu)成的圖結(jié)構(gòu)，其中，頂點為3種類型的信號設(shè)備，邊用來表示頂點之間的連接關(guān)系?；谶@種圖結(jié)構(gòu)，可以構(gòu)建站場型數(shù)據(jù)結(jié)構(gòu)來存儲各信號點的信息。

1.2 基于鏈表的站場型數(shù)據(jù)結(jié)構(gòu)

所謂站場型數(shù)據(jù)結(jié)構(gòu)，就是把每個設(shè)備對象看成一個個節(jié)點，然后依據(jù)其在信號平面布置圖的位置來構(gòu)建設(shè)備節(jié)點圖，節(jié)點在圖中的位置與實際站場圖中設(shè)備的位置相對應(yīng)[8]。每個設(shè)備節(jié)點都由兩部分組成：數(shù)據(jù)域（Data標記區(qū)域）和指針域（Prev表示前向指針，Next表示后向指針），具體結(jié)構(gòu)設(shè)計，如圖3所示。

圖3 信號設(shè)備節(jié)點結(jié)構(gòu)

其中，數(shù)據(jù)域用來存放該節(jié)點設(shè)備的數(shù)據(jù)屬性，指針域用來存儲該節(jié)點與相鄰節(jié)點的連接關(guān)系，根據(jù)節(jié)點類型來確定指針數(shù)目。對于信號機和軌道電路，其前方或者后方最多與一個設(shè)備存在連接關(guān)系，因此其前向指針和后向指針各設(shè)置一個即可；對于道岔，其前方或者后方可能與一個或兩個信號設(shè)備有連接，因此需要為其設(shè)計兩個前向指針和兩個后向指針。

為了方便站場中進路的雙向搜索，采用基于雙向鏈表的存儲結(jié)構(gòu)來構(gòu)建站場型數(shù)據(jù)結(jié)構(gòu)。根據(jù)各設(shè)備節(jié)點在信號平面布置圖中的位置關(guān)系將各設(shè)備節(jié)點通過指針連接起來[9]，構(gòu)建如圖4所示的基于雙向鏈表的站場型數(shù)據(jù)結(jié)構(gòu)圖，通過指針可以實現(xiàn)進路的雙向搜索。

圖4 基于雙向鏈表的站場型數(shù)據(jù)結(jié)構(gòu)圖

2 進路搜索算法的設(shè)計

2.1 進路搜索算法比較

目前，應(yīng)用較為廣泛的基于圖的進路搜索算法主要有深度優(yōu)先搜索算法、廣度優(yōu)先搜索算法和啟發(fā)式搜索算法。

（1）深度優(yōu)先搜索算法是一種盲目搜索算法，搜索沿著狀態(tài)空間的某一條單一路徑從起點開始向下搜索，只有當(dāng)搜索到一個沒有后繼節(jié)點的節(jié)點時，才考慮替代路徑。其缺點是，搜索深度可能無限深，或者深度超出可能的深度范圍。為了避免這種情況，使用深度優(yōu)先搜索時往往給定一個深度界限，任何節(jié)點只要達到這個界限，就視為沒有后繼節(jié)點處理。但即使規(guī)定了深度界限，深度優(yōu)先搜索也不能保證一定找到最優(yōu)路徑。

（2）廣度優(yōu)先搜索也是盲目搜索算法，搜索以接近起始節(jié)點的程度為依據(jù)來擴展節(jié)點，搜索是逐層進行的。相比深度優(yōu)先，廣度優(yōu)先搜索可以保證只要存在最優(yōu)路徑就一定可以搜索到。但對于結(jié)構(gòu)復(fù)雜、擴展節(jié)點相對較多的鐵路站場來說，廣度優(yōu)先并不是一種好的選擇。

（3）啟發(fā)式搜索利用啟發(fā)信息來指導(dǎo)搜索過程，不斷地將當(dāng)前節(jié)點的估價值與其他節(jié)點的估價值進行比較，并對待擴展節(jié)點進行排序，然后選擇最有希望的節(jié)點進行擴展。相比于盲目搜索，啟發(fā)式搜索沿著目標方向擴展節(jié)點，能夠減少大量的搜索路徑，使搜索更加高效。本文采用啟發(fā)式搜索算法中的A*搜索算法進行進路搜索。

2.2 A*搜索算法

A*搜索算法利用啟發(fā)函數(shù)來決定待擴展節(jié)點，基本思想如下：

（1）假定存在啟發(fā)函數(shù)f(n)，并且可以通過f(n)確定下一步要擴展的最佳節(jié)點，由于f(n)表示起始節(jié)點到目標節(jié)點的接近程度，因此f(n)越小表示找到的節(jié)點狀態(tài)越好。

（2）選取f(n)最小的節(jié)點作為下一步要擴展的節(jié)點，假設(shè)可以產(chǎn)生這個擴展節(jié)點的全部后繼節(jié)點。

（3）直到下一個待擴展節(jié)點是目標節(jié)點時搜索結(jié)束。

A*搜索算法是一種最佳優(yōu)先搜索算法，其特點在估價函數(shù)的定義上，為此需要重新定義A*搜索算法的估價函數(shù)f*(n)，如式（1）：

其中，f(n)—啟發(fā)函數(shù)，表示從起始節(jié)點經(jīng)由節(jié)點n到達目標節(jié)點的最優(yōu)路徑代價；g(n)—表示從起始節(jié)點到當(dāng)前節(jié)點n的實際代價；h(n)—表示從當(dāng)前節(jié)點n到達目標節(jié)點的最優(yōu)路徑的估計代價值；

f*(n)—f(n)的某個估值，起始節(jié)點經(jīng)由中間節(jié)點n到目標節(jié)點的估計代價；

g*(n)—g(n)的某個估值，起始節(jié)點到當(dāng)前節(jié)點n的最優(yōu)路徑的估計代價；

h*(n)—h(n)的某個估值，從當(dāng)前節(jié)點n到達目標節(jié)點的最優(yōu)路徑的估計代價。

式中，當(dāng)g(n)≥g*(n)時，隨著算法執(zhí)行到深層將會獲得更多的搜索信息，兩者的數(shù)值也會越來越接近，直到兩者數(shù)值相等找到最優(yōu)路徑。如果對A*搜索算法估計函數(shù)中的啟發(fā)函數(shù)h(n)進行限制，使其滿足h*(n)≤h(n)，稱h*(n)是可采納的，此時只要存在最優(yōu)解就一定可以找到該解。

2.3 A*搜索算法在進路搜索中的具體設(shè)計

2.3.1 A*搜索算法搜索策略

A*搜索算法使用open和closed列表來維護狀態(tài)。open表用來記錄已計算出估價值的待考察的節(jié)點，closed表用來記錄已經(jīng)訪問過得節(jié)點。相比盲目搜索，A*搜索算法新增加的一步就是對open表中的節(jié)點狀態(tài)進行排序，排序依據(jù)起始節(jié)點到目標節(jié)點的接近程度的估價值。這樣，每一輪循環(huán)中open列表中都保存的是最有希望的節(jié)點。需要注意的是，每一個狀態(tài)節(jié)點都保留其祖先節(jié)點的信息，這樣做的目的：（1）可以隨時比較當(dāng)前路徑是否是最佳路徑；（2）可以利用這些信息返回最終搜索到的路徑[10-11]。

C#中的List類是一種很好的用來存儲數(shù)組數(shù)據(jù)的列表，該類可以根據(jù)需求來動態(tài)地分配存儲空間，而且List類自帶添加、刪除、查找等方法，使用起來很方便，因此，open表和closed表均使用List類存儲。

2.3.2 啟發(fā)函數(shù)的設(shè)計

A*搜索算法利用啟發(fā)函數(shù)來決定下一步要擴展的節(jié)點，啟發(fā)函數(shù)直接影響搜索效率的，因此，啟發(fā)函數(shù)的設(shè)計在A*搜索算法中至關(guān)重要。

對于城軌鐵路站場，其結(jié)構(gòu)相對簡單，節(jié)點設(shè)備幾十到幾百不等，搜索寬度不大，每個節(jié)點的后繼擴展節(jié)點至多只有兩個，每個節(jié)點設(shè)備在站場中位置相對固定，可以考慮采用歐幾里得距離來計算h(n)的值，但在遇到對向道岔時，還要考慮直股優(yōu)先/彎股優(yōu)先問題，因此給h(n)增加縱向分量，在遇到對向道岔時，會比較分岔處的兩節(jié)點的估價值，來指導(dǎo)搜索方向[12-13]。假設(shè)計算從起始節(jié)點S(xs, ys)到目標節(jié)點E(xe, ye)的估價值，設(shè)搜索過程中當(dāng)前節(jié)點為n，坐標為（xn, yn），則對搜索過程中任意節(jié)點n的估價函數(shù)h(n)如式（2）：

式中， M—權(quán)值系數(shù)。

最終，確定啟發(fā)函數(shù)f(n)，如式（3）：

2.3.3 A*搜索算法流程圖設(shè)計

A*搜索算法的一般步驟為：

（1）把起始節(jié)點S存入open表中，將closed表置空。（2）重復(fù)以下過程，直到找到目標節(jié)點。如果open表為空，則宣告失敗。（3）選取open表中估價值最小的節(jié)點min作為最優(yōu)節(jié)點，并將其存入closed表中。（4）如果min就是目標節(jié)點，那么成功搜索到目標節(jié)點，結(jié)束搜索。（5）如果min不是目標節(jié)點，則擴展其后繼節(jié)點ptemp，并存儲到open表中。（6）計算估價值f(n)，轉(zhuǎn)（2）。

將A*搜索算法應(yīng)用到進路搜索中，實際上是在A*搜索算法的基礎(chǔ)上加入城軌聯(lián)鎖的檢查條件，這里，主要是檢查搜索到的進路是否被占用。擴展節(jié)點時，通過始終端信號機節(jié)點的坐標先后位置來確定搜索方向，并結(jié)合節(jié)點類型和后繼節(jié)點的估價值來確定待擴展節(jié)點?？紤]到搜索到的節(jié)點可能存在被占用的情況，該模塊中設(shè)計了一個存儲關(guān)鍵道岔節(jié)點的容器，若搜索到的節(jié)點被占用，則回退到最新存儲的道岔節(jié)點，沿其另一個子節(jié)點方向繼續(xù)搜索可替代進路。搜索流程，如圖5所示。

3 聯(lián)鎖仿真平臺的功能需求及模塊設(shè)計

搭建城軌聯(lián)鎖仿真平臺，主要功能包括：進路控制、道岔控制、信號機控制和軌道區(qū)段控制等。其中，進路控制是計算機聯(lián)鎖的核心功能，基于A*搜索算法的進路搜索模塊就是實現(xiàn)該功能的關(guān)鍵?？紤]到操作人員可能希望看到A*搜索算法的搜索過程，仿真平臺要求顯示搜索過程中訪問到的節(jié)點。

根據(jù)仿真平臺的功能需要，將聯(lián)鎖功能劃分為3個主要模塊：

（1）站場初始化模塊：存儲各信號設(shè)備節(jié)點初始的相關(guān)信息，并將設(shè)備節(jié)點以鏈表的形式連接起來。（2）進路處理模塊：主要實現(xiàn)進路的選排（進路搜索）、進路鎖閉、進路解鎖以及道岔單獨操縱等功能。（3）命令顯示模塊：主要用于輸出當(dāng)前執(zhí)行的命令、錯誤提示信息以及進路搜索過程中搜索到的節(jié)點信息等。

聯(lián)鎖仿真平臺模塊結(jié)構(gòu)圖，如圖6所示。

4 進路搜索測試

圖5 A*搜索算法流程

圖6 聯(lián)鎖仿真平臺模塊圖

在仿真平臺上進行進路選排測試，順序按下始終端信號機按鈕，檢查聯(lián)鎖條件后可對進路預(yù)選排，對選排成功的進路命令顯示區(qū)給出搜索過程中訪問的所有節(jié)點。經(jīng)多次反復(fù)測試，選排進路過程中搜索到的節(jié)點基本上為進路上的節(jié)點，有效地避免了訪問到過多的擴展節(jié)點，從而提高了進路搜索效率。圖7為測試的兩條進路，選排成功后進路鎖閉，始端信號機開放。

圖7 進路選排測試

5 結(jié)束語

進路搜索是聯(lián)鎖系統(tǒng)的核心模塊，直接影響著進路控制的效率和正確性，因此進路搜索方法的效率至關(guān)重要，本文將A*搜索算法應(yīng)用到進路搜索中，在算法中加入聯(lián)鎖條件的檢查，另外，考慮到搜索到的節(jié)點可能存在被占用情況，在算法中對關(guān)鍵道岔節(jié)點進行存儲，一旦搜索到的節(jié)點被占用，就會回退到關(guān)鍵道岔節(jié)點沿另一方向搜索。經(jīng)過聯(lián)鎖仿真系統(tǒng)上進行驗證，該方法可以快速、準確地搜索到聯(lián)鎖進路，有效減少了搜索過程中擴展節(jié)點數(shù)目，能夠提高進路搜索效率。

[1]朱 怡. 基于計算機聯(lián)鎖的進路表搜索生成系統(tǒng)的設(shè)計與實現(xiàn)[D]. 上海：上海交通大學(xué)，2012.

[2]王文波 ，馬學(xué)霞. 鐵路車站計算機聯(lián)鎖軟件進路搜索算法研究[J]. 鐵路計算機應(yīng)用，2016，25（4）：63-66.

[3]胡 媛，魏宗壽. 采用DFS策略的進路搜索算法研究[J]. 鐵路計算機應(yīng)用，2007，16（9）：4-6.

[4]高利民，李文慧，孫 慧. 雙向廣度搜索算法在聯(lián)鎖進路自動生成中的應(yīng)用[J]. 鐵路計算機應(yīng)用，2007，16（5）：43-45.

[5]陳志穎，董 昱，楊 柳，等. 計算機聯(lián)鎖進路搜索算法的分析與研究[J]. 鐵道通信信號，2007（4）： 4-6.

[6]陳 光，楊 揚. 計算機聯(lián)鎖系統(tǒng)進路表自動生成算法[J].鐵路計算機應(yīng)用，2015，24（5）：5-8.

[7]徐 鑫，陳光武. 計算機聯(lián)鎖軟件設(shè)計及進路搜索算法的研究與應(yīng)用[J]. 鐵路計算機應(yīng)用，2011，20（1）：49-52.

[8]文武臣，王曉明. 計算機聯(lián)鎖的數(shù)據(jù)結(jié)構(gòu)及進路搜索算法[J].重慶工學(xué)院學(xué)報：自然科學(xué)版， 2008（6）：51-53.

[9]吳益芳. 進路搜索數(shù)據(jù)結(jié)構(gòu)與算法研究[J]. 鐵路通信信號，2010，46（8）： 34-36.

[10]蔡自興，徐光祐. 人工智能及其應(yīng)用[M]. 北京： 清華大學(xué)出版社，2010：63-75.

[11]羅 兵，梨花嵩，李敬民. 人工智能原理及應(yīng)用[M]. 北京：機械工業(yè)出版社，2011：170-188.

[12]梁藝凡，譚 麗，馮 挺. A*進路搜索算法的研究與實現(xiàn)[J]. 鐵道標準設(shè)計，2013（2）：117-119+127.

[13]宋 巖. 基于A-Star算法的進路搜索研究[D]. 成都：西南交通大學(xué)， 2014.