Transcript O(b^d)

Outline for 3/28
•
•
•
•
•
•
Introduction & Logistics
Textbook: chapters 3, 4 and 5.
Notion of a Problem Space
Search Techniques
Constraint Satisfaction Techniques
Game Search; Video: Kasparov vs. Deep Blue
Logistics:
• John Q. Yang [email protected]
• Mathrew Cary [email protected]
• www.cs.washington.edu/education/courses/cse592/00sp
• Reading
– Required: Textbook by Russell & Norvig and Tom Mitchell
– Recommended: various papers
• Grading:
– Problem Set
– AI Tool Demonstration in Class
– Final Project (Group)
25%
25%
50%
Defining Intelligence?
Artificial Intelligence
•
•
•
•
•
•
•
•
•
Planning (To get a good job I should get an MS/CSE…)
Diagnosis (My car won’t start, but I know it has gas…)
Design (Space Shuttle, Boeing 777, Pentium)
Communicate (Language + Social reasoning)
Theorem Proving (Fermat’s Last Theorem)
Perceive/Act (Vision, Manipulation)
Game Playing (Kasparov vs. Deep Blue)
Create Art (MacBeth, Mona Lisa, Taj Mahal)
Learn to ...
4
AI as Science
• Origin & Laws of the Physical Universe
• Origin & Laws of Biological Life
• Nature of Intelligent Thought
AI as Engineering
•
•
•
•
Softbots & Intelligent User Interfaces
Mobile Robots … Immobots
Machine Learning Algorithms; Data Mining
Medical Expert Systems...
AI Theory
• For example, Machine Learning
– Given tree structured instance space with n attributes,
you need
• 4 log(2/d) + 16n log(13/e))/e examples
AI Practice
•
•
•
•
Game Playing
Pattern Classification: Character Recognition, …
Machine Learning: Data Mining, Web Agents
Perception – Vision, Speech
Course Topics by Week
•
•
•
•
•
•
•
•
•
•
Search (1 and 2-person) & Constraint Satisfaction
KR&R 1: Logic representation & Theorem Proving
KR&R 2: Planning and Diagnosis
Machine Learning 1: Supervised Learning
Machine Learning 2: Unsupervised Learning
Natural Language Processing
AI-Tools demo
Application Sampler I
Application Sampler II
Final Project
Search (one solution)
• Brute force
– DFS, BFS, iterative deepening, iterative broadening
• Heuristic
– Best first, beam, hill climbing, simulated annealing,
limited discrepancy
• Optimizing
– Branch & bound, A*, IDA*, SMA*
• Adversary Search
– Minimax, alpha-beta, conspiracy search
• Constraint Satisfaction
– As search, preprocessing, backjumping, forward
checking, dynamic variable ordering
Search (Internet and Databases)
•
•
•
•
•
Look for all solutions
Must be efficient
Often uses indexing
Also uses heuristics (e.g., Google )
More than search itself
– NLP can be important
– Scale up to thousands of users
– Caching is often used
Outline
• Defining a Search Space
• Types of Search
–
–
–
–
–
Blind
Heuristic
Optimization
Adversary Search
Constraint Satisfaction
• Analysis
– Completeness
– Time & Space Complexity
Specifying a search problem?
•
•
•
•
•
What are states (nodes in graph)?
What are the operators (arcs between nodes)?
Initial state?
Goal test?
[Cost?, Heuristics?, Constraints?]
E.g., Eight Puzzle
7 2
4 1
8 5
3
6
1 2
4 5
7 8
3
6
11
Towers of Hanoi
•
•
•
•
What are states (nodes in graph)?
What are the operators (arcs between nodes)?
Initial state?
Goal test?
a
b
c
12
Planning
• What is Search Space?
– What are states?
– What are arcs?
•
•
•
•
What is Initial State?
What is Goal?
Path Cost?
Heuristic?
c
a
b
PickUp(Block)
PutDown(Block)
a
b
c
13
Missionaries and Cannibals
•
•
•
•
•
What are states (nodes in graph)?
What are the operators (arcs between nodes)?
Initial state?
Goal test?
2 Representations
mmm
ccc
14
Search Strategies
• Blind Search
–
–
–
–
Depth first search
Breadth first search
Iterative deepening search
Iterative broadening search
• Heuristic Search
• Optimizing Search
• Constraint Satisfaction
15
Depth First Search
• Maintain stack of nodes to visit
• Evaluation
– Complete?
Not for infinite spaces
– Time Complexity?
a
O(b^d)
– Space Complexity?
b
c
O(d)
d
e
f
g
h
Breadth First Search
• Maintain queue of nodes to visit
• Evaluation
– Complete?
Yes
a
– Time Complexity?
O(b^d)
b
– Space Complexity?
c
O(b^d)
d
e
f
g
h
Iterative Deepening Search
• DFS with limit; incrementally grow limit
a
b
c
Iterative Deepening Search
• DFS with limit; incrementally grow limit
• Evaluation
– Complete?
Yes
– Time Complexity?
a
O(b^d)
– Space Complexity?
b
O(d)
d
c
e
f
g
h
Heuristic Search
• A heuristic is:
– Function from a state to a real number
• Low number means state is close to goal
• High number means state is far from the goal
A* Search
• Idea
– Best first search with admissible heuristic
– Plus keep checking until all possibilities look worse
• Evaluation
– Finds optimal solution?
Yes
– Time Complexity?
O(b^d)
– Space Complexity?
O(b^d)
Admissable Heuristics
• f(x) = g(x) + h(x)
• g: cost so far
• h: underestimate of remaining costs
e
a
12
8
d
f
10
8
14
b
7 2
4 1
15
c
For transportation planning?
20
For eight puzzle?
8
5
3
6
Hill Climbing
• Idea
– Always choose best child; no backtracking
• Evaluation
– Complete?
No - suffers from plateau, local maxima, ridges
– Time Complexity?
O(b^d)
but only in pathological cases
– Space Complexity?
O(b)
Simulated Annealing
• Objective: avoid local minima
• Technique:
– For the most part use hill climbing
– Occasionally take non-optimal step
– Reduce probability(non-optimal) over time
• Comparison to Hill Climbing
– Completeness?
– Speed?
– Space Complexity?
temp
Importance of Heuristics
7 2
4 1
8 5
• h1 = number of tiles in the wrong place
• h2 = sum of distances of tiles from correct loc
D
2
4
6
8
10
12
14
18
24
IDS
10
112
680
6384
47127
364404
3473941
A*(h1)
6
13
20
39
93
227
539
3056
39135
A*(h2)
6
12
18
25
39
73
113
363
1641
3
6
Constraint Satisfaction
•
•
•
•
•
•
Chronological Backtracking (BT)
Backjumping (BJ)
Conflict-Directed Backjumping (CBJ)
Forward checking (FC)
Dynamic variable ordering heuristics
Preprocessing Strategies
Chinese Constraint Network
Must be
Hot&Sour
Soup
Appetizer
Chicken
Dish
No
Peanuts
Vegetable
No
Peanuts
Total Cost
< $30
Pork Dish
Not Both
Spicy
Seafood
Rice
Not
Chow Mein
CSPs in the real world
•
•
•
•
Scheduling Space Shuttle Repair
Transportation Planning
Computer Configuration
Diagnosis
Recognizing Trihedral Objects
• Trihedral objects: all vertices are intersections of three
planes.
• Labeling: with +, - and ->
• Enumerating all labels:
• Using constraint satisfaction to find correct labels
– NP hard in general
– CSP gives good solutions
Binary Constraint Network
• Set of n variables: x1 … xn
• Value domains for each variable: D1 … Dn
• Set of binary constraints (also known as relations)
– Rij  Di  Dj
– Specifies which values of xi are consistent w/ those of xj
• Partial assignment of values with a tuple of pairs
– {...(x,a)…} means variable x gets value a...
– Consistent if all constraints satisfied on all vars in tuple
– Tuple = full solution if consistent & all vars included
• Tuple {(xi, ai) … (xj, aj)} consistent w/ a set of vars {xm …
xn} iff  am … an such that this tuple is consistent: {(xi, ai)
… (xj, aj), (xm, am) … (xn, an)} }
N Queens
• Variables = board columns
• Domain values = rows
• Rij = {(ai, aj) : (ai  aj)  (|i-j|  |ai-aj|)
– e.g. R12 = {(1,3), (1,4), (2,4), (3,1), (4,1), (4,2)}
Q
Q
Q
• {(x1, 2), (x2, 4), (x3, 1)} consistent with (x4)
• Shorthand: “{2, 4, 1} consistent with x4”
CSP as a search problem?
•
•
•
•
What are states (nodes in graph)?
What are the operators (arcs between nodes)?
Initial state?
Goal test?
Q
Q
Q
32
Chronological Backtracking (BT)
(e.g., depth first search)
1
Q
Q
2
Q
6
Q
Q
Q
Q
4
Q
Consistency check performed in the order
in which vars were instantiated
If c-check fails, try next value of current var
If no more values, backtrack to most recent var
3
Q
Q
Q
5
Backjumping (BJ)
• Similar to BT, but more efficient when no consistent
instantiation can be found for the current var
• Instead of backtracking to most recent var…
• BJ reverts to deepest var which was checked against
the current var
Q
Q
Q
BJ Discovers
(2, 5, 3, 6) inconsistent with x6
No sense trying other values of x5
Q
Q
BT vs. BJ
{
Preprocessing Strategies
• Even FC-CBJ is O(b^d) time worst case
• Sometimes useful to spend polynomial time preprocessing
to achieve local consistency before doing exponential search
• Arc consistency
–
–
–
–
Consider all pairs of vars
Can any values be eliminated from a domain ala FC
Propagate
O(d^2) time where d= number of vars
Forward Checking (FC)
• Perform Consistency Check Forward
• Whenever assign var a value
– Prune inconsistent values from
– As-yet unvisited variables
– Backtrack if domain of any var ever collapses
FC only visits consistent nodes
but not all such nodes
skips (2, 5, 3, 4) which CBJ visits
But FC can’t detect that
(2, 5, 3) inconsistent with {x5, x6 }
Q
Q
Q
Q
Q
Dynamic variable ordering
• In the N-queens examples we assumed
– First x1 then x2 then ...
• But this order not required
– Any order ok with respect to completeness
– A good order leads to huge speedup
• A good heuristic:
– Choose variable w/ minimum remaining values
• This is easy if one is doing FC
Number of Nodes Explored
BT=BM
More
BJ=BMJ=BMJ2
FC
CBJ=BM-CBJ=BM-CBJ2
FC-CBJ
Fewer
Number of Consistency Checks
BT
BJ
FC
BM
CBJ
BMJ
FC-CBJ
BMJ2
BM-CBJ
BM-CBJ2
Combinatorial Optimization
• Nonlinear Programs
• Convex Programs
– Local optimality  global optimality
– Kuhn Tucker conditions for optimality
• Linear Programs
– Simplex Algorithm
• Flow and Matching
• Integer Programming
Game Tree Search (java applet)
• Two person games: min (adversary) and max (me!)
• Max wants to win by expanding all possible moves of min,
and looks for the ‘best’ branch
• There is a utility function e(n) attached to each terminal
node
• Values of utility function propagates upward
– Max: chooses the max value of all children
– Min: chooses the min value of all children
• Tic-Tac-Toe
–
–
–
–
MAX = “X”, MIN = “O”
e (leaf node) = Total-Open-Paths(MAX) – Total-Open-Paths(MIN)
e (leaf node) = +/- infinity for winning nodes
e (MAX node) = MAX {e(succ nodes)}; e(MIN node) = MIN {}
Search Tree
Start node
MAX
1
X
?
-2
X
X
MIN
X
O
6-5=1
X
X
X
X
O
O
5-5=0
O
?
O
Tricks
• Alpha value: for MAX nodes, is a current lower bound on
its evaluation function (it never goes down for MAX)
• Beta value: for MIN nodes, is a current upper bound on its
evaluation function (it never goes up for MIN)
• Rule 1:
– if MAX is parent, MIN is a child and
– (alpha(MAX) > = beta(MIN),
– then terminate search on MIN
• Rule 2:
– if MIN is parent, MAX is a child, and
– (alpha(MAX) > = beta(MIN),
– Then terminate search on MAX
Watch Video