陳曉倩，劉瑞祥

北京聯(lián)合大學(xué) 智慧城市學(xué)院，北京100101

1 引言

與有人機(jī)相比，無人機(jī)具有體積小、成本低、生存能力強(qiáng)、機(jī)動(dòng)性能好、使用方便等優(yōu)點(diǎn)，業(yè)已在空中作戰(zhàn)、局勢(shì)偵察、精細(xì)農(nóng)業(yè)、電力巡檢等領(lǐng)域得到廣泛應(yīng)用。航跡規(guī)劃是無人機(jī)任務(wù)執(zhí)行能力實(shí)現(xiàn)的核心技術(shù)之一，是指在綜合考慮飛行時(shí)間、燃料消耗、外界威脅等因素的前提下，為無人機(jī)規(guī)劃出一條符合任務(wù)需求和動(dòng)態(tài)約束的最優(yōu)航跡[1]。良好的航跡規(guī)劃能力是無人機(jī)飛行任務(wù)優(yōu)化執(zhí)行的重要保證。

已有的無人機(jī)航跡規(guī)劃算法包括A*算法[2]、遺傳算法[3]、蟻群算法[4]、粒子群算法[5]及人工勢(shì)場(chǎng)法[6]等。由于航跡規(guī)劃的規(guī)劃區(qū)域復(fù)雜多變，加之要考慮無人機(jī)的性能約束等條件，算法存在尋優(yōu)能力差、計(jì)算量過大、效率不高等問題，在航跡規(guī)劃的最優(yōu)性和實(shí)時(shí)性方面有待進(jìn)一步提高。

近年來，強(qiáng)化學(xué)習(xí)算法在無人機(jī)領(lǐng)域的應(yīng)用日益得到關(guān)注。李東華等人采用多智能體強(qiáng)化學(xué)習(xí)的方法，采用兩個(gè)功能不同的智能體，分別對(duì)應(yīng)局部和全局路徑規(guī)劃[7]。郝釧釧等人利用無人機(jī)的航跡約束條件指導(dǎo)規(guī)劃空間離散化并在回報(bào)函數(shù)中引入回報(bào)成型技術(shù)[8]。上述文獻(xiàn)利用無人機(jī)的航跡約束條件指導(dǎo)規(guī)劃空間離散化，一定程度上降低了離散規(guī)劃問題的規(guī)模，提高了規(guī)劃獲得的航跡的可用性，但是航跡的精度直接與空間離散柵格尺度相關(guān)，在復(fù)雜應(yīng)用場(chǎng)景中航跡精度無法保證。楊祖強(qiáng)等人采用Wire Fitting Neural Network Q（WFNNQ）學(xué)習(xí)方法實(shí)現(xiàn)了連續(xù)狀態(tài)連續(xù)動(dòng)作的航跡規(guī)劃[9]。但連續(xù)的狀態(tài)和動(dòng)作采用神經(jīng)網(wǎng)絡(luò)逼近，訓(xùn)練時(shí)間較長(zhǎng)，收斂性較差，不適合在線應(yīng)用。

為彌補(bǔ)已有方法的不足，本文采用最小二乘策略迭代算法開展無人機(jī)航跡規(guī)劃問題研究。該算法采用帶參線性函數(shù)逼近器近似表示值函數(shù)，避免進(jìn)行空間離散化，提高了航跡精度。同時(shí)最小二乘方法利用采集的樣本數(shù)據(jù)求解值函數(shù)參數(shù)，直接對(duì)策略進(jìn)行評(píng)價(jià)和改進(jìn)。通過復(fù)雜城市場(chǎng)景中的飛行動(dòng)力學(xué)仿真對(duì)算法的有效性進(jìn)行了驗(yàn)證，并與經(jīng)典的Q 學(xué)習(xí)算法進(jìn)行對(duì)比，仿真結(jié)果表明LSPI 算法規(guī)劃出的三維航跡更為平滑，規(guī)劃時(shí)間更短，有利于飛機(jī)實(shí)際飛行。

2 問題描述

