一種基于圖論的機(jī)場(chǎng)空域無人機(jī)流量控制方法

崔愷，曾國(guó)奇，林偉，全權(quán)

（1.北京航空航天大學(xué) 電子信息工程學(xué)院，北京100083； 2.北京航空航天大學(xué) 無人系統(tǒng)研究院，北京100083；3.北京航空航天大學(xué) 杭州創(chuàng)新研究院，杭州310051； 4.北京航空航天大學(xué) 自動(dòng)化科學(xué)與電氣工程學(xué)院，北京100083）

近年來，國(guó)內(nèi)外快遞業(yè)務(wù)量劇增與人力成本的飆升，無人配送技術(shù)具有廣闊的應(yīng)用前景。無人機(jī)配送直線距離最短、運(yùn)輸效率高，對(duì)復(fù)雜服務(wù)場(chǎng)景有較好的適應(yīng)能力，無人機(jī)投遞包裹的能力已經(jīng)在多次實(shí)驗(yàn)中得到了證實(shí)［1］，因此用無人機(jī)解決“最后一公里”的問題，是未來的有效選擇［2-3］。

美國(guó)是無人機(jī)物流的先驅(qū)陣地，無人機(jī)物流始于美國(guó)亞馬遜公司，2013年亞馬遜公司公布無人機(jī)計(jì)劃Prime Air，UPS、谷歌等公司與美國(guó)郵政等對(duì)無人機(jī)物流進(jìn)行了大量研究與測(cè)試；歐洲各國(guó)發(fā)展迅速，自2013年起不斷進(jìn)行相關(guān)布局與測(cè)試。亞馬遜公司在英國(guó)完成了從倉庫直接向用戶家中傳遞產(chǎn)品的測(cè)試［4］，DHL使用其Parcelcopter無人機(jī)交付緊急醫(yī)療用品［5］，瑞士郵政的無人機(jī)為醫(yī)院提供實(shí)驗(yàn)室樣本等［6］。

中國(guó)無人機(jī)物流從追趕到領(lǐng)跑，2013年順豐進(jìn)行無人機(jī)測(cè)試并進(jìn)入試運(yùn)行，2017年起順豐與京東相繼獲得空域批文［7-8］，蘇寧、中通等企業(yè)實(shí)現(xiàn)了物流無人機(jī)的試飛以至首次派送［9］。

無人機(jī)應(yīng)用于城市物流前景廣闊，能夠有效處理城市物流“最后一公里”難題。城市內(nèi)物流要求無人機(jī)具有更高的靈活性與安全性，多旋翼無人機(jī)與垂直起降無人機(jī)均可實(shí)現(xiàn)懸停與垂直起降，機(jī)動(dòng)性能優(yōu)異，轉(zhuǎn)向靈活，對(duì)機(jī)場(chǎng)要求較低，適合中短距物流配送，是城市物流的極佳選擇。

當(dāng)前中國(guó)市面上的無人機(jī)機(jī)場(chǎng)，如一飛智控的“梧桐”自動(dòng)化無人機(jī)機(jī)場(chǎng)、訊蟻的無人樞紐站RH1與順豐無人機(jī)快遞接駁機(jī)場(chǎng)等［10］，均能實(shí)現(xiàn)單次單架無人機(jī)的起降。但上述無人機(jī)機(jī)場(chǎng)實(shí)際上只是無人機(jī)的自動(dòng)接收設(shè)備，前一架無人機(jī)離開機(jī)場(chǎng)之后，后續(xù)無人機(jī)才能降落。在真實(shí)的物流場(chǎng)景中，“機(jī)場(chǎng)”將是物資庫存區(qū)、中轉(zhuǎn)站或配送站，需具有同時(shí)起降多架無人機(jī)的能力。在機(jī)場(chǎng)區(qū)域無人機(jī)密度較大時(shí)，需要設(shè)計(jì)應(yīng)用于城市物流場(chǎng)景的機(jī)場(chǎng)與合理的流量控制方法，保證無人機(jī)在機(jī)場(chǎng)區(qū)域的飛行安全并提高通行效率。

文獻(xiàn)［11］提出了一種單入口單出口、航路交叉、多停機(jī)坪的機(jī)場(chǎng)模型。機(jī)場(chǎng)中使用無約束的停機(jī)坪基本模型［12］，即任意一架無人機(jī)可以進(jìn)入任意一座停機(jī)坪，機(jī)場(chǎng)中各停機(jī)坪面積相等。針對(duì)該類機(jī)場(chǎng)模型提出了一種保證安全、效率優(yōu)先的無人機(jī)機(jī)場(chǎng)流量控制方法，實(shí)現(xiàn)了無人機(jī)在機(jī)場(chǎng)的安全有序飛行。但該方法對(duì)無人機(jī)的控制精度要求較高，實(shí)際情況下可能因干擾因素影響存在安全隱患，同時(shí)文獻(xiàn)［11］沒有考慮需要緊急降落的無人機(jī)的調(diào)度問題。

本文是對(duì)筆者課題組研究成果［11］的改進(jìn)和拓展。在文獻(xiàn)［11］的基礎(chǔ)上提出一種基于圖論安全優(yōu)先的機(jī)場(chǎng)空域流量控制方法，可實(shí)現(xiàn)同時(shí)段多架次垂直起降無人機(jī)的起降［13］，并為需要緊急降落的無人機(jī)設(shè)計(jì)了降落通道和流量控制方法。通過測(cè)試機(jī)場(chǎng)運(yùn)行容量與機(jī)場(chǎng)內(nèi)飛行無人機(jī)之間最小距離評(píng)估了所提方法的有效性。

1 問題描述

