回答集程序设计.ppt

1、回答集程序设计,华南师范大学07级研究生 吕勇全,主要内容,程序设计的一般步骤 常用前端和求解引擎 Lparse支持的语法形式 例子：家庭关系 例子：图着色问题 语法和语义的扩展 Grounding,例子：积木世界 例子：自动排课,基于回答集的问题求解一般步骤,1. 编写回答集程序 2. 给出与具体问题相关的基事实和常量的值 3. 调用回答集求解器求解 （3.1）程序的例化和化简(front end) （3.2）求解基程序的回答集,常用的回答集求解器前端和求解引擎,常用的前端： lparse, dlv-instantiate,gringo,plp,nlp等。 常用的求解引擎： Smodels,

2、 Cmodels, Assat, Clasp等。,lparse支持的语法形式（一）,常量(constant)：常量是指问题域中的某一个体，可以是数字或符号，一般以小写字母开头。 如： a, 10, foo, bar. 变量(Variable)：变量用来概括一类事情，在回答集程序中常通过求解来给变量赋予某一确定的值，变量一般用大写字母开头。 如：X， Foo, Bar. 原子(Atom)：原子由谓词符号后跟一串常量或变量的列表组成，常用来表达常量之间的关系。 如：parent(john,jill).,lparse支持的语法形式（二）,规则（Rule): 规则允许我们对谓词进行推理，如果规则体的原

3、子都为真，我们就能推出规则头的原子也必定为真。 sibling(X,Y):- parent(Z,X), parent(Z,Y). 事实（Fact）： female(joan). 约束（Constraint）：规则头为空的规则。 :- parent(Z,X), parent(X,Z).,例子：一个家庭关系的回答集程序,程序1： sibling(X,Y):- parent(Z,X),parent(Z,Y). mother(X,Y):- parent(X,Y), female(X). uncle(X,Y):- parent(Z,Y),sibling(Z,X),male(X). female(joan

4、). female(jill). male(jack). parent(joan,jack). parent(joan,jill).,例子：图着色问题,程序2： color(red).color(blue).color(yellow). col(X,red):- node(X), not col(X,blue), not col(X,yellow). col(X,blue):- node(X), not col(X,red), not col(X,yellow). col(X,yellow):- node(X), not col(X,blue), not col(X,red). :- edge

5、(X,Y), col(X,C), col(Y,C),color(C). node(a). node(b).node(c).node(d). edge(a,b).edge(b,c).edge(c,d).edge(d,a). hide. show col(X,Y).,语法和语义的扩展（一）,(1) 定义域谓词(domain predicate)：定义域谓词可以表示为color(1.k)的形式, 相当于color(1)，color(2)， color(k)。 在规则体中：b:- a(1.3) (2) Smodels中的选择规则（choice rule）：选择规则具有如下的两种形式：,语法和语义的扩展

6、（二）,（3）dlv中的弱约束（weak constraint）：dlv中的弱约束特征允许我们用一种更容易和自然的方式来一些优化问题。 程序3： a v b. c :- b. : a. : b. : c. 程序3在dlv上运行，所获得的最佳模型是a。但程序avb. c:-b.的回答集是a，b，c。,语法和语义的扩展（三）,（4）析取规则： 析取程序的回答集是规则体被满足时规则头的最小模型，规则（2）的回答集为：sun，light,语法和语义的扩展（四）,（5）经典否定(Classical Negation) （6）嵌套逻辑程序(Nested logic programs) 与下面的两条规则含意

7、相同：,Grounding（一）,A grounding transforms a normal logic program into an equivalent ground logic program where the equivalence is defined as having the same set of stable models. 程序4： man(a).man(b).man(c). male(X):- man(X),not female(X). female(X):- man(X),not male(X).,Grounding（二）,程序4做Grounding后得到程序5

