E-R模型的回答集编程表示

作为一种广为接受的语义数据模型,E-R模型被广泛地应用于数据库设计阶段.但是E-R模型自身却存在某些缺陷,这些缺陷制约了对其进一步的应用.针对E-R模型的改进,目前主要存在基于图形表示和描述性逻辑表示两种途径.但是,前者仍然不具有自动推理能力,而后者却存在表示能力弱、与数据库兼容性不足等缺陷.为克服以上缺陷,提出一种利用回答集编程(answer set programming)表示E-R模型的新方法.首先,对应于数据库的E-R模式被区分为基本和扩展两种类型,并分别完成它们的语法与语义定义.其次,利用回答集编程完成以上两类模式的逻辑编程表示.最后,完成表示的正确性证明.提出的方法不仅为E-R模型提供了一种新的逻辑表示途径,而且相对原有的两种E-R模型改进途径具有明显的优势.更为重要的是该研究成果使得应用E-R模型实现异构数据库之间的语义协作成为可能.

基于回答集编程的UML模型不一致性修正

为支持大规模工业应用的设计,研究统一建模语言(UML)中的不一致性修正问题,提出基于回答集编程的修正方法,处理类图和序列图之间的不一致性。采用逻辑程序表示UML图和固有约束规则,借助推理机求解得到回答集,该回答集能使UML图保持一致性,实例验证了该方法的有效性。

基于回答集编程的Banks选举求解方法

采用启发式算法的Banks选举在进行求解时执行效率较低。为解决该问题,提出一种基于回答集编程(ASP)的求解方法。通过建立Banks选举问题到ASP问题的映射,编写相对应的ASP,调用回答集求解器进行求解,得到的每一个ASP模型就是Banks选举问题的一个解。实验结果表明,当问题规模为200时,该方法的求解时间为4.196 s,求解效率高于手工启发式方法。

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

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

一个带破圈启发方法的回答集编程系统(英文)

回答集编程(answer set programming,ASP)是一种回答集语义下的逻辑编程范例,可应用于非单调推理,叙述式问题求解等领域.本文为ASP提出并实现了一种破圈启发方法与一种基部限制式前向搜索过程,所得到的系统称为LPS.实验结果显示,相对于其他经典的ASP系统,LPS能够有效地解决处于相变难区域中的逻辑程序,通常这些程序被认为是计算困难的.除此以外,通过使用被称为动态变元过滤(dynamic variable filtering,DVF)的技术,LPS可以在计算过程中极大地缩小搜索树的尺寸.

回答集编程在RoboCup中型组的应用

在RoboCup MSL足球机器人中,教练机程序负责对机器人的单机任务和机器人之间的协作进行规划。在多机协作的过程中,由教练机导致的机器人之间的协作冲突会导致任务的失败。如何消解教练机中存在的冲突问题成为中型组研究的一个重点。回答集编程(ASP)作为逻辑编程的一种,近年来逐渐在RoboCup家庭组中得到应用。通过将ASP引入到中型组,某些特定情况下的协作冲突被有效消解,并且通过Matlab仿真,将原程序所产生的结果与ASP方法产生的结果进行比对,可以看到冲突被有效解决。

从经典逻辑知识构建ASP知识库的新方法

回答集程序设计(ASP)是一种主流的非单调知识表示工具。为了能够在利用ASP求解问题过程中使用现有的以经典逻辑表示的知识,给出了一种把以谓词逻辑公式表示的约束型知识和定义型知识转化为ASP程序或知识库的新方法,并以实例说明了其有效性。该方法满足转化后ASP程序的回答集与原公式集的模型具有一一对应关系。在实际应用中,该方法提供了一项从现存的以谓词逻辑为表示语言的知识库,构建以ASP为知识表示语言的非单调知识库的技术。

基于ASP的CSP并发系统验证研究

传统并发通信顺序进程(CSP)性质的验证通常使用3个不同的模型层面,从而增加了系统的复杂性和验证工具开发的难度;同时,主流的并发系统模型验证工具不支持在系统的一次运行中验证多个性质,这也降低了性质验证的效率。首先将CSP程序转换为ASP程序,然后将CSP进程并发规则和以LTL/CTL公式表示的待验证性质转换为ASP规则,从而建立了基于ASP验证CSP并发系统性质的统一框架。实验结果表明,基于ASP的CSP并发系统验证技术易于实现,在保持较高验证效率的同时,能够支持在验证软件的一次执行中验证多条LTL/CTL公式。

基于ASP的CSP模型验证性质反例生成技术研究

