Transcript Unit2 - คณะเทคโนโลยีสารสนเทศและการสื่อสาร มหาวิทยาลัยพะเยา

Problem-Solving
อาจารย์อุทยั เซี่ยงเจ็น
สานักเทคโนโลยีสารสนเทศและการสื่ อสาร
มหาวิทยาลัยนเรศวร วิทยาเขตสารสนเทศพะเยา
Artificial Intelligence
1
Content
Decision Tree
Decision Table
Depth-First Search
Breadth-First Search
Heuristic
Artificial Intelligence
2
Notation Used in Decision Trees
A box
is used to show a choice that the
manager has to make.
A circle
is used to show that a probability
outcome will occur.
Lines
connect outcomes to their choice
or probability outcome.
Artificial Intelligence
3
Decision Tree Example 1
Joe’s garage is considering hiring another mechanic. The
mechanic would cost them an additional $50,000 / year in salary
and benefits.
If there are a lot of accidents in Providence this year, they
anticipate making an additional $75,000 in net revenue.
If there are not a lot of accidents, they could lose $20,000 off
of last year’s total net revenues.
Because of all the ice on the roads, Joe thinks that there will
be a 70% chance of “a lot of accidents” and a 30% chance of “fewer
accidents”.
Assume if he doesn’t expand he will have the same revenue
as last year.
Draw a Decision Tree for Joe and tell him what he should do.
Artificial Intelligence
4
70% chance of an increase
in accidents
Hire new
mechanic
Profit = $70,000
Cost = $50,000
30% chance of a
decrease in accidents
Profit = - $20,000
Don’t hire new
mechanic
Cost = $0
• Estimated value of “Hire Mechanic” =
NPV =.7(70,000) + .3(- $20,000) - $50,000 = - $7,000
• Therefore you should not hire the mechanic
Artificial Intelligence
5
Decision Tree Example 2
Mary is a manager of a gadget factory. Her factory has been
quite successful the past three years. She is wondering whether or
not it is a good idea to expand her factory this year. The cost to
expand her factory is $1.5M.
If she does nothing and the economy stays good and
people continue to buy lots of gadgets she expects $3M in revenue;
while only $1M if the economy is bad.
If she expands the factory, she expects to receive $6M if
economy is good and $2M if economy is bad.
She also assumes that there is a 40% chance of a good
economy and a 60% chance of a bad economy.
Draw a Decision Tree showing these choices.
Artificial Intelligence
6
Expand Factory
Cost = $1.5 M
40 % Chance of a Good
Economy
Profit = $6M
60% Chance Bad
Economy
Profit = $2M
Don’t Expand
Factory
Cost = $0
Good Economy
(40%)
Profit = $3M
Bad Economy (60%)
Profit = $1M
NPVExpand = (.4(6) + .6(2)) – 1.5 = $2.1M
NPVNo Expand = .4(3) + .6(1) = $1.8M
$2.1 > 1.8, therefore you should expand the factory
NPV = Net Present Value
7
Decision Table (If Conditions Then Actions)
Conditions
Condition Alternatives
Actions
Action Entries
Printer troubleshooter
Conditions
Printer does not print
Y
Y
Y
Y
N
N
N
N
A red light is flashing
Y
Y
N
N
Y
Y
N
N
Printer is unrecognized
Y
N
Y
N
Y
N
Y
N
Check the power cable
Actions
X
Check the printer-computer cable
X
X
Ensure printer software is installed
X
X
Check/replace ink
X
Check for paper jam
X
X
X
X
X
X
X
If Printer does not print AND A red light is flashing AND Printer is recognized
Then Check/replace ink AND Check for paper jam
8
Example
Rule 1:
IF
THEN
it is raining AND it is not warm today
take an umbrella AND take an overcoat.
IF
THEN
it is raining AND it is warm today
take a raincoat
IF
THEN
it is not raining AND the weather forecast is fine AND it is warm today
do not take an umbrella, a raincoat, or an overcoat
IF
THEN
it is not raining AND the weather forecast is fine AND it is not warm today
take an overcoat
IF
THEN
it is not raining AND the weather forecast is not fine AND it is warm today
take an umbrella
IF
THEN
if is not raining AND the weather forecast is not fine AND it is not warm today
take an umbrella AND take an overcoat
Rule 2:
Rule 3:
Rule 4:
Rule 5:
Rule 6:
9
Example
Weather Forecast
Conditions
It is raining
Y
Y
Y
Y
N
N
N
N
the weather forecast is fine
Y
Y
N
N
Y
Y
N
N
It is warm today
Y
N
Y
N
Y
N
Y
N
X
X
Actions
X
X
Take an umbrella
X
Take A raincoat
Take An overcoat
X
X
Artificial Intelligence
X
X
X
10
Why Search?
In many tasks, we know what a solution looks
like, but do not have an algorithm that
produces a solution.
– Goal + preferences
Search is a general problem solving
technique for this kind of situations.
Search Problem:
– Input: Initial State + Goal (utility) + actions (state
transitions)
– Output: A sequence of actions to reach the goal.
Artificial Intelligence
11
Example: Travel Task
Artificial Intelligence
12
Clean House Task
Artificial Intelligence
13
Vacuum Cleaner Space
Artificial Intelligence
14
Search Problem
State space
Initial state
Successor function
Goal test
Path cost
Artificial Intelligence
15
Example: 8-queens
Place 8 queens in a chessboard so that no two queens
are in the same row, column, or diagonal (ทแยง).
Not a solution
Not a solution
What is solution?
Artificial Intelligence
16
Example: Robot navigation
What is the state space?
Artificial Intelligence
17
Example: Robot navigation
Cost of one horizontal/vertical step = 1
Cost of one diagonal step = 2
Artificial Intelligence
18
Example: Robot navigation
Artificial Intelligence
19
Example: Robot navigation
Artificial Intelligence
20
Example: Robot navigation
Cost of one step = ???
Artificial Intelligence
21
Example: Robot navigation
Artificial Intelligence
22
Example: Robot navigation
Artificial Intelligence
23
Example: Robot navigation
Cost of one step: length of segment
Artificial Intelligence
24
Example: Robot navigation
Artificial Intelligence
25
Example: Assembly Planning
Initial state
Complex function:
it must find if a collision-free
merging motion exists
Goal state
Successor function:
• Merge two subassemblies
Artificial Intelligence
26
Example: Assembly Planning
Artificial Intelligence
27
Example: Assembly Planning
Artificial Intelligence
28
Assumptions in Basic Search
The environment is static
The environment is discretizable
The environment is observable
The actions are deterministic
 open-loop solution
