Artificial Intelligence

Halil

chapter03a.pdf

Home >Computer Science homework help >Artificial Intelligence

CSE 482 - Artificial Intelligence

Artificial Intelligence: A Modern Approach

Original Slides by S. Russell Modified by A. H. Özer

Problem Solving and Search

Problem Solving and Search 1

Outline

♢ Problem-solving agents

♢ Problem types

♢ Problem formulation

♢ Example problems

♢ Basic search algorithms

Problem Solving and Search 2

Problem-Solving Agents

Restricted form of general agent:

function Simple-Problem-Solving-Agent( percept) returns an action

static: seq, an action sequence, initially empty

state, some description of the current world state

goal, a goal, initially null

problem, a problem formulation

state←Update-State(state,percept) if seq is empty then

goal←Formulate-Goal(state) problem←Formulate-Problem(state,goal) seq←Search( problem)

action←Recommendation(seq,state) seq←Remainder(seq,state) return action

Problem Solving and Search 3

Problem-Solving Agents

Note: This is offline problem solving; solution executed “eyes closed.” Online problem solving involves acting without complete knowledge.

Problem Solving and Search 4

Example: Romania

An agent is on holiday in Romania; currently in Arad.

He must be in Bucharest tomorrow to catch his flight.

Giurgiu

Urziceni Hirsova

Eforie

Neamt

Oradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Dobreta Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

118

111

120

151

140

101

211

138

146 85

142

Problem Solving and Search 5

Problem Definition

A problem can be defined formally by five components:

♢ The initial state that the agent starts in. e.g. In(Arad)

♢ A description of the possible actions available to the agent.

– Given a particular state s, ACTIONS(s) returns the set of actions that can be executed in s.

– ACTIONS(In(Arad)) = {Go(Sibiu), Go(Timisoara), Go(Zerind)}

♢ A description of what each action does, i.e. the transition model.

– RESULT(s, a) returns the state that results from doing action a in state s.

– e.g. RESULT(In(Arad), Go(Zerind)) = In(Zerind)

Problem Solving and Search 6

Problem Definition

♢ The goal test which determines whether a given state is a goal state. e.g. In(Bucharest)

♢ A path cost function that assigns a numeric cost to each se- quence of states.

– The cost function reflects agent’s own performance measure.

Problem Solving and Search 7

Problem Definition

The state space is the set of all states reachable from the initial state by any sequence of actions.

– The initial state, actions and the transition model define the state space.

– The state space forms a directed graph in which the nodes are the states, the arcs are the actions.

– A path in the state space is a sequence of states connected by a sequence of actions.

A solution is an action sequence (or path) that leads from the initial state to a goal state.

The optimum solution is the solution that has the lowest path cost among all solutions, i.e. the shortest path.

Problem Solving and Search 8

Selecting a State Space

Real world is complex ⇒ state space must be abstracted for problem solving

(Abstract) state = set of real states

(Abstract) action = complex combination of real actions e.g., “Arad → Zerind” represents a complex set

of possible routes, detours, rest stops, etc. For guaranteed realizability, any real state “in Arad”

must get to some real state “in Zerind”

(Abstract) solution = set of real paths that are solutions in the real world

Each abstract action should be “easier” than the original problem!

Problem Solving and Search 9

Example: vacuum world state space graph R

S S

L R

states? actions? goal test? path cost?

Problem Solving and Search 10

Example: vacuum world state space graph R

S S

L R

states?: integer dirt and robot locations (ignore dirt amounts etc.) actions? goal test? path cost?

Problem Solving and Search 11

Example: vacuum world state space graph R

S S

L R

states?: integer dirt and robot locations (ignore dirt amounts etc.) actions?: Left, Right, Suck, NoOp goal test? path cost?

Problem Solving and Search 12

Example: vacuum world state space graph R

S S

L R

states?: integer dirt and robot locations (ignore dirt amounts etc.) actions?: Left, Right, Suck, NoOp goal test?: no dirt path cost?

Problem Solving and Search 13

Example: vacuum world state space graph R

S S

L R

states?: integer dirt and robot locations (ignore dirt amounts etc.) actions?: Left, Right, Suck, NoOp goal test?: no dirt path cost?: 1 per action (0 for NoOp)

