不確定環境下無人機多任務區偵察決策研究

張耀中, 胡波, 李寄瑋, 張建東

(西北工業大學 電子信息學院, 陜西 西安 710129)

不確定環境下無人機多任務區偵察決策研究

張耀中, 胡波, 李寄瑋, 張建東

(西北工業大學 電子信息學院, 陜西 西安 710129)

針對不確定性環境下多任務區的遍歷偵察決策問題,結合無人機攜帶任務載荷及待偵察任務區的特性,建立了相應的偵察收益函數,根據無人機攜帶偵察載荷的任務工作時間約束以及每個任務區的最小偵察收益需求,同時保證遍歷偵察所有任務區的條件下,提出了一種改進的布谷鳥搜索算法為每個待偵察任務區分配最優的偵察載荷工作時間,從而使整個偵察任務過程的信息收益最大化。最后通過數字仿真驗證了無人機多任務區偵察決策方案的可行性,通過與標準布谷鳥搜索算法對比分析,表明改進后的布谷鳥搜索算法對此類決策問題的求解效率比標準布谷鳥搜索算法及傳統的遺傳算法都有較大提高,從而為無人機進行多任務區的最優化遍歷偵察問題提供了科學的決策依據。

無人機;偵察收益;改進布谷鳥算法

在美軍無人機Unmanned Aerial Vehicle (UAV)路線圖2005-2030中指出,在現代戰爭中信息收集任務是一項危險而復雜的任務,UAV能夠代替人類在該領域發揮重要作用。大量的應用實踐已經表明,UAV因其低廉的成本和良好的機動性與隱身性已經成為現代戰場上廣泛使用的一種偵察手段。UAV在任務偵察階段能夠代替有人機執行“危險、惡劣、枯燥”的任務[1-2],已被廣泛應用于戰場偵察、對地打擊、城市反恐、地震救援、以及海上搜救等眾多領域。UAV對地偵察是指通過UAV機載成像系統或其他偵察載荷,及時獲取指定區域情報信息的過程[3]。如何在UAV執行偵察任務之前進行相應的任務規劃,提高UAV的任務執行效率已經成為一個熱點問題。文獻[4]重點解決了在考慮3D環境和禁飛區限制條件下,如何獲取到目標區域的最大偵察信息,提出了相應的多UAV路徑規劃模型并給出了改進的遺傳算法求解方案。文獻[5]提出了一種基于新的“自適應”進化多目標優化方法的多基地多UAV協同偵察任務規劃算法。相關文獻都在不同程度上研究了無人機航路規劃和偵察搜救問題,并取得了一定的成果。由于在復雜的戰場環境中、地震之后的災情分析中、大面積海域的偵察搜救中,都有眾多的任務區需要UAV去執行信息收集任務,如何進行有效的任務規劃決策是當前研究的熱點問題之一[6-13]。但UAV的任務工作時間及載荷工作能力都是有限的,通常難以完成對所有任務區的完全信息偵察任務,在實際任務中通常我們也不需要對任務區執行完全偵察,只要偵察到的情報信息滿足一定要求即可。因此,如何快速有效地完成對所有任務區的非完全信息遍歷偵察是本文的研究重點。基于以上所述,本文提出將一種改進的新興仿生計算算法——布谷鳥搜索算法[14-15]應用到UAV多任務區偵察決策問題中,有效解決了對該類問題求解的快速性及有效性,從而為工業應用提供了決策依據。

1 問題描述

在軍事情報偵察、區域反恐、地震救援以及海上搜救等有關任務中,經常需要單架UAV對有關區域中的多個關注任務點區域進行相關的信息偵察。在UAV自身性能、任務時間及偵察載荷的工作能力約束條件下,如何最有效地規劃各個關注任務點區域的載荷工作時間分配對偵察任務的完成效果有至關重要的影響。假定在任務場景中存在N個待偵察的關注任務區,已知N個待偵察任務區的位置信息、區域信息和UAV攜帶的偵察載荷信息并需要滿足最大偵察載荷工作時間限制。如圖1所示。

圖1 UAV多任務區偵察規劃示意圖

對任務區域的偵察收益主要通過UAV獲取的偵察情報來體現,而偵察情報的獲取主要跟UAV在任務區域偵察的時間相關,時間越長,偵察所獲得情報越多,反之,時間越短,獲取到的偵察情報也越少。

