改進的動態(tài)A*-Q-Learning算法及其在無人機航跡規(guī)劃中的應用

程傳斌 倪艾辰 房翔宇 張亮

DOI：10.19850/j.cnki.2096-4706.2021.09.001

摘? 要：Q-Learning算法是一種基于價值函數的強化學習方法。傳統(tǒng)的Q-Learning算法迭代效率低且容易陷入局部收斂，針對該劣勢改進了算法，引入A*算法和動態(tài)搜索因子ε。將改進后的動態(tài)A*-Q-Learning算法應用于三維復雜環(huán)境下無人機的航跡規(guī)劃，分析無人機航跡規(guī)劃結果的回報函數、探索步數和運行效率。結果表明，改進后的算法可使無人機在復雜環(huán)境下具有很強的自適應性;同時，動態(tài)搜索因子ε能有效地避免智能體在搜尋過程中陷入局部最優(yōu)的狀況，在復雜地形中能尋找到更優(yōu)的路徑。

關鍵詞：無人機;航跡規(guī)劃;A*改進;動態(tài)搜索因子ε;動態(tài)A*-Q-Learning

中圖分類號：TP181;V279? ? ? 文獻標識碼：A 文章編號：2096-4706（2021）09-0001-06

Improved Dynamic A*-Q-Learning Algorithm and Its Application in?UAV Route Planning

CHENG Chuanbin1，NI Aichen2，FANG Xiangyu1，ZHANG Liang1

（1.School of Science，Wuhan University of Technology，Wuhan? 430070，China;

2.School of Economics，Wuhan University of Technology，Wuhan? 430070，China）

Abstract：The Q-Learning algorithm is a reinforcement learning method based on value functions. The traditional Q-Learning algorithm lacks efficiency in iteration and is easy to fall into local convergence. To solve the disadvantage，the algorithm is improved：introducing A* algorithm and dynamic search factor ε. The improved dynamic A*-Q-Learning algorithm is applied to the route planning of UAV in 3D complex environment，and the return function，exploration steps and operation efficiency of UAV route planning results are analyzed. The results demonstrate that the improved algorithm can enable UAV to have strong adaptability in the face of complex environment;meanwhile，dynamic search factors ε can effectively avoid the agent falling into the local optimal condition in the search process，and find a better path in complex terrain.

Keywords：UAV;route planning;A* improvement;dynamic search factor ε;dynamic A*-Q-Learning

0? 引? 言

強化學習是機器學習的范式和方法論之一，用于描述和解決智能體（Agent）在與環(huán)境的交互過程中通過學習策略以達成回報最大化或實現特定目標的問題^[1]。它具有良好的適應性，能夠在未知環(huán)境中不斷試錯從而尋找最優(yōu)策略^[2]。

目前，強化學習可廣泛應用于機器人二維平面的路徑規(guī)劃過程中^[3]，采用的算法多為Q-Learning算法^[4]。傳統(tǒng)的Q-Learning算法由于受大規(guī)模動作值過估計而出現不穩(wěn)定和效果不佳等情況^[5]。因此，許多學者對Q-Learning算法進行了改進。Wen等^[6]基于模糊規(guī)則初始化Q值，加快了算法的收斂速度;朱志斌等人^[7]利用系統(tǒng)數據迭代求解出可使給定目標函數最小化的控制律，實現了多智能體系統(tǒng)的一致性;蔣國飛^[8]等將BP神經網絡和Q-Learning有效結合，解決了確定和隨機倒立擺模型的平衡控制。

近年來，隨著信息技術的快速發(fā)展，無人機的應用由廣闊空曠地域中的常規(guī)應用逐漸轉變?yōu)閺碗s地理環(huán)境中的軍事應用，這對無人機的機動性和遠程通信水平提出了更高的要求^[9]。在復雜環(huán)境下合理規(guī)劃路線，能夠提高無人機執(zhí)行任務的效率和安全性，為無人機的安全航行保駕護航^[10]。