對(duì)一個(gè)可同時(shí)停放多架垂直起降無人機(jī)的機(jī)場(chǎng)，若任意時(shí)刻只有一架無人機(jī)起飛或降落，只需使無人機(jī)從機(jī)場(chǎng)入口沿直線飛行至停機(jī)坪上方或從停機(jī)坪上方沿直線飛行至機(jī)場(chǎng)出口。但若有一架以上無人機(jī)在機(jī)場(chǎng)中飛行，則存在無人機(jī)相撞的風(fēng)險(xiǎn)。因而需要預(yù)先設(shè)置可用航道，令無人機(jī)在機(jī)場(chǎng)中沿規(guī)劃出的航道飛行，并設(shè)計(jì)無人機(jī)模型，模擬無人機(jī)在機(jī)場(chǎng)航路的飛行。

1.1 機(jī)場(chǎng)航路圖模型設(shè)計(jì)

本文涉及到的無人機(jī)起降方式為垂直起降，機(jī)場(chǎng)航路中確定存在節(jié)點(diǎn)包括出口、入口、停機(jī)坪節(jié)點(diǎn)與停機(jī)坪上方節(jié)點(diǎn)。僅靠上述節(jié)點(diǎn)的連接來組成機(jī)場(chǎng)內(nèi)部航路無法保證無人機(jī)的飛行安全，因此需要設(shè)置一部分節(jié)點(diǎn)作為連接停機(jī)坪上方節(jié)點(diǎn)與出入口的中間節(jié)點(diǎn)。

機(jī)場(chǎng)區(qū)域整體呈矩形，每塊停機(jī)坪區(qū)域?yàn)檎叫危瑹o人機(jī)停放于停機(jī)坪中心。設(shè)機(jī)場(chǎng)有6個(gè)停機(jī)坪，機(jī)場(chǎng)航路圖設(shè)計(jì)如圖1所示［11］。機(jī)場(chǎng)只有1個(gè)入口、1個(gè)出口，機(jī)場(chǎng)內(nèi)有多個(gè)停機(jī)坪，且航路交叉。圖1中實(shí)心點(diǎn)表示機(jī)場(chǎng)節(jié)點(diǎn)；空心點(diǎn)表示停機(jī)坪與停機(jī)坪上方節(jié)點(diǎn)；實(shí)線表示機(jī)場(chǎng)中的航路；虛線表示停機(jī)坪區(qū)域的航路。

圖1 機(jī)場(chǎng)航路示意圖［11］Fig.1 Schematic diagram of airfield route［11］

上述機(jī)場(chǎng)航路圖可視為由線連接的點(diǎn)集，可采用圖論模型［14］來表示。用無向圖Γ＝（N，E）表示機(jī)場(chǎng)航路圖模型，N表示機(jī)場(chǎng)所有節(jié)點(diǎn)，E?N2表示N中各節(jié)點(diǎn)之間是否有路徑直接相連，即表示機(jī)場(chǎng)所有航段。

機(jī)場(chǎng)節(jié)點(diǎn)數(shù)量為nN，機(jī)場(chǎng)航段數(shù)量為nE，則圖Γ節(jié)點(diǎn)可枚舉表示為，其中1＜nN∈Z＋；圖Γ航段可表示為，其中1＜nE∈Z＋。任意航段均可以其兩側(cè)節(jié)點(diǎn)表示為E（j）＝｛Ns（j），Ne（j）｝∈E，其中Ns（j），Ne（j）∈N。

令機(jī)場(chǎng)航路圖圖論模型為Γ，則得到Γ中航路圖步驟如下：

步驟1 獲取所有機(jī)場(chǎng)節(jié)點(diǎn)坐標(biāo)，設(shè)共有nN個(gè)節(jié)點(diǎn)（1＜nN∈Z＋），編號(hào)為i的節(jié)點(diǎn)為N（i），坐標(biāo)為pwp，i。

步驟2 獲取Γ的鄰接矩陣A，A為nN階對(duì)稱方陣，E（G）是圖Γ中航路的集合，A的值可表示為

步驟3 將距離作為航路圖的權(quán)值。根據(jù)節(jié)點(diǎn)坐標(biāo)位置與節(jié)點(diǎn)之間連通關(guān)系，計(jì)算得到帶距離權(quán)值的鄰接矩陣GA，GA為nN階對(duì)稱方陣，其值如下所示：

該矩陣包含了各節(jié)點(diǎn)之間的相對(duì)位置及連通關(guān)系，通過對(duì)GA進(jìn)行處理可實(shí)現(xiàn)對(duì)機(jī)場(chǎng)空域進(jìn)行流量控制。

1.2 無人機(jī)模型

若能保證無人機(jī)飛行安全，則無人機(jī)的飛行與其大小、形狀無關(guān)，即可將無人機(jī)視為一個(gè)質(zhì)點(diǎn)。假定機(jī)場(chǎng)空域有M 架無人機(jī)，滿足如下模型：

式中：li∈R＋；pU，i∈R3與vi∈R3分別表示第i架無人機(jī)的位置與速度；vd，i為第i架無人機(jī)的期望速度，i＝1，2，…，M。

2 流量控制方法設(shè)計(jì)

要實(shí)現(xiàn)無人機(jī)在機(jī)場(chǎng)內(nèi)有序飛行，需要對(duì)進(jìn)場(chǎng)與離場(chǎng)的無人機(jī)進(jìn)行流量控制，規(guī)定無人機(jī)何時(shí)可以進(jìn)入機(jī)場(chǎng)空域。無人機(jī)在進(jìn)場(chǎng)或離場(chǎng)飛行前，應(yīng)規(guī)劃出航路后沿航路飛行。為保證無人機(jī)飛行安全，在為無人機(jī)規(guī)劃航路應(yīng)需避開可能發(fā)生沖突的航段。規(guī)避這部分航段之后，可能無法規(guī)劃出有效航路，起降延誤，無人機(jī)需要在入口或停機(jī)坪處等待。

