1 Brian Williams, Spring 03 1 Problem Solving as State Space Search Brian C. Williams 16.410-13 Sep 15 th , 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Russell and Norvig AIMA Brian Williams, Spring 03 2 Complex missions must carefully: ? Plan complex sequences of actions Schedule tight resources Monitor and diagnose behavior Repair or reconfigure hardware. ? Most AI problems, like these, may be formulated as state space search. Courtesy of NASA/JPL-Caltech. http://www.jpl.nasa.gov. 2 Brian Williams, Spring 03 3 Assignments Remember: Problem set #1: Rules and Scheme due today September 15th, 2003. Reading: – Solving problems by searching: AIMA Ch. 3 Homework for this lecture: – Problem set #2 due Monday, Sept. 22 Brian Williams, Spring 03 4 Outline Problem Formulation – Problem solving as state space search Mathematical Model – Graphs and search trees Reasoning Algorithms – Depth and breadth-first search 3 Brian Williams, Spring 03 5 Early AI: What are the universal problem solving methods? Astronaut Goose Grain Fox Rover Can the astronaut get its produce safely across the Martian canal? Astronaut + 1 item allowed in the rover. Goose alone eats Grain Fox alone eats Goose Simple Trivial Brian Williams, Spring 03 6 Problem Solving as State Space Search Formulate Goal – State Astronaut, Fox, Goose & Grain across river Formulate Problem – States Location of Astronaut, Fox, Goose & Grain at top or bottom river bank – Operators Move rover with astronaut & 1 or 0 items to other bank. Generate Solution – Sequence of States Move(goose,astronaut), Move(astronaut), . . . Image taken from NASA's website: http://www.nasa.gov. 4 Brian Williams, Spring 03 7 Astronaut Goose Grain Fox Grain Fox Astronaut Goose Astronaut Grain Fox Goose Goose Astronaut Fox Grain Astronaut Goose Grain Fox Astronaut Goose Grain Fox Grain Astronaut Goose Fox Astronaut Goose Grain Fox Fox Astronaut Goose Grain Astronaut Goose Fox Grain Goose Fox Astronaut Grain Goose Grain Astronaut Fox Astronaut Grain Goose Fox Astronaut Fox Goose Grain Goose Grain Fox Astronaut Astronaut Goose Grain Fox Brian Williams, Spring 03 8 Astronaut Goose Grain Fox Grain Fox Astronaut Goose Astronaut Grain Fox Goose Goose Astronaut Fox Grain Astronaut Goose Grain Fox Astronaut Goose Grain Fox Grain Astronaut Goose Fox Astronaut Goose Grain Fox Fox Astronaut Goose Grain Astronaut Goose Fox Grain Goose Fox Astronaut Grain Goose Grain Astronaut Fox Astronaut Grain Goose Fox Astronaut Fox Goose Grain Goose Grain Fox Astronaut Astronaut Goose Grain Fox 5 Brian Williams, Spring 03 9 Example: 8-Puzzle States: Operators: Goal Test: 5 4 6 1 7 3 8 2 1 2 8 3 7 6 4 5 Start Goal integer location for each tile AND … move empty square up, down, left, right goal state as given Brian Williams, Spring 03 10 Planning as State Space Search: STRIPS Operator Representation ?Effects specify how to change the set of assertions. a a north11 W0 W1 ? Initial state: (and (block a) (block b) (block c) (on-table a) (on-table b) (clear a) (clear b) (clear c) (arm-empty)) ? goal (partial state): (and (on a b) (on b c))) ? Available actions ? Strips operators precondition: (and (agent-at 1 1) (agent-facing north)) effect: (and (agent-at 1 2) (not (agent-at 1 1))) North11 6 Brian Williams, Spring 03 11 STRIPS Action Schemata (:operator pick-up :parameters ((block ?ob1)) :precondition (and (clear ?ob1) (on-table ?ob1) (arm-empty)) :effect (and (not (clear ?ob1)) (not (on-table ?ob1)) (not (arm-empty)) (holding ?ob1))) Instead of defining: pickup-A and pickup-B and … Define a schema: N o t e : s t r i p s d o e s n ’ t a l l o w d e r i v e d e f f e c t s ; y o u m u s t b e c o m p l e t e ! } Brian Williams, Spring 03 13 Outline Problem Formulation – Problem solving as state space search Mathematical Model – Graphs and search trees Reasoning Algorithms – Depth and breadth-first search 7 Brian Williams, Spring 03 14 Problem Formulation: A Graph Operator Link (edge) State Node (vertex) Directed Graph (one-way streets) Undirected Graph (two-way streets) Brian Williams, Spring 03 15 Examples of Graphs San Fran Boston LA Dallas Wash DC Airline Routes A B C A B C A B C A B C Put C on B Put C on A Put B on C Put C on A A B C Put A on C Planning Actions (graph of possible states of the world) 8 Brian Williams, Spring 03 16 A Graph San Fran Boston LA Dallas Wash DC Airline Routes A Graph G is represented as a pair <V,E>, where: V is a set of vertices E is a set of (directed) edges An edge is a pair <v1, v2> of vertices, where v2 is the head of the edge, and v1 is the tail of the edge < {Bos, SFO, LA, Dallas, Wash DC} {<SFO, Bos>, <SFO, LA> <LA, Dallas> <Dallas, Wash DC> . . .} > Brian Williams, Spring 03 17 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D A C Represent searched paths using a tree. <S, A, D, C> 9 Brian Williams, Spring 03 18 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D A C G Represent searched paths using a tree. Brian Williams, Spring 03 19 A Solution is a State Sequence: Problem Solving Searches Paths C S B G A D S D BA C G C G D C G Represent searched paths using a tree. 10 Brian Williams, Spring 03 20 Search Trees Root Link (edge) Node (vertex) Brian Williams, Spring 03 21 Search Trees Parent (Ancestor) Child (Descendant) Siblings 11 Brian Williams, Spring 03 22 Outline Problem Formulation – Problem solving as state space search Mathematical Model – Graphs and search trees Reasoning Algorithms – Depth and breadth-first search Brian Williams, Spring 03 23 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Heuristic Hill-Climbing Uses heuristic measure of goodness (informed) Best-First of a node,e.g. estimated distance to. Beam goal. Optimal Branch&Bound Uses path “length” measure. Finds (informed) A* “shortest” path. A* also uses heuristic 12 Brian Williams, Spring 03 24 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Brian Williams, Spring 03 25 Depth First Search (DFS) S D BA C G C G D C G Idea: Explore descendants before siblings Explore siblings left to right 1 2 3 4 5 6 7 8 9 10 11 13 Brian Williams, Spring 03 26 Breadth First Search (BFS) S D BA C G C G D C G Idea: Explore relatives at same level before their children Explore relatives left to right 1 2 4 8 9 5 3 6 10 11 7 Brian Williams, Spring 03 27 Elements of Algorithm Design Description: – stylized pseudo code, sufficient to analyze and implement the algorithm. Analysis: Soundness: – is a solution returned by the algorithm guaranteed to be correct? Completeness: – is the algorithm guaranteed to find a solution when there is one? Time complexity: – how long does it take to find a solution? Space complexity: – how much memory does it need to perform search? 14 Brian Williams, Spring 03 28 Outline Problem Formulation: State space search Model: Graphs and search trees Reasoning Algorithms: DFS and BFS – A generic search algorithm – Depth-first search example – Handling cycles – Breadth-first search example Brian Williams, Spring 03 29 Simple Search Algorithm How do we maintain the Search State? ? A set of partial paths explored thus far. ? An ordering on which partial path to expand next ? called a queue Q. How do we search? ? Repeatedly: ? Select next partial path ? Expand it. ? Terminate when goal found. S D BA C G C G D C G 15 Brian Williams, Spring 03 30 Simple Search Algorithm ? S denotes the start node ? G denotes the goal node. ?A partial path is a path from S to some node D, ? e.g., (D A S) ? The head of a partial path is the most recent node of the path, ? e.g., D. ?TheQ is a list of partial paths, ? e.g. ((D A S) (C A S) …). S D BA C G C G D C G Brian Williams, Spring 03 31 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2. 16 Brian Williams, Spring 03 32 Outline Problem Formulation: State space search Model: Graphs and search trees Reasoning Algorithms: DFS and BFS – A generic search algorithm – Depth-first search example – Handling cycles – Breadth-first search example Brian Williams, Spring 03 33 Depth First Search (DFS) S D BA C G C G D C G Idea: Explore descendants before siblings Explore siblings left to right 1 2 3 4 5 6 7 8 9 10 11 Where do we place the children on the queue? Assume we pick first element of Q Add path extensions to ? of Q 17 Brian Williams, Spring 03 34 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2. Brian Williams, Spring 03 35 Depth-First Pick first element of Q; Add path extensions to front of Q C S B G A D Q 5 4 3 2 1(S) 1 18 Brian Williams, Spring 03 36 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2. Brian Williams, Spring 03 37 C S B G A D Q 5 4 3 2 1(S) 1 Depth-First Pick first element of Q; Add path extensions to front of Q 19 Brian Williams, Spring 03 38 C S B G A D Q 5 4 3 2 1 (A S) (S) 1 Added paths in blue Depth-First Pick first element of Q; Add path extensions to front of Q Brian Williams, Spring 03 39 C S B G A D Q 5 4 3 2 1 (A S) (B S) (S) 1 Added paths in blue Depth-First Pick first element of Q; Add path extensions to front of Q 20 Brian Williams, Spring 03 40 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2. Brian Williams, Spring 03 41 C S B G A D Q 5 4 3 2 1 (A S) (B S) (S) 1 Added paths in blue 2 Depth-First Pick first element of Q; Add path extensions to front of Q 21 Brian Williams, Spring 03 42 C S B G A D Q 5 4 3 2 1 (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 Depth-First Pick first element of Q; Add path extensions to front of Q Added paths in blue Brian Williams, Spring 03 43 C S B G A D Q 5 4 3 2 1 (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 Depth-First Pick first element of Q; Add path extensions to front of Q Added paths in blue 22 Brian Williams, Spring 03 44 C S B G A D Q 5 4 3 2 1 (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 Depth-First Pick first element of Q; Add path extensions to front of Q Added paths in blue Brian Williams, Spring 03 45 C S B G A D Q 5 4 3 2 1 (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 Depth-First Pick first element of Q; Add path extensions to front of Q Added paths in blue 23 Brian Williams, Spring 03 46 C S B G A D Q 5 4 3 2 1 (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First Pick first element of Q; Add path extensions to front of Q Added paths in blue Brian Williams, Spring 03 47 C S B G A D Q 5 4 3 2 1 (C D A S)(G D A S) (B S) (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First Pick first element of Q; Add path extensions to front of Q 24 Brian Williams, Spring 03 48 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) 2. If Q is empty, fail. Else, pick a partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else: a) Remove N from Q b) Find all children of head(N) and create all the one-step extensions of N to each child. c) Add all extended paths to Q d) Go to step 2. Brian Williams, Spring 03 49 C S B G A D Q 5 4 3 2 1 (C D A S)(G D A S) (B S) (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First Pick first element of Q; Add path extensions to front of Q 25 Brian Williams, Spring 03 50 C S B G A D (G D A S)(B S)6 Q 5 4 3 2 1 (C D A S)(G D A S) (B S) (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First Pick first element of Q; Add path extensions to front of Q Brian Williams, Spring 03 51 C S B G A D (G D A S)(B S)6 Q 5 4 3 2 1 (C D A S)(G D A S) (B S) (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First Pick first element of Q; Add path extensions to front of Q 26 Brian Williams, Spring 03 52 Outline Problem Formulation: State space search Model: Graphs and search trees Reasoning Algorithms: DFS and BFS – A generic search algorithm – Depth-first search example – Handling cycles – Breadth-first search example Brian Williams, Spring 03 53 C S B G A D Issue: Starting at S and moving top to bottom, will depth-first search ever reach G? 27 Brian Williams, Spring 03 54 C S B G A D (G D A S)(B S)6 Q 5 4 3 2 1 (C D A S)(G D A S) (B S) (D A S) (B S) (C A S) (D A S) (B S) (A S) (B S) (S) 1 2 3 4 Depth-First C visited multiple times Multiple paths to C, D & G How much wasted effort can be incurred in the worst case? Effort can be wasted in more mild cases Brian Williams, Spring 03 55 How Do We Avoid Repeat Visits? Idea: ? Keep track of nodes already visited. ? Do not place visited nodes on Q. Does this maintain correctness? ? Any goal reachable from a node that was visited a second time would be reachable from that node the first time. Does it always improve efficiency? ? Guarantees each node appears at most once at the head of a path in Q. 28 Brian Williams, Spring 03 56 Simple Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 1. Initialize Q with partial path (S) as only entry; set Visited = ( ) 2. If Q is empty, fail. Else, pick some partial path N from Q 3. If head(N) = G, return N (goal reached!) 4. Else a) Remove N from Q b) Find all children of head(N) not in Visited and create all the one-step extensions of N to each child. c) Add to Q all the extended paths; d) Add children of head(N) to Visited e) Go to step 2. Brian Williams, Spring 03 58 Outline Problem Formulation: State space search Model: Graphs and search trees Reasoning Algorithms: DFS and BFS – A generic search algorithm – Depth-first search example – Handling cycles – Breadth-first search example 29 Brian Williams, Spring 03 59 Breadth First Search (BFS) S D BA C G C G D C G Idea: Explore relatives at same level before their children Explore relatives left to right 1 2 4 8 9 5 3 6 10 11 7 Where do we place the children on the queue? Assume we pick first element of Q Add path extensions to ? of Q Brian Williams, Spring 03 60 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1S(S) 1 30 Brian Williams, Spring 03 61 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1 S(S) 1 Brian Williams, Spring 03 62 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1 A,B,S(A S) (B S) S(S) 1 31 Brian Williams, Spring 03 63 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1 A,B,S(A S) (B S) S(S) 1 2 Brian Williams, Spring 03 64 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1 C,D,B,A,S(B S) (C A S) (D A S) A,B,S(A S) (B S) S(S) 1 2 32 Brian Williams, Spring 03 65 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D 6 VisitedQ 5 4 3 2 1 C,D,B,A,S(B S) (C A S) (D A S) A,B,S(A S) (B S) S(S) 1 2 3 Brian Williams, Spring 03 70 Breadth-First Pick first element of Q; Add path extensions to end of Q C S B G A D G,C,D,B,A,S(G B S)6 VisitedQ 5 4 3 2 1 G,C,D,B,A,S(D A S) (G B S) G,C,D,B,A,S(C A S) (D A S) (G B S)* C,D,B,A,S(B S) (C A S) (D A S) A,B,S(A S) (B S) S(S) 1 2 3 4 5 6 33 Brian Williams, Spring 03 72 Depth First Search (DFS) S D BA C G C G D C G S D BA C G C G D C G Breadth First Search (BFS) For each search type, where do we place the children on the queue? Depth-first: Add path extensions to front of Q Pick first element of Q Breadth-first: Add path extensions to back of Q Pick first element of Q Brian Williams, Spring 03 73 Summary Most problem solving tasks may be formulated as state space search. Mathematical representations for search are graphs and search trees. Depth-first and breadth-first search may be framed, among others, as instances of a generic search strategy. Cycle detection is required to achieve efficiency and completeness. 34 Brian Williams, Spring 03 74 Appendix Brian Williams, Spring 03 81 Breadth-First (without Visited list) Pick first element of Q; Add path extensions to end of Q C S B G A D (G B S) (C D A S) (G D A S)7 (D B S) (G B S) (C D A S) (G D A S)6 Q 5 4 3 2 1 (D A S) (D B S) (G B S) (C A S) (D A S) (D B S) (G B S)* (B S) (C A S) (D A S) (A S) (B S) (S) 1 2 3 4 5 6 7