基于導(dǎo)向強化Q學(xué)習(xí)的無人機路徑規(guī)劃

周彬，郭艷，李寧，鐘錫健

陸軍工程大學(xué) 通信工程學(xué)院，南京 210007

無人機(Unmanned Aerial Vehicle，UAV)作為一種新型的智能載體，具有機動性高、靈活性強、結(jié)構(gòu)簡單、造價低、隱蔽性強和安全性高等優(yōu)勢，在地質(zhì)氣象觀測、快遞運輸?shù)让裼妙I(lǐng)域發(fā)揮了重要作用，同時也被廣泛應(yīng)用于軍事領(lǐng)域中執(zhí)行監(jiān)視、偵察、追蹤等任務(wù)[1]。路徑規(guī)劃是指在有障礙物的環(huán)境中，根據(jù)最短路徑和最短規(guī)劃時間等評估標(biāo)準(zhǔn)，找到一條從初始位置到目標(biāo)位置的最優(yōu)/較優(yōu)的無碰撞路徑[2]。無人機應(yīng)用場景一般地域廣闊、環(huán)境復(fù)雜，如何快速準(zhǔn)確地規(guī)劃出一條安全、快捷的路徑，是無人機應(yīng)用的重要研究方向[3]。

針對無人機路徑規(guī)劃問題，大量研究進行了有益的探索[4-12]。從所需初始信息的完整程度來看，可將現(xiàn)有的無人機路徑規(guī)劃方法分為兩大類:基于先驗完整環(huán)境信息的全局路徑規(guī)劃方法和基于部分環(huán)境信息的局部路徑規(guī)劃方法[4]。目前，對于全局路徑規(guī)劃方法的研究較為成熟，如A*算法[5]、Voronoi圖[6]和人工勢場法[7]等。但全局路徑規(guī)劃方法大都需要提前建立好完整模型，當(dāng)環(huán)境復(fù)雜時計算開銷非常大；且在實際應(yīng)用中，無人機面對不斷變化的動態(tài)環(huán)境時很難掌握全局信息，使用確定性方法來實現(xiàn)路徑規(guī)劃過程的最優(yōu)控制是不可行的[8]。因此，基于部分未知或完全未知的環(huán)境信息進行路徑規(guī)劃，更具有實際意義，也更受關(guān)注。在這方面，很多學(xué)者已經(jīng)進行了大量研究，并取得了一定的成果，如基于神經(jīng)網(wǎng)絡(luò)(NN)[9]、粒子群優(yōu)化(PSO)[10]和強化學(xué)習(xí)(RL)[11]等算法的局部路徑規(guī)劃方法。這些方法在一定程度上克服了先驗環(huán)境信息不足的問題，極大地提高了無人機在復(fù)雜環(huán)境下的適應(yīng)性，且能夠獲得較好的路徑[12]。

隨著機器學(xué)習(xí)的迅速發(fā)展，人們試圖利用基于深度學(xué)習(xí)(Deep Learning，DL)和強化學(xué)習(xí)(Reinforcement Learning，RL)的方法來解決路徑規(guī)劃問題[13]。其中最具代表性的是基于馬爾可夫決策過程的標(biāo)準(zhǔn)Q學(xué)習(xí)算法[14]，作為一種監(jiān)督式學(xué)習(xí)方法，它能夠根據(jù)環(huán)境的變化，通過學(xué)習(xí)機制為無人機規(guī)劃出一條較優(yōu)的無碰撞路徑。文獻[15]通過結(jié)合貪婪策略和玻爾茲曼概率選擇策略提出了一種新的動作選擇策略，避免標(biāo)準(zhǔn)Q學(xué)習(xí)算法陷入局部最優(yōu)，并通過啟發(fā)函數(shù)限定無人機飛行的方向角度，加快無人機路徑規(guī)劃的收斂速度。文獻[16]通過基于位置信息的Q學(xué)習(xí)算法導(dǎo)航無人機，并利用函數(shù)逼近的方法降低Q函數(shù)的維數(shù)，加快算法的收斂速度。由此可見，雖然Q學(xué)習(xí)算法在無人機路徑規(guī)劃問題上研究已久，但如何解決其容易陷入局部最優(yōu)、收斂速度慢等問題仍是現(xiàn)在研究的熱點[17]。