本文的流量控制方法主要包括航路規(guī)劃方法、延時(shí)策略與航路圖更新3個(gè)部分，以得到無人機(jī)的進(jìn)離場(chǎng)時(shí)間與路徑。從無人機(jī)準(zhǔn)備進(jìn)場(chǎng)或離場(chǎng)到飛行結(jié)束，流量控制方法整體流程如圖2所示。

即在規(guī)劃出有效航路后對(duì)航路圖進(jìn)行更新，航路無效時(shí)延時(shí)等待；在無人機(jī)飛行過程中，在滿足一些條件時(shí)繼續(xù)對(duì)航路圖進(jìn)行更新。本文設(shè)計(jì)的流量控制方法還要為需要緊急降落的無人機(jī)提供降落的方案。

圖2 流量控制流程圖Fig.2 Flowchart of flow control

2.1 航路規(guī)劃方法設(shè)計(jì)

本文中采用基于Dijkstra算法［15］的方法規(guī)劃路徑。Dijkstra算法是一種使用廣度優(yōu)先搜索解決賦權(quán)有向圖的單源最短路徑問題的優(yōu)化方法，可以滿足需求。機(jī)場(chǎng)航路不存在負(fù)權(quán)邊，滿足Dijkstra算法使用條件。

機(jī)場(chǎng)中航路由無向圖Γ中的邊組成，設(shè)無人機(jī)Uk的航路中第i航段表示為Ek（i），則航路可表示為RE，k＝［Ek（1），Ek（2），…，Ek（nx）］，nx為航路中邊的數(shù)量。但使用航路中的節(jié)點(diǎn)序列比使用邊表示航路更加方便。對(duì)于航路中前后相接的航段，前方航段起點(diǎn)即為后方航段終點(diǎn)。沿?zé)o人機(jī)飛行方向，航段Ek（j）前方為Ek（j＋1），設(shè)Ek（j）的起點(diǎn)為Ns（Ek（j）），終點(diǎn)為Ne（Ek（j）），則Ne（Ek（j））＝Ns（Ek（j＋1）），其中1≤j≤nE∈Z＋。設(shè)使用節(jié)點(diǎn)編號(hào)表示的Uk航路為RN，k，RN，k＝N（RE，k）＝［Ns（Ek（1）），Ne（Ek（1）），Ne（Ek（2）），…，Ne（Ek（nx））］。

在設(shè)計(jì)機(jī)場(chǎng)時(shí)采用無約束的停機(jī)坪模型，進(jìn)場(chǎng)規(guī)劃時(shí)，以入口節(jié)點(diǎn)為起點(diǎn)，以各個(gè)停機(jī)坪節(jié)點(diǎn)為終點(diǎn)。用Dijkstra算法逐個(gè)計(jì)算出在無向圖Γ中從入口到每一座停機(jī)坪的最短路徑，所有路徑中最短的一條為進(jìn)場(chǎng)路徑RN，k；若有多條路徑長(zhǎng)度相等且最短，選擇航路序列中同等位置但節(jié)點(diǎn)編號(hào)最小的一條。如圖3所示的加粗實(shí)線，在機(jī)場(chǎng)中沒有其他無人機(jī)時(shí)，無人機(jī)U1進(jìn)場(chǎng)路徑RN，1＝［N（4），N（1），N（5），N（21）］；U2進(jìn)場(chǎng)路徑RN，2＝［N（4），N（7），N（10），N（23）］。

離場(chǎng)航路規(guī)劃以當(dāng)前所處停機(jī)坪節(jié)點(diǎn)為起點(diǎn)，以機(jī)場(chǎng)出口為終點(diǎn)，直接利用Dijkstra算法得出離場(chǎng)路徑。

圖3 機(jī)場(chǎng)進(jìn)場(chǎng)航路規(guī)劃示意圖Fig.3 Schematic diagram of airfield arrival route planning

2.2 飛行延時(shí)策略設(shè)計(jì)

設(shè)Uk接收到進(jìn)場(chǎng)或離場(chǎng)指令的時(shí)間為ts，k，并在該時(shí)間點(diǎn)為無人機(jī)規(guī)劃路徑。若無可用路徑，起降延時(shí)，并在一段時(shí)間后再次規(guī)劃航路，直到航路可用。設(shè)T為當(dāng)前時(shí)刻，Uk在當(dāng)前時(shí)刻總延時(shí)為Td，k，每次增加的延時(shí)時(shí)間為tstep，k，從開始等待到飛行流程如下所示。

設(shè)計(jì)延時(shí)策略目的如下：

1）禁止進(jìn)場(chǎng)時(shí)后方無人機(jī)超越前方等待的無人機(jī)。

2）使延時(shí)等待最久的無人機(jī)盡早進(jìn)場(chǎng)或離場(chǎng)。

上述目的通過改變無人機(jī)每次延時(shí)tstep，k來實(shí)現(xiàn)。設(shè)置一個(gè)較小的tstep1，一個(gè)較大的tstep2，令tstep2≥2 tstep1。當(dāng)存在多架無人機(jī)進(jìn)場(chǎng)延時(shí)或離場(chǎng)延時(shí)，延時(shí)最久的無人機(jī)tstep，k＝tstep1，其余無人機(jī)tstep，k＝tstep2。設(shè)在當(dāng)前時(shí)刻進(jìn)場(chǎng)延時(shí)或離場(chǎng)延時(shí)的無人機(jī)數(shù)量為nU，d，機(jī)場(chǎng)中全部的無人機(jī)數(shù)量為nU，ttl。無人機(jī)處于進(jìn)場(chǎng)延時(shí)還是離場(chǎng)延時(shí)可通過判斷Uk實(shí)時(shí)位置pU，k得出。判斷進(jìn)場(chǎng)或離場(chǎng)時(shí)Uk實(shí)時(shí)tstep，k策略如圖4所示。