本文針對(duì)城市反恐、智能物流、抗震救災(zāi)等應(yīng)用關(guān)注的無人機(jī)在復(fù)雜環(huán)境中的航跡規(guī)劃問題開展研究。所提出的算法能夠?qū)б裏o人機(jī)安全無碰地從任一起始位置出發(fā)，到達(dá)目標(biāo)位置，實(shí)現(xiàn)航跡長(zhǎng)度、飛行高度、飛行安全性等指標(biāo)的優(yōu)化。

無人機(jī)航跡規(guī)劃功能結(jié)構(gòu)如圖1 所示。任務(wù)規(guī)劃器提供航跡規(guī)劃的起始位置(X,Y,Z) 、目標(biāo)位置(XT,YT,ZT)與速度(Vx,Vy,Vz)、航跡約束；基于算法的航跡規(guī)劃器利用以上任務(wù)信息及無人機(jī)提供的當(dāng)前位置速度信息生成新的動(dòng)作(Vx,Vy,Vz) 并提供給無人機(jī)；無人機(jī)飛控系統(tǒng)對(duì)飛行動(dòng)作進(jìn)行解析得到無人機(jī)控制指令作用于無人機(jī)；無人機(jī)將下一位置(X',Y',Z')反饋給航跡規(guī)劃和飛行控制模塊。

基于上述任務(wù)場(chǎng)景和功能結(jié)構(gòu)，本文所述航跡規(guī)劃問題如式（1）所示。航跡優(yōu)化的目標(biāo)是使航跡費(fèi)用J 最小，即找到一組具有最短航跡長(zhǎng)度的可飛航跡。約束條件主要包括：航跡無碰和最大速度vmax。Co表示無人機(jī)與障礙物間的碰撞次數(shù)。

3 強(qiáng)化學(xué)習(xí)算法

3.1 MDP模型

強(qiáng)化學(xué)習(xí)是一種從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)技術(shù)。學(xué)習(xí)過程如下：Agent 通過對(duì)感知到的環(huán)境狀態(tài)采取各種試探動(dòng)作，獲得環(huán)境狀態(tài)的適合度評(píng)價(jià)值（通常是一個(gè)獎(jiǎng)勵(lì)或懲罰信號(hào)），從而修改自身的動(dòng)作策略以獲得較大的獎(jiǎng)勵(lì)或較小的懲罰[10]。馬爾科夫決策過程（Markov Decision Process，MDP）常用來對(duì)強(qiáng)化學(xué)習(xí)問題進(jìn)行建模[11]。MDP 問題通?？梢杂靡粋€(gè)五元組{S,A,P,R,γ}來描述[11]，其中S 是狀態(tài)空間，A 是動(dòng)作空間，P 是狀態(tài)轉(zhuǎn)移概率，R 是立即回報(bào)（獎(jiǎng)賞）函數(shù)，γ∈(0,1)是折扣因子。Agent 根據(jù)策略π 來選擇動(dòng)作。強(qiáng)化學(xué)習(xí)的目標(biāo)是對(duì)于一個(gè)MDP 模型，獲得最優(yōu)策略π*滿足式（2）：

其中rt為單步回報(bào)，Jπ為策略π 的期望折扣總回報(bào)。

3.2 最小二乘策略迭代算法

最小二乘策略迭代（Least-Squares Policy Iteration，LSPI）是一種基于逼近方法的強(qiáng)化學(xué)習(xí)算法，在值函數(shù)空間進(jìn)行逼近[12]。經(jīng)典的Q 學(xué)習(xí)算法對(duì)狀態(tài)空間進(jìn)行離散，采用查詢表的形式存儲(chǔ)動(dòng)作值函數(shù)和策略，智能體能夠到達(dá)的狀態(tài)是有限的，不能遍歷所有狀態(tài)，離散尺度過大會(huì)降低系統(tǒng)精度。對(duì)于大規(guī)?；蛘哌B續(xù)空間問題，近似是一種有效的方法，可以遍歷狀態(tài)空間中所有的狀態(tài)，保證系統(tǒng)精度。

