Solving Problems by Searching - Santa Clara Universitytschwarz/COEN266/Searching.pdf · Recurring...

Solving Problems by Searching

Artificial Intelligence Santa Clara University 2016

Problem Solving Agents• Problem Solving Agents

• Use atomic representation of states • Planning agents

• Use factored or structured states

• Uninformed search algorithms • Algorithms only use state space

• Informed search algorithms • Algorithms use some guidance where to find

solution

Problem Solving Agents• Problem formulation

• What actions and state to consider • Goal formulation

• What is a desirable state

Problem Solving Agents• First set of assumptions

• Environment is observable• Agent knows current state

• Environment is discrete • In any state, there are only a finite number of

actions to be taken (and states to be reached) • Environment is known

• Agent knows which states are reached by what action

• Environment is deterministic • Each action has exactly one outcome

Problem solving agents• Search:

• Looking for a sequence of actions that lead to the (a) goal

• Execution: • Follow the sequence of actions

• Formulate - Search - Execute• Notice: agent does not react to precepts during the

execute phase • Open loop system: loop between agent and

environment is broken

Problem Solving Agents• Well-defined problem

1. Initial state 2. Descriptions of actions 3. Transition model: Which action leads to what

state 4. Goal test 5. Path cost

Recurring Sample Problem: Navigating Rumania

Giurgiu

UrziceniHirsova

Eforie

NeamtOradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Drobeta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

A typical toy problem

R

LS S

S S

R

L

R

L

R

L

S

SS

S

L

L

LL R

R

R

R

Another toy problem2

Start State Goal State

1

3 4

6 7

5

1

2

3

4

6

7

8

5

8

Another toy problem

A simple real world problem• Find a flight from A to B (with stop overs)

Uninformed Searching• Uninformed searching

• Go through the search space looking for a state that fulfills the goal condition

• Search space represented as a graph of nodes • Expand nodes (create all the neighbors of the

current node)

Uniformed Searching• State examples:

• 8-puzzle • State given by a matrix with entries 0-8

• 0 represents the blank space • Note: for half of the initial states, there is no

solution

_goal_state=[[1,2,3],

[4,5,6],

[7,8,0]]

https://gist.github.com/flatline/838202

https://gist.github.com/flatline/838202

Uninformed Searching• n - queens problem

• States are given by the position of j queens • Each queen needs to be in a different column • State given by an array (Python list) of j numbers • Avoid generating states that are not legal

def __init__(self, parent, move): self.parent = parent if parent: self.lista = parent.lista[:] else: self.lista = [] self.lista.append(move) def __str__(self): return "State "+str(self.lista) def test(self): #test whether any queen can take another one for col in range(0,len(self.lista)): row = self.lista[col] for j in range(len(self.lista)): if j == col: continue if self.lista[j] == row+j-col or self.lista[j] == row-j+col: return False return True

Uninformed Searching• When generating nodes, can revisit the same node

• Repeated state — Loopy path • Search tree is then infinite, even though state

space is finite • Assuming going from one state to another incurs

costs • Assuming costs add up • Then loopy paths never are cost-optimal

Uninformed Searching

(c)(b)(a)

Black: explored set — discovered and expanded White: frontier — discovered but not yet expanded Gray: unknown set — not yet discovered

Example

Giurgiu

UrziceniHirsova

Eforie

NeamtOradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Drobeta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

Breadth first search: حفظنا اهلل منه

Generate all accessible nodes in order until finding goal state

Uninformed Searching• Breadth first search

• Finds guaranteed a goal state if there is a path to the goal state • Expand initial state, then the states expanded from it, then the

states expanded from them, …def bfs(Instance):

states = fifo(Instance.initial) while states:

current = states.pop(0) else:

for state in current.neighbours(): if state.notmarked() and state.feasible(): if state.isGoal(): return state state.markVisited() states.append(state)

Uninformed Search• BFS: Will find closest goal node

• Assume a branching factor of b • Number of unexplored nodes reachable from a

node during the breadth-first search • Assume nearest goal state is at distance d from

the initial state • BFS creates

nodesb+ b2 + b3 + . . .+ bd = O(bd)

Uninformed Search• BFS:

• Memory is stressed: too many nodes kept in fifo queue

• Time needs depends on the depth of the search

Uninformed Search• Uniform cost search:

• Assume that all state transitions incur a cost • g(node) = cost to reach node from initial node • Expand the node n with the lowest path cost g(n) • Apply goal test only when the node is expanded

