Sri Sai Vidya Vikas Shikshana Samithi ®

SAI VIDYA INSTITUTE OF TECHNOLOGY

Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

ARTIFICIAL INTELLIGENCE(BCS515B)
MODULE 1
Introduction: What Is AI? , The State of The Art.
Intelligent Agents: Agents and environment, Concept of Rationality, The nature of
environment, The structure of agents.
Chapter 1 - 1.1, 1.4
Chapter 2 - 2.1, 2.2, 2.3, 2.4
Text book: Stuart J. Russell and Peter Norvig, Artificial Intelligence, 3rd Edition, Pearson,
2015
Data: Raw facts, unformatted information.
Information: It is the result of processing, manipulating and organizing data in response to a
specific need. Information relates to the understanding of the problem domain.
Knowledge: It relates to the understanding of the solution domain – what to do?
Intelligence: It is the knowledge in operation towards the solution – how to do? How to apply
the solution?

ARTIFICIAL INTELLIGENCE: Artificial intelligence is the study of how make computers to

do things which people do better at the moment. It refers to the intelligence controlled by a
computer machine.
One View of AI is
• About designing systems that are as intelligent as humans
• Computers can be acquired with abilities nearly equal to human intelligence
• How system arrives at a conclusion or reasoning behind selection of actions
• How system acts and performs not so much on reasoning process.

In the Figure 1.1 The definitions on top are concerned with thought processes and reasoning,

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

whereas the ones on the bottom address behavior. The definitions on the left measure success in
terms of fidelity to human performance, whereas RATIONALITY the ones on the right measure
against an ideal performance measure, called rationality. A system is rational if it does the “right
thing,” given what it knows. Historically, all four approaches to AI have been followed, each by
different people with different methods. A human-centered approach must be in part an
empirical science, involving observations and hypotheses about human behavior. A rationalist
approach involves a combination of mathematics and engineering. The various group have both
disparaged and helped each other. Let us look at the four approaches in more detail.

1.1.1 Acting Humanly: The Turing Test Approach

The Turing Test, proposed by Alan Turing TURING TEST (1950), was designed to provide a
satisfactory operational definition of intelligence. A computer passes the test if a human
interrogator, after posing some written questions, cannot tell whether the written responses come
from a person or from a computer.

The computer would need to possess the following capabilities:

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

• natural language processing to enable it to communicate successfully in English;

• knowledge representation to store what it knows or hears;
• automated reasoning to use the stored information to answer questions and to draw
• machine learning to adapt to new circumstances and to detect and extrapolate patterns

To pass the total Turing Test, the computer will need

• computer vision to perceive objects, and
• robotics to manipulate objects and move about.

Why Artificial Intelligence?

❑ Making mistakes on real-time can be costly and dangerous.
❑ Time-constraints may limit the extent of learning in real world.
1.1.2 Thinking humanly: The cognitive modeling approach

If we are going to say that a given program thinks like a human, we must have some way of
determining how humans think. We need to get inside the actual workings of human minds.
There are three ways to do this: through introspection—trying to catch our own thoughts as
they go by; through psychological experiments—observing a person in action; and through
brain imaging—observing the brain in action. Once we have a sufficiently precise theory of
the mind, it becomes possible to express the theory as a computer program.

For example, Allen Newell and Herbert Simon, who developed GPS, the “General Problem
Solver” (Newell and Simon, 1961), were not content merely to have their program solve
problems correctly. They were more concerned with comparing the trace of its reasoning
steps to traces of human subjects COGNITIVE SCIENCE solving the same problems. The
interdisciplinary field of cognitive science brings together computer models from AI and
experimental techniques from psychology to construct precise and testable theories of the
human mind.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

1.1.3 Thinking rationally: The “laws of thought” approach

The Greek philosopher Aristotle was one of the first to attempt to codify “right thinking,”
that is, irrefutable reasoning processes. His SYLLOGISM syllogisms provided patterns for
argument structures that always yielded correct conclusions when given correct premises—
for example, “Socrates is a man; all men are mortal; therefore, Socrates is mortal.” These
laws of thought were LOGIC supposed to govern the operation of the mind; their study
initiated the field called logic.

1.1.4 Acting rationally: The rational agent approach

An agent is just something that acts (agent comes from the Latin agere, to do). Of course, all

computer programs do something, but computer agents are expected to do more: operate

autonomously, perceive their environment, persist over a prolonged time period, adapt to

change, and create and pursue goals. A rational agent is one that acts so as to achieve the best

outcome or, when there is uncertainty, the best expected [Link] the “laws of thought”

