1Search: Uninformed SearchMaterial in part from http://www.cs.cmu.edu/~awm/tutorialsRussel & Norvig Chap. 3A Search Problem• Find a path from START to GOAL• Find the minimum number of transitionsbadpqhecfrSTARTGOAL2Example2831647528316475START GOALExample• State: Configuration of puzzle• Transitions: Up to 4 possible moves (up, down, left, right)• Solvable in 22 steps (average)• But: 1.8 105 states (1.3 1012 states for the 15-puzzle) Cannot represent set of states explicitly2831647528316475START GOAL3Example: Robot NavigationXxSTARTGOALStates = positions in the mapTransitions = allowed motionsNESWNavigation: Going from point START to point GOAL given a (deterministic) mapOther Real-Life ExamplesProtein designhttp://www.blueprint.org/proteinfolding/trades/trades_problem.htmlScheduling/Manufacturinghttp://www.ozone.ri.cmu.edu/projects/dms/dmsmain.htmlScheduling/Sciencehttp://www.ozone.ri.cmu.edu/projects/hsts/hstsmain.htmlRoute planningRobot navigationhttp://www.frc.ri.cmu.edu/projects/mars/dstar.htmlDon’t necessarily know explicitly the structure of a search problem410cm resolution4km2 = 4 108 statesWhat we are not addressing (yet)• Uncertainty/Chance State and transitions are known and deterministic• Game against adversary• Multiple agents/Cooperation• Continuous state space For now, the set of states is discrete5Overview• Definition and formulation• Optimality, Completeness, and Complexity• Uninformed Search– Breadth First Search– Search Trees– Depth First Search– Iterative Deepening• Informed Search– Best First Greedy Search– Heuristic Search, A*A Search ProblembadpqhecfrSTARTGOAL6Formulation• Q: Finite set of states• S Q: Non-empty set of start states• G Q: Non-empty set of goal states• succs: function Q P(Q)succs(s) = Set of states that can be reached from s in one step• cost: function QxQ Positive Numbers cost(s,s’) = Cost of taking a one-step transition from state s to state s’• Problem: Find a sequence {s1,…,sK} such that:1. s1S2. sKG3. si+1succs(si) 4. Σ cost(si, si+1) is the smallest among all possible sequences (desirable but optional)⊆⊆∈∈∈Example• Q = {START, GOAL, a, b, c, d, e, f, h, p, q, r}• S = {START} G = {GOAL}• succs(d) = {b,c}• succs(START) = {p,e,d}• succs(a) = NULL• cost(s,s’) = 1 for all transitionsbadpqhecfrSTARTGOAL7Desirable Properties• Completeness: An algorithm is complete if it is guaranteed to find a path if one exists• Optimality: The total cost of the path is the lowest among all possible paths from start to goal• Time Complexity• Space ComplexitybadpqhecfrSTARTGOALbadpqhecfrSTARTGOALBreadth-First Search• Label all states that are 0 steps from S Call that set VobadpqhecfrSTARTGOAL8Breadth-First Search• Label the successors of the states in Vothat are not yet labelled Set V1of states that are 1 step away from the startbadpqhecfrSTARTGOAL0 steps1 stepBreadth-First Search• Label the successors of the states in V1that are not yet labelled Set V2of states that are 1 step away from the startbadpqhecfrSTARTGOAL0 steps1 step2 steps9Breadth-First Search• Label the successors of the states in V2that are not yet labelled Set V3of states that are 1 step away from the startbadpqhecfrSTARTGOAL0 steps1 step2 steps3 stepsBreadth-First Search• Stop when goal is reached in the current expansion set goal can be reached in 4 stepsbadpqhecfrSTARTGOAL0 steps1 step2 steps3 steps4 steps10Recovering the Path• Record the predecessor state when labeling a new state• When I labeled GOAL, I was expanding the neighbors of f f is the predecessor of GOAL• When I labeled f, I was expanding the neighbors of r ris the predecessor of f• Final solution: {START, e, r, f, GOAL}badpqhecfrSTARTGOALUsing Backpointers• A backpointer previous(s) point to the node that stored the state that was expanded to label s• The path is recovered by following the backpointers starting at the goal statebadpqhecfrSTARTGOAL11Example: Robot NavigationXxSTARTGOALStates = positions in the mapTransitions = allowed motionsNESWNavigation: Going from point START to point GOAL given a (deterministic) mapBreadth First SearchV0 S (the set of start states)previous(START) := NULLk 0while (no goal state is in Vkand Vkis not empty) doVk+1 empty setFor each state s in VkFor each state s’ in succs(s)If s’ has not already been labeledSet previous(s’) sAdd s’ into Vk+1k k+1if Vkis empty signal FAILUREelse build the solution path thus: Define Sk= GOAL, and forall i <= k, define Si-1= previous(Si)Return path = {S1,.., Sk}12Properties• BFS can handle multiple start and goal states• Can work either by searching forward from the start or backward for the goal (forward/backward chaining)• (Which way is better?)• Guaranteed to find the lowest-cost path in terms of number of transitions??See maze exampleComplexity• N = Total number of states• B = Average number of successors (branching factor)• L = Length from start to goal with smallest number of stepsBreadth First SearchBFSSpaceTimeOptimalCompleteAlgorithm13V3V’3Bidirectional Search• BFS search simultaneously forward from START and backward from GOAL• When do the two search meet?• What stopping criterion should be used?• Under what condition is it optimal?STARTGOALV1V’1V2V’2Complexity• N = Total number of states• B = Average number of successors (branching factor)• L = Length for start to goal with smallest number of stepsBi-directional Breadth First SearchBIBFSBreadth First SearchBFSSpaceTimeOptimalCompleteAlgorithmB = 10, L = 6 22,200 states generated vs. ~107Major savings when bidirectional search is possible because2BL/2 << BL14Counting Transition Costs Instead of TransitionsbadpqhecfrSTARTGOAL213191582249555413Counting Transition Costs Instead of Transitions• BFS finds the shortest path in number of steps but does not take into account transition costs• Simple modification finds the least cost path• New field: At iteration k, g(s) = least cost path to s in kor fewer stepsbadpqhecfrSTARTGOAL21319158224955541315Uniform Cost Search• Strategy to select state to expand next• Use the state with the smallest value of g() so far• Use priority queue for efficient access to minimum g at every iterationPriority Queue• Priority queue = data structure in which data of the form (item, value) can be inserted and the item of minimum value can be
View Full Document