孫上杰 姜樹海 崔嵩鶴 康玥 陳語唐

摘 要：針對強化學(xué)習(xí)算法收斂速度慢，易產(chǎn)生“維度災(zāi)難”的問題提出一種深度學(xué)習(xí)與強化學(xué)習(xí)相結(jié)合的算法，用于解決六足森林消防機器人的路徑規(guī)劃問題。采用Python方法建立二維網(wǎng)格地圖，對復(fù)雜的環(huán)境進(jìn)行模擬，減小建模的復(fù)雜性，在相同的條件下，分別對強化學(xué)習(xí)和深度強化學(xué)習(xí)算法進(jìn)行仿真研究。對比仿真結(jié)果表明，深度強化學(xué)習(xí)算法下機器人到達(dá)目標(biāo)點所需步長隨迭代次數(shù)而減少，能使學(xué)習(xí)效率得到顯著的提高，可以說明算法的收斂速度更快。

關(guān)鍵詞：森林消防;機器人;深度學(xué)習(xí);路徑規(guī)劃

Abstract：In order to solve the problem of slow convergence and dimension disaster of reinforcement learning algorithm， an algorithm combining deep learning and reinforcement learning is proposed to solve the path planning problem of six legged forest fire fighting robot. Python method is used to build a two-dimensional grid map to simulate the complex environment and reduce the complexity of modeling. Under the same conditions， the reinforcement learning algorithm and the deep reinforcement learning algorithm are simulated respectively. The simulation results show that the step length required by the robot to reach the target point under the deep reinforcement learning algorithm decreases with the number of iterations， which can significantly improve the learning efficiency and show that the convergence speed of the algorithm is faster.

Keywords：Forest fire fighting; robot; deep learning; path planning

0 引言

路徑規(guī)劃[1-3]是在已知或者未知環(huán)境下，為移動機器人提供全程無碰撞的最優(yōu)路徑，它是移動機器人定位與導(dǎo)航技術(shù)中的重要方法 。 路徑規(guī)劃方法[4]主要包括兩個大的類別，一個是基于模型的全局路徑規(guī)劃，這類路徑規(guī)劃問題是已知移動機器人所在環(huán)境的信息，通過已知的環(huán)境信息進(jìn)行路徑規(guī)劃;另一個是基于傳感器的局部路徑規(guī)劃，即移動機器人所處的環(huán)境信息部分或全部是未知的，這里所說的環(huán)境是一個動態(tài)環(huán)境。不管是哪一類路徑規(guī)劃，算法主要包括傳統(tǒng)算法、啟發(fā)式算法[5]、智能仿生學(xué)算法[6]和強化學(xué)習(xí)算法[1]，以及上述算法的改進(jìn)與融合[7-10]。

強化學(xué)習(xí)算法[1]區(qū)別于其他算法，是一種不需要先驗知識的人工智能算法，與環(huán)境直接進(jìn)行試錯迭代，獲取獎勵值來優(yōu)化策略，非常適合于森林消防機器人路徑規(guī)劃的研究。根據(jù)求解方法不同，強化學(xué)習(xí)算法可以分為值函數(shù)法和直接策略搜索法。值函數(shù)法包含與模型無關(guān)的強化學(xué)習(xí)算法和基于模型的強化學(xué)習(xí)算法。與模型無關(guān)的強化學(xué)習(xí)算法無需構(gòu)建環(huán)境模型就可應(yīng)用于復(fù)雜環(huán)境下的機器人路徑規(guī)劃，更符合森林消防機器人路徑規(guī)劃的要求。

Q-learning學(xué)習(xí)算法是Watkins等[11]在1989年提出的與模型無關(guān)的強化學(xué)習(xí)算法，這個算法不需要知道模型就可以保證收斂。Q-learning算法是通過構(gòu)建Q值表來選擇最優(yōu)策略[12-13]，應(yīng)用于路徑規(guī)劃時，離散精度難以控制，如果精度過低，易造成信息丟失;如果精度過細(xì)、維數(shù)很大時，會導(dǎo)致維數(shù)災(zāi)難[14]。因此，該方法不能完全適用于解決本文課題組開發(fā)的六足仿生森林消防機器人的路徑規(guī)劃問題。