approach to AI, the emphasis was on correct inferences. Making correct inferences is

sometimes part of being a rational agent, because one way to act rationally is to reason

logically to the conclusion that a given action will achieve one’s goals and then to act on that

conclusion. On the other hand, correct inference is not all of rationality; in some situations,

there is no provably correct thing to do, but something must still be done. There are also

ways of acting rationally that cannot be said to involve inference. For example, recoiling

from a hot stove is a reflex action that is usually more successful than a slower action taken

after careful deliberation.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

1.4 The State of Art

Robotic vehicles: A driverless robotic car named STANLEY sped through the rough terrain of

the Mojave dessert at 22 mph, finishing the 132-mile course first to win the 2005 DARPA Grand

Challenge. STANLEY is a Volkswagen Touareg outfitted with cameras, radar, and lase

rangefinders to sense the environment and onboard software to command the steering, braking,

and acceleration (Thrun, 2006). The following year CMU’s BOSS won the Urban Challenge,

safely driving in traffic through the streets of a closed Air Force base, obeying traffic rules and

avoiding pedestrians and other vehicles.

Speech recognition: A traveler calling United Airlines to book a flight can have the entire

conversation guided by an automated speech recognition and dialog management system.

Autonomous planning and scheduling: A hundred million miles from Earth, NASA’s Remote

Agent program became the first on-board autonomous planning program to control the scheduling

of operations for a spacecraft (Jonsson et al., 2000). REMOTE AGENT generated plans from high-

level goals specified from the ground and monitored the execution of those plans—detecting,

diagnosing, and recovering from problems as they occurred. Successor program MAPGEN (Al-

Chang et al., 2004) plans the daily operations for NASA’s Mars Exploration Rovers, and

MEXAR2 (Cesta et al., 2007) did mission planning—both logistics and science planning—for the

European Space Agency’s Mars Express mission in 2008.

Game playing: IBM’s DEEP BLUE became the first computer program to defeat the world

champion in a chess match when it bested Garry Kasparov by a score of 3.5 to 2.5 in an exhibition

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

match (Goodman and Keene, 1997). Kasparov said that he felt a “new kind of intelligence” across

the board from him. Newsweek magazine described the match as “The brain’s last stand.” The

value of IBM’s stock increased by $18 billion. Human champions studied Kasparov’s loss and

were able to draw a few matches in subsequent years, but the most recent human-computer

matches have been won convincingly by the computer.

Spam fighting: Each day, learning algorithms classify over a billion messages as spam, saving the

recipient from having to waste time deleting what, for many users, could comprise 80% or 90% of

all messages, if not classified away by algorithms. Because the spammers are continually updating

their tactics, it is difficult for a static programmed approach to keep up, and learning algorithms

work best (Sahami et al., 1998; Goodman and Heckerman, 2004).

Logistics planning: During the Persian Gulf crisis of 1991, U.S. forces deployed a Dynamic

Analysis and Replanning Tool, DART (Cross and Walker, 1994), to do automated logistics

planning and scheduling for transportation. This involved up to 50,000 vehicles, cargo, and people

at a time, and had to account for starting points, destinations, routes, and conflict resolution among

all parameters. The AI planning techniques generated in hours a plan that would have taken weeks

with older methods. The Defense Advanced Research Project Agency (DARPA) stated that this

single application more than paid back DARPA’s 30-year investment in AI.

Robotics: The iRobot Corporation has sold over two million Roomba robotic vacuum cleaners for

home use. The company also deploys the more rugged PackBot to Iraq and Afghanistan, where it

is used to handle hazardous materials, clear explosives, and identify the location of snipers.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Machine Translation: A computer program automatically translates from Arabic to English,

allowing an English speaker to see the headline “Ardogan Confirms That Turkey Would Not

Accept Any Pressure, Urging Them to Recognize Cyprus.” The program uses a statistical model

built from examples of Arabic-to-English translations and from examples of English text totaling

two trillion words (Brants et al., 2007). None of the computer scientists on the team speak Arabic,

but they do understand statistics and machine learning algorithms.

Chapter 2 - 2.1, 2.2, 2.3, 2.4

INTELLIGENT AGENTS

AGENTS & ENVIRONMENTS