2 UAV多任務區偵察決策問題建模

為了分析問題方便,做如下的變量定義:

n: 任務場景中的待偵察任務區數量(含UAV起飛基地);

M: 起飛基地與偵察任務區集合M={1,2,3…n},節點1表示起飛基地,節點M{1}表示待偵察任務區集合;

(xi,yi): 第i個任務區中心的位置坐標,i∈M,(x1=0,y1=0);

Si: 第i個任務區域的面積,i∈M,假定任務區為長方形區域;

ci: 第i個任務區的價值系數,i∈M,其中c1=0;

w: UAV攜帶偵察載荷的掃描寬度;

v: UAV的任務飛行速度,設為固定值;

T: UAV攜帶偵察載荷的最大工作時間;

Gimin: 對第i個任務區進行偵察必須達到的最小信息收益,i∈M,G0min=0;

Gi(t): 對第i個任務區進行t時間偵察獲得的信息收益;

Gmax:對所有任務區進行偵察獲取的最大信息收益;

ti:為第i個任務區分配的載荷偵察時間,i∈M,其中t1=0。

2.1 UAV偵察信息確定性指標模型

UAV對任務區偵察的目的是為了獲得有效信息從而降低對任務區域的不確定性,一般情況下,UAV對任務區進行偵察時都處于復雜的不確定性環境下,由于UAV任務飛行時間及偵察載荷工作時間的限制,通常難以保證對每個任務區域都能做到完全信息偵察。為了有效衡量偵察載荷在特定時間內對任務區偵察的信息收益,本文提出了采用信息確定性指標來衡量特定時間內對任務區的偵察收益,信息確定性指標主要跟UAV在任務區域的偵察時間、偵察載荷的工作能力等有關,如下所示

G(t)=G0+G1(1-e-βt)

(1)

G0+G1=1

(2)

式中:G0為偵察開始前UAV對任務區域的信息確定性部分,0≤G0<1;G1為偵察開始前UAV對任務區域的信息不確定性部分;β為偵察載荷對任務區域的偵察能力指數,主要由偵察載荷的固有能力與待偵察任務區的性質決定。

本文中為了便于分析,將載荷的偵察能力指數β定義如下

(3)

式中，s′為偵察載荷單位時間內的有效偵察面積;s為待偵察任務區的面積大小。

任務載荷在單位時間內的有效偵察面積s′表示為

s′=w·v

(4)

式中:w為任務載荷對任務區的有效掃描寬度;v為UAV的任務飛行速度。

綜上所述,可把(3)式表示為下式

(5)

2.2 UAV多任務區偵察收益模型

在多任務區偵察環境下,每一個任務區i都有相應的偵察價值系數,根據任務區性質的不同分配不同的價值系數ci。UAV多任務區總偵察收益表示UAV對所有任務區域進行偵察后的綜合收益,收益大小表示UAV偵察多個任務區域時,獲得的總信息量,收益值越大,表示UAV偵察獲得的有效信息越多,對所有偵察區域的綜合信息確定性就越大。而每一個任務區i的偵察收益則主要由分配給該任務區的載荷偵察時間ti確定,多任務區域的偵察時間規劃問題可以表示為如下的最優化問題(假定偵察開始前UAV對任務區域的信息確定性部分為0)

(6)

其中約束條件為

(7)

G(ti)≥Gimin, i=1,2,3,…,n

(8)

(9)

式中,約束方程(8)為每個任務區需要滿足的最小偵察收益約束,約束方程(9)為UAV對所有任務區的任務偵察時間約束不能大于所攜帶偵察載荷的有效工作時間。這里規定了UAV對于每個任務區的偵察都應有一個最小偵察收益的限制,即使得UAV偵察完該任務區后獲得的情報信息不至于過少或者沒有,從而導致對該任務區的偵察情報信息失去實用價值。

3 CSA算法的改進策略

