Nhân bản – Phụng sự – Khai phóng

Solving Problems by Searching

Artificial Intelligence
 CONTENTS

• Search Problems

• Uninformed Search

• Informed Search

Artificial Intelligence 2
 CONTENTS

• Search Problems
• Uninformed Search

• Informed Search

Artificial Intelligence 3
 CONTENTS

• Search Problems
• Problem solving agents
• Search Trees

Artificial Intelligence 4
 Search Problems

The Seven Bridges of

Königsberg Euler’s
graphical representation

Artificial Intelligence 5
 Problem solving agents

 Problem-solving agent in Artificial Intelligence is goal-based

agents that focus on goals, is one embodiment of a group of
algorithms, and techniques to solve a well-defined problem.

Artificial Intelligence 6
 …Problem solving agents

Example: Traveling in Romania

• State space:
• Cities

• Successor function:
• go to adjacent city with cost =
distance

• Start state:
• Arad
• Goal test:
• Is state == Bucharest?
• Solution?

Artificial Intelligence 7
 …Problem solving agents

• A search problem consists of:

• State space: set of possible states
• Successor function (with actions, costs): description of what
each action does and cost
• Start state: that the agent starts in.
• Goal test: determines whether a given state is a goal state
• A solution is a sequence of actions that leads from the start
state to a goal state. Solution quality is measured by the cost,
and an optimal solution has the lowest cost among all solutions.
Problem solving agent

Artificial Intelligence 8
 …Problem solving agents

Example: Pac-Man game (eat-all-dots)

• State space:
• {(x,y), dot booleans}

• Successor function
• update location and “N”, 1.0
possibly a dot boolean

• Start state “E”, 1.0

• Goal test: eat all the dots

Artificial Intelligence 9
 …Problem solving agents
Example: vacuum world

• State space:
• agent location & dirt locations
• Successor function:
• Left, Right, Suck
• Star state:
• Any state can be designated
• Goal stest:
• This checks whether all the squares are clean

Artificial Intelligence 10
 …Problem solving agents

Example: the 8-puzzle

• State space: location of each of squares

• Successor function: movements of the blank space Left, Right, Up,or Down
• Start state: Any state can be designated
• Goal test: This checks whether the state matches the goal state

Artificial Intelligence 11
 …Problem solving agents

Example: the 8-puzzle

Artificial Intelligence 12
 …Problem solving agents

Example: the 8-queens problem

• The goal of the 8-queens problem is to place

eight queens on a chessboard such that no
queen attacks any other.

• State space: any arrangement of 0 to 8 queens

on the board is a state
• Successor function: Add a queen to an empty
square
• Start state: No queens on the board
an attempted solution that fails: the
• Goal test: 8 queens are on the board, none queen in the rightmost column is
attacked attacked by the queen at the top left.

Artificial Intelligence 13
 …Problem solving agents

Problem solving agent function

Artificial Intelligence 14
 Search Trees

State Space Graphs vs. Search Trees

State Space Graph Search Tree

Each NODE in in the search
tree is an entire PATH in
the state space graph. S

a G d e p
b c
b c e h r q
e
d f a a h r p q f
S h
p q f q c G
p r We construct both on
q
demand – and we construct q c G a
as little as possible.
a

Artificial Intelligence 15
 …Search Trees

Artificial Intelligence 16
 …Search Trees

Artificial Intelligence 17
 …Search Trees

Artificial Intelligence 18
 …Search Trees
• Example
a G
b c
e
d f
S h
p q r

Artificial Intelligence 19
 …Search Trees
• Example
a G
b c
e
d f
S h
p q r

S s
sd
d e p se
sp
b c e h r q sdb
sdc
a a h r p q f sde
sdeh
p q f q c G
sder
a sderf
q c G
sderfc
a sderfG

Artificial Intelligence 20
 CONTENTS

• Search Problems

• Uninformed Search

• https://www.massey.ac.nz/~mjjohn
so/notes/59302/l03.html
• Informed Search

Artificial Intelligence 21
 CONTENTS

