楊秀霞,高恒杰,劉 偉，張 毅

(1.海軍航空大學(xué) 岸防兵學(xué)院，山東 煙臺(tái) 264001； 2.海軍航空大學(xué) 戰(zhàn)勤學(xué)院，山東 煙臺(tái) 264001)

1 引言

隨著機(jī)器人技術(shù)的不斷發(fā)展進(jìn)步，人們對(duì)機(jī)器人運(yùn)動(dòng)過程中適應(yīng)周圍環(huán)境、自主采取相應(yīng)措施能力的要求越來越高[1]。通過建立諸如軌跡長度最短、運(yùn)動(dòng)時(shí)間最少的優(yōu)化目標(biāo)，找到復(fù)雜環(huán)境中起點(diǎn)和終點(diǎn)之間的最優(yōu)路徑，實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃，是機(jī)器人自主導(dǎo)航的關(guān)鍵問題之一[2]。

目前常用的路徑規(guī)劃算法有圖搜索算法，人工勢(shì)場(chǎng)法[3-4]，快速擴(kuò)展隨機(jī)樹法[5-6]，以及以遺傳算法[7]、蟻群算法[8-9]為代表的群智能算法。但是上述路徑規(guī)劃算法進(jìn)行規(guī)劃前需要環(huán)境先驗(yàn)信息，對(duì)于未知復(fù)雜環(huán)境的應(yīng)用性不強(qiáng)。作為一種重要的機(jī)器學(xué)習(xí)方法，強(qiáng)化學(xué)習(xí)在機(jī)器人路徑規(guī)劃中受到越來越多的關(guān)注和應(yīng)用。機(jī)器人在環(huán)境中通過探索獲取知識(shí)，在試錯(cuò)過程中進(jìn)行學(xué)習(xí)，強(qiáng)化學(xué)習(xí)方法在環(huán)境先驗(yàn)信息較少的路徑規(guī)劃中優(yōu)勢(shì)十分明顯。傳統(tǒng)的Q學(xué)習(xí)算法在初始化過程中將Q值設(shè)為均等值或隨機(jī)值，即在無先驗(yàn)知識(shí)的情況下進(jìn)行學(xué)習(xí)，這樣會(huì)使算法收斂速度慢[10]。文獻(xiàn)[11]在Q值初始化過程中引入人工勢(shì)場(chǎng)法中的引力勢(shì)場(chǎng)，加快了算法的收斂速度。文獻(xiàn)[12]利用接受信號(hào)強(qiáng)度定義回報(bào)值，提出了“導(dǎo)向強(qiáng)化”的原則，加快了學(xué)習(xí)算法的收斂速度。文獻(xiàn)[13]通過結(jié)合玻爾茲曼概率選擇策略和貪婪策略，提出了一種新的動(dòng)作選擇策略，加快了路徑規(guī)劃的收斂速度。文獻(xiàn)[14]通過人工勢(shì)場(chǎng)法的合力引導(dǎo)機(jī)制減少了路徑搜索時(shí)間。文獻(xiàn)[15]通過引入環(huán)境勢(shì)能值作為搜索啟發(fā)信息對(duì)Q值進(jìn)行初始化，縮短了算法學(xué)習(xí)時(shí)間。由此可見，雖然Q學(xué)習(xí)算法在路徑規(guī)劃問題上研究已久，但如何加快其收斂速度仍是目前的研究熱點(diǎn)。

針對(duì)傳統(tǒng)Q學(xué)習(xí)算法收斂速度慢的問題，本文在傳統(tǒng)Q學(xué)習(xí)算法基礎(chǔ)上借鑒最優(yōu)控制的思想，提出一種基于分階段最優(yōu)探索的路徑規(guī)劃算法。首先基于環(huán)境規(guī)模和預(yù)計(jì)探索信息確定每一階段探索步長；其次根據(jù)每一階段探索步長設(shè)置獎(jiǎng)勵(lì)池和獎(jiǎng)勵(lì)閾值，確保每一階段探索路徑為該階段最優(yōu)路徑；然后重置變量因子，使本次階段基于上一階段的最優(yōu)路徑繼續(xù)探索；最后確定各個(gè)階段的最優(yōu)路徑，并將每一階段最優(yōu)路徑組合為全局最優(yōu)路徑，實(shí)現(xiàn)機(jī)器人從起始點(diǎn)到目標(biāo)點(diǎn)的路徑規(guī)劃。

