谷志鳴，高文明，魏瀟龍，姚登凱

（1.解放軍91899部隊，遼寧葫蘆島125001；2.空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安710051）

基于蒙特卡洛法的無人機(jī)飛行沖突解脫安全評估*

谷志鳴1，高文明2，魏瀟龍2，姚登凱2

（1.解放軍91899部隊，遼寧葫蘆島125001；2.空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安710051）

沖突解脫技術(shù)是無人機(jī)與有人機(jī)共域飛行的前提保障。針對目前缺少對沖突解脫技術(shù)安全評估的方法，提出運用蒙特卡洛法對飛行沖突進(jìn)行仿真模擬，得出沖突解脫算法的安全效率。提出基于改進(jìn)蟻群算法的沖突解脫技術(shù)，實現(xiàn)無人機(jī)的飛行沖突解脫；利用蒙特卡洛法，對飛行沖突過程進(jìn)行大規(guī)模仿真，計算沖突解脫效率，與基本蟻群算法進(jìn)行對比，并從安全角度對結(jié)果進(jìn)行分析。提出的思路可為未來無人機(jī)空域運行安全評估體系的構(gòu)建提供一種理論參考。

無人機(jī)，蟻群算法，蒙特卡洛，沖突解脫

0 引言

無人駕駛航空器即無人機(jī)，因其體積小、使用風(fēng)險小，成本低、對環(huán)境要求低等諸多優(yōu)點，在軍事和民用領(lǐng)域受到青睞［1］。隨著無人機(jī)技術(shù)的發(fā)展，無人機(jī)早已具備了全空域飛行的能力，但由于“感知-避讓”功能的不完善，國內(nèi)外無人機(jī)的管制一般都采用劃設(shè)隔離空域的方式運行［2］，限制了無人機(jī)在各領(lǐng)域的應(yīng)用，為使無人機(jī)能充分發(fā)揮它的作用，找到一種可靠的飛行沖突解脫技術(shù)成為目前無人機(jī)系統(tǒng)設(shè)計的關(guān)鍵技術(shù)之一［3］。

目前，國內(nèi)外對無人機(jī)沖突解脫技術(shù)的研究有很多，但是絕大多數(shù)研究都集中在沖突解脫算法的有效性上，從算法的可靠性以及無人機(jī)空域飛行安全的角度檢驗沖突解脫算法性能的研究很少。在國外，M.Garcia［4］，Eva Crück［5］在沖突解脫算法上都提出了自己的觀點，但研究中并未對算法的可靠性上未加證明，很大程度上降低了算法應(yīng)用于實際工程的可能性。Jose Asmat［6］設(shè)計了一種利用TCAS（Traffic Alert Collision Avoidance System）技術(shù)來進(jìn)行無人機(jī)協(xié)同方式下的沖突解脫技術(shù)，并用Monte Carlo的仿真驗證了沖突解脫方案的安全性能；在國內(nèi)方面對無人機(jī)評估主要集中于任務(wù)執(zhí)行效率方面，王淵［7］、崔莉薇［8］等分別應(yīng)用不同的智能算法，實現(xiàn)了飛行沖突解脫，但僅僅比較了解脫航跡的長度和算法運算速度，未對算法的可靠性進(jìn)行說明；也有使用風(fēng)險評價指數(shù)矩陣法［9］、層次分析法［10］、多級模糊綜合評判法［11］等方法進(jìn)行無人機(jī)安全評估，但相對數(shù)量較少。

鑒于此，本文基于蟻群算法提出了一種無人機(jī)飛行沖突解脫技術(shù)，再利用蒙特卡洛法（MC，Monte Carlo）對改進(jìn)的算法進(jìn)行可靠性分析，從安全的角度對算法的性能進(jìn)行比較。

1 蒙特卡洛方法簡介

隨著現(xiàn)代計算機(jī)技術(shù)的飛速發(fā)展，蒙特卡洛法已經(jīng)成為人們解決復(fù)雜統(tǒng)計模型和隨機(jī)事件模擬的主要工具。蒙特卡洛法又稱為隨機(jī)模擬法或統(tǒng)計模擬法，屬于計算數(shù)學(xué)的一個分支，其實質(zhì)是按一定概率分布產(chǎn)生隨機(jī)數(shù)的方法來模擬實際中可能出現(xiàn)的隨機(jī)現(xiàn)象，通過利用計算機(jī)軟件進(jìn)行大規(guī)模仿真實驗，得到模擬的實驗數(shù)據(jù)，在此實驗的基礎(chǔ)上進(jìn)行分析判斷，得到實際問題中可能出現(xiàn)的規(guī)律或求解方法。在現(xiàn)實生活中進(jìn)行工程實驗時，試驗有可能高風(fēng)險，耗費高，耗時長甚至具有破壞性，不可能通過反復(fù)試驗進(jìn)行實驗數(shù)據(jù)的采集，此時蒙特卡洛法不失為最簡單、經(jīng)濟(jì)、實用的方法。