無人機(jī)規(guī)劃出航線后延時(shí)時(shí)間Td，k清零，因此Td，k＞0即表示Uk處于延時(shí)狀態(tài)。在確定Uk為進(jìn)場(chǎng)或離場(chǎng)之后通過圖4所示策略確定所有處于延時(shí)狀態(tài)Uk的tstep，k。注意進(jìn)場(chǎng)與離場(chǎng)無人機(jī)之間的延時(shí)計(jì)算互不影響，將兩類無人機(jī)的延時(shí)時(shí)間分開比較。

圖4 t step，k實(shí)時(shí)計(jì)算策略Fig.4 Real-time computing strategy of t step，k

2.3 機(jī)場(chǎng)航路圖更新方法設(shè)計(jì)

機(jī)場(chǎng)航路圖更新根據(jù)無人機(jī)的飛行狀態(tài)、實(shí)時(shí)位置等信息，將機(jī)場(chǎng)中部分航段中斷或恢復(fù)。如機(jī)場(chǎng)中已有無人機(jī)U1飛行，后續(xù)進(jìn)場(chǎng)的U2規(guī)劃航路時(shí)受U1影響不能經(jīng)過一部分航路，則對(duì)于U2該部分航路被中斷。被中斷的航路在滿足某些條件下（如U1降落或離場(chǎng)）應(yīng)被恢復(fù)，使該部分航路能夠重復(fù)使用。本節(jié)為全文重點(diǎn)研究?jī)?nèi)容。與文獻(xiàn)［11］中的方法不同，本文設(shè)計(jì)的航路圖更新方法確保無人機(jī)在機(jī)場(chǎng)空域的飛行安全。

若GA（i，j）＝0，說明航點(diǎn)N（i）與N（j）之間不存在航路。航路圖更新僅指對(duì)原有的航路變化，不允許產(chǎn)生新的航路。設(shè)去掉中斷的航路后，剩余機(jī)場(chǎng)航路矩陣為GA，r，GA，r也是對(duì)稱 矩陣。中斷航路時(shí)GA，r對(duì)應(yīng)位置歸零，恢復(fù)航路時(shí)GA，r對(duì)應(yīng)位置恢復(fù)原值。則無人機(jī)經(jīng)過機(jī)場(chǎng)，不斷更新航路圖的過程實(shí)質(zhì)上是將GA，r中的值不斷歸零與恢復(fù)原值。

為保證無人機(jī)的飛行安全，規(guī)定任意時(shí)刻同航段上最多只有1架無人機(jī)，不考慮無人機(jī)間縱向安全距離。因此在為無人機(jī)規(guī)劃完成航路之后，規(guī)劃出的航路應(yīng)被中斷。但若2架無人機(jī)航線存在公共節(jié)點(diǎn)，且可能在相近的時(shí)間到達(dá)該公共點(diǎn)，仍舊存在安全隱患。

文獻(xiàn)［11］中為了防止在公共節(jié)點(diǎn)處發(fā)生沖突，先規(guī)劃出一條航線，預(yù)估無人機(jī)按當(dāng)前速度沿航線飛行時(shí)在公共節(jié)點(diǎn)是否發(fā)生沖突。若并無沖突，則這條航線就是在空域內(nèi)的航路；否則重新規(guī)劃航路。一旦無人機(jī)沒有按照當(dāng)前速度飛行或受其他因素干擾，便可能發(fā)生意料之外的沖突。

為進(jìn)一步提高飛行安全性能，在規(guī)劃有效航路后，本文將GA，r中所有已規(guī)劃出航路中節(jié)點(diǎn)為端點(diǎn)的航段全部中斷，可以保證所有無人機(jī)的航路不存在公共點(diǎn)，使2架無人機(jī)的航路不存在交集?？梢栽跓o人機(jī)Uk飛過整條航路后恢復(fù)因Uk被中斷的所有航路。但上述策略飛行效率較低，因此規(guī)定Uk每經(jīng)過一個(gè)節(jié)點(diǎn)，在GA，r中恢復(fù)以該節(jié)點(diǎn)為端點(diǎn)的航段，前方航段除外。在規(guī)劃完成航路后中斷航路，無人機(jī)在機(jī)場(chǎng)內(nèi)飛行過程中恢復(fù)航路。

若有多架無人機(jī)在機(jī)場(chǎng)內(nèi)飛行，可能有部分航段被重復(fù)中斷，若不進(jìn)行處理，任意一架無人機(jī)經(jīng)過該航段端點(diǎn)節(jié)點(diǎn)后，會(huì)將該航段恢復(fù)。該航段此時(shí)可能不應(yīng)恢復(fù)，仍舊存在安全隱患。用標(biāo)志位矩陣GF記錄航段被中斷的次數(shù)，GF將與鄰接矩陣A共同判斷各個(gè)航段是否可以中斷或恢復(fù)，令初始值GF＝A。GF（i，j）＝1表示節(jié)點(diǎn)i，j之間航路為通，否則說明該航路不存在或已中斷。

