王 凡，范文斌，张雪艳，郭玉堂，刘乐群

（合肥师范学院 计算机科学与技术系，安徽 合肥 230601）

提高回答集编程在家庭机器人仿真上求解效率初探

王 凡，范文斌，张雪艳，郭玉堂，刘乐群

（合肥师范学院 计算机科学与技术系，安徽 合肥 230601）

家庭机器人仿真比赛是由中科大发起的一项基于简单机器人模型在一定范围内实现任务规划的比赛.Answer Set Programm ing（回答集编程）是一种非单调逻辑编程技术，是在融合逻辑编程理论基础上发展而来的.独创性的提出合并关联原子动作来提高回答集编程的求解效率，并在家庭机器人仿真比赛中实现较高效率的自动规划.

回答集编程；家庭机器人；行动规划；逻辑推理

家庭机器人是在家庭环境下为为人类服务的一种机器人，能够代替人类完成家庭中的各种繁重且重复的工作[1,2].家庭机器人仿真比赛是一项关于家庭机器人如何对给定的一系列任务进行合理的规划的问题的比赛，服务器会给出一组场景信息和任务信息，通过程序在规定的时间内能算出一套最佳的动作序列，服务器对给出的动作序列进行鉴定模拟，计算成绩[3].

回答集编程（Answer Set Programming）技术是近年来比较流行的解决人工智能问题的一种非单调推理编程技术，已成为很多的研究者用于非单调推理的知识表示和推理的工具，经过研究者们多年的工作积累，回答集编程理论方面己相对成熟，但是，其常例化穷举的本质使得其求解器的效率不是很高，影响其广泛应用[4].

本文就回答集编程效率不高的现状，提出了利用合并关联原子动作的方法来提高回答集编程的求解效率，并用编写相应代码实现，最后设置一组对照实验证明其正确性与实用性.

1 简介

1.1 Answer Set Programming

1.1.1 ASP基础

在经典逻辑中，我们经常考虑这样一个推理：从前提“所有的人都是有死的”和“苏格拉底是人”推出结论“苏格拉底是有死的”.这样的推理我们称为演绎推理，然而在人们日常的推理中，给出的信息往往是不完全的，所以推理出的结论往往是可错的，比如我们通常认为“鸟会飞”，知道“twweety是一直鸟”的话就会推出结论“tweety会飞”.可是一旦我们增加前提“tweety是一只鸵鸟”，我们知道通常“鸵鸟是不会飞的”，则之前的结论“tweety会飞”就不合理了，即增加了前提使原先推出的结论推不出，也就是说，这样的推理不具有单调性，我们称这种性质为非单调性，称这样的推理为非单调推理[5].

回答集编程（ASP）是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程[5].逻辑程序和非单调推理两个领域的交叉融合促使了回答集编程研究的产生.

1.1.2 ASP求解

ASP求解问题，只需要将问题本身描述出来，不需要关心使用何种算法，即先构造问题的可能解，在刻画约束解的条件，对问题表达为通用的问题描述部分和问题实例，这样同一段问题描述的代码可以处理不同的问题实例[4].ASP的求解过程分两个步骤：

常例化（Grounding）：原始程序中可能含有变量或其他语法缩写，将其常例化为仅含常规则的程序，并且解释翻译相应的语法缩写.

模型搜索（计算回答集）：计算常例化以后程序的回答集，一般采用搜索方式.

1.2 家庭机器人仿真比赛

家庭机器人仿真比赛针对自主机器人在家庭环境中的基本应用来设置一系列问题，每一个问题由一个场景描述和一个任务描述组成，其中场景描述确定家庭环境的初始状态，代表机器人通过感知器获得的家庭环境信息；任务描述包含了用户下达任务的详细信息，代表用户通过人机对话向机器人传递的各种信息[6].

1.2.1 原子动作

机器人原子动作，体现机器人的基本行动能力，是仿真平台对机器人底层功能的抽象，机器人为原子动作的主体[3].规定，机器人只能根据这些原子动作来改变场景.

1.2.2 场景描述

场景描述是家庭机器人仿真平台虚拟的一套环境，规定了在一个房间内，某个位置拥有某个物体，例如：table(4).location(4,108).表示物体table的编号为4号，其位置为108.场景描述就是机器人在规划前房间的初始状态.

1.2.3 任务描述

任务描述包括三个方面，第一为机器人需要完成的任务集，例如：puton(book,desk).give(human,blue book).表示机器人需要将一本书放在桌子上并且还要给人一本蓝色的书；第二为对场景的补充，例如：near(yellow book,red cup).表示黄色的书在红色的杯子边上；第三为约束信息，例如：not onplate(red cup).表示机器人无论如何都不能将红色的杯子放在盘子里.

2 ASP在家庭机器人仿真上的应用

使用ASP编程来实现家庭仿真机器人行动序列的自动规划，首先应该对平台给出的场景信息进行解析存储，然后对平台给出的任务描述进行解析，任务部分分为三大块，分别为：任务、补充信息和约束，接下来将场景信息和任务描述进行ASP常例化，最后用ASP进行求解，流程图如图1：

利用ASP编程来实现家庭机器人仿真行动序列的自动规划其核心就是如何使用回答集编程规则对问题进行描述、对行为进行描述的问题.下面将从这两个方面进行阐述.

图1 用ASP求解家庭仿真流程图

2.1 问题描述

