楊雅寧

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

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

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

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

1 基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)規(guī)劃算法理論

1.1 強(qiáng)化學(xué)習(xí)與動(dòng)態(tài)規(guī)劃

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

圖1 強(qiáng)化學(xué)習(xí)基本原理

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

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

(1)

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

(2)

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

(3)

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

1.2 基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)規(guī)劃算法描述

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

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

2 實(shí)驗(yàn)仿真

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

2.1 環(huán)境建模

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

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

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

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

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

2.2 實(shí)驗(yàn)仿真

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

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

(ii)如果選擇執(zhí)行的動(dòng)作將使無人機(jī)反向遠(yuǎn)離目標(biāo)區(qū)域且下一區(qū)域?yàn)榘踩珔^(qū)域，那么無人機(jī)將獲得回報(bào)為-3，如圖3中向左的動(dòng)作，無人機(jī)將進(jìn)入新區(qū)域.

(iii)如果選擇執(zhí)行的動(dòng)作不影響無人機(jī)對(duì)目標(biāo)區(qū)域的趨向性，且下一區(qū)域?yàn)榘踩珔^(qū)域，那么無人機(jī)將獲得回報(bào)為-2，如圖3中向上的動(dòng)作，無人機(jī)將進(jìn)入新區(qū)域.

(iv)如果選擇執(zhí)行的動(dòng)作將使無人機(jī)正向靠近目標(biāo)區(qū)域，且下一區(qū)域?yàn)榘踩珔^(qū)域，如圖3中向下或向右的動(dòng)作，那么無人機(jī)將獲得回報(bào)為-1，無人機(jī)將進(jìn)入新區(qū)域.

(v)如果選擇執(zhí)行的動(dòng)作使無人機(jī)進(jìn)入目標(biāo)任務(wù)區(qū)域，那么獲得回報(bào)0，無人機(jī)將進(jìn)入任務(wù)區(qū)域.

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

圖4 仿真結(jié)果

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

3 結(jié)語

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