整個(gè)機(jī)場(chǎng)運(yùn)行過程中，在GF滿足一定條件下，對(duì)GA，r進(jìn)行更新。無人機(jī)規(guī)劃出有效航路之后，若GF（i，j）＝1，則中斷航路，且使GF（i，j）＝0；若GF（i，j）≤0且原本存在航路（即A（i，j）＝1），說 明 該 航 路 已 被 中 斷，只 需 使 GF（i，j）＝GF（i，j）-1。無人機(jī)飛過一個(gè)航點(diǎn)時(shí)，若以該節(jié)點(diǎn)為端點(diǎn)的航段對(duì)應(yīng)的GF（i，j）＝0，則恢復(fù)航路，且使GF（i，j）＝1；若GF（i，j）＜0且原本存在航路，只需使GF（i，j）＝GF（i，j）＋1。注意GF為對(duì)稱矩陣，在更新GF（i，j）時(shí)需要同步更新GF（j，i）。

為防止無人機(jī)通過停放有無人機(jī)的停機(jī)坪上方航點(diǎn)，停機(jī)坪區(qū)域航路需進(jìn)行特殊處理。

無人機(jī)進(jìn)場(chǎng)航路圖更新步驟如下：

步驟1 設(shè)Uk的進(jìn)場(chǎng)航路為RN，k＝［N（i1），N（i2），…，N（ir）］，在GF對(duì)應(yīng)值滿足條件時(shí)，

GA，r對(duì)稱，將GA，r（in，im）一同修改，并對(duì)GF同時(shí)進(jìn)行更新。規(guī)劃出有效航路后，將所有以RN，k中節(jié)點(diǎn)為端點(diǎn)的航段中斷，并進(jìn)行標(biāo)記。

2），GA，r表達(dá)式如下：

同理，將GA，r（in，ia）一并修改并對(duì)GF進(jìn)行更新，恢復(fù)的航路不包括N（ia）到下一航點(diǎn)的航段。若無人機(jī)U1與U2位置如圖3所示，剩余航路圖如圖5所示。

圖5 機(jī)場(chǎng)剩余航路示意圖Fig.5 Schematic diagram of airfield remaining route

步驟3 為避免后續(xù)無人機(jī)進(jìn)入已被占據(jù)的停機(jī)坪，規(guī)定無人機(jī)到達(dá)航路中的停機(jī)坪節(jié)點(diǎn)N（ir-1）與N（ir）時(shí)不恢復(fù)停機(jī)坪區(qū)域航路，也不改變停機(jī)坪區(qū)域航段的標(biāo)志位。

停機(jī)坪與停機(jī)坪上方航點(diǎn)在進(jìn)場(chǎng)航路中為最后兩位，在無人機(jī)進(jìn)場(chǎng)直到起飛離開停機(jī)坪的過程中均需保持航路中斷的狀態(tài)，直到無人機(jī)起飛后才會(huì)恢復(fù)。進(jìn)場(chǎng)航路圖更新流程如圖6所示。

離場(chǎng)航路圖更新與進(jìn)場(chǎng)時(shí)類似。但在規(guī)劃航路前，需先將無人機(jī)所在停機(jī)坪區(qū)域航路全部恢復(fù)，否則無法規(guī)劃出可用航路。若規(guī)劃出航路無效，則需再次中斷該停機(jī)坪區(qū)域所有航段，到下個(gè)離場(chǎng)時(shí)間點(diǎn)再次恢復(fù)。更新過程中需符合GF矩陣的限制，并對(duì)GF進(jìn)行更新。航路圖更新步驟與進(jìn)場(chǎng)時(shí)步驟1、2相同，但在步驟2時(shí)可以一直飛離出口節(jié)點(diǎn)。離場(chǎng)時(shí)航路圖更新流程如圖7所示。

與入口相連的航段有兩條，雖然兩條航段在航路規(guī)劃時(shí)被中斷，但無人機(jī)進(jìn)場(chǎng)后在規(guī)劃航路之外的航段會(huì)立即恢復(fù)，因此無人機(jī)可以連續(xù)進(jìn)場(chǎng)；但與出口相連的航段直到無人機(jī)離場(chǎng)才能恢復(fù)，因此同時(shí)段只能實(shí)現(xiàn)1架無人機(jī)起飛離場(chǎng)。

圖6 進(jìn)場(chǎng)航路圖更新流程圖Fig.6 Flowchart of airfield arrival route map update

2.4 無人機(jī)緊急降落方法設(shè)計(jì)

在正常飛行以外，若無人機(jī)運(yùn)輸?shù)氖切枰o急處理的物品或者無人機(jī)自身狀態(tài)不佳，無人機(jī)需要緊急降落，機(jī)場(chǎng)應(yīng)設(shè)計(jì)降落通道。對(duì)于此類無人機(jī)，需要遵循如下原則：

圖7 離場(chǎng)航路圖更新流程圖Fig.7 Flowchart of airfield departure route map update

1）確保無人機(jī)飛行安全。

2）使無人機(jī)盡快降落。

因此，無人機(jī)緊急降落航路應(yīng)沿最短路徑飛行至停機(jī)坪區(qū)域。無人機(jī)在機(jī)場(chǎng)以外的空域飛行時(shí)高度高于機(jī)場(chǎng)航路，因此設(shè)計(jì)緊急航路高度高于正常飛行航路，且航線從入口直接飛行至停機(jī)坪上方。

在入口及各停機(jī)坪上方航點(diǎn)上方增加一個(gè)航點(diǎn)作為緊急降落航路，如圖8所示。

圖8 緊急降落機(jī)場(chǎng)航路示意圖Fig.8 Schematic diagram of airfield route for emergency landing

當(dāng)無人機(jī)需要緊急降落時(shí)，從緊急入口進(jìn)入。航路規(guī)劃方法與進(jìn)場(chǎng)時(shí)的航路規(guī)劃方法相同。由于部分緊急降落的航路夾角較小，若有無人機(jī)連續(xù)緊急降落，緊急入口附近存在安全隱患。因此規(guī)定前一架無人機(jī)從緊急入口進(jìn)入時(shí)，將以緊急入口為端點(diǎn)的航段全部中斷，在該無人機(jī)飛過安全距離后恢復(fù)該部分航路。

