基于深度Q網絡和人工勢場的移動機器人路徑規劃研究

王冰晨，連曉峰，顏 湘，白天昕，董兆陽

(北京工商大學 人工智能學院，北京 100048)

0 引言

伴隨人工智能技術的興起，移動機器人正在朝著自探索、自學習、自適應的方向發展[1]。行成路徑的策略被稱為路徑規劃。作為自主移動機器人運動規劃的主要探究內容之一, 路徑規劃的目的是通過環境感知與主動避障功能尋找一個合理的最優路線,該道路由起點到目標點在既定的目標距離內不和其他障礙物交叉,并且要調整機器人移動方向,使之盡量滿足更短、更平緩的條件。依照自主移動機器人在它運行環境內信息的剖析水平,路徑規劃可分兩種類別, 即局部路徑規劃和全局路徑規劃。路徑規劃效果的優劣會立刻裁奪自主移動機器人完成任務的時效性和質量好壞，而機器人路徑規劃的核心內容是算法的設計[2]。常用的移動機器人路徑規劃算法有人工勢場法[3]、粒子群優化算法[4]、模糊邏輯算法[5]、遺傳算法[6]等。而這類常用的方式多數需依據環境建模，往往需求預先構造出地圖相關信息，然后對環境路徑做好控制規劃。一旦建立出了不準確模型，必將惡化過程與結果的實時性和準確性，乃至將會影響移動機器人及其周邊環境的安全性。按照訓練方法的不同，路徑規劃可分成監督學習、無監督學習和強化學習幾類方式,在實施路徑規劃時監督學習需要提前建立出環境信息，需要提供大量的先驗知識，不然將不能完成滿足需求的路徑規劃。無監督學習同監督學習一樣。與此相反，強化學習不必提前了解環境信息，換句話說即無須先驗知識，所以這種學習方式被普遍地使用于智能移動機器人路徑規劃中。強化學習的智能體將會和環境持續不斷試錯和交互，并經由累積獎勵于改良策略，這是類于周圍狀況映照至行為的學習方法[7]，它把學習當成是一個“試探-評價”的進程。Q學習(Q-learning)是強化學習中的一種常用的基礎模型，并且不需要了解具體模型就能夠確保最終收斂，它也為當前運用到智能自主移動機器人路徑規劃的特別見效的模型之一，當于狀態空間相對小的情境下可以輕松地取得滿意的路徑規劃結果[8]，得到滿意的相關參數，該算法是經由搭建Q值表來挑選最佳策略的，當維度比較高的時候，這將引起維數災難[9]。

深度強化學習(DRL，deep reinforcement learning)算法將強化學習的決策能力與深度學習強大的感知能力融合到一起，在應對不同情境的工作中表現優秀，這非常利于移動機器人的自主路徑規劃或導航避障。深度Q網絡(DQN，deep q-learning network)是眾多深度強化學習算法中的非常典型的常用算法，它是一個貼近人們思考邏輯的人工智能算法，核心就是把Q-table的更新轉化為函數問題，通過擬合一個function來代替Q-table產生Q值。Mnih等人[10]提出了DQN技術，并將它使用到Atari2600中，在游戲內達到人類玩家甚至超越人類玩家的水準。Schaul等人[11]提出訓練DQN模型的方法為根據優先級的經驗回放方式取代原本的同概率選擇方式，優先回放的核心思路是給經驗池里的經驗分別規定優先級，之后在選擇經驗時會偏向于挑選優先級很高的經驗。Xin等人[12]在進行移動機器人路徑規劃時，第一次使用到了DQN算法。

為解決DQN算法在路徑規劃上存在的收斂速度慢，訓練前期產生巨大迭代空間的問題，本文在現有的路徑規劃算法和深度Q網絡基礎上，提出一種基于深度強化學習和人工勢場法融合的路徑規劃算法。

1 人工勢場