2 問題描述

2.1 任務(wù)描述

本文的路徑規(guī)劃問題可以描述為：機(jī)器人從起始點(diǎn)出發(fā)，通過路徑規(guī)劃尋找安全路徑，并按規(guī)劃路徑行動(dòng)并躲避障礙物，最后安全達(dá)到目標(biāo)點(diǎn)。

在本文的路徑規(guī)劃問題中通過柵格法建立環(huán)境模型，柵格地圖由n*n的網(wǎng)格組成。地圖中分布著多個(gè)位置不同的靜態(tài)障礙物和動(dòng)態(tài)障礙物。本文中路徑規(guī)劃環(huán)境如圖1所示。

圖1 路徑規(guī)劃環(huán)境模型示意圖

圖1中，矩形區(qū)域?yàn)闄C(jī)器人起始點(diǎn)，空心圓、實(shí)心圓、星型區(qū)域分別表示地圖中動(dòng)態(tài)障礙物、靜態(tài)障礙物的位置和機(jī)器人的目標(biāo)點(diǎn)。其中，動(dòng)態(tài)障礙按一定規(guī)則在地圖中移動(dòng)。起始點(diǎn)和目標(biāo)點(diǎn)的信息均已知，而障礙信息是未知的。

基于上述設(shè)定，本文提出算法的目標(biāo)有2個(gè)：一是最快規(guī)劃出機(jī)器人從起始點(diǎn)到目標(biāo)點(diǎn)的最短可行路徑，引導(dǎo)機(jī)器人安全到達(dá)目標(biāo)點(diǎn)；二是避免行進(jìn)過程中發(fā)生碰撞和出界。

2.2 機(jī)器人運(yùn)動(dòng)學(xué)模型

機(jī)器人二維運(yùn)動(dòng)學(xué)簡化模型為：

(1)

式(1)中：(x,y)為機(jī)器人位置坐標(biāo)；v為機(jī)器人的運(yùn)動(dòng)速度；φ為本文的控制量，對(duì)應(yīng)運(yùn)動(dòng)航向角。

3 改進(jìn)Q學(xué)習(xí)路徑規(guī)劃算法

3.1 傳統(tǒng)Q學(xué)習(xí)算法原理

Q學(xué)習(xí)算法最初是由WATKINS等提出的一種無模型的值函數(shù)強(qiáng)化學(xué)習(xí)算法。該算法可用馬爾科夫決策過程(MDP)框架來形式化描述。MDP可用一個(gè)四元組(S,A,P(s,s′,a),R(s,s′,a)) 定義，其中S表示狀態(tài)空間，A表示動(dòng)作空間，P(s,s′,a)表示狀態(tài)轉(zhuǎn)移概率函數(shù)(模型)，該模型定義了智能體執(zhí)行動(dòng)作a∈A后，環(huán)境狀態(tài)s∈S轉(zhuǎn)移到新狀態(tài)s′∈S的概率。

獎(jiǎng)勵(lì)R(s,s′,a)是人為設(shè)定的在智能體選擇并做出動(dòng)作a∈A后，環(huán)境狀態(tài)s∈S轉(zhuǎn)移到新狀態(tài)s′∈S的獎(jiǎng)勵(lì)。強(qiáng)化學(xué)習(xí)智能體遵循策略π從t1時(shí)刻狀態(tài)開始到t2時(shí)刻狀態(tài)結(jié)束時(shí)，狀態(tài)累積獎(jiǎng)勵(lì)回報(bào)之和定義為：

(2)

式(2)中：ri為智能體每一次選擇并做出動(dòng)作后環(huán)境反饋的獎(jiǎng)勵(lì)；γ∈(0,1)為折扣因子。