本文研究的是無人機(jī)飛行沖突解脫問題，不可能在安全性未達(dá)標(biāo)的情況下在現(xiàn)實中進(jìn)行沖突解脫效率測試，因而采取應(yīng)用計算機(jī)軟件進(jìn)行仿真模擬。飛機(jī)在飛行時由于設(shè)備精度，飛行員操作誤差，環(huán)境影響等因素，飛行軌跡具有隨機(jī)性，具有蒙特卡洛方法的特征，故而應(yīng)用蒙特卡洛法進(jìn)行仿真，因涉及安全的因素十分復(fù)雜，本文將所有因素，在綜合作用下可以假定為高斯分布［13］。進(jìn)行大規(guī)模的仿真，得出無人機(jī)沖突解脫算法成功避險的概率，并對結(jié)果進(jìn)行分析。

2 改進(jìn)蟻群算法的沖突解脫技術(shù)

蟻群算法作為一種最新提出的仿生進(jìn)化算法具有:魯棒性強(qiáng)、并行計算能力、全局搜索能力、正反饋機(jī)制、易于與其他算法混合等優(yōu)點［14］。目前為止，蟻群算法已經(jīng)成功解決了旅行商問題、指派問題、調(diào)度問題、車輛路由問題、網(wǎng)絡(luò)路由問題等組合優(yōu)化問題，且與旅行商問題具有一定的相似性，但由于蟻群算法具有搜索時間長、易陷入局部解兩大缺點，必須要加以改善才能適應(yīng)無人機(jī)沖突解脫的復(fù)雜性與對時效性的要求。

在傳統(tǒng)蟻群算法中，一般將節(jié)點和節(jié)點之間的距離的倒數(shù)作為啟發(fā)因子，如式（1）:

式中:dij為節(jié)點i到節(jié)點j的距離。螞蟻k由狀態(tài)i向j轉(zhuǎn)移的概率選擇公式為:

式中:Pij（kt）為t時刻螞蟻k從節(jié)點i轉(zhuǎn)移至j的概率為t時刻節(jié)點i到j(luò)路徑上的信息素濃度；為節(jié)點j的啟發(fā)函數(shù)；allowedk為螞蟻k下一步可能到達(dá)的路徑點集；α，β分別表示的作用程度。

在所有螞蟻進(jìn)行完一次路徑規(guī)劃后，則需要進(jìn)行信息素的更新，信息素更新公式為:

在無人機(jī)路徑規(guī)劃問題中，有時候最優(yōu)解與次優(yōu)解之間會相差較大距離，甚至不在同一方向上。最大最小螞蟻系統(tǒng)中只有最優(yōu)螞蟻才釋放信息素，將所有螞蟻趨向最優(yōu)螞蟻附近，當(dāng)最優(yōu)螞蟻附近的解與真實的最優(yōu)解之間差距較大時，最優(yōu)解就有可能被錯過，對此，引入基于排序的螞蟻系統(tǒng)。每次迭代完成，對所有螞蟻進(jìn)行排序，除最優(yōu)螞蟻釋放信息素外，適應(yīng)度為前γ的螞蟻都進(jìn)行信息素的釋放，信息素更新公式為:

在完成一次信息素更新之后，一次循環(huán)結(jié)束，對形成的路徑進(jìn)行適應(yīng)性評價，適應(yīng)性函數(shù)為:

其中:w1，w2，w3為權(quán)重；J為綜合代價；Js為矩形空域威脅代價；Jr為圓形空域威脅代價；Ja為動態(tài)航空器的綜合威脅代價；Jl為無人機(jī)的航程約束代價。

無人機(jī)的飛行沖突解脫運用了動態(tài)路徑規(guī)劃的原理，在每完成一次路徑規(guī)劃之后，進(jìn)行一次狀態(tài)轉(zhuǎn)移，并對空域態(tài)勢進(jìn)行再次探測與更新，基于最新的態(tài)勢信息，無人機(jī)進(jìn)行航路的重規(guī)劃，不斷滾動前進(jìn)，直至到達(dá)終點。