人工勢場法(APF，artificial potential field)路徑規劃是由Khatib[13]提出的一種虛擬力算法，是局部路徑規劃里面頻繁被用到的算法，物理學里面的勢，也被稱為“位”，為一種能量的概念。把經典力學里的“場”的思想加到此算法里面，假設使移動機器人于此類虛擬力場里實施運動動作。究竟怎么規劃勢場會影響此方法的實用性和性能。它的核心概念為把自主移動機器人在周圍現實情境中的運動設想成一個在寬泛的人工力場中的運動，利用目標物對自主移動機器人形成“引力”影響，障礙物對自主移動機器人形成“斥力”影響，最終再利用求出的合力來限制自主移動機器人的運動，如圖1所示，是人工勢場法中對環境下自主移動機器人的受力分析。而應用勢場法設計出來的運動路線，通常是是相對平滑而且安全的[14]。

圖1 人工勢場法中機器人的受力分析

最常見的引力場函數(Attractive Field)如公式(1)所示：

(1)

其中:ζ為引力增益,d(q,qgoal)是當前點q與目標點qgoal之間的歐幾里得距離。引力場有了，那么引力就是引力勢場對距離的負導數：

Fatt(q)=-▽Uatt(q)=ζ(qgoal-q)

(2)

最常見的斥力場函數(Repulsive Potential)如公式(3)所示：

(3)

其中:η是斥力增益，D(q)是目前點q與相離最近的障礙物點之間的歐幾里得距離，Q*是障礙物出現斥力影響的距離閾值，大于此閾值距離的障礙物不會產生排斥力作用來影響移動機器人。同理，斥力為：

Frep(q)=-▽Urep(q)=

(4)

將斥力場與引力場疊加，就形成了人工勢力場：

U(q)=Uatt(q)+Urep(q)

(5)

F(q)=-▽U(q)

(6)

在排斥力勢場和引力勢場合力的驅動下，將移動機器人由高勢能位置移動到低勢能位置，同時找到一條能夠到達目標點位置的無碰撞路徑。地圖上目標位置的引力(即重力)涵蓋了整個環境地圖，2D空間的引力場示意圖如圖2所示，因此自主移動機器人可以從地圖上的任何位置向目標點位置進行移動。

圖2 2D空間引力場

人工勢場法如同搭建了類似吸鐵石的場景，里面容納了引力場與斥力場。深色物體產生斥力，是障礙物，箭標指向是移動機器人接下來運行的方向。智能移動機器人依據箭標的指向抵至目標物，目標物有類似于“引力”似的招至移動機器人與它的距離減小。但于障礙物周圍，移動機器人反著箭標的方向，類似于對機器人形成“斥力”。移動機器人移動的方向即斥力和引力的合力的指向。

人工勢場法也存在諸多問題，比如在移動機器人距離目標位置相對遠的時候，引力會變的非常大，且比較小的斥力在乃至能夠被無視的情境下，移動機器人在路徑上大概率將碰到障礙物；在目標點位置旁邊有障礙物時侯，斥力會變得特別大，而引力特別小，移動機器人抵達目標點位置將會變得很麻煩；當環境中的一點，引力和斥力正好完全相等，方向相反，那么移動機器人將很輕易地深陷震蕩或局部最優解。

對于上述存在的問題來說，接觸到障礙物的問題，能夠經由修改引力函數來處理，阻止遇到距離目標點位置過于遠從而出現引力太大的情況；目標點位置旁邊有障礙物從而引起目標不可達的問題，能夠經由引進其它斥力函數來處理，此函數增添目標點和移動機器人距離的作用，一定程度而言，當移動機器人在目標點附近時，即使斥力作用變大，但與此同時距離在變小，所以此函數的增添能夠產生對斥力場的拖拽影響；陷入局部最優解和震蕩是人工勢場法的一大難題，能夠經由增添一個隨機擾動，從而使得移動機器人脫離局部最優的情況。

2 深度強化學習

深度學習和強化學習的聯結是人工智能領域的一個必然發展的趨勢。深度強化學習可以經由端對端的學習方式完成從原始輸入到輸出的直接控制，即能夠運用到強化學習的試錯算法和積累獎勵函數來加速神經網絡設計，又能夠使用到深度學習的高維數據處理本領與快捷特征提取本領來成功搞定強化學習中的值函數逼近問題，可以進行“從零開始”“無師自通”的學習方式。

2.1 卷積神經網絡

