基于改進精英蟻群算法的無人機三維航跡規(guī)劃*

袁夢順，陳 謀，邵書義，吳慶憲，閆 東

（南京航空航天大學(xué)自動化學(xué)院，南京 211106）

0 引言

隨著無人機技術(shù)的進步，軍用和民用無人機已被廣泛應(yīng)用以完成各種任務(wù)，其智能化是目前主要的發(fā)展方向之一。航跡規(guī)劃是無人機智能化進程中的重要部分，也是智能控制與決策方向研究的熱點。航跡規(guī)劃首先需要滿足約束條件，然后為無人機規(guī)劃出符合需求的航跡。在航跡規(guī)劃問題求解中，常用的搜索算法有A*算法、快速擴展隨機樹算法、群智能算法和人工勢場法。

在航跡規(guī)劃算法中，群智能算法全局搜索能力較強；人工勢場法能夠?qū)λ阉鞣较蜻M行引導(dǎo)，且搜索出的航跡能夠與障礙物保持安全距離。文獻［4］提出了精英蟻群算法，算法中的信息素更新規(guī)則采用雙精英螞蟻策略，提升了算法的快速性。文獻［5］研究了自適應(yīng)蟻群算法，將螞蟻搜索方式調(diào)整為局部搜索，減少了不必要節(jié)點的搜索。人工勢場法在地圖中設(shè)置障礙物斥力場和目標點引力場，文獻［6］利用人工勢場法能夠為無人機規(guī)劃出一條與障礙物保持安全距離的航跡。文獻［7］提出了附加勢場概念，避免了人工勢場法陷入局部極值。

與二維航跡規(guī)劃問題不同，三維航跡規(guī)劃地圖空間大、約束條件復(fù)雜，需在算法快速性和航跡代價之間作出取舍，以滿足實際應(yīng)用場景。解決三維航跡規(guī)劃問題時，文獻［8］中的群智能算法由于起始搜索階段的隨機性，搜索時間較長。文獻［9］中的人工勢場法核心為勢場函數(shù)，需要合理轉(zhuǎn)換后才能應(yīng)用于三維柵格地圖中。

基于以上研究，為了規(guī)劃出一條安全、平滑且代價較小的航跡，本文提出了一種基于精英蟻群算法的改進算法，通過引入人工勢場中的引力場與斥力場，螞蟻的鄰節(jié)點搜索限制，雙精英螞蟻策略，以及信息素擴散模型，加快算法的收斂速度。然后將混沌擾動添加到信息素更新規(guī)則中，增強算法的全局搜索能力。此外，為了處理規(guī)劃出航跡轉(zhuǎn)彎角較多的問題，引入視線算法以平滑航跡。仿真結(jié)果表明，本文算法規(guī)劃出的航跡能夠滿足無人機飛行期望需求。

1 問題描述

無人機航跡規(guī)劃首先需要滿足基礎(chǔ)地圖、威脅區(qū)域和本身物理條件等限制，隨后從起始點開始搜索，規(guī)劃出可以到達目標點的可飛航跡。規(guī)劃空間為三維柵格地圖，每個柵格在算法中都是一個搜索節(jié)點，柵格中心為當前節(jié)點的坐標。因此，航跡規(guī)劃問題可以描述為：在滿足約束條件的前提下，從柵格地圖節(jié)點集合中選擇航跡節(jié)點，使無人機沿航跡節(jié)點飛行時與障礙物保持安全距離，且具有較小的航跡代價。圖1 為二維柵格地圖中的航跡規(guī)劃示意圖，圖中黑色矩形為障礙物，藍色圓形為威脅區(qū)域。

圖1 航跡規(guī)劃示意圖

1.1 約束條件設(shè)置

