This preview shows page 1-2-3-4-5-6-7-8-9-10-73-74-75-76-77-78-79-80-81-82-83-147-148-149-150-151-152-153-154-155-156 out of 156 pages.
Last time: SummaryOutline: Problem solving and searchExample: Measuring problem!Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Which solution do we prefer?Problem-Solving AgentExample: BucketsRemember (lecture 2): Environment typesProblem typesSlide 24Slide 25Slide 26Slide 27Example: Vacuum worldSlide 29Slide 30Slide 31Example: RomaniaExample: Traveling from Arad To BucharestProblem formulationSelecting a state spaceExample: 8-puzzleSlide 37Slide 38Back to Vacuum WorldSlide 40Example: Robotic AssemblyReal-life example: VLSI LayoutSlide 43Slide 44Slide 45Slide 46Search algorithmsLast time: Problem-SolvingSlide 49Slide 50Last time: Finding a solutionSlide 52Slide 53Slide 54From problem space to search treePaths in search treesGeneral search exampleSlide 58Slide 59Slide 60Implementation of search algorithmsEncapsulating state information in nodesEvaluation of search strategiesBinary Tree ExampleComplexityComplexity: Tower of HanoiSlide 67Slide 68Slide 69Slide 70Slide 71Slide 72Complexity example: Traveling Salesman ProblemSlide 74Why is exponential complexity “hard”?So…Slide 77Slide 78Note on NP-hard problemsComplexity: O() and o() measures (Landau symbols)Landau symbolsExamples, propertiesPolynomial-time hierarchyComplexity and the human brainRemember: Implementation of search algorithmsSlide 86Slide 87Note: ApproximationsUninformed search strategiesBreadth-first searchSlide 91Slide 92Slide 93Slide 94Slide 95Properties of breadth-first searchSlide 97Time complexity of breadth-first searchSpace complexity of breadth-firstUniform-cost searchRomania with step costs in kmSlide 102Slide 103Slide 104Properties of uniform-cost searchImplementation of uniform-cost searchCaution!Note: Loop DetectionExampleBreadth-First Search SolutionUniform-Cost Search SolutionNote: Queueing in Uniform-Cost SearchA Clean Robust AlgorithmSlide 114Slide 115Slide 116Slide 117Slide 118Slide 119Slide 120Slide 121Slide 122Slide 123More examples…Depth-first searchDepth First SearchSlide 127Slide 128Slide 129Slide 130Properties of depth-first searchTime complexity of depth-first: detailsSpace complexity of depth-firstAvoiding repeated statesDepth-limited searchIterative deepening searchSlide 137Slide 138Slide 139Slide 140Slide 141Slide 142Slide 143Slide 144Slide 145Iterative deepening complexitySlide 147Bidirectional searchSlide 149Slide 150Slide 151Bidirectional SearchSlide 153Slide 154Comparing uninformed search strategiesSummaryCS 561, Lectures 3-51Last time: Summary•Definition of AI?•Turing Test?•Intelligent Agents:•Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its effectors to maximize progress towards its goals.•PAGE (Percepts, Actions, Goals, Environment)•Described as a Perception (sequence) to Action Mapping: f : P* A•Using look-up-table, closed form, etc.•Agent Types: Reflex, state-based, goal-based, utility-based•Rational Action: The action that maximizes the expected value of the performance measure given the percept sequence to dateCS 561, Lectures 3-52Outline: Problem solving and search•Introduction to Problem Solving•Complexity•Uninformed search•Problem formulation•Search strategies: depth-first, breadth-first•Informed search•Search strategies: best-first, A*•Heuristic functionsCS 561, Lectures 3-53Example: Measuring problem!Problem: Using these three buckets,measure 7 liters of water.3 l5 l9 lCS 561, Lectures 3-54Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-55Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-56Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-57Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-58Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-59Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-510Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-511Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-512Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-513Example: Measuring problem!•(one possible) Solution:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-514Example: Measuring problem!•Another Solution:a b c0 0 0 start0 5 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-515Example: Measuring problem!•Another Solution:a b c0 0 0 start0 5 03 2 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-516Example: Measuring problem!•Another Solution:a b c0 0 0 start0 5 03 2 03 0 23 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-517Example: Measuring problem!•Another Solution:a b c0 0 0 start0 5 03 2 03 0 23 5 20 0 63 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-518Example: Measuring problem!•Another Solution:a b c0 0 0 start0 5 03 2 03 0 23 5 23 0 7 goal3 0 60 3 63 3 61 5 60 5 7 goal3 l5 l9 la b cCS 561, Lectures 3-519Which solution do we prefer?•Solution 1:a b c0 0 0 start3 0 00 0 33 0 30 0 63 0 60 3 63 3 61 5 60 5 7 goal•Solution 2:a b c0 0 0 start0 5 03 2 03 0 23 5 23 0 7 goalCS 561, Lectures 3-520Problem-Solving AgentNote: This is offline problem-solving. Online problem-solving involves acting w/o complete knowledge of the problem and environmentaction// From LA to San Diego (given curr. state)// e.g., Gas usage // What is the current state?// If fails to reach goal, updateCS 561, Lectures 3-521Example: BucketsMeasure 7 liters of water using a 3-liter, a 5-liter, and a 9-liter buckets.•Formulate goal: Have 7
View Full Document
Unlocking...