CS 460, Lectures 3-51Last time: Summary• Definition of AI?• Turing Test?• Intelligent Agents:• Anything that can be viewed asperceiving 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 460, 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 460, Lectures 3-53Example: Measuring problem!Problem: Using these three buckets,measure 7 liters of water.3 l5 l9 lCS 460, Lectures 3-54Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-55Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-56Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-57Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-58Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-59Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-510Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-511Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-512Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-513Example: Measuring problem!• (one possible) Solution:abc000start300003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-514Example: Measuring problem!• Another Solution:abc000start050003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-515Example: Measuring problem!• Another Solution:abc000start050320003303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-516Example: Measuring problem!• Another Solution:abc000start050320302303006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-517Example: Measuring problem!• Another Solution:abc000start050320302352006306036336156057goal3 l5 l9 labcCS 460, Lectures 3-518Example: Measuring problem!• Another Solution:abc000start050320302352307goal306036336156057goal3 l5 l9 labcCS 460, Lectures 3-519Which solution do we prefer?• Solution 1:abc000start300003303006306036336156057goal• Solution 2:abc000start050320302352307goalCS 460, Lectures 3-520Problem-Solving AgentNote: This is offlineproblem-solving. Onlineproblem-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 460, Lectures 3-521Example: BucketsMeasure 7 liters of water using a 3-liter, a 5-liter, and a 9-liter buckets.• Formulate goal: Have 7 liters of waterin 9-liter bucket• Formulate problem:• States: amount of water in the buckets• Operators: Fill bucket from source, empty bucket• Find solution: sequence of operators that bring youfrom current state to the goal stateCS 460, Lectures 3-522Remember (lecture 2): Environment typesNoSemiNoSemiNoMarsNoNoNoNoNoOffice EnvironmentYes/NoNoYes/NoYesYesVirtual RealityYesNoNoYesYesOperating SystemDiscreteStaticEpisodicDeterministicAccessibleEnvironmentThe environment types largely determine the agent design.CS 460, Lectures 3-523Problem types• Single-state problem: deterministic, accessibleAgent knows everything about world, thus cancalculate optimal action sequence to reach goal state.• Multiple-state problem: deterministic, inaccessibleAgent must reason about sequences of actions andstates assumed while working towards goal state.• Contingency problem: nondeterministic, inaccessible•Must use sensors during execution•Solution is a tree or policy•Often interleave search and execution• Exploration problem: unknown state spaceDiscover and learn about environment while taking actions.CS 460, Lectures 3-524Problem types• Single-state problem: deterministic, accessible• Agent knows everything about world (the exact state),• Can calculate optimal action sequence to reach goal state.• E.g., playing chess. Any action will result in an exact stateCS 460, Lectures 3-525Problem types• Multiple-state problem: deterministic, inaccessible• Agent does not know the exact state (could be in any of the possible states)• May not have sensor at all• Assume states while working towards goal state.• E.g., walking in a dark room• If you are at the door, going straight will lead you to the kitchen• If you are at the kitchen, turning left leads you to the bedroom• …CS 460, Lectures 3-526Problem types• Contingency problem: nondeterministic, inaccessible• Must use sensors during execution• Solution is a tree or policy• Often interleave search and execution• E.g., a new skater in an arena• Sliding problem.• Many skaters aroundCS 460, Lectures 3-527Problem types• Exploration problem: unknown state spaceDiscover and learn about environment while taking actions.•E.g., MazeCS 460, Lectures 3-528Example: Vacuum worldSimplified world: 2 locations, each may or not contain dirt,each may or not contain vacuuming agent.Goal of agent: clean up the dirt.CS 460, Lectures 3-529Example: Romania• In Romania, on vacation. Currently in Arad.• Flight leaves tomorrow from Bucharest.• Formulate goal:Ø be in Bucharest• Formulate problem:Ø states: various citiesØ operators: drive between cities• Find solution:Ø sequence of cities, such that total driving distance is minimized.CS 460, Lectures 3-530Example: Traveling from Arad To BucharestCS 460, Lectures 3-531Problem formulationCS 460, Lectures 3-532Selecting a state space• Real