Q學(xué)習(xí)算法會(huì)根據(jù)智能體的狀態(tài)空間和動(dòng)作空間建立一個(gè)Q表，用來存儲(chǔ)所有的狀態(tài)-動(dòng)作對(duì)的Q值。同時(shí)，通過設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，評(píng)價(jià)智能體選擇的動(dòng)作在環(huán)境中的優(yōu)劣，如果狀態(tài)-動(dòng)作對(duì)得到來自環(huán)境的正獎(jiǎng)勵(lì)，則它對(duì)應(yīng)的Q值會(huì)不斷增大；如果狀態(tài)-動(dòng)作對(duì)得到來自環(huán)境的負(fù)獎(jiǎng)勵(lì)，則它對(duì)應(yīng)的Q值會(huì)不斷減小。通過每一回合的訓(xùn)練逐漸更新Q(st,a)逐漸逼近Q*(st,a)，基于貝爾曼公式的Q表更新公式為：

Q(st,a)=Q(st,a)+α[rt+γmaxQ(st+1,a)-Q(st,a)]

(3)

式(3)中：α∈(0，1)為學(xué)習(xí)率；rt為智能體每次選擇動(dòng)作時(shí)得到的獎(jiǎng)勵(lì)；γ∈(0,1)為折扣因子。最后，智能體根據(jù)Q表在每個(gè)狀態(tài)下選擇最優(yōu)動(dòng)作完成目標(biāo)任務(wù)。Q學(xué)習(xí)算法流程如圖2所示。

圖2 傳統(tǒng)Q學(xué)習(xí)算法流程框圖

傳統(tǒng)Q學(xué)習(xí)算法常用的策略為ε-貪婪策略。其策略思想是確定一個(gè)探索因子ε，在選擇動(dòng)作時(shí)，智能體以ε的概率選擇最優(yōu)動(dòng)作，以1-ε的概率隨機(jī)選擇一個(gè)動(dòng)作。其算法表達(dá)式為：

(4)

式(4)中，ε∈[0,1]。當(dāng)ε趨近于0時(shí)，智能體僅探索環(huán)境；當(dāng)ε趨近于1時(shí)，智能體僅利用環(huán)境。σ是一個(gè)隨機(jī)變量，σ∈[0,1]。如果σ小于等于ε，則智能體選擇能令Q值最大化的動(dòng)作；如果σ大于ε，則智能體隨機(jī)選擇動(dòng)作。

3.2 階段Q學(xué)習(xí)路徑規(guī)劃算法原理

由3.1節(jié)傳統(tǒng)Q學(xué)習(xí)算法的基本原理可知，傳統(tǒng)Q學(xué)習(xí)算法采取新動(dòng)作主要依賴于每一步中隨機(jī)變量σ與ε的比較。在訓(xùn)練的每一回合中，若隨機(jī)變量σ>ε的頻數(shù)遠(yuǎn)遠(yuǎn)多于σ≤ε的頻數(shù)，則智能體將一直探索新動(dòng)作，而不會(huì)根據(jù)Q表選擇最優(yōu)動(dòng)作，這時(shí)便不易規(guī)劃出最優(yōu)路徑；若隨機(jī)變量σ≤ε的頻數(shù)遠(yuǎn)遠(yuǎn)小于σ>ε的頻數(shù)，則智能體將一直遵循Q表選擇當(dāng)前狀態(tài)的最優(yōu)動(dòng)作，從而缺乏對(duì)環(huán)境的探索使路徑陷入局部最優(yōu)。更重要的是，由于訓(xùn)練過程中需要的回合數(shù)過于龐大，智能體因?yàn)椴呗跃窒扌远鴮?dǎo)致路徑的大量重復(fù)探索，導(dǎo)致算法的學(xué)習(xí)效率低，收斂速度慢。

針對(duì)上述問題，本文對(duì)傳統(tǒng)Q學(xué)習(xí)算法進(jìn)行改進(jìn)，提出一種基于分階段最優(yōu)探索的改進(jìn)Q學(xué)習(xí)路徑規(guī)劃算法。