• Uninformed search
• Depth-First Search (Tìm kiếm theo chiều sâu )
• Breadth-First Search (Tìm kiếm theo chiều rộng)
• Iterative-Deepening Search (Tìm kiếm sâu dần)
• Uniform-Cost Search (Tìm kiếm với chi phí cực tiểu)

Artificial Intelligence 22
 Depth-First Search (DFS)

• Strategy: expand a deepest node first

• Implementation: Fringe is a LIFO stack

Artificial Intelligence 23
 … Depth-First Search (DFS)

a G
b c
e
d f
S h
p q r

d e p

b c e h r q

a a h r p q f

p q f q c G

q c G a

a
Artificial Intelligence 24
 …Depth-First Search (DFS)

Properties
• Complete: Guaranteed to find a solution if one exists?
• Optimal: Guaranteed to find the least cost path?
• Time complexity?
• Space complexity?
b 1 node
• Cartoon of search tree: … b nodes
• b is the branching factor b2 nodes
• m is the maximum depth m tiers

• solutions at various depths

• Number of nodes in entire tree? bm nodes

• 1 + b + b2 + …. bm = O(bm)
Artificial Intelligence 25
 …Depth-First Search (DFS)
Properties
1 node
• What nodes DFS expand? b
b nodes
…
• Some left prefix of the tree. b2 nodes
• Could process the whole tree! m tiers

• Time: If m is finite, takes time O(bm)

• Space: Only has siblings on path to root, so O(bm)
bm nodes
• complete?
• m could be infinite, so only if we prevent cycles
(more later)
• optimal?
• No, it finds the “leftmost” solution, regardless of
depth or cost
Artificial Intelligence 26
 Breadth-First Search (BFS)

• Strategy: expand a shallowest node first

• Implementation: Fringe is a FIFO queue

Artificial Intelligence 27
 …Breadth-First Search (BFS)

a G
b c
e
d f
S h
p q r

d e p
Search
b c e h r q
Tiers
a a h r p q f

p q f q c G

q c G a
a
Artificial Intelligence 28
 …Breadth-First Search (BFS)

Artificial Intelligence 29
 …Breadth-First Search (BFS)

Artificial Intelligence 30
 …Breadth-First Search (BFS)

Artificial Intelligence 31
 …Breadth-First Search (BFS)

Artificial Intelligence 32
 …Breadth-First Search (BFS)

Artificial Intelligence 33
 …Breadth-First Search (BFS)

Artificial Intelligence 34
 …Breadth-First Search (BFS)

Artificial Intelligence 35
 …Breadth-First Search (BFS)

Artificial Intelligence 36
 …Breadth-First Search (BFS)

Artificial Intelligence 37
 …Breadth-First Search (BFS)

Artificial Intelligence 38
 …Breadth-First Search (BFS)

Artificial Intelligence 39
 …Breadth-First Search (BFS)

Artificial Intelligence 40
 …Breadth-First Search (BFS)

Artificial Intelligence 41
 …Breadth-First Search (BFS)

Artificial Intelligence 42
 …Breadth-First Search (BFS)

Artificial Intelligence 43
 …Breadth-First Search (BFS)

Properties

• What nodes does BFS expand?

• Processes all nodes above shallowest solution
1 node
b
• Let depth of shallowest solution be s … b nodes
s tiers
• Time: takes time O(bs) b2 nodes
• Space: has roughly the last tier, so O(bs)
bs nodes
• complete?
• s must be finite if a solution exists, so yes!
• optimal? bm nodes

• Only if costs are all 1 (more on costs later)

Artificial Intelligence 44
 …Breadth-First Search (BFS)

DFS vs BFS

• DFS: need to get to the bottom. Memory constrained.

• BFS: solutions not too far down.

Artificial Intelligence 45
 Iterative-Deepening Search (IDS)

• Idea: get DFS’s space advantage with BFS’s time / shallow-solution

advantages
• Run a DFS with depth limit 1. If no solution… b
…
• Run a DFS with depth limit 2. If no solution…
• Run a DFS with depth limit 3. …..