無人機的航跡規(guī)劃可以根據無人機的任務分配情況進行界定^[11]，實驗是在不考慮無人機任務分配及任務關系的條件下進行的。目前大量航跡規(guī)劃的研究中，主要的方法可以分為基于圖論的方法、智能優(yōu)化算法、基于勢場的方法、隨機規(guī)劃算法以及啟發(fā)性搜索算法^[12-16]。其中，啟發(fā)性搜索算法包含A*算法^[17]和D*Lite算法^[18]等。此外，已經有部分研究著眼于Q-Learning在三維航跡中的應用。郝釧釧等^[19]通過設置三維環(huán)境中的航跡約束條件，合理引導和規(guī)劃空間的離散化過程;封碩等^[20]將深度學習嵌套入Q-Learning框架，對三維救災環(huán)境中的機器人路徑進行規(guī)劃。無人機的航跡規(guī)劃受限于傳統(tǒng)算法，沒有表現出優(yōu)秀的自我探索能力，期望通過強化學習賦予無人機自主學習能力，使其能夠靈活應對更加復雜的環(huán)境。

本文在引入馬爾科夫決策過程^[21]五個重要組成部分（環(huán)境與動力、策略、回報函數、價值函數、Bellman期望方程）的基礎上，結合A*算法改進傳統(tǒng)的Q-Learning算法^[22]，同時引入動態(tài)搜索因子ε?；趯嶒灁祿?，分別對Q-Learning算法和動態(tài)A*-Q-Learning算法的回報函數、探索步數和運行效率這三方面的數據進行了分析：改進的動態(tài)A*-Q-Learning算法總回報值高，探索步數較少，運行效率高。這表明在無人機飛行過程中，改進后的算法能夠以更小的代價求得更優(yōu)的解。此外，動態(tài)A*-Q-Learning算法還賦予了無人機較強的自適應性，在風力變化不定的情況下，無人機依舊可以迅速采取相應策略實現航跡的適當調整。

1? Q-Learning算法分析及改進

1.1? 基本原理

強化學習模型由智能體和環(huán)境組成，其主要內容是智能體通過與環(huán)境交互，對當前狀態(tài)下不同動作策略的價值函數進行估計，執(zhí)行高回報動作，避免執(zhí)行低回報或懲罰的動作，從而達到不斷改進策略，逼近最優(yōu)決策的效果。強化學習模型的機理圖如圖1所示。

無人機通過Agent與環(huán)境交互，獲得航跡過程的本質是馬爾可夫決策過程（Markov decision process，MDP），無人機的下一個空間狀態(tài)只與當前的狀態(tài)信息有關，與之前的信息狀態(tài)無關，即無人機航跡規(guī)劃的過程具有馬爾可夫性。

MDP由五個元素構成：

1.2? 基于A*的策略舒適化改進

A*算法是無人機航跡規(guī)劃中較為成熟的解決方法。該算法不僅具有最佳優(yōu)先搜索、高效率搜索的特點，同時具有結合Dijkstra算法能夠找尋最佳路徑的優(yōu)勢。具體流程為：

Agent探索的過程是不斷尋找最優(yōu)策略的過程，其運行效率會隨著探索過程的減少而提高。結合A*算法，利用算法得到的路徑結果對Q-Learning的價值函數Q（s，a）進行初始化，不僅能有效縮短算法迭代時間，同時還能令航跡規(guī)劃的結果比A*算法更精確。

具體是實現步驟為：

Step 1：調用A*算法得到一條起點至終點的最短路徑;

Step 2：記錄路徑中上一個狀態(tài)s遷移至下一個狀態(tài)s'所采用的動作a;

Step 3：令Q（s，a）=C，C>0。對于狀態(tài)s的其余動作a'，令Q（s，a'）=0，完成對價值函數的初始化。

1.3? 動態(tài)搜索因子ε的改進