3.2.1 確定各階段探索步長

3.2.2 設(shè)置獎(jiǎng)勵(lì)池和獎(jiǎng)勵(lì)閾值

考慮到各階段可能存在提前得到最優(yōu)路徑的情況(即m′次探索后得到最優(yōu)路徑，其中m′

獎(jiǎng)勵(lì)池的作用是存儲(chǔ)當(dāng)前階段中每次探索后的獎(jiǎng)勵(lì)值。每次探索后的獎(jiǎng)勵(lì)值都會(huì)與獎(jiǎng)勵(lì)池中最近一次得到的獎(jiǎng)勵(lì)相比較，如果相同，計(jì)數(shù)為+1。當(dāng)計(jì)數(shù)達(dá)到獎(jiǎng)勵(lì)閾值Rmax時(shí)，視為當(dāng)前階段已經(jīng)規(guī)劃出最優(yōu)路徑，則結(jié)束本階段的規(guī)劃進(jìn)入下一階段規(guī)劃路徑。

3.2.3 重置變量因子

為了確保各階段在前一階段最優(yōu)路徑基礎(chǔ)上繼續(xù)對(duì)路徑進(jìn)行規(guī)劃，基于式(4)設(shè)計(jì)重置變量因子機(jī)制。

(5)

由式(4)可知，當(dāng)σ=0時(shí)，算法的動(dòng)作策略總是會(huì)選擇Q表中最優(yōu)動(dòng)作。即第X個(gè)階段探索的起點(diǎn)為前面各個(gè)階段探索的最優(yōu)路徑的終點(diǎn)。這樣就保證了每一階段的路徑規(guī)劃都是基于前一階段的最優(yōu)路徑上進(jìn)行的。

3.2.4 確定全局最優(yōu)路徑

定義：只要總是選取動(dòng)作序列

(6)

則累積獎(jiǎng)勵(lì)期望總是最大的，即各個(gè)階段路徑組合即為最優(yōu)路徑。

證明：設(shè)全局策略(即全局動(dòng)作序列)

(7)

是最快規(guī)劃出安全路徑的最優(yōu)策略，相應(yīng)的最小代價(jià)為：

(8)

式(8)中，x(i)為第i個(gè)階段的狀態(tài)。

(9)

因此，有2個(gè)動(dòng)作序列

(10)

使得：

J*>J**

(11)

式(11)中：

(12)

上述結(jié)論與J*為最小代價(jià)的假設(shè)相矛盾。因此，反設(shè)不成立，證畢。

3.3 階段Q學(xué)習(xí)路徑規(guī)劃算法設(shè)計(jì)

將機(jī)器人路徑規(guī)劃問題建模為馬爾科夫決策過程(MDP)。下面依次對(duì)該模型的3個(gè)要素，即狀態(tài)空間、動(dòng)作空間和獎(jiǎng)勵(lì)函數(shù)進(jìn)行設(shè)計(jì)。

為了計(jì)算方便，機(jī)器人在環(huán)境中的位置表示為機(jī)器人的狀態(tài)。即s={X,V}，其中，X表示機(jī)器人的任意時(shí)刻位置及各個(gè)障礙的位置信息，V表示機(jī)器人的在當(dāng)前狀態(tài)下可能采取的動(dòng)作。

為了提高訓(xùn)練速度，加快Q表收斂，在本文中將動(dòng)作空間離散為A∈{0°，90°,180°,360°}，在柵格環(huán)境內(nèi)對(duì)應(yīng)向右、向上、向左，向下。

本文獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)為：當(dāng)智能體與目標(biāo)點(diǎn)的當(dāng)前距離小于前一時(shí)刻與目標(biāo)點(diǎn)的距離時(shí)，獎(jiǎng)勵(lì)設(shè)為+2n；反之，獎(jiǎng)勵(lì)設(shè)為-6n。當(dāng)智能體與障礙物相撞時(shí)，獎(jiǎng)勵(lì)設(shè)為-40n。其他可行區(qū)域的獎(jiǎng)勵(lì)值設(shè)為0。獎(jiǎng)勵(lì)函數(shù)的表達(dá)式為：