在算法搜索過程中，螞蟻選擇的鄰節(jié)點必須在無人機性能限制范圍內(nèi)，否則不考慮。設(shè)置約束條件可以省略不符合約束的鄰節(jié)點，減少算法運行時間。對于無人機自身性能限制，參考文獻［11］中的約束條件，本文主要考慮最大轉(zhuǎn)彎角、最大爬升角、最小相對高度和最遠航程約束。對于威脅區(qū)域，本文主要考慮導(dǎo)彈威脅區(qū)域和天氣威脅區(qū)域，其中，天氣威脅為雷暴和強風(fēng)等。

1.2 航跡代價函數(shù)

在航跡規(guī)劃中，航跡代價有多種計算公式本文采用的計算公式如下：

式中，表示航跡段的總數(shù)，L表示第段航跡的位置變化值，此項計算長度代價。G表示進入第段時轉(zhuǎn)彎角度值，此項計算轉(zhuǎn)彎代價。H表示第段的高度變化值，此項計算高度代價。、和分別為長度代價、轉(zhuǎn)彎代價和高度代價的權(quán)重，能夠?qū)桔E搜索產(chǎn)生影響，各項權(quán)重的取值與實際飛行任務(wù)有關(guān)。

2 基于改進精英蟻群算法的三維航跡規(guī)劃

2.1 改進精英蟻群算法基本原理

算法起始時，初始化蟻群數(shù)量和迭代次數(shù)，螞蟻從起始點出發(fā)，按照輪盤賭規(guī)則選擇下一節(jié)點，不斷循環(huán)，直至搜索到終點為止。每有一只螞蟻到達終點，根據(jù)式（1）計算航跡代價，隨后對各節(jié)點的信息素濃度進行調(diào)整。完成一次迭代時，對當代蟻群中代價最小的兩條航跡進行額外的信息素更新，即雙精英螞蟻策略，該策略可以避免蟻群算法過早收斂。

每次迭代完成后，信息素會同時發(fā)生擴散，即在航跡附近柵格擴散信息素，可以使算法更快地搜尋到期望航跡，算法在符合迭代終止條件后，用視線算法對航跡進行全局優(yōu)化，使航跡更加平滑且代價更小，最后輸出滿意的航跡。

2.2 三維航跡規(guī)劃算法具體設(shè)計

在應(yīng)用三維柵格地圖進行航跡規(guī)劃時，鄰節(jié)點搜索范圍為周圍的26 個柵格，通過數(shù)組索引加減即可訪問鄰節(jié)點。在此基礎(chǔ)上，算法設(shè)計主要包括4個方面：啟發(fā)函數(shù)、信息素更新、信息素擴散和航跡優(yōu)化。

2.2.1 啟發(fā)函數(shù)

傳統(tǒng)蟻群算法在初始迭代時，螞蟻搜索節(jié)點是隨機選擇下一節(jié)點，算法收斂速度較慢。在柵格地圖中，算法搜索出的航跡可能會與障礙物邊緣發(fā)生碰撞，本文引入人工勢場法解決這些問題。

為了使算法快速規(guī)劃出航跡，首先為目標點設(shè)置引力勢場，節(jié)點的引力場值Att計算公式可表示為

為了使航跡與障礙物保持安全距離，為障礙物設(shè)置斥力勢場。設(shè)障礙物對以其坐標為圓心，半徑的球體區(qū)域產(chǎn)生斥力，則節(jié)點的斥力場值Rep計算公式如下：

綜合引力場與斥力場，得到的啟發(fā)式函數(shù)計算公式可描述為

圖2 人工勢場圖

由圖2 分析可知，節(jié)點在選擇下一節(jié)點時，傾向于選擇斥力場值和引力場值較大的節(jié)點，示意圖中為斥力場值和引力場值都等于1 的節(jié)點。

2.2.2 信息素更新

信息素更新時，航跡節(jié)點的信息素會揮發(fā)一部分，則節(jié)點在（+1）時刻的信息素濃度計算公式為

式中，控制參量，仿真中取=4。

2.2.3 信息素擴散

圖3 信息素擴散模型

2.2.4 航跡全局優(yōu)化

