基于MDP的移動機器人室內導航對話管理實現

王恒升 王思遠 張震鋼

摘要：針對自然語言指令對遠程移動機器人導航控制中自然語言理解達不到要求這一問題，提出通過人機對話提高機器人對自然語言指令理解的程度。設計了一個面向救災機器人室內導航的對話管理系統，建立了對話管理系統的馬爾科夫決策過程（MDP）模型。該模型將自然語言指令中導航要素及其屬性的組合定義為狀態集合，把機器人作出的對話回應定義為動作集合。模型訓練的結果是從導航指令中識別出具體的狀態，機器人能作出合理的回應，以使對話能夠自然流暢地進行，達到最終正確理解導航指令。機器人的自然語言生成基于人工智能標記語言（ AIML）設計。實驗測試表明，對話過程流暢自然，用戶體驗較好，準確率達到85.16%。

關鍵詞：對話管理系統;馬爾科夫決策過程（MDP）;人機交互;移動機器人導航

中圖分類號：TP391.1

文獻標志碼：A

1 引 言

對移動機器人進行遠程控制是很多場合的必要選擇，例如月球探測車，用于災害或危險場合的救援機器人等。對機器人進行遠程操作的研究與實踐很早就出現了，例如早在1988年美國三厘島核電站發生核事故后，就使用了一臺遠程操作的機器人，操作人員在無核區，通過鉛化玻璃，操作處于有核區的一臺機器人進行核事故處理。

我們在文獻[1]提出一種通過自然語言進行遠程人機交互的方案，即操作人員通過自然語言發出指令，機器人在遠程執行指令要求的動作。這種自然的、類似人與人之間的交互方式不（或者很少）需要對操作人員進行專門訓練。用于救災機器人的交互時，方便領域專家直接對機器人發出緊急作業指令;用于服務機器人的交互時，更容易為普通用戶所接受。用自然語言與機器人進行交互需要解決的問題包括：語音識別、語義理解[2]、語音合成等。語音識別與語音合成方面的研究已經取得很大的進展，目前可以得到免費的漢語語音識別[3]與語音合成的網絡服務。語義理解被稱為“ AI-完全”問題，雖然在語義網、機器翻譯等方面有不少的研究成果，但目前還不能完全解決這個問題。在文1中將應用范圍限制在遠程機器人導航控制的自然語言理解，提出一種基于層疊條件隨機場（CRF）的自然語言理解模型，將操作人員的自然語言導航指令轉換為結構化的機器人導航指令要素，其總體的正確率達到70%以上。但對于遠程控制機器人完成所需的任務，直接通過單方面的指令理解顯然是不夠安全的。即便是一個人通過對講機遠程指揮另一個人完成某個任務，單方面的指令傳輸都是不夠的，因為存在誤解指令的可能性;往往需要通過對話以確認對指令的正確理解。因此通過自然語言對機器人進行遠程控制時，對話管理[4]是必須的，借以滿足確認指令的需要。

人與計算機對話的研究起因于圖靈測試，即如果人無法區分與他正在對話的是真正的人還是程序，則這個對話程序就通過了圖靈測試，被認為具有一定智能。目前人與計算機的對話系統研究引起了學術界和工業界的巨大興趣，最出名的包括蘋果公司的Siri，微軟的Cortana，谷歌的GoogleNow等，這些產品主要以助理的形式出現，被稱為語音助理。這些被統稱為Chatbot的對話軟件用于協助使用者完成打開應用、搜索網頁、填寫表格等，一般都具有專用性。專門用于圖靈測試的對話系統主要用于模仿人的談話過程，例如2014年6月Engene對話系統通過了圖靈測試，也是迄今唯一通過圖靈測試的對話系統;該系統模仿一個13歲男孩，在對話過程中會出現與這個年齡小孩相應的錯誤，騙過了三分之一的評委，獲勝。還有一些專用的對話系統用于協助旅程規劃[5]、汽車導航問路[6]、處理電子郵件[7]等。許多簡單的對話系統是通過掃描關鍵詞，在數據庫中尋找最合適的模式匹配來是實現的;現在的方向是在對話系統引入對話管理等技術。