Uninformed Searchdef uniformCostSearch(instance):

frontier = priorityQueue(instance.initial, 0)

explored = []

while frontier:

current = frontier.pop() #get lowest cost node

if current.isGoal():

print(current) #print out inverse path to goal

for node in current.neighbours():

node.parent = current

pathCost = current.cost + current.actionCost(node)

if node in frontier and node.cost > pathCost:

node.cost = pathCost #duplicate, update


elif node not in frontier and node not in explored:

frontier.insert(node)

explored.append(current)

Group Quiz• Apply Uniform Cost Search to go from Sibiu to

Bucharest

Giurgiu

UrziceniHirsova

Eforie

NeamtOradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Drobeta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

Uninformed Search• Depth First Search:

• Use stack instead of fifo in organizing the frontierdef dfs(Instance):

states = lifo(Instance.initial) while states:

current = states.pop(0) else:

for state in current.neighbours(): if state.notmarked() and state.feasible(): if state.isGoal(): return state state.markVisited() states.append(state)

Uninformed Search• DFS will find a solution more quickly if they are lots

of solutions at a certain depth. • n-queens problem:

n bfs dfs4 14 85 43 56 148 317 511 98 1964 1139 8041 4110 34814 10211 164245 5212 841988 26113 4601177 11114 26992956 189915

Uninformed Search

A

C

F G

M N O

A

C

F G

L M N O

A

C

F G

L M N O

C

F G

L M N O

A

B C

E F G

K L M N O

A

C

E F G

J K L M N O

A

C

E F G

J K L M N O

A

B C

D E F G

I J K L M N O

A

B C

D E F G

H I J K L M N O

A

B C

D E F G

H I J K L M N O

A

B C

D E F G

H I J K L M N O

A

B C

D E F G

H I J K L M N O

DFS on a binary tree

Uninformed Search• DFS works well if there are goal states at a limited

depth • but horribly if there are not

• Depth limited search • If you don’t find a goal, break off after reaching a

maximum depth of d • How do we determine d?

• Sometimes, the problem can tell us • Iterative deepening depth first search

Uninformed Search• Iterative deepening depth first search

• Do limited depth dfs • Increase limit, if no solution found

• Why is this a good idea? • We recreate parts of the previous search tree • Repeated work is not a big portion of the total

work done

db+ (d� 1)b2 + (d� 2)b3 + . . .+ 2bd�1 + 1bd = O(bd)

Uninformed Search• Bidirectional Search

• Basic idea: • Search from the initial state and from the goal

state • Success if you can connect • Complexity O(bˆd/2)

GoalStart

Informed Searches• Use additional information

• Rumanian road map: • Straight-line distance to goal

• 8-puzzle • Sum of the Manhattan distance of current

location of a piece to goal location of a piece • n-queen problem

• Need to redefine states

Informed Search

• Tree search • Expand nodes without regard whether expanded

nodes have been visited • Graph search

• Expand nodes but disregard explored nodes

Informed Searchdef treeSearch(instance):

frontier = [ instance.initial ]

while frontier:

current = frontier.pop()

if current.isGoal():

return current

else:

for node in current.neighbor()


frontier.push(node)

Informed Searchdef graphSearch(instance):

explored = [] frontier = [instance.initial] while frontier:

current = frontier.pop() if current.isGoal():

print( current ) explored.push(current) for node in current.neighbor():

if node not in explored and node not in frontier: node.parent = current frontier.push(node)

Informed Search• Best-first search

• Do graph search • Use a priority queue • Have an evaluation function for each node

Informed Search• Greedy first search:

• Expand nodes according to the best node • Example: Use straight-line distance to the goal

Urziceni

NeamtOradea

Zerind

Timisoara

Mehadia

SibiuPitestiRimnicu Vilcea

Vaslui

Bucharest

GiurgiuHirsova

Eforie

Arad

Lugoj

DrobetaCraiova

Fagaras

Iasi

016024216177

151

366

244226

176

241

25332980

199

380234

374

100193

Informed Search

Rimnicu Vilcea

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Timisoara

Sibiu Bucharest

329 374

366 380 193

253 0

Rimnicu Vilcea

Arad

Sibiu

Arad Fagaras Oradea

Timisoara329

Zerind374

366 176 380 193

Zerind

Arad

Sibiu Timisoara253 329 374