算法中，螞蟻搜索鄰節(jié)點時，是以柵格為基礎(chǔ)的，所以規(guī)劃出的航跡中轉(zhuǎn)彎角度為固定角度，且轉(zhuǎn)彎較多，需進行全局優(yōu)化。在全局優(yōu)化中，主要運用三維柵格地圖中的視線算法，視線算法在兩點之間連接一條直線，直線經(jīng)過的柵格無障礙物，則判定兩點是可通視的。利用視線算法，當判斷出兩節(jié)點可通視，且省略兩節(jié)點之間的多余節(jié)點后仍滿足無人機約束條件，則將兩節(jié)點直接相連。航跡優(yōu)化如圖4 所示，點虛線為原航跡，長劃虛線為優(yōu)化后的航跡。

圖4 航跡全局優(yōu)化

2.3 改進精英蟻群算法流程

基于改進精英蟻群算法的三維航跡規(guī)劃步驟如下：

1）初始化地圖、信息素濃度矩陣以及參數(shù)；2）對地圖中的障礙物構(gòu)造斥力場；3）將只螞蟻置于起始點；4）每只螞蟻通過狀態(tài)轉(zhuǎn)移策略選擇下一節(jié)點。在鄰節(jié)點集合中，螞蟻會綜合考慮引力場、斥力場和信息素濃度信息進行選擇。其中，鄰節(jié)點集合由符合約束條件的鄰節(jié)點構(gòu)成；5）所有螞蟻是否完成搜索，若否，則返回到步驟4），若是，則執(zhí)行下一步；6）根據(jù)螞蟻搜索到的航跡對地圖節(jié)點上的信息素濃度進行更新，更新規(guī)則中添加了混沌擾動；7）是否符合迭代終止條件，若否，則返回到步驟3），若是，則執(zhí)行下一步；8）利用視線算法進行航跡全局優(yōu)化，輸出最終航跡。

算法具體流程圖如圖5 所示。

圖5 算法具體流程圖

3 仿真結(jié)果與分析

為驗證算法的有效性，以Windows 10 為平臺，Python3.6 語言為編程環(huán)境進行仿真，實驗的硬件平臺為：Intel Core i5 4210M 處理器，主頻2.6 GHz，8 GB 內(nèi)存。在相同硬件平臺的條件下，用不同的地圖對本文算法進行了驗證。同時，為了進一步說明本文算法的作用，進行對比仿真，分析算法的優(yōu)點和缺點。

3.1 算法仿真結(jié)果

仿真中，單個柵格長度、寬度和高度均為100 m。首先在規(guī)格為64×64×64 的柵格地圖1 中，使用本文算法進行航跡搜索。在地圖1 中，山峰1 頂點為（2.05 km，1.85 km，1.15 km），山峰2 頂點為（4.25 km，2.05 km，1.55 km），山峰3 頂點為（3.55 km，4.05 km，2.05 km）。設(shè)定無人機的起始點為（0.15 km，0.15 km，0.25 km），目標點為（6.25 km，6.05 km，1.45 km）。規(guī)劃出的航跡如圖6 所示，其中黑色線段表示規(guī)劃出的無人機航跡。

圖6 地圖1 規(guī)劃航跡

在增加威脅區(qū)域后的柵格地圖2 中，使用本文算法進行航跡搜索。球體威脅區(qū)域為導(dǎo)彈威脅，球體威脅區(qū)域1 中心為（1.05 km，0.85 km，0.35 km），半徑為0.3 km；球體威脅區(qū)域2 中心為（1.05 km，3.05 km，0.55 km），半徑為0.5 km；球體威脅區(qū)域3中心為（3.25 km，0.65 m，0.55 km），半徑為0.5 km；球體威脅區(qū)域4 中心為（3.25 km，3.35 m，0.85 km），半徑為0.3 km。圓柱體威脅區(qū)域為天氣威脅，圓柱體威脅區(qū)域1 平面中心坐標為（4.95 km，5.05 km），半徑為0.5 km，高度為2 km，圓柱體威脅區(qū)域2 平面中心坐標為（0.95 km，5.35 km），半徑為0.5 km，高度為1.5 km。搜索起始點和目標點與之前相同，規(guī)劃出的航跡如圖7 所示。

