基于任务规划的家庭仿真服务机器人的研究

章伟++蔡亚楠++杨为民

摘要：随着智能产业的发展，家庭服务机器人越来越多的进入人们的视野。家庭服务机器人研究中两个比较核心的问题是，机器人的任务规划和人机交互。针对于一般的搜索算法会形成组合爆炸，难以求解的问题，本文提出一种任务拆分方法解决任务规划的问题。并基于询问和感知提出两种处理人机交互的方法。通过应用在家庭服务机器人仿真平台上取得的良好效果，证明该算法有效。

关键词：家庭仿真；机器人；任务规划；人机交互；信息获取

中图分类号：TP242 文献标识码：A 文章编号：1009-3044（2016）17-0188-04

Abstract： With the development of the intelligent industry， the home service robot gradually come into the people's eyes. For home service robots， the two core issues are robot task planning and human-computer interaction. For the problem that the general algorithm will cause the combination explosion and it is difficult to solve， this paper puts forward a method to solve task planning problem by the task resolution. Then puts forward two king of methods to solve human-computer interaction based on query and perception. Through the experiment applied in the simulation home service robots's platform， the result shows that this algorithm can solve the problem well.

Key words： family simulation， robot， mission planning， human computer interaction， information acquisition

近年来随着机器人工业应用的普及，家庭服务机器人也逐渐成为了机器人研究领域的热点，

这个领域的成果有助于解决中国人口老龄化，大量老人无人照顾的问题[1] 。为了推广和发展家庭服务机器人的研究，RoboCup世界杯于2006年增加了家庭服务机器人的比赛。目前国内外已有很多一流大学开始了研究和竞赛，在国内以中国科技大学的“可佳”服务机器人为代表。为了促进家庭仿真服务机器人的发展，2009年，由中国科学技术大学首次举办了家庭服务机器人仿真项目比赛，主要是模拟机器人和机器人所可能会处于的环境，致力于研究服务机器人的高层功能，包括机器人的人机对话、对任务的自动规划和自动推理等[2]。由于仿真项目不涉及硬件，所以在很大程度上减少了研究的限制，加速了服务机器人的发展，有利于服务机器人的推广和研究。对于服务机器人竞赛也有很大的帮助。

1家庭机器人仿真

家庭机器人仿真基于一个3D机器人，针对这个机器人在一个模拟现实世界中的室内环境来放置一系列的物体，设置一系列的任务。机器人有九种原子动作来实现九种物理行动，通过这九种物理行动，可以来给定的环境中完成各种任务。机器人设定有一个手爪和一个盘子，可以任意移动一个位置，所有物体的坐标是一维的。手爪一次只能抓一个物体，盘子一次只能放一个物体。机器人可以询问系统物体的位置，也可以自己感知当前坐标下的所有物体的集合。可以看出，机器人完成一个任务会有多种解法。

家庭服务机器人仿真项目比赛所有任务的评分标准为[3]：

仿真服务机器人运行于Challenge Server平台上，由server向client发送场景信息和任务描述信息，client提取并处理信息发回server，server接收到处理的结果，给出判定的分数。Client端程序即为参赛的程序，通过server提供的接口来运行平台。

2问题描述

在实际处理场景中会同时处理多个任务，研究的目的是如何能够用最少的动作完成尽可能多的任务。在人工智能中描述为：从一个状态通过一系列尽可能花费较少的原子行动到达最终状态。图（1）为其状态空间分解图：

针对任务规划问题，已经涌现出几种策略，例如中山大学的A*算法，广东工业大学的文化算法[4]，中国科学技术大学的回答集编程[5]，以及安徽大学也曾采用A*算法[6][7]。这些算法都属于启发式搜索，类似于遗传算法，都是利用搜索给出的原子行动，进行不断试探，寻找一个最短的动作序列来完成状态的转换，并通过一定的约束条件简化计算得出一个最优序列再去执行。这些算法对于任务数较少的时候有着精确的序列和路径规划，随着任务数的增多会组合出非常复杂的序列，难以在规定时间内给出解，在此称之为“组合爆炸”。随着家庭仿真server版本的不断更新，任务数逐渐增多，对时间的要求也越来越严格。对于需要实时完成的动作序列，大量的计算根本无法在规定的时间（目前为5秒）之内计算出最优路径。

3任务最优规划

3.1任务序列

为了解决组合爆炸所带来的复杂性难以求解的问题，提出一种将任务分成单个任务，逐一完成的方法。在文献[8]中，多机器人行为序列也比较复杂，但是通过将行为拆分单个机器人，研究其行动序列，再将其组合为多机器人行为，可以大大简化机器人的行动序列复杂度[8]。类比于单机器人多任务，对于单个任务手算即可产生最佳解法，也可以大大降低了求解难度。这种方法带来的另一个好处就是任务可以实时处理，即使得不出总体最优解，也可以在计算的过程中，解决已经计算出的任务，而不会一直计算无法给出解。并且由于任务描述基本都是每次给出一条任务，因此只需按照其给出的描述拆成单一的任务即可，对于同时给出两条的任务，可以拆成两条描述语句。