本文根據文獻1在自然語言指令理解的基礎上，設計了并實現了一個對話管理系統，主要目的是確保機器人在執行指令要求的動作之前，對指令的理解是正確的。本文后續內容安排如下：第2節介紹系統的總體方案，第3節介紹基于馬爾科夫決策過程模型（ MDP）的對話管理系統，第4節介紹基于人工智能標記語言（ AIML）自然語言生成模塊，第5節介紹機器人語音交互平臺搭建，對話準確率測試以及對話實例展示系統對話效果，最后總結全文。

2 系統結構

基于自然語言的遠程人機交互的示意如圖1所示，操作員在室外安全的區域通過自然語言給處于室內危險現場的機器人發出指令。人機對話系統的整體結構如圖2所示。圖中指令輸入模塊和語音合成模塊采用現有的網絡服務;指令語義理解模塊將自然語言指令轉換為結構化的指令，我們在文1中對這個模塊進行了詳細介紹;在對話管理模塊采用MDP模型，目的是將機器理解的指令內容反饋給操作者，如果有誤則進一步通過對話進行修正;如果無誤就確認指令。自然語言生成模塊采用AIML語言編寫。

考慮到交互過程中需要從自然語言中抽取出用戶態度，以及導航要素多會帶來MDP模型的狀態數激增的問題，這里對文1中導航語義分類模塊和導航要素做出了以下調整：（1）在原來11類導航詞性的基礎上，增加了表示語氣態度的“肯定”和“否定”兩類詞性，如表1所示。（2）將原來的6個導航指令要素修改成了4個：目的地、動作、距離和速度，表2給出幾個導航指令以及導航要素的示例。

經過簡化以后的結構化指令格式為“目的地、動作、距離和速度”，實際的口語導航指令可能會省略其中的要素，表2中的“___”表示省略的導航要素。

3 基于MDP的對話管理

對話管理是對話系統的核心部分，其作用是對用戶與系統的對話交互過程進行控制，模型的好壞決定了對話過程的自然性與交互的流暢性。已有的對話管理技術主要包括：基于任務的方法[8]、基于槽填充的方法[9]、基于信息狀態更新的方法[10]和基于概率模型的方法[11]。基于任務和槽填充的方法主要是查詢和匹配數據庫已有對話內容[12]，其對話過程較為機械，人機交互效果較差，但實現復雜度低，易于開發商業系統。基于信息狀態更新的方法采用的是有限狀態自動機方法，需要人為地去定義自動機狀態和狀態轉移條件，如果需要交互的信息較多，那么需要考慮的狀態和狀態轉移條件就會爆炸性增長，人工的去設計一個完備的對話系統將是一個異常繁雜的過程。本文設計的對話系統是用于領域專家遠程指揮機器人完成救災任務，需要系統具有良好的交互體驗。考慮到救災任務種類多，設計的面向導航的對話系統需要移植機器人其它的任務，如通過對話控制救災機器人自帶的機械臂的作業過程，因此對話系統應該具有良好可擴展移植性。本文選用MDP模型來實現對話管理的功能。MDP模型是一種概率模型，相對于其他對話管理的方法，它是通過分析對話數據利用強化學習（RL）算法來學習管理的決策，這種方法克服了人工定義規則的耗時、覆蓋率不夠等缺點，且具有移植性好、人機交互體驗自然等優點。

3.1

MDP模型建立

MDP模型可以用4元組M={S，A，T，R}來描述，用來定義可觀察的環境狀態（S）集和一系列的可執行的動作（A）集，T和R是模型參數，其中T為狀態轉移矩陣，R為回報矩陣。訓練好的模型可以在外部環境處于S中的某一狀態s時，從A中選擇一個動作a，使狀態s遷移到另一狀態s';如果s是人們所希望的狀態，則這個選擇就是“好的”選擇，反之則是“不好的”選擇。模型訓練的過程，就是對這個“選擇”進行優化的過程;一系列“好的”選擇，就構成優化的“策略”;得到最優策略，就是模型訓練的目標。

在對話系統中，我們把操作員的導航指令看作外部環境，它所處的狀態由導航指令所包含的要素來定義的;“動作”就是機器人對指令的回復。如果機器人對操作員的指令語言回復得自然流暢，可以快速順利地達到雙方對指令語句含義的共識，我們就說這個模型是“好的”，否則模型就需要進一步優化。下面給出本文對話管理MDP模型的具體定義。

