基于循環卷積神經網絡的POMDP值迭代算法

于丹寧，倪 坤，劉云龍

（廈門大學航空航天學院，福建廈門 361102）

0 概述

隨著人工智能技術的快速發展，智能體規劃被廣泛應用于組合調度、游戲博弈等任務［1-2］中，然而現實世界中的動態系統多數面向部分可觀測環境，針對部分可觀測環境下的智能體規劃問題，部分可觀測馬爾科夫決策過程（Partially Observable Markov Decision Process，POMDP）模型應用而生［3-5］。POMDP模型的核心思想是將動態系統中的不確定性規劃問題轉化為最優化問題進行求解，但由于其基于系統隱含狀態空間進行建立，因此人為建立模型需要大量先驗知識并且存在容易陷入局部極小值的問題［6-7］。深度神經網絡作為一種多層次特征學習網絡，能夠自動從訓練數據中學習抽象特征［8］。KARKUS等人在深度神經網絡與QMDP模型的基礎上，提出基于卷積神經網絡（Convolutional Neural Network，CNN）的POMDP值迭代算法QMDP-net［9］，其是QMDP模型的網絡化表示，能使POMDP模型所需的參數以網絡中權值的形式通過訓練數據進行自動學習，無需提供大量的先驗知識或假設POMDP模型已知。此外，QMDP-net已被證明在未預先給定環境模型的情況下可有效解決2D網格地圖上的導航規劃問題［10-12］。

由于QMDP-net中的值迭代模塊是通過卷積層與最大池化層相結合的網絡結構進行表示，然而該網絡結構使得QMDP-net存在訓練結果不穩定、隨機種子及超參數敏感等問題［13-14］。為解決上述問題，本文提出一種基于循環卷積神經網絡（Recurrent Convolutional Neural Network，RCNN）的POMDP值迭代算法RQMDP-net，使用門控循環單元（Gated Recurrent Unit，GRU）網絡實現值迭代過程，并以經典游戲《格子世界》網格地圖上的導航規劃任務為例對RQMDP-net算法的有效性進行驗證。

1 基于CNN的POMDP值迭代算法

1.1 POMDP模型

POMDP是一種對部分可觀測環境規劃問題進行系統建模的常用模型。POMDP模型由一個七元組構成：M=（S，A，O，T，Z，R，b0）［15］，其中：S、A、O分別表示動態系統的所有狀態集合、動作集合和觀測集合；T(s，a，s')=Pr(s'|s，a)表示狀態轉移概率，即在狀態s下執行動作a后，轉移到其他狀態s'的概率分布；Z(s，a，o)=Pr(o|s，a)表示觀測概率，即在狀態s下執行動作a后，獲得觀測值o的概率分布；R（s，a）表示在狀態s下執行動作a所獲得的獎勵；b0表示初始狀態分布，即在初始時刻智能體在狀態集合S上的分布。

在部分可觀測環境下，智能體僅通過當前觀測無法準確感知當前所處的狀態，因此需要根據過去的歷史序列{a1，o1，a2，o2，…，at，ot}對當前狀態進行估計。POMDP引入信念狀態b來表示智能體的當前狀態，其中b是對過去所有歷史信息的總體統計量，代表當前所有隱含狀態的概率分布［16］。在已知當前信念狀態b、執行動作a和獲得觀測值o的情況下，通過貝葉斯公式的更新來獲得下一時刻的信念狀態［17］可表示為：

1.2 值迭代對POMDP的求解

值迭代對POMDP的求解是在建立準確POMDP模型的基礎上，使用值迭代算法進行動作選擇以達到回報最大化的目的。值迭代作為求解馬爾科夫決策過程（Markov Decision Process，MDP）的一種經典動態規劃算法，其從任意初始狀態值開始，使用貝爾曼方程組迭代求解狀態的值函數。令Vk(s)表示狀態s在第k次迭代中的評估值，值迭代過程可表示為［9］：

POMDP模型使用信念狀態b表示智能體當前所處狀態，其向量中元素b(s)表示智能體當前處于狀態s的概率。當k趨于無窮大時，值函數V（s）會收斂于最優值函數V*(s)，此時在b狀態下執行動作a所得的最大回報其對應的最優策略可表示為：