關(guān)于策略π 的狀態(tài)-動(dòng)作值函數(shù)Qπ(s,a)定義為在狀態(tài)s 下采取動(dòng)作a，且后續(xù)動(dòng)作都按照策略進(jìn)行選擇時(shí)獲得的期望總回報(bào)[13]。Q 值根據(jù)式（3）的貝爾曼公式計(jì)算[14]：

其中R(s,a)表示在狀態(tài)s 下執(zhí)行動(dòng)作a 后獲得的立即回報(bào)；P(s,a,s')∈[0,1]表示在狀態(tài)s 下選擇動(dòng)作a 后使環(huán)境狀態(tài)轉(zhuǎn)移到狀態(tài)s' 的概率；π(a';s')表示策略在狀態(tài)s'選擇a'的概率。

圖1 無人機(jī)航跡規(guī)劃功能結(jié)構(gòu)圖

在大規(guī)模或連續(xù)空間中，對(duì)Qπ(s,a)進(jìn)行逼近。通常使用線性函數(shù)逼近器將值函數(shù)表示為一組基函數(shù)φ1,φ2,…,φn的線性組合[13]，如式（4）所示，其中ω 是一個(gè)n 維的參數(shù)向量。

LSPI是一類無模型、離策略的近似迭代算法，離線方法有更好的樣本利用率[15]。利用采樣方法，根據(jù)樣本數(shù)據(jù)來學(xué)習(xí)參數(shù)ω[16]。假設(shè)在任意策略π 下收集到N個(gè)樣本：

其中：

LSPI 的結(jié)構(gòu)框圖如圖2 所示[17]。策略評(píng)估中采用線性函數(shù)逼近器逼近Q 值函數(shù)，逼近形式如式（2）所示，策略改進(jìn)中通過式（7）所示的貪心策略逐步改善策略，直到前后兩次策略π[t]和π[t+1]沒有差別，得到最終的最優(yōu)策略。

圖2 最小二乘策略迭代結(jié)構(gòu)圖

基于LSPI的策略學(xué)習(xí)算法偽代碼如算法1所示。

算法1 基于LSPI的策略學(xué)習(xí)算法

輸入：D,ε,ω0

輸出：ω

1. 初始化：確定基函數(shù)φ，基函數(shù)個(gè)數(shù)k 和折扣因子γ

2. 計(jì)算ω：

while ‖ ω-ω' ‖＞ε do

ω ←ω'

for each (s,a,r,s')∈D do

end for

4 基于最小二乘策略迭代的無人機(jī)航跡規(guī)劃

4.1 無人機(jī)航跡規(guī)劃問題的MDP建模

由于LSPI 算法是針對(duì)MDP 模型逼近最優(yōu)策略的一類有效方法，因此先將無人機(jī)航跡規(guī)劃問題建模為MDP 模型。由于無人機(jī)在航跡規(guī)劃過程中，下一時(shí)刻的位置只與當(dāng)前位置和在當(dāng)前位置采取的動(dòng)作有關(guān)，而與其他信息無關(guān)，因此可直接建模為MDP模型。

狀態(tài)空間為無人機(jī)的三維位置集合，動(dòng)作空間定義為無人機(jī)的三維速度集合?；貓?bào)函數(shù)的設(shè)計(jì)需要考慮各種航跡費(fèi)用、飛行安全性、UAV的動(dòng)態(tài)約束等航跡性能指標(biāo)，具體如式（8）所示：

ωh、ωt和ωo分別為各項(xiàng)航跡性能指標(biāo)的權(quán)重系數(shù)。在航跡規(guī)劃問題中所考慮的回報(bào)包括連續(xù)回報(bào)和離散回報(bào)兩類。

連續(xù)回報(bào)包括：UAV的飛行高度H= ||Z-Z0，其中Z0為無人機(jī)的最佳飛行高度；距離目標(biāo)位置的距離差：

離散回報(bào)為碰撞懲罰；R 為狀態(tài)轉(zhuǎn)移過程中發(fā)生碰撞的懲罰項(xiàng)；C0為UAV與障礙發(fā)生碰撞的次數(shù)。

4.2 基于LSPI的無人機(jī)航跡規(guī)劃

采樣的樣本數(shù)據(jù)形式為(s,a,r,s')，表示在當(dāng)前狀態(tài)s 選擇動(dòng)作a 執(zhí)行后獲得回報(bào)值r ，同時(shí)到達(dá)下一狀態(tài)s' 。當(dāng)無人機(jī)到達(dá)目標(biāo)位置或者發(fā)生碰撞時(shí)結(jié)束單次采樣過程。采樣階段結(jié)束后，采用LSPI 算法對(duì)采集的樣本數(shù)據(jù)進(jìn)行學(xué)習(xí)得到最優(yōu)策略。

基函數(shù)的選擇是LSPI 算法中一個(gè)基本的問題，高斯徑向基函數(shù)是一種常用的基函數(shù)，適用于逼近光滑且連續(xù)的函數(shù)[17]。函數(shù)形式如式（9）所示：

其中μ 表示函數(shù)中心，σ 表示函數(shù)寬度。

動(dòng)作的表示是通過復(fù)制 ||A 次基函數(shù)實(shí)現(xiàn)的，基函數(shù)大小為 ||? × ||A 。計(jì)算選中動(dòng)作對(duì)應(yīng)的基函數(shù)值，其余動(dòng)作的基函數(shù)值都為0，即

其中m 表示基函數(shù)個(gè)數(shù)，l 表示選中的動(dòng)作a,na表示動(dòng)作個(gè)數(shù)。

策略的學(xué)習(xí)根據(jù)算法1所示的偽碼進(jìn)行，學(xué)習(xí)到策略后，根據(jù)策略進(jìn)行航跡規(guī)劃，航跡規(guī)劃偽碼如算法2所示。根據(jù)學(xué)習(xí)到的策略估計(jì)Q 值，選擇Q 值最大的動(dòng)作執(zhí)行直到到達(dá)目標(biāo)位置。

算法2 航跡規(guī)劃算法

輸入：s0,sT,ω

輸出：Path(s0,sT)

1. 初始化：Path(s0,sT)←{s0}

s ←s0

2. 航跡點(diǎn)計(jì)算：

while s ≠sTdo

π=arg max φT(s,a)ω

s′=nextstate(s,π)

s ←s'

Path(s0,sT)←s'

3. 輸出Path(s0,sT)

5 仿真結(jié)果與分析

通過無人機(jī)在復(fù)雜城市環(huán)境中的航線飛行仿真任務(wù)來驗(yàn)證本文航跡算法的有效性。由于針對(duì)無人機(jī)航跡規(guī)劃問題暫無標(biāo)準(zhǔn)測(cè)試用例，本文設(shè)計(jì)了包含多種復(fù)雜形狀障礙的城市場(chǎng)景，如圖3所示。任務(wù)區(qū)域?yàn)?00 m×100 m×60 m，設(shè)計(jì)無人機(jī)起始點(diǎn)為（15，25，0），目標(biāo)點(diǎn)為（85，65，35）。航點(diǎn)的到達(dá)需要穿越復(fù)雜障礙環(huán)境，增加了任務(wù)的挑戰(zhàn)性。為了增加仿真的真實(shí)性，采用文獻(xiàn)[18]所述四旋翼動(dòng)力學(xué)模型作為仿真中的無人機(jī)對(duì)象。仿真采用Matlab 軟件，由有2.5GHz Core i5-7200U CPU和4 GB RAM的計(jì)算機(jī)實(shí)現(xiàn)。

圖3 城市場(chǎng)景抽象圖

采用徑向基函數(shù)對(duì)狀態(tài)進(jìn)行特征提取，狀態(tài)特征向量由8 個(gè)高斯基函數(shù)和1 個(gè)常量組成。位置X 分量取{25，65}兩個(gè)中心點(diǎn)，Y 分量中心點(diǎn)取{25，65}，Z 分量中心點(diǎn)取{15 35}，構(gòu)成狀態(tài)空間共8 個(gè)高斯基中心點(diǎn)。探索因子γ=0.95。收集的樣本數(shù)據(jù)量為20 000。

由于目前采用與LSPI相關(guān)的強(qiáng)化學(xué)習(xí)方法進(jìn)行無人機(jī)航跡規(guī)劃的研究較少，因此采用強(qiáng)化學(xué)習(xí)中應(yīng)用相對(duì)廣泛的Q學(xué)習(xí)算法作為對(duì)比算法驗(yàn)證LSPI算法在無人機(jī)航跡規(guī)劃中的有效性。圖4 為L(zhǎng)SPI 算法與Q 學(xué)習(xí)算法的實(shí)驗(yàn)結(jié)果對(duì)比圖，其中橫坐標(biāo)為情節(jié)數(shù)，縱坐標(biāo)表示每一情節(jié)對(duì)應(yīng)的運(yùn)行步數(shù)。從圖中可以看出，在收斂速度和收斂結(jié)果方面LSPI 算法都要優(yōu)于Q 學(xué)習(xí)算法，且收斂更加穩(wěn)定。圖5給出了Q學(xué)習(xí)算法與LSPI算法規(guī)劃的三維航跡對(duì)比圖，其中黑虛線為算法規(guī)劃出的航跡，紅實(shí)線表示的是將算法規(guī)劃結(jié)果用于UAV 氣動(dòng)模型得到的仿真飛行曲線。具體統(tǒng)計(jì)數(shù)據(jù)見表1。由圖5及表1 可知，兩種算法都能實(shí)現(xiàn)避障，但LSPI 算法的規(guī)劃時(shí)間及航跡長(zhǎng)度更短。雖然LSPI算法規(guī)劃的航跡轉(zhuǎn)彎與起伏動(dòng)作次數(shù)較多，但總的轉(zhuǎn)彎角度和小，轉(zhuǎn)彎幅度小，更利于飛機(jī)實(shí)際飛行。Q學(xué)習(xí)算法中采用查詢表的形式存儲(chǔ)策略，對(duì)狀態(tài)空間進(jìn)行離散化處理，狀態(tài)是離散有限的，無人機(jī)的位置只能是離散化后的狀態(tài)空間中的位置，若離散尺度偏大，計(jì)算出的航跡點(diǎn)間的距離就較長(zhǎng)，無法保證無人機(jī)的平滑飛行。LSPI 算法中依據(jù)函數(shù)逼近器計(jì)算策略，函數(shù)是連續(xù)的，無人機(jī)可以到達(dá)狀態(tài)空間中的任意位置，只要?jiǎng)幼髟O(shè)置合理，航跡點(diǎn)間的航跡長(zhǎng)度就可以保證無人機(jī)平滑飛行。