Problem Solving and Search 14

Example: The 8-puzzle

Start State Goal State

51 3

4 6

7 8

states? actions? goal test? path cost?

Problem Solving and Search 15

Example: The 8-puzzle

Start State Goal State

51 3

4 6

7 8

states?: integer locations of tiles (ignore intermediate positions) actions? goal test? path cost?

Problem Solving and Search 16

Example: The 8-puzzle

Start State Goal State

51 3

4 6

7 8

states?: integer locations of tiles (ignore intermediate positions) actions?: move blank left, right, up, down (ignore unjamming etc.) goal test? path cost?

Problem Solving and Search 17

Example: The 8-puzzle

Start State Goal State

51 3

4 6

7 8

states?: integer locations of tiles (ignore intermediate positions) actions?: move blank left, right, up, down (ignore unjamming etc.) goal test?: = goal state (given) path cost?

Problem Solving and Search 18

Example: The 8-puzzle

Start State Goal State

51 3

4 6

7 8

states?: integer locations of tiles (ignore intermediate positions) actions?: move blank left, right, up, down (ignore unjamming etc.) goal test?: = goal state (given) path cost?: 1 per move

[Note: Optimum solution of n-Puzzle family is NP-hard]

Problem Solving and Search 19

Example: The 8-queens Problem

states?: Any arrangement of 0 to 8 queens on the board. initial state?: No queens on the board. actions?: Add a queen to any empty square. goal test?: 8 queens are on the board, none attacked. path cost?: none

[Note: 64 ·63 . . . 57 ≈ 1.8 ·1014 possible paths to search!]

Problem Solving and Search 20

The 8-queens Problem - Alternative

states?: All possible arrangements of n queens (1 ≤ n ≤ 8), one per column in the leftmost n columns, with no queen attacking another. actions?: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen.

[Note: Reduces the state space from 1.8 ·1014 states to 2057!]

Problem Solving and Search 21

Infinite State Space

Donald Knuth (1964) conjectured that starting with number 4, a sequence of factorial, square root, and floor operations will reach any desired positive integer.

e.g. ⌊ √√√√√√

√√√√√ √√√√√√(4!)!⌋ = 5

states?: Positive numbers. initial state?: 4. actions?: Apply factorial, square root, or floor operation (factorial for integers only). goal test?: State is the desired integer.

[Note: (4!)! = 620448401733239439360000]

Problem Solving and Search 22

Tree search algorithms

Basic idea: offline, simulated exploration of state space by generating successors of already-explored states

(a.k.a. expanding states)

function Tree-Search( problem,strategy) returns a solution, or failure

initialize the frontier (nodes to be visited) using the initial state of problem

loop do

if the frontier is empty then return failure

choose a leaf node for expansion according to strategy and remove it from the

frontier

if the node contains a goal state then return the corresponding solution

expand the node and add the resulting nodes to the frontier

end

Problem Solving and Search 23

Tree search example

Rimnicu Vilcea Lugoj

ZerindSibiu

Arad Fagaras Oradea

Timisoara

AradArad Oradea

Arad

Problem Solving and Search 24

Tree search example

Rimnicu Vilcea LugojArad Fagaras Oradea AradArad Oradea

Zerind

Arad

Sibiu Timisoara

Problem Solving and Search 25

Tree search example

Lugoj AradArad OradeaRimnicu Vilcea

Zerind

Arad

Sibiu

Arad Fagaras Oradea

Timisoara

Problem Solving and Search 26

Implementation: states vs. nodes

A state is a (representation of) a physical configuration A node is a data structure constituting part of a search tree

includes parent, children, depth, path cost g(x) States do not have parents, children, depth, or path cost!

State Node depth = 6

g = 6

state

parent, action

The Expand function creates new nodes, filling in the various fields and using the successor function (RESULT) of the problem to cre- ate the corresponding states.

Problem Solving and Search 27

General Graph Search

function Graph-Search( problem,strategy) returns a solution, or failure

initialize the frontier (nodes to be visited) using the initial state of problem

initialize the explored set to be empty

loop do

if there the frontier is empty then return failure

