回答集程序设计_理论、方法、应用与研究

《回答集程序设计_理论、方法、应用与研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、回答集程序设计:理论、方法、应用与研究崔仲毅，程渤(北京邮电人学网络与交换技术国家重点实验室)摘要：冋答集程序设计(Answersetprogramming,ASP)是一种面向复杂搜索的声明型程序设计方法。ASP是综合非单调推理、演绎数据库和逻辑程序设计方法的一项研究成果，适合于解决知识密集型问题。ASP语法结构与Prolog类似，但其计算机制不同，主要借助于高效的命题逻辑可满足求解器进行计算。本文对ASP的语法、语义、程序设计方法以及应用分别进行了阐述。最后，对ASP的未来研究方向进行了讨论。关键词：回答集程序设计；声明型程序设计方法

2、；非单调推理中图分类号：请查阅《中国图书馆分类法》AnswerSetProgramming：Theories,Techniques,ApplicationsandResearchesZhaiZhongyi,ChengBo(StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTclccommunications)Abstract:Answersetprogramming(ASP)isaformofdeclarativeprogram

3、mingorientedtowardsdifficultsearchproblems.Asanoutgrowthofresearchonnonmonotonicreasoning,deductivedatabaseandlogicprogramming,itisparticularlyusefulinknowledgeintensiveapplications.ASPprogramsconsistofrulesthatlooklikePrologrules,butthecomputationalmechanismsofASParebas

4、edonfastsatisfiabilitysolversforpropositionallogic.Inthispaper,weintroducethesyntaxandsemanticofASPprograms,themethodfordevelopingASPprogramsandtheapplicationofASP・Finally,wediscussthefuturedirectionofASP・Keywords:Answersetprogramming;DeclarativeProgramming;NonmonotonicR

5、easoningo引言基于经典逻辑的程序设计语言对于实现智能化起到了基础性作用。但经典逻辑的推理方式是单调的，当加入新的知识时只能增添新的结论，而不能否定以前的结论。为了用机器模拟人类的智能化思维，非单调推理显得至关重要⑴。20世纪70年代提出了缺省逻辑(DefaultLogic)⑵、自认知逻辑(Auto-epistemicLogic)⑶、划分理论(Circumscription)^]等几种非单调推理方法，由于缺少高效的开发工具和不具备模块化程序设计，这儿种推理方法并没育得到广泛应用。Gclfond和LifschitzI*1988年提出

6、了—种稳定模型语义(StableModelScmantic)[5],其在非单调推理下成功地解释了失败即否定(NotasFailure)。以稳定模型为基础，90年代末形成了一种新的逻辑程序设计方法一冋答集程序设计方法[6.7.8.9]o目前，冋答集程序设计是知识表示的有效方法，并成为非单调推理和逻徘程序设计研究领域的热点问题。回答集程序设计的基本思想是：用一组逻辑程序來描述给定的问题，然后用ASP求解器计算出冋答集模型，得到的冋答集即问题的解决途径。此过程类似于命题可满足件判定过程，首先用命题理论把问题刻画出来，然后通过计算模块或推理模块

7、把一纽成真解释作为问题的解决方法。冋答集程序设计的语法结构与Prolog比较类似，但其计算机制与Prolog完基金项冃：教育部博士点基金(20100005120009)作者简介：翟仲毅(1986-),男，博士生，主耍研究方向：知识表示与推理、模型检测、Web服务组合通信联系人：程渤(1975・)，男，副教授，形式化技术、移动互联网与服务.chengbo@bupt.edu.cn全不同。Prolog的计算机制是从询问开始，经过一系列的消解，从而判断询问是否被满足［⑼。ASP则是根据稳定模型语义计算出一系列冋答集，这些冋答集即是满足程序的解⑴

8、。经过多次语法扩展，ASP已具有强大的描述能力⑴］。随看高效的ASP求解器的出现，ASP已在许多领域得到了的广泛应用，如规划［12.13J,航夭决策［】4］、模型检测卩5」6］等领域。ASP作为一种新型的程