針對上述問題，本文提出了基于接收信號強度(RSS)的路徑規(guī)劃方法，利用無人機探索環(huán)境獲得的信號強度更新回報值，然后根據(jù)玻爾茲曼(Boltzmann)概率選擇策略指導(dǎo)無人機路徑規(guī)劃。并在仿真中與基于位置信息的Q學(xué)習(xí)算法比較，驗證了所提算法的優(yōu)越性。同時，根據(jù)無人機飛行環(huán)境的特點，引入“導(dǎo)向強化”原則強化Q學(xué)習(xí)算法的學(xué)習(xí)效率，提高路徑規(guī)劃收斂速度，大大減少了迭代次數(shù)。最后，利用數(shù)值仿真驗證了所提算法的優(yōu)越性。

本文組織如下：第1節(jié)介紹了系統(tǒng)框架和模型，第2節(jié)介紹了基于接收信號強度的導(dǎo)向強化Q學(xué)習(xí)的無人機路徑規(guī)劃，第3節(jié)進行仿真結(jié)果分析，第4節(jié)給出了結(jié)論。

1 系統(tǒng)框架和模型建立

1.1 接收信號強度模型

一般而言，信號傳輸鏈路所處的環(huán)境決定該傳輸鏈路為視距傳輸模型(LOS)還是非視距傳輸模型(NLOS)。由于無人機與目標(biāo)點之間的環(huán)境未知，障礙物或建筑等的位置、高度等信息不可完全獲取，無人機與目標(biāo)信號源之間的信號傳輸可能會受到障礙、建筑等的影響。所以，假設(shè)該鏈路同時存在LOS和NLOS，2種鏈路中的選擇概率由無人機與目標(biāo)點之間的環(huán)境類型所決定。本文使用一種常用的依概率選擇的傳輸損耗模型[18]，無人機ui與可疑信號源D之間的路徑損耗為

(1)

LoS的概率由無人機與信號源之間的環(huán)境所決定，可表示為

(2)

(3)

由此可得，無人機ui與可疑信號源D之間的路徑損耗為

(4)

假設(shè)無人機和信號源的天線都是全向天線，基于以上的信道模型，無人機ui接收到信號源D的信號強度(RSS)可以表示為

Sui,D=Pui,D·Hui,D+σ2

(5)

1.2 標(biāo)準(zhǔn)Q學(xué)習(xí)算法

Q學(xué)習(xí)算法[19]是一種機器學(xué)習(xí)的方法，通過智能體(Agent)與環(huán)境反復(fù)交互，學(xué)習(xí)獲得一個或一系列較優(yōu)的行為，這個學(xué)習(xí)過程是采用馬爾可夫決策過程(MDP)形式，通過sense-act-learn循環(huán)的方式進行學(xué)習(xí)，其組元可以表示為{S,A,P(s′|a,s),R(s,a,s′)}，其中S表示有限狀態(tài)空間集；A表示有限動作空間集；P(s′|a,s)表示狀態(tài)轉(zhuǎn)移概率函數(shù)，即智能體在當(dāng)前狀態(tài)s時執(zhí)行動作a，轉(zhuǎn)移到下一個狀態(tài)s′的概率，其中s,s′∈S，a∈A；R(s,a,s′)表示回報值，即智能體在狀態(tài)s時執(zhí)行動作a，狀態(tài)轉(zhuǎn)移到s′所得到的回報。

在標(biāo)準(zhǔn)的Q學(xué)習(xí)算法中，智能體從環(huán)境中感知得到當(dāng)前的狀態(tài)s∈S，基于當(dāng)前的狀態(tài)s和過去學(xué)習(xí)到的經(jīng)驗知識，智能體決定執(zhí)行某一個動作a∈A，實施該動作之后，智能體依概率P(s′|a,s)轉(zhuǎn)移到下一個狀態(tài)s′∈S并獲得一個回報值R(s,a,s′)。在這個過程中，定義一個Q函數(shù)，用于計算某一個狀態(tài)-動作對(s,a)所獲得的期望回報值，Q函數(shù)為關(guān)于變量(s,a)的函數(shù)，其一種常用的更新公式為