在UAV多任務區偵察決策問題中,針對任務區的偵察時間規劃問題屬于連續時間約束的非線性規劃問題,由Yang等人提出來的仿生算法——布谷鳥搜索算法(cuckoo search algorithm,CSA)在解決此類問題中具有較高的計算性能,但是標準的布谷鳥搜索算法完全依賴于隨機搜索步長,難以保證其快速收斂性,因此,本文提出一種基于偵察收益的自適應步長搜索策略來改進布谷鳥搜索算法(improved cuckoo search algorithm,ICSA)對所提出的規劃問題進行求解。

3.1 布谷鳥搜索算法(CSA)

CSA算法是由Yang Xinshe和Suash Deb于2009年受到自然界中的寄生繁殖行為影響而提出的一種新興仿生智能優化算法。主要包括最優選擇、局部隨機擾動、全局Lévy飛行進行隨機選擇3個過程要素[15]。

1) 最優選擇

通過保留最好的鳥窩或最優解來選擇最優,類似于遺傳算法中的精英保留主義,確保了搜索移動在局部最優解的領域范圍內進行,保證了最優解被保留到下一代而且不會有被逐出種群的危險。

2) 局部隨機擾動

局部隨機擾動過程可以描述為

(10)

3) 基于全局Lévy飛行的隨機選擇過程

全局隨機搜索過程按Lévy飛行過程進行,即

?L(β)

(11)

(12)

式中，u和v都服從正態分布,即

3.2 改進的布谷鳥搜索算法(ICSA)

經過大量的標準算例測試,標準CSA算法都能較快獲得問題的全局最優解,但是標準算法中的部分參數在初始化步驟中被設定為固定值,在特定問題的求解過程中容易使搜索過程中的局部尋優性能減弱,從而導致全局收斂速度變慢。本文提出對算法中的α和β參數進行改進,根據搜索過程的不同階段來自適應的調整這2個參數的取值,使得在早期迭代過程中取值足夠大以增強解的多樣性,而在迭代過程的后期自適應減小以更好地進行局部搜索。

1) 基于偵察收益的自適應步長搜索因子

在標準CSA算法中α通常取常量1,容易導致算法的性能和局部收斂速度變慢。因此引入如下的自適應步長搜索因子

(13)

2) 基于偵察收益的自適應搜索比例因子

β主要決定了解的分布狀況,引入如下的自適應搜索比例因子

(14)

通過對CSA算法中參數的改進,可以有效地使個體或鳥蛋自適應的逐漸靠近最優解,在初期執行更多的全局搜索而后期則轉向更多的局部搜索。由于CSA算法參數少,搜索完全依賴隨機步長,改進后的CSA算法相較于標準CSA算法具有更快的收斂速度。

3.3 ICSA的算法流程

采用改進后的CSA算法進行多任務區偵察規劃求解的具體流程如下:

Step 1 初始化算法參數(種群數量n、宿主鳥發現外來鳥蛋的概率pa、最大迭代次數、β0);

Step 2 隨機產生n個鳥窩;

Step 3 計算每個鳥窩的適應度Fi,并記錄鳥窩個體極值及相應最佳鳥窩;

Step 4 如果達到最大迭代次數,轉向Step 8,否則算法繼續;

Step 5 通過公式(12)、(13)得到新的解,同時保留當前最優解,記錄此時的鳥窩極值;

Step 6 以概率pa拋棄較差鳥窩,并通過公式(11)在局部建立全新的鳥窩,記錄此時的鳥窩極值;

Step 7 迭代次數加1,并轉向Step 4;

Step 8 算法停止并輸出最優解。

4 仿真實驗

1) 仿真場景想定

以高空長航時偵察型無人機對任務場景中多個固定任務區進行不完全信息遍歷偵察為例,對本文所提出的算法進行仿真驗證與分析。為便于說明問題,設偵察前對任務區的信息完全未知,待偵察任務區的面積已知且不隨仿真過程而變化,UAV在二維平面內運動且不考慮地面威脅源的影響。任務場景為300 km×300 km的戰場環境,UAV起飛基地的坐標為(0,0)偵察載荷的最大任務工作時間為25 h,對偵察區域的有效掃描寬度為0.3 km,UAV飛行速度220 km/h,戰場環境中的待偵察任務區為16個,任務區有關屬性信息設置如表1所示。

表1 待偵察任務區屬性信息設置表