1.3 QMDP-net算法

由于使用值迭代算法對POMDP問題進行求解的前提是建立準確的POMDP模型，然而學習動態系統的POMDP模型通常很困難，因此模型建立需要大量的先驗知識。QMDP-net是一種用于解決部分可觀測環境下動態規劃問題的網絡化值迭代算法。QMDP-net使用深度神經網絡對POMDP算法的求解過程進行表示，使得所需POMDP模型的參數可以以網絡中權值的形式通過訓練數據進行自動學習［9］。因此，QMDP-net可以在無先驗知識的情況下對POMDP問題進行求解。

QMDP-net共分為POMDP模型和值迭代過程兩部分。QMDP-net將POMDP模型中的狀態轉移概率、觀測概率和獎勵函數參數化為：

其中，函數fT、fZ和fR分別使用卷積神經網絡進行表示，其對應的內核權重WT、WZ和WR通過端到端的訓練方式從訓練數據中獲得。

在使用卷積層來參數化規劃所需模型的基礎上，利用卷積層和最大池化層構造值更新過程，并通過循環更新操作達到價值迭代的目的。第k次狀態值的更新過程可表示為：

2 基于RCNN的POMDP值迭代算法

2.1 算法思想

雖然QMDP-net在無先驗知識的情況下具有較好的性能表現，但其存在訓練效果不穩定、參數敏感等優化難題。QMDP-net使用卷積層與最大池化層相結合的網絡結構表示狀態值的更新過程，由于卷積神經網絡不具備記憶功能，因此需要通過不斷循環運行該網絡模塊來達到值迭代的效果。循環神經網絡（Recurrent Neural Network，RNN）具有記憶功能，更適合于循環處理時序問題［18］，因此，將值迭代過程編碼為循環神經網絡可有效緩解QMDP-net的優化難題。

由于RNN無法解決長期依賴問題，當循環次數較多時容易出現梯度消失現象［19］，因此本文使用門控循環單元網絡來模擬值迭代過程，提出基于循環卷積神經網絡的POMDP值迭代算法RQMDP-net。GRU通過門控機制有效緩解了RNN的梯度消失問題，而且相比LSTM具有更簡單的網絡結構［20］。將值迭代過程使用由GRU和CNN結合構造的循環卷積神經網絡進行表示，具體為：

2.2 RQMDP-net算法

RQMDP-net在經典游戲《格子世界》網格地圖上的導航規劃任務中，系統狀態空間為N×N（其中N為網格數量），對應信念狀態b可由N×N矩陣表示，該模型已知包含地圖和任務目標信息的環境參數X。

對于POMDP模型的建立，本文使用雙卷積神經網絡結構。對實現狀態更新的貝葉斯公式進行分解并將其表示為神經網絡，其模型網絡結構表達式為：

本文使用循環卷積神經網絡實現值迭代過程，RQMDP-net網絡結構如圖1所示?？梢钥闯?，表示網格地圖和任務目標的圖像信息θ通過表示獎勵函數fR的網絡轉換為大小為N×N×|A|的獎勵信息R(s，a)，此網絡是由兩個卷積層組成的卷積神經網絡：第一層卷積包含150個大小為3×3的卷積核，并使用線性整流函數（Relu）作為激活函數，其作用是對輸入圖像信息進行特征提??；第二層卷積包含|A|個1×1的卷積，其作用是將前一層輸出的特征轉換為用于價值迭代計算的R(s，a)。在獎勵信息計算完成后，通過GRU實現價值迭代的計算過程，此處循環神經網絡的神經元個數設置為150。在每次迭代時，作為狀態價值V（s）的GRU隱含狀態ht經過表示轉移函數fT的網絡后轉換為表示Q(s，a)的其網絡由一個包含|A|個大小為3×3卷積核的卷積層組成，之后與R(s，a)分別作為GRU的隱含狀態和輸入參與下一次迭代的值計算。經過K次迭代后的與當前信念狀態b（s）相乘并加和得到Q(b，a)，即在當前信念狀態b下，執行動作可獲得Q值。最終經過全連接（Fully Connected，FC）層和softmax層計算得到表示關于所有可執行動作的概率分布Pr（a），并選擇對應P（ra）最大的a作為最優動作。

