結(jié)合神經(jīng)網(wǎng)絡(luò)和Q（λ）-learning 的路徑規(guī)劃方法

王 健，張平陸，趙忠英，程曉鵬

（1.沈陽(yáng)新松機(jī)器人自動(dòng)化股份有限公司 特種機(jī)器人BG，沈陽(yáng)110169；2.沈陽(yáng)科技學(xué)院 機(jī)械與交通工程系，沈陽(yáng)110167）

路徑規(guī)劃是移動(dòng)機(jī)器人的一項(xiàng)重要功能，用于引導(dǎo)移動(dòng)機(jī)器人在地圖中自主運(yùn)動(dòng)。 路徑規(guī)劃的優(yōu)劣直接影響移動(dòng)機(jī)器人的運(yùn)動(dòng)效率、機(jī)器損耗和工作效率。 與其它機(jī)器學(xué)習(xí)方法不同，增強(qiáng)學(xué)習(xí)方法無(wú)需監(jiān)督信號(hào)，而是通過智能體與環(huán)境之間的信息交互進(jìn)行“試錯(cuò)”，以極大化評(píng)價(jià)反饋信號(hào)為目標(biāo)，通過學(xué)習(xí)得到最優(yōu)或次優(yōu)的搜索策略。 總體來(lái)說，增強(qiáng)學(xué)習(xí)的主要目標(biāo)就是將狀態(tài)映射到動(dòng)作的同時(shí)，最大化期望回報(bào)。

隨著增強(qiáng)學(xué)習(xí)理論和算法的不斷發(fā)展與成熟，應(yīng)用增強(qiáng)學(xué)習(xí)方法解決移動(dòng)機(jī)器人路徑規(guī)劃問題正成為路徑規(guī)劃的研究熱點(diǎn)[1]。 文獻(xiàn)[2]提出了改進(jìn)的Q-learning 方法用于解決單個(gè)機(jī)器人的路徑規(guī)劃問題， 通過引入標(biāo)志位減少了學(xué)習(xí)過程的收斂時(shí)間，提高了算法的效率；文獻(xiàn)[3]提出用神經(jīng)網(wǎng)絡(luò)模型來(lái)解決最短路徑規(guī)劃問題；文獻(xiàn)[4]提出基于分層強(qiáng)化學(xué)習(xí)的路徑規(guī)劃方法；文獻(xiàn)[5]對(duì)基于神經(jīng)網(wǎng)絡(luò)和POS 的機(jī)器人路徑規(guī)劃方法做了較為深入的研究。 強(qiáng)化學(xué)習(xí)是目前機(jī)器學(xué)習(xí)中富有挑戰(zhàn)性和廣泛應(yīng)用前景的研究領(lǐng)域之一[6]。

目前，傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法在移動(dòng)機(jī)器人路徑規(guī)劃應(yīng)用中，由于其學(xué)習(xí)初始階段對(duì)環(huán)境沒有先驗(yàn)知識(shí)，往往存在收斂速度慢、學(xué)習(xí)時(shí)間長(zhǎng)等問題。 故在此通過引入神經(jīng)網(wǎng)絡(luò)方法， 對(duì)傳統(tǒng)Q-learning 算法進(jìn)行改進(jìn)，優(yōu)化設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，提出了基于神經(jīng)網(wǎng)絡(luò)的改進(jìn)Q-learning 學(xué)習(xí)算法。

1 Q（λ）-learning 算法

Q-learning 是一種與模型無(wú)關(guān)的強(qiáng)化學(xué)習(xí)方法，在環(huán)境未知條件下，通過不斷試錯(cuò)和探索，對(duì)所有可能的狀態(tài)和動(dòng)作進(jìn)行多次嘗試，采用數(shù)值迭代方法逼近最優(yōu)解。

它以狀態(tài)-動(dòng)作對(duì)應(yīng)的Q（s，a）為估計(jì)函數(shù)，逐漸減小相鄰狀態(tài)間Q 值估計(jì)的差異達(dá)到收斂條件，即

式中：S 為狀態(tài)集；A 為動(dòng)作集；T（s，a，a′）為狀態(tài)s下執(zhí)行動(dòng)作a 后轉(zhuǎn)換到狀態(tài)s′的概率；R（s，a）為狀態(tài)s 下執(zhí)行動(dòng)作a 的獎(jiǎng)勵(lì)；γ 為折扣因子。 尋找最優(yōu)Q 值Q*（s，a）的搜索策略為

更新公式為

在Q-learning 算法中引入跡的思想， 能夠記錄狀態(tài)被訪問的次數(shù)，在更新前一時(shí)刻的狀態(tài)值函數(shù)時(shí)， 也能對(duì)之前的狀態(tài)值函數(shù)進(jìn)行更新， 即Q（λ）-learning 算法。 其更新公式為

式中：Isst和Iaat為指數(shù)函數(shù)，如果s=st則值為1，反之為0。 誤差項(xiàng)為

更新動(dòng)作公式為

搜索函數(shù)為

式中：σ 為0～1 之間的隨機(jī)數(shù)；ε 為探索因子，為0～1 之間的數(shù)。

