任 智, 張 棟,*, 唐 碩

(1. 西北工業(yè)大學航天學院, 陜西 西安 710072; 2. 陜西省空天飛行器設計重點實驗室, 陜西 西安 710072)

0 引 言

飛行器飛行前預先裝訂的規(guī)劃航跡難以應對瞬息萬變的戰(zhàn)場態(tài)勢,在實際飛行過程中需根據戰(zhàn)場實時態(tài)勢對航跡進行在線規(guī)劃與動態(tài)調整。在線航跡規(guī)劃技術是在滿足飛行性能約束與戰(zhàn)場環(huán)境約束等條件下求解規(guī)劃航跡,是提高飛行器在復雜戰(zhàn)場環(huán)境中生存能力與任務完成能力的關鍵技術,對規(guī)劃算法的實時性與規(guī)劃結果最優(yōu)性有更高的要求。常見航跡規(guī)劃方法包括:人工勢場法[1]、遺傳算法[2]、群智能算法[3-6]、A*算法[7]等。其中,A*算法原理簡單且規(guī)劃結果穩(wěn)定可靠,已被廣泛應用于工程實踐中[8]。

近年來,國內外學者對A*算法的研究與改進主要從啟發(fā)函數設計、拓展節(jié)點策略和數據處理方法3個角度出發(fā)。文獻[9]通過調整啟發(fā)函數中啟發(fā)信息的權重,增加少許計算時間，以換取航跡結果的優(yōu)化。文獻[10]引入了跳點搜索的拓展節(jié)點方法,通過對搜索空間直線和對角線方向上冗余節(jié)點的有效剪枝,提升二維柵格空間的搜索速度。文獻[11]采用動態(tài)矩形的雙向搜索路徑方法,進一步提升了算法的遍歷速度。文獻[12]通過引入對算法性能的評價標準為改進A*算法選擇了合適的參數,提升了算法的魯棒性。上述改進方法針對的是二維空間下的航跡規(guī)劃場景,而三維空間規(guī)劃的航跡節(jié)點數目更多,計算量更大。文獻[13]針對動態(tài)環(huán)境下無人航跡規(guī)劃問題，將稀疏A*算法嵌入到即時修復式架構,實現規(guī)定時間內可行航跡的生成與威脅連續(xù)機動下的在線航跡規(guī)劃。文獻[14]基于指數衰減的方法，調整A*算法在搜索節(jié)點過程中啟發(fā)信息的權重,改進方法能夠適應不同的環(huán)境。

隨著人工智能技術的發(fā)展,強化學習方法在無人系統導航與控制領域得到深入應用[15]。強化學習在航跡規(guī)劃問題中的應用方法主要包括:直接依據具體航跡規(guī)劃問題建立強化學習模型[16-19],常結合深度神經網絡等方法對強化學習方法進行優(yōu)化,但效果有限且訓練結果不穩(wěn)定、變化大[20-23];結合強化學習方法對傳統智能算法進行參數優(yōu)化設計,能夠有效解決傳統智能算法早熟收斂、多樣性不足、難以確定搜索參數等問題[24-27]。

考慮到實際戰(zhàn)場環(huán)境下的規(guī)劃任務需求,飛行器在線航跡規(guī)劃問題并不追求得到問題的最優(yōu)解,而是盡可能快地得到可行解。因此,區(qū)別于傳統改進方法中對啟發(fā)信息的加權,引入收縮因子改進A*算法代價函數。由于復雜地形環(huán)境對多約束條件下A*算法性能有著巨大影響,在不同任務場景中難以根據工程經驗確定收縮因子的大小。對于遺傳算法、梯度優(yōu)化等傳統優(yōu)化算法而言,難以結合A*算法的整體規(guī)劃過程對其航跡最優(yōu)與求解效率構建目標優(yōu)化模型,僅能夠針對特定任務場景下的A*算法收縮因子進行優(yōu)化,故優(yōu)化結果不具備通用性。而深度確定性策略梯度(deep deterministic policy gradient, DDPG)方法能夠綜合利用神經網絡與強化學習無模型學習的優(yōu)勢,以提升算法綜合性能為訓練目標設計獎勵函數,無需構建具體優(yōu)化模型,將A*算法整體規(guī)劃作為學習訓練的抽象環(huán)境,利用神經網絡擬合改進A*算法代價函數的收縮因子。因此,首先建立A*算法時間性能與最優(yōu)性能變化度量模型;然后，結合DDPG方法設計神經網絡與A*算法搜索的復合架構,對不同任務場景收縮因子策略進行訓練;最后，在線飛行時依據離線訓練結果確定的收縮因子進行三維A*算法在線航跡規(guī)劃。