在強化學習算法中，需要設計出合理的策略依次為繁多的狀態(tài)確定最優(yōu)的動作選擇。在Q-Learning算法中，采用ε-貪心策略來平衡對環(huán)境的探索和利用。其基本思想是確定一個探索因子ε，在確定動作時，Agent通過ε的概率選擇當前回報最高的動作，或者以1-ε的概率隨機選擇一個動作策略。在Q-Learning中，ε通常取一個定值，這樣可能會導致Agent在迭代計算的初期，對環(huán)境的探索程度不夠，尋找不到最優(yōu)路徑，而在迭代的后期又遲遲沒辦法收斂。

為解決上述問題，引入動態(tài)搜索因子ε，根據迭代計算的進度動態(tài)調整ε的大小。設ε=f（x），f（x）表示ε與迭代次數x之間的函數關系。具體函數表達式為：

式中，x為當前迭代次數，N為最大迭代次數。

當Agent處于第x代，由f（x）得到ε的值，通過比較rand（）與ε的大小關系，進一步確定是進行貪心選擇還是進行隨機選擇。

動態(tài)搜索因子ε的引入能夠有效解決以A*算法結果初始化價值函數Q（s，a）后容易陷入局部最優(yōu)的問題，同時加速迭代后期算法的收斂速度。下面給出基于上述改進的偽代碼：

Algorithm 1

Input： Starting point coordinates， End point coordinates

Output： UAV track

Call the algorithm A*

find the static environment route

Initialize the Q-table，

Repeat （for each episode）

Initialize s， a for all s∈S， a∈A

Repeat （for each step of episode）

Calculate ε

2? 無人機三維航跡規(guī)劃建模

2.1? 仿真環(huán)境設置

2.1.1? 風力對航跡的影響

考慮到實際環(huán)境中無人機的航跡會受到天氣的影響，導致規(guī)劃航跡與實際航跡存在偏差，因此設置有風區(qū)域模擬無人機受天氣影響的場景。設置該區(qū)域為任意立體空間，進入該空間內的無人機可能會受到風力的影響并沿風力方向強制移動至下一離散空間點上。風力的影響將持續(xù)到無人機離開該區(qū)域為止。同時考慮到風力可能會出現不連續(xù)吹風的情況，即無人機處于有風區(qū)域時并不會持續(xù)受到風力對航跡的影響，設置風力對無人機造成航跡偏移影響的概率為p=0.9。

2.1.2? 山體環(huán)境設置

在現代軍事領域中，無人機需能夠在復雜的地形環(huán)境中執(zhí)行任務，其中以山脈丘陵地區(qū)為主。因此，規(guī)劃其航跡以避免與山體發(fā)生碰撞是必然要求。通過構造三維函數來刻畫山體的輪廓，描述仿真環(huán)境中的山體信息。山體的輪廓函數設置為：

式中，z表示山體表面上某點的垂直高度，（x，y）表示該點在xOy平面上的投影坐標，（a_i，b_i）表示山體中心在xOy平面上的投影坐標，k_i表示地形坡度參數。參數取不同數值時會得到不同的山峰。實驗山體相關參數設置如表1所示。

無人機在實際航行過程中應避免與山體發(fā)生碰撞，即無人機應與障礙物保持一定的安全距離。同時山體表面豐富的植被讓環(huán)境信息變得更為復雜，為簡化山體表面植被的環(huán)境信息，對山體進行“膨脹”處理，使得仿真環(huán)境中的山體體積擴大為實際山體體積的（1+β）倍，在滿足完全躲避山體要求的同時與山體保持安全距離。實驗仿真環(huán)境如圖2所示。

仿真環(huán)境空間大小設置為7×7×4，以0.25為間隔對仿真環(huán)境進行離散化處理。在Agent與環(huán)境交互的過程中以Δt的間隔更新環(huán)境信息，以適應環(huán)境變化。

2.2? 空間狀態(tài)設置