An agent is anything that can be viewed as perceiving its environment through sensors and acting
upon that environment through actuators. This simple idea is illustrated in Figure 2.1. A human
agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract, and so on for
actuators. A robotic agent might have cameras and infrared range finders for sensors and various
motors for actuators. A software agent receives keystrokes, file contents, and network packets as
sensory inputs and acts on the environment by displaying on the screen, writing files, and sending
network packets. We use the term percept to refer to the agent’s perceptual inputs at any given
instant. An agent’s percept sequence is the complete history of everything the agent has ever
perceived. In general, an agent’s choice of action at any given instant can depend on the entire
percept sequence observed to date, but not on anything it hasn’t perceived. By specifying the
agent’s choice of action for every possible percept sequence, we have said more or less everything
there is to say about the agent. Mathematically speaking, we say that an agent’s behavior is
described by the agent function that maps any given percept sequence to an action.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

We can imagine tabulating the agent function that describes any given agent; for most agents, this
would be a very large table—infinite, in fact, unless we place a bound on the length of percept
sequences we want to consider. Given an agent to experiment with, we can, in principle, construct
this table by trying out all possible percept sequences and recording which actions the agent does
in [Link] table is, of course, an external characterization of the agent. Internally, the agent
function for an artificial agent will be implemented by an agent program. It is important to keep
these two ideas distinct. The agent function is an abstract mathematical description; the agent
program is a concrete implementation, running within some physical system.

2.2 GOOD BEHAVIOR: THE CONCEPT OF RATIONALITY

A rational agent is one that does the right thing—conceptually speaking, every entry in the table
for the agent function is filled out correctly. Obviously, doing the right thing is better than doing
the wrong thing, but what does it mean to do the right thing?
We answer this age-old question in an age-old way: by considering the consequences of the agent’s

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

behavior. 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.

2.2.1 Rationality
What is rational at any given time depends on four things:
• 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.

This leads to a definition of a 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.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Consider the simple vacuum-cleaner agent that cleans a square if it is dirty and moves to the other
square if not; this is the agent function tabulated in Figure 2.3. Is this a rational agent? That
depends! First, we need to say what the performance measure is, what is known about the

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

environment, and what sensors and actuators the agent has. Let us assume the following:
• 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 (Figure 2.2) but the dirt distribution and
the initial location of the agent are not. Clean squares stay clean and sucking cleans the current
square. The Left and Right actions move the agent left and right except when this would take the
agent outside the environment, in which case the agent remains where it is.
• The only available actions are Left , Right, and Suck.
• The agent correctly perceives its location and whether that location contains dirt.
We claim that under these circumstances the agent is indeed rational; its expected performance is
at least as high as any other agent’s.

2.2.2 Omniscience, learning, and autonomy

We need to be careful to distinguish between rationality and omniscience. An omniscient agent
knows the actual outcome of its actions and can act accordingly; but omniscience is impossible
in reality. Consider the following example: I am walking along the Champs Elys´ees one day and
I see an old friend across the street. There is no traffic nearby and I’m not otherwise engaged, so,
being rational, I start to cross the street. Meanwhile, at 33,000 feet, a cargo door falls off a
passing airliner, and before I make it to the other side of the street I am flattened. Was I irrational
to cross the street? It is unlikely that my obituary would read “Idiot attempts to cross street.”
This example shows that rationality is not the same as perfection. Rationality maximizes
expected performance, while perfection maximizes actual performance. Retreating from a
requirement of perfection is not just a question of being fair to agents. The point is that if we
expect an agent to do what turns out to be the best action after the fact, it will be impossible to
design an agent to fulfill this specification—unless we improve the performance of crystal balls
or time machines.
To the extent that an agent relies on the prior knowledge of its designer rather than on its own

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

percepts, we say that the agent lacks autonomy. A rational agent should be autonomous—it
should learn what it can to compensate for partial or incorrect prior knowledge. For example, a
vacuum-cleaning agent that learns to foresee where and when additional dirt will appear will do
better than one that does not. As a practical matter, one seldom requires complete autonomy
from the start: when the agent has had little or no experience, it would have to act randomly
unless the designer gave some assistance. So, just as evolution provides animals with enough
built-in reflexes to survive long enough to learn for themselves, it would be reasonable to
provide an artificial intelligent 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 prior knowledge. Hence, the incorporation of learning allows one
to design a single rational agent that will succeed in a vast variety of environments.

2.3 THE NATURE OF ENVIRONMENTS

Now that we have a definition of rationality, we are almost ready to think about building rational
agents. First, however, we must think about task environments, which are essentially the
“problems” to which rational agents are the “solutions.” We begin by showing how to specify a
task environment, illustrating the process with a number of examples. We then show that task
environments come in a variety of flavors. The flavor of the task environment directly affects the
appropriate design for the agent program.

2.3.1 Specifying the task environment