Q*(s,a)=Q(s,a)+

式中：λ∈(0,1)為折扣因子。Q函數(shù)可以概(6)括為智能體在過去學(xué)習(xí)到的經(jīng)驗知識，并持續(xù)更新。

1.3 狀態(tài)轉(zhuǎn)移策略

在本文無人機動作選擇的問題中，假設(shè)無人機所處的狀態(tài)為s，此時的動作空間為A={a1,a2,…,ak,…,aK},k=1,2,…,K，每一個狀態(tài)-動作對對應(yīng)一個Q值，其中一種動作的選擇方案為選擇最大Q值所對應(yīng)的動作，即

(7)

式中：as表示在無人機在狀態(tài)s選擇的動作。

(8)

式中：P(ak|s)表示無人機處于狀態(tài)s時選擇動作ak∈A的概率;κB>0為玻爾茲曼常數(shù);T為溫度;Z(T)為概率分布的標(biāo)準(zhǔn)化因子：

(9)

根據(jù)上述的動作選擇概率公式(8)，無人機在狀態(tài)s轉(zhuǎn)移到下一個狀態(tài)s′的概率可表示為

(10)

假設(shè)在狀態(tài)s執(zhí)行某個動作ak后，依概率1轉(zhuǎn)移到狀態(tài)s′(指某個特定的狀態(tài))，且執(zhí)行其他動作時，依概率0轉(zhuǎn)移到狀態(tài)s′，即

(11)

則，狀態(tài)s到狀態(tài)s′的轉(zhuǎn)移概率可簡化為

P(s′|s)=P(ak|s)

(12)

2 無人機路徑規(guī)劃

2.1 基于接收信號強度的回報函數(shù)

在本文研究的無人機搜索目標(biāo)信號源的過程中，所獲得的關(guān)于目標(biāo)信號源的信息只有接收信號強度，可以將該信息作為Q學(xué)習(xí)過程中的回報值，因為無人機搜索目標(biāo)信號源的過程，可以理解為縮小無人機與目標(biāo)信號源之間的距離的過程，而其兩者之間的距離越小，則無人機接收到可疑信號的強度就越強，因此可以將回報值定義為

R(s,a,s′)=Sui,D(s′)

(13)

式中：Sui,D(s′)為無人機ui處于狀態(tài)s′時所獲得的目標(biāo)信號強度。然而，由于相鄰的狀態(tài)之間所接收到的信號強度的差值并不大，單以Sui,D(s′)作為回報值，且依概率選擇動作的隨機性太強，難以收斂。下面提出一種更優(yōu)的方案。

通過接收到的信號強度的變化，可以判斷無人機的飛行方向是趨向還是背離目標(biāo)信號源，即由接收信號強度的變化可以獲得方向信息。例如，如果無人機ui在狀態(tài)s獲得的信號強度Sui,D(s)小于在下一個狀態(tài)s′所獲得的信號強度Sui,D(s′)(假設(shè)無人機ui在狀態(tài)s實施動作ak后到達狀態(tài)s′)，則說明無人機的飛行方向趨向目標(biāo)信號源，且如果ΔSss′=Sui,D(s′)-Sui,D(s)越大，說明動作ak方向與目標(biāo)信號源方向的偏離角越小，故將回報函數(shù)定義為

R(s,a,s′)=α[Sui,D(s′)-Sui,D(s)]

(14)

式中：α為信號強度差系數(shù)，α越大，信號強度差在回報函數(shù)中占得比重就越大。

(四)加強會計信息化建設(shè)，會計軟件是行政事業(yè)單位開展財務(wù)管理以及會計工作的重要工具，它的使用極大地提高會計工作的準(zhǔn)確性和工作效率，但隨著會計制度的改革不斷深化，會計軟件系統(tǒng)的部分模塊功能在實際工作不能滿足新的需要，因此現(xiàn)有會計核算軟件要根據(jù)政府會計制度的設(shè)置要求及時地進行系統(tǒng)升級與調(diào)試。好的會計軟件的使用可以極大地精簡財務(wù)計算管理工作，也能讓行政事業(yè)單位的財務(wù)狀況更加及時規(guī)范地體現(xiàn)。會計軟件的使用必須符合財政部制定的相關(guān)會計信息化工作規(guī)范和標(biāo)準(zhǔn)，確保利用現(xiàn)代化信息技術(shù)手段開展會計核算及生成的會計信息符合政府會計制度和會計準(zhǔn)則。

