A－SMGCS機場場面運行控制的Petri網建模＊

朱新平 韓松臣 湯新民

（南京航空航天大學民航學院 南京 210016）

先進機場場面引導與控制系統（A－SMGCS），屬于飛行區場面運行的一種精細化控制手段，其特點是能在各種氣象條件、交通密度和場面布局下，利用多種傳感技術獲取活動目標的位置信息，并實時進行沖突探測與解脫.多年來，國內外關于場面運行建模多局限于傳統運籌學基礎上的生產調度與控制方法［1－3］，存在可解決問題規模較小，實時性差等缺點，且直接以A－SMGCS運行控制為目標的研究成果較少.文獻［4－5］綜合考慮航空器場面運行和管制員決策行為，采用著色Petri網對場面管制過程進行建模.文獻［6］以航班進離港及地面作業保障為研究對象，分別建立了對應的帶抑制弧高級Petri網模型，以及面向對象的時序Petri網模型.文獻［7］采用著色Petri網對場面管制的動態變化過程進行建模.文獻［8］采用開放Petri網對空中交通管制輔助決策系統進行建模，能夠有效地描述管制系統與外部控制的交互機制.文獻［9］采用普通Petri網建模航空器場面運行過程，依據管制規則和運行約束定義模型的標識控制規范，并基于有限容量庫所設計結構型Petri網控制器.本文采用自頂向下和模塊化的建模方式，實現A－SMGCS場面運行控制的Petri網建模.建模過程分兩步，即先建立場面資源模型，然后結合航空器場面滑行模型，生成最終的場面運行控制Petri網模型.

1 場面運行控制建模要求

A－SMGCS場面運行過程涉及多種資源（如跑道、滑行道、停機坪／機位等），加之航空器對上述資源的并行動態占有，使得整個場面運行過程規模龐大，具有多約束、多目標和隨機不確定性.另一個主要特點是場面資源布局復雜.如果從更高層去抽象，場面運行過程則可看作是由一連串的離散事件（如引導燈關閉或開啟，管制放行等）分開的航空器滑行過程組成的離散事件動態系統（DEDS）.因此，A－SMGCS場面運行過程建模需要考慮場面資源特定的物理布局，全面考慮并抽象出涉及的各種資源，及其與航空器之間的復雜交互關系.

2 場面資源基本網模型

2.1 基本網模型定義與生成規則

定義1 場面資源基本網模型定義為N＝｛P，T，I，O，M｝.其中，庫所集合P 為各典型運行單元，包括跑道、滑行道交叉口和直線段、停機位運行單元；T為所有變遷的集合，表示航空器穿越運行單元邊界活動；任意變遷t∈T具有惟一的輸入或輸出庫所，表示航空器只能從一個單元離開然后進入另一個單元；M為模型標識，表示場面運行狀態.

定義2 運行單元有向圖定義為G＝（E，R）.其中：E為頂點集合；R是邊集合.G中頂點對應于離散得到的各典型運行單元（包括交叉口、直線段、跑道、停機位），可表示為E＝｛e1，e2，…，en｝，n為運行單元總數；對e1，e2∈E，若從e1到e2存在有向邊連接，則表示從運行單元e1到e2存在可供航空器滑行的通道.對運行單元有向圖G采用聯接矩陣表示法，圖的聯接矩陣與圖一一對應.

由有向圖G生成基本網模型N 的規則：（1）建立從G的頂點集E到N的庫所集P的一一映射f，即P＝f（E）；（2）對任一cij而言，若cij＝1，則在庫所pi，pj∈P 之間添加變遷tij，使得pi∈（p）tij，pj∈t（p）ij，并將tij加入集合T中；（3）若某一航空器a的坐標（xa，ya）位于運行單元ei范圍內，則該單元對應庫所標識M（pi）＝1；將M（p），p∈P按照與E對應的順序排成行向量M＝［M（p1），M（p2），…］，便得到基本網模型的標識.

2.2 基本網模型的擴展