为了解决当前通信顺序进程(CSP)模型检测不支持在验证工具的一次运行中验证多个性质的问题,建立了基于ASP的CSP并发模型验证框架。主要研究在该框架下当待验证的系统性质不满足时生成相应性质反例的技术。把ASP程序调试中的ASP程序支撑原因分析技术应用于该问题的研究,提出了相应的反例生成算法,实例表明了该算法的正确性。

基于ASP的程序切片

针对程序切片在程序理解和程序测试方面的应用,提出了一种基于ASP的程序切片方法。ASP是一种声明性问题解决方法,它可以高效地描述程序切片问题。基于ASP的切片方法,可以把切片的查找转化为回答集的求解。另外,对传统数据流切片算法进行了改进;改进后的算法可以减少重复计算,提高了运行效率。通过实验表明了此改进法的正确性和高效性;并且比较了3种ASP求解器(DLV、Smodels、Cmodels)的执行效率,基于Cmod-els的改进算法的运行效率是最高的。

基于ASP逻辑的偏好多语境系统

多语境系统(MCS)是对分布式系统(如多知识库系统)的一种形式刻画。在现有MCS的基础上,一方面提出一种基于ASP(回答集编程)逻辑的偏好多语境系统PMCS;另一方面,利用其偏好语义实现MCS的桥规则的删除功能,以及使用偏好桥规则处理MCS的不一致性问题。

基于启发式搜索的ASP程序支撑原因分析算法

为了尽快找到一个错误及其来源,以加快ASP程序调试的效率,把启发式搜索技术引入ASP程序支撑原因分析算法。在生成支撑原因分析图时利用启发式函数,仅搜索对回答集产生影响且有可能更快找到一个支撑原因的规则。改进算法在搜索关于某个回答集的支撑原因时,其时间和空间复杂度明显下降。实例分析表明了该算法的有效性。

基于进程迹的CSP模型验证框架

CSP(Communicating Sequential Processes)是构建并发系统和网络安全协议的经典方法。当前主流的CSP模型验证方法需将进程转化为迁移系统,转化过程比较复杂;性质采用迹进行规范,不利于活性的描述。提出了一种基于进程迹的CSP模型验证框架,其性质采用通用的规范方法LTL进行描述。利用ASP(Answer Set Programming)技术实现了一个CSP验证系统。实验表明,与类似系统相比,该系统的描述能力更强,验证结果的准确性更高,在性质不满足时还可提供反例。

家庭仿真求解最优路径问题算法研究

家庭仿真项目是全国机器人大赛的新兴项目,侧重对服务机器人在执行任务中自动规划、自然语言解析、自动判断及推理等认知能力考查,通过对在该仿真项目中应用比较广泛的最优策略算法以及回答集编程(Answer Set Programming,ASP)进行综述和比较,总结了当前关于回答集编程在提高求解效率方面的改进方法。

目的地选择服务系统中的智能逻辑推理

针对当前目的地选择服务系统机械片面地理解用户的查询请求,提出了采用回答集(ASP)逻辑推理的方式,综合运用旅游常知、情景信息和用户信息处理用户的查询请求,使查询结果在精度上有了很大的提高.同时对现有的一个ASP推理引擎进行了改进,使其能实现非确定性推理,并应用于目的地选择服务系统中.

实现家庭服务机器人中文指令解析问题研究

为了实现家庭服务机器人在无人干预的情况下自主地执行中文指令中蕴涵的服务任务,提出一种基于回答集的中文指令任务规划方法,将组块标注和回答集编程(answer set programming,ASP)应用于家庭服务机器人任务规划。通过组块标注对中文指令进行预处理,根据转换规则将关键信息转换为谓词集,并将它转换成ASP规则,给出中文服务指令处理的各个环节的实验结果,并结合实例展示从谓词集到机器人可以执行的动作序列的映射过程。最后,通过合并部分原子动作的方式对回答集进行改进,提高了求解效率,并在任务规划时加入了成本规划,确认求得最优动作序列。该方法对促进自然人—机器人交互技术的发展具有重要的意义。

服务机器人自然语言处理的研究与应用

目的:以服务机器人的自然语言处理为目标,主要研究场景信息分析、自然语言任务信息理解等问题,最终求解出机器人的最优动作序列。方法:使用关键字搜索算法处理自然语言,通过格式化处理、分组标记和谓词转换等技术处理为特定格式的指令语言,之后使用回答集编程(Answer Set Programming,ASP)技术对指令语言任务信息进行规划,求解出最佳的机器人动作序列,并改进ASP在自然语言任务规划中的性能。结果:通过试验验证关键词搜索算法,在自然语言任务处理中较简单处理方式,有明显的性能提高。结论:关键字搜索算法能很好的完成自然语言处理任务,并可提高任务规划的性能,以及提升服务机器人自然语言处理的整体效率。