2.2 導(dǎo)向強化原則

方向信息不僅可以作為回報函數(shù)中的一部分，而且可以指導(dǎo)無人機在下一個狀態(tài)s′的動作(無人機的狀態(tài)s′由無人機在狀態(tài)s實施動作ak后到達)，因為如果方向ak在狀態(tài)s時趨向于目標(biāo)信號源，那么在下一個狀態(tài)s′時選擇動作ak也很可能趨向于目標(biāo)信號源。在標(biāo)準(zhǔn)Q學(xué)習(xí)算法的基礎(chǔ)上，可以通過方向信息對于無人機動作選擇進行優(yōu)化，稱之為具有“導(dǎo)向強化”原則。動作的選擇由Q值表決定，方向信息對下一個動作的影響可表示為

Q(s′,ai)=

(15)

式中：ak為無人機ui在狀態(tài)s時執(zhí)行的特定動作，ai∈A為無人機ui在狀態(tài)s′時可選擇執(zhí)行的任意動作；ρ∈[0,1]為折扣因子，控制前一步的方向信息對后一步動作的影響的大小，其值越大，方向的導(dǎo)向性越強。

2.3 導(dǎo)向強化Q學(xué)習(xí)算法主要步驟

1) 對當(dāng)前環(huán)境進行柵格化，確定起始點坐標(biāo)和目標(biāo)點坐標(biāo)，并以目標(biāo)點為中心建立信號強度場，作為無人機獲取接收信號強度來計算回報值。

2) 初始化狀態(tài)值，清空Q函數(shù)矩陣和回報矩陣，無人機從起始點開始進行探索并獲取信號強度。

3) 根據(jù)無人機所在狀態(tài)s位置的Q函數(shù)計算各個動作ak的轉(zhuǎn)移概率，并根據(jù)概率策略選擇動作a。

4) 執(zhí)行動作a飛行至狀態(tài)s′位置，并獲取新的信號強度。通過回報函數(shù)計算出回報值，更新狀態(tài)s下動作a的Q函數(shù)，并根據(jù)導(dǎo)向強化以折扣因子ρ來更新狀態(tài)s′對應(yīng)的Q函數(shù)。

5) 將當(dāng)前環(huán)境位置更新至狀態(tài)s′位置，并判斷是否為目標(biāo)位置或達到最大迭代次數(shù)，如果不是，則結(jié)束本次迭代學(xué)習(xí)過程，迭代次數(shù)+1，繼續(xù)返回到步驟3)，否則到步驟6)。

6) 結(jié)束該次嘗試學(xué)習(xí)，嘗試次數(shù)+1，并返回到步驟2)，繼續(xù)進行下一次嘗試學(xué)習(xí)。

7) 最后判斷是否到達可接受目標(biāo)參數(shù)，或已經(jīng)達到設(shè)定的最大嘗試次數(shù)，2個條件中只要有一個滿足，則結(jié)束整個學(xué)習(xí)過程。

3 仿真及分析

3.1 實驗環(huán)境

本節(jié)通過仿真實驗來驗證基于接收信號強度的導(dǎo)向強化Q學(xué)習(xí)算法的性能。首先將環(huán)境柵格化為100×100區(qū)域網(wǎng)格，以其左下角為坐標(biāo)原點，建立一個以水平方向為x軸，豎直方向為y軸的坐標(biāo)系。標(biāo)記出起始位置和目標(biāo)位置，紅色星點為起始位置，藍色星點為目標(biāo)位置，其中3個圓圈內(nèi)部表示為無法穿越的障礙物區(qū)域，其他區(qū)域(在邊界內(nèi)部)為無人機的自由活動區(qū)域(如圖1 所示)。無人機動作空間集合為所在狀態(tài)s位置有上、下、左、右4 個動作，即圖中藍色箭頭指示；而對于障礙區(qū)域則不能進入，即圖中紅色箭頭指示；對角區(qū)域考慮到障礙物形狀不規(guī)則、柵格化不理想等因素，設(shè)計為需要經(jīng)過兩步到達(如圖2所示)。