(13)

3.4 階段Q學(xué)習(xí)路徑規(guī)劃算法流程

根據(jù)上述內(nèi)容，給出階段Q學(xué)習(xí)路徑規(guī)劃算法步驟如下：

步驟2：計(jì)算本次階段的初始步長k，計(jì)算已完成路徑規(guī)劃的所有階段的總步長T。判斷是否滿足重置變量因子條件，若滿足k≥T，進(jìn)入步驟5，否則重置變量因子。

步驟3：重置變量因子。在當(dāng)前階段探索前，將ε-貪婪算法的隨機(jī)變量σ置為0。

步驟4：判斷重置因子結(jié)束條件。當(dāng)前步長k′是否等于本次階段初始步長k，若不滿足，轉(zhuǎn)入步驟3。

步驟5：迭代探索。根據(jù)ε-貪婪算法選擇動(dòng)作與環(huán)境交互，根據(jù)在環(huán)境中得到的獎(jiǎng)勵(lì)更新Q表。

步驟6：判斷當(dāng)前階段獎(jiǎng)勵(lì)值重復(fù)次數(shù)，如果未達(dá)到獎(jiǎng)勵(lì)閾值Rmax，則轉(zhuǎn)入步驟5。

步驟7：判斷是否到達(dá)目標(biāo)點(diǎn)，如果未達(dá)到目標(biāo)點(diǎn)，跳出當(dāng)前階段路徑規(guī)劃，進(jìn)入下一階段路徑規(guī)劃，轉(zhuǎn)入步驟2。如果達(dá)到目標(biāo)點(diǎn)，則完成全局最優(yōu)路徑規(guī)劃。

根據(jù)上述算法流程可得到算法流程如圖3所示。

圖3 階段Q學(xué)習(xí)算法路徑規(guī)劃流程框圖

4 仿真與分析

4.1 仿真條件設(shè)定

為驗(yàn)證提出的階段Q學(xué)習(xí)算法的可行性和有效性，本文將在Pycharm2020.1.3環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，采用Open AI的Gym環(huán)境建立柵格環(huán)境。

操作系統(tǒng)環(huán)境為Windows10 x64，使用軟件工具包版本為Python3.6，硬件信息為Intel i7-9750H、DDR4 16GB和1.86TB SSD。

4.2 階段Q學(xué)習(xí)路徑規(guī)劃算法仿真驗(yàn)證

在同一實(shí)驗(yàn)環(huán)境下將本文階段Q學(xué)習(xí)算法與傳統(tǒng)Q學(xué)習(xí)算法進(jìn)行對(duì)比。算法參數(shù)為：環(huán)境信息n=20，最大步長2n=40，階段數(shù)量N=4，探索次數(shù)m=5，獎(jiǎng)勵(lì)閾值Rmax=3，學(xué)習(xí)系數(shù)α=0.2，折扣因子γ=0.9。在安全避障且能達(dá)到目標(biāo)點(diǎn)的前提下，以最快路徑規(guī)劃為指標(biāo)，分別采用傳統(tǒng)Q學(xué)習(xí)算法和階段Q學(xué)習(xí)算法進(jìn)行仿真計(jì)算。仿真結(jié)果如圖4、圖5、圖6及表1所示。

圖4 傳統(tǒng)Q學(xué)習(xí)規(guī)劃路徑示意圖

圖5 階段Q學(xué)習(xí)規(guī)劃路徑示意圖

圖6 回合數(shù)-獎(jiǎng)勵(lì)值曲線

通過對(duì)比分析圖4、圖5及表1中仿真結(jié)果可知，本文設(shè)計(jì)的階段Q學(xué)習(xí)算法能夠有效規(guī)避路徑中的障礙。在相同的仿真環(huán)境下，階段Q學(xué)習(xí)在路徑規(guī)劃時(shí)間及算法收斂時(shí)間指標(biāo)上均優(yōu)于傳統(tǒng)Q學(xué)習(xí)。階段Q學(xué)習(xí)算法路徑規(guī)劃時(shí)間為202s，相比傳統(tǒng)Q學(xué)習(xí)規(guī)劃路徑時(shí)間398s減少了49%。階段Q學(xué)習(xí)算法在第22回合開始收斂，傳統(tǒng)Q學(xué)習(xí)算法第36回合開始收斂，同比降低了39%。

