基于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.