深度學(xué)習(xí)是最近幾年流行的機器人人工智能學(xué)習(xí)算法，它能夠有效地處理高維數(shù)據(jù)。這里將Q-learning算法與深度學(xué)習(xí)算法結(jié)合，解決六足仿生森林消防機器人的路徑規(guī)劃問題。針對強化學(xué)習(xí)算法收斂速度慢、易產(chǎn)生“維度災(zāi)難”的問題，本文提出一種深度學(xué)習(xí)與強化學(xué)習(xí)相結(jié)合的算法，用于解決六足森林消防機器人的路徑規(guī)劃問題。采用Python編程方法建立二維網(wǎng)格地圖，對復(fù)雜的環(huán)境進(jìn)行模擬，減小建模的復(fù)雜性。

1 環(huán)境建模

采用柵格法建模，建立二維柵格圖。柵格圖簡單有效，可以對復(fù)雜的環(huán)境進(jìn)行模擬，減少了建模的復(fù)雜性，數(shù)據(jù)容易在系統(tǒng)內(nèi)表示、儲存和處理，對于障礙物，森林消防機器人對其位置的判斷也更加方便，所以這個環(huán)境建模的方法在路徑規(guī)劃等方面可以大規(guī)模應(yīng)用[15-16]。通過建立一個10×10或5×5的二維柵格圖對環(huán)境進(jìn)行模擬，如圖1所示。定義機器人為綠色方塊，障礙物為紅色方塊，終點為藍(lán)色方塊，安全區(qū)域是灰色方塊，障礙物可以隨機定義位置，定義機器人向左運動記為0，向上為1，向右為2，向下為3，如圖2所示。

機器人是一個學(xué)習(xí)者或決策者，環(huán)境是機器人與之交互并包含機器人之外的一切。在仿真軟件中，機器人可以是Q學(xué)習(xí)機器人或深度Q學(xué)習(xí)機器人。為了比較強化學(xué)習(xí)算法，在相同的環(huán)境中設(shè)置這兩種算法。在網(wǎng)格圖中，有一個a×b的矩陣c，a是行數(shù)，b是列數(shù)。為了將圖形映射轉(zhuǎn)換為矩陣，矩陣的每個狀態(tài)將表示為浮點數(shù)。以下顯示了矩陣的不同狀態(tài)。

（1）障礙物：在此處設(shè)置障礙物，使機器人必須避開此單元。

（2）訪問：機器人已經(jīng)在一單元中。

（3）占用：學(xué)習(xí)機器人正在使用的當(dāng)前單元。

（4）目標(biāo)：機器人必須確定從起始單元格到目標(biāo)單元格的路徑。

（5）空：機器人移動到此單元是有效的。

訪問的單元格僅用于計算獎勵函數(shù)，因此不會顯示在用戶界面上。消防機器人只能夠被允許在空單元格上行動，必須避免移出網(wǎng)格圖，目的是到達(dá)目標(biāo)。在強化學(xué)習(xí)中，機器人的目的是根據(jù)從環(huán)境傳遞給機器人的特殊獎勵信號進(jìn)行形式化。對于每一個時間步驟，獎勵都是一個數(shù)字，機器人必須將收到的獎勵總量最大化。它不僅可以最大化即時獎勵，而且還可以累積獎勵。因此去建立強化學(xué)習(xí)的獎勵功能，定義以下規(guī)則：

（1）獎勵在這里可以是一個大的范圍，它既包括獎勵，也包括懲罰，在這里定義獎勵為正，懲罰為負(fù)。

（2）獎勵范圍從-1.0到1.0。