場面資源具有固定數量的典型運行單元（如交叉口、直線段、停機坪／機位等），因此可基于模塊化和“自頂向下”的建模思想，將各典型運行單元劃進一步分為小的活動區間，構建對應的精細化模塊，并將基本網模型中的庫所用其對應的精細化模塊替代，得到能描述更多運行細節的場面模型.下面給出各單元精細化模塊的構建思路，以及此模塊替代基本網中庫所的替代規則.

2.2.1 典型運行單元精細化模塊

定義3 交叉口Petri網模型 定義為S＝｛P，T，I，O，C，B，M｝.其中P＝｛ps｝（s為交叉口編號），庫所ps為交叉口單元劃分的活動區間；T＝TI∪TO為航空器活動，其中TI（TO）分別為航空器進入（離開）交叉口活動；將可由停止排燈控制的交叉口活動用可控變遷表示，對應變遷t有控制庫所c∈C 滿足c∈（c）t；I（O）為模型的輸入（輸出）函數；B?（C×T）；M 為模型標識，表示交叉口的占用情況.

變遷集合T＝TI∪TO描述了交叉口模塊與其他模塊的聯系，稱為模塊對應的全局變遷集合.

例1 以圖1a）所示一類典型的交叉口運行單元為例.假設該交叉口所連每個直線路段均允許各類航空器分時雙向運行，也即在不同的時段內允許各類航空器沿某一方向滑行，根據定義3可得其對應的Petri網模型如圖1b）所示.變遷t0，t1對應的位置有單向停止排燈，由于只對進入交叉口起控制作用，因此，僅需為變遷t1添加控制庫所.變遷t2，t3對應的位置有雙向停止排燈，對進出交叉口均起控制作用，因此，需為對應的變遷t2，t3均添加控制庫所.

圖1 滑行道交叉口模塊及其Petri網模型

定義4 直線段Petri網模型 定義為L＝｛P′，T′，I′，O′，C′，B′，M′｝.其中，P′＝｛pm｝，pm為直線段單元劃分的活動區間；變遷集合T′＝TV∪表示航空器直線段活動，且tm，n∈TV（m，n為直線段活動區間編號）表示航空器穿越直線段上劃分的活動區間，t∈表示航空器進入或離開直線段；將可由停止排燈控制的直線段活動用可控變遷表示，對應變遷t有控制庫所c∈C滿足c∈（c）t；其他概念同定義3.

例2 以圖2a）所示直線段運行單元為例，假設該直線路段允許各類航空器分時雙向運行，根據定義4可得其對應的Petri網模型如圖2b）所示.

定義5 跑道Petri網模型 定義為S＝｛P″，T″，I″，O″，C″，B″，M″｝.其中 P″＝｛pr｝，庫所pr表示跑道運行單元；T″＝TI∪TO，變遷集合TI和TO分別表示航空器進入和脫離跑道活動.?t∈TI均為可控變遷，有控制庫所c∈C使得c∈（c）t；t∈TO為不可控變遷；其他概念同定義3.

例3 以圖3a）所示跑道活動單元為例，根據定義5可得其對應的Petri網模型如圖3b）所示.

圖2 滑行道直線段模塊及其Petri網模型

圖3 跑道模塊及其Petri網模型

定義6 停機位Petri網模型 定義為A＝｛P?，T?，I?，O?，C?，B?，M?｝.其中 P″＝｛ph｝∪｝（h為停機位編號），庫所ph表示機位活動區域，表示進出該機位的機坪滑行線交叉口；T?＝TA∪TU為航空器機位活動變遷，其中變遷t∈TU表示航空器進入或離開機位交叉口，t′∈TA表示航空器進入或離開機位且為可控變遷，有控制庫所c∈C滿足c∈（c）t′，其他概念同定義3.

TU描述了模塊與外界的交互，稱為模塊的全局變遷集合，TA為模塊的局部變遷集合.

例4 典型的機位運行單元如圖4a）所示，包括進出機位交叉口和機位活動區域，根據定義6可得其對應的Petri網模型如圖4b）所示.

圖4 機坪停機位模塊及其Petri網模型