2 受生物啟發(fā)的神經(jīng)網(wǎng)絡(luò)方法

受生物神經(jīng)系統(tǒng)中Hodgkin 和Huxley 細(xì)胞膜模型[7]與Grossberg 分流細(xì)胞模型[8]的啟發(fā)，文獻(xiàn)[9]提出了受生物啟發(fā)的神經(jīng)網(wǎng)絡(luò)方法，用于解決移動(dòng)機(jī)器人路徑規(guī)劃問題。 該神經(jīng)網(wǎng)絡(luò)方法狀態(tài)方程為

其中

式中：xi為第i 個(gè)神經(jīng)元的神經(jīng)活動(dòng) （神經(jīng)元細(xì)胞膜的電勢(shì)）；A，B，D 分別為被動(dòng)衰減率、神經(jīng)活動(dòng)的上限和下限， 均為非負(fù)常數(shù)；和[Ii]-為第i 個(gè)神經(jīng)元的刺激性、抑制性輸入；Ii為第i 個(gè)神經(jīng)元內(nèi)部輸入；E 為正整數(shù)，且E＞＞B；[]-，[]+分別為取正、取負(fù)函數(shù)。該取正、取負(fù)函數(shù)的功能為

狀態(tài)方程（8）中，第i 個(gè)神經(jīng)元與第j 個(gè)神經(jīng)元之間的權(quán)值連接ωij為一個(gè)距離函數(shù)。 其表達(dá)式為

其中

式中：dij為狀態(tài)qi和qj之間的歐氏距離；μ 和r0為正整數(shù)。

該神經(jīng)網(wǎng)絡(luò)方法不需要學(xué)習(xí)過程，根據(jù)神經(jīng)元細(xì)胞之間的信息傳遞，可以求出神經(jīng)元細(xì)胞所在狀態(tài)的勢(shì)值函數(shù)。 通過實(shí)時(shí)更新勢(shì)值函數(shù)，移動(dòng)機(jī)器人從初始位置沿著勢(shì)值增大的方向到達(dá)目標(biāo)位置，從而得到規(guī)劃路徑。

3 結(jié)合神經(jīng)網(wǎng)絡(luò)和Q（λ）-learning 算法

3.1 優(yōu)化設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)

在Q-learning 算法中，獎(jiǎng)勵(lì)R（s，a）表示狀態(tài)s下執(zhí)行動(dòng)作a 得到的獎(jiǎng)勵(lì)。 獎(jiǎng)勵(lì)值的大小直接影響動(dòng)作選擇的正確性和誤差傳遞的效率。 因此，獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)的好壞，直接影響算法的收斂速度和最優(yōu)解的質(zhì)量。

傳統(tǒng)的Q-learning 算法， 一般將目標(biāo)狀態(tài)的獎(jiǎng)勵(lì)設(shè)為很大的正整數(shù)，障礙物狀態(tài)設(shè)為很小的負(fù)整數(shù)，其余狀態(tài)處的回報(bào)值均為0。這種方式的獎(jiǎng)勵(lì)函數(shù)沒有啟發(fā)性，機(jī)器人在初期學(xué)習(xí)階段很難到達(dá)目標(biāo)，導(dǎo)致收斂速度很慢。

在此，獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)采用文獻(xiàn)[9]所提神經(jīng)網(wǎng)絡(luò)方法。 令狀態(tài)方程（8）中，A=10，B=D=1，E=100，μ=1，r0=2，則狀態(tài)方程轉(zhuǎn)化為

該神經(jīng)網(wǎng)絡(luò)模型可以確保從目標(biāo)狀態(tài)發(fā)出的刺激性信息，通過神經(jīng)元之間的橫向連接，傳遞給該工作空間的所有狀態(tài)，而從障礙物傳出的抑制性信息只在有限的范圍內(nèi)傳播。

通過狀態(tài)方程（11）可以得到每個(gè)狀態(tài)勢(shì)值，勢(shì)值矩陣為X。 將獎(jiǎng)勵(lì)函數(shù)定義為

式中：X（S′）為執(zhí)行下一個(gè)動(dòng)作的狀態(tài)勢(shì)值；X（S）為當(dāng)前狀態(tài)勢(shì)值。

3.2 算法實(shí)現(xiàn)流程

結(jié)合神經(jīng)網(wǎng)絡(luò)和Q（λ）-learning 算法，具體的實(shí)現(xiàn)步驟如下：

步驟1利用狀態(tài)方程（11），經(jīng)過k 次迭代，求出狀態(tài)勢(shì)值矩陣；

步驟2根據(jù)式（12），計(jì)算出獎(jiǎng)勵(lì)函數(shù)R（s，a）；

步驟3進(jìn)行第i 次迭代計(jì)算， 最大迭代次數(shù)為n；

步驟4生成隨機(jī)數(shù)σ，執(zhí)行式（7）搜索策略π（s）；

步驟5執(zhí)行動(dòng)作a，得到獎(jiǎng)勵(lì)R（s，a），轉(zhuǎn)移到新狀態(tài)s′；