（3）從一個單元到另一個單元的每一次移動都需要-0.05分。這將保證機器人在順利到達(dá)指定目標(biāo)的前提下，盡可能減少移動次數(shù)，從而找到最短的目標(biāo)路徑。

（4）為了避免撞到障礙物，如果機器人移動到障礙物單元，將給予-0.75分的處罰。這是一個嚴(yán)格的懲罰，所以希望機器人能夠?qū)W會完全避免這種懲罰。

（5）如果機器人以-0.75分離開網(wǎng)格地圖邊界，將采用上述規(guī)則。

（6）機器人會因為對自己訪問過的單元中的任何操作受到-0.25分的懲罰。這里將使用前面提到的“訪問的單元格”一詞來確定哪些單元格已經(jīng)訪問過或沒有訪問過。這意味著不應(yīng)考慮被訪問的單元。

（7）為了避免在有限的循環(huán)中，最低的總獎勵將會設(shè)置為-0.5×環(huán)境大小。

圖3是一個動作和獎勵功能的示例。由圖3可以看出，每個合法行動的獎勵是-0.05分，例如從步驟1到步驟2、從步驟2到步驟3或從步驟4到步驟5。當(dāng)機器人移動到一個被訪問過的單元時，將得到-0.25分的懲罰。對于最后的行動，機器人就會到達(dá)目的地，所以獎勵是1。

2 Q-learning算法

Q-learning算法首先建立一張Q值表，設(shè)狀態(tài)-動作對的評價值為Q（s，a）。所以函數(shù)Q（s，a）的值是從狀態(tài) s 執(zhí)行動作 a 后的立即回報加上之后遵照最優(yōu)策略的回報值，即當(dāng)前狀態(tài)下機器人選擇策略的優(yōu)劣程度。

式中： St為t時刻機器人的狀態(tài); at為在狀態(tài)St下的動作;rt為獎勵值，是對狀態(tài)St+1的評估，表示機器人由此狀態(tài)執(zhí)行到下一個狀態(tài)所獲得的獎勵值。γ∈（0，1）稱作為折算因子，r為由狀態(tài)S執(zhí)行動作 a 后所得到的獎勵值。通過不斷迭代修改Q值表，使選擇正獎賞動作的概率不斷增加，隨著機器人不斷與環(huán)境交互，更改動作策略集，將機器人的動作最后變化為最佳策略動作集。

一個最典型 Q-learning 算法[17]可以用以下步驟來進(jìn)行。

Step 1 ：首先對所有的狀態(tài)-行為對的 Q 值進(jìn)行初始化處理，給定最終的初始狀態(tài) S。

Step 2 ：根據(jù)機器人行為的選擇策略規(guī)則給定行為a。

Step 3 ：實行行為a，狀態(tài)改變到St+1，并獲得相應(yīng)的報酬。

Step 4 ：根據(jù)相應(yīng)的公式進(jìn)行Q的更新。

Step 5 ： S→St+1。

Step 6 ：如果 S∈St，結(jié)束算法;如果不屬于St+1，轉(zhuǎn)至 Step 2 。

圖4是對于確定性馬爾可夫決策過程的 Q-learning 算法[18]與環(huán)境交互模型的描述。

Q-learning算法在復(fù)雜障礙物密集的環(huán)境下需要構(gòu)建龐大的Q值表，然后根據(jù)回報值循環(huán)更新Q值表的對應(yīng)值，該方法極其耗時，因此Q-learning算法很難應(yīng)用到大狀態(tài)空間下的移動機器人路徑規(guī)劃。

3 深度Q網(wǎng)絡(luò)

深度Q網(wǎng)絡(luò)[19]是Q-learning算法和深度學(xué)習(xí)算法互相結(jié)合最終產(chǎn)生的結(jié)果。深度Q學(xué)習(xí)網(wǎng)絡(luò)是用一個神經(jīng)網(wǎng)絡(luò)來保存內(nèi)容。

