Brian Williams, Spring 03 1Problem Solving as State Space SearchBrian C. Williams16.070 April 15th, 2003Slides adapted from:6.034 Tomas Lozano Perez,Russell and Norvig AIMABrian Williams, Spring 03 2courtesy of JPLSelf-Diagnosing ExplorersBrian Williams, Spring 03 3In Space The Exception is the Rulecourtesy of NASA• Quintuple fault occurs (three shorts, tank-line and pressure jacket burst, panel flies off). • Power limitations too severe to perform new mission..• Novel reconfiguration identified, exploiting LEM batteries for power.• Swaggert & Lovell work on Apollo 13 emergency rig lithium hydroxide unit. APOLLO 13Brian Williams, Spring 03 4Complex missions must carefully:• Plan complex sequences of actions• Schedule tight resources• Monitor and diagnose behavior• Repair or reconfigure hardware.ð Most Autonomy problems, search through a space of options. ð We formulate as state space search.Brian Williams, Spring 03 5Outline• Problem encoding as state space search• Graphs and search trees• Depth and breadth-first searchBrian Williams, Spring 03 6Early AI: What are the universal problem solving methods?AstronautGooseGrainFoxRoverCan the astronaut get its produce safely across the Martian canal?• Astronaut + 1 item allowed in the rover.• Goose alone eats Grain• Fox alone eats GooseSimple TrivialBrian Williams, Spring 03 7Problem Solving as State Space Search• Formulate Goal• Formulate Problem– States– Operators• Generate Solution– Sequence of statesBrian Williams, Spring 03 8Problem Solving as State Space Search• Formulate Goal– 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 itemsto other bank.Brian Williams, Spring 03 9AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAstronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAstronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautAstronautGooseGrainFoxBrian Williams, Spring 03 10Example: 8-Puzzle• States: • Operators: • Goal Test:5 46 17 3821 2837 645Start Goalinteger location for each tile AND …move empty square up, down, left, rightgoal state as givenBrian Williams, Spring 03 14Outline• Problem encoding as state space search• Graphs and search trees• Depth and breadth-first searchBrian Williams, Spring 03 15Problem Formulation: A GraphOperatorLink(edge)StateNode(vertex)DirectedGraph(one-way streets)UndirectedGraph(two-way streets)Brian Williams, Spring 03 16Examples of GraphsSan FranBostonLADallasWash DCAirline RoutesA B CA BCA BCABCPut C on BPut C on APut B on CPut C on AABCPut A on CPlanning Actions(graph of possible states of the world)Brian Williams, Spring 03 17A Solution is a State Sequence:Problem Solving Searches PathsCSBGADSDACRepresent searched paths using a tree.Brian Williams, Spring 03 18A Solution is a State Sequence:Problem Solving Searches PathsCSBGADSDAC GRepresent searched paths using a tree.Brian Williams, Spring 03 19A Solution is a State Sequence:Problem Solving Searches PathsCSBGADSDBAC GC GDC GRepresent searched paths using a tree.Brian Williams, Spring 03 20Search TreesRootLink(edge)Node(vertex)Brian Williams, Spring 03 21Search TreesParent(Ancestor)Child(Descendant)SiblingsBrian Williams, Spring 03 22Outline• Problem encoding as state space search• Graphs and search trees• Depth and breadth-first search– Depth first in lecture– Breadth first at homeBrian Williams, Spring 03 23Classes of SearchBlind Depth-First Systematic exploration of whole tree(uninformed) Breadth-First until the goal is found.Iterative-DeepeningHeuristic Hill-Climbing Uses heuristic measure of goodnessBest-First of a node,e.g. estimated distance to.Beam goal.Optimal Branch&Bound Uses path “length” measure. FindsA* “shortest” path. A* also uses heuristicBrian Williams, Spring 03 24Classes of SearchBlind Depth-First Systematic exploration of whole tree(uninformed) Breadth-First until the goal is found.Iterative-DeepeningBrian Williams, Spring 03 25Depth First Search (DFS)SDBAC GC GDC GIdea: •Explore descendants before siblings•Explore siblings left to right1234567891011SADC GCBDC GGBrian Williams, Spring 03 26Breadth First Search (BFS)SDBAC GC GDC GIdea: •Explore relatives at same level before their children•Explore relatives left to right1248953610117SADC GCBDC GGBrian Williams, Spring 03 27Elements of Algorithm DesignDescription: – 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?• Optimality:– is the algorithm guaranteed to find a best 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?Brian Williams, Spring 03 28Outline• Problem encoding as state space search• Graphs and search trees• Depth and breadth-first search– A generic search algorithm– Depth-first search example– Handling cycles– Breadth-first search example (do at home)Brian Williams, Spring 03 29Simple Search AlgorithmHow 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).• Search repeatedly:• Selects next partial path • Expands it.• Terminates when goal found.SDBAC GC GDC GBrian Williams, Spring 03 30Simple Search Algorithm•Let S denote the start node and G a 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.• The Q is a list of partial paths, • e.g. ((D A S) (C A S) …).SDBAC GC GDC GBrian Williams, Spring 03 31Simple Search AlgorithmLet 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 Q3. If head(N) = G, return N (goal reached!)4. Else: a) Remove N from Qb) Find all children of head(N) and create all the one-step extensions of N to each child.c) Add all extended paths to Qd) Go to step 2.Brian