人工智能原理复习4
Constraint Satisfaction Problems
What is a csp? guess coloring problem; why does this make sense as problem? silly but good representation for real world problems, e.g. scheduling tasks that need resources – can’t run 2 tasks at the same time if they need the same resource CSPs as a search problem?
What is Search For?
Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space
Planning: sequences of actions The path to the goal is the important thing Paths have various costs, depths Heuristics give problem-specific guidance
Identification: assignments to variables The goal itself is important, not the path All paths at the same depth (for some formulations) CSPs are specialized for identification problems
Step back – these are search problems, so we can now take a look at different problems we can use search for Before we had planning; Ninja robot knows where the gem is, but not how to get there Identification; detective robot wants to know where the gem is – the goal is important, not the path; what is the depth?
](https://pic.imgdb.cn/item/6671b857d9c307b7e927ea35.png)
Constraint Satisfaction Problems
Standard search problems: State is a “black box”: arbitrary data structure Goal test can be any function over states Successor function can also be anything
Constraint satisfaction problems (CSPs): A special subset of search problems State is defined by variables Xi with values from a domain D (sometimes D depends on i) Goal test is a set of constraints specifying allowable combinations of values for subsets of variables
Allows useful general-purpose algorithms with more power than standard search algorithms
Before: states were nodes, no structure, just a set, they could be anything Goal test – like a judge; just makes decisions; you don’t know how; Now: Goal test has structure, it ‘s more like a manual describing a set of constraints that have to hold true
CSP Examples
I want you to practice formalizing real problems as search/csp problems
How do you specify constraints in code/math? Implicit vs explicit. What might be explicit?
Binary CSP: each constraint relates (at most) two variables
Binary constraint graph: nodes are variables, arcs show constraints
General-purpose CSP algorithms use the graph structure to speed up search. E.g., Tasmania is an independent subproblem!
Demo:
Run constraint.jar or constraint.exe, load the 5 queens problem. Demo is just showing the n-queens applet as illustration of constraint graph, but later in lecture we’ll interact with the applet. aispace.org will have the latest version
Are these constraints enough? No, there should be N queens there.
0=7, R=4, W=6, U=2, T=8, F=1; 867 + 867 = 1734
Varieties of CSPs and Constraints
Varieties of CSPs
Discrete Variables (today)
Finite domains
Size d means O(dn) complete assignments
E.g., Boolean CSPs, including Boolean satisfiability (NP-complete)
Infinite domains (integers, strings, etc.)
E.g., job scheduling, variables are start/end times for each job
Linear constraints solvable, nonlinear undecidable
Continuous variables
E.g., start/end times for Hubble Telescope observations
Linear constraints solvable in polynomial time by LP methods
Varieties of Constraints
Unary constraints involve a single variable (equivalent to reducing
domains), e.g.:
Binary constraints involve pairs of variables, e.g.:
Higher-order constraints involve 3 or more variables:
e.g., cryptarithmetic column constraints
Preferences (soft constraints):
E.g., red is better than green
Often representable by a cost for each variable assignment
Gives constrained optimization problems
(We’ll ignore these until we get to Bayes’ nets)
Real-World CSPs
Assignment problems: e.g., who teaches what class
Timetabling problems: e.g., which class is offered when and where?
Hardware configuration
Transportation scheduling
Factory scheduling
Circuit layout
Fault diagnosis
… lots more!
Many real-world problems involve real-valued variables…
Origin: The Waltz Algorithm
The Waltz algorithm is for interpreting line drawings of solid polyhedra as 3D objects
An early example of an AI computation posed as a CSP
Approach:
Each intersection is a variable
Adjacent intersections impose constraints on each other
Solutions are physically realizable 3D interpretations
Guzman: Find the Problem
Question: how to detect the number of objects by machine？
回溯搜索
在深度优先搜索的基础上增加如下改进：
1、每次只考虑一个变量
2、可以随时检查约束（增加测试函数）
Backtracking = DFS + variable-ordering + fail-on-violation
Improving Backtracking
Ordering:
o Which variable should be assigned next?
o In what order should its values be tried?
Filtering
Keep track of domains for unassigned variables and cross off bad options
Filtering: Forward Checking
o Filtering: Keep track of domains for unassigned variables and cross off bad options
o Forward checking: Cross off values that violate a constraint when added to the existing assignment
Constraint Propagation
约束传播
核心思想：局部相容性
一元约束：只限制单个变量的取值
二元约束：与两个变量有关
变量个数任意的约束称为全局约束
节点相容
单个变量（对应一个节点）值域中的所有取值满足它的一元约束，就是节点相容的。
弧相容
如果CSP中某变量值域中所有取值满足该变量所有二元约束，则此变量弧相容
弧相容算法AC-3
弧相容可能缩小变量的值域，有时甚至还能找到解（每个变量值域大小都为1时），或者有时发现CSP无解（一些变量的值域大小=0）
路径相容（路径一致性，也就是下面k=3的情况）：观察变量得到隐式约束，并以此来加强二元约束
k-相容：如果对于任何k-1个变量的相容赋值，第k个变量总能被赋予一个和前k-1个变量相容的值，那么这个CSP就是k相容的。
k越高，计算成本越高
k一致性
k=2的情况：弧一致性（弧相容）
部分赋值的回溯搜索算法：
可以用标准的深度优先搜索，状态可能是部分赋值，行动是将var=value加入到赋值中。
回溯搜索用于深度优先搜索中，每次为一个变量选一个赋值，没有合法的值的时候就回溯。
有效解决CSP
变量和取值顺序
变量：
1）选择“合法”取值最少的变量——称为最少剩余值（MRV）启发式。（做一个强有力的引导，方便提早遇到失败，从而剪枝）
2）度启发式：通过选择与其他未赋值变量约束最多的变量来试图降低未来的分支因子。（用来打破僵局，如选择第一个着色区域）
“Fail-fast” ordering
总结一下，对于变量的选择原则是：可选变量最少、约束冲突最多的变量先安排！
值：
最少约束值：优先选择的赋值是给邻居变量留下更多的选择
搜索与推理交错进行
前向检验：只要变量X被赋值，就对它进行弧相容检查，对每个通过约束与X相关的未赋值变量Y，从Y值域中删去与X不相容的值。
智能回溯：向后看
主要概念：前向检验；冲突集；回跳
【参考资料】
http://t.csdnimg.cn/ck8s2
http://t.csdnimg.cn/keaAl （这是与课件配套的）