本文構(gòu)建的沖突場景為航線交叉相遇下的飛行沖突，結(jié)合我國當(dāng)前航空器運行安全間隔的劃分標(biāo)準(zhǔn)［15］，根據(jù)無人機(jī)每次飛行與其他航空器的最小間隔距離，對無人機(jī)運行的安全狀況進(jìn)行分類。當(dāng)無人機(jī)與有人機(jī)之間的飛行間隔小于1.76 km，則認(rèn)為無人機(jī)存在極高的相撞風(fēng)險，記為一次嚴(yán)重事故。當(dāng)航空器間的距離在10 km～15 km之間時，則認(rèn)為無人機(jī)存在發(fā)生飛行沖突的潛在風(fēng)險。在10 km～15 km的間隔范圍內(nèi)雖然不算一次事故，但對其進(jìn)行統(tǒng)計有利于無人機(jī)沖突解脫反應(yīng)距離的設(shè)置。具體的事故風(fēng)險等級劃分如表1所示。

表1 事故風(fēng)險等級劃分

改進(jìn)算法的飛行沖突避讓流程如圖1所示。

3 仿真結(jié)果

本文利用Matlab2008進(jìn)行仿真，在100km×100km的空域范圍內(nèi)分別構(gòu)造了單機(jī)沖突場景和雙機(jī)沖突場景，單機(jī)沖突分為45°交叉角和90°交叉角兩種情況，雙機(jī)沖突為兩種角度的綜合。有人機(jī)駕駛的航空器按照飛行計劃飛行。無人機(jī)在空域運行過程中需要避開空域中運行的航空器及各類不可進(jìn)入的空域，T代表訓(xùn)練空域，D代表空中危險區(qū)，F(xiàn)代表空中禁區(qū)，Start為無人機(jī)某一航段起始點，Goal為該航段終點。無人機(jī)沖突解脫安全性評估的運行環(huán)境及飛行路徑如圖2所示。

無人機(jī)沖突解脫過程中各類航空器的綜合軌跡如圖3所示。

圖1 基于改進(jìn)算法的飛行沖突避讓流程圖

圖2 無人機(jī)空域運行環(huán)境

圖3 無人機(jī)沖突解脫示意圖

本文評估對象為無人機(jī)自主沖突解脫技術(shù)，重點是評估其安全性水平，因此，管制員與無人機(jī)操作員的影響因素被去除。而有人機(jī)飛行員并不與無人機(jī)進(jìn)行飛行沖突解脫的協(xié)同，將會駕駛飛機(jī)按計劃飛行，航空器在運行過程中可能會受到風(fēng)、人為因素影響、設(shè)備運行誤差的擾動，在綜合作用下可假定為高斯分布。

本文分別對基本蟻群算法和改進(jìn)蟻群算法的沖突解脫技術(shù)進(jìn)行模擬，分為單機(jī)沖突和雙機(jī)沖突，以檢驗各算法對空域復(fù)雜度增加的情況下的沖突解脫安全性水平，其中單機(jī)沖突按交叉角分為45°交叉角和90°交叉角兩種情況，針對每一種情況分別進(jìn)行10萬次的蒙特卡洛仿真實驗，測試沖突解脫算法的安全性水平，得出的數(shù)據(jù)如下頁表2、表3。

對比表2與表3可以發(fā)現(xiàn)，基本蟻群算法與改進(jìn)蟻群算法在90°交叉角上很好地防止了嚴(yán)重事故和危險接近的發(fā)生，但是改進(jìn)算法在飛行沖突和存在風(fēng)險兩個危險等級上改善不明顯。在單機(jī)45°交叉角和雙機(jī)沖突上，改進(jìn)蟻群算法對比基本算法在事故率上有了很明顯的減少，但按照美軍提出的無人機(jī)運行安全目標(biāo)水平105 h內(nèi)20次事故的標(biāo)準(zhǔn)還有較大的差距［15］。對比ICAO提出的10-7次事故/h的標(biāo)準(zhǔn)則可判定無人機(jī)的安全水平無法達(dá)到有人機(jī)的運行標(biāo)準(zhǔn)。說明改進(jìn)的算法還需針對這一情況進(jìn)行進(jìn)一步的改善，來降低無人機(jī)沖突解脫過程中的風(fēng)險。

表2 基于基本蟻群算法事故率

表3 改進(jìn)算法下的事故率

4 結(jié)論

當(dāng)前國內(nèi)有關(guān)無人機(jī)沖突解脫技術(shù)的文獻(xiàn)較多，但大部分研究都集中在沖突解脫技術(shù)的有效性上，很少有針對沖突解脫安全性方面的驗證，并且目前國內(nèi)針對無人機(jī)空域運行安全評估體系還很缺乏。因此，利用蒙特卡洛方法針對無人機(jī)飛行沖突解脫技術(shù)的安全性進(jìn)行了模擬仿真，仿真結(jié)果有較大改善，但安全性仍然無法滿足空域運行的要求。得出無人機(jī)對45°交叉相遇下的沖突解脫能力存在嚴(yán)重的不足，應(yīng)當(dāng)作為安全瓶頸加以重點研究。本文在構(gòu)建無人機(jī)空域運行環(huán)境的過程中作了很多簡化，與實際環(huán)境具有較大差異，但重點在于引入蒙特卡洛法針對無人機(jī)飛行沖突解脫技術(shù)的安全性進(jìn)行模擬，從安全的角度考慮沖突解脫算法的性能，可以為未來無人機(jī)空域運行安全評估體系的構(gòu)建提供一種理論參考。