2.2.2 基本網模型的替代規則 記上節各單元精細化模塊為 WP＝｛Pk，Tk，Ik，Ok，Ck，Bk，Mk｝，將基本網N＝｛P，T，I，O，M｝中的庫所用對應的WP替代，可得到更能描述運行細節的場面模型，記為 Nt＝｛Pt，Tt，It，Ot，Ct，Bt，Mt｝，稱之為場面資源精細化Petri網模型.其中：（1）Pt＝∪Pk，Tt＝（∪）∪T（其中為各替代模塊的局部變遷集合）；（2）對?p∈Pt，?t∈Tt，It（p，t）＝Ik（p，t），Ot（p，t）＝Ok（p，t）；（3）若t∈Tt在其對應的模型中滿足（c）t＝｛c｝，則有（c，t）?Bt，且c∈Ct；（4）對?p∈Pt，Mt（p）＝Mk（pi），其中pk∈Pk.

上述規則中，規則（1）將基本網模型中的每一個庫所都用對應的精細化模塊替代，并將基本網中的變遷進行擴展，增加了各模塊中所包含的局部變遷；規則（2）中Nt中輸入和輸出函數均來自各精細化模塊的輸入輸出函數；規則（3）中添加精細化模塊的控制庫所及其連接關系；規則（4）對場面精細化模型中的標識（也即航空器運行狀態）依據精細化模塊來確定.

3 航空器建模和場面最終模型

用著色托肯建模每一架航空器a∈A，其顏色為＜rr（a）＞.其中，rr（a）表示該航空器從當前位置開始的后續滑行路徑（用庫所序列表示）.如M（ps）＝＜rr（a）＞表明航空器當前處于ps對應運行區間，托肯顏色rr（a）代表航空器a從ps開始將會通過的運行區間，由此則可描述此航空器的運行趨勢.

定義航空器場面滑行計劃集合為W＝｛π1，…，πh｝，其中πi＝rr（a）為航空器的后續滑行路徑.將資源精細化模型Nt與W 相結合，可得到場面運行最終模型：

其中，相關元素的確定方法如下.

1）著色屬性ζ可由算法Computζ（Nt，W）確定.

2）對?（pi，TIm）∈It，（pi，Tim）＝ID，其中ID為單位函數，對托肯顏色不做任何改變；否則（pi，Tim）＝0.

3）對?（pm，Tim）∈Ot，（pm，Tim）＝UP，其中：UP 為函數，將托肯顏色由＜rr（a）＞變為＜rr′（a）＞（rr′（a）為從rr（a）中去掉其第一個元素后的剩余庫所序列；否則（pm，Tim）＝0.

4）顏色集合Ω＝｛ζ（x）｜x∈Pt∪Tt｝.

算法.Computζ（Nt，W）.

輸入.Nt＝｛Pt，Nt，It，Ot，Ct，Bt，Mt｝；

W＝｛π1，…，πh｝，πi＝rr（a）.

目的.為每一個元素q∈Pt∪Tt計算其著色集合C（q）.

步驟1 對πi＝rr（a），對?pi∈rr（a），將顏色屬性πi加入到C（pi）中.

步驟2 對pi的后向變遷tim∈，將顏色屬性πi加入到C（tim）中.

步驟3 對其他πi繼續上述步驟.

算法復雜度分析：場面運行模型的構造過程，其主要工作在于為各元素計算著色屬性.實際上，算法Computζ（Nt，W）的復雜度很低，為O（h×（｜Pt｜＋｜Tt｜）），屬于多項式算法，其中h為場面運行的航空器架數，｜·｜為集合·中元素個數.

4 建模實例

以首都機場T3C航站樓東側飛行區的一部分為例，該部分的場面資源構成如圖5所示，主要資源包括機坪停機位301至312的活動區Z1至Z13，滑行道交叉口Z14至Z16，Z24至Z26，以及Z19；滑行道直線段 Z17，Z18，Z20至 Z23；跑道運行區Z27；場面停止排燈b0至b10，其中b0為雙向停止排燈，其余為單向停止排燈.

圖5 首都機場T3C航站樓飛行區一部分場面資源構成