S：系統的狀態空間，為一個有限集合，如圖3所示，在本文指的是由自然語言理解模塊從操作人員的導航指令中提取的四個導航要素以及具體屬性排列組合的集合，根據提取出的導航要素以及其內容所確定的導航要素屬性可以確定系統當前所處的狀態。圖3示出每個導航要素屬性值的取值范圍，其中0表示未從導航指令中提取到該導航要素，1表示提取到該導航要素但用戶并未確認，2表示提取到該導航要素并且用戶已經確認，3表示提取到該導航要素但該要素的內容并未出現在己建立的詞庫中。考慮到救災機器人所處的室內建筑存在特定的地名詞，故建立了目的地的地名詞詞庫，所以“目的地”要素的屬性值取0～3;同樣針對指令中包含的機器人的動作也建立了動作詞庫，所以“動作”要素的屬性取值也為0～3。未對距離和速度兩個要素建立詞庫，其取值為0～2。排列組合所有的可能，得到狀態總數為4*4*3*3=144個，表3中列出了部分狀態編號與其對應的要素取值。

A：所有動作的有限集合，在本文中動作即為機器人接受來自人的命令后作出相應的對話回復，表4示出系統所有的動作，從0到9共10種動作。

表4中Re request動作指的是如果系統未提取到導航要素或者操作人說一些與導航無關的自然語言，系統進行的引導提問。Confirm指的有多個要素需要同時確認的提問，V_confirm、D _co n-firm、A_confirm、E_confirm分別指的是對速度、距離、動作、目的地確認的提問，Request指的是存在多個導航要素提取到值但未出現在詞庫當中時，系統的總詢問，A request、Erequest分別表示動作和目的地出現值3的情況下的詢問，Done表示機器人理解操作人員的指令，且操作人員確認無誤后，系統完成一次成功的對話，機器人根據指令內容執行相關的導航任務。

T：S×A→T是狀態轉移矩陣，是一個與S和A相關的矩陣，用T（s，α，s）來描述，矩陣的元素表示在狀態s下，執行動作a，轉移到下一個狀態s'的概率p（s' l s，a）。在本文指的是當操作人員下達指令后，導航要素確定一個狀態s，機器人給出某種行為a后，操作人員下一句對話導航要素確定的狀態s的概率。根據定義可知T是一個三維矩陣，對于本文來說其大小為10 *144 *144。T由已有的對話語料庫統計得來，語料格式如下表：

表5中U表示用戶，S表示系統。S46表示用戶對話確定的狀態是狀態編號為46的狀態。Al表示系統動作編號為1的動作。訓練語料由收集的101條導航相關對話段落組成，根據該語料庫統計出T，由于T較大，這里未給出具體的數值。在統計T的過程中，由于我們收集的用于機器人室內導航語料較少，矩陣中的值會出現很多為0的概率值，即狀態s通過動作a轉移到s'的概率為0，這種情況是不合理且不允許大量出現在狀態轉移矩陣的。本文采用平滑處理的方法來處理0概率問題，借鑒了n元語法模型的加法平滑思想。加法平滑其基本思路是假設每一個n元語法的次數比實際統計的次數多發生δ次，0≤δ≤1，因此概率按下式計算：

式（1）中聲p_add表示進過平滑處理后的概率，w表示詞句中的詞組，δ表示假設每種情況發生的次數，c表示n元語法實際發生的次數，|V|表示語料中單詞的個數，在本文中系統一共有144種狀態

R：S×A→Ⅱ（R）是回報矩陣，表示機器人通過a到達狀態s的立即回報值，是根據人們期望的目標來設定的。在這個模型中，下一個狀態和期望獲得的立即報酬僅與當前狀態和所執行的動作有關，而與歷史無關。n+l時刻的狀態和報酬只依賴于n時刻的狀態和在n時刻所執行的動作。在本文中R是一個10*144（動作總數*狀態總數）的矩陣，給定的報酬函數規則如下：

（1）當出現用戶尚未確認意圖而機器人就采取Done動作時為-100

（2）當出現用戶已確認意圖且機器人采取Done動作時為200

（3）其它情況的回報值為-10

在（3）中取-10是為了讓系統在未完成對話前每一次對話都有”懲罰”，這個”懲罰”可以促使系統以最少對話次數完成有效的對話。

3.2

MDP模型求解

MDP模型求解采用強化學習的方法，其任務是學習一個行為策略π*：S→A，使系統選擇的動作序列能夠獲得的回報值累計達到最大。下式表示系統在狀態s下經過一系列策略兀時，系統所累積的回報值，稱為值函數，其中y為折扣因子，0≤γ≤1，本文取0.95。

