2009-8-20 史忠植 高级人工智能 1
高级人工智能第三章 约束推理史忠植中国科学院计算技术所
2009-8-20 史忠植 高级人工智能 2
第三章 约束推理
3.1 概述
3.2 回溯法
3.3 约束传播
3.4 回跳法
3.5 约束推理系统 COPS
3.6 ILOG SOLVER
2009-8-20 史忠植 高级人工智能 3
3.1 概述
Over the years,the theory and application
of optimization has grown into an important
field of research,We can distinguish following
fields of research that pay attention to
optimization problem:
operations research
constraint program
genetic algorithm
neural network
2009-8-20 史忠植 高级人工智能 4
3.1 概述
Operations Research
Traditionally,a lot of the attention in
operations research has been paid to optimization
problems,particularly,planning,scheduling,
that are based on mathematical model,For solving
problems,one should write particular program in
terms of algorithm,When modeling a practical
scheduling problem using classical models,one
is often forced to discard many degrees of
freedom and side constraints,
2009-8-20 史忠植 高级人工智能 5
3.1 概述
Constraint Programming concerned with solving
instances of the constraint satisfaction problem,The
general Constraint Satisfaction Problem (CSP)
A set of n variables {x1,x2,…xn} with values
in the discrete,finite domains{D1,D2,…Dn},.
,{4,5,6,7}
,{red,green,blue}
A set of m constraints{c1,c2,…cm} which are
predicates c1{x1,x2,…xj} defined on the Cartesian
production D1xD2x…xDj,If is TRUE,
the valuation of the variables is said to be satisfied.
C1,color(wood,red)
C2,x y 16
2009-8-20 史忠植 高级人工智能 6
3.1 概述一个约束通常是指一个包含若干变量的关系表达式，
用以表示这些变量所必须满足的条件。约束表示广泛地应用于 AI 的各个领域，包括定性推理、基于模型的诊断、自然语言理解、景物分析、任务调度、系统配置、科学实验规划、机械与电子设备的设计与分析等。
2009-8-20 史忠植 高级人工智能 7
3.1 概述一个约束满足问题 (Constraint Satisfaction Problem,
简称 CSP) 包含一组变量与一组变量间的约束。一般而言，变量表示领域参数，每个变量都有一个固定的值域。
一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束 满足问题 的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。
2009-8-20 史忠植 高级人工智能 8
3.1 概述约束表示易于理解、编码及有效实现，它具有以下优点,
约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。
约束表示允许变量的域包含任意多个值，而不像命题只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。
易于并行实现。因为约束网络上的信息传播可以认为是同时的。
适合于递增型系统。约束可以递增式地加入到约束网络。
易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等,都可以自然地嵌入约束系统。
2009-8-20 史忠植 高级人工智能 9
3.1 约束表示
一元谓词。
序关系语言，只包含偏序关系或实变量上的大小关系。
形如,x - y > c” 的方程。
单位系数的线性方程与不等式，即所有的系数为 -1,0,1。
任意系数的线性方程与不等式。
约束的布尔组合。
代数与三角方程。
2009-8-20 史忠植 高级人工智能 10
3.1 约束推理
约束搜索约束搜索主要研究有限域上的约束满足。对有限域而言，
约束满足问题一般情况下是 一个 NP 问题。
约束语言
2009-8-20 史忠植 高级人工智能 11
3.1 约束搜索
回溯法。
约束传播。
智能回溯与真值维护。
可变次序例示。
局部修正法。
2009-8-20 史忠植 高级人工智能 12
约束语言
CONSTRAINTS
CHIP
COPS
ILOG
2009-8-20 史忠植 高级人工智能 13
CONSTRAINTS约束语言
CONSTRAINTS是一个面向电路描述的约束表示语言。
作为一个约束表示语言,它使用了符号处理技术来求解数学方程。
在 CONSTRAITS中，物理部件的功能及器件的结构都用约束表示。
这些约束一般是线性方程与不等式,也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。
2009-8-20 史忠植 高级人工智能 14
CONSTRAINTS约束语言
CONSTRAINTS 的一个优点是在类型层次中表示约束，用约束来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。
同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，
也缺乏有限域上的 域传播机制。
2009-8-20 史忠植 高级人工智能 15
约束逻辑程序设计语言 CHIP
CHIP(Constrant handling in Prolog) 就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外,CHIP还包含一个一般的延迟计算机制。
CHIP 主要应用于两个领域,运筹学与硬件设计。
CHIP 缺乏类型机制，而这种机制对于表达领域概念是极其重要的。
2009-8-20 史忠植 高级人工智能 16
面向对象约束语言 COPS
COPS系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。
2009-8-20 史忠植 高级人工智能 17
面向对象约束语言 COPS
COPS的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算； 通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。 COPS系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言 COPS具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。
2009-8-20 史忠植 高级人工智能 18
Exhaustive Search
Exhaustive-Search-Top(P) {where P is a CSP of the
form(V,D,C)}
1,f:= the null assignment
2,return Exhaustive-Search(f,P)
2009-8-20 史忠植 高级人工智能 19
Exhaustive Search
Exhaustive-Search(f,P)
1,if f is a total assignment of the variables in P
2,if f satisfies the constraints in P
3,answer,= f
4,else
5,answer,= Unsat
6,else
7,v,= some variable in P that is not yet assigned a
value by f
8,answer,= Unsat
9,for each value while answer = Unsat
10,f(v),=
11,answer,= Exhaustive-Search(f,P)
12,return answer
2009-8-20 史忠植 高级人工智能 20
Backtracking
Backtracking-Top(P)
1 f,= the null assignment
2 return Backtracking(f,P)
2009-8-20 史忠植 高级人工智能 21
Backtracking
Backtracking(f,P)
1 if f is a total assignment of the variables in P
2 answer,= f
3 else
4 v,= some variable in P that is not yet assigned a value
by f
5 answer,= Unsat
6 for each value while answer = Umsat
7 f(v),= x
8 if f satisfies the constraints in P
9 answer,= Backtracking(f,P)
10 return answer
2009-8-20 史忠植 高级人工智能 22
Backtracking
尽管回溯法好于生成测试法,但对于非平凡问题仍然是低效的 。 其原因在于搜索空间中不同路径的搜索重复相同的失败子路径 。 一些研究者认为,造成这种反复的原因是所谓的局部不一致性 。 最简单的情形是所谓的结点不一致性 。 对一个变量 vi的一个一元约束 。 存在域中一个值 vi不满足该约束 。 这样,每当 vi取到 a 时就会出现不一致性 。
另一种重复的情形 是所谓的弧不一致性 。
2009-8-20 史忠植 高级人工智能 23
3.3 CONSTRAINT PROPAGATION
( r e d,g r e e n )
( r e d,b lu e )
( r e d,g r e e n,
b lu e )
弧一致性
Arc consistency
2009-8-20 史忠植 高级人工智能 24
弧一致性
Arc consistency
如果对 vi 的当前域中的所有值 x，存在 vj的当前域中的某值 y使得 vi=x和 vj=y是 vi与 vj之间的约束所允许的，则弧 (vi,vj)是弧一致的。
弧一致性的概念是有向的。即 (vi,vj)
是弧一致的并不自动地意味着 (vj,vi)是一致的。
2009-8-20 史忠植 高级人工智能 25
3.3 CONSTRAINT PROPAGATION
All of the Mackworth algorithms make use
of a Revise procedure.
Let Dv be the current domain of v,
Let Dw be the current domain of w,
Let P be the constraint predicate that
holds between v and w,then Revise updates
Dv as follows:
yxPDDxD wyvv,s u c h t h a t,,
2009-8-20 史忠植 高级人工智能 26
CONSTRAINT PROPAGATION
Mackworth 1977
AC-1
AC-2
AC-3
2009-8-20 史忠植 高级人工智能 27
约束传播修改算法
REVISE(Vi,Vj)
1 DELETE? false;
2 for each x? Di do
3 if there is no such yj? Dj
4 such that(x,yj) is consistent,
5 then
6 delete x from Di;
7 DELETE? true;
8 endif
9 endfor
10 return DELETE;
11 end REVISE
2009-8-20 史忠植 高级人工智能 28
AC-1
1 Q? ;
2 repeat
3 CHANGE? false;
4 for each (Vi,Vj)? Q do
5 CHANGE? REVISE(Vi,Vj)? CHANGE;
6 endfor;
7 until not(CHANGE);
8 end AC-1
V V G i ji j,, a r c s
2009-8-20 史忠植 高级人工智能 29
AC-3
1 Q? ;
2 While Q not empty
3 Select and delete any arc(Vk,Vm) from Q;
4 If (REVISE(Vk,Vm))
5 Then Q? {(Vi,Vk) such that (Vi,Vk)?arcs(G),
6 i?k,i?m};
6 endfor;
7 endwhile;
8 end AC-3
V V G i ji j,, a r c s
2009-8-20 史忠植 高级人工智能 30
Backjumping
Backjumping-Top(P)
1 f,= the null assignment
2 <answer,conflict-set>,= Backjumping(f,P)
3 return answer
2009-8-20 史忠植 高级人工智能 31
Backjumping
Backjumping(f,P)
1 if f is a total assignment of the variables in P
2 answer,= <f,?>
3 else
4 v,= some variable in P that is not yet assigned a value
by f
5 answer,= Unsat
6 conflict-set,=?
7 for each value
8 f(v),= x
9 if f satisfies the constraints in P
10 <answer,new-conflicts>,= Backjumping(f,P)
2009-8-20 史忠植 高级人工智能 32
Backjumping
11 else
12 new-conflicts,= the set of variables in a
violated constraint
13 if answer? Unsat
14 return <answer,?>
15 else if v? new-conflicts
16 return <Unsat,new-conflicts>
17 else
18 conflict-set,= conflict-set? (new-conflicts
{v})
19 return <Unsat,conflict-set>
2009-8-20 史忠植 高级人工智能 33
COPS
Constraint,predicate expression
P(t1,...,tn)
where
P is built in function,such as
sum
times
eq(equal)
neq(not equal)
ge(great than or equal to)
gt(great than)
also can be defined by users
2009-8-20 史忠植 高级人工智能 34
COPS
Conditional constraint
condition1,constraint1;
.
.
conditionn,constraintn
where
condition1,...,conditionn are boolean expressions.
constraint1,..,constraintn are constraints or contraints table.
2009-8-20 史忠植 高级人工智能 35
COPS
RULE
Rule is used to define new function,method,predicate,or add
new constraint into object.
RULE [class::] predicate(varibles) (boolean expression)
{
constraint_1;
constraint_n;
CASE
boolean expression_1,constraint_1;
boolean expression_m,constraint_m;
}
2009-8-20 史忠植 高级人工智能 36
COPS
For example:
RULE multiple(INTEGER,*x,INTEGER,y,INTEGER,z)
(neq(y,0))
{
equal(x,divide(z,y));
}
z = x * y
2009-8-20 史忠植 高级人工智能 37
COPS
CLASS [class_name][:superclass_name]
{
// attributes definition
date type,attribute_name;
...
// rule definition
rule_name;
...
//function definition
function_name;
...
// method definition
method_name;
...
}
2009-8-20 史忠植 高级人工智能 38
COPS
Implementation
Program written by COPS consists of classes and rules,COPS
constraint programming language is a declarative language,providing
classes,methods which are exist in object oriented language,It is
similar with C++,COPS has the features:
constraint
object oriented
logic programming
production system
2009-8-20 史忠植 高级人工智能 39
COPS
COPS_Compiler
1 {
2 Call yacc to parse the program and
3 to generate internal structures.
4 Initializatiion
5 Create Cops Constant trueNode;
6 Allocate memories for global variables.
2009-8-20 史忠植 高级人工智能 40
COPS
7 Interprte the program with the internal structures.
8 Constraint networks are built up for Unsolved
9 constraints and variables.
10 while some constraints in the constraint networks are
triggered,
11 inteprete the triggered constraints.
12 }
2009-8-20 史忠植 高级人工智能 41
COPS
Interpreter:
1 {
2 switch (constraint type)
3 case Constant:
4 return Constant:
5 case global variable:
6 interprete global variable:
7 case local variable or argument:
8 interprete local variable or argument:
9 case object-attribute pair;
10 interprete object-attribute pair:
11 case function call:
2009-8-20 史忠植 高级人工智能 42
COPS
12 interprete function call:
13 case method call:
14 interprete method call:
15 case CASE expression:
16 interprete CASE expression:
17,..
18 default:
20 report error
21 }
2009-8-20 史忠植 高级人工智能 43
ILOG SOLVER
Combines object oriented programming with constraint logic
programming,containing logic variables,incremental constraint
satisfaction and backtracking.
variables,C++ object
integer variable CtIntVar
floating variable CtFloatVar
boolean variable CtBoolVar
Memory Management
new:
delete:
2009-8-20 史忠植 高级人工智能 44
ILOG SOLVER
Constraints
CtTell(x == (y + z));
Basic constraints,=,?,?,<,>,+,-,*,/,subset,
superset,union,intersection,member,boolean or,boolean and,
boolean not,boolean xor,
CtTell((x==0) || (y==0));
CtIfThen (x < 100,x = x+1);
Search
2009-8-20 史忠植 高级人工智能 45
ILOG SOLVER
CTGOALn,how to execute
CTGOAL1(CtInstantiate,CtIntVar* x){
CtInt a = x->chooseValue();
CtOr(Constraint(x == a),
CtAnd(Constraint(x != a),
CtInstantiate(x)));
}
2009-8-20 史忠植 高级人工智能 46
ILOG Schedule 1.0
Schedule
CtSchedule class
Global object,time original ---tineMin
time horizon ---timeMax
2009-8-20 史忠植 高级人工智能 47
ILOG Schedule 1.0
Resources
CtResource
CtDiscreteResource
CtUnaryResource
CtDiscreteEnergy
CtStateResource
2009-8-20 史忠植 高级人工智能 48
ILOG Schedule 1.0
Activities
CtActivity class
CtIntervalActivity
An activity is defined by its start time,end time and duration
Activities require,provide,consume and produce resources
2009-8-20 史忠植 高级人工智能 49
Scheduling Problem
Prices paid as tasks begin $1000 per day
Availability,Day 0:$20000,Day 15,+$9000
2009-8-20 史忠植 高级人工智能 50
Constraints
// To create a schedule with origin 0 and given horizon.
CtSchedule* schedule =
new CtSchedule(0,horizon);
// To create an activity with the given duration.
CtIntervalActivity* act =
new CtIntervalActivity(schedule,duration);
//To post a precedence constraint between act1 and act2.
act2->startsAfterEnd(act1,0);
2009-8-20 史忠植 高级人工智能 51
Constraints
//To create a total budget of limited capacity (here 29000).
CtDiscreteResource* res =
new CtDiscreteResource(schedule,
CtRequiredResource,
capacity);
// To state that only cap (here 20000) is available prior to a
// given date (here 15).
res->setCapacityMax(0,date,cap);
// To state that an activity act consumes c units of res.
act->consumes(res,c);
2009-8-20 史忠植 高级人工智能 52
Algorithm Program
CtBoolean IsUnScheduled(CtActivity* act){
// Return true if act does not have a fixed start time.
if (act->getStartVariable()->isBound())
return CtFalse;
else
return CtTrue;
}
2009-8-20 史忠植 高级人工智能 53
Algorithm Program
CtBoolean IsMoreUrgent(CtActivity* act1,
CtActivity* act2){
// Returns true if act1 is more urgent than act2.
// Returns true if act2 is unbound (==0)
if (act2 == 0)
return CtTrue;
else if (act1->getStartMax() < act2->getStartMax())
return CtTrue;
else
return CtFalse;
}
2009-8-20 史忠植 高级人工智能 54
Algorithm Program
CtActivity* SelectActivity(CtSchedule* schedule){
// Returns the unscheduled activity with the smallest latest
// statrt time,Returns 0 if all activities are scheduled.
CtActivity* bestActivity = 0;
//Creates an iterator to iterate on all activities.
CtActivityIterator* iterator(schedule);
CtActivity* newActivity;
while(iterator.next(newactivity))
if((IsUnScheduled(newActivity))
&& (IsMoreUgent(newActivity,bestActivity)))
bestactivity = newActivity;
return bestActivity;
}
2009-8-20 史忠植 高级人工智能 55
Algorithm Program
void SolveProblem(CtSchedule* schedule){
// Solve the problem assuming constraints have been posted.
CtActivity* act = SelectActivity(schedule);
while (act !=0) {
act->setStartTime(act->getStartMin());
act = SelectActivity(schedule);
}
}
2009-8-20 史忠植 高级人工智能 56
Optimal Solution to the
Scheduling Problem
高级人工智能第三章 约束推理史忠植中国科学院计算技术所
2009-8-20 史忠植 高级人工智能 2
第三章 约束推理
3.1 概述
3.2 回溯法
3.3 约束传播
3.4 回跳法
3.5 约束推理系统 COPS
3.6 ILOG SOLVER
2009-8-20 史忠植 高级人工智能 3
3.1 概述
Over the years,the theory and application
of optimization has grown into an important
field of research,We can distinguish following
fields of research that pay attention to
optimization problem:
operations research
constraint program
genetic algorithm
neural network
2009-8-20 史忠植 高级人工智能 4
3.1 概述
Operations Research
Traditionally,a lot of the attention in
operations research has been paid to optimization
problems,particularly,planning,scheduling,
that are based on mathematical model,For solving
problems,one should write particular program in
terms of algorithm,When modeling a practical
scheduling problem using classical models,one
is often forced to discard many degrees of
freedom and side constraints,
2009-8-20 史忠植 高级人工智能 5
3.1 概述
Constraint Programming concerned with solving
instances of the constraint satisfaction problem,The
general Constraint Satisfaction Problem (CSP)
A set of n variables {x1,x2,…xn} with values
in the discrete,finite domains{D1,D2,…Dn},.
,{4,5,6,7}
,{red,green,blue}
A set of m constraints{c1,c2,…cm} which are
predicates c1{x1,x2,…xj} defined on the Cartesian
production D1xD2x…xDj,If is TRUE,
the valuation of the variables is said to be satisfied.
C1,color(wood,red)
C2,x y 16
2009-8-20 史忠植 高级人工智能 6
3.1 概述一个约束通常是指一个包含若干变量的关系表达式，
用以表示这些变量所必须满足的条件。约束表示广泛地应用于 AI 的各个领域，包括定性推理、基于模型的诊断、自然语言理解、景物分析、任务调度、系统配置、科学实验规划、机械与电子设备的设计与分析等。
2009-8-20 史忠植 高级人工智能 7
3.1 概述一个约束满足问题 (Constraint Satisfaction Problem,
简称 CSP) 包含一组变量与一组变量间的约束。一般而言，变量表示领域参数，每个变量都有一个固定的值域。
一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束 满足问题 的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。
2009-8-20 史忠植 高级人工智能 8
3.1 概述约束表示易于理解、编码及有效实现，它具有以下优点,
约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。
约束表示允许变量的域包含任意多个值，而不像命题只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。
易于并行实现。因为约束网络上的信息传播可以认为是同时的。
适合于递增型系统。约束可以递增式地加入到约束网络。
易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等,都可以自然地嵌入约束系统。
2009-8-20 史忠植 高级人工智能 9
3.1 约束表示
一元谓词。
序关系语言，只包含偏序关系或实变量上的大小关系。
形如,x - y > c” 的方程。
单位系数的线性方程与不等式，即所有的系数为 -1,0,1。
任意系数的线性方程与不等式。
约束的布尔组合。
代数与三角方程。
2009-8-20 史忠植 高级人工智能 10
3.1 约束推理
约束搜索约束搜索主要研究有限域上的约束满足。对有限域而言，
约束满足问题一般情况下是 一个 NP 问题。
约束语言
2009-8-20 史忠植 高级人工智能 11
3.1 约束搜索
回溯法。
约束传播。
智能回溯与真值维护。
可变次序例示。
局部修正法。
2009-8-20 史忠植 高级人工智能 12
约束语言
CONSTRAINTS
CHIP
COPS
ILOG
2009-8-20 史忠植 高级人工智能 13
CONSTRAINTS约束语言
CONSTRAINTS是一个面向电路描述的约束表示语言。
作为一个约束表示语言,它使用了符号处理技术来求解数学方程。
在 CONSTRAITS中，物理部件的功能及器件的结构都用约束表示。
这些约束一般是线性方程与不等式,也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。
2009-8-20 史忠植 高级人工智能 14
CONSTRAINTS约束语言
CONSTRAINTS 的一个优点是在类型层次中表示约束，用约束来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。
同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，
也缺乏有限域上的 域传播机制。
2009-8-20 史忠植 高级人工智能 15
约束逻辑程序设计语言 CHIP
CHIP(Constrant handling in Prolog) 就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外,CHIP还包含一个一般的延迟计算机制。
CHIP 主要应用于两个领域,运筹学与硬件设计。
CHIP 缺乏类型机制，而这种机制对于表达领域概念是极其重要的。
2009-8-20 史忠植 高级人工智能 16
面向对象约束语言 COPS
COPS系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。
2009-8-20 史忠植 高级人工智能 17
面向对象约束语言 COPS
COPS的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算； 通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。 COPS系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言 COPS具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。
2009-8-20 史忠植 高级人工智能 18
Exhaustive Search
Exhaustive-Search-Top(P) {where P is a CSP of the
form(V,D,C)}
1,f:= the null assignment
2,return Exhaustive-Search(f,P)
2009-8-20 史忠植 高级人工智能 19
Exhaustive Search
Exhaustive-Search(f,P)
1,if f is a total assignment of the variables in P
2,if f satisfies the constraints in P
3,answer,= f
4,else
5,answer,= Unsat
6,else
7,v,= some variable in P that is not yet assigned a
value by f
8,answer,= Unsat
9,for each value while answer = Unsat
10,f(v),=
11,answer,= Exhaustive-Search(f,P)
12,return answer
2009-8-20 史忠植 高级人工智能 20
Backtracking
Backtracking-Top(P)
1 f,= the null assignment
2 return Backtracking(f,P)
2009-8-20 史忠植 高级人工智能 21
Backtracking
Backtracking(f,P)
1 if f is a total assignment of the variables in P
2 answer,= f
3 else
4 v,= some variable in P that is not yet assigned a value
by f
5 answer,= Unsat
6 for each value while answer = Umsat
7 f(v),= x
8 if f satisfies the constraints in P
9 answer,= Backtracking(f,P)
10 return answer
2009-8-20 史忠植 高级人工智能 22
Backtracking
尽管回溯法好于生成测试法,但对于非平凡问题仍然是低效的 。 其原因在于搜索空间中不同路径的搜索重复相同的失败子路径 。 一些研究者认为,造成这种反复的原因是所谓的局部不一致性 。 最简单的情形是所谓的结点不一致性 。 对一个变量 vi的一个一元约束 。 存在域中一个值 vi不满足该约束 。 这样,每当 vi取到 a 时就会出现不一致性 。
另一种重复的情形 是所谓的弧不一致性 。
2009-8-20 史忠植 高级人工智能 23
3.3 CONSTRAINT PROPAGATION
( r e d,g r e e n )
( r e d,b lu e )
( r e d,g r e e n,
b lu e )
弧一致性
Arc consistency
2009-8-20 史忠植 高级人工智能 24
弧一致性
Arc consistency
如果对 vi 的当前域中的所有值 x，存在 vj的当前域中的某值 y使得 vi=x和 vj=y是 vi与 vj之间的约束所允许的，则弧 (vi,vj)是弧一致的。
弧一致性的概念是有向的。即 (vi,vj)
是弧一致的并不自动地意味着 (vj,vi)是一致的。
2009-8-20 史忠植 高级人工智能 25
3.3 CONSTRAINT PROPAGATION
All of the Mackworth algorithms make use
of a Revise procedure.
Let Dv be the current domain of v,
Let Dw be the current domain of w,
Let P be the constraint predicate that
holds between v and w,then Revise updates
Dv as follows:
yxPDDxD wyvv,s u c h t h a t,,
2009-8-20 史忠植 高级人工智能 26
CONSTRAINT PROPAGATION
Mackworth 1977
AC-1
AC-2
AC-3
2009-8-20 史忠植 高级人工智能 27
约束传播修改算法
REVISE(Vi,Vj)
1 DELETE? false;
2 for each x? Di do
3 if there is no such yj? Dj
4 such that(x,yj) is consistent,
5 then
6 delete x from Di;
7 DELETE? true;
8 endif
9 endfor
10 return DELETE;
11 end REVISE
2009-8-20 史忠植 高级人工智能 28
AC-1
1 Q? ;
2 repeat
3 CHANGE? false;
4 for each (Vi,Vj)? Q do
5 CHANGE? REVISE(Vi,Vj)? CHANGE;
6 endfor;
7 until not(CHANGE);
8 end AC-1
V V G i ji j,, a r c s
2009-8-20 史忠植 高级人工智能 29
AC-3
1 Q? ;
2 While Q not empty
3 Select and delete any arc(Vk,Vm) from Q;
4 If (REVISE(Vk,Vm))
5 Then Q? {(Vi,Vk) such that (Vi,Vk)?arcs(G),
6 i?k,i?m};
6 endfor;
7 endwhile;
8 end AC-3
V V G i ji j,, a r c s
2009-8-20 史忠植 高级人工智能 30
Backjumping
Backjumping-Top(P)
1 f,= the null assignment
2 <answer,conflict-set>,= Backjumping(f,P)
3 return answer
2009-8-20 史忠植 高级人工智能 31
Backjumping
Backjumping(f,P)
1 if f is a total assignment of the variables in P
2 answer,= <f,?>
3 else
4 v,= some variable in P that is not yet assigned a value
by f
5 answer,= Unsat
6 conflict-set,=?
7 for each value
8 f(v),= x
9 if f satisfies the constraints in P
10 <answer,new-conflicts>,= Backjumping(f,P)
2009-8-20 史忠植 高级人工智能 32
Backjumping
11 else
12 new-conflicts,= the set of variables in a
violated constraint
13 if answer? Unsat
14 return <answer,?>
15 else if v? new-conflicts
16 return <Unsat,new-conflicts>
17 else
18 conflict-set,= conflict-set? (new-conflicts
{v})
19 return <Unsat,conflict-set>
2009-8-20 史忠植 高级人工智能 33
COPS
Constraint,predicate expression
P(t1,...,tn)
where
P is built in function,such as
sum
times
eq(equal)
neq(not equal)
ge(great than or equal to)
gt(great than)
also can be defined by users
2009-8-20 史忠植 高级人工智能 34
COPS
Conditional constraint
condition1,constraint1;
.
.
conditionn,constraintn
where
condition1,...,conditionn are boolean expressions.
constraint1,..,constraintn are constraints or contraints table.
2009-8-20 史忠植 高级人工智能 35
COPS
RULE
Rule is used to define new function,method,predicate,or add
new constraint into object.
RULE [class::] predicate(varibles) (boolean expression)
{
constraint_1;
constraint_n;
CASE
boolean expression_1,constraint_1;
boolean expression_m,constraint_m;
}
2009-8-20 史忠植 高级人工智能 36
COPS
For example:
RULE multiple(INTEGER,*x,INTEGER,y,INTEGER,z)
(neq(y,0))
{
equal(x,divide(z,y));
}
z = x * y
2009-8-20 史忠植 高级人工智能 37
COPS
CLASS [class_name][:superclass_name]
{
// attributes definition
date type,attribute_name;
...
// rule definition
rule_name;
...
//function definition
function_name;
...
// method definition
method_name;
...
}
2009-8-20 史忠植 高级人工智能 38
COPS
Implementation
Program written by COPS consists of classes and rules,COPS
constraint programming language is a declarative language,providing
classes,methods which are exist in object oriented language,It is
similar with C++,COPS has the features:
constraint
object oriented
logic programming
production system
2009-8-20 史忠植 高级人工智能 39
COPS
COPS_Compiler
1 {
2 Call yacc to parse the program and
3 to generate internal structures.
4 Initializatiion
5 Create Cops Constant trueNode;
6 Allocate memories for global variables.
2009-8-20 史忠植 高级人工智能 40
COPS
7 Interprte the program with the internal structures.
8 Constraint networks are built up for Unsolved
9 constraints and variables.
10 while some constraints in the constraint networks are
triggered,
11 inteprete the triggered constraints.
12 }
2009-8-20 史忠植 高级人工智能 41
COPS
Interpreter:
1 {
2 switch (constraint type)
3 case Constant:
4 return Constant:
5 case global variable:
6 interprete global variable:
7 case local variable or argument:
8 interprete local variable or argument:
9 case object-attribute pair;
10 interprete object-attribute pair:
11 case function call:
2009-8-20 史忠植 高级人工智能 42
COPS
12 interprete function call:
13 case method call:
14 interprete method call:
15 case CASE expression:
16 interprete CASE expression:
17,..
18 default:
20 report error
21 }
2009-8-20 史忠植 高级人工智能 43
ILOG SOLVER
Combines object oriented programming with constraint logic
programming,containing logic variables,incremental constraint
satisfaction and backtracking.
variables,C++ object
integer variable CtIntVar
floating variable CtFloatVar
boolean variable CtBoolVar
Memory Management
new:
delete:
2009-8-20 史忠植 高级人工智能 44
ILOG SOLVER
Constraints
CtTell(x == (y + z));
Basic constraints,=,?,?,<,>,+,-,*,/,subset,
superset,union,intersection,member,boolean or,boolean and,
boolean not,boolean xor,
CtTell((x==0) || (y==0));
CtIfThen (x < 100,x = x+1);
Search
2009-8-20 史忠植 高级人工智能 45
ILOG SOLVER
CTGOALn,how to execute
CTGOAL1(CtInstantiate,CtIntVar* x){
CtInt a = x->chooseValue();
CtOr(Constraint(x == a),
CtAnd(Constraint(x != a),
CtInstantiate(x)));
}
2009-8-20 史忠植 高级人工智能 46
ILOG Schedule 1.0
Schedule
CtSchedule class
Global object,time original ---tineMin
time horizon ---timeMax
2009-8-20 史忠植 高级人工智能 47
ILOG Schedule 1.0
Resources
CtResource
CtDiscreteResource
CtUnaryResource
CtDiscreteEnergy
CtStateResource
2009-8-20 史忠植 高级人工智能 48
ILOG Schedule 1.0
Activities
CtActivity class
CtIntervalActivity
An activity is defined by its start time,end time and duration
Activities require,provide,consume and produce resources
2009-8-20 史忠植 高级人工智能 49
Scheduling Problem
Prices paid as tasks begin $1000 per day
Availability,Day 0:$20000,Day 15,+$9000
2009-8-20 史忠植 高级人工智能 50
Constraints
// To create a schedule with origin 0 and given horizon.
CtSchedule* schedule =
new CtSchedule(0,horizon);
// To create an activity with the given duration.
CtIntervalActivity* act =
new CtIntervalActivity(schedule,duration);
//To post a precedence constraint between act1 and act2.
act2->startsAfterEnd(act1,0);
2009-8-20 史忠植 高级人工智能 51
Constraints
//To create a total budget of limited capacity (here 29000).
CtDiscreteResource* res =
new CtDiscreteResource(schedule,
CtRequiredResource,
capacity);
// To state that only cap (here 20000) is available prior to a
// given date (here 15).
res->setCapacityMax(0,date,cap);
// To state that an activity act consumes c units of res.
act->consumes(res,c);
2009-8-20 史忠植 高级人工智能 52
Algorithm Program
CtBoolean IsUnScheduled(CtActivity* act){
// Return true if act does not have a fixed start time.
if (act->getStartVariable()->isBound())
return CtFalse;
else
return CtTrue;
}
2009-8-20 史忠植 高级人工智能 53
Algorithm Program
CtBoolean IsMoreUrgent(CtActivity* act1,
CtActivity* act2){
// Returns true if act1 is more urgent than act2.
// Returns true if act2 is unbound (==0)
if (act2 == 0)
return CtTrue;
else if (act1->getStartMax() < act2->getStartMax())
return CtTrue;
else
return CtFalse;
}
2009-8-20 史忠植 高级人工智能 54
Algorithm Program
CtActivity* SelectActivity(CtSchedule* schedule){
// Returns the unscheduled activity with the smallest latest
// statrt time,Returns 0 if all activities are scheduled.
CtActivity* bestActivity = 0;
//Creates an iterator to iterate on all activities.
CtActivityIterator* iterator(schedule);
CtActivity* newActivity;
while(iterator.next(newactivity))
if((IsUnScheduled(newActivity))
&& (IsMoreUgent(newActivity,bestActivity)))
bestactivity = newActivity;
return bestActivity;
}
2009-8-20 史忠植 高级人工智能 55
Algorithm Program
void SolveProblem(CtSchedule* schedule){
// Solve the problem assuming constraints have been posted.
CtActivity* act = SelectActivity(schedule);
while (act !=0) {
act->setStartTime(act->getStartMin());
act = SelectActivity(schedule);
}
}
2009-8-20 史忠植 高级人工智能 56
Optimal Solution to the
Scheduling Problem