在仿真實驗中，為了能夠將改進后的算法應用于三維無人機航跡規(guī)劃，首先將無人機放置于一個三維空間當中;接著，分別對無人機的空間狀態(tài)和動作策略機制進行設置，定義無人機的空間狀態(tài)為無人機在空間中的坐標位置，例如，無人機在（x₀，y₀，z₀）時，經過動作決策移動到（x₁，y₁，z₁），即無人機從空間狀態(tài)（x₀，y₀，z₀）轉移到空間狀態(tài)（x₁，y₁，z₁）。

2.3? 動作策略設置

式中，D為當前點到終點的歐氏距離，a=5，b=-100，c=-1。

執(zhí)行回報指無人機每執(zhí)行一次動作決策所得到的獎勵;目標回報指無人機到達終點時所獲得的獎勵;山體回報指無人機撞擊山體的損失;越界回報指無人機離開構建的仿真環(huán)境所受到的損失。

執(zhí)行回報設置的作用是在能夠完成無人機躲避障礙到達目的地的同時，使得航跡最短。對每一步施加懲罰，使Agent能夠得到步數盡可能少的路徑。

3? 實驗結果及分析

3.1? 實驗參數

實驗在7×7×4的三維仿真環(huán)境中進行，對Agent的運動進行了模擬和檢測。此外，對改進后的動態(tài)A*-Q-Learning算法和傳統(tǒng)的Q-Learning算法進行比較，以驗證改進后的A*和動態(tài)搜索因子ε對無人機航跡規(guī)劃的積極作用。

實驗中使用的主要參數如表2所示。

其中，學習率α為算法中的參數，決定收斂速度的快慢;折扣因子γ表示對未來獎勵的看重程度;山體膨脹系數指的是為防止無人機飛行時與山體距離過于接近而發(fā)生事故，將山體放大的倍數。

3.2? 仿真環(huán)境飛行結果

設定起點為（0，0，0），終點為（3.5，4.0，1.5），圖3給出了仿真環(huán)境中無人機從起點到終點的飛行軌跡。

從圖3中可以看出，無人機從起點開始出發(fā)，穿過仿真環(huán)境中的山脈和風力區(qū)域到達終點。使用Q-Learning算法時，無人機航跡與直線距離偏差較大，且航跡受風力影響較大;而使用動態(tài)A*-Q-Learning算法時，無人機航跡與直線距離偏差較小，并且在經過風力區(qū)域時也保持著較高的穩(wěn)定性。

3.3? 回報函數分析

回報函數通過將任務目標具體化和數值化，實現了目標與算法之間的溝通。在具體的運用之中，隨著迭代的推進，回報函數的大小及變化趨勢能夠有效地反映出算法的優(yōu)良程度。

圖4中，Q-Learning算法與動態(tài)A*-Q-Learning算法在起始時刻的回報值表現出差異。Q-Learning算法的回報值約為-60，根據回報函數的設置，其航跡表現為無目的性地徘徊;動態(tài)A*-Q-Learning算法起始時刻的回報值約為-100，其在初始化策略的過程中沒有考慮到風力的作用，在風力的作用下與山體發(fā)生碰撞，得到負回報-100，即在不考慮風力的作用下，航跡的起始初始值遠大于傳統(tǒng)算法。其航跡結果表明動態(tài)A*-Q-Learning算法比Q-Learning算法更具方向性，有效加快了Agent探索過程。

從整體看，Q-Learning算法的回報值增長趨勢較緩，在迭代次數為50 000左右時就收斂于-20左右;動態(tài)A*-Q-Learning算法的回報值增長趨勢明顯，最后收斂于0左右，表明其在探索最優(yōu)路徑的過程中花費了較多的時間，但是最后的總回報卻更優(yōu)。

因此，從回報函數值的變化趨勢可以推斷出：在迭代初期，動態(tài)A*-Q-Learning算法與Q-Learning算法相比，前者的航跡表現出更強的方向性，同時所得到的結果具有更優(yōu)的回報。

3.4? 探索步數分析