In our discussion of the rationality of the simple vacuum-cleaner agent, we had to specify the
performance measure, the environment, and the agent’s actuators and sensors. We group all
these under the heading of the task environment. For the acronymically minded, we call PEAS
this the PEAS (Performance, Environment, Actuators, Sensors) description. In designing an
agent, the first step must always be to specify the task environment as fully as possible. The
vacuum world was a simple example; let us consider a more complex problem: an automated

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

taxi driver. We should point out, before the reader becomes alarmed, that a fully automated taxi
is currently somewhat beyond the capabilities of existing technology. The full driving task is
extremely open-ended. There is no limit to the novel combinations of circumstances that can
arise—another reason we chose it as a focus for discussion. Figure 2.4 summarizes the PEAS
description for the taxi’s task environment. We discuss each element in more detail in the
following paragraphs.

2.3.2 Properties of task environments

We can, however, identify a fairly small number of dimensions along which task environments can
be categorized. These dimensions determine, to a large extent, the appropriate agent design and the
applicability of each of the principal families of techniques for agent implementation.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Fully observable vs. partially observable: If an agent’s sensors give it access to the complete
state of the environment at each point in time, then we say that the task environment is fully
observable. A task environment is effectively fully observable if the sensors detect all aspects that
are relevant to the choice of action; relevance, in turn, depends on the performance measure. Fully
observable environments are convenient because the agent need not maintain any internal state to
keep track of the world. 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—for
example, a vacuum agent with only a local dirt sensor cannot tell whether there is dirt in other

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

squares, and an automated taxi cannot see what other drivers are thinking. If the agent has no
sensors at all then the environment is unobservable.

Single agent vs. multiagent: The distinction between single-agent and multiagent environments
may seem simple enough. For example, an agent solving a crossword puzzle by itself is clearly in a
single-agent environment, whereas an agent playing chess is in a two agent environment. There
are, however, some subtle issues. First, we have described how an entity may be viewed as an
agent, but we have not explained which entities must be viewed as agents. Does an agent A (the
taxi driver for example) have to treat an object B (another vehicle) as an agent, or can it be treated
merely as an object behaving according to the laws of physics, analogous to waves at the beach or
leaves blowing in the wind? The key distinction is whether B’s behavior is best described as
maximizing a performance measure whose value depends on agent A’s behavior. 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 multiagent environments are often quite different from those in single-
agent environments; for example, communication often emerges as a rational behavior in
multiagent environments; in some competitive environments, randomized behavior is rational
because it avoids the pitfalls of predictability.
Deterministic vs. stochastic: If the next state of the environment is completely deter- mined by
the current state and the action executed by the agent, then we say the environment is
deterministic; otherwise, it is stochastic. In principle, an agent need not worry about uncertainty in
a fully observable, deterministic environment. (In our definition, we ignore uncertainty that arises
purely from the actions of other agents in a multiagent environment; thus, a game can be
deterministic even though each agent may be unable to predict the actions of the others.) If the

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

environment is partially observable, however, then it could appear to be stochastic. Most real
situations are so complex that it is impossible to keep track of all the unobserved aspects; for
practical purposes, they must be treated as stochastic. Taxi driving is clearly stochastic in this
sense, because one can never predict the behavior of traffic exactly; moreover, one’s tires blow out
and one’s engine seizes up without warning. The vacuum world as we described it is deterministic,
but variations can include stochastic elements such as randomly appearing dirt and an unreliable
suction mechanism. We say an environment is uncertain if it is not fully observable or not
deterministic. One final note:
Our use of the word “stochastic” generally implies that uncertainty about outcomes is quantified in
terms of probabilities; a nondeterministic environment is one in which actions are characterized by
their possible outcomes, but no probabilities are attached to them. Nondeterministic environment
descriptions are usually associated with performance measures that require the agent to succeed for
all possible outcomes of its actions.

Episodic vs. sequential: In an episodic task environment, the agent’s experience is divided into
atomic episodes. In each episode the agent receives a percept and then performs a single action.
Crucially, the next episode does not depend on the actions taken in previous episodes. Many
classification tasks are episodic. For example, an agent that has to spot defective parts on an
assembly line bases each decision on the current part, regardless of previous decisions; moreover,
the current decision doesn’t affect whether the next part is defective. In sequential environments,
on the other hand, the current decision could affect all future decisions. 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.
Static vs. dynamic: If the environment can change while an agent is deliberating, then we say the
environment is dynamic for that agent; otherwise, it is static. Static environments are easy to deal
with because the agent need not keep looking at the world while it is deciding on an action, nor

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