Arad366

(a) The initial state

(b) After expanding Arad

(c) After expanding Sibiu

(d) After expanding Fagaras

Informed Search• Greedy best first search

has difficulties • Going from Iasi to

Fagaras • First expand Neamt • This puts Iasi back

into the frontier • Can never consider

Vaslui, because Vaslui is farther from Fagaras according to the heuristics

Giurgiu

UrziceniHirsova

Eforie

NeamtOradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Drobeta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

Informed Search• Greedy best-first search

• Combine with graph search algorithm • Do not consider repeated states

• Version is complete for finite trees

Informed Search• A* search

• Evaluation function f for node n: • g(n) cost of getting to node n • h(n) heuristic for getting from node n to goal

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

Informed Search• A* search

• When will A* be optimal? • Heuristic needs to be admissible

• Never overestimate the costs to reach the goal from the current node

• Heuristic needs to be consistent (when using graph search) • Estimated costs of reaching goal from n is less than or

equal to the costs of going from n to successor n’ plus estimated costs of reaching the goal from n’.

8n, 8n0, n0successor of n h(n) costs(n, n0

) + h(n0)

Informed Search• Tree-version of A* is optimal if heuristic is

admissible • Graph version of A* is optimal if heuristic is

consistent

• Clue: f-costs are nondecreasing on any path generated

• Can "prune" even neighbors of initial node

(a) The initial state

(b) After expanding Arad

(c) After expanding Sibiu

Arad

Sibiu Timisoara447=118+329

Zerind449=75+374393=140+253

Arad366=0+366

(d) After expanding Rimnicu Vilcea

(e) After expanding Fagaras

(f) After expanding Pitesti

Zerind

Arad

Sibiu

Arad

Timisoara

Rimnicu VilceaFagaras Oradea

447=118+329 449=75+374

646=280+366 413=220+193415=239+176 671=291+380

Zerind

Arad

Sibiu Timisoara447=118+329 449=75+374

Rimnicu Vilcea

Craiova Pitesti Sibiu526=366+160 553=300+253417=317+100

Zerind

Arad

Sibiu

Arad

Timisoara

Sibiu Bucharest

Fagaras Oradea

Craiova Pitesti Sibiu

447=118+329 449=75+374

646=280+366

591=338+253 450=450+0 526=366+160 553=300+253417=317+100

671=291+380

Zerind

Arad

Sibiu

Arad

Timisoara

Sibiu Bucharest

Oradea


Bucharest Craiova Rimnicu Vilcea418=418+0

447=118+329 449=75+374

646=280+366

591=338+253 450=450+0 526=366+160 553=300+253

615=455+160 607=414+193

671=291+380

Rimnicu Vilcea

Fagaras Rimnicu Vilcea

Arad Fagaras Oradea646=280+366 415=239+176 671=291+380

Informed Search• A* expands nodes according to contours

O

ZA

TL

MD

C

R

F

P

G

BU

H

E

V

I

N

380

400

420

S

Informed Search• A* works well

• If there are many sub-optimal paths that are not quite a goal, then A* will explore many unnecessary spaces

Informed Search• A* problems

• A* needs to maintain big arrays • it never throws away a node • runs out of memory before it runs out of user’s

patience

Informed Search• Memory bounded A* variants

• Iterative deepening • Cut-off consideration of nodes with f-value

larger than a certain value • If not successful, adjust cut-off point • Can be difficult if f-values are floats

Informed Search• Recursive best-first search

• Uses only linear space • Uses an f-limit value to keep track of the best

alternative path available

Informed Search• RBFS Search

• f_limit on top

• heuristic on bottom

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Craiova Sibiu

Bucharest Craiova Rimnicu Vilcea

Zerind

Arad

Sibiu

Arad

Sibiu Bucharest

Rimnicu VilceaOradea

Zerind

Arad

Sibiu

Arad

Timisoara

Timisoara

Timisoara

Fagaras Oradea Rimnicu Vilcea


646 415 671

526 553

646 671

450591

646 671

526 553

418 615 607

447 449

447

447 449

449

366

393

366

393

413

413 417415

366

393

415 450 417Rimnicu Vilcea

Fagaras

447

415

447

447

417

(a) After expanding Arad, Sibiu, and Rimnicu Vilcea

(c) After switching back to Rimnicu Vilcea and expanding Pitesti

(b) After unwinding back to Sibiu and expanding Fagaras