然而任务拆分也会带来缺点，即任务拆分之后会大大降低全局的可靠性。在执行任务的过程中由于多个任务可能涉及操作同一个物体，而系统判断有没有完成任务是依据最终每个物体的状态，因此经常会出现一个任务将另一个任务破坏了的情况，达不到最终期望的状态。例如如下任务：1.Close A，2.Takeout B from A。若先执行任务1在执行任务2，任务2要从A里拿出B物体，肯定要把A的门打开才能完成任务2，。执行完1，2后系统判断最后的状态，只完成了任务2，任务1没有完成。

针对任务拆分带来的缺点，通过分析实验各个任务和场景之间的联系，将拆分过后的任务进行排序，增大全局可靠性，给出一个最好的动作序列，保证每个任务都不会被其后的任务破坏。这样既可以解决“组合爆炸”的问题，又可以保证完成每个任务，达到实时给出最优解的目的。排序需要一个好的规则，对于各种不同的场景需要得出一个统一的规律，下面给出试验中所得的规律及优先级设置的思路。

在设置优先级的时候将info设置为最高优先级，这是比较好的一种方式，因为info的信息是确定的，将其解析可以把信息放入初始状态中，这样就可以增加所知道的信息。对于维护任务consnot和consnotnot为第二优先级，维护任务的状态是已经确定的，不可以被破坏掉，因此将次物体的id存到一个单独的集合，在任务搜索的时候搜索不到这些物体，可以保证状态不被破坏。剩下的就是需要执行的任务，为了最快的完成的每个任务而不会将其他任务的状态破坏，采用给每个任务设置不同的优先级方法来完成。

需要执行的任务的优先级可以根据一个简单的规则来设定：机器人在执行下一任务时不能对已完成的任务造成破坏。机器人在执行下一任务时尽可能使机器人手上为空。

经过大量的测试分析，对于goto应该放到最后来做，因为若goto后有任务，必定会移动到其他地方，则此任务失败。对于pickup放在倒数第二个，此后不需要再操作物体，因此手里的物体不会放下。其他任务依次分析，一些需要对容器操作的动作优先级最高，对于open优先级其次，其后是close，再是puton。考虑到涉及容器的操作，应该先开门后关门，对于give放在close之后。

经过以上分析，和实际实验测试得出一个高效的动作序列如下：

给出每个任务的执行次序，之后就可以具体处理每个任务了。

3.2预处理

对任务描述进行预处理，可以任务进行解析、提取出有用信息：要执行什么动作、要对哪些物体进行操作。经过预处理之后，仿真机器人的执行效率能得到很大的提升。但仅仅是这样简单的预处理并不能顺利完成所有的任务。在家庭仿真服务机器人比赛的中，一个任务文档内的两个不同任务之间可能并不完全的独立，而是在执行完一个任务后会对已完成的任务造成破坏。在家庭仿真服务机器人比赛中，导致这种情况发生的大部分原因是机器人在执行不同任务时处理的是同一小物体[9]。

3.2.1任务分组

假设场景信息中有以下描述：

（sort 12 book） （size 12 small） （color 12 black）

（sort 13 book） （size 13 small） （color 13 green）

任务信息中有以下描述：

（：task （putin X Y） （：cond （sort X book） （sort Y closet）））

（：task （puton X Y） （：cond （sort X book） （color X black） （sort Y table）））

按照之前设定的动作序列，先执行putin任务，在执行puton任务。但是在实际过程中，若搜索函数每次都是顺序搜索，在执行两个任务时，搜索到的均是black book。显然，执行完puton任务之后把之前执行过的putin任务给破坏掉了。此时对任务进行预处理可以有效解决此问题。

可以看到，putin中的有效信息为（putin X Y）、（sort X book）、（sort Y closet），有效信息数为3。puton中的有效信息为（puton X Y）、 （sort X book）、（color X black） （sort Y table），有效信息数为4。两组信息之间仅仅是差了一条关于小物体的描述信息。这样就可以在执行任务之前先将所要处理的任务分成两组。将任务信息中有对小物体进行描述的任务分成一组并优先处理这一组的任务，将任务信息中没有对小物体进行描述的任务分成另一组，执行每组的任务时同样是按照之前设定的动作序列依次执行。

对于putdown、goto这两种任务要单独处理。这就相当于设定了四个优先级，putdown的任务优先级最高，有对小物体进行描述的一组任务优先级第二，另一组的任务优先级第三， goto的任务优先级最低。

通过这种简单的分组排序来对任务优先级进行划分，这样在合理的安排任务执行顺序就可以得到最优的任务规划。这样处理起来简单有效，基本可以保证每个任务都能完成。

3.3人机交互

在家庭仿真机器人的比赛中，比赛第二阶段所给的任务文档里给出的任务场景是不完整的，还有错误的，需要智能体机器人去问系统或感知周围环境来获取任务所需的正确信息。但是通过询问系统所给出的答案只有60%的正确率，感知周围环境得到的信息则是100%正确。根据正确的信息才能进行任务的正确的规划。下面提出三种人机交互的方式，经过实验均为可行策略。

