DOC PREVIEW
CMU CS 15381 - Uninformed Search

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CMU CS 15381 - Uninformed Search

Documents in this Course
Planning

Planning

19 pages

Planning

Planning

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

27 pages

Lecture

Lecture

19 pages

FOL

FOL

41 pages

lecture

lecture

34 pages

Exam

Exam

7 pages

Lecture

Lecture

22 pages

Handout

Handout

11 pages

Midterm

Midterm

14 pages

lecture

lecture

83 pages

Handouts

Handouts

38 pages

mdp

mdp

37 pages

HW2

HW2

7 pages

nn

nn

25 pages

lecture

lecture

13 pages

Handout

Handout

5 pages

Lecture

Lecture

27 pages

Lecture

Lecture

62 pages

Lecture

Lecture

5 pages

Load more
Download Uninformed Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Uninformed Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Uninformed Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?