need it worry about the passage of time. 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 semidynamic. Taxi driving is clearly
dynamic: the other cars and the taxi itself keep moving while the driving algorithm dithers about
what to do next. Chess, when played with a clock, is semidynamic. Crossword puzzles are static.
Discrete vs. continuous: The discrete/continuous distinction applies to the state of the
environment, to the way time is handled, and to the percepts and actions of the agent. For example,
the chess environment has a finite number of distinct states (excluding the clock). Chess also has a
discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time
problem: the speed and location of the taxi and of the other vehicles sweep through a range of
continuous values and do so smoothly over time. Taxi-driving actions are also continuous (steering
angles, etc.). Input from digital cameras is discrete, strictly speaking, but is typically treated as
representing continuously varying intensities and locations.
Known vs. unknown: Strictly speaking, this distinction refers not to the environment itself but to
the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment. In a
known environment, the outcomes (or outcome probabilities if the environment is stochastic) for
all actions are given. Obviously, if the environment is unknown, the agent will have to learn how it
works in order to make good decisions. Note that the distinction between known and unknown
environments is not the same as the one between fully and partially observable environments. It is
quite possible for a known environment to be partially observable—for example, in solitaire card
games, I know the rules but am still unable to see the cards that have not yet been turned over.
Conversely, an unknown environment can be fully observable—in a new video game, the screen
may show the entire game state but I still don’t know what the buttons do until I try them.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

2.4 THE STRUCTURE OF AGENTS

The job of AI is to design an agent program that implements the agent function— the mapping
from percepts to actions. We assume this program will run on some sort of computing device with
physical sensors and actuators—we call this the architecture:
agent = architecture + program .
Obviously, the program we choose has to be one that is appropriate for the architecture. If the
program is going to recommend actions like Walk, the architecture had better have legs. The
architecture might be just an ordinary PC, or it might be a robotic car with several onboard
computers, cameras, and other sensors. In general, the architecture makes the percepts from the
sensors available to the program, runs the program, and feeds the program’s action choices to the
actuators as they are generated.
2.4.1 Agent programs

For example, Figure 2.7 shows a rather trivial agent program that keeps track of the percept

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

sequence and then uses it to index into a table of actions to decide what to do.
The table—an example of which is given for the vacuum world in Figure 2.3—represents
explicitly the agent function that the agent program embodies.

The four basic kinds of agent programs that embody the principles underlying almost all intelligent
systems:
• Simple reflex agents
• Model-based reflex agents
• Goal-based agents and
• Utility-based agents.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

2.4.2 Simple reflex agents

The simplest kind of agent is the simple reflex agent. These agents select actions on the basis of the
current percept, ignoring the rest of the percept history. For example, the vacuum agent whose
agent function is tabulated in Figure 2.3 is a simple reflex agent, because its decision is based only
on the current location and on whether that location contains dirt. An agent program for this agent
is shown in Figure 2.8. Notice that the vacuum agent program is very small indeed compared to the
corresponding table. The most obvious reduction comes from ignoring the percept history, which
cuts down the number of possibilities from 4T to just 4. A further, small reduction comes from the
fact that when the current square is dirty, the action does not depend on the location. Simple reflex
behaviors occur even in more complex environments. Imagine yourself as the driver of the
automated taxi. If the car in front brakes and its brake lights come on, then you should notice this
and initiate braking. In other words, some processing is done on the visual input to establish the
condition we call “The car in front is braking.” Then, this triggers some established connection in
the agent program to the action “initiate braking.” We call such a connection a condition–action
rule,5 written as if car-in-front-is-braking then initiate-braking.

Humans also have many such connections, some of which are learned responses (as for driving)
and some of which are innate reflexes (such as blinking when something approaches the eye). In
the course of the book, we show several different ways in which such connections can be learned
and implemented.
The program in Figure 2.8 is specific to one particular vacuum environment. A more general and
flexible approach is first to build a general-purpose interpreter for condition– action rules and then
to create rule sets for specific task environments. Figure 2.9 gives the structure of this general
program in schematic form, showing how the condition–action rules allow the agent to make the

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

connection from percept to action.