步驟6判斷s′是否為終止?fàn)顟B(tài)， 如果是則跳到步驟3 進(jìn)行下一次迭代（i=i+1），不是則跳到步驟7；

步驟7根據(jù)式（5），計(jì)算誤差；

步驟8根據(jù)式（4），更新動(dòng)作狀態(tài)跡，并更新其他動(dòng)作狀態(tài)跡；

步驟9根據(jù)式（6），更新動(dòng)作值函數(shù)；

步驟10s←s′，跳到步驟3，搜索下一個(gè)狀態(tài)。

算法完成一次訓(xùn)練的流程如圖1 所示。 該算法在迭代學(xué)習(xí)之前對(duì)根據(jù)環(huán)境地圖信息進(jìn)行狀態(tài)勢(shì)值計(jì)算，獲得先驗(yàn)知識(shí)，以指導(dǎo)獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)，從而提高算法的收斂速度和最優(yōu)解的質(zhì)量。

4 仿真試驗(yàn)與結(jié)果分析

通過仿真試驗(yàn)來(lái)驗(yàn)證改進(jìn)方法的有效性，試驗(yàn)環(huán)境采用20×20 柵格地圖（如圖2 所示），以圖中左上角S 為移動(dòng)機(jī)器人的起點(diǎn)， 以右下角E 為目標(biāo)。圖中， 白色部分為移動(dòng)機(jī)器人的自由運(yùn)動(dòng)區(qū)間；黑色部分為障礙物，移動(dòng)機(jī)器人無(wú)法穿越該區(qū)域。

圖1 結(jié)合神經(jīng)網(wǎng)絡(luò)和Q（λ）-learning 算法流程Fig.1 Algorithm based on neural network and Q（λ）-learning flow chart

圖2 最優(yōu)策略示意圖Fig.2 Optimal strategy schematic diagram

移動(dòng)機(jī)器人動(dòng)作集A 包括上移、右上、右移、右下、下移、左下、左移、左上等8 個(gè)動(dòng)作；狀態(tài)集包括400 個(gè)位置，障礙物和目標(biāo)狀態(tài)為終止?fàn)顟B(tài)。當(dāng)移動(dòng)機(jī)器人移動(dòng)到終止?fàn)顟B(tài)， 則本次訓(xùn)練循環(huán)結(jié)束，重新進(jìn)行下一次訓(xùn)練。

采用神經(jīng)網(wǎng)絡(luò)方法經(jīng)過1000 次迭代計(jì)算得到的勢(shì)值分布如圖3 所示。 根據(jù)式（12）處理狀態(tài)勢(shì)值可以得到獎(jiǎng)勵(lì)函數(shù)R（s，a）。

圖3 狀態(tài)勢(shì)值分布Fig.3 State potential value distribution

算法中幾個(gè)重要的參數(shù)會(huì)直接影響收斂速度。仿真試驗(yàn)中，折扣因子γ 初始化為0.8，學(xué)習(xí)速率α初始化為0.05，探索因子ε 初始化為0.5，最大探索步數(shù)初始化為400。當(dāng)搜索步數(shù)超過最大步數(shù)時(shí)，仍未到達(dá)終止?fàn)顟B(tài)，則認(rèn)為此次訓(xùn)練失敗，重新進(jìn)入下一次訓(xùn)練。

采用經(jīng)典Q-learning 方法， 在訓(xùn)練32000 次時(shí)收斂， 而本文方法僅需15000 次訓(xùn)練達(dá)到收斂狀態(tài)，可見收斂速度有很大的提升。 訓(xùn)練完成的最優(yōu)策略如圖2 所示， 從起點(diǎn)到終點(diǎn)的最優(yōu)路徑如圖4所示。

圖4 從起點(diǎn)到終點(diǎn)最優(yōu)路徑Fig.4 Optimal path from start to end

采用同樣的方法，生成另外3 個(gè)障礙物分布不同的柵格地圖，使用同樣參數(shù)完成訓(xùn)練。 統(tǒng)計(jì)移動(dòng)機(jī)器人在地圖所有狀態(tài)下到達(dá)目標(biāo)狀態(tài)的平均步數(shù)，見表1。

表1 兩種方法平均步數(shù)的對(duì)比Tab.1 Comparison of average steps between the two methods

移動(dòng)機(jī)器人在所有狀態(tài)移動(dòng)到終點(diǎn)的平均步數(shù)越少，說明策略越優(yōu)。 由表可知，本文方法在5 次試驗(yàn)中，平均次數(shù)均明顯低于經(jīng)典Q-learning 方法。

5 結(jié)語(yǔ)

所提出的結(jié)合神經(jīng)網(wǎng)絡(luò)和Q（λ）-learning 算法的移動(dòng)機(jī)器人路徑規(guī)劃算法，通過優(yōu)化設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，為增強(qiáng)學(xué)習(xí)提供了先驗(yàn)知識(shí)，解決了強(qiáng)化學(xué)習(xí)中存在的收斂速度慢和解的局部最優(yōu)問題。通過仿真試驗(yàn)，本文方法與經(jīng)典學(xué)習(xí)方法相比較，驗(yàn)證了該方法的有效性。