Artificial Intelligence
29
Search Problem Variants
One or several initial states
One or several goal states
The solution is the path or a goal node
– In the 8-puzzle problem, it is the path to a
goal node
– In the 8-queen problem, it is a goal node
Any, or the best, or all solutions
Artificial Intelligence
30
Important Parameters
Number of states in state space
Size of memory needed to store a state
Running time of the successor function
Artificial Intelligence
31
Applications
Route finding: airline travel,
telephone/computer networks
Pipe routing, VLSI routing
Pharmaceutical drug design
Robot motion planning
Video games
Artificial Intelligence
32
Cannibals and Missionaries
http://www.plastelina.net/examples/games/game2.html
Artificial Intelligence
33
A Starter Activity
Cannibals and Missionaries
–
–
–
–
Three missionaries and three cannibals
Want to cross a river using one canoe.
Canoe can hold up to two people.
Can never be more cannibals than missionaries on
either side of the river.
– Get all safely across the river without any
missionaries being eaten.
Find a solution…
Artificial Intelligence
34
Problem Types
Deterministic, fully observable  single-state
problem
Non-observable  conformant problem
Nondeterministic and/or partially observable 
contingency problem
Unknown state space  exploration problem
Artificial Intelligence
35
Single-State Problem Formulation
A problem is defined by four items:
1. initial state
2. successor function (which actually defines all
reachable states)
3. goal test
4. path cost (additive)
e.g., sum of distances, number of
actions executed, etc.
C(x,a,y) is the step cost, assumed to be
0
Artificial Intelligence
36
Problem Representation : Cannibals
and Missionaries
Initial State
– We can show number of cannibals,
missionaries and canoes on each side of the
river.
– Start state is therefore:
[3,3,1,0,0,0]
Artificial Intelligence
37
Problem Representation : Cannibals
and Missionaries
Initial State
– However, since the system is closed, we only
need to represent one side of the river, as we
can deduce the other side.
– We will represent the finishing side of the
river, and omit the starting side.
– So start state is:
[0,0,0]
Artificial Intelligence
38
Problem Representation : Cannibals
and Missionaries
Successor Function
– There are five actions we can represent
1. Move one cannibal across the river.
2. Move two cannibals across the river.
3. Move one missionary across the river.
4. Move two missionaries across the river.
5. Move one missionary and one cannibal.
Artificial Intelligence
39
Problem Representation : Cannibals
and Missionaries
Successor Function
– To be a little more mathematical/computer
like, we want to represent this in a true
successor function format…
S(state)  state
1. Move one cannibal across the river.
S([x,y,0])  [x+1,y,1]
S([x,y,1])  [x-1,y,0]
[Note, this is a slight simplification.
Obviously, 0  x, y, x+1, and x-1  3 ]
Artificial Intelligence
40
Problem Representation : Cannibals
and Missionaries
Successor Function
– To be a little more mathematical/computer
like, we want to represent this in a true
successor function format…
S(state)  state
1. Move one cannibal across the river.
S([x,y,0])  [x+1,y,1]
S([x,y,1])  [x-1,y,0]
You write the other four functions…
Artificial Intelligence
41
Problem Representation : Cannibals
and Missionaries
Successor Function
S([x,y,0])  [x+1,y,1]
S([x,y,1])  [x-1,y,0]
S([x,y,0])  [x+2,y,1]
S([x,y,1])  [x-2,y,0]
S([x,y,0])  [x,y+1,1]
S([x,y,1])  [x,y-1,0]
S([x,y,0])  [x,y+2,1]
S([x,y,1])  [x,y-2,0]
S([x,y,0])  [x+1,y+1,1]
S([x,y,1])  [x-1,y-1,0]
Artificial Intelligence
42
Problem Representation : Cannibals
and Missionaries
Successor Function
S([x,y,0])  {[x+1,y,1] , [x+2,y,1] , [x,y+1,1] , [x,y+2,1] ,
[x+1,y+1,1] }
S([x,y,1])  {[x-1,y,0] , [x-2,y,0] , [x,y-1,0] , [x,y-2,0] , [x-1,y1,0] }
Where valid states [a,b,c] are those such that :
0a3
0b3
0c1
Artificial Intelligence
43
Problem Representation : Cannibals
and Missionaries
Successor Function
S([x,y,0])  {[x+1,y,1] , [x+2,y,1] , [x,y+1,1] , [x,y+2,1] ,
[x+1,y+1,1] }
S([x,y,1])  {[x-1,y,0] , [x-2,y,0] , [x,y-1,0] , [x,y-2,0] , [x-1,y1,0] }
Where valid states [a,b,c] are those such that :
0a3
0b3
0c1
Actually one more set of “constraints” we will get to later.
Artificial Intelligence
44
Problem Representation : Cannibals
and Missionaries
Goal State
– [3,3,1]
Artificial Intelligence
45
Problem Representation : Cannibals
and Missionaries
Path Cost
– One unit per trip across the river.
Artificial Intelligence
46
Problem Representation : Cannibals
and Missionaries
Initial State
–
[0,0,0]
Successor Function
S([x,y,0])  {[x+1,y,1] , [x+2,y,1] , [x,y+1,1] , [x,y+2,1] ,
[x+1,y+1,1] }
S([x,y,1])  {[x-1,y,0] , [x-2,y,0] , [x,y-1,0] , [x,y-2,0] , [x1,y-1,0] }
Goal State
–
[3,3,1]
Path Cost
–
One unit per trip across the river.
Artificial Intelligence
47
Search by generating states
3
2
1
5
4
100
6
1 --> 2
2 --> 5
1 -->6
3 --> 5
2 --> 3
5 --> 4
Artificial Intelligence
48
Basic concepts (1)
State: finite representation of the world at a
given time.
Operator: a function that transforms a state
into another (also called rule, transition,
successor
function, production, action).
Initial state: world state at the beginning.
Goal state: desired world state (can be several)
Goal test: test to determine if the goal has been
reached.
Artificial Intelligence
49
Basic concepts (2)
Reachable goal: a state for which there exists a
sequence of operators to reach it.
State space: set of all reachable states from
initial state (possibly infinite).
Cost function: a function that assigns a cost
to each operation.
Performance:
– cost of the final operator sequence
– cost of finding the sequence
Artificial Intelligence
50
Problem formulation
The first taks is to formulate the problem in
terms of states and operators
Some problems can be naturally defined this
way, others not!
Formulation makes a big difference!
Examples:
– water jug problem, tic-tac-toe, 8-puzzle, 8-queen
problem, cryptoarithmetic
– robot world, travelling salesman, part assembly
Artificial Intelligence
51
Example 1: water jug (1)
Given 4 and 3 liter jugs, a water pump, and a sink,
how do you get exactly two liters into the 4 liter jug?
4
3
Jug 1
Jug 2
Pump
Sink
• State: (x,y) for liters in jugs 1 and 2, integers 0 to 4
• Operations: empty jug, fill jug, pour water between jugs
• Initial state: (0,0); Goal state: (2,n)
Artificial Intelligence
52
Water jug operations
1. (x, y | x < 4)
(4, y)
Fill 4
a move
2. (x, y | y < 3)
(x, 3)
Fill 3
3. (x, y | x > 0)
(0, y)
Dump 4
b move
4. (x, y | y > 0)
(x, 0)
Dump 3
5. (x, y | x+y >=4 and y>0) (4, y - (4 - x))
Pour from 3 to 4 until 4 is full
6. (x, y | x+y >=3 and x>0) (x - (3 - y), 3)
Pour from 4 to 3 until 3 is full
7. (x, y | x+y <=4 and y>0) (x+y, 0)
Pour all water from 3 to 4
Artificial Intelligence
53
Water Jug Problem: one solution
Gallons in y
0
Trasition Rule
2
fill 3
7
pour from 3 to 4
0
2
fill 3
3
5
2
3
pour from 3 to 4
until 4 is full
dump 4
2
0
7
3
Artificial Intelligence
pour from 3 to 4
54
Example 2: cryptoarithmetic
Assign numbers to letters so that the sum is correct
FO RTY
+
TEN
+
TEN
S I XTY
29786
+
850
+
850
31486
Solution
F=2, O=9
R=7, T=8
Y=6, E=5
N=0, I=1
X=4
• State: a matrix, with letters and numbers
• Operations: replace all occurrences of a letter with a
digit not already there
• Goal test: only digits, sum is correct
Artificial Intelligence
55
Example 3: 8-puzzle
9! =362,880 states
• State: a matrix, with numbers and the empty space
• Operation: exchange tile with adjacent empty space
• Goal test: state matches final state; cost is # of moves
Artificial Intelligence
56
Other search problems
Path finding problems in graphs: shortest
path, shortest circuit visiting each node once.
1
a
b
10
2
3
9
s
4
6
7
5
c
2
d
Automatic assembly, protein design, Internet search
Artificial Intelligence
57
Graph representation
Nodes represent states
G(V,E)
Directed edges represent operation applications - labels indicate operation applied
Initial, goal states are start
and end nodes
G (V , E )
Edge weight: cost of applying an operator
Search: find a path from start to end node
Graph is generated dynamically as we search
Artificial Intelligence
58
Graph characteristics
A tree, directed acyclic graph, or graph with
cycles -- depends on state repetitions
Number of states (n)
– size of problem space, possibly infinite
Branching factor (b)
– # of operations that can be applied at each state
– maximum number of outgoing edges
Depth level (d)
– number of edges from the initial state
Artificial Intelligence
59
Water jug problem: tree
a
b
(0,0)
(0,3)
(4,0)
b
(4,3)
(0,3)
a
(0,0)
(1,3)
(1,0)
(4,0)
(2,0)
(4,3)
(0,0)
(3,0)
(4,3)
(2,3)
Artificial Intelligence
60
Water jug problem: graph
(0,0)
(4,0)
(1,3)
(0,3)
(4,3)
Artificial Intelligence
(3,0)
61
Data structures
State: structure with world parameters
Node:
– state, depth level
– # of predecesors, list of ingoing edges
– # of successors, list of outgoing edges
Edge: from and to state, operation number, cost
Operation: from state to state, matching function
Hash table of operations
Queue to keep states to be expanded
Artificial Intelligence
62
General search algorithm
function General-Search(problem) returns solution
nodes := Make-Queue(Make-Node(Initial-State(problem))
loop do
if nodes is empty then return failure
node := Remove-Front (nodes)
if Goal-Test[problem] applied to State(node) succeeds
then return node
new-nodes := Expand (node, Operators[problem]))
nodes := Insert-In-Queue(new-nodes)
end
Artificial Intelligence
63
Search issues: graph generation
Tree vs. graph
– how to handle state repetitions?
– what to do with infinite branches?
How to select the next state to expand
– uninformed vs. informed heuristic search
Direction of expansion
– from start to goal, from goal to start, both.
Efficiency
– What is the most efficient way to search?
Artificial Intelligence
64
Properties of search strategies
Completeness
– guarantees to find a solution if a solution exists, or
return fail if none exists
Optimality
– Does the strategy find the optimal solution
Time complexity
– # of operations applied in the search
Space complexity
– # of nodes stored during the search
Artificial Intelligence
65
Factors that affect search efficiency
1. More start or goal states? Move towards the
larger set
G
I
G
I
G
I
G
Artificial Intelligence
I
66
Factors that affect search efficiency
2. Branching factor: move in the direction with the
lower branching factor
G
I
G
I
Artificial Intelligence
67
Uninformed search methods
No a-priori knowledge on which node is best to
expand (ex: crypto-arithmetic problem)
Methods
–
–
–
–
–
Depth-first search (DFS)
Breath-first search (BFS)
Depth-limited search
Iterative deepening search
Bidirectional search
Artificial Intelligence
68
A graph search problem...
4
A
4
B
C
3
S
G
G
5
5
4
D
2
E
4
Artificial Intelligence
F
3
69
… becomes a tree
S
A
B
C
11
D
D
E
D F
14
G
19
A
E
B
F
C
19
G
17
E
B
C
17
B
E
F
A C
15 15
G
13
F
G 25
Artificial Intelligence
70
Depth first search
Dive into the search tree as far as you can, backing up
only when there is no way to proceed
function Depth-First-Search(problem) returns solution
nodes := Make-Queue(Make-Node(Initial-State(problem))
loop do
if nodes is empty then return failure
node := Remove-Front (nodes)
if Goal-Test[problem] applied to State(node) succeeds
then return node
new-nodes := Expand (node, Operarors[problem]))
nodes := Insert-At-Front-of-Queue(new-nodes)
end
Artificial Intelligence
71
Depth-first search
S
A
B
C
11
D
14
D
D
E
A
E
F
B
F
G
19
C
19
G
17
E
B
C
17
B
E
A
15
F
C G
15 13
F
G 25
Artificial Intelligence
72
Breath-first search
Expand the tree in successive layers, uniformly looking
at all nodes at level n before progressing to level n+1
function Breath-First-Search(problem) returns solution
nodes := Make-Queue(Make-Node(Initial-State(problem))
loop do
if nodes is empty then return failure
node := Remove-Front (nodes)
if Goal-Test[problem] applied to State(node) succeeds
then return node
new-nodes := Expand (node, Operators[problem]))
nodes := Insert-At-End-of-Queue(new-nodes)
end
Artificial Intelligence
73
Breath-first search
S
A
B
C
11
D
D
E
D F
14
G
19
A
E
B
F
C
19
G
17
E
B
C
17
B
E
F
A C
15 15
G
13
F
G 25
Artificial Intelligence
74
Depth-limited search
Like DFS, but the search is limited to a predefined
depth.
The depth of each state is recorded as it is
generated. When picking the next state to expand,
only those with depth less or equal than the current
depth are expanded.
Once all the nodes of a given depth are explored,
the current depth is incremented.
Combination of DFS and BFS. Change the InsertQueue function in the algorithm above.
Artificial Intelligence
75
Depth-limited search
S
depth = 3
A
3
D
6
B
C
11
D
E
D F
14
G
19
A
E
B
F
C
19
G
17
E
B
C
17
B
E
F
A C
15 15
G
13
F
G 25
Artificial Intelligence
76
IDS: Iterative deepening search
Problem: what is a good depth limit?
Answer: make it adaptive!
Generate solutions at depth 1, 2, ….
function Iterative-Deepening-Search(problem) returns solution
nodes := Make-Queue(Make-Node(Initial-State(problem)
for depth := 0 to infinity
if Depth-Limited-Search(problem, depth) succeeds
then return its result
end
return failure
Artificial Intelligence
77
Iterative deepening search
S
S
S
A
Limit = 0
D
Limit = 1
S
S
A
Limit = 2
S
D
A
B
Artificial Intelligence
D
D
A
E
78
Iterative search is not as wasteful
as it might seem
The root subtree is computed every time instead
of storing it!
Most of the solutions are in the bottom leaves
anyhow: b + b2 + …+ bd = O(bd)
Repeating the search takes:
(d+1)1 + (d)b + (d - 1)b2 + … (1)bd = O(bd)
For b = 10 and d = 5 the number of nodes
searched up to level 5 is 111,111 vs. repeated
123,450 (only 11% more) !!
Artificial Intelligence
79
Bidirectional search
Expand nodes from the start and goal state
simultaneously. Check at each stage if the nodes of
one have been generated by the other. If so, the
path concatenation is the solution
• The
operators must be reversible
• single start, single goal
• Efficient check for identical states
• Type of search that happens in each half
Artificial Intelligence
80
Bidirectional search
S
A
B
C
11
D
D
E
D F
14
G
19
Forward
Backwards
A
E
B
F
C
19
G
17
E
B
C
17
B
E
F
A C
15 15
G
13
F
G 25
Artificial Intelligence
81
Comparing search strategies
bd+1
bd+1
bC/e
bC/e
Artificial Intelligence
82
Repeated states
Repeated states can the source of great
inefficiency: identical subtrees will be explored
many times!
A
B
C
A
B
C
C
B
C
C
How much effort to invest in detecting repetitions?
Artificial Intelligence
83
Strategies for repeated states
Do not expand the state that was just generated
– constant time, prevents cycles of length one, ie.,
A,B,A,B….
Do not expand states that appear in the path
– depth of node, prevents some cycles of the type
A,B,C,D,A
Do not expand states that were expanded before
– can be expensive! Use hash table to avoid looking at all
nodes every time.
Artificial Intelligence
84
Summary: uninformed search
Problem formulation and representation is key!
Implementation as expanding directed graph of
states and transitions
Appropriate for problems where no solution is
known and many combinations must be tried
Problem space is of exponential size in the
number of world states -- NP-hard problems
Fails due to lack of space and/or time.
Artificial Intelligence
85
Heuristic Search
Blind search totally ignores where the
goals are.
A heuristic function that gives us an
estimate of how far we are from a goal.
– Example:
How do we use heuristics?
Artificial Intelligence
86
Heuristic Function
Function h(N) that estimate the cost of the
cheapest path from node N to goal node.
Example: 8-puzzle
5
8
4 2 1
7 3 6
N
1 2 3 h(N) = number of misplaced tiles
=6
4 5 6
7 8
goal
Artificial Intelligence
87
Heuristic Function
Function h(N) that estimate the cost of the
cheapest path from node N to goal node.
Example: 8-puzzle
5
8
4 2 1
7 3 6
N
1 2 3 h(N) = sum of the distances of
every tile to its goal position
4 5 6
=2+3+0+1+3+0+3+1
7 8
= 13
goal
Artificial Intelligence
88
Greedy Best-First Search
Path search(start, operators, is_goal) {
fringe = makeList(start);
while (state=fringe.popFirst()) {
if (is_goal(state))
return pathTo(state);
S = successors(state, operators);
fringe =
insert(S,
fringe);
}
return NULL;
}
Order the nodes in the fringe in increasing values of h(N)
Artificial Intelligence
89
Robot Navigation
Artificial Intelligence
90
Robot Navigation
f(N) = h(N), with h(N) = Manhattan distance to the goal
8
7
7
6
5
4
5
4
3
3
2
6
7
6
8
7
3
2
3
4
5
6
5
1
0
1
2
4
5
6
5
4
3
2
Artificial Intelligence
3
4
5
6
91
Robot Navigation
f(N) = h(N), with h(N) = Manhattan distance to the goal
8
7
7
6
5
4
5
4
3
3
2
6
77
6
8
7
3
2
3
4
5
6
5
1
00
1
2
4
5
6
5
4
3
2
Artificial Intelligence
3
4
5
6
92
Properties of the Greedy Best-First
Search
If the state space is finite and we avoid repeated
states, the best-first search is complete, but in
general is not optimal
If the state space is finite and we do not avoid
repeated states, the search is in general not
complete
If the state space is infinite, the search is in
general not complete
Artificial Intelligence
93
Admissible heuristic
Let h*(N) be the cost of the optimal path
from N to a goal node
Heuristic h(N) is admissible if:
0  h(N)  h*(N)
An admissible heuristic is always
optimistic
Artificial Intelligence
94
8-Puzzle
5
8
1
2
3
6
4
2
1
4
5
7
3
N
6
7
8
goal
• h1(N) = number of misplaced tiles = 6 is admissible
• h2(N) = sum of distances of each tile to goal = 13
is admissible
• h3(N) = (sum of distances of each tile to goal)
+ 3 x (sum of score functions for each tile) = 49
is not admissible
Artificial Intelligence
95
A* Search
A* search combines Uniform-cost and Greedy
Best-first Search
Evaluation function:
f(N) = g(N) + h(N)
where:
– g(N) is the cost of the best path found so far to N
– h(N) is an admissible heuristic
– f(N) is the estimated cost of cheapest solution
THROUGH N
0 <   c(N,N’) (no negative cost steps).
Order the nodes in the fringe in increasing
values of f(N)
Artificial Intelligence
96
Completeness & Optimality of A*
Claim 1: If there is a path from the initial
to a goal node, A* (with no removal of
repeated states) terminates by finding the
best path, hence is:
– complete
– optimal
Artificial Intelligence
97
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
3+3
1+5
2+3
3+4
5+2
goal
0+4
3+2
1+3
2+3
4+1
5+0
3+4
1+5
2+4
Artificial Intelligence
98
Robot Navigation
f(N) = g(N)+h(N), with h(N) = Manhattan distance to goal
8+3
8 7+4
7 6+3
6+5
6 5+6
5 4+7
4 3+8
3 2+9
2 3+10
3 4
7+2
7
6+1
6
5
5+6
5 4+7
4 3+8
3
3 2+9
2 1+10
1 0+11
0 1
6
5
2
4
7+0
7 6+1
6
5
8+1
8 7+2
7 6+3
6 5+4
5 4+5
4 3+6
3 2+7
2 3+8
3 4
Artificial Intelligence
5
6
99
Robot navigation
f(N) = g(N) + h(N), with h(N) = straight-line distance from N to goal
Cost of one horizontal/vertical step = 1
Cost of one diagonal step = 2
Artificial Intelligence
100
Consistent Heuristic
The admissible heuristic h is consistent
(or satisfies the monotone restriction) if for
every node N and every successor N’ of N:
h(N)  c(N,N’) + h(N’)
N
c(N,N’)
(triangular inequality)
N’
h(N)
h(N’)
Artificial Intelligence
101
8-Puzzle
5
8
1
2
3
6
4
2
1
4
5
7
3
N
6
7
8
goal
• h1(N) = number of misplaced tiles
• h2(N) = sum of distances of each tile to goal
are both consistent
Artificial Intelligence
102
Claims
If h is consistent, then the function f along
any path is non-decreasing:
N
f(N) = g(N) + h(N)
f(N’) = g(N) +c(N,N’) + h(N’)
h(N)  c(N,N’) + h(N’)
f(N)  f(N’)
c(N,N’)
N’
h(N)
h(N’)
If h is consistent, then whenever A* expands
a node it has already found an optimal path to
the state associated with this node
Artificial Intelligence
103
Avoiding Repeated States in A*
If the heuristic h is consistent, then:
Let CLOSED be the list of states
associated with expanded nodes
When a new node N is generated:
– If its state is in CLOSED, then discard N
– If it has the same state as another node in the
fringe, then discard the node with the largest f
Artificial Intelligence
104
Complexity of Consistent A*
Let s be the size of the state space
Let r be the maximal number of states that
can be attained in one step from any state
Assume that the time needed to test if a
state is in CLOSED is O(1)
The time complexity of A* is O(s r log s)
Artificial Intelligence
105
Heuristic Accuracy
h(N) = 0 for all nodes is admissible and
consistent. Hence, breadth-first and uniformcost are particular A* !!!
Let h1 and h2 be two admissible and
consistent heuristics such that for all nodes N:
h1(N)  h2(N).
Then, every node expanded by A* using h2 is
also expanded by A* using h1.
h2 is more informed than h1
– h2 dominates h1
Which heuristic for 8-puzzle is better?
Artificial Intelligence
106
Iterative Deepening A* (IDA*)
Use f(N) = g(N) + h(N) with admissible and
consistent h
Each iteration is depth-first with cutoff on
the value of f of expanded nodes
Artificial Intelligence
107
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=4
6
Artificial Intelligence
108
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=4
4
6
6
Artificial Intelligence
109
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=4
4
5
6
6
Artificial Intelligence
110
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
5
4
Cutoff=4
4
5
6
6
Artificial Intelligence
111
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
6
5
4
5
6
6
4
Cutoff=4
Artificial Intelligence
112
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
6
Artificial Intelligence
113
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
4
6
6
Artificial Intelligence
114
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
4
5
6
6
Artificial Intelligence
115
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
4
5
7
6
6
Artificial Intelligence
116
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
5
4
5
7
6
6
Artificial Intelligence
117
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
5
4
5
5
7
6
6
Artificial Intelligence
118
8-Puzzle
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
4
Cutoff=5
5
4
5
5
7
6
6
Artificial Intelligence
119
About Heuristics
Heuristics are intended to orient the search along
promising paths
The time spent computing heuristics must be
recovered by a better search
After all, a heuristic function could consist of solving
the problem; then it would perfectly guide the search
Deciding which node to expand is sometimes called
meta-reasoning
Heuristics may not always look like numbers and
may involve large amount of knowledge
Artificial Intelligence
120
When to Use Search Techniques?
The search space is small, and
– There is no other available techniques, or
– It is not worth the effort to develop a more
efficient technique
The search space is large, and
– There is no other available techniques, and
– There exist “good” heuristics
Artificial Intelligence
121
Summary
Heuristic function
Greedy Best-first search
Admissible heuristic and A*
A* is complete and optimal
Consistent heuristic and repeated states
Heuristic accuracy
IDA*
Artificial Intelligence
122