利用由運行單元有向圖G生成基本網模型N的規則，得到基本網模型如圖6所示.其中，每個庫所pj對應一個運行單元zj，且相鄰庫所間存在2個活動變遷，描述航空器的不同運行方向.然后根據替代規則，將基本網模型中的庫所用精細化模塊替代，得到場面資源精細化模型，例如可將圖7基本網模型中的庫所p17用對應的精細化模塊替代.最后，采用著色托肯建模航空器，并得到最終運行模型.若Z17中航空器a0的滑行路徑為π0＝rr（a0）＝（，p16，p15，p10），Z23中航空器a1的滑行路徑為π1＝rr（a1）＝（p23，p26，p27），則模型的標識）＝＜π0＞，（p23）＝＜π1＞描述了場面運行狀態，并可由算法Computζ（Nt，W）確定航空器滑行路徑上各庫所和變遷的著色屬性如下：C（）＝｛π0｝，j＝1，2；C（pi）＝｛π0｝，i＝16，15，10；C（）＝｛π0｝；C（t17，16）＝｛π0｝；C（t16，15）＝｛π0｝；C（t15，10）＝｛π0｝；C（pi）＝｛π1｝，i＝23，26，27；C（t23，26）＝｛π1｝，C（t26，27）＝｛π1｝.在場面運行控制Petri網模型中，通過為其中的控制庫所決策控制律，并進一步給出對應位置停止排燈切換指令，即可控制航空器場面滑行并避免沖突.

圖6 圖5所示飛行區場面運行的Petri網模型

5 結束語

提出一種基于Petri網的A－SMGCS場面運行控制建模方法.該方法有以下優點：（1）基于典型運行單元劃分建立的有向圖模型，從全局視角清晰、直觀地反映了場面資源組成及關聯；（2）采用Petri網間接建模場面運行過程，既保證了模型總體結構的清晰性，又達到了將場面復雜動態過程轉換為具有精確語義的Petri網模型的目的，降低了建模過程的復雜度和調整的難度，并避免了信息描述不清、考慮不全面等原因而帶來的控制軟件設計周期延長；（3）引入控制庫所體現了外界對場面運行過程的控制作用，可消除航空器資源占用沖突.借助于所建立的模型，可進一步對場面運行過程展開邏輯分析與控制綜合研究.

［1］Visser H，Roling P.Optimal airport surface traffic planning using mixed integer linear programming［C］／／Proc.of AIAA＇s 3rd Annual Aviation Technology，Integration，and Operations（AtiO）Technology Conference.Denver，CO，2003：17－19.

［2］Capozzi B J，DiFelici J.Towards automated airport surface traffic control：potential benefits and feasibility［C］／／Proc.of AIAA Guidance，Navigation，and Control Conference and Exhibit.Providence，RI，2004：1－16.

［3］Gillian C，Arthur R，Receding Horizon.Iterative optimization of taxiway routing and runway scheduling［C］／／Proc.of AIAA Guidance，Navigation，and Control Conference.Chicago，Illinois，2009：1－14.

［4］Werther B.Colored Petri net based modeling of airport control processes［C］／／Proc.of International conference on Computational Intelligence for Modelling，Control and Automation，CIMCA.Sydney，2006：1－6.

［5］Werther B，Moehlenbrink C，Rudolph M.Colored Petri net based formal airport control model for simulation and analysis of airport control processes［J］.Lecture Notes in Computer Science 4561，2007：1 027－1 036.

［6］秦 瑛.機場終端區作業的離散事件系統建模與優化［D］.北京：中國民用航空學院空管學院，2006.

［7］Demael J J，Levis A H.On the generation of a variable structure airport surface traffic control system［C］／／Proc.Of IEEE International Symposium on Intelligent Control.Tallinn，IEEE Press，1989：74－81.

［8］黃圣國，肖 靖.基于Petri網的空中交通管制輔助決策系統［J］.南京航空航天大學學報，2000，32（4）：206－211.

［9］Tang Xinmin，Zhu Xinping，Han Songchen.Petri net controller synthesis for advanced surface movement guidance and control system ［C］／／Proc.of IEEE International conference on Information and Automation.USA：IEEE Press，2009：483－488.