仿真環境為Intel 2.53GHz主頻,2G內存的PC機,Windows 7操作系統,Matlab2010a軟件。設定ICSA算法的最大迭代次數為500次,種群數量為20,宿主鳥發現鳥蛋的概率為0.25。

2)仿真算列1

設定所有的待偵察任務區重要程度一樣,要求對每個任務區的偵察收益都不能小于0.25,通過仿真計算,完成全部任務區偵察的總信息收益為6.439 9,對每個待偵察任務區的偵察時間分配及相應的偵察信息收益見表2、圖2及圖3。

表2 任務區偵察信息時間/收益信息

圖2 算例1偵察時間分配結果

3)仿真算列2

如果有T1、T9、T153個任務區需要重點偵察,要求的最小偵察收益不能小于0.55,其余任務區的偵

圖3 算例1偵察收益圖

察收益不能小于0.25。通過仿真計算,此時完成全部任務區偵察的總信息收益為6.295 4,對每個待偵察任務區的偵察時間分配及相應的偵察信息收益見表3、圖7及圖8。

表3 任務區偵察信息時間/收益結果

由仿真結果可知,改進的CSA算法為各個任務區分配的偵察時間滿足任務要求,同時UAV對每個任務區的偵察收益都不小于各個任務區所要求的最小偵察收益。

為了測試ICSA算法的性能,在上述仿真條件下分別采用了ICSA算法、標準CSA算法,遺傳算法進行了仿真對比分析,3種算法的進化收斂曲線如圖6所示。

圖4 算例2偵察時間分配結果 圖5 算例2偵察收益圖圖6 不同算法時偵察收益進化曲線

從仿真結果可以看出,ICSA算法為各個待偵察任務區分配的偵察時間滿足約束要求,UAV對每個待偵察任務區的偵察收益都不小于預定的最小偵察收益約束,同時最大限度的使用了偵察載荷的可用工作時間。從ICSA、CSA及GA 3種算法求解目標函數最優值的進化曲線中可以看出,相對于標準CSA算法和GA算法,改進的布谷鳥搜索算法具有收斂速度快的優點,能夠在較小的迭代次數下達到收斂。算法能夠快速有效地給出最優的多任務區偵察任務決策方案。

5 結 論

本文針對UAV多任務區域的偵察決策問題,提出了任務區偵察信息確定性指標,建立了多任務區偵察決策的數學模型,進行了相應的仿真分析,仿真結果表明,該方法可以在UAV偵察載荷工作時間約束下獲得對任務區域綜合偵察收益最大化的決策方案。

由于單架UAV攜帶載荷偵察能力的局限以及戰場環境與任務區域的復雜性,使得單架UAV常常難以有效的對全部偵察任務區實施滿意的偵察信息收集。因此,在后續工作中,將對異構型多UAV攜帶多種載荷對多任務區域的協同偵察問題展開進一步的研究。

[1] Unmanned Systems Integrated Roadmap FY2013-2038[J]. Department of Defense, 2013

[2] Robert L,Yi B,Tim B. UAVs in Civil Airspace: Safety Requirements[J]. IEEE Aerospace & Electronic Systems Magazine,2009,1(9): 5-17

[3] 許友平. 無人機對地偵察/攻擊航路規劃軟件系統的研制與研發[D]. 南京:南京航空航天大學, 2013 Xu Youping. Research and Development on Route Planning in UAV′s Tasks of Reconnaissance and Air-to-Ground Attack[D]. Nanjing, Nanjing University of Aeronautics and Astronautics, 2013 (in Chinese)

[4] Halit Ergezer, M Kemal Leblebiciolu. 3D Path Planning for UAVs for Maximum Information Collection[C]∥2013 International Conference on Unmanned Aircraft Sysytems(ICUAS), Atlanta, 2013

[5] 田菁,沈林成. 多基地多無人機協同偵察問題研究[J]. 航空學報,2007,26(4):913-921 Tian Jing, Sheng Lincheng. Research on Mnlti-Base Mnlti-UAV Cooperative Reconnaissance Problem[J]. Acta Aeronautica et Astronautica Sinica, 2007, 26(4): 913-921 (in Chinese)

[6] Adel Guitouni, Masri H. An Orienteering Model for the Search and Rescue Problem[J]. Springer, 2014,11(10): 459-473

