楊雅寧

(寧夏師范學院 物理與電子信息工程學院，寧夏 固原 756099)

自主無人機的飛行軌跡是根據(jù)預(yù)先規(guī)劃并裝載到其飛行控制系統(tǒng)的航線進行的，航線規(guī)劃技術(shù)是無人機系統(tǒng)的關(guān)鍵技術(shù)之一.航線規(guī)劃是指無人機執(zhí)行任務(wù)前，在綜合考慮安全、航時、航程等條件下，預(yù)先規(guī)劃出一條或多條從起點到終點的最優(yōu)飛行航線.在實際應(yīng)用場景中，無人機起點到任務(wù)點之前往往存在地理、氣象、軍事等安全威脅，甚至還可能存在禁飛空域的影響，因此，無人機航線規(guī)劃是在復(fù)雜環(huán)境下的最優(yōu)化問題.

近些年，對無人機航跡規(guī)劃算法的研究有很多，包括遺傳算法[1]、A*算法[2]、蟻群算法[3]、人工勢場算法[4]等.隨著人工智能技術(shù)的興起，研究人員提出了基于人工智能的路徑規(guī)劃方法.Chen Y W等[5]提出采用神經(jīng)網(wǎng)絡(luò)方法進行最優(yōu)機器人路徑規(guī)劃的方法，Wu P[6]等人提出了一種基于深度學習的機器人路徑規(guī)劃方法，李志龍[7]等提出了一種基于強化學習Q-Learning算法實現(xiàn)機場服務(wù)機器人的路徑規(guī)劃，武曲[8]等人結(jié)合LSTM算法，提出了基于強化學習的動態(tài)環(huán)境規(guī)劃算法.

本文針對復(fù)雜環(huán)境下中小型無人機航線規(guī)劃問題，結(jié)合強化學習的動態(tài)規(guī)劃算法理論，提出一種基于強化學習的動態(tài)規(guī)劃算法，解決復(fù)雜環(huán)境下無人機的航線規(guī)劃問題.并基于gym環(huán)境，使用Python語言進行仿真，驗證算法的合理性和可行性.

1 基于強化學習的動態(tài)規(guī)劃算法理論

1.1 強化學習與動態(tài)規(guī)劃

強化學習是人工智能中策略學習的一種，是一種重要的機器學習方法.該方法起源于動物心理學的相關(guān)原理，模仿人類和動物學習的試錯機制，是一種通過與環(huán)境交互學習，實現(xiàn)狀態(tài)到行為的映射關(guān)系，并以此獲得最大累計期望回報的方法[9].強化學習的要素包括智能體(Agent)、行為(Action)、環(huán)境(Environment)和回報(Reward).環(huán)境被劃分為不同狀態(tài)(State)，智能體處于環(huán)境中的不同狀態(tài)s，通過選擇行為a，實現(xiàn)與環(huán)境的交互，并從交互中獲得回報r，這個過程稱為策略π.圖1解釋了強化學習的基本原理，在一個離散時間序列t=1,2,…中，智能體需要完成某項任務(wù)，在每一個時刻t，智能體都能從環(huán)境中接受一個狀態(tài)st,并通過行為at與環(huán)境交互，轉(zhuǎn)移到環(huán)境中新的狀態(tài)st+1，同時返回一個立即回報rt+1，回報以價值函數(shù)Vt+1或行為價值函數(shù)Qt+1的形式給出.智能體在與環(huán)境交互的過程中，總是趨向于選擇能獲得最大回報的行為at，即獲得最大的價值函數(shù)Vt+1或者行為價值函數(shù)Qt+1，用更大價值函數(shù)或行為價值函數(shù)下的行為更新曾經(jīng)的行為.當價值函數(shù)或行為價值函數(shù)穩(wěn)定收斂，智能體的行為軌跡即為最優(yōu)策略π.

圖1 強化學習基本原理

動態(tài)規(guī)劃是運籌學的一個分支，是求解決策過程最優(yōu)化的數(shù)學方法.動態(tài)規(guī)劃算法的特點是一個問題可以劃分為不同的子問題，求解問題的最優(yōu)解可以通過求解若干子問題的最優(yōu)解來實現(xiàn).子問題狀態(tài)之間存在遞推關(guān)系，可通過較小的子問題狀態(tài)遞推出較大的子問題的狀態(tài).作為強化學習理論的基石馬爾可夫過程同樣符合以上特點，因此，動態(tài)規(guī)劃算法可以用于求解馬爾可夫決策過程.用動態(tài)規(guī)劃算法所求解的馬爾可夫模型MDP由描述，即問題模型的狀態(tài)S、狀態(tài)轉(zhuǎn)移概率P、行為A及回報系數(shù)γ均是已知的.在此過程中，智能體通過自身的行為選擇，從獲得的回報價值中不斷學習，最終使得整個學習過程中獲得的回報價值達到最大，既獲得最優(yōu)策略.