人工神經網絡(ANN，artificial neural networks)是一種模擬生物神經系統的結構和行為，從信息處理的視角對生物神經元網絡實行抽象，搭建一種容易模型，依據不一樣的連接方式構建不一樣的網絡，進行分布式并行信息處理的算法模型。人工神經網絡借助改變結構中神經元與神經元之間的權重關聯，進而完成處理相關信息的目標。卷積神經網絡(CNN，convolutional neural network)是一種前饋型神經網絡，是由一些卷積層和池化層構成的，對于圖像處理技術方面卷積神經網絡的運用特別廣泛，并且表現結果格外優秀。

卷積神經網絡主要由：輸入層、卷積層、ReLU層、池化(Pooling)層和全連接層(全連接層和常規神經網絡中的一樣)構成。把幾個類型層相互疊加到一起，能夠搭建成為一個完整的卷積神經網絡。在現實情況的使用過程里，經常把卷積層與ReLU層一起叫作卷積層，因此卷積層在通過卷積步驟之后還需要通過激活函數。如圖3是一種卷積神經網絡結構。

圖3 一種卷積神經網絡結構圖

將卷積神經網絡與典型人工神經網絡相比，成功處理的一類問題是“將復雜問題簡化”，將諸多參數降低維度到些許參數，之后再進一步處理。最主要的原因為：在絕大多數情況下，降低維度的處理并不改變最終結果。舉例像2 000像素的圖片被降維至400像素，此行為最終不改變人眼看出來圖片中原來的小動物具體是什么種類，機器也和人眼一樣。成功處理的另一類問題是“保留視覺特征”，從視覺的角度來看，在圖片的具體內容(本質)不發生改變，不過圖片位置發生了改變的情況。在我們改變圖像中物體的位置時，用經典人工神經網絡的方法處理得到的參數將與之相差特別多,此現象極度與圖像處理的要求相矛盾。但卷積神經網絡成功處理了此問題，它應用幾乎相同于視覺的方法維持了圖像的特征，當圖像做翻轉、旋轉或者變換位置得動作時，它仍然可以快速地識別得出這也是類似的圖像。

伴隨著深度學習相關技術的研究與發展，卷積神經網絡在各種圖像數據集上的準確率越來越高，其結構也向著更深的方向發展，這得益于大數據技術和GPU的出現。這些進步使得卷積神經網絡在計算機視覺領域獲得了廣泛的應用，從簡單的圖像分類，到精確到每一像素的圖像分割，卷積神經網絡都有著特別出色的表現。

2.2 馬爾可夫決策過程

強化學習可以看作狀態、動作和獎勵三者的時間序列，其中狀態又可以分為三種：環境狀態，智能體狀態和信息狀態。信息狀態包含歷史的所有有用信息，一般指馬爾可夫。馬爾可夫狀態中，當前狀態只與前一個狀態有關，一旦當前狀態已知，就會舍棄歷史信息，只需要保留當前狀態。

經過前人數多年的持續探索和研究，最終一種能夠成功處理多數強化學習問題的框架被發明揭示，此框架即馬爾可夫決策過程(MDP，markov decision processes)。接下來本文將相對詳細地介紹馬爾可夫決策過程：首先介紹馬爾可夫性，接著介紹馬爾可夫過程，最后介紹馬爾可夫決策過程。

馬爾可夫性指下一個狀態只與當前狀態有關，且與先前的狀態無關。馬爾可夫性定義為：狀態st是馬爾可夫性的，當且僅當:

P[st+1|st]=P[st+1|s1,…,st]

(7)

從上面的定義可以看出，某個狀態是馬爾可夫的，即該狀態從歷史中捕獲了所有信息。因此，一旦得到了該狀態，就可以舍棄歷史信息了。換句話說，當前狀態是未來的充分統計量。在強化學習過程中，狀態s包含了足夠多的歷史信息，來描述未來所有的回報。

馬爾可夫過程的定義：隨機變量序列中的每個狀態都是馬爾可夫的，是一個二元組(S，P)，S為有限狀態集，P是狀態轉移概率。

對于馬爾可夫狀態s和他的后繼狀態s′，定義狀態轉移概率為：

Pss′=[st+1=s′|st=s]

(8)

狀態轉移矩陣P定義了所有由狀態s到后繼狀態s′的轉移概率，即:

(9)

