基于线性规划的家庭仿真机器人的研究

常顺 吴雪峰 刘向举

摘要： 由于家庭仿真机器人比赛在第二阶段场景信息中存在错误信息，导致常规算法难以实现且效果不佳。针对该问题提出线性规划算法予以解决，首先，对不同种类任务进行优先级排序，采用混合人机交互方式纠正场景中的错误信息;其次，采用分而治之方法规划每个任务，并根据场景进行优先级实时调整;最后，在Ubuntu16.04系统下进行大量实验，结果表明我们所提方法能有效完成多任务规划问题并可以准确纠正错误信息以完成任务。

关键词：多任务规划;人机交互;信息纠正;家庭仿真;机器人

中图分类号：TP311     文献标识码：A

文章编号：1009-3044（2019）18-0183-04

随着智能科技的发展，智能产品在人们生活中随处可见，对其研究也是一种热门，其中机器人的研究也是其中一项重要研究。现在各大高校也开始研究这个领域，其中一些高校也取得了一些成绩。为了促进大学生也参与到这一项目中，全国乃至全世界也举办了很多的机器人比赛。在安徽，2009年中国科学技术大学首次举办了家庭仿真机器人比赛，主要针对自主机器人在家庭环境中的典型应用，主要研究人机交互、自动规划、推理、环境感知和重新规划。

在机器人的研究中，其中任务规划部分一直是难点，而且在近些年来也有许多的算法应用到任务规划中，比如：蚁群算法[1]、A*算法[2]、文化算法[4] 、遗传算法[5]等。这些算法在场景全部为正确信息或者人机交互结果全为正确位置结果时，使用起来效果较好，这些算法对任务进行规划，可以很好地完成任务并且损耗比较小。但是现在存在的问题是：在中国科学技术大学举办的家庭仿真机器人比赛中，第二阶段的比赛场景不仅有错误信息而且人机交互返回的结果也不一定正确，这样在使用上面的算法就会出现严重的错误。因为在上面的算法中，对动作结点进行规划时需要的信息是正确的，这样就会出错。

本文主要研究家庭仿真机器人比赛的第二阶段的任务规划，与第一阶段不同的是在这个阶段中所给的场景信息有可能出错;以及人机交互中的询问（askloc）有60%返回正确位置关系，30%返回错误位置关系，10%返回“not_know”。在这篇文章中，提出的线性规划就可以很好地解决这个问题。通过对任务类型进行线性排序然后在逐一完成，再根据每个任务中的具体场景进行规划，可以很好地解决这个问题。

1 家庭仿真机器人比赛

家庭仿真机器人比赛简单说就是一个虚拟3D机器人在一个模拟环境下完成一些任务。完成任务需要做的动作有九个原子动作：move、pickup、putdown、toplate、fromplate、open、close、putin、takeout。机器人的设定为一只手一个盘子，手和盘子上只能放入一个小物体。

2 任务描述

在家庭仿真比赛中，任务种类有多种：give（human，A）、puton（A，B）、goto（A） 、putdown（A）、pickup（A）、open（A）、putin（A，B） 、close（A） 、takeout（A，B）。在任务种类中B表示大物体A表示小物体，机器人通过拿起小物体完成相应的任务要求获得分数。在任务信息中不仅有任务信息，还有约束信息：not task，not info，not not info，维护约束是非常必要的。

本人主要研究这9中任务，使用线性规划的方法规划完成场景中的任务。任务的具体描述如下：1. give（human，A）是将小物体A移动到human的位置2. puton（A，B）将小物体A放到大物体B的位置3. goto（A） 是机器人移动到小物体A的位置4.putdown（A）将机器人手中或者盘子中的物体A放下5.pickup（A）使机器人拿起小物体A放在手中或者盘子中6.open（A）将容器A的门打开7.putin（A，B） 将小物体A放入容器B内部8.close（A） 将容器A的门关闭9.takeout（A，B）将小物体A从容器B中拿出。完成这写种类任务，不能在场景结束之后的最终状态破坏（就是物体最终状态与任务描述相同），否则相当于没有完成。在每个场景中，这9种任务含有其中的一部分或者全部，并且每种的任务数量可能不唯一，比如：

3 任务规划

3.1 任务优先级调整

有许多算法可以完成多任务，比如：A*算法、进化算法、ASP、文化算法等。这里主要针对家庭仿真机器人比赛的第二阶段，在场景信息中存在错误信息和缺失信息，以及人机交互时返回的信息并不全是正确位置信息，所以使用这些算法可能会出现许多异常问题。为了避免错误信息带来困扰，提出一个算法：线性规划，也就是将多个任务进行逐一完成，采取分而治之的方法。

