Solving problems by searching

1

How an agent can find a sequence of actions that will eventually achieve its goal

Problem-solving agents

2

Example: Romania

3

• On holiday in Romania; currently in Arad.
• Flight leaves tomorrow from Bucharest
• Formulate goal:
• be in Bucharest
• Formulate problem:
• states: various cities
• actions: drive between cities
• Find solution:
• sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest

Example: Romania

4

Graphs

• Notation
• Common graph theory problems
• Common algorithms
• Questions?

Problem types

• Deterministic, fully observable 🡪 single-state problem
• Agent knows exactly which state it will be in; solution is a sequence
• Non-observable 🡪 sensorless problem (conformant problem)
• Agent may have no idea where it is; solution is a sequence
• Nondeterministic and/or partially observable 🡪 contingency problem
• percepts provide new information about current state
• often interleave} search, execution
• Unknown state space 🡪 exploration problem

Example: vacuum world

• Single-state, start in #5. Solution?

Example: vacuum world

• Single-state, start in #5. �Solution? [Right, Suck]

​

• Sensorless, start in �{1,2,3,4,5,6,7,8} e.g., �Right goes to {2,4,6,8} �Solution?

Example: vacuum world

• Sensorless, start in �{1,2,3,4,5,6,7,8} e.g., �Right goes to {2,4,6,8} �Solution? �[Right,Suck,Left,Suck]

​

​

​

• Contingency

​

• Partially observable: location, dirt at current location.
• Percept: [L, Clean], i.e., start in #5 or #7�Solution? �

Example: vacuum world

• Sensorless, start in �{1,2,3,4,5,6,7,8} e.g., �Right goes to {2,4,6,8} �Solution? �[Right,Suck,Left,Suck]

​

​

​

• Contingency
• Nondeterministic: Suck may �dirty a clean carpet
• Partially observable: location, dirt at current location.
• Percept: [L, Clean], i.e., start in #5 or #7�Solution? [Right, if dirt then Suck]

Single-state problem formulation

A problem is defined by four items:

​

1. initial state e.g., "at Arad"
2. actions or successor function S(x) = set of action–state pairs
• e.g., S(Arad) = {<Arad 🡪 Zerind, Zerind>, … }
3. goal test, can be
• explicit, e.g., x = "at Bucharest"
• implicit, e.g., Checkmate(x)
4. path cost (additive)
• e.g., sum of distances, number of actions executed, etc.
• c(x,a,y) is the step cost, assumed to be ≥ 0

​

• A solution is a sequence of actions leading from the initial state to a goal state

Selecting a state space

• Real world is absurdly 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

Vacuum world state space graph

​

​

​

​

​

• states?
• actions?
• goal test?
• path cost?

Vacuum world state space graph

​

​

​

​

​

• states? integer dirt and robot location
• actions? Left, Right, Suck
• goal test? no dirt at all locations
• path cost? 1 per action

Example: The 8-puzzle

​

​

​

​

​

• states?
• actions?
• goal test?
• path cost?

Blind Search

15

Example: The 8-puzzle

​

​

​

​

​

• states? locations of tiles
• actions? move blank left, right, up, down
• goal test? = goal state (given)
• path cost? 1 per move�

​

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

Blind Search

16

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 state, parent node, action, path cost g(x), depth

​

​

​

​

​

​

• The Expand function creates new nodes, filling in the various fields and using the SuccessorFn of the problem to create the corresponding states.�

Blind Search

17

Search strategies

• A search 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
• 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 ∞)�

Blind Search

18

Uninformed search strategies

• Uninformed search 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

Blind Search

19

Breadth-first search

• Expand shallowest unexpanded node�
• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end�

Blind Search

20

Breadth-first search

• Expand shallowest unexpanded node�
• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end�

Blind Search

21

Breadth-first search

• Expand shallowest unexpanded node�
• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end�

Blind Search

22

Breadth-first search

• Expand shallowest unexpanded node�
• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end�

Blind Search

23

Properties of breadth-first search

• Complete? Yes (if b is finite)
• Time? 1+b+b²+b³+… +b^d = O(b^d+1)
• Space? O(b^d+1) (keeps every node in memory)
• Optimal? Yes (if cost = 1 per step)

​

• Space is the bigger problem (more than time)�

Blind Search

24

Properties of breadth-first search

Blind Search

25

Uniform-cost search

• Expand least-cost unexpanded node
• Implementation:
• fringe = queue ordered by path cost
• �

Blind Search

26

Uniform-cost search

• Equivalent to breadth-first if step costs all equal
• Complete? Yes, if step cost ≥ ε
• Time? # of nodes with g ≤ cost of optimal solution, O(b^{ceiling(C*/ ε)}) where C^* is the cost of the optimal solution
• Space? # of nodes with g ≤ cost of optimal solution, O(b^{ceiling(C*/ ε)})
• Optimal? Yes – nodes expanded in increasing order of g(n)�

Blind Search

27

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

Blind Search

28

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

Blind Search

29

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

30

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

31

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

32

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

33

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

34

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

35

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

36

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

37

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

38

Depth-first search

• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front�

Blind Search

39

Properties of depth-first search

• Complete? No: infinite-depth, loops
• Modify to avoid repeated states along path

🡪 complete in finite spaces

• Time? O(b^m): terrible if m is much larger than d
• if solutions are dense, may be faster than BFS
• Space? O(bm), i.e., linear space!
• Optimal? No�

Blind Search

40

Depth-limited search

= depth-first search with depth limit l,

i.e., nodes at depth l have no successors�

Blind Search

41

Iterative deepening search

Blind Search

42

Iterative deepening search l =0

Blind Search

43

Iterative deepening search l =1

Blind Search

44

Iterative deepening search l =2

Blind Search

45

Iterative deepening search l =3

Blind Search

46

Iterative deepening search

• Nodes generated in a DLS to d with branching factor b:

N_DLS = b⁰ + b¹ + b² + … + b^d-2 + b^d-1 + b^d

​

• Nodes generated in an IDS to d with branching factor b:

N_IDS = (d+1)b⁰ + d b¹ + (d-1)b² + … + 3b^d-2 +2b^d-1 + 1b^d

​

• For b = 10, d = 5,
• N_DLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111�
• N_IDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

​

• Overhead = (123,456 - 111,111)/111,111 = 11%

Blind Search

47

Properties of iterative deepening search

• Complete? Yes
• Time? O(b^d)
• Space? O(bd)
• Optimal? Yes, if step cost = 1

Blind Search

48

Summary of algorithms

+1 wrong -> 1+

Blind Search

49

Repeated states

• Failure to detect repeated states can turn a linear problem into an exponential one!�

Blind Search

50

Summary

• Problem formulation usually requires abstracting away real-world details to define a state space that can feasibly be explored

​

• Variety of uninformed search strategies

​

• Iterative deepening search uses only linear space and not much more time than other uninformed algorithms�

Blind Search

51