一种导览机器人的任务规划方法研究

李月光，尹 东，张 荣



一种导览机器人的任务规划方法研究

李月光，尹 东，张 荣

(中国科学技术大学信息科学技术学院，合肥 230027)

为导览机器人实现服务目标的引导规划，提出一种以机器人操作系统为实验平台，结合马尔科夫决策过程和微重启技术的任务规划方法。该方法在全面考虑服务对象身份需求信息及服务过程的总代价后，利用马尔科夫决策模型确立最优执行方案。采用基于机器人分布式操作系统建立的微重启自我修复机制解决功能失效问题。仿真结果验证了该规划方案在执行导览任务中的有效性，同时表明微重启技术在处理功能失效问题时相对于传统处理方法具有优越性，其在随机附加障碍的情况下可获得91.03%的规划成功率。

导览机器人；操作系统；马尔科夫决策过程；任务规划；微重启；马尔科夫决策模型

1 概述

近年来包括导览机器人、家庭服务机器人、医疗型机器人等在内的多种服务机器人得到了迅速的发展，很多博物馆、科技馆已经可以见到导览机器人的身影。在实际应用中导览机器人面临如下问题：(1)能否实现导览任务，即功能设计的合理性；(2)能否对异常情况进行处理，即安全稳定性；(3)执行速度能否达到要求，即高效实用性。这些都是任务规划所要解决的问题，因此，研究导览机器人的任务规划具有重大的意义。

作为机器人功能实现的重要环节，很多学者从不同角度研究了机器人任务规划的方法。常用的注重人机互动的任务规划方法有：将机器人与人分享同一套描述环境的符号集模型，如文献[1-2]提出了多层次交互式任务规划，解决了使用符号集进行人机交互效率较低的问题。文献[3]提出了一种模仿人类意识的规划框架，使得人机交互更加安全合理。实现实时处理随机问题的规划方法有马尔科夫决策理论，文献[4-5]研究了马尔科夫决策模型在机器人规划上的应用。改变描述空间环境的方式也是任务规划的研究重点。传统的描述方法有度量地图[6]及拓扑地图[7]，文献[8]结合两者优点提出了混合地图，文献[9]介绍了语义地图描述方法，文献[10]将语义地图用在任务规划中取得了很好的效果。针对规划速度的问题，文献[11]提出了一种用超图的邻接矩阵求解状态之间可达关系的方法，简化了规划过程，提高了求解效率。

本文主要研究导览机器人在中国科学技术大学校史馆实现引导讲解服务的任务规划设计。规划决策的关注点是高层规划，提出一种具有一定普适性的解决方案。该方案在其他的导览场景，如医院、银行、博物馆都可以使用，它囊括从机器人服务对象的选取到任务序列的生成，再到异常情况的处理，整个服务过程的设计方法。

2 导览任务功能结构设计

任务规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得状态为止[12]。因此，对任何机器人的规划都不能脱离机器人的功能本身，就本文来说设计一个能够实现导览任务的总体结构，并确定该结构中各个功能模块间的联系是任务规划的第一步。

2.1 基于机器人操作系统的功能结构设计

本文的导览机器人采用的是机器人操作系统(ROS)分布式通信系统。这里的分布式通信系统是指系统中各个模块的运行方式是以节点形式相对独立的运行，当每个节点运行完成后其结果由通信机制整合到一起。这种工作方式可以分解简化问题，提高效率。ROS系统中节点与核心或者节点之间的通信是通过话题与服务实现的，该实现过程由通信核心(即内核)通过启动节点rosout收集其运行的调试信息，进行全程的监督管理。根据ROS系统结构，将导览任务细分，设计的功能结构如图1所示。

图1 功能结构

导览任务分为3个部分：人机信息交互模块，导航模块，运动控制模块。这3个功能模块构成系统的二级节点，其中每个模块又有各自的任务子节点。他们之间的通信方式是这样设计的：节点4和节点5在运行结束时会以话题的形式向核心发布运行结果，同时节点1向核心订阅这个话题(任何节点都可以订阅)信息，该信息的传递由节点rostopic控制，并参与到节点1的功能实现。节点2和节点3在运行时向核心提出服务要求，此时满足条件的节点5、节点7及节点8、节点9将会分别启动应答。最终当所有节点的功能都实现完毕，则整体任务完成。

