基于循環(huán)卷積神經(jīng)網(wǎng)絡的POMDP值迭代算法

于丹寧，倪 坤，劉云龍

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

0 概述

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

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

1 基于CNN的POMDP值迭代算法

1.1 POMDP模型

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

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

1.2 值迭代對POMDP的求解

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

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

1.3 QMDP-net算法

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

QMDP-net共分為POMDP模型和值迭代過程兩部分。QMDP-net將POMDP模型中的狀態(tài)轉(zhuǎn)移概率、觀測概率和獎勵函數(shù)參數(shù)化為：

其中，函數(shù)fT、fZ和fR分別使用卷積神經(jīng)網(wǎng)絡進行表示，其對應的內(nèi)核權(quán)重WT、WZ和WR通過端到端的訓練方式從訓練數(shù)據(jù)中獲得。

在使用卷積層來參數(shù)化規(guī)劃所需模型的基礎(chǔ)上，利用卷積層和最大池化層構(gòu)造值更新過程，并通過循環(huán)更新操作達到價值迭代的目的。第k次狀態(tài)值的更新過程可表示為：

2 基于RCNN的POMDP值迭代算法

2.1 算法思想

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

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

2.2 RQMDP-net算法

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

對于POMDP模型的建立，本文使用雙卷積神經(jīng)網(wǎng)絡結(jié)構(gòu)。對實現(xiàn)狀態(tài)更新的貝葉斯公式進行分解并將其表示為神經(jīng)網(wǎng)絡，其模型網(wǎng)絡結(jié)構(gòu)表達式為：

本文使用循環(huán)卷積神經(jīng)網(wǎng)絡實現(xiàn)值迭代過程，RQMDP-net網(wǎng)絡結(jié)構(gòu)如圖1所示。可以看出，表示網(wǎng)格地圖和任務目標的圖像信息θ通過表示獎勵函數(shù)fR的網(wǎng)絡轉(zhuǎn)換為大小為N×N×|A|的獎勵信息R(s，a)，此網(wǎng)絡是由兩個卷積層組成的卷積神經(jīng)網(wǎng)絡：第一層卷積包含150個大小為3×3的卷積核，并使用線性整流函數(shù)（Relu）作為激活函數(shù)，其作用是對輸入圖像信息進行特征提?。坏诙泳矸e包含|A|個1×1的卷積，其作用是將前一層輸出的特征轉(zhuǎn)換為用于價值迭代計算的R(s，a)。在獎勵信息計算完成后，通過GRU實現(xiàn)價值迭代的計算過程，此處循環(huán)神經(jīng)網(wǎng)絡的神經(jīng)元個數(shù)設置為150。在每次迭代時，作為狀態(tài)價值V（s）的GRU隱含狀態(tài)ht經(jīng)過表示轉(zhuǎn)移函數(shù)fT的網(wǎng)絡后轉(zhuǎn)換為表示Q(s，a)的其網(wǎng)絡由一個包含|A|個大小為3×3卷積核的卷積層組成，之后與R(s，a)分別作為GRU的隱含狀態(tài)和輸入?yún)⑴c下一次迭代的值計算。經(jīng)過K次迭代后的與當前信念狀態(tài)b（s）相乘并加和得到Q(b，a)，即在當前信念狀態(tài)b下，執(zhí)行動作可獲得Q值。最終經(jīng)過全連接（Fully Connected，F(xiàn)C）層和softmax層計算得到表示關(guān)于所有可執(zhí)行動作的概率分布Pr（a），并選擇對應P（ra）最大的a作為最優(yōu)動作。

圖1 RQMDP-net網(wǎng)絡結(jié)構(gòu)Fig.1 RQMDP-net network structure

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

3 實驗與結(jié)果分析

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

3.1 實驗環(huán)境

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

3.2 實驗設置與結(jié)果分析

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

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

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

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

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

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

4 結(jié)束語

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