3.3.1重复询问

在处理任务时，为了顺利完成任务，必须获取正确的信息。对于未知物体的位置的获取，重复询问可以算是最简单的一种策略了。在家庭仿真服务机器人第二阶段的比赛中，通过AskLoc动作询问系统得到的信息只有60%的正确率，错误为30%，不知道为10%。不知道不算在内，实际上正确率为66.6%，错误率为33.3%。根据伯努利概型，二项概率公式，可以计算出得到n次之内对的概率。二项概率公式如下：

其中p为正确概率，q为错误概率。在考虑AskLoc动作所花的代价，每次询问都会扣除2分，而完成一个任务得40分。所以，重复询问策略一般是：询问系统三次，将两次或两次以上的相同的信息视为正确信息。通过这种策略最后得到的信息有74.07%的概率为正确信息。

3.3.2移动感知

通过重复询问得到的信息的正确率始终达不到100%。而通过sense动作感知周围环境所得到的信息能保证是100%正确的。这时，就可以将Move动作与Sense动作交替使用，从而得到任务所需的正确信息。再判断Sense得到的信息中是否有需要的信息，如果有，则继续往下执行任务；如果没有，则移动到下一位置，再次感知当前位置上的所有物品信息，直到找到所需信息。

很显然，这种策略在足够大的代价下是能够可以找到所有物品的位置信息。但是这种策略往往具有盲目性，它只是不断从一个大物体的位置移动到另一个大物体的位置。很多情况快只移动一次是并不能找到所需的位置信息，需要继续寻找下去，而如果这时整个任务中所需要小物体的位置信息只有一个，这样所花的代价往往是过大的，甚至超过了重复询问所花费的代价。

同时这种策略还会导致另一个问题：超时问题。由于一直没有找到所需要的小物体，就会导致机器人在处理任务时超过了比赛规定的时间。

相对于重复询问策略，在家庭仿真服务机器人比赛中，这种移动感知策略更佳被优先采用，而且在比赛中这种策略出现超时的情况也比较少。

3.3.3询问感知

在家庭仿真服务机器人比赛的第二阶段中，除了要处理任务文档中的缺失信息外，还要处理文档中给出的错误信息。这时可以考虑使用比赛平台提供的AskLoc（）和Sense（）函数一起配合使用。

将每次AskLoc得到的有效信息都当做正确信息使用，这时得到的信息的正确率为66.6%。然后继续处理任务。在执行任务时，无论是因为之前到的信息错误还是任务文档中的错误场景描述导致平台返回“false”信息，都可以使用Sense动作来更新得到的物体位置信息。然后重新执行AskLoc动作获取有效信息，重复之前的过程直到任务完成。

由概率统计随机变量及其分布公式：P（n）=1-（1-p）^n（p为正确概率）算出概率。基于这样的策略得出概率折线图如图2：

根据图2（其中横坐标为询问次数，纵坐标为理论正确概率）可以看出，这种策略通过两次AskLoc动作得到正确信息的概率要比重复询问三次得到的正确信息的概率要高得多，理论上三次询问就能得到正确信息了。

4 结语

在家庭服务仿真机器人的比赛中，机器人到每一个坐标的代价是相等的。因此给出的最优任务序列是实验和分析得出的，只能是在大部分情况下最优，在某些情境下不一定是最优序列。一个正确信息的获取是整个任务规划的基础，如何快速高效的获取所需的正确信息将是提高提高任务规划效率的关键方法。

参考文献：

[1] 田国会，李晓磊，赵守鹏，等.家庭服务机器人智能空间技术研究与进展[J].山东大学学报：工学版，2007，37（5）：53-59.

[2]XiaopingChen，JianminJi，JiehuiJiang， GuoqiangJin，FengWang，JiongkunXie.Developing High-level Cognitive Functions for Service Robots， In： Proc. of 9th Int. Conf. on Autonomous Agents and Multi-agent Systems （AAMAS 2010）， Toronto， Canada， May 2010.， 2012，2（1）： 100-117.

[3] 家庭机器人仿真比赛规则2013：15-16. http：//www.wrighteagle.org/homesimulatin

[4] 陈树斌，陈玮，李剑平. 基于文化算法的家庭服务机器人任务规划[J].计算机工程与应用，2012，48（33）：212-216.

[5] 吉建民. 提高ASP效率的若干途径及服务机器人上应用[D].中国科学技术大学，2010.

[6] 李星. 服务机器人仿真系统的动作序列规划研究[D]. 安徽大学，2012.

[7] 王孝贵. 仿真服务机器人任务规划研究[D]. 安徽大学，2013.

[8] 余婷，梁阿磊.基于局部行为序列的多机器人曲线移动技术[J].计算机应用与软件，2009，26（12）：40-43.

[9]刘岩恺，薛毅.家庭仿真求解最优路径问题算法研究，2006，11（6）：28-29.