[7] Manisha Mishra, Xu Huan, David Sidoti. Multi-Objective Coordinated Path Planning for a Team of UAVS in a Dynamic Environmet[C]∥19th ICCRTS:C2 Agility:Lessons Learned from Research and Operations, Alexandria, 2014

[8] Ma Jingyan, Zhang Kehong. Research on TSP Solution Based on Genetic Algorithm of Logistic Equation[C]∥2010 2nd International Conference on Computer Science and Network Technology, Wuhan, 2010: 738-742

[9] Jeremy Baxter, Scott Findlay, Martin Paxton. Scheduling UAV Surveillance Tasks,Lessons Learnt from Trials with Users[C]∥2013 IEEE International Conference on Systems,Man and Cybernetics, Manchester, 2013

[10] Hyo-Sang Shin, Cedrice Leboucher, Antonios Tsourdos. Resource Allocation with Cooperative Path Planning for Multiple UAVs[C]∥2012 UKACC International Conference on Control, Cardiff, 2012

[11] Durdana Habib, Shoab A. Khan,Habibullah Jamal, Collaborative Path Planning for Multiple Unmanned Aerial Vehicles in Dynamic Environment[C]∥The 2011 Signal Processing, Communications and Computing, Xi′an, 2011

[12] Sujit P B, Joao Sousa, Fernando Pereira.Multiple UAV Teams for Multiple Tasks[C]∥The 2009 IEEE Symposium on Computational Intelligence in Security and Defense Applications, Ottawa, 2009

[13] Luca F Bertuccelli, Han-Lim Choi, Peter Cho. Real-Time Multi-UAV Task Assignment in Dynamic and Uncertain Environment[C]∥AIAA Guidance, Navigation, and Control Conference Chicago Chicago Illinois, 2009

[14] Yang Xinshe, Deb Susan. Cuckoo Search:Recent Advances and Applications[J]. Neural Computing and Applications, 2014,24(1):169-174

[15] Yang Xinshe. Cuckoo Search and Firefly Algorithm[M]. Poland, Polish Academy of Sciences, 2014: 49-195

[16] Yang X S, Deb S. Engineering Optimization by Cuckoo Search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 21(2): 330-343

[17] Aziz Ouaarab,Belaǐd Ahiod, Yang Xinshe. Discrete Cuckoo Search Algorithm for the Traveling Salesman Problem[J]. Neural Computing and Applications,2014,7(24):1659-1669

[18] Marichelvam M K, Prabaharah T, Yang X S. Improved Cuckoo Search Algorithm for Hybrid Flow Shop Scheduling Problems to Minimize Makespan[J]. Applied Soft Computing, 2014,19(1): 93-101

[19] Yang Xinshe, Deb Suasn. Cuckoo Search via Lévy Flights[C]∥2009 World Congress on Nature & Biologically Inspired Computing, India, 2009

UAV Multi-Mission Reconnaissance Decision-Making under Uncertainty Environment

Zhang Yaozhong, Hu Bo, Li Jiwei, Zhang Jiandong

(School of Electronics and Information, Northwestern Polytechnical University, Xi′ an 710129, China)

In this paper, the multi-mission reconnaissance decision-making problem under uncertainty environment is considered, where a team of Unmanned Air Vehicle (UAV) must perform search and rescue missions on a set of geographically dispersed areas in the region of interest. According to the task locations, performance of UAV itself and operational time of the reconnaissance payload, this optimal reconnaissance time schedule problem requires the UAV to balancing the reconnaissance gains among the multi-task areas in order to generate a plan that is efficient, with respect to overall mission duration and satisfies all problem constraints. For this optimal time schedule problem, we formulate a new algorithm that is based on Improved Cuckoo Search Algorithm (ICSA). Simulation results show that the proposed algorithm can solve the problem effectively, and compared with classic genetic algorithm, it is also more efficiency.

unmanned aerial vehicle(UAV); reconnaissance gains; improved cuckoo search algorithm(ICSA)

2016-04-01

西北工業大學研究生創意創新種子基金(Z2016125)資助

張耀中(1974—)，西北工業大學副教授，主要從事火力控制原理、復雜系統建模與仿真、無人機任務規劃等研究。

TP311.5

A

1000-2758(2016)06-1028-07