表1 2種算法的仿真數(shù)據(jù)

4.3 調(diào)整各階段探索步長仿真驗(yàn)證

在同一實(shí)驗(yàn)環(huán)境下，采用階段Q學(xué)習(xí)算法將不同的階段數(shù)量時(shí)的路徑規(guī)劃情況進(jìn)行對(duì)比。仿真環(huán)境仍為大小為20*20的網(wǎng)格環(huán)境。

算法參數(shù)同3.2節(jié)。在安全避障且能達(dá)到目標(biāo)點(diǎn)的前提下，以最快路徑規(guī)劃為指標(biāo)，采用改進(jìn)Q學(xué)習(xí)算法分別設(shè)置不同的階段數(shù)量進(jìn)行仿真計(jì)算，仿真結(jié)果如圖7、圖8及表2所示。

圖7 不同階段數(shù)量的收斂回合數(shù)直方圖

圖8 不同階段數(shù)量的路徑規(guī)劃時(shí)間直方圖

通過對(duì)比分析圖7、圖8及表2仿真結(jié)果可知，階段Q學(xué)習(xí)算法中不同階段數(shù)量會(huì)影響算法的收斂速度和路徑規(guī)劃時(shí)間。其中，當(dāng)N=2時(shí)，算法的路徑規(guī)劃時(shí)間和收斂回合數(shù)最小，分別為196 s，30。當(dāng)N逐漸增大時(shí)，算法的路徑規(guī)劃時(shí)間和收斂回合數(shù)隨之增大，這一現(xiàn)象與獎(jiǎng)勵(lì)閾值設(shè)置有關(guān)。不論獎(jiǎng)勵(lì)閾值設(shè)置的大小，當(dāng)階段數(shù)量變多時(shí)，機(jī)器人在每一階段探索時(shí)會(huì)重復(fù)之前所有階段的路徑，這將影響算法的學(xué)習(xí)效率和收斂時(shí)間。值得注意的是，當(dāng)N=1時(shí)，意味著1次性規(guī)劃從起始點(diǎn)到終止點(diǎn)的路徑，這時(shí)階段Q學(xué)習(xí)算法等價(jià)于傳統(tǒng)Q學(xué)習(xí)算法。

表2 不同階段數(shù)量的仿真數(shù)據(jù)

根據(jù)以上仿真結(jié)果可知，階段Q學(xué)習(xí)算法相比傳統(tǒng)Q學(xué)習(xí)算法更優(yōu)，而且收斂時(shí)間更短。這是由于采用了分步最優(yōu)搜索改進(jìn)了Q學(xué)習(xí)算法中的搜索方式，避免了訓(xùn)練中選擇動(dòng)作的不確定性，因此可以提高算法的學(xué)習(xí)效率。此外，不同的階段數(shù)量N將會(huì)影響階段Q學(xué)習(xí)算法的收斂速度，通過設(shè)置合理的階段數(shù)量可以有效提高階段Q學(xué)習(xí)算法的學(xué)習(xí)效率，減少算法的收斂時(shí)間。

4 結(jié)論

1) 為了提高算法的收斂速度和學(xué)習(xí)效率，借鑒最優(yōu)控制思想，提出了基于階段Q學(xué)習(xí)算法，通過設(shè)置探索步長和獎(jiǎng)勵(lì)值，確保每一階段探索為最優(yōu)路徑，提高算法收斂速度。

2) 階段Q學(xué)習(xí)算法與傳統(tǒng)Q學(xué)習(xí)算法仿真對(duì)比可知，階段Q學(xué)習(xí)算法能夠明顯提升算法收斂速度，減小路徑規(guī)劃時(shí)間，更利于機(jī)器人的行駛。