1 問題描述與分析

1.1 航跡規(guī)劃模型

在線航跡規(guī)劃首先需要考慮戰(zhàn)場環(huán)境約束條件,通過對拓展節(jié)點的篩選實現算法搜索空間的剪枝。典型戰(zhàn)場環(huán)境約束條件包括地面地形約束、禁飛區(qū)約束、平臺安全約束等[28-29]。此外,規(guī)劃航跡節(jié)點的拓展與自身飛行性能約束緊密結合,確定了航跡節(jié)點在規(guī)劃空間中的搜索邊界。典型飛行性能約束條件包括最短航跡長度約束、最小轉彎半徑約束與最大轉彎角約束、最大俯仰角約束以及機動能力約束。

(1)

式中:第一式表征最短航跡長度約束,lmin為由飛行器自身性能確定的最小航跡長度,h為拓展節(jié)點步長,hmin為最小步長;第二式表征最小轉彎半徑約束,φ為航向角,βmax為最大轉彎角,PiPi+1=(xi+1-xi,yi+1-yi,zi+1-zi)表征由相鄰節(jié)點確定的航跡片段;第三式表征最大俯仰角約束,αmax為最大俯仰角,z為節(jié)點高程值;第四式表征機動性能約束與飛行器飛行過程中其他約束的參數關系,v為飛行速度,nmax為最大可用過載,g為重力加速度。

1.2 三維A*算法拓展方式

結合航跡規(guī)劃模型中建立的飛行性能約束,航跡節(jié)點在三維空間中以生成樹的方式展開，進行拓展搜索。搜索過程具體為：以當前點為球心、搜索步長為半徑的球面上對上、下、左、右、前與斜對角等9個方向進行搜索,則當前飛行器飛行至第k個航跡節(jié)點時在發(fā)射坐標系下的姿態(tài)角為

(2)

為保證拓展節(jié)點的搜索粒度,可考慮將水平方向和垂直方向上的搜索范圍按角度等分。由此,根據算法步長與俯仰角和轉彎角約束，將規(guī)劃空間離散成可供拓展的航跡節(jié)點。各節(jié)點包括高程坐標信息、俯仰角、轉彎角和評價函數值的六要素信息。設當前搜索節(jié)點Pcur(xcur,ycur,zcur,αcur,βcur,Fcur),對應父節(jié)點Ppar(xpar,ypar,zpar,αpar,βpar,Fpar),拓展節(jié)點為Pnext={Pnext,i|i=1,2,…},拓展方式如圖1所示。

圖1 拓展方式示意圖Fig.1 Schematic diagram of expansion mode

1.3 三維A*算法代價函數

A*算法在Dijkstra算法的基礎上,采用貪心策略,通過在搜索過程中引入啟發(fā)信息,使搜索節(jié)點趨向于最優(yōu)路徑。代價函數包括當前節(jié)點到起始點的路程信息和當前節(jié)點到目標節(jié)點的啟發(fā)信息兩個部分。在傳統代價函數改進中對啟發(fā)信息加權,具體形式為

f=fg+ε·fh

(3)

式中:fg為采用曼哈頓方法確定的當前節(jié)點到起始點間的路程代價;fh為當前節(jié)點到目標點的啟發(fā)信息;ε為啟發(fā)信息在代價函數中的權重系數。當ε=1時,代價函數中的啟發(fā)信息與路程信息的量級相同,此時為標準A*算法；當ε>1時,代價函數中啟發(fā)信息膨脹,隨著ε的增大,航跡節(jié)點的搜索拓展更傾向于目標搜索節(jié)點,最終航跡規(guī)劃結果的航跡長度增加,求解時間減小。這表明:權重系數的增大能夠通過犧牲規(guī)劃結果最優(yōu)性來提升算法時間性能。特別地,當ε=0時，標準A*算法退化為Dijkstra算法。