機器人與環(huán)境交互的每一步，機器人都有自己的狀態(tài)，機器人會選擇一個措施。在選擇最佳措施后，就會進(jìn)行下一步，機器人將獲得一個獎勵值。之后的神經(jīng)網(wǎng)絡(luò)會根據(jù)狀態(tài)和獎勵值來讓機器人了解周圍的環(huán)境。一開始，機器人不知道環(huán)境會轉(zhuǎn)移到哪種狀態(tài)和獎勵是什么。在機器人學(xué)習(xí)期間，機器人會觀察這些數(shù)值并且進(jìn)行不斷改進(jìn)神經(jīng)網(wǎng)絡(luò)的輸出是在0到1范圍內(nèi)作用的概率分布。較高的行動概率可能會為機器人提供更好的累積獎勵，如圖5所示。

在左側(cè)，二維網(wǎng)格圖包括起點、終點和障礙物。對于機器人來說，理解這個地圖太過于復(fù)雜，為此利用環(huán)境建模中的方法將他轉(zhuǎn)化為矩陣。深度Q網(wǎng)絡(luò)也像其他傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)一樣，都需要一個包含多個節(jié)點的輸入層。矩陣是二維的數(shù)組，但要將他轉(zhuǎn)化為一維數(shù)組，之后隱藏層提取輸入空間特征，輸出層將其轉(zhuǎn)化為概率分布。可以對Tensor Flow（最廣泛使用實現(xiàn)機器學(xué)習(xí)的算法庫）庫充分地利用，從而構(gòu)建一個數(shù)值計算圖來執(zhí)行這些任務(wù)。圖6中的代碼展示了如何用高級api-keras（一種易于使用的神經(jīng)網(wǎng)絡(luò)庫）構(gòu)建Tensor Flow神經(jīng)網(wǎng)絡(luò)。該神經(jīng)網(wǎng)絡(luò)不但可以經(jīng)過激活層利用激活函數(shù)，也可以作為實現(xiàn)的代碼通過激活參數(shù)使用激活函數(shù)。編譯模型需要使用損失函數(shù)。Keras支持好幾種十分常見的損失函數(shù)。為了使損失函數(shù)最小化，Keras模型還需要一個優(yōu)化器。經(jīng)過幾次實驗，選擇了tanh（雙曲正切函數(shù)）作為激活函數(shù)，mse（均方誤差）作為損失函數(shù)，adam（可以替代傳統(tǒng)隨機梯度下降過程的一階優(yōu)化算法）作為優(yōu)化算法。

4 仿真結(jié)果

圖7和圖8分別為Q學(xué)習(xí)和結(jié)合算法的回報值和到達(dá)目標(biāo)點所需步長隨迭代次數(shù)變化圖，由圖7可以看出步長在迭代1 700次左右才開始收斂，而且迭代兩千次后的回報值還是負(fù)數(shù)，說明算法沒有很好的學(xué)習(xí)。圖9為機器人在迭代2 000次過程中所得到的最短路徑軌跡。該軌跡也是機器人從初始點到目標(biāo)點的最短距離。說明通過機器人與它所處的環(huán)境之間的不斷交互，機器人在強化學(xué)習(xí)的幫助下能夠在簡單環(huán)境中進(jìn)行良好的路徑規(guī)劃。

結(jié)合后的深度Q學(xué)習(xí)算法的回報值和到達(dá)目標(biāo)點所需步長隨迭代次數(shù)變化圖（圖8），可以看出步長在迭代200多次后就開始收斂，回報值迭代1 000次后也為正數(shù)，這說明該算法的收斂速度明顯快于Q-learning算法，在復(fù)雜的環(huán)境下也可以進(jìn)行良好的路徑規(guī)劃。其對應(yīng)的最短路徑為圖10。

5 結(jié)束語