每個行為對應(yīng)的回報價值用行為價值函數(shù)Q(s,a)給出，如式(1)所示，

(1)

智能體處在s狀態(tài)下，轉(zhuǎn)移到s′，獲得的回報價值V(s)用最大價值函數(shù)Q(s,a)給出，如式(2)所示，

(2)

初始迭代時，模型所有狀態(tài)的價值函數(shù)全部為0，當?shù)趉+1次迭代價值時，使用第k次計算出來的價值函數(shù)Vk(s′)更新計算Vk+1(s)，迭代公式如式(3)所示，

(3)

當?shù)趉+1次迭代值函數(shù)為Vk+1(s)時，使用第k次計算出來的價值函數(shù)Vk(s′)更新計算Vk+1(s).經(jīng)過多次迭代，直到價值函數(shù)V(s)穩(wěn)定收斂.這時，智能體在每個狀態(tài)的價值函數(shù)或者最大的行為價值函數(shù)下的行為a為智能體學習到的行為軌跡，即為最優(yōu)策略π.

1.2 基于強化學習的動態(tài)規(guī)劃算法描述

動態(tài)規(guī)劃算法的流程如圖2所示.首先創(chuàng)建環(huán)境，將環(huán)境劃分為不同的狀態(tài)，初始化各狀態(tài)的價值函數(shù)V(s).根據(jù)每個狀態(tài)s下的可能行為a，計算不同行為對應(yīng)的行為價值函數(shù)Q(s,a) 函數(shù).對不同的行為a，求取最大的行為值函數(shù)，作為當前狀態(tài)下的價值函數(shù)V(s).如此反復(fù)迭代，直到價值函數(shù)V(s)穩(wěn)定，算法達到收斂狀態(tài).根據(jù)收斂的價值函數(shù)，抽取每個狀態(tài)下的行為a，所有狀態(tài)的行為軌跡，就是所求最優(yōu)策略π.

圖2 動態(tài)規(guī)劃算法流程圖

2 實驗仿真

本研究基于gym環(huán)境，使用Python語言進行仿真驗證.在考慮無人機起點與任務(wù)點之間面臨的氣象威脅、軍事威脅和地理威脅的情況下，改進動態(tài)規(guī)劃算法，使其適應(yīng)無人機任務(wù)的復(fù)雜環(huán)境，實現(xiàn)飛行航線的動態(tài)規(guī)劃.

2.1 環(huán)境建模

本實驗使用柵格法表示無人機起點到任務(wù)點之間的地圖環(huán)境，如圖3所示.無人機作為智能體，通過執(zhí)行向上(UP)、向右(RIGHT)、向下(DOWN)和向左(LEFT)的行為動作與地圖環(huán)境交互，獲得回報.與一般情況下使用動態(tài)規(guī)劃算法尋找“寶藏”問題相比，本實驗的環(huán)境中存在有限個威脅區(qū)域(陷阱)，同時目標位置(“寶藏”)和威脅區(qū)域均是已知的，因此該問題的最終可以定義為在存在陷阱的復(fù)雜環(huán)境中尋找一條從起點到終點的最短路徑(航時航程最短)，作為無人機的計劃航線.為使模型更接近真實環(huán)境，本實驗的環(huán)境模型遵循以下約束.

(i)根據(jù)無人機的起點(O,O)和任務(wù)點(M,N)的方位關(guān)系，拓展出邊長分別為OM和ON的矩形區(qū)域，作為地圖環(huán)境.

(ii)在滿足無人機性能要求的前提下，將矩形區(qū)域劃分為大小相等的正方形柵格，構(gòu)建地圖柵格.圖3中構(gòu)建了25個柵格的地圖環(huán)境，每個柵格分配一個編號，0,1,2,…,24，共25個編號.左上角紅色方格為起點區(qū)域，右下角黃色圓形區(qū)域為任務(wù)區(qū)域，白色區(qū)域為安全區(qū)域，黑色區(qū)為威脅或禁飛區(qū)域.根據(jù)實際應(yīng)用情況，無人機的起點與任務(wù)點一定是安全區(qū)域.

圖3 無人機地圖柵格環(huán)境示例

