Searches (ai)

Outline CS380: Intro to Artificial Intelligence 9/29/2006 Jay Modi Department of Computer Science Drexel University www.cs.drexel.edu/~pmodi

An Example Search Problem

Problem Solving in Deterministic, SingleAgent Domains  Uninformed Search Methods  BFS, DFS, IDS

Terminology  b: branching factor, max number of next states of any state  d: steps to goal  m: maximum possible path length  Not always finite. Why not?

1

Terminology: States vs. Nodes

Tree search algorithms  A state is a property of the world, e.g., location  A node is a data structure which specifies state, parent node, action, path cost g(x), depth

 Basic idea:

 A state can have multiple nodes

Nodes State Sibiu

Arad

Fagaras

State: Sibiu State of Parent Node: Arad

 offline, simulated exploration of state space by generating successors of already-explored states (a.k.a.~expanding states)

State: Sibiu State of Parent Node: Fagaras

The Mother of All Search Algorithms  current state <− start state  loop:  is current state = the goal state? If yes, output path and terminate.  generate all next states of current state and add to fringe set  current state <− choose state from fringe set

Complications  How to choose next state from fringe set?  Answer has significant implications on:  Time complexity  Number of loops

 Space complexity  Size of fringe set

 Completeness  Does loop terminate

 Optimality All search algorithms can be viewed as instances of this. Simple, right?

 Quality of output path

2

How to Choose From Fringe Set?

Breadth-First Search

 One idea:  Implement fringe set as a First-in First-out (FIFO) queue f

-> e,d,c,b ->

a

 We call this Breadth-First Search Start State: A Current State: A Fringe Set: {}

Breadth-First Search

Start State: A Current State: A Fringe Set: {C, B} Choose next state: B

Breadth-First Search

Start State: A Current State: B Fringe Set: { E, D, C} Choose next state: C

3

Breadth-First Search

Properties of BFS  Is it Complete?  Is it Optimal?  Will it always return shortest path?

 Space complexity Start State: A Current State: C Fringe Set: { G, F, E, D} Choose next state: D

How to Choose From Fringe Set?

 How large can the fringe set get?  O(bd+1) :( Why?

 Time complexity?

Depth-First Search

 Another idea:  Implement fringe set as a Last-in,First-out (LIFO) queue f -> e,d,c,b,a f <- f,e,d,c,b,a

 We call this Depth-First Search

Start State: A Goal State: M Current State: A Fringe Set: {}

4

Depth-First Search

Start State: A Current State: A Fringe Set: {B, C} Choose Next State: B

Start State: A Current State: B Fringe Set: {D, E, C} Choose Next State: D

Depth-First Search

Start State: A Current State: B Fringe Set: {D, E, C} Choose Next State: D

Depth-First Search

Q: What would BFS do?

Depth-First Search

Start State: A Current State: D Fringe Set: {H,I,E,C} Choose Next State: H

5

Depth-First Search

Start State: A Current State: H Fringe Set: {I,E,C} Choose Next State: I

Depth-First Search

Start State: A Current State: E Fringe Set: {J, K ,C} Choose Next State: J

Depth-First Search

Start State: A Current State: I Fringe Set: {E,C} Choose Next State: E

Depth-First Search

Start State: A Current State: J Fringe Set: {K ,C} Choose Next State: K

6

Depth-First Search

Start State: A Current State: K Fringe Set: {C} Choose Next State: C

Depth-First Search

Start State: A Current State: F Fringe Set: {L, M, G} Choose Next State: L

Depth-First Search

Start State: A Current State: C Fringe Set: {F, G} Choose Next State: F

Depth-First Search

Start State: A Current State: L Fringe Set: {M, G} Choose Next State: M

7

Depth-First Search

Properties of depth-first search  Space?  bm+1

 Time?  Optimal?  Complete? Start State: A Goal Reached. Current State: M Algorithm Terminates Fringe Set: {G} Current State = Goal State

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

 No. Why?  Can we fix this?

Guaranteeing Completeness  Idea: Invoke Depth-Limited DFS with iteratively increasing values of L  We call this Iterative Deepening Search

 Idea: Cut off search after depth limit L  We call this Depth-Limited DFS  Is it complete?

8

Iterative deepening search l =0

Iterative deepening search l =1

Iterative deepening search l =2

Iterative deepening search l =3

9

Iterative deepening search  Iterative Deepening search repeatedly reexpanding nodes  Seems inefficient, but is it?

Iterative deepening search 

Number of nodes generated in a depth-limited search to depth d with branching factor b?  NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd



Number of nodes generated in an iterative deepening search to depth d with branching factor b?  NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd



For b = 10, d = 5,  NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111  NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Properties of iterative deepening search    

Complete? Time? Space? Optimal?



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



Iterative Deepening is the method of choice for searching large state spaces when depth of solution is not known

Properties of iterative deepening search    

Complete? Yes Time? d b1 + (d-1)b2 + … + bd = O(bd) Space? O(bd) Optimal? Yes, if step cost = 1

10

Bidirectional Search  In IDS, we saw that branching factor gets exponentially worse with depth

Path Costs  So far, we have assumed unit cost for each state transition.  What if each transition has a different cost?

Bidirectional Search  In IDS, we saw that branching factor gets exponentially worse with depth  Idea: Minimize depth by doing two parallel searches

How to Choose From Fringe Set?  A third idea:  Implement fringe set as an insert-in-order Priority queue (e,6) (b,10), (a,5), (d,3), (c,1)

 We call this Uniform-Cost Search

11

Uniform Cost Search 3

1

3

4

0

1

4

Start State: A Current State: A Fringe Set: {}

3

4

3

0

4

Start State: A Current State: A Fringe Set: {(C,3), (B,1)} Choose next state: B

Uniform Cost Search

3

Uniform Cost Search

1

3

4

0

Uniform Cost Search 1

4

Start State: A Current State: B Fringe Set: { (E,5), (D,4), (C,3)} Choose next state: C

3

4

3

0

4

Start State: A Current State: C Fringe Set: { (G, 7), (E,5), (D,4), (F,3)} Choose next state: F

12

Summary of algorithms

Summary  Agent and Environment Types  Variety of uninformed search strategies  Iterative deepening search uses only linear space and not much more time than other uninformed algorithms

13