3 性能測(cè)試

3.1 評(píng)估指標(biāo)

對(duì)于有人機(jī)，扇區(qū)容量評(píng)估在空域安全與空域設(shè)計(jì)等方面非常重要［16］，是影響空中交通系統(tǒng)安全和效率的核心因素［17］。本文方法雖針對(duì)可垂直起降的無人機(jī)設(shè)計(jì)，與有人機(jī)差別很大，但空域容量仍是機(jī)場(chǎng)性能的重要指標(biāo)。

實(shí)驗(yàn)中通過測(cè)試機(jī)場(chǎng)的運(yùn)行容量［18］來評(píng)估機(jī)場(chǎng)性能，運(yùn)行容量是指在可接受的延誤水平下，空域系統(tǒng)單位時(shí)間所能服務(wù)的最大航空器架次。仿真時(shí)使用無人機(jī)進(jìn)場(chǎng)間隔，即每隔多長(zhǎng)時(shí)間進(jìn)場(chǎng)1架無人機(jī)來表示機(jī)場(chǎng)容量。在確保無人機(jī)飛行安全時(shí)，通過調(diào)整無人機(jī)的進(jìn)場(chǎng)間隔時(shí)間，得到可接受平均延誤時(shí)長(zhǎng)（以下簡(jiǎn)稱平均延時(shí)）時(shí)的間隔，該間隔對(duì)應(yīng)機(jī)場(chǎng)運(yùn)行容量。測(cè)量進(jìn)場(chǎng)與進(jìn)離場(chǎng)間隔時(shí)間與平均延時(shí)的曲線，并找出對(duì)應(yīng)機(jī)場(chǎng)運(yùn)行容量的進(jìn)場(chǎng)間隔時(shí)間。

無人機(jī)之間的距離可以最直觀地表示空域系統(tǒng)的安全性能，機(jī)場(chǎng)運(yùn)行時(shí)場(chǎng)內(nèi)無人機(jī)的最小距離是機(jī)場(chǎng)安全性能的重要指標(biāo)。在本文設(shè)計(jì)的流量控制方法中，一段航路同時(shí)段最多只有1架無人機(jī)經(jīng)過，不需要設(shè)計(jì)縱向安全距離，令安全距離為無人機(jī)直徑的2倍即可。

實(shí)驗(yàn)通過測(cè)試任意時(shí)刻場(chǎng)內(nèi)飛行的無人機(jī)之間距離的最小值來評(píng)估流量控制方法的安全性能，若任意時(shí)刻的無人機(jī)重心最小距離均大于安全距離，則該方法可以確保無人機(jī)飛行安全。

測(cè)試機(jī)場(chǎng)性能時(shí)只針對(duì)正常飛行的無人機(jī)進(jìn)行實(shí)驗(yàn)。因?yàn)闄C(jī)場(chǎng)性能的測(cè)試是在無人機(jī)流量很高的極端情況下進(jìn)行的測(cè)量，而無人機(jī)緊急降落是在機(jī)場(chǎng)實(shí)際運(yùn)行時(shí)的功能。在機(jī)場(chǎng)內(nèi)有空閑停機(jī)坪時(shí)，需要緊急降落的無人機(jī)降落延時(shí)可以忽略不計(jì)，只需要測(cè)試此種情況下無人機(jī)之間的安全性能。

3.2 仿真實(shí)驗(yàn)

實(shí)驗(yàn)分別對(duì)擁有3座、6座與12座停機(jī)坪的機(jī)場(chǎng)進(jìn)行測(cè)試。每座停機(jī)坪為邊長(zhǎng)10m的正方形區(qū)域，停機(jī)坪節(jié)點(diǎn)位于區(qū)域中心。3種機(jī)場(chǎng)的停機(jī)坪排布分別為一行三列、二行三列、三行四列。航路高10 m，入口與出口節(jié)點(diǎn)與左上方、右上方的2座停機(jī)坪正對(duì)（6座停機(jī)坪機(jī)場(chǎng)示意圖見圖1）。無人機(jī)在機(jī)場(chǎng)內(nèi)勻速飛行，速度為0.4m／s，進(jìn)場(chǎng)間隔均勻。無人機(jī)處于等待狀態(tài)時(shí)每次延時(shí)時(shí)間為10 s；若有多架無人機(jī)處于延時(shí)狀態(tài)，后進(jìn)入等待狀態(tài)的無人機(jī)每次延時(shí)時(shí)間為20 s。入口處在前一架無人機(jī)飛出10 s后，方允許后續(xù)無人機(jī)進(jìn)場(chǎng)。停機(jī)坪上方航點(diǎn)到四周航段距離為5m，該距離需要能夠確保無人機(jī)之間的飛行安全，因此設(shè)無人機(jī)直徑為1.5m，無人機(jī)之間安全距離為3m。仿真開始時(shí)，機(jī)場(chǎng)中沒有無人機(jī)。

測(cè)試緊急降落的安全性能時(shí)，用少數(shù)緊急降落無人機(jī)與多數(shù)正常飛行無人機(jī)按照一定進(jìn)場(chǎng)間隔在圖8所示的機(jī)場(chǎng)中進(jìn)行測(cè)試。

3.2.1 進(jìn)場(chǎng)容量測(cè)試

無人機(jī)只進(jìn)場(chǎng)不離場(chǎng)，不考慮停機(jī)坪承載量的情況下，每座停機(jī)坪在無人機(jī)降落后恢復(fù)停機(jī)坪區(qū)域航線，等待后續(xù)無人機(jī)降落。

