Intelligent AgentsChapter 2Chapter 2 1Outline♦ PAGE (Percepts, Actions, Goals, Environment)♦ Environment types♦ Agent functions and programs♦ Agent types♦ Vacuum world♦ we want to design rational agents - how to define successChapter 2 2PAGEMust first specify the setting for intelligent agent designConsider, e.g., the task of designing an automated taxi:Percepts??Actions??Goals??Environment??Chapter 2 3PAGEMust first specify the setting for intelligent agent designConsider, e.g., the task of designing an automated taxi:Percepts?? video, accelerometers, gauges, engine sensors, keyboard, GPS,...Actions?? steer, accelerate, brake, horn, speak/display, ...Goals?? safety, reach destination, maximize profits, obey laws, passengercomfort, ...Environment?? US urban streets, freeways, traffic, pedestrians, weather,customers, ...♦ Internet Shopping Agents - percepts, actions, goals, environmentChapter 2 4Rational agentsWithout loss of generality, “goals” specifiable by performance measuredefining a numerical value for any environment history (modulo what canthe agent perceive)Rational action: whichever action maximizes the expected value of the per-formance measure given the percept sequence to dateRational 6= omniscientRational 6= clairvoyantRational 6= successful♦ accesible vs . unaccesible ♦ deterministic vs. undeterministic ♦ episodicvs. noepisodic ♦ static vs. dynamic ♦ discrete vs. continuousChapter 2 5Environment typesSolitaire Backgammon Internet shopping TaxiAccessible??Deterministic??Episodic??Static??Discrete??Chapter 2 6Environment typesSolitaire Backgammon Internet shopping TaxiAccessible?? Yes Yes No NoDeterministic?? Yes No Partly NoEpisodic?? No No No NoStatic?? Yes Semi Semi NoDiscrete?? Yes Yes Yes NoThe environment type largely determines the agent designThe real world is (of course) inaccessible, stochastic, sequential, dynamic,continuousChapter 2 7Agent functions and programsAn agent is completely specified by the agent functionmapping percept sequences to actions(In principle, one can supply each possible sequence to see what it does.Obviously, a lookup table would usually be immense.)Aim: find a way to implement the rational agent function conciselyAn agent programtakes a single percept as input, keeps internal state:function Skeleton-Agent( percept) returns actionstatic: memory, the agent’s memory of the worldmemory ← Update-Memory(memory, percept)action ← Choose-Best-Action(memory)memory ← Update-Memory(memory, action)return actionChapter 2 8Agent typesFour basic types in order of increasing generality:– simple reflex agents– reflex agents with state– goal-based agents– utility-based agentsChapter 2 9Simple reflex agentsAgentEnvironmentSensorsEffectorsWhat the worldis like nowWhat action Ishould do nowCondition−action rules♦ lookup table out of question get-input, rule-match, rule-actionChapter 2 10Reflex agents with stateAgentEnvironmentSensorsEffectorsWhat the worldis like nowWhat action Ishould do nowStateHow the world evolvesWhat my actions doCondition−action rulesget-input, update-state, rule-match, rule-action, update-stateChapter 2 11Goal-based agentsAgentEnvironmentSensorsEffectorsWhat it will be like if I do action AWhat the worldis like nowWhat action Ishould do nowStateHow the world evolvesWhat my actions doGoalsneeds a goal, involves some search, planning aheadChapter 2 12Utility-based agentsAgentEnvironmentSensorsEffectorsWhat it will be like if I do action AWhat the worldis like nowHow happy I will be in such a stateWhat action Ishould do nowStateHow the world evolvesWhat my actions doUtilityexplicit utility - measure how happy agent is to be in a stateChapter 2 13The vacuum worldPercepts (<bump> <dirt> <home>)Actions shutoff forward suck (turn left) (turn right)Goals(performance measure on environment history)– +100 for each piece of dirt cleaned up– -1 for each action– -1000 for shutting off away from homeEnvironment– grid, walls/obstacles, dirt distribution and creation, agent body– movement actions work unless bump into wall– suck actions put dirt into agent body (or not)Accessible? Deterministic? Episodic? Static? Discrete?Chapter 3, Sections 1–5 14Problem solving and searchChapter 3, Sections 1–5Chapter 3, Sections 1–5 15Outline♦ Problem-solving agents (problem, goal and means of achieving it)♦ Problem types♦ Problem formulation♦ Example problems♦ autonomous agents, games, proving theorems, path finding problems♦ Basic search algorithms (search for solution - what space ? )Notion of the problem space - set of states - set of operators - how to getfrom the initial state to the final stateChapter 3, Sections 1–5 16Problem-solving agentsRestricted form of general agent:function Simple-Problem-Solving-Agent( p) returns an actioninputs: p, a perceptstatic: s, an action sequence, initially emptystate, some description of the current world stateg, a goal, initially nullproblem, a problem formulationstate ← Update-State(state, p)if s is empty theng ← Formulate-Goal(state)problem ← Formulate-Problem(state, g)s ← Search( problem)action ← Recommendation(s, state)s ← Remainder(s, state)return actionNote: this is offline problem solving.Online problem solving involves acting without complete knowledge of theproblem and solution.Chapter 3, Sections 1–5 17Example: The 8-puzzleStart StateGoal State245678123467812345678123456785states??operators??goal test??path cost??Chapter 3, Sections 1–5 18Example: The 8-puzzleStart StateGoal State245678123467812345678123456785states??: integer locations of tiles (ignore intermediate positions)operators??: move blank left, right, up, down (ignore unjamming etc.)goal test??: = goal state (given)path cost??: 1 per move[Note: optimal solution of n-Puzzle family is NP-hard]Chapter 3, Sections 1–5 19Example: RomaniaOn holiday in Romania; currently in Arad.Flight leaves tomorrow from BucharestFormulate goal:be in BucharestFormulate problem:states: various citiesoperators: drive between citiesFind solution:sequence of cities, e.g., Arad, Sibiu, Fagaras, BucharestChapter 3, Sections 1–5 20Example: RomaniaGiurgiuUrziceniHirsovaEforieNeamtOradeaZerindAradTimisoaraLugojMehadiaDobretaCraiovaSibiuFagarasPitestiVasluiIasiRimnicu VilceaBucharestChapter 3, Sections 1–5 21Problem typesDeterministic, accessible =⇒ single-state problemDeterministic, inaccessible=⇒ multiple-state problemNondeterministic, inaccessible=⇒ contingency