根據這個最優的值函數，通過迭代的方法可以計算出相應的最優策略。實現值迭代的偽代碼程序如下：

當MDP模型訓練完成后即生成狀態到動作的映射集。對話管理模塊將已提取好的結構化導航指令為輸入，根據MDP模型的結果便可得到對應的最優動作;在動作之后接上結構化指令，就得到了含有策略的結構化指令，例如導航指令為”快速前進至a503”時，其結構化指令為“a503前加速”，對應的動作為“總確認”，則得到的帶策略的結構化指令為：“總確認a503前加速”。

在python下使用pymdptoolbox工具包訓練MDP模型，利用值函數迭代算法，得到文中建立的MDP模型的訓練結果，下表列出了部分映射關系：

4 基于AIML的自然語言生成模塊

AIML是由Richard Wallace開發的基于XML的自然語言生成語言[14]，常被用來開發對話系統的自然語言生成模塊。AIML的原理是“模板匹配”，它定義了一系列有特定語法和含義的標簽，組成AIML文件主體框架的標簽有四個，分別是、、、。其中< aiml>標簽是AIML文件的最上層標簽，是一個二級標簽用于知識庫的分類，、是兩個基本的標簽是對用戶話語的匹配，是匹配后的回答。本文采用AIML的方式如圖4所示，輸入“帶策略的結構化導航指令”，輸出完整的對話語句。表7給出了幾個實例，說明了自然語言指令輸入下，經過指令的結構化處理，再經過MDP模型給出相應動作生成帶策略的結構化指令，最后由AIML輸出的對話語言的全過程。

只通過AIML開發對話系統是及其繁雜的過程，但在本文的系統中，AIML模塊的輸入是經過處理后的帶有策略結構化的語句，即特定格式的輸入，能到達精準的匹配的效果。使機器人對話的效果顯得準確和自然，且使得編寫的AIML文件簡單、邏輯清晰。以匹配“快速前進至a503”為例，自然語言經過處理后在AIML模塊的輸入為“總確認a503前加速”，例子的AIML程序如下：

總確認*前加速

你確定是要加速去 嗎？

其中標簽內為帶有策略的結構化語言，< template>標簽內為機器人對人的回答，*表示通配符，讀取通配符中的值。

5 實 驗

5.1 機器人語音交互平臺

實驗機器人采用MobileRobots公司的Pioneer3AT移動機器人，如圖5所示。實驗平臺整體基于Labview搭建，對話系統模塊中，語音識別與生成采用科大訊飛SDK開發，對話系統主程序由Python編寫其中CRF模型的訓練通過調用CRF++程序實現、MDP模型與AIML開發分別由pymdptoolbox庫、PyAIML庫實現，Labview通過調用可執行文件的形式與對話系統主程序進行數據交互。底層控制系統采用機器人操作系統（ROS）。語音交互實現機器人導航任務時，從遠程PC端輸入語音指令如圖6所示，經過對話系統進行確認，最后通過無線網絡將確認后的指令傳送給機器人并通過ROS控制其完成導航任務。

5.2 系統準確率

在搭建好的機器人語音交互平臺上對對話系統準確率做出測試，表8中給出了測試實驗結果。以人機各對話一次為一輪，對話輪數指的是完成一次人機交互的對話次數。機器人正確理解人的指令為一次成功的對話，其余情況為失敗的對話。測試所得的總正確率為85.16%。本系統旨在通過對話使得在語音識別和自然語言處理模塊的錯誤輸出信息得以糾正，在文1中直接通過CRF模型的輸出對機器人進行導航控制準確率為70.79%，再考慮到語音識別，以及操作人員本身可能出現指令錯誤等因素，系統的準確率為85.16%，說明整個系統是有效的。

下面為對話測試過程中的一個實例，其中S為系統輸出，U為用戶輸入。在用戶輸入信息中分別標出了導航要素以及其屬性值。如快速到a503中”快速/Speed/速度/1”分別指的是，詞/導航詞性/導航要素/導航要素屬性值。同時給出了MDP模型的導航要素組合，在系統輸出中標出了對應的策略。

S：您好，我是P3AT機器人，我能為您做什么？

