基于模擬退火策略的強(qiáng)化學(xué)習(xí)路徑規(guī)劃算法

季野彪，牛龍輝

（西安工程大學(xué)電子信息學(xué)院，西安710000）

0 引言

隨著無人駕駛[1]的興起，機(jī)器人導(dǎo)航技術(shù)[2]越來越受到人們的重視。對于機(jī)器人導(dǎo)航技術(shù)的研究，其核心在于路徑規(guī)劃[3]，即在特定環(huán)境下，依據(jù)某些規(guī)則，規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)無碰撞路徑[4]。強(qiáng)化學(xué)習(xí)是近年來發(fā)展迅速的一種機(jī)器學(xué)習(xí)算法，并在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域取得了較好的應(yīng)用。強(qiáng)化學(xué)習(xí)算法中，agent 通過與環(huán)境的交互進(jìn)行試錯(cuò)學(xué)習(xí)，從而獲得獎(jiǎng)賞值，最終規(guī)劃出一條獎(jiǎng)賞值最高的最優(yōu)路徑[5]。

傳統(tǒng)的Q（λ）學(xué)習(xí)算法進(jìn)行路徑規(guī)劃[6]時(shí)，agent 每到一個(gè)狀態(tài)，其動(dòng)作選擇策略都會有一個(gè)固定的探索因子決定下一個(gè)動(dòng)作是探索環(huán)境還是利用環(huán)境。對于探索因子的設(shè)計(jì)往往會影響算法的性能，過大的探索因子會導(dǎo)致agent 對環(huán)境知識的利用不夠，影響算法收斂速度，過小的探索因子會導(dǎo)致算法陷入局部最優(yōu)。

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

1 強(qiáng)化學(xué)習(xí)

1.1 簡介

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一種類型，通過與環(huán)境交互獲得反饋，目的是為得到較高的正回報(bào)。在學(xué)習(xí)過程中給定agent 獎(jiǎng)賞和懲罰的規(guī)則，agent 根據(jù)自身的經(jīng)驗(yàn)不斷發(fā)現(xiàn)能夠獲得獎(jiǎng)賞的動(dòng)作，最終學(xué)習(xí)出一條獎(jiǎng)賞值最高的狀態(tài)——?jiǎng)幼麈淸8]。圖1 所示為強(qiáng)化學(xué)習(xí)過程中agent 與環(huán)境的交互過程。首先，agent 獲取當(dāng)前所處狀態(tài)s，并依據(jù)動(dòng)作選擇策略選擇動(dòng)作a；隨后，采取動(dòng)作a，環(huán)境狀態(tài)由s 轉(zhuǎn)移到s'，同時(shí)給出獎(jiǎng)賞值r；最后，agent 通過獎(jiǎng)賞值r 以及值更新公式更新狀態(tài)-動(dòng)作值。

標(biāo)準(zhǔn)的強(qiáng)化學(xué)習(xí)算法框架包含四大要素[9]：

（1）環(huán)境模型

環(huán)境模型提供了agent 進(jìn)行學(xué)習(xí)的環(huán)境，并設(shè)計(jì)了狀態(tài)和動(dòng)作之間的映射空間。

（2）策略

策略π 提供了agent 在各個(gè)狀態(tài)選擇動(dòng)作的依據(jù)。

（3）獎(jiǎng)賞函數(shù)

獎(jiǎng)賞函數(shù)r 為agent 執(zhí)行一次動(dòng)作之后，環(huán)境對該動(dòng)作是否有利于達(dá)成目標(biāo)的評價(jià)，r 值越大則表明該動(dòng)作越利于達(dá)成目標(biāo)。

（4）值函數(shù)[10]

值函數(shù)V 是agent 選擇的動(dòng)作的期望回報(bào)，通過對值函數(shù)的更新提高回報(bào)動(dòng)作的選擇概率，降低其他動(dòng)作的選擇概率，從而獲得較大的期望回報(bào)。

根據(jù)選擇不同動(dòng)作所獲得的回報(bào)值不同調(diào)整策略，使得回報(bào)最大化：

圖1 強(qiáng)化學(xué)習(xí)中的智能體-環(huán)境交互過程

1.2 Q（λ）學(xué)習(xí)算法