The agent program, which is also very simple, is shown in Figure 2.10. The INTERPRET-INPUT
function generates an abstracted description of the current state from the percept, and the RULE-
MATCH function returns the first rule in the set of rules that matches the given state description.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Note that the description in terms of “rules” and “matching” is purely conceptual; actual
implementations can be as simple as a collection of logic gates implementing a Boolean circuit.
Simple reflex agents have the admirable property of being simple, but they turn out to be of limited
intelligence. The agent in Figure 2.10 will work only if the correct decision can be made on the
basis of only the current percept—that is, only if the environment is fully observable. Even a little
bit of unobservability can cause serious trouble. For example, the braking rule given earlier
assumes that the condition car-in-front-is-braking can be determined from the current percept—a
single frame of video. This works if the car in front has a centrally mounted brake light.
Unfortunately, older models have different configurations of taillights, brake lights, and turn-signal
lights, and it is not always possible to tell from a single image whether the car is braking. A simple
reflex agent driving behind such a car would either brake continuously and unnecessarily, or,
worse, never brake at all. We can see a similar problem arising in the vacuum world. Suppose that
a simple reflex vacuum agent is deprived of its location sensor and has only a dirt sensor. Such an
agent has just two possible percepts: [Dirty] and [Clean]. It can Suck in response to [Dirty]; what
should it do in response to [Clean]? Moving Left fails (forever) if it happens to start in square A,
and moving Right fails (forever) if it happens to start in square B. Infinite loops are often
unavoidable for simple reflex agents operating in partially observable environments. Escape from
infinite loops is RANDOMIZATION possible if the agent can randomize its actions. For example,
if the vacuum agent perceives [Clean], it might flip a coin to choose between Left and Right . It is
easy to show that the agent will reach the other square in an average of two steps. Then, if that
square is dirty, the agent will clean it and the task will be complete. Hence, a randomized simple
reflex agent might outperform a deterministic simple reflex agent.

2.4.3 Model-based reflex agents

The most effective way to handle partial observability is for the agent to keep track of the part of
the world it can’t see now. That is, the agent should maintain some sort of internal state that
depends on the percept history and thereby reflects at least some of the unobserved aspects of the

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

current state. For the braking problem, the internal state is not too extensive— just the previous
frame from the camera, allowing the agent to detect when two red lights at the edge of the vehicle
go on or off simultaneously. For other driving tasks such as changing lanes, the agent needs to
keep track of where the other cars are if it can’t see them all at once. And for any driving to be
possible at all, the agent needs to keep track of where its keys are. Updating this internal state
information as time goes by requires two kinds of knowledge to be encoded in the agent program.
First, we need some information about how the world evolves independently of the agent—for
example, that an overtaking car generally will be closer behind than it was a moment ago. Second,
we need some information about how the agent’s own actions affect the world—for example, that
when the agent turns the steering wheel clockwise, the car turns to the right, or that after driving
for five minutes northbound on the freeway, one is usually about five miles north of where one was
five minutes ago. This knowledge about “how the world works”—whether implemented in simple
Boolean circuits or in complete scientific theories—is called a model of the world. An agent that
uses such a model is called a model-based agent.
Figure 2.11 gives the structure of the model-based reflex agent with internal state, showing how
the current percept is combined with the old internal state to generate the updated description of
the current state, based on the agent’s model of how the world works. The agent program is shown
in Figure 2.12. The interesting part is the function UPDATE-STATE, which is responsible for
creating the new internal state description. The details of how models and states are represented
vary widely depending on the type of environment and the particular technology used in the agent
design.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

2.4.4 Goal-based agents

Knowing something about the current state of the environment is not always enough to decide
what to do. For example, at a road junction, the taxi can turn left, turn right, or go straight on. The
correct decision depends on where the taxi is trying to get to. In other words, as well as a current

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

state description, the GOAL agent needs some sort of goal information that describes situations
that are desirable—for example, being at the passenger’s destination. The agent program can
combine this with the model (the same information as was used in the model based reflex agent) to
choose actions that achieve the goal. Figure 2.13 shows the goal-based agent’s structure.
Sometimes goal-based action selection is straightforward—for example, when goal satisfaction
results immediately from a single action. Sometimes it will be more tricky—for example, when the
agent has to consider long sequences of twists and turns in order to find a way to achieve the goal.
Notice that decision making of this kind is fundamentally different from the condition– action rules
described earlier, in that it involves consideration of the future—both “What will happen if I do
such-and-such?” and “Will that make me happy?” In the reflex agent designs, this information is
not explicitly represented, because the built-in rules map directly from

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

percepts to actions. The reflex agent brakes when it sees brake lights. A goal-based agent, in
principle, could reason that if the car in front has its brake lights on, it will slow down. Given the
way the world usually evolves, the only action that will achieve the goal of not hitting other cars is
to brake. Although the goal-based agent appears less efficient, it is more flexible because the
knowledge that supports its decisions is represented explicitly and can be modified. If it starts to
rain, the agent can update its knowledge of how effectively its brakes will operate; this will
automatically cause all of the relevant behaviors to be altered to suit the new conditions. For the
reflex agent, on the other hand, we would have to rewrite many condition–action rules. The goal-
based agent’s behavior can easily be changed to go to a different destination, simply by specifying
that destination as the goal. The reflex agent’s rules for when to turn and when to go straight will
work only for a single destination; they must all be replaced to go somewhere new.

