Intelligent Agents: CCAI 221 - Lecture Slides PDF

Intelligent Agents CCAI 221: AI fundaments Amended by Shahd Alahdal From Inst. Ebtehal Alsaggaf 1 Outline:  Agents and Environments  Good Behavior: The Concept of Rationality  The Nature of...

Intelligent Agents CCAI 221: AI fundaments Amended by Shahd Alahdal From Inst. Ebtehal Alsaggaf 1 Outline:  Agents and Environments  Good Behavior: The Concept of Rationality  The Nature of Environments  Specifying the task environment  Properties of task environments  The structure of agents 2 Agents and environments 3  Agents and Environments An agent is anything that can be viewed as: Perceiving its environment through sensors and Acting upon that environment through actuators 4  Agents and Environments Human-agent: Eyes, ears, and other organs for sensors; hands, legs, mouth, and other body parts for actuators Robotic-agent: Cameras and infrared range finders for sensors; various motors for actuators A software-agent: Receives keystrokes, file contents, and network packets as sensory inputs. Acts on the environment by displaying on the screen, writing files, and sending network packets. 5  Agents and environment Agents perceive and act in an environment Percept: perceptual inputs at any given instant Percept sequence: complete history of percepts An agent’s choice of action at any given instant can depend on the entire percept sequence observed to date. Agent function: An agent’s behaviour is described by the agent function, which maps percept sequence to actions f: P* A Agent program: The agent function is internally implemented as an agent program, which runs on an architecture (computing device with physical sensors and actuators) o Aim of AI is to build agent programs o Agent = Architecture + Program 6  Agent: an example Vacuum-cleaner world Percepts: Location (e.g. A or B) and content (e.g. Dirty or clean) Actions: Move left, move right, suck Function: if the current square is dirty then suck, otherwise move to the other square. 7  Example 1: The vacuum cleaner world Agent Program (internal characteristic) 8 Good behavior: the concept of rationality 9  Rational Agents An agent should attempt to do the right thing, based on what it can perceive and the actions it can perform The right action is the one that will cause the agent to be most successful Performance measure: that evaluates any given sequence of environment states. An objective criterion for the success of an agent's behavior e.g., the performance measure of a vacuum-cleaner agent could be ? 10  Rational Agents An agent should attempt to do the right thing, based on what it can perceive and the actions it can perform The right action is the one that will cause the agent to be most successful Performance measure: that evaluates any given sequence of environment states. An objective criterion for the success of an agent's behavior e.g., the performance measure of a vacuum cleaner agent could be amount of dirt cleaned up amount of time taken amount of electricity consumed amount of noise generated, etc. 11  Rational Agents But what is rationality at a given time Rationality at a given time depends on The performance measure that defines the criterion of success The agent’s prior knowledge of the environment The actions that the agent can perform The agent’s percept sequence to date from sensors Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. 12  Rational Agents Rationality is distinct from perfection and omniscience Rationality aims to maximize the expected output, while perfection aims to maximize the actual output An omniscient agent knows the actual outcome of its action Agents can perform actions to modify future percepts to obtain useful information (information gathering, exploration). An agent is autonomous if its behavior is determined by its own experience. Ability to learn and adapt 13  Rational Agents The same agent can be irrational under different circumstances Once all dirt is cleaned up it will oscillate needlessly back and forth – such an agent could be penalised A better agent for this case would do nothing once it is sure that all the squares are clean If the clean squares can become dirty again, the agent should occasionally check and clean them if needed If the geography of the environment is unknown apriori, the agent will need to explore it rather than stick to squares A and B 14 The nature of environments Specifying the task environment Properties of task environments 15 Specifying the task environment (PEAS) 16  Specifying the task environment Task Environment: the “problems” to which rational agents are the “solutions.” The task environment of an agent is often specified as four things: PEAS Performance Environment Actuators Sensors In designing an agent, the first step must always be to specify the task environment as fully as possible. Let’s consider this example: an automated taxi driver Agent Type Performance Environment Actuators Sensors Measure Taxi Driver 17  Specifying the task environment What is the performance measure to which we would like our automated driver to reach? Desirable qualities include getting to the correct destination; minimizing fuel consumption and wear and tear; minimizing the trip time or cost; minimizing violations of traffic laws and disturbances to other drivers; maximizing safety and passenger comfort; maximizing profits. Obviously, some of these goals conflict, so tradeoffs will be required 18  Specifying the task environment What is the driving environment that the taxi will face? People, Traffic lights, cars, pedestrians, animals (cats, dogs, birds), road signs, … The actuators for an automated taxi include those available to a human driver: control over the engine through the accelerator and control over steering and braking. In addition, it will need output to a display screen or voice synthesizer to talk back to the passengers, and perhaps some way to communicate with other vehicles, politely or otherwise. The basic sensors for the taxi will include one or more controllable video cameras so that it can see the road; it might augment these with infrared or sonar sensors to detect distances to other cars and obstacles. To avoid speeding tickets, the taxi should have a speedometer, and to control the vehicle properly, especially on curves, it should have an accelerometer. To determine the mechanical state of the vehicle, it will need the usual array of engine, fuel, and electrical system sensors. Like many human drivers, it might want a global positioning system (GPS) so that it doesn’t get lost. Finally, it will need a keyboard or microphone for the passenger to request a destination. 19 Example : The Taxi Driver 20 PEAS for medical diagnosis system Performance measure Environment Actuators Sensors 21 PEAS for medical diagnosis system Performance measure Healthy patient, minimize costs, satisfaction Environment Patient, hospital, staff Actuators Screen display (questions, tests, diagnoses, treatments, referrals) Sensors Keyboard (entry of symptoms, findings, patient‘s answers) 22  PEAS for a part-picking robot Performance measure Environment Actuators Sensors 23  PEAS for a part-picking robot Performance measure Percentage of parts in correct bins Environment Conveyor belt with parts, bins Actuators Jointed arm and hand Sensors Camera, joint angle sensors 24  PEAS for an intelligent house Performance measure Environment Actuators Sensors 25  PEAS for an intelligent house Performance measure Optimal room temperature, light on/off when people present/absent, optimal power consumption Environment People, house, outside world (including sunlight) Actuators Jointed arm and hand to switch on/off buttons Sensors Movement sensors, temperature sensors, clock, sound sensor 26 PEAS for an interactive teacher (tutor) Performance measure Environment Actuators Sensors 27 PEAS for an interactive teacher (tutor) Performance measure Maximize students’ score on test, improve students’ knowledge Environment Set of students Actuators Screen display (exercises, suggestions, corrections) Sensors Keyboard 28 Note: you can find more examples of agents types and their PEAS in you book Figure/Table 2.5 page: 42 29 Properties of task environments 30  Properties of Task environments Task environments can be categorized according to some dimensions These dimensions, to a large extent, determine the appropriate agent design and the applicability of the techniques for agent implementation The dimensions are: 1. Fully observable vs. partially observable 2. Single-agent vs. multiagent systems 3. Deterministic vs. stochastic 4. Episodic vs. sequential 5. Static vs. dynamic 6. Discrete vs. continuous 31  1. Fully vs. Partially Observable An environment is fully observable (FO) when the sensors can detect all aspects that are relevant to the choice of action, otherwise, it is partially observable (PO) FO environments are more convenient than PO ones. An environment might be PO because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data. Examples: vacuum cleaner (FO), a vacuum cleaner with local dirt sensor (??), taxi driver (??) The vacuum agent with only a local dirt sensor cannot tell whether there is dirt in other squares An automated taxi cannot see what other drivers are thinking. If the agent has no sensors at all then the environment is unobservable. 32  1. Fully vs. Partially Observable Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English teacher Observable Fully Fully Fully 33  1. Fully vs. Partially Observable Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English teacher Observable Fully Fully Fully Partially Fully Partially 34  2. Single vs. Multi-Agent In a single-agent environment, an agent operates by itself in the environment, while in a multi-agent environment more than one agent act Examples: Crossword is a single agent while chess is two-agents Multi-agent systems: Competitive multi-agent environment (can you think of an example?) Cooperative multi-agent environment 35  2. Single vs. Multi-Agent For example, in chess, the opponent entity B is trying to maximize its performance measure, which, by the rules of chess, minimizes agent A’s performance measure. Thus, chess is a competitive multiagent environment. In the taxi-driving environment, on the other hand, avoiding collisions maximizes the performance measure of all agents, so it is a partially cooperative multiagent environment. It is also partially competitive because, for example, only one car can occupy a parking space. The agent-design problems in multi-agent environments are often quite different from those in single-agent environments; For example, communication often emerges as a rational behavior in multi- agent environments; in some competitive environments, randomized behavior is rational because it avoids the problems of predictability. 36  2. Single vs. Multi-Agent Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English teacher Agent Single Multi Multi 37  2. Single vs. Multi-Agent Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English teacher Agent Single Multi Multi Multi Single Multi 38  3. Deterministic vs. stochastic The environment is deterministic if the next state of the environment is completely determined by the current state and the action executed by the agent Stochastic otherwise, uncertainty about outcomes is quantified in terms of probabilities If the environment is partially observable, then it could appear to be stochastic An environment is said to be uncertain if it is either partially observable or stochastic. For example, in Chess, there is no randomness when you move a piece. Thus, chess playing environment is deterministic 39  3. Deterministic vs. Stochastic Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Deterministic D D D If the next state of the environment is completely determined by the current state and the action D -> Deterministic executed by the agent, then we say the environment S -> Stochastic is deterministic; otherwise, it is stochastic. 40  3. Deterministic vs. Stochastic Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Deterministic D D D S S S D -> Deterministic S -> Stochastic 41  4. Episodic vs. Sequential In an episodic environment, the agent's experience is divided into atomic episodes Each episode consists of the agent perceiving (realizing or learning) and then performing a single action The choice of action in each episode depends only on the episode itself The next episode does not depend on the actions taken in previous episodes. In a sequential environment, an agent’s current action affects the future actions 42  4. Episodic vs. Sequential Episodic: For example, an agent that must spot defective parts on an assembly line bases each decision on the current part, regardless of previous decisions. Sequential: Chess and taxi driving are sequential: in both cases, short-term actions can have long-term consequences. Episodic environments are much simpler than sequential environments because the agent does not need to think ahead. 43  4. Episodic vs. Sequential Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Episodic Seq. Seq. Seq. 44  4. Episodic vs. Sequential Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Episodic Seq. Seq. Seq. Seq. Episodic Seq. 45  5. Static vs. Dynamic A static environment is unchanged while an agent is making a decision, while a dynamic environment may change Static environments are easy to deal with The environment is semi-dynamic if the environment itself does not change with the passage of time, but the agent's performance score does (change). 46  5. Static vs. Dynamic Dynamic environments, on the other hand, are continuously asking the agent what it wants to do; if it hasn’t decided yet, that counts as deciding to do nothing. If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi-dynamic. 47  5. Static vs. Dynamic Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Static Static 48  5. Static vs. Dynamic Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Static Static Static Semi Dynamic Dynamic Dynamic Taxi driving is clearly dynamic: the other cars and the taxi itself keep moving while the driving algorithm don’t know about what to do next. Chess, when played with a clock, is semi-dynamic. Crossword puzzles are static. 49  6. Discrete vs. Continuous The discrete/ continuous distinction applies to the state of the environment to the way time is handled, and to percepts and actions. A discrete environment has a finite and clearly defined states, percepts and actions Examples Chess has finite number of discrete states, and has discrete set of percepts and actions Taxi driving has continuous states and actions 50  6. Discrete vs. Continuous Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Discrete Disc. Disc. 51  6. Discrete vs. Continuous Task Crossword Chess Chess with Taxi driving Part picking Interactive Environment puzzle a clock robot English tutor Discrete Disc. Disc. Disc. Cont. Cont. Disc. 52  Environment types: summary Note: you can find more examples of task environments and their characteristics in the book Figure/Table 2.6 page: 45 53  Environment types: summary The environment type largely determines the agent design The real world is partially observable, stochastic, sequential, dynamic, continuous, and multi-agent Building an autonomous agent in such complex environments is a hard AI task 54 The structure of agents 55  Agent implementation (recall) The job of AI is to design agent programs Agent = architecture + program Agent program implements agent function Mapping percepts to actions All agent programs can have the same skeleton: Input = current percepts Output = action Program= manipulates input to produce output 56  Agent implementation Table look-up agents function TABLE-DRIVEN_AGENT(percept) returns an action persistent: percepts, a sequence initially empty table, a table of actions, indexed by percept sequence- initially fully specified append percept to the end of percepts action ← LOOKUP(percepts, table) return action Simple to build, but practically infeasible Space to store the table Take a long time to build the table No autonomy Learning could be very time consuming 57  Agent types Rather than a table, we can produce rational behavior from a small piece of code Five basic types: Simple reflex agents Model-based reflex agents Goal-based agents Utility-based agents Learning agents 58  1. Simple reflex agent Select actions based on the current percept ignoring the rest of the percept history Example: simple reflex vacuum cleaner agent function REFLEX-VACUUM-AGENT([location, status]) returns action if status == Dirty then return Suck else if location == A then return Right else if location == B then return Left Condition-action-rule (example) if car-in-front-is-braking then initiate-braking 59  1. Simple Reflex Agents For example, if a mars lander found a rock in a specific place it needed to collect then it would collect it, if it was a simple reflex agent then if it found the same rock in a different place it would still pick it up as it doesn't take into account that it already picked it up. 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. 60  1. Simple reflex agent Simple, but they turn out to be of very limited intelligence The agent will work only if the correct decision can be made on the basis of the current percept oThe environment must be fully observable Infinite loops are often unavoidable oEscape could be possible by randomizing 61  2. Model-based Reflex Agent To handle a partially observable environment, the agent should keep track of the part of the world it can't see now The agent should maintain some sort of internal state that depends on the percept history Updating the internal state information regularly requires two kinds of knowledge to be encoded in the agent program Information about how the world evolves itself Information about how the agent's own actions affect the world  Needs to maintain a world model This time mars Lander after picking up its first sample, stores this in the internal state of the world around it so when it comes across the second same sample it passes it by and saves space for other samples. 62 2. Model-based reflex agents 63  2. Model-based Reflex Agent The details of how models and states are represented vary widely depending on the type of environment and the technology used in the agent design. Regardless of the kind of representation used, it is seldom possible for the agent to determine exactly the current state of a partially observable environment. Instead, the box labeled “what the world is like now” (previous Figure) represents the agent’s “best guess” (or sometimes best guesses). For example, an automated taxi may not be able to see around the large truck that has stopped in front of it and can only guess what may be causing the hold-up. Thus, uncertainty about the current state may be unavoidable, but the agent still must make a decision. 64  3. Goal-based Agent Knowing about the current state of the environment is not always enough to decide what to do (e.g. decision at a road junction) The agent needs some sort of goal information that describes situations that are desirable The agent program can combine this with information about the results of possible actions in order to choose actions that achieve the goal Usually requires search and planning 65 3. Goal-based Agents 66  Goal-based Vs. Reflex Agent The goal-based agent appears less efficient, but it is more flexible because the knowledge that supports its decision is represented explicitly and can be modified. The goal-based agent's behavior can easily be changed The reflex agent's rules must be changed for a new situation - rewrite many condition-action rules The goal-based agent takes the future into account 67  4. Utility-based Agent Goals alone are not really enough to generate high quality behaviour in most environments What if multiple roads lead to the destination from a junction? Which road would be better – safe, cheap, fast... If a state A is preferred over a state B, then A has a higher utility A utility function maps a state onto a real number which describes the associated degree of happiness/satisfaction Happy-unhappy (goal-based) vs how much happy (utility- based) 68  4. Utility-based agents Figure 2.14 A model-based, utility-based agent. It uses a model of the world, along with a utility function that measures its preferences among states of the world. Then it chooses the action that leads to the best expected utility, where expected utility is computed by averaging over all possible outcome states, weighted by the probability of the outcome. 69  5. Learning Agent Turing – instead of programming intelligent machines by hand, which is too much work, build learning machines and then teach them Learning allows the agent to operate in initially unknown environments and to become more competent than its initial knowledge alone might allow. A Learning agent is capable of learning from its experiences to improve its performance. 70 5. Learning Agents suggested actions 71  5. Learning Agent Learning agents mainly have 4 components Critic: It generates a feedback which describes the performance with respect to fixed performance standard Learning Element: Makes improvement by learning from environments Learning element uses feedback from the critic on How the agent is doing How the performance element should be modified to do better in the future 72  5. Learning Agent Learning agents mainly have 4 components Performance Element: It selects external actions. For example, when you were in school you would do a test and it would be marked: the test is the critic. The teacher would mark the test and see what could be improved and instructs you how to do better next time, the teacher is the learning element, and you are the performance element. Problem Generator: This suggests actions that will lead to new and informative experiences (explore vs. exploit). For example, in science with your current knowledge at that time you would not have thought of placing a courses on a summer, but the teacher suggested an experiment and you did it and this taught you more and added to knowledge base. 73  SUMMARY Agents interact with environments through actuators and sensors The agent function describes what the agent does in all circumstances The performance measure evaluates the environmental sequence A perfectly rational agent maximizes expected performance Agent programs implement (some) agent functions PEAS descriptions define task environments Environments are categorized along several dimensions: Observable? Deterministic? Episodic? Static? Discrete? Single- agent? Several basic agent architectures exist: Simple reflex agents respond directly to percepts, whereas Model-based reflex agents maintain an internal state to track aspects of the world that are not evident in the current percept. Goal-based agents act to achieve their goals, and Utility-based agents try to maximize their own expected 74  Reference Book: Artificial intelligence: a modern approach by Stuart Russel and Peter Norving, third edition (Chapter 2) 75