雖然啟發(fā)信息的加權能夠提升算法實時性能,但隨著加權系數的增大,代價函數值在A*算法列表搜索時也隨之存在數值爆炸的問題,影響搜索效率。因此,將啟發(fā)信息的權重系數轉換為路程代價的收縮因子,使得權重系數限定在有限區(qū)間內,避免搜索過程中列表代價函數值爆炸,代價函數變形為

(4)

式中：ω為路程信息在代價函數中的收縮因子,表征當前路程代價的權重。本文后續(xù)針對路程代價的收縮因子展開對代價函數權重系數的優(yōu)化設計。

2 結合DDPG的改進A*算法

2.1 強化學習模型

強化學習的本質是當前研究的對象(智能體)與環(huán)境的交互。智能體通過對環(huán)境的感知確定當前的狀態(tài),依據既定策略在環(huán)境中選擇動作,進而完成智能體的動作-狀態(tài)轉移。在智能體與環(huán)境的交互過程中,通過值函數對智能體選擇策略進行獎懲,實現滿足目標期望的迭代學習優(yōu)化,使得智能體最終能夠獲得最多的累計獎勵。本節(jié)根據研究問題與對象設計智能體、狀態(tài)、動作等概念,建立強化學習模型。

2.1.1 動作-狀態(tài)設計

考慮本文研究對象與內容,在A*算法求解航跡規(guī)劃過程中,收縮因子的大小影響了規(guī)劃結果最優(yōu)性和時間性能。其中,由于A*算法中的節(jié)點拓展搜索方法采取定步長策略,規(guī)劃航跡結果長度與航跡節(jié)點數目成正比,故可將航跡長度最優(yōu)問題轉化為航跡節(jié)點數目最優(yōu)問題。因此,強化學習模型中的智能體即為概念實體A*算法,對應的狀態(tài)即為A*算法的算法時間性能和規(guī)劃結果最優(yōu)性能在當前收縮因子影響下的優(yōu)化程度,動作即為選定的收縮因子,則動作-狀態(tài)空間映射可表示為

A={ω|ω∈[0,1]}→S={st,se}

(5)

式中:A為智能體動作集;S為智能體狀態(tài)集;st為A*算法時間性能在當前選定收縮因子下相對于標準A*算法時間性能的變化量;se為A*算法最優(yōu)性能在當前選定收縮因子下相對標準A*算法最優(yōu)性能的變化量。

記t為A*算法在當前選定收縮因子下進行航跡規(guī)劃所需的時間;e為A*算法在當前選定收縮因子下進行航跡規(guī)劃最終結果的航跡節(jié)點數目。算法性能變化的衡量以收縮因子w=1時對應的標準A*算法性能為基準,量化百分比指標為

(6)

式中：si為當前縮減因子條件下A*算法航跡規(guī)劃后的性能參數提升百分比;sori為改進前標準A*算法對應的性能參數;simp為引入收縮因子后改進A*算法對應的性能參數。

2.1.2 獎勵函數設計

獎勵函數的設計是強化學習模型的難點,決定了強化學習方法在學習迭代后最終收斂的期望與目標。在本文的研究問題中,獎勵函數是衡量收縮因子的選取對A*算法時間性能和結果最優(yōu)性能影響的數學模型,反映了在解決飛行器航跡規(guī)劃問題時對A*算法時間性能與航跡最優(yōu)性能的需求與側重。兩者變化的歸一化度量為

(7)

考慮飛行器航跡規(guī)劃問題對算法時間性能與結果最優(yōu)性能的要求,設計評價函數:

(8)

考慮獎懲關系,時間性能提升程度越大則給定獎勵,最優(yōu)性能降低程度越大則給定懲罰,結合式(6)設計獎勵函數:

(9)

2.2 結合DDPG的改進方法

2.2.1 DDPG原理[30]

