1Problem Solving and Search2Problem Solving•Rational agents need to perform sequences of actions inorder to achieve goals.•Intelligent behavior can be generated by having a look-uptable or reactive policy that tells the agent what to do inevery circumstance, but:-Such a table or policy is difficult to build-All contingencies must be anticipated•A more general approach is for the agent to haveknowledge of the world and how its actions affect it and beable to simulate execution of actions in an internal model ofthe world in order to determine a sequence of actions thatwill accomplish its goals.•This is the general task of problem solving and is typicallyperformed by searching through an internally modelledspace of world states.3Problem Solving Task•Given:-An initial state of the world-A set of possible possible actions or operators that canbe performed.-A goal test that can be applied to a single state of theworld to determine if it is a goal state.•Find:-A solution stated as a path of states and operators thatshows how to transform the initial state into one thatsatisfies the goal test.•The initial state and set of operators implicitly define a statespace of states of the world and operator transitionsbetween them. May be infinite.4Measuring Performance•Path cost: a function that assigns a cost to a path, typicallyby summing the cost of the individual operators in the path.May want to find minimum cost solution.•Search cost: The computational time and space (memory)required to find the solution.•Generally there is a trade-off between path cost and searchcost and one must satisfice and find the best solution inthe time that is available.5Sample Route Finding Problem Initial state: Arad Goal state: Bucharest Path cost: Number of intermediate cities, distance traveled, expected travel timeGiurgiuUrziceniHirsovaEforieNeamtOradeaZerindAradTimisoaraLugojMehadiaDobretaCraiovaSibiuFagarasPitestiVasluiIasiRimnicu VilceaBucharest6Sample “Toy” Problems•8-puzzle (sliding tile puzzle)•Peg Puzzle (Hi-Q)•Cryptarithmetic FORTY 29786 F=2, O=9, R=7, T=8,...+ TEN + 850+ TEN + 850 ---------- --------- SIXTY 31486Start StateGoal State2456781 234678123456781234567857“Toy” Problems (cont)•8-queens problem (N-queens problem)•Missionaries and cannibalsIdentity of individuals irrelevant,best to represent state as(M,C,B) M = number of missionaries on left bank C = number of cannibals on left bank B = number of boats on left bank (0 or 1)Operators to move: 1M, 1C, 2M, 2C, 1M1CGoal state: (0,0,0)8More Realistic Problems•Route finding•Travelling salesman problem•VLSI layout•Robot navigation•Web searching9Searching Concepts•A state can be expanded by generating all states that canbe reached by applying a legal operator to the state.•State space can also be defined by a successor functionthat returns all states produced by applying a single legaloperator.•A search tree is generated by generating search nodes bysuccessively expanding states starting from the initial stateas the root.•A search node in the tree can contain-Corresponding state-Parent node-Operator applied to reach this node-Length of path from root to node (depth)-Path cost of path from initial state to node10Expanding Nodes and SearchTimisoaraTimisoara(a) The initial stateArad(b) After expanding Arad(c) After expanding SibiuAradSibiu ZerindRimnicu VilceaOradeaFagarasAradAradSibiu Zerindfunction GENERAL-SEARCH(problem,strategy) returns a solution, or failureinitialize the search tree using the initial state of problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add the resulting nodes to the search treeend11Search Algorithm•Easiest way to implement various search strategies is tomaintain a queue of unexpanded search nodes.•Different strategies result from different methods forinserting new nodes in the queue.function GENERAL-SEARCH(problem,QUEUING-FN) returns a solution, or failurenodes MAKE-QUEUE(MAKE-NODE(INITIAL-STATE[problem]))loop doif nodes is empty then return failurenode REMOVE-FRONT(nodes)if GOAL-TEST[problem] applied to STATE(node) succeeds then return nodenodes QUEUING-FN(nodes,EXPAND(node, OPERATORS[problem]))end12Search Strategies•Properties of search strategies-Completeness-Time Complexity-Space Complexity-Optimality•Uniformed search strategies (blind, exhaustive, brute-force) do not guide the search with any additionalinformation about the problem.•Informed search strategies (heuristic, intelligent) useinformation about the problem (estimated distance from astate to the goal) to guide the search.13Breadth-First Search•Expands search nodes level by level, all nodes at level dare expanded before expanding nodes at level d+1•Implemented by adding new nodes to the end of the queue(FIFO queue): GENERAL-SEARCH(problem, ENQUEUE-AT-END)•Since eventually visits every node to a given depth,guaranteed to be complete.•Also optimal provided path cost is a nondecreasing functionof the depth of the node (e.g. all operators of equal cost)since nodes explored in depth order.14Breadth-First Complexity•Assume there are an average of b successors to eachnode, called the branching factor.•Therefore, to find a solution path of length d must explorenodes.•Plus need bdnodes in memory to store leaves in queue.•Assuming can expand and check 1000 nodes/sec and need100 bytes/node storage , b=10Note memory is a bigger problem than time.1 b b+2b3… bd+ + + +Depth Nodes Time Memory0 1 1 millisecond 100 bytes2 111 .1 seconds 11 kilobytes4 11,111 11 seconds 1 megabyte6 10618 minutes 111 megabytes8 10831 hours 11 gigabytes10 1010128 days 1 terabyte12 101235 years 111 terabytes14 10143500 years 11,111 terabytes15Uniform Cost Search•Like breadth-first except always expand node of least costinstead of of least depth (i.e. sort new queue by path cost).•Do not recognize goal until it is the least cost node on thequeue and removed for goal testing.•Therefore, guarantees optimality as long as path cost neverdecreases as a path increases (non-negative operatorcosts).(a) (b)S0SA B C1 5 155 15SA B CG11SA B C15G11G10S GABC1 105515516Depth-First Search•Always