U：你快一點走到a503。（快速/Speed/速度/1到/DurativeVerb/動作/1 a503/Place]目的地/1，狀態要素組合為1101）

S：請問是要讓我快速去a503嗎？（Confirm）

U：哦，不是，是去b503。（哦/AT，不/B-NAT是/I-NAT是/I-NAT去/DurativeVerb/動作/2b503/Place/目的地/1，狀態要素組合為1202）

S：請問目的地是b503嗎？（E_confirm）

U：是的。（是的/AT，狀態要素組合為2202）

S：我這就加快腳步前往目的地b503。（Done）

6 結論

針對基于自然語言的移動機器人遠程導航問題，提出通過對話過程提高人機雙方對導航指令的共識。基于MDP模型設計了一個對話管理系統;以結構化導航指令要素為基礎，構成系統的狀態空間;以確認導航要素為目標構成動作空間;通過MDP模型訓練，得到狀態到動作的映射，成為人機對話的核心;自然語言生成模塊基于AIML構成。整個系統的優點有：（1）人與機器人之間的交互自然，不局限于特定的指令，對操作人員沒有特殊的要求，對話流程控制效果佳。（2）方法的領域通用性。可以應用于其他同類系統，如機械臂控制對話系統，機器人作業過程的對話系統等。目前這項工作還在繼續，存在的問題主要有訓練的語料庫規模較小、對話準確率有待進一步提高。下一步主要工作是將系統投入試用，提高語料庫規模，優化模型參數;進行文本分類工作，建立遠程移動機器人交互的其它對話系統。

參考文獻

[1] WANG H，REN J，LI X.Natural spoken instructions under-standing for rescue robot navigation based on cascaded Condi-tional Random Fields[C]//International Conference on Hu-man System Interactions.2016：216 - 222.

[2]NARASIMHAN K，KULKARM T，BARZILAY R.Language Un-derstand-ing for Text-based Games Using Deep ReinforcementLearrring[J].Computer Science，2015， 40（4）：1-5.

[3] 盧天增.基于Android的智能機器人交互技術研究[D].青島：中國海洋大學，2 015.

[4] LISON P.A hybrid approach to dialogue management basedon probabilistic rules [J].Computer Speech&Language，2015，34（1） ：232-255.

[5] LoPEZ-CoZAR R.Using knowledge on word-islands to im-prove the performance of spoken dialogue systems [J].Knowledge Based Systems，2015，88：223- 243..

[6] SHIMIZU A，QINGZHU D，SEKIGUCHI T，et al.Vehiculardevice， server， and information processing method： U.S.Patent 9，218，812[P].2015-12 - 22.

[7] WALKER M A.An Application of Reinforcement Learningto Dialogue Strategy Selection in a Spoken Dialogue Systemfor Email[Jl.Journal of Artificial Intelligence Research，2011，12（1） ：387-416.

[8]DAN B， RUDNICKY A I.The RavenClaw dialogmanagement framework：Architecture and systems[Jl.Com-puter Speech&Language，2009，23（3）：332-361.

[9] RooUE A，TRAUM D.Improving a virtual human using a modelof degrees of grounding[C]// UCAI 2009，Proceechngs of the，ln-ternational Joint Conference on Artifiaal Intelligence， Pasadena，California，USA，July.2009：1537 -1542.

[10]KRONLID F，LAGER T.Implementing the information-state update approach to dialogue management in a slightlyextended scxmI[C]//Proceedings of the llth InternationalWorkshop on the Semantics and Pragmatics of Dialogue（DECALOG）.2007：99-106.

[11]CUAYaHUITL H， KEIZER S，LEMON O.Strategicdialogue management via deep reinforcement learning[C].NIPS' 15 Workshopon Deep Reinforcement Learning-Montreal，Canada，Dec，2015.

[12]黃民烈，朱小燕，對話管理中基于槽特征有限狀態自動機的方法研究[J].計算機學報，2004，27（8） ：1092-1101.

[13] SPRAUEL J，KOLOBOV A，TEICHTEIL-KONIGSBUCHF.Saturated Path-Constrained MDP：Planning under Uncer-tainty and Deterministic Model-Checking Constraints[C]//AAAL2014：2367-2373.

[14]MARIETTO M G B，DE AGUIAR R V，BARBOSA G O，etal.Artificial intelligence markup language：A brief tutorial[J].International Tournal of Computer Science and Engi-neering Survey 2014，04.