［1］陳金良，高文明，史際剛.無人機(jī)飛行管理［M］.西安:西北工業(yè)大學(xué)出版社，2014:1-2.

［2］李春錦，文涇.無人機(jī)系統(tǒng)的運行管理［M］.北京:北京航空航天大學(xué)出版社，2011.5.

［3］SHIN H S，ANTONIOS T，WHITE B A，et al.UAV Conflict Detection and Resolution forStatic and Dynamic Obstacles［C］//Guidance，Navigation and Control Conference and Exhibit.Honolulu，Hawaii:American Institute of Aeronautics and Astronautics，2008.

［4］GARCIA M，VIGURIA A，OLLERO A.Dynamic graph-search algorithm for global path planning in presence of hazardous weather［J］.J Intell Robot Syst，2013，69:285-295.

［5］Eva Crück，JOHN L.Sense and avoid system for a MALE UAV［C］//Guidance，Navigation and Control Conference and Exhibit.Hilton Head，South Carolina:American Institute of Aeronautics and Astronautics，2007.

［6］JOSE A，BRETT R，JESICA U，et al.Unmanned aerial collision avoidance system［R］.George Mason University:Department of Systems Engineering and Operations Research，2006.

［7］王淵，孫秀霞，劉樹光，等.基于改進(jìn)人工蜂群算法的多機(jī)飛行沖突解脫策略［J］.空軍工程大學(xué)學(xué)報（自然科學(xué)版），2014，15（3）:10-14.

［8］崔莉薇，石為人，劉祥明，等.基于遺傳粒子群算法的飛行沖突解脫［J］.計算機(jī)工程與應(yīng)用，2013，49（7），263-266.

［9］陽再清，劉志強(qiáng).艦載無人機(jī)飛行安全性評估方法研究［J］.宇航計測技術(shù)，2014，34（6）:84-89.

［10］魏法杰，盧珊，張羽.某實際型號無人機(jī)試飛風(fēng)險評估案例［J］.中國管理科學(xué)，2014，22（11）:199-204.

［11］吳忠杰，張耀中，王強(qiáng).無人機(jī)復(fù)雜氣象威脅建模及評估方法［J］.計算機(jī)應(yīng)用，2013，33（4）:1179-1182.

［12］魏瀟龍，姚登凱，戴喆，等.基于路徑規(guī)劃的無人機(jī)飛行沖突解脫技術(shù)［J］.火力與指揮控制，2016，41（10）: 48-54.

［13］閆麗萍，夏元清，楊毅.隨機(jī)過程理論及其在自動控制中的應(yīng)用［M］.北京:國防工業(yè)出版社，2012.4

［14］宋錦娟.一種改進(jìn)的蟻群算法及其在最短路徑問題中的應(yīng)用［D］.太原:中北大學(xué)，2013.

［15］張兆寧，王莉莉，李冬賓.飛行間隔安全評估引論［M］.北京:科學(xué)出版社，2009.

UAV Flight Conflict Resolution Safety Assessment Technique Based on Monte Carlo Method

GU Zhi-ming1，GAO Wen-ming2，WEI Xiao-long2，YAO Deng-kai2
（1.Unit 91899 of PLA，Huludao 125001，China；2.School of Air Traffic Control and Navigation，Air Force Engineering University，Xi’an 710051，China）

Conflict resolution technology is a prerequisite for UAV.Aiming at the lack of the safety assessment method of conflict resolution technology，this paper uses Monte Carlo method to simulate the flight conflict and reached the efficiency of conflict resolution algorithm.In this paper，an improved ant colony algorithm is proposed to achieve the flight conflict resolution；using the Monte Carlo method to simulate the flight conflict process and then compare the efficiency with basic ant colony algorithm.The ideas presented in this paper can provide a theoretical reference for the construction of safety assessment system in the UAV airspace operation in the future.

UAV，ant colony algorithm，Monte Carlo，conflict resolution

V271.4

A

1002-0640（2017）04-0158-04

2016-03-16

2016-04-27

省部級自然科學(xué)基金資助項目（2015JM7364）

谷志鳴（1988-），男，河北無極人，碩士研究生。研究方向：空域規(guī)劃與空中交通流量管理。