由于強化學(xué)習(xí)在復(fù)雜環(huán)境下的收斂速度比較慢，產(chǎn)生“維數(shù)災(zāi)難”，針對這個問題本文提出一種深度學(xué)習(xí)與強化學(xué)習(xí)相結(jié)合的算法，該算法用于解決六足森林消防機器人的路徑規(guī)劃問題。采用Python方法建立二維網(wǎng)格地圖，在相同的條件下，對強化學(xué)習(xí)和深度強化學(xué)習(xí)算法進(jìn)行仿真研究，仿真結(jié)果表明，深度強化學(xué)習(xí)算法的學(xué)習(xí)效率得到顯著提高，算法的收斂速度更快。后期將在森林復(fù)雜的地形環(huán)境下開展森林消防機器人路徑規(guī)劃的實地試驗研究。

【參 考 文 獻(xiàn)】

[1]董瑤， 葛瑩瑩， 郭鴻湧， 等. 基于深度強化學(xué)習(xí)的移動機器人路徑規(guī)劃[J]. 計算機工程與應(yīng)用， 2019， 55（13）： 15-19.

DONG Y， GE Y Y， GUO H Y， et al. Path planning for mobile robot based on deep reinforcement learning[J]. Computer Engineering and Applications， 2019， 55（13）： 15-19.

[2]唐文秀， 劉萍洋， 趙偲宇， 等. 基于立體視覺測量的移動機器人導(dǎo)航技術(shù)研究[J]. 森林工程， 2013， 29（6）： 102-105.

TANG W X， LIU P Y， ZHAO S Y， et al. Research on mobile robot navigation technology based on stereo vision measurement[J]. Forest Engineering， 2013， 29（6）： 102-105.

[3]丁柏群， 姜瑾. 基于蟻群算法和動態(tài)路阻的物流配送路徑優(yōu)化[J]. 森林工程， 2014， 30（2）： 149-152.

DING B Q， JIANG J. Path optimization of logistics distribution vehicle based on ant colony algorithm and dynamic road impedance[J]. Forest Engineering， 2014， 30（2）： 149-152.

[4]王志中. 復(fù)雜動態(tài)環(huán)境下自主機器人路徑規(guī)劃研究[J]. 組合機床與自動化加工技術(shù)， 2018，60（1）： 64-68.

WANG Z Z. Automatic robot path planning under complicit dynamic environment[J]. Modular Machine Tool & Automatic Manufacturing Technique， 2018， 60（1）： 64-68.

[5]張本群. 基于啟發(fā)式算法的路徑規(guī)劃[J]. 計算機仿真， 2012， 29（10）： 341-343.

ZHANG B Q. Path planning based on heuristic algorithm[J]. Computer Simulation， 2012， 29（10）： 341-343.

[6]于振中，李強，樊啟高.智能仿生算法在移動機器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述[J].計算機應(yīng)用研究，，2019，36（11）：3210-3219.

YU Z Z， LI Q， FAN Q G. Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots[J]. Application Research of Computers， 2019， 36（11）： 3210-3219.

[7]程傳奇， 郝向陽， 李建勝， 等. 融合改進(jìn)A～*算法和動態(tài)窗口法的全局動態(tài)路徑規(guī)劃[J]. 西安交通大學(xué)學(xué)報， 2017， 51（11）： 137-143.

CHENG C Q， HAO X Y， LI J S， et al. Global dynamic path planning based on Fusion of improved A～* algorithm and dynamic window approach[J]. Journal of Xian Jiaotong University， 2017， 51（11）： 137-143.

[8]韓亞輝， 王琢， 劉佳鑫， 等. 森林防火機器人的研究現(xiàn)狀與發(fā)展趨勢[J]. 林業(yè)機械與木工設(shè)備， 2020， 48（3）： 4-9.

HAN Y H， WANG Z， LIU J X， et al. Research status and development trend of forest fire protection robots[J]. Forestry Machinery & Woodworking Equipment， 2020， 48（3）： 4-9.

[9]王艷新， 唐文秀， 吳函， 等. 基于多傳感器融合技術(shù)的智能搶險救災(zāi)機器人設(shè)計[J]. 林業(yè)機械與木工設(shè)備， 2018， 46（5）： 17-20.