将任务逐一完成虽然简单，但是依然存在问题，比如：1. close（A） 2.putin（B，A）。在执行任务1之后，再执行任务2，任务2完成之后就默认这个场景的所有任务已经完成，继续执行下一个场景，这样就将任务1的场景破坏，在进行评分时就会判定任务1没有完成。不仅仅没有完成任务，而且执行了一系列动作，消耗了時间，带来的损失较大。

为此，我们对任务优先级进行排序，尽量避免上述存在的问题。但是如何进行排序呢？需要明确在任务描述中存在的任务信息种类：task、info、cons。

在任务处理中info中的信息是对场景信息的补充，需要进行优先处理，因为在以后的任务中可能会需要到这些信息，所以将info类优先等级设置为第一等级。

在cons中，可能约束信息会和任务发生冲突，如1.not info|A on B 2.task|put A on B，这时如果以cons为主，经过计算虽然完成任务比约束多20分，但是减去原子动作、时间消耗、人机交互会损失更多的分数，所以将cons设为第二等级。

接下来是task信息，这里也是最重要的部分，任务的种类如下：give（human，A）， puton（A， B），goto（A）， putdown（A）， pickup（A）， open（A）， putin（A， B）， close（A）， takeout（A， B）。将这些任务类型进行优先级排序，显而易见goto任务需要排在最后一个，优先级为9，如果将这个任务排在前面，在完成其他任务时，会破坏这个任务的完成情况，所以goto优先级必须为9;在执行任务之前首先需要处理机器人手中的物体（除非手中的物体和此任务直接相关），处理手中物体动作为putdown|toplate，所以处理手中的物体是完成每个任务的第一步，因此将putdown任务等级设为1，pickup任务等级设为8;可以将give（human，A）和puton进行合并，二者的任务类型非常相似，puton使用的物体可能存在某个大物体内部，完成takeout、putin、open之后可以将门打开比较方便（确保门的确是打开的，不用进行判断），close可能会阻碍takeout、putin、open、give、puton完成，因此close优先级设为7，puton、give分别为5、6（顺序可以交换）;如果open任务和putin任务发生了关联（即open（B），putin（A，B）），由于open完成一般需要move、open两个动作putin完成一般需要move、pickup、move、putdown、open、pickup、putin，如果执行顺序为open、putin需要：move、open、move、pickup、move、putin，动作损耗为：18分，需6个原子动作，如果执行顺序是putin、open：move、pickup、move、putdown、open、pickup、putin，动作损耗为：18分，需7个原子动作，这样时间损耗就会少一些，takeout任务和putin任务是两个相反的，二者比较相似，所以open优先级为2;如果takeout任务和putin任务有联系（如：takeout（A，B）和putin（C，B）），执行顺序为takeout，putin需要动作：move，open，takeout，putdown，move，pickup，move，putin，动作损耗：22分，需8个原子动作，执行顺序为putin ，takeout需要动作：move，pickup，move，putdown，open，pickup，putin，takeout，动作损耗：20分，需8个原子动作，如果没有联系二者近似等价所以takeout为3，putin为4。

根据上面的分析可以很清楚地得出结果，优先级顺序可以设置为：putdown->open->putin->takeout->puton->give->close->pickup->goto.如果同一种任务出现多次，可以按照出现顺序来排序同一种任务。上面分析所得结果中，优先值越大执行越靠后。

将任务优先级调整之前与调整之后对比，拿2018安徽省省赛题目做对比，调整之前得分为7994;调整之后得分为8862。这之间的差距非常明显，可以充分展示出进行优先级调整之后的作用。

3.2 错误信息纠正

在任务线性规划之后，需要逐一完成。做任务时可能会遇到场景信息出错的情况，这就需要进行人机交互以纠正错误信息。

3.2.1 多次询问

在调用askloc接口询问信息时，60%返回正确位置信息，30%返回错误位置信息，10%返回“不知道”，可以简单调整为：60%返回正确位置信息，40%返回错误位置信息。

根据伯努利概率方程：

通过多次询问将返回的结果存储并比较，如果有两次或者两次以上结果相同，就默认这个结果为正确位置信息。

3.2.2 移动感知

