COMP3308/COMP3608, Lecture 3a
ARTIFICIAL INTELLIGENCE
A* Algorithm
Reference: Russell and Norvig, ch. 3
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 1
Outline
• A* search algorithm
• How to invent admissible heuristics
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 2
A* Search
• UCS minimizes the cost so far g(n)
• GS minimizes the estimated cost to the goal h(n)
• A* combines UCS and GS
• Evaluation function: f(n)=g(n)+h(n)
• g(n) = cost so far to reach n
• h(n) = estimated cost from n to the goal
• f(n) = estimated total cost of path through n to the goal
S
22
A (3) B
837
4
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 3
A* Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021
4
A* Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 5
A* Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 6
A* Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 7
A* Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 8
A* Search for Romania Example
Bucharest is selected for expansion and it is a goal node => stop Solution path: Arad-Sibiu-Riminicu Vilcea-Pitesti-Bucharest, cost=418
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 9
A* Search – Another Example
• Given:
• Goal nodes: C, I, E and K
• Step path cost: along the links
• h value of each node: in brackets ()
• Same priority nodes -> expand the last added first
• RunA*
• list of expanded nodes =?
• solution path =?
• cost of the solution:=?
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021
10
( 0)
( 3)
(0)
• Fringe: S
• Expanded: nill
Solution
S
22
A (3) B
837
563
(0)
CD(5) EFG
(2)
(0)
(2)
4
(4)
3
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 11
Solution
• Fringe: (A, 5), (B, 6) //keep the fringe in sorted order
• Expanded: S
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 12
Solution
• Fringe: (B, 6), (C, 10), (D, 10) //the added children are in blue
• Expanded: S, (A, 5)
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 13
Solution
• Fringe: (G, 7), (F, 8), (E, 9), (C, 10), (D, 10)
• Expanded: S, (A, 5), (B, 6)
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 14
Solution
• Fringe: (K, 8), (F, 8), (E, 9), (C, 10), (D, 10)
• Expanded: S, (A, 5), (B, 6), (G, 7)
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 15
Solution
• K is selected; Goal node? Yes => stop
• Expanded: S, A, B, G, K
• Solution path: SBGK, cost=8
• Is this the optimal solution=?
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 16
A* and UCS
• UCS is a special case of A* when h(n) =?
• In other words, when will A* behave as UCS?
g=2
h=3 f=2+3
Hint:
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 17
• • •
UCS uses which cost? A* uses which cost?
Relation between the 2 costs =?
A* and UCS (Answer)
• UCS is a special case of A* when h(n) =?
• In other words, when will A* behave as UCS?
g=2
h=3 f=2+3
• •
• • •
UCS uses which cost? A* uses which cost?
UCS:g(n) A*:f(n)=g(n)+h(n)
if h(n)=0 => f(n)=g(n), i.e. A* becomes UCS
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 18
• BFS is a special case of A* when
• When will A* behave as BFS?
f(n) =?
A* and BFS
g=2
h=3 f=2+3
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 19
A* and BFS (Answer)
• BFS is a special case of A* when f(n) =?
f=3
f=2 f=3
f=2 f=3 f=3
f=1
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 20
when f(n)=depth(n)
•
And also when this assumption for resolving ties is true: among nodes with the same priority, the left most is expanded first
BFS, UCS and A*
• BFS is a special case of A* when f(n)=depth(n)
• BFS is also a special case of UCS when g(n)=depth(n)
• UCS is a special case of A* when h(n)=0
f=1
BFS f(n)=depth(n)
UCS f(n)=g(n), h(n)=0
A* f(n)=g(n)+h(n)
f=3
f=2 f=3
f=2 f=3 f=3
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 21
Admissible Heuristic
• A heuristic h(n) is admissible if for every node n:
• h(n) h*(n) where h*(n) is the true cost to reach a goal from n
• i.e. the estimate to reach a goal is smaller than (or equal to) the true cost to reach a goal
• Admissible heuristics are optimistic – they think that the cost of solving the problem is less than it actually is!
• e.g. the straight line distance heuristic hSLD(n) never overestimates the actual road distance (cost from n to goal) => it is admissible
• Theorem: If h is an admissible heuristic, then A* is complete and optimal
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 22
Is h Admissible for Our Example?
• No need to check goal nodes (h=0 for them) and nodes that are
not on a goal path
• h(S)=5<=8 (shortest path from S to a goal, i.e. to goal K)
• h(B)=4<=6
• h(G)=2<=3
• h(A)=3<=8
• h(D)=5<=5
• => h is admissible
S (5) 22
A (3) B
837
3 5 6 3
HIJK
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021
23
Optimality of A* – Proof
Optimal solution = the shortest (lowest cost) path to a goal node
Idea: Suppose that some sub-optimal goal G2 has been generated and it is in
the fringe. We will show that G2 can not be selected from the fringe. Given:
G – the optimal goal
G2 – a sub-optimal goal h is admissible
To prove: G2 can not be selected from the fringe for expansion Proof:
Let n be an unexpanded node in the fringe such that n is on the optimal (shortest) path to G (there must be such a node). We will show that f(n)
4) => f(G2)>f(G) by substituting 1) and 2) into 3)
COMP3608 only
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 25
Optimality of A* – Proof (3)
Compare f(n) and f(G)
5) f(n)=g(n)+h(n) (by definition)
6) h(n) <= h*(n) where h*(n) is the true cost from n to G (as h is admissible)
7) => f(n)<=g(n) + h*(n) (5 & 6)
8) = g(G) path cost from S to G via n
9) g(G) = f(G) as f(G)=g(G)+h(G)=g(G)+0 as h(G)=0, G is a goal 10) => f(n)<=f(G) (7,8,9)
Thus f(G)
expansion
COMP3608 only
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 26
Admissible Heuristics for 8-puzzle – h1
• h1(n) = number of misplaced tiles
• h1(Start) = ?
• 7 (7 of 8 tiles are out of position) • Why is h1 admissible?
• recall: admissible heuristics are optimistic – they never overestimate the number of steps to the goal
• h1: any tile that is out of place must be moved once
• true cost: higher; any tile that is out of place must be moved
at least once
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 27
Admissible Heuristics for 8-puzzle – h2
• h2(n) = the sum of the distances of the tiles from their goal positions (Manhattan distance)
• note: tiles can move only horizontally and vertically • h2(Start) = ?
• 18 (2+3+3+2+4+2+0+2) • Why is h2 admissible?
• h2: at each step move a tile to an adjacent position so that it is 1
step closer to its goal position and you will reach the solution in
h2 steps, e.g. move tile 1 up, then left
• True cost: higher as
moving a tile to an adjacent position is not always possible; depends on the position of the blank tile
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021 28
Dominance
• Definition of a dominant heuristic:
• Given 2 admissible heuristics h1 and h2 ,
• h2 dominates h1 if for all nodes n h2(n) h1(n)
• Theorem: A* using h2 will expand fewer nodes than A* using h1 (i.e. h2 is better for search)
• n with f(n) < f* will be expanded (f*=cost of optimal solution path)
• => n with h(n) < f*- g(n) will be expanded
• but h2(n) h1(n)
• => n expanded by A*using h2 will also be expanded by h1 and h1 may also expand other nodes
• Typical search costs for 8-puzzle with d=14:
IDS = 3 473 941 nodes, A*(h1) = 539 nodes, A*(h2) = 113 nodes
• Dominant heuristics give a better estimate of the true cost to a goal G Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 29
Question
• Suppose that h1 and h2 are two admissible heuristics for a given problem. We define two other heuristics:
• h3=min(h1, h2)
• h4= max(h1, h2)
• Q1. Is h3 admissible?
• Q2. Is h4 admissible?
• Q3. Which one is a better heuristic – h3 or h4?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 30
Answer
• Suppose that hl and h2 are two admissible heuristics for a given problem. We define two other heuristics:
• h3=min(hl, h2)
• h4= max(hl, h2)
• Q1. Is h3 admissible?
• Q2. Is h4 admissible?
• Q2. Which one is a better heuristic – h3 or h4?
Answer:
• Q1 and Q2: Both h3 and h4 are admissible as their values
are never greater than an admissible value h1 or h2
• Q3: h4 is a better heuristic since it is closer to the real cost, i.e. h4 is a dominant heuristic since h4(n) h3(n)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 31
How to Invent Admissible Heuristics?
• By formulating a relaxed version of the problem and finding the exact solution. This solution is an admissible heuristic.
• Relaxed problem – a problem with fewer restrictions on the actions
• 8-puzzle relaxed formulation 1:
• a tile can move anywhere
• How many steps do we need to reach the goal state from the initial state? (=solution)
• solution = the number of misplaced tiles = h1(n)
• 8-puzzle relaxed formulation 2:
• a tile can move to any adjacent square
• solution = Manhattan distance = h2(n)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 32
Admissible Heuristics from Relaxed Problems
• Theorem: The optimal solution to a relaxed problem is an admissible heuristic for the original problem
• Intuitively, this is true because:
The optimal solution to the original problem is also a solution to the relaxed version (by definition) => it must be at least as expensive as the optimal solution to the relaxed version => the solution to the relaxed version is less or equally expensive than the solution to the original problem => it is an admissible heuristic for the original problem
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 33
•
Constructing Relaxed Problems Automatically
Relaxed problems can be constructed automatically if the problem definition is written in a formal language
• Problem:
A tile can move from square A to square B if A is adjacent to B and B is blank
• 3 relaxed problems generated by removing 1 or both conditions:
1) A tile can move from square A to square B if A is adjacent to B
2) A tile can move from square A to square B if B is blank
3) A tile can move from square A to square B (always, no conditions)
ABSOLVER (1993) is a program that can generate heuristics automatically using the “relaxed problem” method and other methods
• Generated a new heuristic for the 8-puzzle that was better than any existing heuristic
• Found the first useful heuristic for the Rubik’s cube puzzle
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 34
•
No Single Clearly Best Heuristic?
• Often we can’t find a single heuristic that is clearly the best (i.e. dominant)
• We have a set of heuristics h1, h2, …, hm but none of them dominates any of the others
• Which should we choose?
• Solution: define a composite heuristic:
h(n)=max{h1(n), h2(n), …, hm(n)}
At a given node, it uses whichever heuristic is most accurate (dominant)
• Is h(n) admissible?
Yes, because the individual heuristics are admissible
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 35
• • • •
•
Learning Heuristics from Experience
Example: 8-puzzle
Experience = many 8-puzzle solutions (paths from A to B) Each previous solution provides a set of examples to learn h Each example is a pair (state, associated h)
• h is known for each state, i.e. we have a labelled dataset
The state is suitably represented as a set of useful features, e.g.
• f1 = number of misplaced tiles
• f2 = number of adjacent tiles that should not be adjacent
• h is a function of the features but we don’t know how exactly it depends
on them, we will learn this relationship from the data
We can generate e.g. 100 random 8-puzzle configurations and record the values of f1, f2 and h to form a training set of examples. Using this training set, we build a classifier.
training data
•
•
We use this classifier on new data, i.e. given f1 and f2, to predict h which is
unknown. No guarantee that the learned heuristic is admissible or consistent.
Ex.#
f1
f2
h
Ex1
7
8
14
…
Ex100
5
2
5
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 36
Back to A* and another property of the heuristics…
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 37
Consistent (Monotonic) Heuristic
• Consider a pair of nodes ni and nj, where ni is the parent of nj ni h(ni) parent
cost(ni,nj)
nj h(nj) child
• h is a consistent (monotonic) heuristic, if for all such pairs in the search
graph the following triangle inequality is satisfied:
h(ni) cost(ni,nj)+ h(nj) for all n
parent
ni cost(ni,nj)
nj
h(nj)
child
h(ni)
h=10 cost=3
h=9
consistent 10<=9+3
h=10 cost=3
h=5 not consistent
10 <= 5+3
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021
38
Another Interpretation of the Triangle Inequality
h(ni) cost(ni,nj)+ h(nj) for all n parent child
• => h(nj) h(ni) – cost(ni,nj) , i.e. along any path our estimate of the remaining cost to the goal cannot decrease by more than the arc cost
ni
h(ni) parent h(nj) child
cost(ni,nj) nj
h=10 cost=3
h=9 consistent
h=10 cost=3
h=5 not consistent
5 10-3 39
cost(ni,nj) ni
n j
h(nj)
9 10-3
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021
h(ni)
Consistency Theorems
• Theorem 1: If h(n) is consistent, then f(nj) f(ni), i.e. f is non-
decreasing along any path
Given: h(ni) c(ni, nj)+h(nj) To prove: f(nj) f(ni)
Proof: f(nj)=g(nj)+h(hj)=
=g(ni)+c(ni,nj)+h(nj)=
g(ni) + h(ni) =
=f(ni) =>f(nj) f(ni)
child parent
ni cost(ni,nj)
nj
deff. h(n) consistent
h(ni) parent h(nj) child
• Theorem 2: If f(nj) f(ni), i.e. f is non-decreasing along any path, then h(n) is consistent
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 40
Admissibility and Consistency
• Consistency is the stronger condition • Theorems:
• If a heuristic is consistent, it is also admissible consistent => admissible
• If a heuristic is admissible, there is no guarantee that it is consistent
admissible > consistent
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 41
• •
•
A* uses the f-cost to select nodes for expansion
If h is consistent, the f-costs are non-decreasing => we can draw f-contours in the state space
A* expands nodes in order of increasing f-values, i.e.
• It gradually adds f-contours of nodes
• Nodes inside a contour have f-cost less than or equal to the contour value
Completeness of A* with Consistent Heuristic – Intuitive Idea
•
Completeness – as we add bands of increasing f, we must eventually reach a band where f=h(G)+g(G)=h(G)
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3a, 2021
42
• •
Optimality of A* with Consistent Heuristic – Intuitive Idea
A* finds the optimal solution, i.e. the one with smallest path cost g(n) among all solutions
The first solution must be the optimal one, as subsequent contours will have higher f-cost, and thus higher g-cost (h(n)=0 for goal nodes):
• Bands f1
• Admissible > consistent
• Consistent => admissible
• Dominant heuristic
• given 2 admissible heuristics h1 and h2, h2 is dominant if it gives a
better estimate of the true cost to a goal node
• A* with a dominant heuristic will expand fewer nodes
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 46
Summary of A* (2)
• If h(n) is admissible, A* is optimal
• If h(n) is consistent, A* is optimally efficient – A* will expand less or
equal number of nodes than any other optimal algorithm using h(n)
• However, theoretical completeness and optimality do not mean practical completeness and optimality if it takes too long to get the solution (time and space are exponential)
• => If we can’t design an accurate admissible or consistent heuristic, it may be better to settle for a non-admissible heuristic that works well in practice or for a local search algorithm (next lecture) even though completeness and optimality are no longer guaranteed.
• => Also, although dominant (i.e. good) heuristics are better, they may need a lot of time to compute; it may be better to use a simpler heuristic – more nodes will be expanded but overall the search may be faster.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2021 47