2.2 基于微重启技术的自愈结构设计

微重启技术本质是一种自下至上的递归重启策略[13]。首先重启功能失效的节点及其直接下游节点，如果依然无法解决该失效问题，则把此节点所在的直接上游进行重启。若问题依然存在，则继续递归直至功能实现。涉及到的重启规则定义如下[14]：

(1)若的执行依赖，即A是的上游节点，则。

(5)若和共享数据或状态，则。

根据本文的功能结构，微重启自愈结构设计如图2所示。

图2 自愈结构设计

本文关注的是高层规划，因此，将整个系统结构分为 3层，但为了便于底层实现及后续功能的扩展，将任务层做了进一步的细分。以图2所示的结构为例，假设要恢复系统中一个已发生故障的节点，如动作控制，实际上是恢复其本身及可能引起该故障的所有下游节点，即面部动作及躯干动作。若无法解决问题，那么系统将推断节点功能的失效可能是由其上游节点发生故障而传播过来的，这时将以递归的方式恢复上游节点运动控制，如此进行循环重启直至问题解决。对于数据或状态相互依赖的情况，如全局路径规划和局部路径规划，系统将在重启过程中监听该数据或状态来判定共享项是否需要被重启。

3 导览任务规划模型设计

3.1 马尔科夫决策过程

马尔科夫过程由俄罗斯数学家马尔科夫于1907年提出，它是一种无后效性的过程，即下一时刻的结果仅依赖于当前时刻，而与以前的结果无关。这种忽略历史的影响，无需不断地保存历史信息的特性已被广泛应用于多个领域。马尔科夫决策过程是马尔科夫过程在机器人上的一种应用。

图3 状态转移过程

最终得到的最优策略即为最佳的行动序列。

3.2 基于MDP的规划模型

表1 状态集合

表2 动作集合

4 仿真结果及分析

实验前期准备共邀请了20位志愿者，其中18人包括脸谱信息在内的多个信息将被录入数据库，2位作为首次访问者参与本实验。实验开始时随机数量的人将出现在机器人面前等待服务，机器人将根据识别的结果结合决策模型找到一个最优的执行序列，同时微重启结构将监督动作的执行，最终完成导览目标。下面将选取一个例子展示本文工作。

图4 视觉模块获取信息实例

图5 包含任务信息的平面图

表3 最优实际执行序列

实际行动序列为：

为了验证微重启技术在本次规划中的恢复性能，在每个规划的过程中随机添加了引起任务失败的障碍。由于不同模块重启耗时不同，因此采用重启的节点个数来描述恢复过程的执行复杂度。针对移动失效和识别失效这2类问题，实验包括微重启和宏重启(即重启整个错误模块)在内各进行了4组，每组50次。实验结果如图6所示。

从图6中可以看出，由于障碍是随机添加的，不同性质的障碍恢复复杂度不同，因此曲线有所波动。移动功能的失效因为其设计的复杂度要高于识别功能，所以总体恢复代价高。对于相同的问题，微重启在执行效率上要明显高于宏重启，且随着处理次数的增多差距逐渐加大。

最后，整个规划实验包括多人及单人的情况，共进行了145组，规划达到预期目标的成功率为91.03%(132/145)，错误主要集中在视觉模块性能的局限性，导致服务信息不准确，以及障碍过多，使得系统长时间停留在系统层重启。

5 结束语

本文探讨了整个规划系统的构建方法，提出了基于马尔科夫决策模型和微重启技术的决策方案。该方案通过计算折算累积回报找到最优策略，同时监督单元监听该策略的执行情况，并结合微重启技术确保每次的状态转移都是预期的。通过实验可以看出，虽然该方案降低了马尔科夫决策处理不确定问题的能力，但依然不失为一种有效的规划方法。本文的研究重点在高层规划，但是底层实现的精度对规划结果有很大的影响，根据机器人实际运行情况后续还有大量调试工作。在实际应用中为观测到全部信息的代价很大，因此，采用部分可观察的马尔科夫决策模型是一个较好的改进方向。