強化學習方法的基本過程是通過策略優(yōu)化迭代進行動作狀態(tài)轉移，從而實現最大獎勵總和,DDPG采用Actor-Critic方法架構結合神經網絡和梯度策略(policy gradient, PG)。一方面,在策略函數μ模擬的卷積神經網絡中,即Actor動作估計網絡(策略網絡),采用行為策略β和離線(off-policy)生成狀態(tài)動作轉移策略經驗回放的訓練數據集;另一方面,在狀態(tài)價值函數Q模擬的卷積神經網絡中,即Critic狀態(tài)估計網絡(Q網絡),在策略網絡訓練數據集基礎上進行采樣,進而迭代學習得到最優(yōu)策略。區(qū)別于PG方法選擇動作的概率策略,DDPG方法采用確定性的行為策略β。特別地,在策略網絡參數的訓練過程中,動作決策采用Ornstein-Uhlenbeck隨機過程引入噪聲,通過時序相關的隨機探索,提升算法對潛在更優(yōu)策略的探索效率。

(10)

yt=E[Qμ(st,at)]=

(11)

(12)

(13)

(14)

通過上述損失函數計算函數梯度并更新對應網絡的權值,采用軟更新方法將網絡參數從當前網絡更新到目標網絡:

θμ-←τ·θμ+(1-τ)·θμ′

(15)

θQ-←τ·θQ+(1-τ)·θQ′

(16)

式中:τ為軟策略更新因子。

2.2.2 收縮因子訓練框架

區(qū)別于確定性策略梯度(deterministic policy gradient, DPG)方法的Actor-Critic雙網絡,DDPG方法將各網絡擴增為當前網絡和目標網絡。Actor當前網絡負責策略網絡參數的迭代更新,而Actor目標網絡則負責根據經驗回放池中的狀態(tài)采樣選擇最優(yōu)動作。Critic當前網絡負責Q網絡參數迭代更新,而Critic目標網絡負責當前值函數計算,具體結構如圖2所示。

圖2 Actor-Critic雙網絡架構示意圖Fig.2 Schematic diagram of Actor-Critic network

結合A*算法代價函數中權重系數的優(yōu)化設計,DDPG算法的循環(huán)結構如圖3所示。

圖3 算法循環(huán)結構示意圖Fig.3 Schematic diagram of algorithm cycle structure

綜上,基于DDPG方法的A*算法代價函數中的權重系數優(yōu)化設計方法流程如圖4所示。首先,對卷積神經網絡參數與經驗回放池進行參數初始化;然后,Actor-Critic網絡從經驗回放池中選取與動作對應的收縮因子;接著,由改進A*算法求解任務點間航跡規(guī)劃,并得到算法求解時間與規(guī)劃結果節(jié)點數目;進而,完成狀態(tài)-動作轉移并計算即時獎勵與損失函數;重復上述訓練步驟直至完成最大迭代次數后,隨機更新A*算法航跡規(guī)劃任務點信息,重復訓練直至達到最大學習次數;最終,由此得到對應固定環(huán)境下的收縮因子策略。

圖4 結合DDPG算法流程圖Fig.4 Flow chart of algorithm combined with DDPG

分析訓練過程可知,在每一代訓練前將任務點等信息隨機初始化,在訓練過程中反復調用A*算法對航跡規(guī)劃問題進行求解,收縮因子策略的訓練時間較長。因此,在線航跡規(guī)劃采用離線訓練在線應用的策略,在飛行器出發(fā)前對既定戰(zhàn)場環(huán)境下的收縮因子確定策略進行離線訓練,而在飛行器在線飛行過程中則根據由離線學習結果而確定的收縮因子,采用改進A*算法實現三維航跡在線規(guī)劃。訓練完成后,Actor網絡中存放了可最大程度提升算法綜合性能的收縮因子策略。由第2.1節(jié)可知,模型中狀態(tài)為收縮因子對時間性能與最優(yōu)性能的優(yōu)化程度,動作對應收縮因子,環(huán)境指A*算法的整體規(guī)劃過程。因此，本文提出的強化學習模型具有通用性，訓練的收縮因子策略能夠適用于不同作戰(zhàn)任務場景。

3 仿真分析

本節(jié)首先在三維靜態(tài)環(huán)境下驗證收縮因子對A*算法航跡規(guī)劃時間性能與規(guī)劃結果最優(yōu)性能的影響;然后結合DDPG方法對收縮因子進行訓練,并考慮多組不同任務點與禁飛區(qū)的仿真場景,對比文獻[13]提出的指數衰減加權方法,驗證本文提出的改進A*算法在靜態(tài)場景下的規(guī)劃性能;最后在動態(tài)場景下驗證結合DDPG訓練收縮因子策略的改進A*方法的在線航跡規(guī)劃能力。