8、 程序5： man(a).man(b).man(c). male(a):- man(a),not female(a). male(b):- man(b),not female(b). male(c):- man(c),not female(c). female(a):- man(a),not male(a). female(b):- man(b),not male(b). female(c):- man(c),not male(c).,例子：积木世界,constant： Lasttime:最大步数； grippers:机器手的数量； domain predicate: time(T):时间；

9、block(B)：积木； location(L)：位置； predicate： on(B,L,T):积木B在时间T的位置为L； move(B,L,T)：将积木B在时间T移动到位置L；,例子：积木世界,const grippers = 2 const lasttime = 3 time ( 0 . . lasttime ) . block ( 1 . . 6 ) . location (B) :- block(B) . location ( table ) . *初始状态 on ( 1 , 2 , 0 ) . on ( 2 , table , 0 ) . on ( 3 , 4 , 0 ) . o

10、n ( 4 , table , 0 ) . on ( 5 , 6 , 0 ) . on ( 6 , table , 0 ) . *目标状态 :- not on ( 3 , 2 , lasttime ) . :- not on ( 2 , 1 , lasttime ) . :- not on ( 1 , table , lasttime ) . :- not on ( 6 , 5 , lasttime ) . :- not on ( 5 , 4 , lasttime ) . :- not on ( 4 , table , lasttime ) .,积木世界（模型生成）,*生成动作 move (B

11、, L ,T) : block (B) : location (L) grippers:- time(T) , Tlasttime . *动作的效果 on(B, L ,T+1) :- move (B, L ,T)，block (B)，location (L )，time(T)，Tlasttime . *frame problem on (B, L ,T+1) :- on(B, L ,T) , not -on(B, L ,T+1) , location(L) , block(B) , t ime(T) , Tlasttime . 位置的唯一性 - on(B,L1,T) :- on(B, L ,T

12、)，L!=L1，block(B)，location(L)，location(L1), time(T).,积木世界（模型测试）,*两个积木不能在同一个积木上 :- 2on (B1 ,B,T) : block (B1 ) , block (B) , t ime(T) . *只有在积木上面为空时才能移动 :- move(B, L ,T)， on(B1,B,T), block(B), block(B1), location(L)，time(T), Tlasttime. *一个积木不能移动到另一个正在移动的积木上 :- move(B,B1,T), move(B1,L ,T), block(B), blo

13、ck(B1), location(L), t ime(T), Tlasttime. %运行命令： lparse true-negation block.lp block_world.lp|smodels,例子：自动排课,问题描述： 时间表问题（ Time Table Problems）是典型的组合优化和不确定调度问题，被证明为是NP完全问题 排课问题主要是利用有限的资源将每门课安排在何时、何地，并且教师、班级以及教室的安排不会发生冲突，同时又满足所有约束。 排课中面临的主要问题是约束条件复杂，条件不断变化,排课问题约束条件,基本硬约束(Basehard Constraints) B1 同一时间

14、同一教师不能给两门不同课程上课； B2 同一时间同一班级不能安排两门不同课程； 硬约束(Hard Constraints) H1 某些班级的某些课程可以先行手工安排时间点； H2 某些教师或班级在某个时间上可能不能够利用； H3 体育课安排在上午3一4节或者下午，体育课之后不安排课程，实验课、实习课等课程有自身的安排方式； H4 某一时间段不安排课程； H5 某课程连堂。 软约束(Soft Constraints) S1 班级课程表在星期上尽量分布均匀； S2 课表中的每个时间有一定优度； S3 主课尽量排上午，副课尽量排下午； S4 教师对上课时间存在一定的喜好；,排课问题的回答集程序表示（一）,事实： 班级：class(L) 教师 ：teacher(G) 课程 ：course(C)、course_teacher(C,G) 、course_class(C，L) 时间元 ：time(T) 排课系统首要的规则 ：,排课问题的回答集程序表示（二）,基本硬约束B1 ： 基本硬约束B2 ：,排课问题的回答集