2.4.5 Utility-based agents

Goals alone are not enough to generate high-quality behavior in most environments. For example,
many action sequences will get the taxi to its destination (thereby achieving the goal) but some are
quicker, safer, more reliable, or cheaper than others. Goals just provide a crude binary distinction
between “happy” and “unhappy” states. A more general performance measure should allow a
comparison of different world states according to exactly how happy they would make the agent.
Because “happy” does not sound very scientific, economists and computer scientists use the term
utility instead.
We have already seen that a performance measure assigns a score to any given sequence of
environment states, so it can easily distinguish between more and less desirable ways of getting to
the taxi’s destination. An agent’s utility function is essentially an internalization of the
performance measure. If the internal utility function and the external performance measure are in
agreement, then an agent that chooses actions to maximize its utility will be rational according to
the external performance measure.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Let us emphasize again that this is not the only way to be rational—we have already seen a rational
agent program for the vacuum world (Figure 2.8) that has no idea what its utility function is—but,
like goal-based agents, a utility-based agent has many advantages in terms of flexibility and
learning. Furthermore, in two kinds of cases, goals are inadequate but a utility-based agent can still
make rational decisions. First, when there are conflicting goals, only some of which can be
achieved (for example, speed and safety), the utility function specifies the appropriate tradeoff.
Second, when there are several goals that the agent can aim for, none of which can be achieved
with certainty, utility provides a way in which the likelihood of success can be weighed against the
importance of the goals. Partial observability and stochasticity are ubiquitous in the real world, and
so, therefore, is decision making under uncertainty. Technically speaking, a rational utility-based
agent chooses the action that maximizes the expected utility of the action outcomes—that is, the
utility the agent expects to derive, on average, given the probabilities and utilities of each outcome.
The utility-based agent structure appears in Figure 2.14

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

2.4.6 Learning agents

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

The learning agent can be divided into four conceptual components, as shown in Figure 2.15. The
most important distinction is between the learning element, which is responsible for making
improvements, and the performance element, which is responsible for selecting external actions.
The performance element is what we have previously considered to be the entire agent: it takes in
percepts and decides on actions. The learning element uses feedback from the critic on how the
agent is doing and determines how the performance element should be modified to do better in the
future.
The design of the learning element depends very much on the design of the performance element.
When trying to design an agent that learns a certain capability, the first question is not “How am I
going to get it to learn this?” but “What kind of performance element will my agent need to do this
once it has learned how?” Given an agent design, learning mechanisms can be constructed to
improve every part of the agent. The critic tells the learning element how well the agent is doing
with respect to a fixed performance standard. The critic is necessary because the percepts
themselves provide no indication of the agent’s success. For example, a chess program could
receive a percept indicating that it has checkmated its opponent, but it needs a performance

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

standard to know that this is a good thing; the percept itself does not say so. It is important that the
performance standard be fixed. Conceptually, one should think of it as being outside the agent
altogether because the agent must not modify it to fit its own behavior.

The last component of the learning agent is the problem generator. It is responsible for
suggesting actions that will lead to new and informative experiences. The point is that if the
performance element had its way, it would keep doing the actions that are best, given what it
knows. But if the agent is willing to explore a little and do some perhaps suboptimal actions in the
short run, it might discover much better actions for the long run. The problem generator’s job is to
suggest these exploratory actions. This is what scientists do when they carry out experiments.
Galileo did not think that dropping rocks from the top of a tower in Pisa was valuable in itself. He
was not trying to break the rocks or to modify the brains of unfortunate passers-by. His aim was to
modify his own brain by identifying a better theory of the motion of objects.
To make the overall design more concrete, let us return to the automated taxi example. The
performance element consists of whatever collection of knowledge and procedures the taxi has for
selecting its driving actions. The taxi goes out on the road and drives, using this performance
element. The critic observes the world and passes information along to the learning element. For
example, after the taxi makes a quick left turn across three lanes of traffic, the critic observes the
shocking language used by other drivers. From this experience, the learning element is able to
formulate a rule saying this was a bad action, and the performance element is modified by
installation of the new rule. The problem generator might identify certain areas of behavior in need
of improvement and suggest experiments, such as trying out the brakes on different road surfaces
under different conditions.
In summary, agents have a variety of components, and those components can be represented in
many ways within the agent program, so there appears to be great variety among learning methods.
There is, however, a single unifying theme. Learning in intelligent agents can be summarized as a
process of modification of each component of the agent to bring the components into closer

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

