Answer Set Programming 回答集编程

什么是ASP?

  ASP,全称 Answer Set Programming 中文名叫“回答集编程”。实验室学长要我学ASP的时候,我就去百度查了ASP,结果查到了都是这个:Active Server Page,意为“活动服务器网页”。我当时就在想:“这个不对啊,这个搞网站的,应该是旁边组系统集成组的事呀”。果然,此ASP非彼ASP。
  Answer Set Programming (ASP)提供了一种简单而强大的建模语言来解决组合问题。使用ASP,我们关注的方向就变成要解决的实际问题,而不是解决的方案。和C语言、python等语言有很大的不同,ASP是一种声明式编程,主要用于复杂的搜索问题。它基于逻辑编程的稳定模型语义。在ASP中,搜索问题被简化为计算稳定模型,并且问答集求解器(用于生成稳定模型的程序)用于执行搜索。许多问答集求解器的设计中使用的计算过程是DPLL算法的增强,并且从原理上讲,它总是终止(与Prolog查询评估不同,这可能导致无限循环))。从更一般的意义上讲,ASP包括对知识表示的回答集的所有应用程序,以及使用Prolog风格的查询评估来解决这些应用程序中出现的问题。

  Dimopoulos,Nebel和Köhler 在1993年提出的计划方法是回答集编程的早期示例。他们的方法基于计划和稳定模型之间的关系。Soininen和Niemelä 将现在称为回答集的编程应用于产品配置问题。Marek和Truszczyński在1999年和[Niemelä1999] 发表的关于逻辑编程范例25年的论文中,将答案集求解器用于搜索被确定为一种新的编程范例。的确,Lifschitz [8]在与Marek-Truszczynski论文相同的回顾性卷中首次提出了“答案集”而不是“稳定模型”的新术语。

基本语法

  一个简单的ASP程序包括三个部分:事实、规则、输出。事实和规则,用来描述问题;输出,用来查看结果。

一个简单例子
  现在有烟台,北京,青岛,济南,桂林5个城市,我们现在要坐火车在这4个城市之间穿梭,已知除了北京、桂林以外,其他三个城市之间都有直达的火车,而北京只有到济南的直达火车,桂林到哪个城市都没有直达的,那么从烟台出发,我都能到达哪些城市呢?

 

 

 

ASP代码如下
注:后缀名:.lp

% fact
%city(yantai,beijing,qingdao,jinan,guilin).
road(beijing,jinan).
road(jinan,yantai).
road(jinan,qingdao).
road(qingdao,yantai).
%rule
road(X,Y) :- road(Y,X).
road(X,Y) :- road(X,Z),road(Z,Y).
arrive(X) :- road(yantai,X).
% Displan
#show arrive/1.

事实和规则
  从上面的例子我们可以看出,一个ASP程序包括两个重要的部分:事实和规则。
事实:用于描述现实世界的状态。
规则:用于进行推理。
  ASP程序里还包括了常量(例子中的城市名);谓词(如road, arrive),每个谓词中有若干个参数,我们把带有n个参数的谓词p写作p/n;变量(例子中大写的X、Y),注意的是本质上ASP程序是不支持变量的,这里的变量仅仅是为了方便书写,在实际的求解中这些变量会被替换为程序中出现的所有常量。

符号作用
% 表示注释
. 语句结束
:- 左边为结论,右边为条件。条件成立,则结论为真。
, 表示并且
输出
符号作用
#show 表示输出,如:#show arrive/1. arrive表示规则里的arrive,/1表示里面的元素是1
例子拓展

  如果过了很多年,桂林到济南通了火车,济南到北京的道路在维修中,那现在的情况?

% fact
%city(yantai,beijing,qingdao,jinan,guilin).
road(beijing,jinan).
road(jinan,yantai).
road(jinan,qingdao).
road(qingdao,yantai).
road(guilin,jinan).
maintain(jinan,beijing).
%rule
road(X,Y) :- road(Y,X).
maintain(x,y) :- maintain(y,x).
route(X,Y) :- road(X,Y),not maintain(X,Y).
route(X,Y) :- route(X,Z),route(Z,Y).
arrive(yantai,X) :- route(yantai,X).
% Displan
#show arrive/2.

运行程序

  运行ASP之前先下载安装clingo,下载网址:https://github.com/potassco/clingo/releases/
本人使用的是Ubuntu系统,也可以使用以命令安装:sudo apt-get install gringo

  安装好clingo后直接使用clingo命令即可,如图:

 

 

 结尾

  关于ASP,国内的资源非常少。波茨坦大学有个专门关于ASP的网站:https://potassco.org。将来我将去里面挖掘一些干货。ASP到底能做什么?之前我一直纳闷,直到遇见了这篇论文:Task planning in robotics: an empirical comparison of PDDL- and ASP-based systems ,
讲的关于机器人任务规划,原来如此!好了,现在有了方向,从此学起ASP来,就不会这么迷茫。

热门相关:有个人爱你很久   继母和她的妹妹   豪门情变,渣总裁滚远点!   大妆   大妆