在家庭仿真中，需要描述各物体及机器人的初始状态和目标状态，将其转化为ASP编码，下面是对场景进行初始化的回答集编程：

obj(A):-location(A,X).

loc(X):-location(A,X).

mylocation(A,X,0):-location(A,X).

hasloc(A):-location(A,X).

myplate(A,0):-plate(A),loc(X),obj(A).

myhold(A,0):-hold(A),loc(X),obj(A).

2.2 行为描述

在行为描述阶段也要定义相关谓词来表示机器人的原子行为以及相应的动作序列，下面是机器人执行动作open（A）的回答集编程：

mydooropen(A,t):-occurs(open(A),t),bigobject (A).

:-occurs(open(A),t),not myhold(0,t-1), bigobject(A).

:-occurs(open(A),t),not mydoorclosed(A, t-1),bigobject(A).

3 利用合并关联原子动作提高ASP求解效率

3.1 ASP求解算法

ASP求解的过程就是常例化穷举的过程，图2描述一个典型的ASP求解空间树，图中0表示初始状态，1表示动作move（X），2表示动作pickup（A），3表示动作open（A），4表示动作putdon（A），则若使用ASP求解，则必须将所有叶节点进行扫描，从而找出最优序列，其时间复杂度为O（2n），很显然，ASP的求解效率不是很高[8].

图2 ASP求解空间树

3.2 改进的ASP求解算法

为了提高ASP求解效率，可以将机器人的原子动作中相关联的某些原子动作进行合并，以减少求解器的搜索树空间.例如：家庭机器人仿真比赛的规则中指出，对于任务putin（A，B）规定，机器人必须将小物体A放入到带有门的大物体B中，并且B的门必须是关着的[3]，由此可知，机器人要想将A物体放入到B物体中，就必须执行putin（A，B），但又根据B物体的门必须是关着的，所以，机器人又必须执行close（B），并且根据经验得知，机器人执行完putin（A，B）后往往都要执行close（B），所以就将这两个原子动作复合为一个动作piclo（A），相应的ASP编程如下：

action(piclo(A),t):-action(putin(A,X),t),action (close(X),t+1).

同理也可以将move（X）和pickup（A）复合为动作mtop（A）等，部分复合动作的ASP编程如下：

action(mtop(A),t):-action(move(X),t),action (pickup(A),t+1).

action(mfrp(A),t):-action(move(X),t),action (fromplate(A),t+1).

通过将合并关联原子动作，可以将ASP的搜索空间树进行大量剪枝，使其时间复杂度下降20-30个百分点，大大提高了ASP的求解效率.

4 实验分析

为了测试改进后的ASP求解的效果，设置一组对照实验，实验选取2012年中国服务机器人大赛的家庭仿真组比赛平台（Planner-1.30）和测试题目（从中选取2个环境场景，对每个场景随机选取2组任务）进行测试（平台服务器会根据规划器的动作序列综合考虑为每组测试题计算出最后得分）[7].A组实验为基于简单策略求解，B组实验为未经处理的ASP求解，C组试验为合并原子动作后ASP求解.

实验结果如表1所示：

表1 对比实验结果表

通过表4，可以看到，基于简单ASP的求解在时间上要高于基于简单策略的求解，即简单ASP的效率要比简单策略低，但是基于ASP求解最后的得分要远远大于基于简单策略的求解；同时也可以看到，C组在规定的时间内能完成的任务要多于B组且C组的求解效率要远远高于B组的求解效率，这证明，采用合并关联原子动作的方法确实能提高ASP的求解效率.

5 结束语

实验证明，ASP能规划出家庭仿真机器人最优的行动序列，同时也证明了我们提出的合并关联原子动作的方法能有效提高ASP的求解效率.ASP方式灵活、方法可靠、程序可扩展性好，当场景中物品描述形式或机器人原子动作有所变化，只用相应地修改ASP规则即可.虽然其常列化穷举的本质严重制约了其求解效率[6]，但是在合并了关联原子动作后，ASP求解成功率在可接受的响应时间内提高13-17个百分点.但是，目前还无法从本质上解决其效率低的问题，所以，未来的主要方向是如何尽可能的提高ASP求解效率.

〔1〕田国会,李晓磊,赵守鹏,路飞.家庭服务机器人智能空间技术研究与进展[J].山东大学学报(工学版),2007,37(5):53-59.

〔2〕田国会.家庭服务机器人研究前景广阔[J].国际学术动态,2007（1）:28-29.

〔3〕@HomeSimulation.USTC[EB/OL].http://www. w righteagle.org/homesimulation.[2012-4-23].

〔4〕Apt K,Bol R.Logic programm ing and negation: A survey[J].The Journal of Logic Programming, 1994,19/20:9-71.

〔5〕ZHENG X G J.Multi-agent based hybrid evolutionary algo-rithm [J].Natural Computation, 2011(2):1106-1110.

〔6〕吉建民,陈小平.一种支持个性化协调的服务机器人体系结构[J].南京大学学报（自然科学版）, 2010,46(2):131-139.

〔7〕Pedro Cabalar,Paolo Ferraris.Propositional theories are strongly equivalent to logic programs[J]. Theory and Practice of Logic Programming, 2007,6:745-759.

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

TP181

A

1673-260X（2014）03-0019-03

安徽省高校自然科学研究重点项目（KJ2013A217），合肥师范学院2013本科教学质量提升计划（2013zyzh01），国家级大学生创新创业训练项目（201314098016）