3.1 引入收縮因子的改進A*算法仿真實驗

仿真選定北緯38°至北緯39°與西經112°至西經113°的單元經緯網格作為戰(zhàn)場環(huán)境,戰(zhàn)場環(huán)境地面地形如圖5所示,飛行器性能參數如表1所示,敵方禁飛區(qū)經緯坐標與威脅半徑參數如表2所示。

圖5 戰(zhàn)場環(huán)境地面地形圖Fig.5 Topographic map of battlefield environment

表1 飛行器性能參數表

為進一步提升算法時間性能,考慮算法存儲空間與排序搜索方法:① 為避免A*算法中開放列表中的拓展節(jié)點數目過多,消耗大量排序與計算時間,考慮引入存儲空間約束以進一步提升算法計算效率;② 考慮采用二叉堆方法對代價函數值進行排序[31],若當前開放列表中節(jié)點數目超過預設存儲空間上限,則根據排序結果將代價函數值最大的拓展節(jié)點移除,以保證拓展節(jié)點搜索效率。

表2 禁飛區(qū)參數表

選定收縮因子值區(qū)間邊界驗證收縮因子對算法時間性能的影響,進而確定后續(xù)DDPG方法訓練收縮因子時所需的值函數。兩者規(guī)劃結果對比如圖6與圖7所示。

圖6 標準A*算法與改進A*算法規(guī)劃結果平面圖Fig.6 2D comparison diagram of planning results between standard and improved A* algorithm

圖7 標準A*算法與改進A*算法規(guī)劃結果三維圖Fig.7 3D comparison diagram of planning results between standard and improved A* algorithm

當w=1時，標準A*算法的仿真時間為264.13 s,規(guī)劃結果節(jié)點數目為49個;當w=0時，改進A*算法運行時間為0.932 s,規(guī)劃節(jié)點數目為53個。分析兩者仿真時間、規(guī)劃結果節(jié)點數目以及規(guī)劃路徑結果可以發(fā)現,引入收縮因子后,改進A*算法的規(guī)劃結果滿足戰(zhàn)場環(huán)境約束與飛行器性能約束,能夠在保證航跡規(guī)劃結果可行的前提下提升算法時間性能。

3.2 結合DDPG方法的收縮因子訓練仿真實驗

結合DDPG方法對收縮因子進行迭代訓練,在每一代訓練前更新任務點信息,依據收縮因子值區(qū)間邊界的A*算法航跡規(guī)劃仿真結果。以第3.1節(jié)仿真場景為例確定獎勵函數對應參數,如表3所示。

表3 獎勵函數參數表

DDPG卷積神經網絡參數如表4所示。

表4 卷積神經網絡參數表

DDPG方法訓練A*算法收縮因子策略的仿真環(huán)境為Pycharm 2020.3.1,處理器配置為Intel(R)CoreTMi9-10885H CPU @ 2.40 GHz,累計訓練迭代次數為1 000次,總訓練時間為20.2 min。狀態(tài)變量隨訓練迭代次數的變化結果如圖8與圖9所示,反映了改進A*算法在引入收縮因子后相對于標準A*算法的時間性能與最優(yōu)性能隨迭代次數的變化。在此基礎上,進一步分析迭代訓練下的收縮因子變化與獎勵函數總回報隨迭代次數的變化關系,訓練結果如圖10與圖11所示。

圖8 改進算法最優(yōu)性能變化圖Fig.8 Variation diagram of improved algorithm optimal performance

圖9 改進算法時間性能變化圖Fig.9 Variation diagram of improved algorithm time performance

圖10 迭代收斂的收縮因子圖Fig.10 Diagram of shrinkage factor of iterative convergence

圖11 迭代收斂的總回報圖Fig.11 Diagram of total reward of iterative convergence

分析收縮因子迭代訓練結果可知,在訓練初期收縮因子在給定初值附近進行探索,收縮因子越小,算法時間性能越可以得到顯著提升,規(guī)劃的航跡結果軌跡長度最優(yōu)性能略微下降。收縮因子策略訓練在300代后逐漸收斂,獎勵函數總回報穩(wěn)定在[0.121.0.372],最終確定收縮因子穩(wěn)定在[0.415,0.429]。