agreement with the available feedback information, thereby improving the overall performance of
the agent.

2.4.7 How the components of agent programs work

We can place the representations along an axis of increasing complexity and expressive power—
atomic, factored, and structured. To illustrate these ideas, it helps to consider a particular agent
component, such as the one that deals with “What my actions do.” This component describes the
changes that might occur in the environment as the result of taking an action, and Figure 2.16
provides schematic depictions of how those transitions might be represented.

In an atomic representation each state of the world is indivisible—it has no internal structure.
Consider the problem of finding a driving route from one end of a country to the other via some
sequence of cities (we address this problem in Figure 3.2 on page 68). For the purposes of solving
this problem, it may suffice to reduce the state of world to just the name of the city we are in—a
single atom of knowledge; a “black box” whose only discernible property is that of being identical
to or different from another black box. The algorithms underlying search and game-playing,

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

Hidden Markov models, and Markov decision processes all work with atomic representations—
or, atleast, they treat representations as if they were atomic.
A factored representation splits up each state into a fixed set of variables or attributes, each of
which can have a value. While two different atomic states have nothing in common—they are just
different black boxes—two different factored states can share some attributes (such as being at
some particular GPS location) and not others (such as having lots of gas or having no gas); this
makes it much easier to work out how to turn one state into another. With factored representations,
we can also represent uncertainty—for example, ignorance about the amount of gas in the tank can
be represented by leaving that attribute blank. Many important areas of AI are based on factored
representations, including constraint satisfaction algorithms, propositional logic, planning,
Bayesian networks , and the machine learning algorithms.

SUMMARY:
This chapter has been something of a whirlwind tour of AI, which we have conceived of as
the science of agent design. The major points to recall are as follows:
• An agent is something that perceives and acts in an environment. The agent function for an agent
specifies the action taken by the agent in response to any percept sequence.
• The performance measure evaluates the behavior of the agent in an environment. A rational agent
acts so as to maximize the expected value of the performance measure, given the percept sequence
it has seen so far.
• A task environment specification includes the performance measure, the external environment,
the actuators, and the sensors. In designing an agent, the first step must always be to specify the
task environment as fully as possible.
• Task environments vary along several significant dimensions. They can be fully or partially
observable, single-agent or multiagent, deterministic or stochastic, episodic or sequential, static or

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

dynamic, discrete or continuous, and known or unknown.

• The agent program implements the agent function. There exists a variety of basic agent-program
designs reflecting the kind of information made explicit and used in the decision process. The
designs vary in efficiency, compactness, and flexibility. The appropriate design of the agent
program depends on the nature of the environment.
• Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain
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
“happiness.”
• All agents can improve their performance through learning.

MODULE 1 QUESTION BANK

1. Explain in detail the four categories of AI.
2. Write short notes on a)Robotic Vehicles b)Speech Recognition c)Game Playing
d)Spam fighting e)Logistics Planning f)Machine Translation
3. Illustrate with a neat diagram how agents interact with environments through sensors
and actuators.
4. Explain the concept of rationality.
5. What does being rational depend on?
6. Give the tabular representation of the vacuum cleaner agent function.
7. Distinguish between rationality and omniscience.
8. Explain PEAS (Performance, Environment, Actuators, Sensors) with any simple
agent-environment example.
9. Distinguish between Fully observable and partially observable
10. Distinguish between Single agent and Multiagent.
11. Distinguish between Deterministic and Stochastic.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1

 Sri Sai Vidya Vikas Shikshana Samithi ®
SAI VIDYA INSTITUTE OF TECHNOLOGY
Approved by AICTE, New Delhi, Affiliated to VTU, Recognized by Govt. of Karnataka
Accredited by NBA, New Delhi (CSE, ISE, ECE, MECH & CIVIL),NAAC-‘A’ Grade
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJANUKUNTE, BENGALURU 560 064, KARNATAKA
Phone: 080-28468191/96/97/98 *E-mail: hodcse@[Link] * URL [Link]

12. Distinguish between Episodic and Sequential.

13. Distinguish between Static and Dynamic.
14. Distinguish between Discrete and Continuous.
15. Distinguish between Known and Unknown.
16. Explain the structure of agents with an example of an agent program.
17. Explain with a diagram the simple reflex agent.
18. Explain with a diagram the Model-based reflex agents.
19. Explain with a diagram the Goal-based agents.
20. Explain with a diagram the utility agents.
21. Interpret the working a simple general learning agent.

Prof. Salma Itagi, Dept. of CSE, SVIT MODULE 1