程序代写代做代考 algorithm Microsoft PowerPoint - ai3a.pptx

Microsoft PowerPoint – ai3a.pptx

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, 2018 1

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018 2

Outline
• A* search algorithm
• How to invent admissible heuristics

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018 3

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

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018
4

A* Search for Romania Example

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* Search for Romania Example

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* Search for Romania Example

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* Search for Romania Example

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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, 2018

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

• Run A*
• list of expanded nodes =?
• solution path =?
• cost of the solution:=?

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution

• Fringe: S
• Expanded: nill

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution

• Fringe: (A, 5), (B, 6) //keep the fringe in sorted order
• Expanded: S

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution

• Fringe: (B, 6), (C, 10), (D, 10) //the added children are in blue
• Expanded: S, (A, 5)

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution

• Fringe: (G, 7), (F, 8), (E, 9), (C, 10), (D, 10)
• Expanded: S, (A, 5), (B, 6)

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution

• Fringe: (K, 8), (F, 8), (E, 9), (C, 10), (D, 10)
• Expanded: S, (A, 5), (B, 6), (G, 7)

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Solution
• K is selected; Goal node? Yes => stop

• Expanded: S, A, B, G, K
• Solution path: SBGK, cost=8

• Is this the optimal solution=?

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* and UCS
• UCS is a special case of A* when h(n) =?
• In other words, when will A* behave as UCS?

h=3
f=2+3

g=2 Hint:
• UCS uses which cost?
• A* uses which cost?
• Relation between the 2

costs =?

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* and UCS (Answer)
• UCS is a special case of A* when h(n) =?
• In other words, when will A* behave as UCS?

• 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

h=3
f=2+3

g=2

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* and BFS
• BFS is a special case of A* when f(n) =?
• When will A* behave as BFS?

h=3
f=2+3

g=2

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

A* and BFS (Answer)
• BFS is a special case of A* when f(n) =?

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

f=1

f=2 f=2

f=3 f=3 f=3 f=3

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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

BFS
f(n)=depth(n)

UCS f(n)=g(n),
h(n)=0

A*
f(n)=g(n)+h(n)

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

f=1

f=2 f=2

f=3 f=3 f=3 f=3

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 than A* is complete and
optimal

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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

2 2

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

3 5 3

(5)

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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)g(G) as G2 is suboptimal
4) => f(G2)>f(G) by substituting 1) and 2) into 3)

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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) n will be expanded not G2; A* will not select G2 for

expansion

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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, 2018

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, 2018

• Two 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)  n with h(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

Dominance

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Question
• Suppose that h1 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?
• Q3. Which one is a better heuristic – h3 or h4?

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

• 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(b)
31

Answer

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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
• 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, 2018

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 as 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, 2018

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

• 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, 2018

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, 2018

Learning Heuristics from Experience
• Example: 8-puzzle
• Experience = many 8-puzzle solutions
• 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 data
Ex.# f1 f2 h

Ex1 7 8 14

…

Ex100 5 2 5

training data

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

• 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.

• 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.

Back to A* and another property of the
heuristics…

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Consistent (Monotonic) Heuristic
• Consider a pair of nodes ni and nj, where ni is the parent of nj

• h is a consistent (monotonic) heuristic, if for all such pairs in the search
graph the following triangle inequality is satisfied:

cost(ni,nj)
ni

h(ni)

h(nj)

h=10

h=9

cost=3

consistent
10<=9+3 h=10 h=5 cost=3 not consistent 10 <= 5+3 ni cost(ni,nj) nj h(ni) h(nj) parent child h(ni)  cost(ni,nj)+ h(nj) for all n parent child nj Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018 39 Another Interpretation of the Triangle Inequality • => 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

n
j

cost(ni,nj)

ni h(ni)

h(nj)

h=10

h=9

cost=3

consistent
9  10-3

h=10

h=5

cost=3

not consistent

5  10-3

cost(ni,nj)

h(ni)

h(nj)

parent

child

h(ni)  cost(ni,nj)+ h(nj) for all n
parent child

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

Consistency Theorems

• Theorem 1: If h(n) is consistent, than 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)
• Theorem 2: If f(nj)  f(ni), i.e. f is non-decreasing along any path,

than h(n) is consistent

deff. h(n) consistent

child parent

cost(ni,nj)

h(ni)

h(nj)

parent

child

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3a, 2018

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, 2018

Completeness of A* with Consistent Heuristic –
Intuitive Idea

• 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 – 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, 2018

• 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 g(G2) f(n) does not decrease along
any path

• 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, 2018

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 does not mean practical
completeness if it takes too long to get the solution (time and space
are exponential)

• => If we can’t design an accurate 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, 2018

Related Posts