• Isn’t that wastefully redundant?

• Generally most work happens in the lowest level searched, so not
so bad!

Artificial Intelligence 46
 …Iterative-Deepening Search (IDS)

IDS: d = 0

Artificial Intelligence 47
 …Iterative-Deepening Search (IDS)

IDS: d = 1

B C

Artificial Intelligence 48
 …Iterative-Deepening Search (IDS)

IDS: d = 2

B C

D E F G

Artificial Intelligence 49
 …Iterative-Deepening Search (IDS)

IDS: d = 3

B C

D E F G

H I J K L M

GOAL

Artificial Intelligence 50
 …Iterative-Deepening Search (IDS)

Artificial Intelligence 51
 …Iterative-Deepening Search (IDS)

Properties
• Complete
• Có
• Time:
• (d+1).b0 + d.b1 + (d-1).b2+ … +bd = O(bd)
• Space:
• O(b.d)
• Optimal
• Có - nếu chi phí cho mỗi buớc = 1

Artificial Intelligence 52
 Uniform Cost Search (UCS)
(Djikstra’s algorithm)

• Like breadth first, but with costs.

Label with cumulative cost.

Artificial Intelligence 53
 …Uniform Cost Search(UCS)

Strategy: expand a cheapest node first:

Fringe is a priority queue (priority: cumulative cost)

Artificial Intelligence 54
 …Uniform Cost Search(UCS)

Artificial Intelligence 55
 …Uniform Cost Search(UCS)

Artificial Intelligence 56
 …Uniform Cost Search(UCS)

Artificial Intelligence 57
 …Uniform Cost Search(UCS)

Artificial Intelligence 58
 …Uniform Cost Search(UCS)

Artificial Intelligence 59
 …Uniform Cost Search(UCS)

Artificial Intelligence 60
 …Uniform Cost Search(UCS)

Artificial Intelligence 61
 …Uniform Cost Search(UCS)

Artificial Intelligence 62
 …Uniform Cost Search(UCS)
2 G
a
b c
1 8 2
2
3 e
d f
9 2
S 8
h 1
1 p r
q
15

S 0

d 3 e 9 p 1

b 4 c e 5 h 17 r 11 q 16
11
Cost a 6 a h 13 r 7 p q f
contours
p q f 8 q c G

q 11 c G 10
a
• Contours show equal cost.
a
Artificial Intelligence 63
 …Uniform Cost Search(UCS)

Artificial Intelligence 64
 …Uniform Cost Search(UCS)
Properties
• What nodes does UCS expand?
• Processes all nodes with cost less than cheapest solution!
• If that solution costs C* and arcs cost at least  , then the “effective depth”
is roughly C*/
• Time: O(bC*/) (exponential in effective depth)
• Space: has roughly the last tier, so O(bC*/)
b c1
• complete? …
c2
C*/ “tiers”
• Assuming best solution has a finite cost c3
and minimum arc cost is positive, yes!
• optimal?
• Yes! (Proof next lecture via A*)

Artificial Intelligence 65
 …Uniform Cost Search(UCS)

Uniform Cost Issues

• UCS explores increasing cost contours … c1

c2
c3
• The good: UCS is complete and optimal!

• The bad:
• Explores options in every “direction”
• No information about goal location

Start Goal
• We’ll fix that soon!

Artificial Intelligence 66
 Uninformed Search

Phương pháp tìm kiếm sâu dần (IDS):

• Chi phí về thời gian chỉ nhiều hơn một chút so với các phương pháp khác
• Chi phí về không gian bộ nhớ ở mức hàm tuyến tính

Artificial Intelligence 67
 CONTENTS

• Search Problems

• Uninformed Search

• Informed Search

Artificial Intelligence 68
 CONTENTS

• Informed search (Heuristic search)

• Heuristic Function
• Greedy Search
• A* Search

Artificial Intelligence 69
 Heuristic Function

A heuristic is
 A function that estimates how close a state is to a goal
 Designed for a particular search problem

 Ex: Manhattan distance, Euclidean distance for pathing