(iii)威脅區(qū)域給定狀態(tài)標識為0，其他區(qū)域給定狀態(tài)標識為1.標識為威脅區(qū)域的柵格不得多于總柵格數(shù)量的30%，這也是接近實際應(yīng)用情況的.同時滿足從起點到任務(wù)點至少存在一條能避開威脅區(qū)域的路徑，反之，如果不存在，那么擴展地圖環(huán)境，重新生成地圖柵格.

2.2 實驗仿真

為使算法更好地適應(yīng)無人機航線規(guī)劃場景，降低算法計算量，結(jié)合模型約束條件，將一般動態(tài)規(guī)劃算法做了如下改進：針對模型中的威脅區(qū)域和安全區(qū)域，分別使用0和1作為標識，根據(jù)模型約束和實際使用情況，無人機是不可能置于威脅區(qū)域的，因此算法中直接將威脅區(qū)域的值函數(shù)置零，忽略了在威脅區(qū)域行為值函數(shù)的計算，減低了算法的計算量.根據(jù)模型環(huán)境中無人機起點和任務(wù)點的方位關(guān)系，靈活設(shè)置不同行為所給予的回報值.使無人機正向靠近任務(wù)點的行為回報值更大，使無人機反向遠離任務(wù)區(qū)域的行為回報值更小，使得算法快速收斂.

(i)如果選擇執(zhí)行的動作將使無人機即將離開環(huán)境邊界或進入威脅區(qū)域，那么無人機將獲得回報為-3，并使無人機停留在當前區(qū)域.

(ii)如果選擇執(zhí)行的動作將使無人機反向遠離目標區(qū)域且下一區(qū)域為安全區(qū)域，那么無人機將獲得回報為-3，如圖3中向左的動作，無人機將進入新區(qū)域.

(iii)如果選擇執(zhí)行的動作不影響無人機對目標區(qū)域的趨向性，且下一區(qū)域為安全區(qū)域，那么無人機將獲得回報為-2，如圖3中向上的動作，無人機將進入新區(qū)域.

(iv)如果選擇執(zhí)行的動作將使無人機正向靠近目標區(qū)域，且下一區(qū)域為安全區(qū)域，如圖3中向下或向右的動作，那么無人機將獲得回報為-1，無人機將進入新區(qū)域.

(v)如果選擇執(zhí)行的動作使無人機進入目標任務(wù)區(qū)域，那么獲得回報0，無人機將進入任務(wù)區(qū)域.

仿真結(jié)果如圖4所示，圖4中紅色方框表示無人機的起點，黃色圓圈表示無人機的任務(wù)點，黑色方框表示地圖環(huán)境中的威脅區(qū)域，白色方框代表地圖環(huán)境中的安全區(qū)域，黑色箭頭表示無人機在各安全區(qū)域?qū)W習到的最優(yōu)移動方向.按照箭頭方向，連接無人機起點到任務(wù)區(qū)的路徑，即為無人機學習到的最優(yōu)路徑.

圖4 仿真結(jié)果

圖4(a)和圖4(b)顯示了無人機起點為左上方向，任務(wù)區(qū)為右下方向時，即起點和終點既不在同一經(jīng)度，也不在同一緯度時(這代表了實際應(yīng)用場景的一般情況)，在不同的威脅區(qū)域影響下，無人機處于任意一個安全區(qū)域都能學習到一條安全的最優(yōu)路徑.圖4(c)顯示無人機起點與任務(wù)點在同一經(jīng)(緯)方向時(這代表了實際應(yīng)用場景的特殊情況)，在威脅區(qū)域影響下，無人機無法直接從起飛點到達任務(wù)點，通過拓展地圖區(qū)域，無人機仍能在地圖的任意安全區(qū)域?qū)W習出至少一條最優(yōu)路徑.

3 結(jié)語

本文針對小型無人機從起點到任務(wù)點之間存在安全威脅和空域限制的問題，建立環(huán)境模型，將基于強化學習的動態(tài)規(guī)劃算法應(yīng)用于中小型無人機航線規(guī)劃場景中.與一般動態(tài)規(guī)劃算法相比，該算法通過對環(huán)境模型中威脅區(qū)域增加標識，忽略威脅區(qū)域行為值的計算，減低了算法計算量.同時，根據(jù)環(huán)境模型中無人機起點與任務(wù)點的位置關(guān)系，配置不同狀態(tài)和行為下的回報值，使得算法快速收斂.實驗結(jié)果表明，無論無人機起點和任務(wù)點的位置關(guān)系如何，通過本文的模型和方法，無人機處在環(huán)境中任意安全區(qū)域都能找到至少一條最優(yōu)航線.