Q（λ）學(xué)習(xí)算法是在經(jīng)典Q 學(xué)習(xí)算法中加入資格跡，由單步更新變?yōu)槎嗖礁?。在?dāng)前回報(bào)較好的情況下，不僅更新當(dāng)前狀態(tài)，并為導(dǎo)致到達(dá)該狀態(tài)的某些先前狀態(tài)分配一些回報(bào)，大大提高了算法的收斂時(shí)間。

傳統(tǒng)的Q 學(xué)習(xí)算法的Q 值更新公式如下[11]：

式中：Q(s，a)和Q(s'，a')為狀態(tài)s 和狀態(tài)s'下執(zhí)行動(dòng)作a 和a'對應(yīng)的Q 值；r 為環(huán)境由狀態(tài)s 經(jīng)過動(dòng)作轉(zhuǎn)移到狀態(tài)s'后給出的立即強(qiáng)化信號，即獎(jiǎng)勵(lì)函數(shù)值；α和γ 分別為學(xué)習(xí)率和折扣因子。

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

式中：E(s，a)為資格跡，資格跡初始值都為0，當(dāng)agent 經(jīng)過某個(gè)狀態(tài)時(shí)，當(dāng)前時(shí)刻該狀態(tài)上的資格跡值為1。在執(zhí)行后續(xù)動(dòng)作時(shí)，資格跡E(s，a)中的值依據(jù)下式衰減：

式中：λ 為資格跡衰減因子，agent 每執(zhí)行一次動(dòng)作，狀態(tài)s 處的資格跡值就根據(jù)上式衰減一次。

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

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

2.1 模擬退火算法

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

2.2 模擬退火算法

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

（1）agent 在狀態(tài)st時(shí)刻，隨機(jī)動(dòng)作為ar，回報(bào)值最高的動(dòng)作為ap；

（2）產(chǎn)生（0，1）之間的隨機(jī)數(shù)δ；

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

（4）判斷是否至冷卻狀態(tài)，若至冷卻狀態(tài)，則T=Tmin。

根據(jù)上述動(dòng)作選擇策略，將改進(jìn)的SA-Q(λ)學(xué)習(xí)算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，具體執(zhí)行過程如下路徑規(guī)劃步驟如下：

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

每一幕開始之前進(jìn)行等比降溫操作，保證了隨著學(xué)習(xí)幕數(shù)的增加，動(dòng)作選擇策略中選擇隨機(jī)動(dòng)作的概率逐漸減小，保證了算法收斂速度能夠有效提高。在溫度降至冷卻時(shí)刻后，動(dòng)作選擇策略中選擇隨機(jī)動(dòng)作的概率幾乎為0，保證了算法能夠穩(wěn)定收斂。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為一個(gè)20×20 的柵格世界[16]，如圖2 所示。每個(gè)柵格代表智能體的一種狀態(tài)。黑色柵格為障礙物，白色柵格為可移動(dòng)區(qū)域。對agent 而言，環(huán)境是未知的，且環(huán)境中的障礙物與目標(biāo)都是靜態(tài)的。Agent的運(yùn)動(dòng)方向可分為上、下、左、右，分別代表agent 的四個(gè)可選動(dòng)作。

圖2 試驗(yàn)環(huán)境

3.2 試驗(yàn)參數(shù)的設(shè)計(jì)

本實(shí)驗(yàn)中獎(jiǎng)懲函數(shù)的設(shè)計(jì)如下：

智能體在環(huán)境中移動(dòng)，未碰到障礙物時(shí)，獎(jiǎng)勵(lì)值為0；碰到障礙物，則獲得獎(jiǎng)勵(lì)值-1，到達(dá)終點(diǎn)時(shí)獲得獎(jiǎng)勵(lì)值10。根據(jù)需要，本文將模擬退火參數(shù)設(shè)置為：初始溫度T=300，降溫速率q=0.95，常溫Tmin=10-8。設(shè)置每一幕中最大移動(dòng)步數(shù)為40000，智能體到達(dá)目標(biāo)或者步數(shù)超過40000，則該幕結(jié)束。

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

表1 兩種學(xué)習(xí)算法參數(shù)設(shè)置

3.3 試驗(yàn)及結(jié)果分析

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

4 結(jié)語

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

圖3 算法收斂對比圖

圖4 路徑效果圖