10

5
11.2

Artificial Intelligence 70
 …Heuristic Function
Example: Heuristic Function h(x)

Artificial Intelligence 71
 …Heuristic Function

Example: Heuristic Function

• h(u) = 8
= the number of misplaced tiles
(all of the eight tiles are out of position)

• h(u) = 3+1+2+2+2+3+3+2 = 18
= the sum of the distances of the tiles from their goal positions.

Artificial Intelligence 72
 …Heuristic Function

Tree Search Pseudo-Code

Artificial Intelligence 73
 Greedy Search

Artificial Intelligence 74
 Greedy Search

• Strategy: expand a node that (you think) is closest b

…
to a goal state
• Heuristic: estimate of distance to nearest goal
for each state
• A common case:
• Best-first takes you straight to the (wrong) goal
b
…
• Worst-case: heuristic wrong!!!

Artificial Intelligence 75
 …Greedy Search
h(x)

Artificial Intelligence 76
 …Greedy Search

Artificial Intelligence 77
 …Greedy Search

Artificial Intelligence 78
 …Greedy Search

optimal?: No. Resulting path

to Bucharest is not the shortest!

What can go wrong?

Greedy: 140 + 99 + 211 = 450
Better: 140+80+97+101 = 418
Artificial Intelligence 79
 …Greedy Search

What can go wrong?

Greedy: 140 + 99 + 211 = 450 h(x)
Better: 140+80+97+101 = 418

Artificial Intelligence 80
 A* Search

Artificial Intelligence 81
 A* Search

Idea: Combining UCS and Greedy

• Uniform-Cost orders by path cost, or backward cost: g(n)
• Greedy orders by goal proximity, or forward cost: h(n)
• A* Search orders by the sum: f(n) = g(n) + h(n).

UCS Greedy

A*
Artificial Intelligence 82
 A* Search
• Uniform-cost orders by path cost, or backward cost g(n)
• Greedy orders by goal proximity, or forward cost h(n)

8 g=0
S h=6
g=1
e h=1
h=5 a
1
1 3 2 g=2 g=9
S a d G g=4
h=6 b d e h=1
h=2
h=6 1 h=5
h=2 h=0
1 g=3 g=6 g = 10
c b h=7 c G h=0 d h=2
h=7 h=6
g = 12
G h=0
• A* Search orders by the sum: f(n) = g(n) + h(n)
• >> Đường đi ngắn nhất: S – a – d - G
Artificial Intelligence 83
 …A* Search

Artificial Intelligence 84
 …A* Search

Artificial Intelligence 85
 …A* Search

Artificial Intelligence 86
 …A* Search

Artificial Intelligence 87
 …A* Search

Artificial Intelligence 88
 …A* Search

Greedy: 140 + 99 + 211 = 450

A*: 140+80+97+101 = 418 h(x)
Artificial Intelligence 89
 …A* Search

Properties of A* Search

Uniform-Cost A*

b b
… …

UCS ragged based on cost.

A* narrows when near goal, heuristic
Artificial Intelligence 90
 …A* Search
A* vs. UCS UCS
• UCS expands equally in all “directions”

• A*: expands mainly toward the goal,

but does hedge its bets to ensure optimality

A*

Artificial Intelligence 91
 …A* Search

Comparison

Uniform Cost Greedy A*

Artificial Intelligence 92
 …A* Search

A* Applications

• Video games
• Pathing / routing problems
• Resource planning problems
• Robot motion planning
• Language analysis
• Machine translation
• Speech recognition
•…

Artificial Intelligence 93
 …A* Search

• A* uses both backward costs and (estimates of) forward costs

• A* is optimal with admissible / consistent heuristics

• Heuristic design is key: often use relaxed problems

Artificial Intelligence 94
 SUMMARY

• Search Problems

• Uninformed Search

• Informed Search

Artificial Intelligence 95
 Nhân bản – Phụng sự – Khai phóng

Enjoy the Course…!

Artificial Intelligence 96