WANG Y X， TANG W X， WU H， et al. Design of intelligent emergency rescue robots based on multi-sensor fusion technology[J]. Forestry Machinery & Woodworking Equipment， 2018， 46（5）： 17-20.

[10]胡小平， 李澤玉. 一種改進(jìn)的勢場法路徑規(guī)劃算法[J]. 機械科學(xué)與技術(shù)， 2017， 36（10）： 1521-1529.

HU X P， LI Z Y. An improved potential field method for robot path planning[J]. Mechanical Science and Technology for Aerospace Engineering， 2017， 36（10）： 1521-1529.

[11]WATKINS C J C H， DAYAN P. Q-learning[J]. Machine Learning， 1992， 8（3/4）： 279-292.

[12]童亮， 王準(zhǔn). 強化學(xué)習(xí)在機器人路徑規(guī)劃中的應(yīng)用研究[J]. 計算機仿真， 2013， 30（12）： 351-355.

TONG L， WANG Z. Research on application of reinforcement learning in robot path-planning[J]. Computer Simulation， 2013， 30（12）： 351-355.

[13]劉志榮， 姜樹海， 袁雯雯， 等. 基于深度Q學(xué)習(xí)的移動機器人路徑規(guī)劃[J]. 測控技術(shù)， 2019， 38（7）： 24-28.

LIU Z R， JIANG S H， YUAN W W， et al. Robot path planning based on deep Q-learning[J]. Measurement & Control Technology， 2019， 38（7）： 24-28.

[14]劉志榮， 姜樹海. 基于強化學(xué)習(xí)的移動機器人路徑規(guī)劃研究綜述[J]. 制造業(yè)自動化， 2019， 41（3）： 90-92.

LIU Z R， JIANG S H. Review of mobile robot path planning based on reinforcement learning[J]. Manufacturing Automation， 2019， 41（3）： 90-92.

[15]劉曉磊， 蔣林， 金祖飛， 等. 非結(jié)構(gòu)化環(huán)境中基于柵格法環(huán)境建模的移動機器人路徑規(guī)劃[J]. 機床與液壓， 2016， 44（17）： 1-7.

LIU X L， JIANG L， JIN Z F， et al. Mobile robot path planning based on environment modeling of grid method in unstructured environment[J]. Machine Tool & Hydraulics， 2016， 44（17）： 1-7.

[16]于紅斌，李孝安.基于柵格法的機器人快速路徑規(guī)劃[J].微電子學(xué)與計算機，2005，22（6）：98-100.

YU H B， LI X A. Fast path planning based on gird model of robot[J]. Microelectronics & Computer， 2005， 22（6）： 98-100.

[17]高樂， 馬天錄， 劉凱， 等. 改進(jìn)Q-Learning算法在路徑規(guī)劃中的應(yīng)用[J]. 吉林大學(xué)學(xué)報（信息科學(xué)版）， 2018， 36（4）： 439-443.

GAO L， MA T L， LIU K， et al. Application of improved Q-learning algorithm in path planning[J]. Journal of Jilin University （Information Science Edition）， 2018， 36（4）： 439-443.

[18]白塵.馬爾可夫決策問題的關(guān)鍵狀態(tài)優(yōu)先學(xué)習(xí)算法[J].中國管理信息化，2016，11（9）：198-202.

BAI C. Markov decision process MDP critical states prioritized learning[J]. China Management Informatization， 2016， 11（9）：198-202.

[19]張浩杰， 蘇治寶， 蘇波. 基于深度Q網(wǎng)絡(luò)學(xué)習(xí)的機器人端到端控制方法[J]. 儀器儀表學(xué)報， 2018， 39（10）： 36-43.

ZHANG H J， SU Z B， SU B. End to end control method for mobile robots based on deep Q network[J]. Chinese Journal of Scientific Instrument， 2018， 39（10）： 36-43.