基于模擬退火策略的強化學習路徑規劃算法

季野彪，牛龍輝

（西安工程大學電子信息學院，西安710000）

0 引言

隨著無人駕駛[1]的興起，機器人導航技術[2]越來越受到人們的重視。對于機器人導航技術的研究，其核心在于路徑規劃[3]，即在特定環境下，依據某些規則，規劃出一條從起始點到目標點的最優無碰撞路徑[4]。強化學習是近年來發展迅速的一種機器學習算法，并在移動機器人路徑規劃領域取得了較好的應用。強化學習算法中，agent 通過與環境的交互進行試錯學習，從而獲得獎賞值，最終規劃出一條獎賞值最高的最優路徑[5]。

傳統的Q（λ）學習算法進行路徑規劃[6]時，agent 每到一個狀態，其動作選擇策略都會有一個固定的探索因子決定下一個動作是探索環境還是利用環境。對于探索因子的設計往往會影響算法的性能，過大的探索因子會導致agent 對環境知識的利用不夠，影響算法收斂速度，過小的探索因子會導致算法陷入局部最優。

本文針對Q（λ）學習算法中探索因子的設計問題，通過加入模擬退火（Simulated Annealing，SA）[7]的思想，提出了基于模擬退火策略的Q（λ）學習算法（SA-Q（λ））。改進的SA-Q（λ）學習算法中探索因子動態變化，學習初期探索因子較高，agent 以較大的概率選擇隨機動作，以便盡快地了解環境。隨著學習幕數的增加，探索因子根據退火規則逐漸減小，agent 以較大的概率選擇最優動作。實驗表明，改進的SA-Q（λ）學習算法加快了agent 規劃出最優路徑、提高了算法的收斂速度。

1 強化學習

1.1 簡介

強化學習是機器學習的一種類型，通過與環境交互獲得反饋，目的是為得到較高的正回報。在學習過程中給定agent 獎賞和懲罰的規則，agent 根據自身的經驗不斷發現能夠獲得獎賞的動作，最終學習出一條獎賞值最高的狀態——動作鏈[8]。圖1 所示為強化學習過程中agent 與環境的交互過程。首先，agent 獲取當前所處狀態s，并依據動作選擇策略選擇動作a；隨后，采取動作a，環境狀態由s 轉移到s'，同時給出獎賞值r；最后，agent 通過獎賞值r 以及值更新公式更新狀態-動作值。

標準的強化學習算法框架包含四大要素[9]：

（1）環境模型

環境模型提供了agent 進行學習的環境，并設計了狀態和動作之間的映射空間。

（2）策略

策略π 提供了agent 在各個狀態選擇動作的依據。

（3）獎賞函數

獎賞函數r 為agent 執行一次動作之后，環境對該動作是否有利于達成目標的評價，r 值越大則表明該動作越利于達成目標。

（4）值函數[10]

值函數V 是agent 選擇的動作的期望回報，通過對值函數的更新提高回報動作的選擇概率，降低其他動作的選擇概率，從而獲得較大的期望回報。

根據選擇不同動作所獲得的回報值不同調整策略，使得回報最大化：

圖1 強化學習中的智能體-環境交互過程

1.2 Q（λ）學習算法

Q（λ）學習算法是在經典Q 學習算法中加入資格跡，由單步更新變為多步更新。在當前回報較好的情況下，不僅更新當前狀態，并為導致到達該狀態的某些先前狀態分配一些回報，大大提高了算法的收斂時間。

傳統的Q 學習算法的Q 值更新公式如下[11]：

式中：Q(s，a)和Q(s'，a')為狀態s 和狀態s'下執行動作a 和a'對應的Q 值；r 為環境由狀態s 經過動作轉移到狀態s'后給出的立即強化信號，即獎勵函數值；α和γ 分別為學習率和折扣因子。

在引入資格跡后，Q（λ）學習算法的Q 值更新公式如下[12]：

式中：E(s，a)為資格跡，資格跡初始值都為0，當agent 經過某個狀態時，當前時刻該狀態上的資格跡值為1。在執行后續動作時，資格跡E(s，a)中的值依據下式衰減：

式中：λ 為資格跡衰減因子，agent 每執行一次動作，狀態s 處的資格跡值就根據上式衰減一次。

Agent 在每一個狀態下，都依據貪婪策略選擇即將采取的動作，該策略往往會導致算法陷入局部最優，且無法在增加學習周期的情況下跳出局部最優。為避免算法陷入局部最優以及提高算法的收斂速度，本文提出了動態調整探索因子的思想。將Q（λ）學習算法與模擬退火中Metropolis 規則[13]相結合，使得算法學習前期探索因子較大，學習后期探索因子較小，既避免了算法陷入局部最優，又保證了算法的收斂速度，全面提高了算法性能。

2 基于模擬退火的策略的Q（λ）算法

2.1 模擬退火算法

