论文部分内容阅读
随着理论方面的成熟和相对高效求解器的出现,越来越多的研究者将回答集编程(ASP)作为具有非单调推理能力的知识表示和推理的一般工具,并将其应用到很多领域。但其效率仍然是影响推广的一个主要瓶颈,相关应用也需要进一步推广。这两者相辅相成,一方面,求解效率的提高推动更多应用,另一方面,具体的应用对效率工作提供实际需求。本文从程序结论(在所有回答集中都为真的公式)的角度出发,给出提高回答集编程求解效率的一些途径,并在服务机器人中应用回答集编程,用其实现服务机器人中自动规划、自然语言理解、自动诊断等认知能力。我们已经在科大“可佳”家庭服务机器人中实现相应系统,通过系列化的典型任务测试“可佳”的功能,并且设计了一个仿真测试,对服务机器人中的智能问题求解进行系统性的测试。论文主要工作包括三个方面:基于程序结论提高回答集编程求解效率的一些途径,应用回答集编程实现服务机器人中自动规划、自然语言理解、自动诊断等认知能力,系统性能测试及结果。本文提高回答集编程求解效率的基本思路是,通过计算更多的程序结论并且更有效的使用这些结论来帮助程序求解器更高效的计算。基于此思路,文中给出下面三种途径:首先,利用程序中最多只有一个外在支持规则的环的环公式和程序补全,基于unit propagation计算程序的结论。我们发现,最多只有一个外在支持规则的环的环公式等价于一元或二元子句的集合,并且对于普通逻辑程序,这些环公式可以在多项式时间计算出来,对于析取逻辑程序,可以找到一个多项式时间近似算法计算这些环公式。我们讨论了计算出的结论与普通和析取逻辑程序中良序模型和其他相关工作的关系,并且通过实验说明,对于一些逻辑程序,这些额外的结论可以明显提高求解器的效率。其次,给出刻画析取逻辑程序良序模型语义的一个一般框架,并讨论在此框架基础上计算析取程序的结论。此框架将良序模型刻画为一个基于GL-转换和结论形式的操作的极小不动点,其中GL-转换的形式和结论形式都可以有不同选择。我们证明现有析取程序上定义良序模型的主要工作都可以在此框架下等价刻画,并且基于此框架,我们可以刻画能在多项式时间计算出的析取程序结论。最后,介绍多种利用程序结论化简逻辑程序的方式,并且给出化简后程序与原程序等价(具有相同回答集)的条件。良序模型通常被用来化简程序,但其他程序结论不一定能按良序模型的方式被用来等价化简,这里我们明确了它们能被用来等价化简的条件。服务机器人由于其良好的应用前景受到广泛关注。服务机器人需要在复杂环境下完成复杂目标,从而对其认知能力有较高要求,但目前机器人认知能力还是一个研究难点。本文利用回答集编程来设计和实现服务机器人中自动规划、自然语言理解、自动诊断等认知能力。首先,利用回答集编程实现机器人自动规划的能力,将机器人面临的规划任务转换为相应回答集程序的求解问题。其次,利用回答集编程实现机器人对一些自然语言的理解,用户通过自然语言告知机器人任务,相关信息和因果知识,这些语句通过惰性语义分析转换为相应谓词的集合,接着根据这些谓词集合,将任务转换为回答集程序中目标并求解,将信息和因果知识转换为回答集编程规则并加入知识库。最后,利用回答集编程实现机器人的自动诊断能力。诊断程序可以通过修改规划程序得到,通过计算不正常部件最少的回答集给出系统的诊断结果。我们已经在中科大“可佳”家庭服务机器人上实现上述系统。为了测试系统功能并比较其性能,本文设计了一系列针对实体机器人的典型任务测试,同时也设计了一个仿真测试,系统性的测试服务机器人智能问题求解的性能。我们以此仿真测试作为一个开放性测试平台,比较“可佳”与其他工作性能的差别。最后,“可佳”完成了一系列测试,并且在仿真测试中表现优异,这些结果表明,回答集编程可以方便、有效的实现服务机器人中部分认知功能。本文主要贡献和创新有下面三点:第一,从程序结论的角度出发,本文提出三种提高回答集编程求解效率的途径。首先介绍如何计算程序的只有一个外在支持规则的环的环公式,证明相应计算结论与普通和析取逻辑程序中现有工作之间的关系,并通过实验说明,对于某些程序这里计算出的额外结论可以明显提高求解器的效率。其次,给出刻画析取逻辑程序良序模型语义的一般框架,证明现有析取程序上定义良序模型的主要工作都可以在此框架下等价刻画,并且基于此框架,刻画程序可计算的结论。最后,介绍多种利用程序结论化简逻辑程序的方式,并给出化简后程序与原程序等价的条件。第二,本文用回答集编程解决服务机器人中自动规划问题,并针对自然语言理解,提出一种将惰性语义分析的结果转化为相应回答集编程规则的方式。第三,本文实现“可佳”机器人中任务规划部件,使得“可佳”可以完成复合任务、因果推理等系列测试。并且设计了一个仿真测试,系统性的测试服务机器人智能问题求解的性能。目前还没有看到其他工作,对服务机器人中智能问题求解进行如此细致和系统性的测试。相比于其他工作,“可佳”在仿真测试中表现优异。这些典型任务测试和仿真测试的结果说明,回答集编程可以方便、有效的实现服务机器人中部分认知功能。针对回答集编程研究,本文提供若干提高回答集编程求解效率的途径,讨论回答集编程在实现服务机器人认知功能方面的应用。另一方面,本文在服务机器人方面的应用,为测试知识表示方面工作提供了一个良好平台。由于很多知识表示工作可以通过回答集编程实现,基于文中系统,相应成果可以较容易移植到服务机器人上,相应性能也可以通过服务机器人实际表现来测试。