圖4 不同算法在不同情節(jié)下到達(dá)目標(biāo)所需的時(shí)間步

圖5 不同算法下的三維航跡對(duì)比圖

表1 Q-learning與LSPI算法規(guī)劃結(jié)果對(duì)比表

總的來說，LSPI算法獲得的三維航跡更為平滑，規(guī)劃時(shí)間及航跡長(zhǎng)度更短，沒有過大的轉(zhuǎn)彎動(dòng)作，可以節(jié)省燃料，提高跟蹤精度，更加適合無人機(jī)飛行。

6 結(jié)束語

本文針對(duì)傳統(tǒng)Q 學(xué)習(xí)算法無法有效解決連續(xù)狀態(tài)空間的問題，提出采用基于近似策略表示的最小二乘策略迭代算法進(jìn)行無人機(jī)航跡規(guī)劃研究。采用線性函數(shù)逼近器近似表示動(dòng)作值函數(shù)，利用最小二乘法進(jìn)行參數(shù)更新，根據(jù)學(xué)習(xí)到的參數(shù)采用貪心策略進(jìn)行動(dòng)作選擇。仿真結(jié)果表明該算法能有效解決連續(xù)狀態(tài)空間問題，能夠?yàn)闊o人機(jī)在復(fù)雜城市場(chǎng)景中規(guī)劃出一條從起始位置到目標(biāo)位置的無碰三維航跡且執(zhí)行性能較優(yōu)。

今后的工作將對(duì)算法展開進(jìn)一步測(cè)試，并在算法充分訓(xùn)練后在真實(shí)的無人機(jī)平臺(tái)實(shí)現(xiàn)。