模擬退火算法最早的思想是由N.Metropolis 等人于1953 年提出。1983 年，S.Kirkpatrick 等人成功將退火思想引入到優化組合問題領域[14]。模擬退火算法從某一較高初溫出發，伴隨溫度參數的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，通過跳出局部最優的機制達到全局最優[15]。

2.2 模擬退火算法

將模擬退火算法中跳出局部最優的思想引入到Q（λ）算法中的動作選擇策略中，設計自適應的動態探索因子，使得agent 學習前期探索到的路徑多樣性提高，避免在路徑規劃時陷入局部最優。同時，隨著降火過程，探索因子逐漸減小，提高算法的收斂速度。基于模擬退火的動作選擇策略具體步驟如下：

（1）agent 在狀態st時刻，隨機動作為ar，回報值最高的動作為ap；

（2）產生（0，1）之間的隨機數δ；

（3）判斷δ 與p=e((Q(st，ar)-Q(st，ap))/Tt)之間的大小關系，若δ

（4）判斷是否至冷卻狀態，若至冷卻狀態，則T=Tmin。

根據上述動作選擇策略，將改進的SA-Q(λ)學習算法應用于移動機器人路徑規劃，具體執行過程如下路徑規劃步驟如下：

Set initial temperature T，the end temperature Tmin，the rate of fire reduction q

Initialize Q(s，a)arbitrarily，for all s ∈S，a ∈A(s)

Repeat（for each episode）:

E(s，a)=0，for all s ∈S，a ∈A(s)

Initialize s，a

T=T×q

Repeat（for each step of episode）:

Choose a from s using simulated annealing strategy

Take action a，observe r，s'

δ=r+γ maxa'Q(s'，a')-Q(s，a)

E(s，a)←1

For all s ∈S，a ∈A(s):

Q(s，a)←Q(s，a)+αδE(s，a)

E(s，a)←γλE(s.a)

s ←s'

Until s is terminal

Until learning cycles reach set values

每一幕開始之前進行等比降溫操作，保證了隨著學習幕數的增加，動作選擇策略中選擇隨機動作的概率逐漸減小，保證了算法收斂速度能夠有效提高。在溫度降至冷卻時刻后，動作選擇策略中選擇隨機動作的概率幾乎為0，保證了算法能夠穩定收斂。

3 實驗及結果分析

3.1 實驗環境

實驗環境為一個20×20 的柵格世界[16]，如圖2 所示。每個柵格代表智能體的一種狀態。黑色柵格為障礙物，白色柵格為可移動區域。對agent 而言，環境是未知的，且環境中的障礙物與目標都是靜態的。Agent的運動方向可分為上、下、左、右，分別代表agent 的四個可選動作。

圖2 試驗環境

3.2 試驗參數的設計

本實驗中獎懲函數的設計如下：

智能體在環境中移動，未碰到障礙物時，獎勵值為0；碰到障礙物，則獲得獎勵值-1，到達終點時獲得獎勵值10。根據需要，本文將模擬退火參數設置為：初始溫度T=300，降溫速率q=0.95，常溫Tmin=10-8。設置每一幕中最大移動步數為40000，智能體到達目標或者步數超過40000，則該幕結束。

本文比較學習算法和學習算法的收斂速度，算法中的學習率、折扣因子及策略設置如表1 所示。

表1 兩種學習算法參數設置

3.3 試驗及結果分析

由上述仿真環境以及設置的參數對Q(λ)和SA-Q(λ)兩種算法進行仿真試驗，比較了Q(λ)學習算法與SA-Q(λ)算法的收斂速度。在環境中，設置agent的起始點位置為（0，20），終止點位置為（20，0）。圖3所示為算法收斂速度對比圖，紅色曲線為Q(λ)學習算法收斂曲線，藍色曲線為本文SA-Q(λ)學習算法收斂曲線。圖中可見兩種算法在學習初期都花費較多步數才能到達目標點，而在60 幕之后，本文提出的SA-Q(λ)學習算法隨著降火策略調整探索因子之后，規劃的路徑長度明顯減小，并且于200 幕后算法收斂。傳統的Q(λ)學習算法由于存在0.1 的探索因子，算法在收斂后仍有一定的波動。圖4 為SA-Q(λ)算法收斂后規劃出的最優路徑，路徑長度為38，證實為最優路徑。

4 結語

本文提出了改進的SA-Q(λ)學習算法，平衡了智能體路徑規劃中探索與利用的關系，既避免了算法陷入局部最優，也有效提高了算法收斂速度。在20×20的柵格環境中，通過對比Q(λ)和SA-Q(λ)學習算法的收斂速度，得出SA-Q(λ)學習算法在學習初期對環境的探索率高，同時隨著降火的過程算法對環境的利用提高的結論。在本文的研究工作中，筆者發現降火過程中降火函數的選取在一定程度上也會對算法收斂速度有很大的影響，在今后的研究中將針對降火函數做改進，進一步提高強化學習算法的收斂速度。

圖3 算法收斂對比圖

圖4 路徑效果圖