447

447

∞

∞

∞

417

417

Pitesti

Informed Search• RBFS Search (a) Expand on best path unless the current best leaf (Pitesti) is worse than the best alternative value (Fagaras) Don’t forget to update the value for Rimicu Vilcea

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Craiova Sibiu


Zerind

Arad

Sibiu

Arad

Sibiu Bucharest


Zerind

Arad

Sibiu

Arad

Timisoara

Timisoara

Timisoara



646 415 671

526 553

646 671

450591

646 671

526 553

418 615 607

447 449

447

447 449

449

366

393

366

393

413

413 417415

366

393


Fagaras

447

415

447

447

417




447

447

∞

∞

∞

417

417

Pitesti

Informed Search• RBFS Search (b) Unwind to Sibiu This puts the best leaf value of the forgotten subtree in Rimnicu Vilcea. Expand Fagaras with best leaf value of 450

This is worse than 415 for Rimnicu Vilcea

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Craiova Sibiu


Zerind

Arad

Sibiu

Arad

Sibiu Bucharest


Zerind

Arad

Sibiu

Arad

Timisoara

Timisoara

Timisoara



646 415 671

526 553

646 671

450591

646 671

526 553

418 615 607

447 449

447

447 449

449

366

393

366

393

413

413 417415

366

393


Fagaras

447

415

447

447

417




447

447

∞

∞

∞

417

417

Pitesti

Informed Search• RBFS Search (c) Back up to Sibiu after updating Fagaras Expand again RV Then expand Pitesti This time, we reach Bucharest, because the best alternative value (Timisoara) is worse

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Craiova Sibiu


Zerind

Arad

Sibiu

Arad

Sibiu Bucharest


Zerind

Arad

Sibiu

Arad

Timisoara

Timisoara

Timisoara



646 415 671

526 553

646 671

450591

646 671

526 553

418 615 607

447 449

447

447 449

449

366

393

366

393

413

413 417415

366

393


Fagaras

447

415

447

447

417




447

447

∞

∞

∞

417

417

Pitesti

Informed Search• RBFS generates less nodes than IDA*

• In a sense, IDA* and RBFS throw away too much memory

Informed Search• Memory bounded A* • Simplified memory bounded A*

Informed Search• Simplified memory bounded A*

• Do A* until algorithm runs out of memory • Need to free a node

• Frees the node with the highest value of f • After backing up the f-value to its parent

• If all the descendants of n are forgotten • SMA* does not know where to go from n • But SMA* knows whether n is worth while

considering

Heuristics• Example 8-puzzle

• Branching factor about 3 • Depth about 22 • Exhaustive tree search gives 3**22 ~3*10**10

moves • Graph search has 9!/2 possible states

• Example 15-puzzle • Graph search has 16!/2 = 10,461,394,944,000

states

Heuristics • Heuristic may not overstate the true costs of

moving to the goal state 1. Use number of misplaced tiles 2. Use the sum of the Manhattan distances of tiles

in the actual state to the tiles in the goal state

2


1

3 4

6 7

5

1

2

3

4

6

7

8

5

8

Heuristics • 8-puzzle

• Second choice works better

Heuristics • Relaxed search problems

• Instead of humans inventing heuristics • Computer could generate heuristics by relaxing the rules of

the game • 8 puzzle:

• Allow tiles move to any position • Second heuristic gives the costs to move to the goal in the

relaxed version • Automatic generation of heuristics

• Formulate the rules of the game • Then relax automatically the rules • Try out heuristics

Heuristics • Pattern databases:

• Generate admissible heuristics from subproblems


1

2

3

4

6

8

5

21

3 6

7 8

54

Heuristic: Costs of moving 1,2,3,4 to a goal state

Heuristics • Pattern databases:

• Use various heuristics • 1,2,3,4 • 5,6,7,8

• Pattern database stores the exact solution for a number of subproblems

• Disjoint pattern database • Solve 1, 2, 3, 4 subproblem only counting the moves of

tiles 1, 2, 3, or 4 • Solve 5, 6, 7, 8 subproblem only contain the moves of tiles

5, 6, 7, or 8 • Heuristic is the sum of both values

Solving Problems by Searching - Santa Clara Universitytschwarz/COEN266/Searching.pdf · Recurring...

Documents

Transcript of Solving Problems by Searching - Santa Clara Universitytschwarz/COEN266/Searching.pdf · Recurring...