一個成熟算法在尋優(yōu)過程中所付出的代價可以表現為收斂時所需的步數。探索步數的峰值和增長速度能反映出算法的尋優(yōu)能力及算法的穩(wěn)定性能。

圖5中，Q-Learning算法與動態(tài)A*-Q-Learning算法在探索步數的峰值方面表現出較大的差異。動態(tài)A*-Q-Learning算法探索步數的峰值為55，小于Q-Learning算法探索步數的峰值65，且最終收斂后的步數更少。在環(huán)境信息相同的情況下，動態(tài)A*-Q-Learning算法只需較少的探索步數就可學習到更多的信息，可幫助Agent獲取更多環(huán)境反饋的信息，從而做出更加合理的動作策略。

從整體上看，動態(tài)搜索因子ε增強了動態(tài)A*-Q-Learning算法在迭代初期的探索能力，在獲取更多環(huán)境反饋信息的情況下，幫助算法提高了最終的收斂程度，同時在迭代末期加快了收斂的速度，動態(tài)A*-Q-Learning算法相較于Q-Learning算法，表現出更強的穩(wěn)定性能和探索能力。

3.5? 運行效率分析

運行效率是判斷算法優(yōu)劣的重要指標。主要對算法的空間效率和時間效率進行分析，目前空間效率不作為關注的重點。實驗在相同設備上進行，兩種算法時間上的表現如圖6所示。

圖6中，展示了Q-Learning算法與動態(tài)A*-Q-Learning算法迭代次數與時間的關系曲線。對比曲線的總體水平和斜率，可知動態(tài)A*-Q-Learning算法的總體時間水平低于傳統(tǒng)算法;同時曲線的斜率低于傳統(tǒng)算法的斜率，表明改進后的算法在每代的迭代時間上少于傳統(tǒng)算法。在迭代次數為55 000次之后，斜率保持不變，陷入局部最優(yōu)的狀況，因此，無法探索出更優(yōu)的路徑。

對比Q-Learning算法與動態(tài)A*-Q-Learning算法，在對回報函數、探索步數及運行效率進行分析之后，驗證了動態(tài)A*-Q-Learning算法在結合A*以及引入動態(tài)搜索因子ε后，表現為探索能力增強，算法運行效率提高，得到的結果更優(yōu)的特點。

4? 結? 論

本文通過結合A*算法以及引入動態(tài)搜索因子ε對傳統(tǒng)的Q-Learing算法進行了改進，克服了算法迭代效率低以及易陷入局部收斂的缺點，以更低的成本得到更高的回報。此外，將動態(tài)A*-Q-Learning算法應用于無人機的航跡規(guī)劃中，在仿真環(huán)境下通過實時更新Q值表，使得無人機具備良好的自適應性，能夠根據外界環(huán)境的變化采取最合適的動作策略。最后，無人機通過強化學習獲得了較強的自我探索能力，可在具有更多試錯機會的情況下探索出最優(yōu)飛行路徑。

參考文獻：

[1] 秦智慧，李寧，劉曉彤，等。無模型強化學習研究綜述 [J].計算機科學，2021，48（3）：180-187.

[2] 韓忻辰，俞勝平，袁志明，等.基于Q-Learning的高速鐵路列車動態(tài)調度方法 [C]//第31屆中國過程控制會議（CPCC 2020）.徐州：中國自動化學會和中國自動化學會過程控制專業(yè)委員會，2020：1.

[3] 張汝波，顧國昌，劉照德，等.強化學習理論、算法及應用 [J].控制理論與應用，2000（5）：637-642.

[4] 高陽，陳世福，陸鑫.強化學習研究綜述 [J].自動化學報，2004（1）：86-100.

[5] MATHEW A，JOLLY M J，MATHEW J. Improved Residential Energy Management System Using Priority Double Deep Q-Learning [J].Sustainable Cities and Society，2021，69：102812.

[6] WEN S H，CHEN J H，LI Z，et al. Fuzzy Q-Learning obstacle avoidance algorithm of humanoid robot in unknown environment [C]//第37屆中國控制會議.武漢：中國自動化學會控制理論專業(yè)委員會，2018：5.