馬爾可夫決策過程由五元組組成。其中S為有限的狀態集，A為有限的動作集，P為狀態轉移概率，R為回報函數，γ為折扣因子，用于計算累積回報。

強化學習的目標是，給定一個MDP，尋找最優策略。這里的策略指從狀態到行為的映射：

π(a|s)=P[At=a|St=s]

(10)

該式含義為：策略π在任何狀態s下指定一個動作概率，假設這是一個確定的動作，那么這個策略為確定性策略。事實上，強化學習的策略通常是隨機策略，移動機器人通過不斷測驗其他動作從而找到更優秀的策略，為此引入概率因素。既然策略是隨機的策略，那么狀態變化序列也可能不同，因此累計回報也是隨機的。

2.3 Q-learning

在強化學習中，大部分情況下都會采用時間差分(TD，temporal-difference)算法族。TD-Learning聯結了動態規劃和蒙特卡羅算法，是強化學習的核心思想。實際上，TD-Learning利用了馬爾可夫屬性，通過含蓄地構建MDP結構來利用它，然后從MDP結構來求解問題。

TD-Learning策略迭代包括策略評估和策略改善，若策略評估和改善的更新方式相同則為On-Policy，否則為Off-policy。Q-learning算法就是基于Off-policy的TD優化，其在更新下一策略時使用了max操作，為挑選最優動作，但是當前動作并不見得必能挑選到最優動作，所以這里策略評價的策略和策略改進的策略不同。

Q-learning是Watkins于1989年提出的一種無模型的強化學習方法[15]。它是一種value-based算法，即通過判斷每一步動作的價值來進行下一步的動作， Q-learning的核心是Q-Table，它可以評定所有可用行為的預期效用，并且不使用環境模型，即無需先驗知識。在同一時間，它也能夠處理并解決隨機過渡問題和獎勵問題，并且不必做任何調整。因為目前已經得到了證實，就是從目前狀態出發，每個連續步驟對于收益總回報能得到最大的期望值，針對隨機一個局限的MDP，調整Q-learning學習最終結果是會找到一個最優策略。在起初學習前，Q將被初始化成為一種不定的固定值。接下來在下一個時間t，智能體會進行一次動作選擇at，并獲得一個獎勵rt，得到一個全新的狀態St+1和Q值更新。值函數的迭代過程是該算法的重點，即：

Q(st,at)←Q(st,at)+

(11)

其中:α是學習率，γ為折扣因子。

Q-learning算法通過一個Q-tabel來記錄每個狀態下的動作值，在動作空間或狀態空間相對很大的時候，必要的存儲空間便會更大。如果狀態空間或動作空間連續，則該算法無法使用。所以，Q-learning算法只能用于解決離散并且低維度狀態空間和動作空間類問題。

表1為Q-learning算法的偽代碼。

表1 Q-learning：Off-policy TD Control算法

2.4 深度Q網絡

Mnih等人把卷積神經網絡和經典的Q-learning算法結合到一起，提出了DQN算法模型，該算法的提出開創了深度強化學習新的研究領域。DQN算法的核心概念是以一個人工神經網絡q(s,a:ω),s∈S,a∈A來代替Q-tabel，亦即動作價值函數，該算法將卷積神經網絡作以媒介，將參數是ω的f網絡約等取代為值函數，原理公式為：

f(s,a,ω)≈Q*(s,a)

(12)

其中:f(s,a,ω)能夠是任意類型函數，用函數取代，神經網絡的輸出能夠拿來表征Q值，且不管狀態空間的大小如何，s為輸入狀態。網絡的輸入為狀態信息，而輸出則是每個動作的價值，因此DQN算法不僅可以用來解決連續狀態空間而且可以解決離散動作空間問題。

DQN相較于傳統強化學習算法有兩大非常重要的改進：

1)引入深度學習中的神經網絡，并不直接使用預更新的目前Q網絡。使用的神經網絡為雙重網絡結構，便可以一起使用Q估計網絡和Q目標網絡來完成模型的訓練，并由此來降低目標值與當前值之間的關聯性。在學習經歷中，學習目標是應用目標網絡進行自益從而獲得回報的評估值。在更新的歷程中，無需更新目標網絡的權重，只需更新評估網絡的權重。另外目標網絡和估計網絡的構成是一摸一樣的。此方法極大地提高了網絡訓練的穩定性和收斂性。

