Introduction to Artificial Intelligence PDF

Introduction to Artificial Intelligence Chapter 2 Intelligent Agents Introduction to AI Intelligent Agents What is an agent?  An agent is anything that perceives its environment through sensors and acts upon that environme...

Introduction to Artificial Intelligence Chapter 2 Intelligent Agents Introduction to AI Intelligent Agents What is an agent?  An agent is anything that perceives its environment through sensors and acts upon that environment through actuators.  Example:  Human is an agent  A robot is also an agent with cameras and motors  A thermostat detecting room temperature.  The environment could be everything—the entire universe!  In practice, it is just that part of the universe whose state we care about when designing this agent—the part that affects what the agent perceives and that is affected by the agent’s actions.  Diagram of an agent What AI should fill  Simple Terms Percept  Agent’s perceptual inputs at any given moment  The content an agent’s sensors are perceiving Percept sequence  Complete history of everything that the agent has ever perceived. “an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived.” Agent function & program Agent’s behavior is mathematically described by  Agent function  A function mapping any given percept sequence to an action Practically it is described by  An agent program  The real implementation running within some physical system Example: Vacuum-cleaner world Perception:Where it is in? Clean or Dirty? Actions: Move left, Move right, suck up dirt, do nothing Vacuum-cleaner world  One very simple agent function is the following: if the current square is dirty, then suck; otherwise, move to the other square.  A partial tabulation of this agent function is shown below The program implements the agent function tabulated in Fig. 2.3 Function Reflex-Vacuum-Agent([location,status]) return an action If status = Dirty then return Suck else if location = A then return Right else if location = B then return left We see that various vacuum-world agents can be defined simply by filling in the right-hand column (Action) in various ways. The obvious question, then, is this: What is the right way to fill out the table? In other words, What makes an agent good or bad, intelligent or stupid? Good Behavior: The Concept of Rationality Rational agent  One that does the right thing  = every entry in the table for the agent function is correct (rational). What is correct?  The actions that cause the agent to be most successful  So, we need ways to measure success.  Performance measure  AI has generally stuck to a notion called consequentialism: we evaluate an agent’s behavior by its consequences.  When an agent is plunked down in an environment, it generates a sequence of actions according to the percepts it receives.  This sequence of actions causes the environment to go through a sequence of states.  If the sequence is desirable, then the agent has performed well. This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states. Performance measure Performance measure  An objective function that determines:  How the agent does successfully  E.g., 90% or 30%? An agent, based on its percepts   action sequence: if desirable, it is said to be performing well.  No universal performance measure for all agents Humans have desires and preferences of their own, but Machines do not have desires and preferences of their own. Performance measure A general rule:  Design performance measures according to  What one actually wants in the environment  Rather than how one thinks the agent should behave E.g., in vacuum-cleaner world  We want the floor clean, no matter how the agent behaves  We don’t restrict how the agent behaves “the purpose put into the machine is the purpose which we really desire” Norbert Wiener  We may need to build agents that reflect initial uncertainty about the true performance measure and learn more about it as time goes by Rationality What is rational at any given time depends on four things:  The performance measure defining the criterion of success  The agent’s prior knowledge of the environment  The actions that the agent can perform  The agents’s percept sequence up to now Rational agent For each possible percept sequence,  a rational agent should: “select an action expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has” E.g., an exam  Maximize marks, based on the questions on the paper and your knowledge Example of a rational agent The performance measure awards one point for each clean square at each time step, over a “lifetime” of 1000 time steps. The “geography” of the environment is known a priori but the dirt distribution and the initial location of the agent are not. Clean squares stay clean and sucking cleans the current square. The Right and Left actions move the agent one square except when this would take the agent outside the environment, in which case the agent remains where it is. The only available actions are Right, Left, and Suck. The agent correctly perceives its location and whether that location contains dirt. Under this case, the agent is rational. Omniscience An omniscient agent  Knows the actual outcome of its actions in advance  No other possible outcomes  However, impossible in reality  An example: crossing a street but died of the fallen cargo door from 33,000ft  irrational? Based on the case, it is rational. As rationality maximizes expected performance Perfection maximizes actual performance Hence rational agents are not omniscient. Learning Does a rational agent depend on only current percept?  No, the past percept sequence should also be used  This is called learning  After experiencing an episode, the agent  should adjust its behaviors to perform better for the same job next time.  Autonomy If an agent just depends on the previous knowledge of its designer rather than its own percepts then the agent lacks autonomy A rational agent should be autonomous- it should learn what it can to compensate for partial or incorrect prior knowledge. E.g., a clock  No input (percepts)  Run only but its own algorithm (previous knowledge)  No learning, no experience, etc. E.g., a vacuum-cleaning agent that learns to predict where and when additional dirt will appear will do better than one that does not. It would be reasonable to provide an AI agent with some initial knowledge as well as an ability to learn. After sufficient experience of its environment, the behavior of a rational agent can become effectively independent of its previous knowledge. The Nature of Environments Sometimes, the environment may not be the real world  E.g., flight simulator, video games, Internet  They are all artificial but very complex environments  Those agents working in these environments are called Software agents (softbots)  Because all parts of the agent are software  Examples: softbots that trade on auction and reselling, and Web sites deal with millions of other users and billions of objects, many with real images. Task environments Task environments are the problems  While the rational agents are the solutions Specifying the task environment  PEAS description as fully as possible  Performance  Environment  Actuators  Sensors In designing an agent, the first step must always be to specify the task environment as fully as possible. Automated taxi driver as an example Task environments Performance measure  How can we judge the automated driver?  Which factors are considered?  getting to the correct destination  minimizing fuel consumption  minimizing the trip time and/or cost  minimizing the violations of traffic laws  maximizing the safety and comfort, etc. Task environments Environment  A taxi must deal with a variety of roads  Traffic lights, other vehicles, pedestrians, stray animals, road works, police cars, etc.  Interact with the customer Task environments Actuators (for outputs)  Control over the accelerator, steering, gear shifting and braking  A display to communicate with the customers Sensors (for inputs)  Detect other vehicles, road situations  GPS (Global Positioning System) to know where the taxi is  Many more devices are necessary Task environments PEAS description of the task environment for an automated taxi driver. Properties of task environments Fully observable vs. Partially observable  Fully observable  If an agent’s sensors give it access to the complete state of the environment at each point in time then the environment is effectively and fully observable  if the sensors detect all aspects  That is relevant to the choice of action  Partially observable  An environment might be Partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data.  Example:A local dirt sensor of the cleaner cannot tell whether other squares are clean or not Properties of task environments Deterministic vs. stochastic  next state of the environment is completely determined by the current state and the actions executed by the agent, then the environment is deterministic, otherwise, it is Stochastic.  Strategic environment: deterministic except for actions of other agents -Cleaner and taxi driver are:  Stochastic because of some unobservable aspects  noise or unknown  If the agent has no sensors at all then the environment is unobservable.  The agent’s goals may still be achievable Properties of task environments Episodic vs. sequential  An episode = agent’s single pair of perception & action  The quality of the agent’s action does not depend on other episodes  Every episode is independent of each other  Episodic environment is simpler  The agent does not need to think ahead Sequential  Current action may affect all future decisions -Ex.Taxi driving and chess. Properties of task environments Static vs. dynamic  A dynamic environment is always changing over time  E.g., the number of people in the street  In a static environment, the agent need not keep looking at the world while it is deciding on an action  E.g., Crossword puzzles Semidynamic  The environment is not changed over time but the agent’s performance score does Properties of task environments Discrete vs. continuous  If there are a limited number of distinct states, clearly defined percepts and actions, the environment is discrete  Discrete: Chess game  Continuous:Taxi driving Properties of task environments Single agent VS. multiagent  Playing a crossword puzzle – single agent  Chess playing – two agents  Competitive multiagent environment  Chess playing  Cooperative multiagent environment  Automated taxi driver  Avoiding collision Properties of task environments Known vs. unknown  In a known environment, the outcomes for all actions are given. (example: partially observable solitaire card games).  If the environment is unknown, the agent will have to learn how it works in order to make good decisions. (example: fully observable new video game). Examples of task environments The Structure of agents Agent = architecture + program  Architecture = some sort of computing device (sensors + Motors (actuators))  (Agent) Program = some function that implements the agent mapping = “?”  Agent Program = Job of AI Agent programs Input for Agent Program  Only the current percept Input for Agent Function  The entire percept sequence  The agent must remember all of them Implement the agent program as  A look up table (agent function) Agent programs Skeleton design of an agent program Agent Programs P = the set of possible percepts T= lifetime of the agent  The total number of percepts it receives Size of the look-up table Consider playing chess  T t  P =10,T=150 P t 1  Will require a table of at least 10 entries 150 Agent programs Despite of huge size, look up table does what we want. The key challenge of AI  Find out how to write programs that, to the extent possible, produce rational behavior  From a small amount of code  Rather than a large amount of table entries  E.g., a five-line program of Newton’s Method  V.s. huge tables of square roots, sine, cosine, … Types of agent programs Four types  Simple reflex agents  Model-based reflex agents  Goal-based agents  Utility-based agents Simple reflex agents It uses just condition-action rules  The rules are like the form “if … then …”  efficient but have a narrow range of applicability  Because knowledge sometimes cannot be stated explicitly  Work only if the environment is fully observable  Simple reflex agents Schematic diagram of a simple reflex agent. We use rectangles to denote the current internal state of the agent’s decision process, and ovals to represent the background information used in the process.  Simple reflex agents A simple reflex agent. It acts according to a rule whose condition matches the current state, as defined by the percept. The agent program for a simple reflex agent in the two-location vacuum environment. Model-based Reflex Agents For the world that is partially observable  the agent has to keep track of an internal state  That depends on the percept history  Reflecting some of the unobserved aspects  E.g., driving a car and changing lane Requiring two types of knowledge  How the world evolves independently of the agent  How the agent’s actions affect the world Model-based Reflex Agents Model-based Reflex Agents The agent is with memory Example: Table Agent with Internal State IF THEN Saw an object ahead, Go straight and turned right, and it’s now clear ahead Saw an object ahead, Halt turned right, and object ahead again See no objects ahead Go straight See an object ahead Turn randomly Goal-based agents Current state of the environment is always not enough The goal is another issue to achieve  Judgment of rationality / correctness Actions chosen  goals, based on  the current state  the current percept Goal-based agents Goal-based agents Conclusion  Goal-based agents are less efficient  but more flexible  Agent  Different goals  different tasks  Search and planning  two other sub-fields in AI  to find out the action sequences to achieve its goal Utility-based agents Goals alone are not enough  to generate high-quality behavior  e.g., meals in Canteen, good or not? Many action sequences  the goals  some are better and some worse  If the goal means success,  then utility means the degree of success (how successful it is) Utility-based agents Utility-based agents it is said state A has a higher utility  If state A is more preferred than others Utility is therefore a function  that maps a state onto a real number  the degree of success Utility-based agents Utility has several advantages:  When there are conflicting goals,  Only some of the goals but not all can be achieved  utility describes the appropriate trade-off  When there are several goals  None of them are achieved certainly  utility provides a way for the decision-making Learning Agents After an agent is programmed, can it work immediately?  No, it still need teaching In AI,  Once an agent is done  We teach it by giving it a set of examples  Test it by using another set of examples We then say the agent learns  A learning agent Learning Agents Learning Agents Four conceptual components  Learning element  Making improvement  Performance element  Selecting external actions  Critic  Tells the Learning element how well the agent is doing with respect to fixed performance standards. (Feedback from user or examples, good or not?)  Problem generator  Suggest actions that will lead to new and informative experiences. How the components of agent programs work