choose a leaf node for expansion according to strategy and remove it from the

search tree

if the node contains a goal state then return the corresponding solution

add the node to the explored set

expand the node and add the resulting nodes to the frontier

only if not in the frontier or explored set

end

Problem Solving and Search 28

Search strategies

A strategy is defined by picking the order of node expansion

Strategies are evaluated along the following dimensions: completeness—does it always find a solution if one exists? time complexity—number of nodes generated/expanded space complexity—maximum number of nodes in memory optimality—does it always find a least-cost solution?

Time and space complexity are measured in terms of b—maximum branching factor of the search tree d—depth of the least-cost solution m—maximum depth of the state space (may be ∞)

Problem Solving and Search 29

Uninformed search strategies

Uninformed strategies use only the information available in the problem definition

Breadth-first search

Uniform-cost search

Depth-first search

Depth-limited search

Iterative deepening search

Problem Solving and Search 30

Breadth-first search

Expand shallowest unexpanded node

Implementation: frontier is a FIFO queue, i.e., new successors go at end

B C

D E F G

Problem Solving and Search 31

Breadth-first search

Expand shallowest unexpanded node

Implementation: frontier is a FIFO queue, i.e., new successors go at end

B C

D E F G

Problem Solving and Search 32

Breadth-first search

Expand shallowest unexpanded node

Implementation: frontier is a FIFO queue, i.e., new successors go at end

B C

D E F G

Problem Solving and Search 33

Breadth-first search

Expand shallowest unexpanded node

Implementation: frontier is a FIFO queue, i.e., new successors go at end

B C

D E F G

Problem Solving and Search 34

Breadth-first search

function Breadth-First-Search(problem) returns soln/fail/cutoff

node ← a node with State=problem.Initial-State,Path-Cost=0 if problem.Goal-Test(node.State) then return Solution(node)

frontier ← a FIFO queue with node as the only element explored ← an empty set loop do

if Empty?((frontier)) then return failure

node ← Pop(frontier) add node.State to explored

for each action in problem.Actions(node.State) do

child ← Child-Node(problem,node,action) if child.State is not in explored or frontier then

if problem.Goal-Test(child.State) then return Solution(child)

frontier ← Insert(child,frontier)

Problem Solving and Search 35

Properties of breadth-first search

Complete?

Problem Solving and Search 36

Properties of breadth-first search

Complete? Yes (if b is finite)

Time?

Problem Solving and Search 37

Properties of breadth-first search

Complete? Yes (if b is finite)

Time? 1 + b + b2 + b3 + . . . + bd = O(bd), i.e., exp. in d

Space?

Problem Solving and Search 38

Properties of breadth-first search

Complete? Yes (if b is finite)

Time? 1 + b + b2 + b3 + . . . + bd = O(bd), i.e., exp. in d

Space? O(bd) (keeps every node in memory)

Optimum?

Problem Solving and Search 39

Properties of breadth-first search

Complete? Yes (if b is finite)

Time? 1 + b + b2 + b3 + . . . + bd = O(bd), i.e., exp. in d

Space? O(bd) (keeps every node in memory)

Optimum? Yes (if cost = 1 per step); not optimum in general

For a branching factor b = 10, depth d = 16, 1 million nodes/second, 1000 bytes/node:

The number of nodes: 1016, Time: 350 years, Memory: 10 exabytes

Problem Solving and Search 40

Uniform-cost search

Expand least-cost unexpanded node.

Implementation: frontier = priority queue ordered by path cost, lowest first.

Equivalent to breadth-first if step costs all equal. Sibiu Fagaras

Pitesti

Rimnicu Vilcea

Bucharest

101

211

Problem Solving and Search 41

Uniform-cost search

Complete? Yes, if step cost ≥ ϵ (No-Op operation?)

Time? # of nodes with g ≤ cost of optimum solution, O(b1+⌊C ∗/ϵ⌋)

where C∗ is the cost of the optimum solution

Space? # of nodes with g ≤ cost of optimum solution, O(b1+⌊C ∗/ϵ⌋)

Optimum? Yes—nodes expanded in increasing order of g(n)