卷積神經網絡的訓練是一種最優化問題，所謂的最優化就是最優化一個損失函數[16]，是標簽與卷積神經網絡之間輸出的偏差值，其目標是使得損失函數值最小。所以，首先必須有一定的訓練樣本，其中含有許多的帶標記數據，接著再經由以反向傳播[17]方式的梯度下降來改變并更新卷積神經網絡的參數。

此時使用Q-learning計算出來的正確Q值當做標記信息，為Q-Network提供需要的訓練樣本，不斷地優化權重矩陣。因此，Q-Network訓練的損失函數為：

L(ω)=

(13)

其中:Q(st,at,ω)是目前網絡輸出，用于評價與目前狀態動作相應的值函數，Q(st+1,at+1,ω-)是Q-target的輸出，用于獲得目標函數的Q值，ω-由參數ω延遲更新得到。

2)采用了經驗回放機制，要求在每次進行網絡更新時輸入的信息數據符合獨立同分布，從而打破數據間的關聯性。記憶回放的基本思路是在每一回學習進程中隨機地選擇出記憶庫中的部分樣本數據，然后對它實行梯度下降學習。智能體會隨機從經驗池中抽取定量的transition，以進行學習，既可以學習現在也可以學習過去的經驗，同時隨機的抽取也降低了樣本之間的相關性導致的過擬合。要想能夠把新的經驗單元與舊經驗單元任意地混雜并加以更換,進而打斷相鄰樣本數據之間的關聯性，需要利用到記憶矩陣中的經驗單元(s,a,r,s′)。同時其中多數經驗會被多次重復地利用或加以更新，對于數據取得相對麻煩的情境特別適用，以此提升樣本的利用率。

DQN的算法運行結構圖如圖4所示。

圖4 DQN 算法運行結構圖

智能體不斷與周圍環境交互，并獲取交互數據(s,a,r,s′)存入replay memory，當經驗池中有足夠多的數據之后，從經驗池中隨機抽取出一個batch_size大小的數據，然后使用當前網絡計算Q的預測值，再利用Q-Target網絡計算出Q目標值，進而計算兩者之間的損失函數，使用梯度下降來改變或更新當前網絡參數，重復若干次后，把當前網絡的參數復制給Q-Target網絡。

3 深度Q網絡和人工勢場融合算法

深度強化學習是深度學習與強化學習的整合體，實際來說是融合了強化學習和深度學習的各自優點,但它仍然偏重于強化學習，處理的關鍵依舊是有關決策的,僅僅依靠神經網絡強勁的表達本領來擬合Q表或徑直擬合策略用來處理狀態-動作空間問題[18]。

傳統的DQN算法訓練時間長，收斂速度慢。DQN在Q表的初始化進程中通常被設計為絕對隨機抽取，對環境并無先驗信息，此設計導致自主移動機器人在各個初始狀態對動作的挑選是完全任意的。通常使用ε-貪婪策略進行動作選擇。當自主移動機器人挑選出動作并進入到接下來的狀態時，它通常會按照目前狀態下動作的即時獎勵與接下來狀態的最大行為值函數來更新和調整目前狀態的行為價值函數。DQN算法是一種Off-policy算法。在最開始幾輪訓練規劃中，尤其是在規模相對大的未知的環境下，會輕松地出現巨大的無效迭代空間[19]，之后伴著路徑規劃訓練過程的慢慢增多，智能體對環境信息有了越來越多的了解，Q值將逐步趨向收斂狀態，進而路徑規劃回合的速率也會隨著逐步變快[20]。

為了克服DQN算法收斂速度慢且在計算初始階段容易陷入巨大的無效迭代空間問題，我們采用了DQN與人工勢場算法結合的方式初始化Q值，提供給算法先驗知識，鑒于地圖上障礙物散播相對比較聚集，以便增強算法的實時性能，刨除障礙物出現的斥力場對移動機器人的排斥力作用，本文只考慮目標點對自主移動機器人的引力作用。本文的引力勢場函數的引力如式(14)所示。

(14)

Q(s,a,ω)=r+γV(s′)

(15)

該算法的流程圖如圖5所示。

圖5 DQN改進算法流程圖