[7] 朱志斌，王付永，尹艷輝，等.基于Q-Learning的離散時間多智能體系統(tǒng)一致性 [J].控制理論與應用，2021，38（7）：997-1005.

[8] 蔣國飛，吳滄浦.基于Q學習算法和BP神經網絡的倒立擺控制 [J].自動化學報，1998（5）：88-92.

[9] 胡嘉悅，李廣文，章衛(wèi)國，等.面向有人/無人機協(xié)同遠程作戰(zhàn)的IVMS架構 [J/OL].航空學報：1-12[2021-04-30].http：//kns.cnki.net/kcms/detail/11.1929.V.20210326.1703.022.html.

[10] 王科銀，石振，楊正才，等.改進強化學習算法應用于移動機器人路徑規(guī)劃 [J/OL].計算機工程與應用：1-7[2021-04-28].http：//kns.cnki.net/kcms/detail/11.2127.TP.20210331.1016. 006.html.

[11] 吳蔚楠.多無人飛行器分布式任務規(guī)劃技術研究 [D].哈爾濱：哈爾濱工業(yè)大學，2018.

[12] 張棟，李如飛，閆曉東，等.基于智能優(yōu)化算法的集群協(xié)同航跡規(guī)劃方法研究 [J].戰(zhàn)術導彈技術，2020（6）：17-29+ 103.

[13] 閻昊，樊興，夏學知.圖結構與Dijkstra算法在無人機航跡規(guī)劃中的應用 [J].火力與指揮控制，2010，35（4）：155-157+160.

[14] 王寧，代冀陽，應進.基于改進勢場的無人機編隊恢復與一致性仿真 [J/OL].系統(tǒng)仿真學報：1-16[2021-04-12].https：//doi.org/10.16182/j.issn1004731x.joss.20-0980.

[15] 陳誠，林秋婷，邱榮祖.基于隨機規(guī)劃模型的彈性木材供應鏈網絡優(yōu)化 [J].森林與環(huán)境學報，2021，41（1）：88-95.

[16] 鄭書朋，鄭淑濤，朱思濱，等.基于啟發(fā)搜索策略的飛行仿真系統(tǒng)實時調度算法 [J].沈陽工業(yè)大學學報，2011，33（1）：86-92.

[17] 張志文，張鵬，毛虎平，等.改進A*算法的機器人路徑規(guī)劃研究 [J].電光與控制，2021，28（4）：21-25.

[18] 程志，張志安，樂偉揚，等.基于D* Lite算法的三維路徑規(guī)劃研究 [J].傳感器與微系統(tǒng)，2020，39（12）：71-73+77.

[19] 郝釧釧，方舟，李平.基于Q學習的無人機三維航跡規(guī)劃算法 [J].上海交通大學學報，2012，46（12）：1931-1935.

[20] 封碩，舒紅，謝步慶.基于改進深度強化學習的三維環(huán)境路徑規(guī)劃 [J].計算機應用與軟件，2021，38（1）：250-255.

[21] 張思齊.基于部分可觀測馬爾科夫決策過程的干擾決策研究 [D].西安：西安電子科技大學，2019.

[22] 秦旋，陳舒鈴，喬任.復雜性視角下基于Agent智能體的復雜工程社會風險演化研究 [J].軟科學，2021，35（6）：125-131.

作者簡介：程傳斌（1998.01—），男，漢族，江西上饒人，本科在讀，研究方向：強化學習;倪艾辰（2000.06—），男，漢族，江蘇鎮(zhèn)江人，本科在讀，研究方向：數字經濟;房翔宇（1999.12—），男，漢族，河南永城人，本科在讀，研究方向：人工智能和大數據;通訊作者：張亮（1977.02—），男，漢族，湖北隨州人，教授，博士，研究方向：分布參數的控制理論。

收稿日期：2021-04-06

基金項目：國家自然科學基金（61573012）