Problem Solving and Search 42

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 43

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 44

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 45

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 46

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 47

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 48

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 49

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 50

Depth-first search

Expand deepest unexpanded node

Implementation: frontier = LIFO queue, i.e., put successors at front

B C

D E F G

H I J K L M N O

Problem Solving and Search 51

Properties of depth-first search

Complete?

Problem Solving and Search 52

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces

Time?

Problem Solving and Search 53

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces

Time? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-

first

Space?

Problem Solving and Search 54

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces

Time? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-

first

Space? O(bm), i.e., linear space!

Optimum?

Problem Solving and Search 55

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces

Time? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-

first

Space? O(bm), i.e., linear space!

Optimum? No

Problem Solving and Search 56

Depth-limited search

= depth-first search with depth limit l, i.e., nodes at depth l have no successors.

Problem Solving and Search 57

Depth-limited search

Recursive implementation:

function Depth-Limited-Search(problem, limit) returns soln/fail/cutoff

return Recursive-DLS(Make-Node(problem.Initial-State),problem,

limit)

function Recursive-DLS(node,problem, limit) returns soln/fail/cutoff

if problem.Goal-Test(node.State) then return Solution(node)

else if limit = 0 then return cutoff

else

cutoff-occurred?← false for each action in problem.Actions(node.State) do

child ← Child-Node(problem,node,action) result ← Recursive-DLS(child,problem, limit-1) if result = cutoff then cutoff-occurred?←true else if result ̸= failure then return result

if cutoff-occurred? then return cutoff else return failure

Problem Solving and Search 58

Iterative deepening search

function Iterative-Deepening-Search( problem) returns a solution

inputs: problem, a problem

for depth← 0 to ∞ do result←Depth-Limited-Search( problem,depth) if result ̸= cutoff then return result

end

Problem Solving and Search 59

Iterative deepening search l = 0

Limit = 0 A A

Problem Solving and Search 60

Iterative deepening search l = 1

Limit = 1 A

B C

Problem Solving and Search 61

Iterative deepening search l = 2

Limit = 2 A

B C

D E F G

B C

D E F G

B C

D E F G

B C

D E F G

B C

D E F G

B C

D E F G

B C

D E F G

B C

D E F G

Problem Solving and Search 62

Iterative deepening search l = 3

Limit = 3

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H I J K L M N O

B C

D E F G

H J K L M N OI

B C

D E F G

H I J K L M N O

Problem Solving and Search 63

Properties of iterative deepening search

Complete?

Problem Solving and Search 64

Properties of iterative deepening search

Complete? Yes

Time?

Problem Solving and Search 65

Properties of iterative deepening search

Complete? Yes

Time? (d + 1)b0 + db1 + (d−1)b2 + . . . + bd = O(bd)

Space?

Problem Solving and Search 66

Properties of iterative deepening search

Complete? Yes

Time? (d + 1)b0 + db1 + (d−1)b2 + . . . + bd = O(bd)

Space? O(bd)

Optimum?

Problem Solving and Search 67

Properties of iterative deepening search

Complete? Yes

Time? (d + 1)b0 + (d)b1 + (d−1)b2 + . . . + (1)bd = O(bd)

Space? O(bd)

Optimum? Yes, if step cost = 1 Can be modified to explore uniform-cost tree: iterative length-

ening search.

Problem Solving and Search 68

Properties of iterative deepening search

Numerical comparison for b = 10 and d = 5, solution at far right leaf:

N(IDS) = 50 + 400 + 3, 000 + 20, 000 + 100, 000 = 123, 450

N(BFS) = 10 + 100 + 1, 000 + 10, 000 + 100, 000 = 111, 110

Revisiting in IDS does not incur much overhead.

In general, IDS is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

Problem Solving and Search 69

Summary of algorithms

Criterion Breadth- Uniform- Depth- Depth- Iterative First Cost First Limited Deepening

Complete? Yes Yes Yes (if finite) Yes, if l ≥ d Yes Time bd b1+⌊C

∗/ϵ⌋ bm bl bd

Space bd b1+⌊C ∗/ϵ⌋ bm bl bd

Optimal? Yes∗ Yes No No Yes∗

Problem Solving and Search 70