3.3 靜態(tài)對比仿真實驗

在第3.1節(jié)場景基礎上設計不同任務點與禁飛區(qū)位置的任務場景,根據第3.2節(jié)中訓練的收縮因子策略結果,對多任務場景進行航跡規(guī)劃仿真,并與文獻[13]提出的指數衰減加權方法進行對比。設多組不同任務點與禁飛區(qū)的經緯坐標如表5所示。其中,第1、2、3組與第4、5、6組的任務點不同且禁飛區(qū)位置相同;第1、4組與第2、5組與第3、6組的任務點相同且禁飛區(qū)位置不同。表6給出了設計的6組任務場景下，兩種改進A*算法的仿真時間與規(guī)劃結果節(jié)點數目的仿真結果。

表5 仿真場景參數表

表6 各場景仿真結果表

以表5中的場景1為例,指數衰減加權方法的改進A*算法運行時間為9.612 s,規(guī)劃結果節(jié)點數目為69個;結合DDPG方法訓練收縮因子策略的改進A*算法的運行時間為1.373 s,規(guī)劃結果節(jié)點數目為52個,兩種改進方法的航跡結果對比如圖12與圖13所示。

圖12 兩種改進A*算法規(guī)劃結果平面圖Fig.12 2D comparison diagram of planning results between two improved A* algorithms

分析表6仿真結果可知,結合DDPG方法訓練的收縮因子策略相較于指數衰減加權方法，改進效果好且魯棒性強,而指數衰減加權方法規(guī)劃結果最優(yōu)性差強人意,且對于不同地形環(huán)境與任務場景的改進效果不穩(wěn)定。

圖13 兩種改進A*算法規(guī)劃結果三維圖Fig.13 3D comparison diagram of planning results between two improved A* algorithms

3.4 三維動態(tài)仿真實驗

為驗證改進A*算法在線航跡規(guī)劃方法的可行性與有效性,在第3.1節(jié)場景基礎上設計動態(tài)威脅,飛行器飛行性能參數與表1 設置相同。設禁飛區(qū)3向南以15 m/s的速度勻速運動,禁飛區(qū)5向北以15 m/s的速度勻速運動,禁飛區(qū)6沿北偏西45°方向以15 m/s的速度勻速運動。在第3.2節(jié)收縮因子訓練結果的基礎上,采用改進A*算法,設拓展節(jié)點的步長為2 km,以10 s為滾動規(guī)劃周期對三維動態(tài)場景進行在線航跡規(guī)劃,最終全過程仿真結果如圖14與圖15所示。

分析仿真結果,飛行器全段飛行仿真時間為580.0 s,總航跡節(jié)點數目為58個,規(guī)劃航跡結果滿足地形環(huán)境與飛行器性能約束。仿真結果表明,結合DDPG方法訓練收縮因子策略改進后的A*算法能夠滿足飛行器在線航跡規(guī)劃的時間性能要求。

圖14 動態(tài)場景改進算法規(guī)劃結果平面圖Fig.14 2D diagram of planning results for improved algorithm in dynamic scenario

圖15 動態(tài)場景改進A*算法規(guī)劃結果三維圖Fig.15 3D diagram of planning results for improved algorithm in dynamic scenario

4 結 論

基于強化學習方法改進三維A*算法,在保證飛行器三維航跡規(guī)劃結果最優(yōu)性的同時提升了算法的時間性能。引入收縮因子改進A*算法代價函數加權方法,解決了啟發(fā)信息加權后在A*搜索時列表中代價函數值過大而影響搜索效率的問題,進一步提升了算法時間性能?？紤]收縮因子對規(guī)劃結果最優(yōu)性與實時性的影響,建立綜合指標模型,并結合DDPG方法對收縮因子進行訓練優(yōu)化。針對復雜約束條件與地形環(huán)境的不同仿真場景,改進算法的時間性能均能滿足在線航跡規(guī)劃的實時性要求,且算法規(guī)劃結果滿足飛行器自身性能條件與戰(zhàn)場環(huán)境約束。