分別在3座、6座、12座停機(jī)坪的3種機(jī)場(chǎng)通過20架、50架、100架無人機(jī)，調(diào)整無人機(jī)進(jìn)場(chǎng)間隔并計(jì)算每架無人機(jī)平均延時(shí)。設(shè)進(jìn)場(chǎng)時(shí)允許的平均延時(shí)為25 s。進(jìn)場(chǎng)間隔時(shí)間-平均延時(shí)關(guān)系如圖9所示。

圖9中橫虛線為允許的延誤水平（25 s），與3條曲線交點(diǎn)的橫坐標(biāo)即為對(duì)應(yīng)運(yùn)行容量的進(jìn)場(chǎng)間隔時(shí)間。3種機(jī)場(chǎng)無人機(jī)進(jìn)場(chǎng)間隔時(shí)間分別在大于23 s、16 s與14 s時(shí)可以滿足允許的延誤。

3.2.2 進(jìn)離場(chǎng)容量測(cè)試

分別在3種機(jī)場(chǎng)通過15架、30架、60架無人機(jī)，調(diào)整進(jìn)場(chǎng)間隔時(shí)間并分別計(jì)算進(jìn)場(chǎng)平均延時(shí)、離場(chǎng)平均延時(shí)與平均總延時(shí)，無人機(jī)在降落40 s后準(zhǔn)備起飛。設(shè)允許的平均總延時(shí)為50 s。3種機(jī)場(chǎng)進(jìn)離場(chǎng)間隔時(shí)間-平均延時(shí)關(guān)系如圖10所示。

3種機(jī)場(chǎng)進(jìn)場(chǎng)間隔時(shí)間-平均總延時(shí)如圖11所示。

圖10 間隔時(shí)間-平均延時(shí)（進(jìn)離場(chǎng)）Fig.10 Interval versus average delay of arrival and departure

圖11 間隔時(shí)間-平均總延時(shí)（進(jìn)離場(chǎng)）Fig.11 Interval versus average total delay of arrival and departure

3種機(jī)場(chǎng)無人機(jī)進(jìn)場(chǎng)間隔時(shí)間分別在大于70、75與105 s時(shí)可以滿足允許的延誤。對(duì)于有12座停機(jī)坪的機(jī)場(chǎng)，在平均延時(shí)可接受的情況下，對(duì)機(jī)場(chǎng)中停機(jī)坪的利用率非常低。

3.2.3 進(jìn)場(chǎng)安全性能測(cè)試

分別使用達(dá)到3種機(jī)場(chǎng)運(yùn)行容量時(shí)的進(jìn)場(chǎng)間隔時(shí)間與10 s的間隔時(shí)間，使用與測(cè)試運(yùn)行容量時(shí)相同數(shù)量的無人機(jī)流，測(cè)試進(jìn)場(chǎng)時(shí)無人機(jī)之間的最短相距距離，結(jié)果如圖12所示。

圖12縱坐標(biāo)為仿真各個(gè)時(shí)刻所有機(jī)場(chǎng)內(nèi)飛行中的無人機(jī)最短相距距離。圖12（a）和圖12（b）分別為進(jìn)場(chǎng)間隔時(shí)間達(dá)到進(jìn)場(chǎng)容量時(shí)和間隔時(shí)間為10 s時(shí)各個(gè)機(jī)場(chǎng)內(nèi)所有飛行中的無人機(jī)不同時(shí)刻的最短相距距離。2組數(shù)據(jù)中任意時(shí)刻最短相距距離均大于4m，大于安全距離。

3.2.4 進(jìn)離場(chǎng)安全性能測(cè)試

分別使用達(dá)到3種機(jī)場(chǎng)運(yùn)行容量時(shí)的進(jìn)場(chǎng)間隔時(shí)間與20 s的間隔時(shí)間，使用與測(cè)試運(yùn)行容量時(shí)相同數(shù)量的無人機(jī)流，測(cè)試進(jìn)離場(chǎng)時(shí)無人機(jī)之間的最短相距距離，結(jié)果如圖13所示。

圖13（a）為間隔時(shí)間達(dá)到進(jìn)場(chǎng)運(yùn)行容量時(shí)各個(gè)機(jī)場(chǎng)內(nèi)所有飛行中的無人機(jī)不同時(shí)刻的最短相距距離，圖13（b）為間隔時(shí)間為20 s時(shí)不同時(shí)刻的最短相距距離。2組數(shù)據(jù)中任意時(shí)刻最短相距距離均大于4m，大于安全距離。

圖12 運(yùn)行時(shí)間-無人機(jī)最短相距距離（進(jìn)場(chǎng)）Fig.12 Arrival running time versus the shortest distance between drones

圖13 運(yùn)行時(shí)間-無人機(jī)最短相距距離（進(jìn)離場(chǎng)）Fig.13 Arrival and departure running time versus the shortest distance between drones

3.2.5 緊急降落安全性測(cè)試

保持正常飛行的無人機(jī)進(jìn)場(chǎng)間隔時(shí)間為100 s，一共通過10架正常飛行的無人機(jī)，緊急降落的無人機(jī)數(shù)量從1架增加到5架，分別在第1、3、5、7、9架正常飛行的無人機(jī)之后從緊急入口進(jìn)場(chǎng)，計(jì)算仿真過程中的最小距離。測(cè)試結(jié)果如表1所示。

表1 緊急降落最小距離Tab le 1 M inim um d istance during em ergency landing

表1表明緊急降落時(shí)的最小距離均遠(yuǎn)大于安全距離。

3.3 結(jié)果說明

圖9結(jié)果表明，在保證無人機(jī)飛行安全時(shí)，機(jī)場(chǎng)內(nèi)停機(jī)坪數(shù)量越多，其進(jìn)場(chǎng)運(yùn)行容量越大。