4 仿真實驗

4.1 實驗環境

為了驗證本文提出的人工勢場與DQN結合算法在路徑規劃中的收斂速度和較小迭代空間上的出眾性能，對本文提出的改進DQN方法與傳統DQN算法進行了效果對比。由于柵格法建模的廣泛性和實用性[21],實驗環境使用柵格法進行建模。本文模擬軟件使用的實驗環境如表2所示。

表2 實驗環境與配置

4.2 參數配置

機器人的動作A={向上，向下，向左，向右}。

獎勵函數將會對強化學習挑選動作的優劣給給出評價，在強化學習過程中具有積極的任務完成指引效果，用r表示。本文算法獎勵函數設置為：

(16)

仿真實驗的各個參數為如表3所示。

表3 實驗參數

4.3 實驗結果與分析

運動環境大小設置為16×16的柵格環境，其中每個柵格的尺寸為1×1像素。將柵格地圖環境左上角設置為坐標的原點，橫向方向設為x軸，縱向方向設為y軸，定義起點位置為(1，1)，目標點位置為(15，15)，黑色的柵格象征障礙區域，白色的柵格象征自由移動區域，仿真環境如圖6所示。將自主移動機器人近似作為一個點，忽略其體積對仿真實驗的影響。通過實驗仿真，在全局靜態環境下，利用改進DQN算法得到的從起點到終點路徑規劃和傳統DQN算法結果相同，如圖7所示。利用傳統的DQN算法與改進的DQN得到的迭代收斂對比如圖8和圖9所示。

圖6 仿真環境

圖7 最短路徑圖

圖8 DQN算法迭代變化曲線圖

圖9 APF+DQN改進算法迭代變化曲線圖

圖7中左上角點為任務起點，右下角點則為目標點，其軌跡是移動機器人從起點到目標點的正確且最優路徑。說明由于機器人與環境做出的不斷交互，本文提出的改進深度強化學習算法可以使得機器人在該環境中進行正確的路徑規劃。

以迭代步數(episode)為橫坐標，到達目標點所需步長(step)為縱坐標做出曲線圖，從而進行兩種算法的對比。當迭代步數的慢慢擴展增多，從起點至目標點的規劃步長數目也逐漸趨向變小，最后會收斂至最優步長。

通過迭代圖對比，可以得出改進的DQN算法得出的路徑規劃前期產生的迭代空間更小，收斂更早。傳統的DQN算法在前約220次迭代產生較大的迭代空間，需要迭代約300次才可以收斂。改進的DQN算法在前約90次迭代中產生了較小的迭代空間，需要約160次就達到了收斂。

傳統DQN算法在訓練初始階段由于缺乏樣本池，所以動作選擇的隨機性相對較大，且只有得到大批的樣本后便能訓練出正確的模型。通過結合了深度Q網絡算法與人工勢場法，使得在訓練初始階段能夠提供給模型適量的導向，進而減小了訓練過程的盲目性和隨機性，也因此進一步減少了訓練時間，可以較快地得到優化模型。表4概括地對比了兩種算法的性能，數據是對兩種算法分別運行了10次取得的數據平均數。

表4 兩種算法性能對比

上述仿真結果表明，本文所提出的算法能夠實現智能移動機器人行走過程中的全局路徑規劃，對環境的路徑規劃有著良好的表現。在收斂時間方面，改進算法相較于傳統算法減少了60.99%，同時在收斂前的迭代次數方面減少了45.47%。所以對于傳統DQN算法而言，本文所采用的融合人工勢場法的DQN算法效率更高，收斂速度更快，前期訓練產生的迭代空間更小。

5 結束語

改進DQN算法針對傳統DQN算法訓練時間長、收斂速度慢、訓練前期產生巨大迭代空間等問題，在原始DQN算法的基礎上引入基于人工勢場法的引力場來輔助初始化Q值進行改進，應用二維柵格環境進行試驗驗證。實驗結果表明，改進DQN算法減少了算法訓練時間，加快了收斂速度，減小了訓練前期產生的迭代空間，對解決實際問題有一定的應用價值。本文主要面對靜態環境下的全局路徑規劃研究，至于深度Q網絡算法在繁雜的動態環境下的相關問題，尚有待繼續的研究和討論。