于丹寧，倪 坤，劉云龍

（廈門大學(xué)航空航天學(xué)院，福建廈門 361102）

0 概述

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

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

1 基于CNN的POMDP值迭代算法

1.1 POMDP模型

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

1.2 值迭代對POMDP的求解

值迭代對POMDP的求解是在建立準(zhǔn)確POMDP模型的基礎(chǔ)上，使用值迭代算法進(jìn)行動作選擇以達(dá)到回報最大化的目的。值迭代作為求解馬爾科夫決策過程（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表示智能體當(dāng)前所處狀態(tài)，其向量中元素b(s)表示智能體當(dāng)前處于狀態(tài)s的概率。當(dāng)k趨于無窮大時，值函數(shù)V（s）會收斂于最優(yōu)值函數(shù)V*(s)，此時在b狀態(tài)下執(zhí)行動作a所得的最大回報其對應(yīng)的最優(yōu)策略可表示為：

1.3 QMDP-net算法

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

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

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

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

2 基于RCNN的POMDP值迭代算法

2.1 算法思想

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

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

2.2 RQMDP-net算法

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

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

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

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

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

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

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

3.1 實驗環(huán)境

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

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

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

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

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

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

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

圖2 交叉熵?fù)p失值與數(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)絡(luò)的POMDP值迭代算法RQMDP-net。利用GRU網(wǎng)絡(luò)與CNN實現(xiàn)值迭代過程，解決了僅由卷積層和最大池化層構(gòu)成的QMDP-net訓(xùn)練不穩(wěn)定、超參數(shù)設(shè)置敏感等問題，并且通過GRU網(wǎng)絡(luò)的強(qiáng)時序處理能力，提升了RQMDP-net的算法運(yùn)行速度。實驗結(jié)果表明，與QMDP-net相比，RQMDP-net在訓(xùn)練過程中網(wǎng)絡(luò)收斂速度更快，任務(wù)規(guī)劃能力更強(qiáng)。后續(xù)可將RQMDP-net擴(kuò)展至具有更復(fù)雜狀態(tài)空間的導(dǎo)航規(guī)劃任務(wù)中，進(jìn)一步提高其適用性與通用性。