圖1 RQMDP-net網絡結構Fig.1 RQMDP-net network structure

本文采用反向傳播算法［21］最小化交叉熵損失函數來優化深度神經網絡模型，并將表示動作選擇錯誤程度的損失函數定義為：

3 實驗與結果分析

為驗證基于循環卷積神經網絡的值迭代算法RQMDP-net的有效性，實驗在經典游戲《格子世界》網格地圖上的導航規劃任務中對RQMDP-net與QMDP-net的執行情況進行對比，并基于TensorFlow實現算法網絡框架的搭建，同時使用NVIDIA 1060 GPU加速圖像處理。

3.1 實驗環境

實驗任務是使智能體在N×N網格地圖中進行導航。智能體已知的環境參數為標明障礙物和導航目標的N×N網格地圖，其能觀測四周是否有障礙物信息，而不同的位置周圍障礙物的分布情況可能相同，因此智能體無法僅根據當前觀測信息來獲知自身在網格中的準確位置，即智能體狀態。智能體可執行的動作包括向四周走動和原地不動5個。

3.2 實驗設置與結果分析

在實驗中，將來自1 300種隨機環境下的65 000條專家軌跡（每個環境對應50條專家軌跡）作為數據集，其中，1 000種隨機環境的50 000條軌跡作為訓練集，300種環境的15 000條軌跡作為測試集。在網絡訓練過程中使用ADAM優化器更新網絡參數，其初始學習率為0.000 1。

本文實驗將導航準確率和交叉熵損失值作為算法性能評價指標，其中，導航準確率為智能體導航至目標位置的概率，交叉熵損失值為當前網絡動作選擇錯誤的概率。實驗中有網格數量N和值迭代次數K2個控制變量，其中，N取值為10、18、24、36，K取值為3、5、10、15。本文通過兩組實驗驗證算法有效性及控制變量變化對算法性能的影響。

第1組實驗通過設置不同的網格數量和值迭代次數來對比RQMDP-net和QMDP-net的導航準確率。由表1可以看出，在不同的網格數量下，RQMDP-net的導航準確率高于QMDP-net。在相同的網格數量下，隨著值迭代次數的增加，RQMDP-net的導航準確率在多數情況下相比QMDP-net增長更快?？梢姡琑QMDP-net在10×10網格地圖中的導航準確率高達98.5%，并且在36×36網格地圖中相比QMDP-net最多提升5.8個百分點。

表1 在N×N網格地圖中K次值迭代的算法導航準確率對比Table 1 Comparison of algorithm navigation accuracy of K iterations in the N×N gird map %

第2組實驗通過設置不同的網格數量和值迭代次數來對比RQMDP-net和QMDP-net的交叉熵損失值下降情況。由圖2可以看出，與QMDP-net相比，RQMDP-net的交叉熵損失值下降更快，可經過更少的數據集迭代次數達到最低值，主要原因為RQMDP-net利用GRU網絡使其時序處理能力更強，最終交叉熵損失值也更小，即相同條件下的RQMDP-net動作選擇錯誤的概率小于QMDP-net。

圖2 交叉熵損失值與數據集迭代次數的關系Fig.2 The relationship between cross entropy loss value and the number of iterations of the dataset

4 結束語

本文提出一種基于循環卷積神經網絡的POMDP值迭代算法RQMDP-net。利用GRU網絡與CNN實現值迭代過程，解決了僅由卷積層和最大池化層構成的QMDP-net訓練不穩定、超參數設置敏感等問題，并且通過GRU網絡的強時序處理能力，提升了RQMDP-net的算法運行速度。實驗結果表明，與QMDP-net相比，RQMDP-net在訓練過程中網絡收斂速度更快，任務規劃能力更強。后續可將RQMDP-net擴展至具有更復雜狀態空間的導航規劃任務中，進一步提高其適用性與通用性。