圖10結(jié)果表明，無人機(jī)進(jìn)離場(chǎng)時(shí)增大進(jìn)場(chǎng)間隔時(shí)間，進(jìn)場(chǎng)平均延時(shí)會(huì)快速降低，但對(duì)離場(chǎng)平均延時(shí)影響不大。這是由于在設(shè)計(jì)的流量控制策略下，同時(shí)刻只允許1架無人機(jī)起飛，此時(shí)其他準(zhǔn)備離場(chǎng)的無人機(jī)被迫延時(shí)等待。在進(jìn)場(chǎng)平均延時(shí)趨向于0 s時(shí)，離場(chǎng)平均延時(shí)快速降低，這是由于此時(shí)無人機(jī)進(jìn)場(chǎng)頻率很低，機(jī)場(chǎng)內(nèi)同時(shí)存在的無人機(jī)數(shù)量較少，對(duì)需要離場(chǎng)的無人機(jī)限制大幅減小，使離場(chǎng)平均延時(shí)快速降低。

圖11結(jié)果表明，在確保飛行安全時(shí)，機(jī)場(chǎng)內(nèi)停機(jī)坪數(shù)量越多，其進(jìn)離場(chǎng)運(yùn)行容量越小。其結(jié)果與進(jìn)場(chǎng)相反，分析后發(fā)現(xiàn)，任意1架無人機(jī)規(guī)劃出離場(chǎng)航路后，會(huì)阻塞住出口節(jié)點(diǎn)直到離開機(jī)場(chǎng)，同時(shí)刻只允許1架無人機(jī)離場(chǎng)，影響了離場(chǎng)效率，且機(jī)場(chǎng)越大，在機(jī)場(chǎng)中等待的無人機(jī)數(shù)量越多，無人機(jī)在機(jī)場(chǎng)內(nèi)飛行時(shí)間越長(zhǎng)，使平均延時(shí)越高。

圖12與圖13結(jié)果表明，所有機(jī)場(chǎng)中，無論是進(jìn)場(chǎng)或者進(jìn)離場(chǎng)，無人機(jī)之間的最短相距距離均超過安全距離，說明本文所設(shè)計(jì)的流量控制方法能夠保證無人機(jī)的飛行安全。

表1表明本文設(shè)計(jì)的緊急降落方法是安全可行的，在機(jī)場(chǎng)正常使用時(shí)，能夠?yàn)樾枰o急降落的無人機(jī)提供通道。

4 結(jié) 論

1）本文針對(duì)城市物流場(chǎng)景設(shè)計(jì)了一種單入口單出口、航路交叉、多停機(jī)坪的無人機(jī)機(jī)場(chǎng)模型，并就此模型提出一種基于圖論的中小型垂直起降無人機(jī)的流量控制方法，實(shí)現(xiàn)了同時(shí)段多架次無人機(jī)在機(jī)場(chǎng)中安全起降，并為需要緊急降落的無人機(jī)提供降落通道。

2）所提方法能夠?qū)崿F(xiàn)對(duì)垂直起降固定翼無人機(jī)與多旋翼無人機(jī)在設(shè)計(jì)機(jī)場(chǎng)區(qū)域的流量控制，保證無人機(jī)在機(jī)場(chǎng)空域的飛行安全，算法魯棒性較高。

3）設(shè)計(jì)機(jī)場(chǎng)時(shí)應(yīng)設(shè)計(jì)較大的停機(jī)坪，不宜使機(jī)場(chǎng)內(nèi)停機(jī)坪數(shù)量過多。較小的停機(jī)坪會(huì)降低機(jī)場(chǎng)的安全性能，過多的停機(jī)坪會(huì)影響無人機(jī)進(jìn)離場(chǎng)效率，降低機(jī)場(chǎng)容量。

4）安全優(yōu)先的流量控制方法能夠確保無人機(jī)的飛行安全，但由于同時(shí)刻只允許1架無人機(jī)起飛，影響了無人機(jī)飛行效率，降低機(jī)場(chǎng)運(yùn)行容量。因此，在后續(xù)工作中，應(yīng)實(shí)現(xiàn)同時(shí)段多架無人機(jī)的離場(chǎng)飛行，進(jìn)一步提高機(jī)場(chǎng)運(yùn)行容量。

5）所提方法與文獻(xiàn)［11］設(shè)計(jì)的效率優(yōu)先的流量控制方法均能實(shí)現(xiàn)無人機(jī)在機(jī)場(chǎng)的安全飛行。2種方法在無人機(jī)離場(chǎng)時(shí)都會(huì)在出口發(fā)生阻塞，因而運(yùn)行容量相接近。安全優(yōu)先的方法最小距離要大于效率優(yōu)先的方法，且對(duì)無人機(jī)控制精度要求較低，安全性能優(yōu)于效率優(yōu)先的方法。

6）所提方法在規(guī)劃航路時(shí)就保證了機(jī)場(chǎng)內(nèi)無人機(jī)的飛行安全。若無人機(jī)機(jī)場(chǎng)規(guī)劃時(shí)，采用本文設(shè)計(jì)的機(jī)場(chǎng)模型，均可使用本文提出的流量控制方法。無論機(jī)場(chǎng)大小與出入口數(shù)量，都可以保證機(jī)場(chǎng)內(nèi)無人機(jī)的飛行安全。若存在多個(gè)出口，需要判斷無人機(jī)從哪個(gè)出口離場(chǎng)；若出入口數(shù)量較多，在從機(jī)場(chǎng)出入口到外部航路的飛行過程中需要進(jìn)行更加縝密的防沖突判斷，后續(xù)研究將考慮存在多個(gè)出入口的情況中機(jī)場(chǎng)和空中的流量調(diào)度。