圖7 地圖2 規(guī)劃航跡

改進精英蟻群算法在不同地圖中，規(guī)劃出航跡的各項指標如表1 所示。

從不同地圖的可視化結(jié)果來看，在圖6 中，本文算法規(guī)劃出的航跡與障礙物能夠保持安全距離，且航跡較為平滑。在添加了威脅區(qū)域后，圖7 中的航跡能夠規(guī)避威脅區(qū)域，航跡較圖6 有改變，但是航跡仍舊平滑安全。由表1 中的數(shù)據(jù)可知，相同規(guī)格地圖，當?shù)匦螐?fù)雜時，航跡代價和搜索時間都會略有增加。通過不同地圖的仿真，在一定時間內(nèi)均能規(guī)劃出符合要求的航跡，所以本文算法能夠有效解決無人機的航跡規(guī)劃問題。

表1 不同地圖航跡數(shù)據(jù)

3.2 對比仿真結(jié)果

在上述規(guī)格為64×64×64 的柵格地圖2 中，搜索起始點和目標點與之前相同，用基礎(chǔ)蟻群算法、文獻［13］中的改進蟻群算法和本文算法進行對比仿真。文獻［13］算法規(guī)劃出的航跡如圖8 所示。

圖8 文獻［13］算法規(guī)劃航跡

不同算法規(guī)劃出航跡的各項指標如表2 所示。

表2 不同算法航跡數(shù)據(jù)

將圖8 與本文算法規(guī)劃的航跡圖比較，本文算法規(guī)劃出的航跡比較平滑，轉(zhuǎn)彎角較少，符合無人機約束條件，效果較好。分析表2 數(shù)據(jù)可知，基礎(chǔ)蟻群算法表現(xiàn)較差，算法搜索時間較長，航跡節(jié)點數(shù)較多，航跡長度較長。因為基礎(chǔ)蟻群算法航跡節(jié)點之間必須是相鄰柵格，所以航跡節(jié)點數(shù)眾多，且算法中沒有對目標點的啟發(fā)函數(shù)，所以搜索時間較長。文獻［13］算法搜索時間較短，航跡節(jié)點數(shù)較多，航跡長度略短，因為算法僅添加了啟發(fā)函數(shù)。本文算法航跡代價最小，航跡節(jié)點數(shù)明顯減少，且搜索時間最短。算法的提升在于以下方面，首先將人工勢場法與啟發(fā)函數(shù)結(jié)合，添加到轉(zhuǎn)態(tài)轉(zhuǎn)移策略中，提升了算法快速性；其次通過雙精英策略和信息素擴散，進一步減少搜索時間；同時在信息素更新中加入混沌擾動，增強全局搜索能力；最后利用視線算法進行中間節(jié)點的省略，減少了航跡節(jié)點數(shù)，且降低了航跡代價。

4 結(jié)論

本文提出了一種以精英蟻群算法為基礎(chǔ)改進的算法，設(shè)置斥力場使無人機與障礙物保持安全距離，設(shè)置引力場使算法快速規(guī)劃出期望航跡。在細節(jié)方面，設(shè)計了算法的啟發(fā)函數(shù)、鄰節(jié)點搜索、信息素更新、信息素擴散和視線算法。將完成設(shè)計的算法應(yīng)用到三維柵格地圖中，最終規(guī)劃出滿意航跡。隨后與其他蟻群算法規(guī)劃出的航跡進行對比，本文算法規(guī)劃速度較快，航跡平滑，航跡代價小且航跡安全。本文提出的算法為三維靜態(tài)環(huán)境中的航跡規(guī)劃算法，能夠為無人機規(guī)劃出符合需求的航跡，后續(xù)將調(diào)整算法中的參數(shù)，從而減少算法的運行時間。