[1] Dillmann R, Zoellner R, Ehrenmann M. Interactive Natural Programming of Robots: Introductory Overview[C]//Proc. of IEEE-RAS Joint Workshop on Technical Challenge for Dependable Robots in Human Environments. Tolouse, France: [s. n.], 2002: 253-258.

[2] Galindo C, Madrigal F J A. Multihierarchical Interactive Task Planning: Application to Mobile Robotics[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2008, 38(3): 785-798.

[3] Sisbot E A. A Human-aware Manipulation Planner[J]. IEEE Transactions on Robotics, 2012, 28(5): 1045-1057.

[4] 石 轲. 基于马尔可夫决策过程理论的Agent决策问题研究[D]. 合肥: 中国科学技术大学, 2008.

[5] 范长杰. 基于马尔可夫决策理论的规划问题的研究[D]. 合肥: 中国科学技术大学, 2010.

[6] Thrun S, Fox D, Burgard W. Probabilistic Mapping of an Environment by a Mobile Robot[C]//Proc. of IEEE Interna- tional Conference on Robotics and Automation. [S. l.]: IEEE Press, 1998: 1546-1551.

[7] Choset H, Nagatani K. Topological Simultaneous Localization and Mapping(SLAM): Toward Exact Localization Without Explicit Localization[J]. IEEE Transactions on Robotics and Automation, 2001, 17(2): 125-137.

[8] Buschka P, Saffiotti A. Some Notes on the Use of Hybrid Maps for Mobile Robots[C]//Proc. of the 8th International Conference on Intelligent Autonomous Systems. Amsterdam, the Netherlands: [s. n.], 2004: 547-556.

[9] 庄 磊. 智能移动机器人地图描述和导航方法研究[D]. 南京: 南京理工大学, 2011.

[10] Galindoa G, Madrigala J A F, Saffiotti A. Robot Task Planning Using Semantic Maps[J]. Robotics and Autonomous Systems, 2008, 56(11): 955-966.

[11] 文中华, 黄 巍, 刘任任, 等. 模型检测规划中的状态之间的可达关系研究[J]. 计算机学报, 2012, 35(8): 1635-1643.

[12] 蔡自兴. 机器人学[M]. 2版. 北京: 清华大学出版社, 2009.

[13] Shi Changting, Zhang Rubo, Zhao Jing. Software Self-recovery Method of AUV Based on Micro-reboot[C]//Proc. of the 9th World Congress on Intelligent Control and Automation. [S. l.]: IEEE Press, 2011: 91-96.

[14] Shi Changting. Layered Self-healing Software Architecture of AUV Based on Micro-reboot[C]//Proc. of International Workshop on Intelligent Systems and Applications. [S. l.]: IEEE Press, 2009: 1951-1954.

编辑 顾逸斐

Study on a Task Planning Method for Tour Guide Robot

LI Yue-guang, YIN Dong, ZHANG Rong

(School of Information Science and Technology, University of Science and Technology of China,Hefei 230027, China)

Towards the planning problem of robot for guiding service objects, Robot Operating System(ROS) as experimental platform, combined with Markov Decision Process(MDP) and micro-reboot technology, this paper presents a robot task planning scheme suitable for guide service. After considering comprehensive service object identity information and total cost of service process, the scheme establishes optimal execution plan using MDP model. And based on the ROS distributed system, the scheme uses micro-reboot self-repairing mechanism to solve the functional failure problem. The simulation results show that the proposal is effective in the implementation of navigation mission. Compared with the traditional processing method, it shows the advantages of micro-reboot technology in dealing with functional failures. The planning scheme gets 91.03% success rate in the case of additional barriers randomly.

tour guide robot;operating system; Markov Decision Process(MDP); task planning; micro-reboot; Markov decision model

1000-3428(2014)03-0196-05

A

TP18

中国科学技术大学重要方向培育基金资助项目“机器人智能交互、柔性机械与高性能样机研制”。

李月光(1987－)，男，硕士，主研方向：机器人任务规划，机器视觉；尹 东、张 荣，副教授。

2012-12-19

2013-04-02 E-mail：lyg@mail.ustc.edu.cn

10.3969/j.issn.1000-3428.2014.03.041