圖1 柵格化區(qū)域模型Fig.1 Grid-based environment model

圖2 無人機動作空間模型Fig.2 UAV action space model

3.2 實驗分析

在仿真實驗中，將通過2組實驗分別從基于接收信號強度算法的可行性和導(dǎo)向強化Q學(xué)習(xí)算法的有效性上進行對比分析。其中，Q學(xué)習(xí)算法所有學(xué)習(xí)過程的實驗參數(shù)及關(guān)鍵參數(shù)值如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameters setting

圖3為基于接收信號強度的算法產(chǎn)生的路徑軌跡，圖4為基于位置距離的算法產(chǎn)生的路徑軌跡。圖5為多障礙基于接收信號強度的算法產(chǎn)生的路徑軌跡。如圖3～圖5所示，在每次嘗試中都會對周圍的路徑進行探索，并根據(jù)回報值調(diào)整路徑，最終尋得目標(biāo)點，且基于接收信號的算法在多障礙的情況下也能獲得較好的路徑。

圖3 基于接收信號強度算法的路徑軌跡Fig.3 Path planning with received signal strength algorithm

圖4 基于位置距離算法的路徑軌跡Fig.4 Path planning with location distance algorithm

圖5 多障礙基于接收信號強度算法的路徑軌跡Fig.5 Path planning in multi-obstacles environment with received signal strength algorithm

如圖6所示，基于接收信號強度的算法前期收斂速度較快，在嘗試20次左右開始收斂；而基于位置距離的算法在嘗試25次左右開始收斂。

圖6 兩種回報值的收斂過程Fig.6 Convergence process of two reward values

由此可見，前者比后者具有更好的收斂性，其最少迭代步數(shù)也幾乎是相同的，可以說明以接收信號強度為回報值有較好的規(guī)劃效果。但在研究背景中并無法預(yù)知目標(biāo)的確切位置，即無人機與目標(biāo)之間的位置距離并不容易獲得，因此基于接收信號強度的路徑規(guī)劃可以發(fā)揮很好的作用。

2) 為凸顯改進Q學(xué)習(xí)算法的優(yōu)勢，仿真中與標(biāo)準(zhǔn)Q學(xué)習(xí)算法、蟻群算法和粒子群算法進行比較。

如圖7所示，與其他3種算法相比，導(dǎo)向強化Q學(xué)習(xí)算法最終規(guī)劃的路徑長度比標(biāo)準(zhǔn)Q學(xué)習(xí)算法、蟻群算法更優(yōu)，有較好的優(yōu)化性能。相對粒子群算法來說，雖然最終規(guī)劃的路徑長度相同，但粒子群算法在50次嘗試后才開始收斂，導(dǎo)向強化Q學(xué)習(xí)算法在10次嘗試后就逐步收斂到最優(yōu)，在算法收斂速度上有絕對優(yōu)勢。

圖7 不同算法的收斂過程Fig.7 Convergence process of different algorithms

特別是，標(biāo)準(zhǔn)Q學(xué)習(xí)算法在嘗試20次左右才開始收斂，相比導(dǎo)向強化Q學(xué)習(xí)算法收斂速度較慢，且最終優(yōu)化路徑長度效果差。由此可見，“導(dǎo)向強化”原則能夠有效加快Q學(xué)習(xí)算法的收斂速度，對無人機路徑規(guī)劃有較好的指導(dǎo)效果。

4 結(jié) 論

1) 在目標(biāo)位置信息未知的情況下，該方法以接收信號強度為回報值，能夠迅速準(zhǔn)確地規(guī)劃出飛行路徑，與基于位置距離的方法相比，收斂速度更快，表現(xiàn)出了更好的路徑規(guī)劃性能。

2) 與傳統(tǒng)算法相比，導(dǎo)向強化Q學(xué)習(xí)算法在收斂性、時間復(fù)雜度和路徑規(guī)劃上優(yōu)勢明顯。從而驗證了“導(dǎo)向強化”原則，可以加快算法收斂速度，在無人機飛行路徑規(guī)劃中有較好的適用性。