1Problem SolvingProblem SolvingRussell and Norvig: Chapter 3CSMSC 421 – Fall 2003Announcements and OutlineAnnouncements: Lise’s office hours: Thu 1:30-3:00 and by appt HW1 due next TueOutline: Problem Solving Agents Problem Formulation Basic SearchProblemProblem--Solving AgentSolving Agentenvironmentagent?sensorsactuatorsProblemProblem--Solving AgentSolving Agentenvironmentagent?sensorsactuators• Formulate Goal • Formulate Problem•States•Actions• Find Solution2Example: Route findingExample: Route findingHoliday PlanningOn holiday in Romania; Currently in Arad. Flight leaves tomorrow from Bucharest.Formulate Goal:Be in BucharestFormulate Problem:States: various citiesActions: drive between citiesFind solution:Sequence of cities: Arad, Sibiu, Fagaras, BucharestProblem FormulationGiurgiuUrziceniHirsovaEforieNeamtOradeaZerindAradTimisoaraLugojMehadiaDobretaCraiovaSibiuFagarasPitestiVasluiIasiRimnicu VilceaBucharest71751181117075120151140998097101211138146859098142928786GoalStartStatesActionsSolutionVacuum WorldRLSSSSRLRLRLSSSSLLLL RRRR3Search ProblemSearch ProblemState space each state is an abstract representation of the environment the state space is discreteInitial stateSuccessor functionGoal testPath costSearch ProblemSearch ProblemState spaceInitial state: usually the current state  sometimes one or several hypothetical states (“what if …”)Successor functionGoal testPath costSearch ProblemSearch ProblemState spaceInitial stateSuccessor function: [state Æ subset of states] an abstract representation of the possible actionsGoal testPath costSearch ProblemSearch ProblemState spaceInitial stateSuccessor functionGoal test: usually a condition sometimes the description of a statePath cost4Search ProblemSearch ProblemState spaceInitial stateSuccessor functionGoal testPath cost: [path Æ positive number] usually, path cost = sum of step costs e.g., number of moves of the empty tileExample: 8Example: 8--puzzlepuzzle1234567812345678Initial stateGoal stateExample: 8Example: 8--puzzlepuzzle12345678123456781234567812345678Example: 8Example: 8--puzzlepuzzleSize of the state space = 9!/2 = 181,44015-puzzle Æ .65 x 101224-puzzle Æ .5 x 102510 millions states/sec0.18 sec6 days12 billion years5Your Turn: Search ProblemYour Turn: Search ProblemState spaceInitial stateSuccessor functionGoal testPath costSearch of State SpaceSearch of State SpaceSearch of State SpaceSearch of State SpaceSearch State SpaceSearch State Space6Search of State SpaceSearch of State SpaceSearch of State SpaceSearch of State SpaceSearch of State SpaceSearch of State SpaceÆ search treeSimple Agent AlgorithmSimple Agent AlgorithmProblem-Solving-Agent1. initial-state Å sense/read state2. goal Å select/read goal3. successor Å select/read action models4. problem Å (initial-state, goal, successor)5. solution Å search(problem)6. perform(solution)7Example: 8Example: 8--queensqueensPlace 8 queens in a chessboard so that no two queens are in the same row, column, or diagonal.A solution Not a solutionExample: 8Example: 8--queensqueensFormulation #1:•States: any arrangement of 0 to 8 queens on the board• Initial state: 0 queens on the board• Successor function: add aqueen in any square• Goal test: 8 queens on theboard, none attackedÆ 648states with 8 queensExample: 8Example: 8--queensqueensFormulation #2:•States: any arrangement of k = 0 to 8 queens in the kleftmost columns with noneattacked• Initial state: 0 queens on the board• Successor function: add aqueen to any square in the leftmost empty column such that it is not attackedby any other queen• Goal test: 8 queens on theboardÆ 2,067 statesExample: Robot navigationExample: Robot navigationWhat is the state space?8Example: Robot navigationExample: Robot navigationCost of one horizontal/vertical step = 1Cost of one diagonal step = √2Example: Robot navigationExample: Robot navigationExample: Assembly PlanningExample: Assembly PlanningInitial stateGoal stateSuccessor function:• Merge two subassembliesComplex function:it must find if a collision-freemerging motion existsExample: Assembly PlanningExample: Assembly Planning9Example: Assembly PlanningExample: Assembly PlanningAssumptions in Basic SearchAssumptions in Basic SearchThe environment is staticThe environment is discretizableThe environment is observableThe actions are deterministicSimple Agent AlgorithmSimple Agent AlgorithmProblem-Solving-Agent1. initial-state Å sense/read state2. goal Å select/read goal3. successor Å select/read action models4. problem Å (initial-state, goal, successor)5. solution Å search(problem)6. perform(solution)Search of State SpaceSearch of State SpaceÆ search tree10Basic Search ConceptsBasic Search ConceptsSearch treeSearch node Node expansionSearch strategy: At each stage it determines which node to expandSearch Nodes Search Nodes ≠≠StatesStates123456781234567812345678135681345678247212345678The search tree may be infinite evenwhen the state space is finiteThe search tree may be infinite evenwhen the state space is finiteFringeFringeSet of search nodes that have not been expanded yetImplemented as a queue FRINGE INSERT(node,FRINGE) REMOVE(FRINGE)The ordering of the nodes in FRINGE defines the search strategySearch AlgorithmSearch Algorithm1. If GOAL?(initial-state) then return initial-state2. INSERT(initial-node,FRINGE)3. Repeat:If FRINGE is empty then return failuren Å REMOVE(FRINGE)s Å STATE(n)For every state s’ in SUCCESSORS(s) Create a node n’ If GOAL?(s’) then return path or goal state INSERT(n’,FRINGE)11Search StrategiesA strategy is defined by picking the order of node expansionStrategies 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 solutionTime and space complexity are measured in terms of b – maximum brancing factor of the search tree d – depth of the least-cost solution m – maximum depth of the state space (may be ∞)Important RemarkImportant RemarkSome problems formulated as search problems are NP-hard problems. We cannot expect to solve such a problem in less than exponential time in the worst-caseBut we can nevertheless strive to solve as many instances of the problem as possible Blind vs. Heuristic