1Last time: SummaryDefinition of AI?Definition of AI? Turing Test? Intelligent Agents: Anything that can be viewed as perceiving its environment through sensors and actingupon that environment1actingupon 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.Last time: Summary Agent Types: Reflex, state-based, goal-based, utility-basedRational Action:The action that2Rational Action:The action that maximizes the expected value of the performance measure given the percept sequence to date2Outline: Problem solving and searchIntroduction to Problem SolvingIntroduction to Problem Solving ComplexityUninformed search3Uninformed search Problem formulation Search strategies: depth-first, breadth-firstOutline: Problem solving and search Informed search Search strategies: best-first, A* Heuristic functions43Example: Measuring problem!3 l5 l9 l5 Problem: Using these three buckets, measure 7 liters of water.Problem-Solving Agenttion//From LA to San Diego (given current state)//e.g. Gas usage //What is the current state?6Note: This is offline problem-solving. Online problem-solving involves acting w/o complete knowledge of the problem and environment//If fails to reach goal, update4Example: BucketsMeasure 7 liters of water using a 3 liter a 5Measure 7 liters of water using a 3 liter, a 5 liter, and a 9 liter bucket. Formulate goal: Have 7 liters of water in 9-liter bucket Formulate problem:St ttf t ithbkt7States: amount of water in the buckets Operators: Fill bucket from source, empty bucket Find solution: sequence of operators that bring you from current state to the goal stateRemember (lecture 2): Environment typesEnvironment Accessibl Deterministi Episodic Static DiscreteecOperating SystemYes Yes No No YesVirtual Reality Yes Yes Yes/No No Yes/NoOffice EnvironmentNo No No No No8Mars No Semi No Semi NoThe environment types largely determine the agent design.•Accessible: The complete states of the environment is accessible.•Deterministic: The next state is determinable from the current state and the action.5Problem typesSinglestate problem:deterministicSingle-state problem:deterministic, accessibleAgent knows everything about world (the exact state), Can calculate optimal action sequence to reach goal state.9state.E.g. playing chess. Any action will result in an exact stateProblem typesMultiple-state problem:deterministic,Multiplestate problem:deterministic, inaccessibleAgent does not know the exact state (could be in any of the possible states)May not have sensor at allAssume states while working towards goal state.10E.g. walking in a dark roomIf you are at the door, going straight will lead you to the kitchenIf you are at the kitchen, turning left leads you to the bedroom…6Problem typesContingency problem:Contingency problem:nondeterministic, inaccessibleMust use sensors during executionSolution is a tree or policyOften interleave search and executionk11E.g. A new skater in an arenaSliding problem.Many skaters aroundProblem typesEl ti blkExploration problem: unknown state spaceDiscover and learn about environment while taking actions.E.g. Maze12E.g. Maze7Example: Vacuum worldSimplified world: 2 locations, each may or not contain dirt,pyeach may or not contain vacuuming agent.Goal of agent: clean up the dirt.13Example: Romania¾Formulate problem:¾Formulate problem:¾ states: various cities¾ operators: drive between citiesFind solution:14Find solution:¾ sequence of cities, such that total driving distance is minimized.8Example: Traveling from Arad To Bucharest15Problem formulation169Selecting a state spaceReal world is absurdly complex;Real world is absurdly complex; 17Example: 8-puzzleState:start state goal state18State: Operators: Goal test: Path cost:10Example: 8-puzzlestart state goal state Why search algorithms?19Back to Vacuum World2011Example: Robotic Assembly21& wire crossingcs;bout placement &22Enter schematido not worry ab1223Real-life example: VLSI LayoutQ: How to put these chips and connectionQ: How to put these chips and connection on a board?2413Real-life example: VLSI Layout“optimal way”??py¾ minimize surface area¾ minimize number of signal layers¾ minimize number of vias (connections from one layer to another)25to another)¾ minimize length of some signal lines (e.g., clock line)¾ distribute heat throughout board¾ etc.omponentsd tools to place cong.26Use automatedand route wirin1427Search algorithmsBasic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)2815Search algorithmsFunction General-Search(problem, strategy) returns a solution, or failurei iti li th h t i th i iti l t t blinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategy29gyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendExample: Traveling from Arad To Bucharest3016From problem space to search tree Some material in this and following slides is fromSome material in this and following slides is fromhttp://www.cs.kuleuven.ac.be/~dannyd/FAI/ check it out!AA BB CC334444Problem space31DD EE FFGGSS444455553322From problem space to search tree AA BB CC334444DD EE FFGGSS444455553322SSAA DDBB DD EEAA332222444444444455555555Problem spaceAssociated32CC EE EE BB BB FFDD FF BB FF CC EE AA CC GGGG CC GG FFGG3333333322224444444444444444444455555555loop-freesearch tree17Paths in search treesSSDenotes:Denotes:SSAA DDBB DD EEAACC EE EE BB BB FFDDFFBBFFCCEEAACCGGDenotes:Denotes:SASADenotes:Denotes:SDASDA33DDFFBBFFCCEEAACCGGGG CC GG FFGGDenotes:Denotes:SDEBASDEBAGeneral search example3418General search example35General search example3619General search example37Implementation of search algorithmsFunctionGeneral-Search(problem Queuing-Fn)returnsaFunction GeneralSearch(problem, QueuingFn) returnsa solution, or failurenodes Å make-queue(make-node(initial-state[problem]))loop doif nodes is empty then return failurenode Å Remove-Front(nodes)38if Goal-Test[problem] applied
View Full Document
Unlocking...