这种方法类似于暴力破解，通过一直调用move、sence来一直感知，通过判断sence返回的正确信息中是否有任务需要的信息，若有，执行任务;否则，继续调用move、sence获得信息直到获得正确的位置信息。该方法简单而且可以帮助我们准确的获得全部信息，可以更好地完成任务。但是带来的损耗也是无法承受的。该方法纠正错误场景信息需要调用大量move、sence方法，这两种方法会消耗较长时间，如果一个场景文件存在的错误信息较多将会消耗较多的时间。然而比赛规定一个场景运行时间不超过5s，因此该方法可能会超时如果规定一个场景为5s，这样的方法在未完成任务的情况下就已经超时，所以不建议采用这种方法。

3.2.3 混合方法

将上述两种方法进行结合，通过进行询问，并对询问的结果进行移动感知，判定场景信息正确与否。即每次询问之后调用move和sence接口判断返回结果是否正确（这两个方法损耗比较小）。

根据伯努利概率方程，可知询问三次大概率（90%以上）可以得到正确的结果。可以设置处理一个错误信息时最多询问三次（可以根据自己的需要调整），如果三次没有得到正确结果，放弃这個任务。

4 细节部分

4.1 分支结构优化

家庭仿真机器人比赛的代码量较大（我的代码大概有5000行），在场景信息处理、任务信息处理和其他部分会使用到大量条件语句if{}else if{}…else{}这个分支结构虽然简单，但是相对效率较低，更替为switch case语句可以节约很多时间（大概一个场景可以节约0.3s），获得更高的分数。

4.2 pickup任务量大于一经过大量数据测试以及对比一些参赛队伍的log文件发现，当一个场景出现多个pickup任务时，许多队伍将会出错。大多是由于潜意识认为一个场景中指挥出现一个pickup任务，这样在处理时将会出现错误。

4.3 close、open任务处理

在3.1中，我们将close、open任务的优先级设为7，这个优先级比较低，基本上在一个场景中是最后一个任务或者倒数第二个。

在处理任务信息时，可以将close、open任务的目标放入集合中，每当移动到大物体旁时，可以判断这个大物体是否在集合中，如果在集合中在移走之前关闭一下，这样就可以节约一些不必要的损耗。以colse为例：

如果按照固定的优先级，执行完putin任务之后，移动到另一个位置执行另一个任务。然后在移动到2位置执行close在无形中多移动了一次，无论在动作损耗还是时间损耗上都增加了，而就这个整个场景而言损失了3分。

5 总结

在本文中，首先給出了一些应用在家庭仿真机器人中的算法，但是在家庭仿真机器人比赛中第二阶段存在错误场景信息使得这些算法难以实现且效果不理想，为了解决这个问题提出了线性规划。线性规划只需要根据任务类型对任务进行优先级排序，然后逐一完成，这样可以避免错误信息给任务执行时带来的困扰。对任务进行优先级排序之后，对场景中的任务按照优先顺序逐一完成，不仅可以避免破坏已经完成的任务，还可以为后面的任务坐下铺垫。但是在使用线性规划时，也不能完全按照这种优先级顺序，有时需要根据具体情况具体分析，这样可以更好的完成任务规划。

在任务规划之后，更需要注意的是细节部分，这些不仅影响一个场景对整个比赛的过程都有很大的影响，比如close和open类型的任务，这种任务可以用于贯穿全局完成，如果在完成其余任务之时能完成，这样最好，如果不能完成也没有任何损失。类似问题仍然存在，可以经过大量实验发现这些问题，在进行改良会取得较好效果。

经过线性规划实现算法之后，需要经过调试，以及大量数据测试，不断发现问题并进行解决才能有更好的效果。个人觉得半人工半智能的方法是非常有效的，希望经过不断地测试、调整之后使得家庭服务机器人更加智能。

参考文献：

[1]余伶俐，蔡自兴，刘晓莹，高平安.均分点蚁群算法在群集机器人任务规划中的应用与研究[J].高技术通讯.2009， 19（10）： 1054-1060.

[2]乔文莉，陈万米.基于A*算法的家庭服务机器人仿真设计[J].工业控制计算机. 2004， 27（04）： 128-129.

[3] 章伟，蔡亚楠，杨为民. 基于任务规划的家庭仿真服务机器人的研究[J].电脑知识与技术.2016，12（17）：188-191.

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

[5]周友行，何清华，谢习华. 基于遗传算法的凿岩机器人孔序规划[J].机器人.2002，24（1）： 62-65.

[6] 范佳， 钱徽，朱淼良， 陈武斌. 优化路径分配的多作业机器人任务规划[J]. 计算机工程.2010， 36（23）： 142-145.

[7] 余伶俐 焦继乐 蔡自兴. 一种多机器人任务规划算法及其系统实现[J].计算机科学.2010， 37（6）：252-255.

【通联编辑：梁书】