Chapter 1

Artificial Intelligence and Agents

The history of AI is a history of fantasies, possibilities, demonstrations,

and promise. Ever since Homer wrote of mechanical “tripods” waiting on
the gods at dinner, imagined mechanical assistants have been a part of our
culture. However, only in the last half century have we, the AI commu-
nity, been able to build experimental machines that test hypotheses about
the mechanisms of thought and intelligent behavior and thereby demon-
strate mechanisms that formerly existed only as theoretical possibilities.

– Bruce Buchanan [2005]

This book is about artificial intelligence (AI), a field built on centuries of thought,
which has been a recognized discipline for over 60 years. As well as solving
practical tasks, AI provides tools to test hypotheses about the nature of thought
itself. Deep scientific and engineering problems have already been solved and
many more are waiting to be solved. Many practical applications are currently
deployed and the potential exists for an almost unlimited number of future
applications. This book presents the principles that underlie intelligent com-
putational agents.

1.1 What is Artificial Intelligence?

Artificial intelligence, or AI, is the field that studies the synthesis and analysis of
computational agents that act intelligently. Consider each part of this definition.
An agent is something that acts in an environment; it does something.
Agents include worms, dogs, thermostats, airplanes, robots, humans, compa-
nies, and countries.
An agent is judged solely by how it acts. Agents that have the same effect
in the world are equally good.

3
4 1. Artificial Intelligence and Agents

Intelligence is a matter of degree. The aspects that go into an agent acting

intelligently include
• what it does is appropriate for its circumstances, its goals, and its percep-
tual and computational limitations
• it takes into account the short-term and long-term consequences of its
actions, including the effects on society and the environment
• it learns from experience
• it is flexible to changing environments and changing goals.
A computational agent is an agent whose decisions about its actions can be
explained in terms of computation. That is, the decision can be broken down
into primitive operations that can be implemented in a physical device. This
computation can take many forms. In humans, this computation is carried out
in “wetware”; in computers it is carried out in “hardware.” Although there are
some agents that are arguably not computational, such as the wind and rain
eroding a landscape, it is an open question whether all intelligent agents are
computational.
All agents are limited. No agent is omniscient (all knowing) or omnipotent
(can do anything). Agents can only observe everything in very specialized and
constrained domains. Agents have finite memory. Agents in the real world do
not have unlimited time to act.
The central scientific goal of AI is to understand the principles that make
intelligent behavior possible in natural or artificial systems. This is done by
• the analysis of natural and artificial agents
• formulating and testing hypotheses about what it takes to construct in-
telligent agents
• designing, building, and experimenting with computational systems that
perform tasks commonly viewed as requiring intelligence.
As part of science, researchers build empirical systems to test hypotheses or to
explore the space of possible designs. These are distinct from applications that
are built to be useful for an application domain.
The definition is not for intelligent thought. The role of thought is to affect
action and lead to more intelligent behavior.
The central engineering goal of AI is the design and synthesis of agents
that act intelligently, which leads to useful artifacts.
Building general intelligence isn’t the only goal of AI researchers. The aim
of intelligence augmentation is to augment human intelligence and creativity.
A diagnostic agent helps medical practitioners make better decisions, a search
engine augments human memory, and natural language translation systems
help people communicate. AI systems are often in human-in-the-loop mode,
where humans and agents work together to solve problems. Sometimes the
actions of artificial agents are to give advice to a human. Sometimes humans
give advice or feedback to artificial agents, particularly for cases where deci-
sions are made quickly or repeatedly.
1.1. What is Artificial Intelligence? 5

1.1.1 Artificial and Natural Intelligence

Artificial intelligence (AI) is the established name for the field, but the term “ar-
tificial intelligence” is a source of much confusion because artificial intelligence
may be interpreted as the opposite of real intelligence.
For any phenomenon, you can distinguish real versus fake, where the fake
is non-real. You can also distinguish natural versus artificial. Natural means
occurring in nature and artificial means made by people.

Example 1.1 A tsunami is a large wave in an ocean. Natural tsunamis oc-

cur from time to time and are caused by earthquakes or landslides. You could
imagine an artificial tsunami that was made by people, for example, by ex-
ploding a bomb in the ocean, yet which is still a real tsunami. One could also
imagine fake tsunamis: either artificial, using computer graphics, or natural,
such as a mirage that looks like a tsunami but is not one.

It is arguable that intelligence is different: you cannot have fake intelligence.

If an agent behaves intelligently, it is intelligent. It is only the external behavior
that defines intelligence; acting intelligently is being intelligent. Thus, artificial
intelligence, if and when it is achieved, will be real intelligence created artifi-
cially.
This idea of intelligence being defined by external behavior was the moti-
vation for a test for intelligence designed by Turing [1950], which has become
known as the Turing test. The Turing test consists of an imitation game where
an interrogator can ask a witness, via a text interface, any question. If the in-
terrogator cannot distinguish the witness from a human, the witness must be
intelligent. Figure 1.1 shows a possible dialog that Turing suggested. An agent
that is not really intelligent could not fake intelligence for arbitrary topics.

Interrogator: In the first line of your sonnet which reads “Shall I compare thee
to a summer’s day,” would not ”a spring day” do as well or better?
Witness: It wouldn’t scan.
Interrogator: How about “a winter’s day,” That would scan all right.
Witness: Yes, but nobody wants to be compared to a winter’s day.
Interrogator: Would you say Mr. Pickwick reminded you of Christmas?
Witness: In a way.
Interrogator: Yet Christmas is a winter’s day, and I do not think Mr. Pickwick
would mind the comparison.
Witness: I don’t think you’re serious. By a winter’s day one means a typical
winter’s day, rather than a special one like Christmas.
Figure 1.1: Part of Turing’s possible dialog for the Turing test
6 1. Artificial Intelligence and Agents

There has been much debate about the usefulness of the Turing test. Un-
fortunately, although it may provide a test for how to recognize intelligence, it
does not provide a way to realize intelligence.
Levesque [2014] suggested a new form of question, a Winograd schema
after the following example of Winograd [1972]:

• The city councilmen refused the demonstrators a permit because they

feared violence. Who feared violence?

• The city councilmen refused the demonstrators a permit because they

advocated violence. Who advocated violence?

These two sentences only differ in one word – feared/advocated – but have the
opposite answer.
Winograd schemas have the property that (a) humans can easily disam-
biguate them and (b) there is no simple grammatical or statistical test that could
disambiguate them. For example, the sentences above would not qualify if the
phrase “demonstrators feared violence” was much less or more likely than the
phrase “councilmen feared violence” independently of the context, and simi-
larly with advocating.

Example 1.2 The following examples are due to Davis [2015]:

• Steve follows Fred’s example in everything. He [admires/influences] him
hugely. Who [admires/influences] whom?
• The table won’t fit through the doorway because it is too [wide/narrow].
What is too [wide/narrow]?
• Grace was happy to trade me her sweater for my jacket. She thinks it looks
[great/dowdy] on her. What looks [great/dowdy] on Grace?
• Bill thinks that calling attention to himself was rude [to/of] Bert. Who
called attention to himself?
Each of these have their own reasons why one answer is preferred to the other.
A computer that can reliably answer these questions needs to know about all of
these reasons, and arguably requires the ability to do commonsense reasoning.
Common sense should also allow it to reject sentences such as “The doorway
won’t fit through the chair because it is too narrow. What is too narrow?”.
Figure 1.2 (page 7) shows some answers provided by ChatGPT [OpenAI,
2022], based on GPT-3 [Brown et al., 2020], one of the most capable large lan-
guage models in 2022. ChatGPT gives a different answer each time it is called.
You can decide whether it solves this Winograd schema. The technology be-
hind GPT-3 and related models is described in Section 8.5 (page 350).

Grosz [2012], arguing that language is inherently social and connected to

human cooperation, suggested that a more appropriate test should involve
purposeful natural language, not language just for the purpose of tricking a
human. She suggested the question:
1.1. What is Artificial Intelligence? 7

Human: The table won’t fit through the doorway because it is too narrow.
What is too narrow?
ChatGPT: If a table won’t fit through a doorway because it is too narrow,
it means that the width of the table is greater than the width of the doorway.
In other words, the doorway is not wide enough to allow the table to pass
through it. This can be a problem if you are trying to move the table from one
room to another and the only way to do so is through the doorway. In order
to solve this problem, you may need to remove the door or trim the table so
that it fits through the doorway. Alternatively, you may need to find a different
route to move the table, such as through a window or by taking it apart and
reassembling it in the other room.
Human: The table won’t fit through the doorway because it is too wide.
What is too wide?
ChatGPT: If a table won’t fit through a doorway because it is too wide, it
means that the width of the doorway is smaller than the width of the table.
In other words, the table is too big to fit through the doorway. This can be
a problem if you are trying to move the table from one room to another and
the only way to do so is through the doorway. In order to solve this problem,
you may need to remove the door or trim the table so that it fits through the
doorway. Alternatively, you may need to find a different route to move the
table, such as through a window or by taking it apart and reassembling it in
the other room.
Human: The doorway won’t fit through the chair because it is too narrow.
What is too narrow?
ChatGPT: ”Too narrow” means that the doorway is not wide enough to
fit through the chair. In this context, the doorway is the object that is being
compared to the chair, and it is not wide enough to pass through the chair
without encountering some difficulty or obstruction. This could be because
the doorway is physically smaller in width than the chair, or because there is
some other physical feature of the chair that is preventing the doorway from
fitting through it. For example, the chair might have armrests or other protu-
berances that make it difficult for the doorway to pass through. In general, the
phrase ”too narrow” is used to describe something that is not wide enough to
fit through or pass a particular opening or gap.
Human: The doorway won’t fit through the chair because it is too narrow.
What is too narrow?
ChatGPT: If a doorway is too narrow to fit through a chair, it means that the
width of the doorway is smaller than the width of the chair. This can happen if
the chair is too wide to fit through the doorway, or if the doorway is not wide
enough to accommodate the chair. In either case, the chair will not be able to
pass through the doorway because there is not enough space for it to fit.
Figure 1.2: ChatGPT answers to some Winograd schemas
8 1. Artificial Intelligence and Agents

Is it imaginable that a computer (agent) team member could behave, over

the long term and in uncertain, dynamic environments, in such a way that
people on the team will not notice it is not human?
– Barbara Grosz [2012]
An equal member of the team needs to be trusted enough to act in the world
appropriately, know when to ask questions, and when to not act. This chal-
lenge also allows for incremental improvement; starting with simple group
interactions before moving to complex ones.
Interacting in natural language is not the only aspect of intelligence. An
agent acting in an environment needs common sense, “the ability to make
effective use of ordinary, everyday, experiential knowledge in achieving or-
dinary, practical goals” [Brachman and Levesque, 2022b]. Here, knowledge
is used in a general way to mean any non-transient information in an agent.
Such knowledge is typically not stated in natural language; people do not state
what everyone knows. Some knowledge, such as how to ride a bike or recog-
nize a face, cannot be effectively conveyed by natural language. Formalizing
common sense has a long history [McCarthy, 1958; Davis, 1990], including the
development of representations and actual commonsense knowledge.

1.1.2 Natural Intelligence

The obvious naturally intelligent agent is the human being. Some people might
say that worms, insects, or bacteria are intelligent, but more people would say
that dogs, whales, or monkeys are intelligent (see Exercise 1.1 (page 48)). One
class of intelligent agents that may be more intelligent than humans is the class
of organizations. Ant colonies are a prototypical example of organizations.
Each individual ant may not be very intelligent, but an ant colony can act more
intelligently than any individual ant. The colony can discover food and ex-
ploit it very effectively, as well as adapt to changing circumstances. Corpo-
rations can be more intelligent than individual people. Companies develop,
manufacture, and distribute products where the sum of the skills required is
much more than any individual could master. Modern computers, from low-
level hardware to high-level software, are more complicated than any single
human can understand, yet they are manufactured daily by organizations of
humans. Human society viewed as an agent is arguably the most intelligent
agent known.
It is instructive to consider where human intelligence comes from. There
are three main sources:
Biology Humans have evolved into adaptable animals that can survive in var-
ious habitats.
Culture Culture provides not only language, but also useful tools, useful con-
cepts, and the wisdom that is passed from parents and teachers to chil-
dren.
1.2. A Brief History of Artificial Intelligence 9

Lifelong learning Humans learn throughout their life and accumulate knowl-
edge and skills.

These sources interact in complex ways. Biological evolution has provided

stages of growth that allow for different learning at different stages of life.
Biology and culture have evolved together; humans can be helpless at birth,
presumably because of our culture of looking after infants. Culture interacts
strongly with learning. A major part of lifelong learning is what people are
taught by parents and teachers. Language, which is part of culture, provides
distinctions in the world that are useful for learning.
When building an intelligent system, the designers have to decide which
of these sources of intelligence need to be programmed in, and which can be
learned. It is very unlikely that anyone will be able to build an agent that starts
with a clean slate and learns everything, particularly for non-repetitive tasks.
Similarly, most interesting and useful intelligent agents learn to improve their
behavior.

1.2 A Brief History of Artificial Intelligence

Throughout human history, people have used technology to model themselves.
There is evidence of this from ancient China, Egypt, and Greece, bearing wit-
ness to the universality of this activity. Each new technology has, in its turn,
been exploited to build intelligent agents or models of mind. Clockwork, hy-
draulics, telephone switching systems, holograms, analog computers, and dig-
ital computers have all been proposed both as technological metaphors for in-
telligence and as mechanisms for modeling mind.
Hobbes (1588–1679), who has been described by Haugeland [1985, p. 85]
as the “Grandfather of AI,” espoused the position that thinking was symbolic
reasoning, like talking out loud or working out an answer with pen and pa-
per. The idea of symbolic reasoning was further developed by Descartes (1596–
1650), Pascal (1623–1662), Spinoza (1632–1677), Leibniz (1646–1716), and others
who were pioneers in the European philosophy of mind.
The idea of symbolic operations became more concrete with the develop-
ment of computers. Babbage (1792–1871) designed the first general-purpose
computer, the Analytical Engine. Leonardo Torres y Quevedo build a chess
playing machine based on similar ideas in 1911 [Randell, 1982]. In the early
part of the twentieth century, there was much work done on understanding
computation. Several models of computation were proposed, including the
Turing machine by Alan Turing (1912–1954), a theoretical machine that writes
symbols on an infinitely long tape, and the lambda calculus of Church (1903–
1995), which is a mathematical formalism for rewriting formulas. It can be
shown that these very different formalisms are equivalent in that any function
computable by one is computable by the others. This leads to the Church–
Turing thesis:
10 1. Artificial Intelligence and Agents

Any effectively computable function can be carried out on a Turing

machine (and so also in the lambda calculus or any of the other
equivalent formalisms).

Effectively computable means following well-defined operations. In Turing’s

day, “computers” were people who followed well-defined steps; computers
as known today did not exist. This thesis says that all computation can be
carried out on a Turing machine or one of the other equivalent computational
machines. The Church–Turing thesis cannot be proved but it is a hypothesis
that has stood the test of time. No one has built a machine that has carried
out computation that cannot be computed by a Turing machine. There is no
evidence that people can compute functions that are not Turing computable.
This provides an argument that computation is more than just a metaphor for
intelligence; reasoning is computation and computation can be carried out by
a computer.
Some of the first applications of computers were AI programs. Samuel
[1959] built a checkers program in 1952 and implemented a program that learns
to play checkers in the late 1950s. His program beat the Connecticut state
checkers champion in 1961. Wang [1960] implemented a program that proved
every logic theorem (nearly 400) in Principia Mathematica [Whitehead and Rus-
sell, 1925, 1927]. Newell and Simon [1956] built a program, Logic Theorist,
that discovers proofs in propositional logic.
In parallel, there was also much work on neural networks learning inspired
by how neurons work. McCulloch and Pitts [1943] showed how a simple
thresholding “formal neuron” could be the basis for a Turing-complete ma-
chine. Learning for artificial neural networks was first described by Minsky
[1952]. One of the early significant works was the perceptron of Rosenblatt
[1958]. The work on neural networks became less prominent for a number of
years after the 1968 book by Minsky and Papert [1988], which argued that the
representations learned were inadequate for intelligent action. Many technical
foundations for neural networks were laid in the 1980s and 1990s [Rumelhart
et al., 1986; Hochreiter and Schmidhuber, 1997; LeCun et al., 1998a]. Widespread
adoption followed the success by Krizhevsky et al. [2012] for ImageNet [Deng
et al., 2009], a dataset of over 3 million images labelled with over 5000 cate-
gories. Subsequent major advances include the introduction of generative ad-
versarial networks (GANs) [Goodfellow et al., 2014] and transformers [Vaswani
et al., 2017]. Neural networks in various forms are now the state of the art for
predictive models for large perceptual datasets, including images, video, and
speech, as well as some tasks for text. They are also used for generative AI,
to generate images, text, code, molecules, and other structured output. See
Chapter 8.
Neural networks are one of many machine learning tools used for making
predictions from data in modern applications. Other methods have been devel-
oped though the years, including decision trees [Breiman et al., 1984; Quinlan,
1993] and logistic regression, introduced by Verhulst in 1832 [Cramer, 2002].
1.2. A Brief History of Artificial Intelligence 11

These have diverse applications in many areas of science. Combining these al-
gorithms leads to the state-of-the-art gradient-boosted trees [Friedman, 2001;
Chen and Guestrin, 2016], which demonstrates the close interconnections be-
tween statistics and machine learning.
While useful, making predictions is not sufficient to determine what an
agent should do; an agent also needs to plan. Planning in AI was initially
based on deterministic actions. Fikes and Nilsson [1971] used deterministic
actions to control a mobile robot. Planning under uncertainty has a long his-
tory. Markov decision processes (MDPs), the foundation for much of planning
under uncertainty, and dynamic programming, a general way to solve them,
were invented by Bellman [1957]. These were extended into decision-theoretic
planning in the 1990’s [Boutilier et al., 1999]. Decision-theoretic planning with
learning is called reinforcement learning. The first reinforcement learning
programs were due to Andreae [1963] and Michie [1963]. Major advances
came with the inventions of temporal-difference learning [Sutton, 1988] and
Q-learning [Watkins and Dayan, 1992]. Work in reinforcement learning has
exploded, including superhuman performance in chess, Go and other games
[Silver et al., 2017].
Planning requires representations. The need for representations was recog-
nized early.

A computer program capable of acting intelligently in the world must have

a general representation of the world in terms of which its inputs are in-
terpreted. Designing such a program requires commitments about what
knowledge is and how it is obtained. . . . More specifically, we want a com-
puter program that decides what to do by inferring in a formal language
that a certain strategy will achieve its assigned goal. This requires formal-
izing concepts of causality, ability, and knowledge.

– McCarthy and Hayes [1969]

Many of the early representations were ad hoc, such as frames [Minsky,

1975], like the schemas of Kant [1787], Bartlett [1932], and Piaget [1953]. Later
representations were based on logic [Kowalski, 1979], with knowledge being
defined in logic and efficient inference. This resulted in languages such as Pro-
log [Kowalski, 1988; Colmerauer and Roussel, 1996].
Probabilities were eschewed in AI, because of the number of parameters
required, until the breakthrough of Bayesian networks (belief networks) and
graphical models [Pearl, 1988], which exploit conditional independence, and
form a basis for modeling causality. Combining first-order logic and probabil-
ity is the topic of statistical relational AI [De Raedt et al., 2016].
There has been a continual tension between how much knowledge is learned
and how much is provided by human experts or is innate to an agent. It has
long been recognized that learning is needed, and it is known that learning
cannot be achieved with data alone (page 315). During the 1970s and 1980s,
12 1. Artificial Intelligence and Agents

expert systems came to prominence, where the aim was to capture the knowl-
edge of an expert in some domain so that a computer could carry out expert
tasks. DENDRAL [Buchanan and Feigenbaum, 1978], developed from 1965 to
1983 in the field of organic chemistry, proposed plausible structures for new
organic compounds. MYCIN [Buchanan and Shortliffe, 1984], developed from
1972 to 1980, diagnosed infectious diseases of the blood, prescribed antimicro-
bial therapy, and explained its reasoning.
An alternative approach, de-emphasizing explicit knowledge representa-
tions, emphasized situated embodied agents [Brooks, 1990; Mackworth, 2009].
The hypothesis is that intelligence emerges, in evolution and individual devel-
opment, through ongoing interaction and coupling with a real environment.
During the 1960s and 1970s, natural language understanding systems were
developed for limited domains. For example, the STUDENT program of Bo-
brow [1967] could solve high-school algebra tasks expressed in natural lan-
guage. Winograd’s [1972] SHRDLU system could, using restricted natural
language, discuss and carry out tasks in a simulated blocks world. CHAT-
80 [Warren and Pereira, 1982] could answer geographical questions placed to it
in natural language. Figure 1.3 (page 13) shows some questions that CHAT-80
answered based on a database of facts about countries, rivers, and so on. These
systems could only reason in very limited domains using restricted vocabu-
lary and sentence structure. Interestingly, IBM’s Watson, which beat the world
champion in the TV game show Jeopardy! in 2011, used a technique similar
to CHAT-80 [Lally et al., 2012] for understanding questions; see Section 15.7
(page 674).
In applications using language in the wild, such as speech recognition and
translation in phones, many technologies are combined, including neural net-
works; see Chapter 8. Large language models (page 364), trained on huge
datasets, can be used to predict the next word in a text, enabling predictive
spelling and the creation of new text.

1.2.1 Relationship to Other Disciplines

AI is a very young discipline. Other disciplines as diverse as philosophy, neu-
robiology, evolutionary biology, psychology, economics, political science, soci-
ology, anthropology, control engineering, statistics, and many more have been
studying aspects of intelligence much longer.
The science of AI could be described as “synthetic psychology,” “experi-
mental philosophy,” or “computational epistemology” – epistemology is the
study of knowledge. AI can be seen as a way to study the nature of knowledge
and intelligence, but with more powerful experimental tools than were previ-
ously available. Instead of being able to observe only the external behavior of
intelligent systems, as philosophy, psychology, economics, and sociology have
traditionally been able to do, AI researchers experiment with executable mod-
els of intelligent behavior. Most important, such models are open to inspection,
redesign, and experimentation in a complete and rigorous way. Modern com-
1.2. A Brief History of Artificial Intelligence 13

puters provide a way to construct the models about which philosophers have
only been able to theorize. AI researchers can experiment with these mod-
els as opposed to just discussing their abstract properties. AI theories can be
empirically grounded in implementations. Sometimes simple agents exhibit
complex behavior, and sometimes sophisticated, theoretically motivated algo-
rithms don’t work in real-world domains, which would not be known without
implementing the agents.
It is instructive to consider an analogy between the development of fly-
ing machines over the past few centuries and the development of thinking
machines over the past few decades. There are several ways to understand
flying. One is to dissect known flying animals and hypothesize their com-
mon structural features as necessary fundamental characteristics of any flying
agent. With this method, an examination of birds, bats, and insects would sug-
gest that flying involves the flapping of wings made of some structure covered
with feathers or a membrane. Furthermore, the hypothesis could be tested by
strapping feathers to one’s arms, flapping, and jumping into the air, as Icarus
did. An alternative methodology is to try to understand the principles of flying
without restricting oneself to the natural occurrences of flying. This typically
involves the construction of artifacts that embody the hypothesized principles,

Does Afghanistan border China?

What is the capital of Upper Volta?
Which country’s capital is London?
Which is the largest African country?
How large is the smallest American country?
What is the ocean that borders African countries and that borders
Asian countries?
What are the capitals of the countries bordering the Baltic?
How many countries does the Danube flow through?
What is the total area of countries south of the Equator and not in
Australasia?
What is the average area of the countries in each continent?
Is there more than one country in each continent?
What are the countries from which a river flows into the Black Sea?
What are the continents no country in which contains more than two
cities whose population exceeds 1 million?
Which country bordering the Mediterranean borders a country that
is bordered by a country whose population exceeds the population
of India?
Which countries with a population exceeding 10 million border the
Atlantic?
Figure 1.3: Some questions CHAT-80 could answer
14 1. Artificial Intelligence and Agents

even if they do not behave like flying animals in any way except flying. This
second method has provided both useful tools – airplanes – and a better un-
derstanding of the principles underlying flying, namely aerodynamics. Birds
are still much better at flying though forests.
AI takes an approach analogous to that of aerodynamics. AI researchers
are interested in testing general hypotheses about the nature of intelligence
by building machines that are intelligent and that do not necessarily mimic
humans or organizations. This also offers an approach to the question, “Can
computers really think?” by considering the analogous question, “Can air-
planes really fly?”
AI is intimately linked with the discipline of computer science because the
study of computation is central to AI. It is essential to understand algorithms,
data structures, and combinatorial complexity to build intelligent machines. It
is also surprising how much of computer science started as a spinoff from AI,
from timesharing to computer algebra systems.
Finally, AI can be seen as coming under the umbrella of cognitive science.
Cognitive science links various disciplines that study cognition and reason-
ing, from psychology to linguistics to anthropology to neuroscience. AI distin-
guishes itself within cognitive science by providing tools to build intelligence
rather than just studying the external behavior of intelligent agents or dissect-
ing the inner workings of intelligent systems.

1.3 Agents Situated in Environments

AI is about practical reasoning: reasoning in order to do something. A coupling
of perception, reasoning, and acting comprises an agent. An agent acts in an
environment. An agent’s environment often includes other agents. An agent
together with its environment is called a world.
An agent could be, for example, a coupling of a computational engine with
physical sensors and actuators, called a robot, where the environment is a
physical setting. An autonomous agent is one that acts in the world with-
out human intervention. A semi-autonomous agent acts with a human-in-
the-loop who may provide perceptual information and carry out the task. An
agent could be a program that acts in a purely computational environment, a
software agent, often called a bot.
Figure 1.4 (page 15) shows a black-box view of an agent in terms of its
inputs and outputs. At any time, what an agent does depends on:
• prior knowledge about the agent and the environment
• stimuli received from the environment, which can include observations
about the environment (e.g., light, sound, keyboard commands, web re-
quests) as well as actions that the environment imposes on the agent (e.g.,
bumping the agent)
• past experiences, including history of interaction with the environment
(its previous actions and stimuli) and other data, from which it can learn
1.3. Agents Situated in Environments 15

• goals that it must try to achieve or preferences over states of the world
• abilities, the primitive actions the agent is capable of carrying out.

Inside the black box, an agent has a belief state that can encode beliefs
about its environment, what it has learned, what it is trying to do, and what
it intends to do. An agent updates this internal state based on stimuli. It uses
the belief state and stimuli to decide on its actions. Much of this book is about
what is inside this black box.
Purposive agents have preferences or goals. They prefer some states of the
world to other states, and they act to try to achieve the states they prefer most.
The non-purposive agents are grouped together and called nature. Whether
or not an agent is purposive is a modeling assumption that may, or may not,
be appropriate. For example, for some applications it may be appropriate to
model a dog as purposive, such as drug-sniffing dogs, and for others it may
suffice to model a dog as non-purposive, such as when they are just part of the
environment.
If an agent does not have preferences, by definition it does not care what
world state it ends up in, and so it does not matter to it what it does. The reason
to design an agent is to instill preferences in it – to make it prefer some world
states and try to achieve them. An agent does not have to know its preferences
explicitly. For example, a thermostat for a heater is an agent that senses the
world and turns the heater either on or off. There are preferences embedded
in the thermostat, such as to keep the room at a pleasant temperature, even
though the thermostat arguably does not know these are its preferences. The
preferences of an agent are often the preferences of the designer of the agent,
but sometimes an agent can acquire goals and preferences at run time.

Abilities

Goals/Preferences

Prior Knowledge Agent

Stimuli
Actions
Past Experiences

Environment

Figure 1.4: An agent interacting with an environment

16 1. Artificial Intelligence and Agents

This is an all-encompassing view of intelligent agents varying in complex-

ity from a simple thermostat, to a diagnostic advising system whose percep-
tions and actions are mediated by human beings, to a team of mobile robots,
to society itself. An agent does not have access to anything else; anything that
does not affect one of these inputs cannot affect the agent’s action.

1.4 Prototypical Applications

AI applications are widespread and diverse and include medical diagnosis,
scheduling factory processes, robots for hazardous environments, game play-
ing, autonomous cars, natural language translation systems, choosing adver-
tisements, personal assistants, and tutoring agents. Rather than treating each
application separately, we abstract the essential features of such applications to
better understand the principles behind intelligent reasoning and action.
Five main application domains are developed in examples throughout the
book. Although the particular examples presented are simple – otherwise they
would not fit into the book – the application domains are representative of the
range of domains in which AI techniques can be, and are being, used.

1.4.1 An Autonomous Delivery and Helping Robot

Imagine a robot with wheels and the ability to pick up, put down and manip-
ulate objects. It has sensing capabilities allowing it to recognize objects and
to avoid obstacles. It can be given orders in natural language and obey them,
making reasonable choices about what to do when its goals conflict. Such a
robot could deliver packages or coffee in an office environment, clean a home
and put things in their appropriate place, or help caregivers in a hospital. Em-
bedded in a wheelchair, it could help disabled people. It should be useful as
well as safe.
In terms of the black-box characterization of an agent in Figure 1.4 (page 15),
the autonomous delivery robot has as inputs:
• prior knowledge, provided by the agent designer, about the agent’s ca-
pabilities, what objects it may encounter and have to differentiate, what
requests mean, and perhaps about its environment, such as a map
• past experience obtained while acting, for instance, about the effects of its
actions (and – hopefully limited – experiences of breaking objects), what
objects are common in the world, and what requests to expect at different
times of the day
• goals in terms of what it should deliver and when, as well as preferences
specifying trade-offs, such as when it must forgo one goal to pursue an-
other, or the trade-off between acting quickly and acting safely
• stimuli about its environment from observations from input devices such
as cameras, sonar, touch, sound, laser range finders, or keyboards as well
as stimuli such as the agent being forcibly moved or crashing.
1.4. Prototypical Applications 17

The robot’s outputs are motor controls specifying how its wheels should turn,
where its limbs should move, and what it should do with its grippers. Other
outputs may include speech and a video display.
Example 1.3 Figure 1.5 depicts a typical laboratory environment for a delivery
robot. This environment consists of four laboratories and many offices. In our
examples, the robot can only push doors, and the directions of the doors in
the diagram reflect the directions in which the robot can travel. Rooms require
keys and those keys can be obtained from various sources. The robot must
deliver parcels, beverages, and dishes from room to room. The environment
also contains a stairway that is potentially hazardous to the robot.

1.4.2 A Diagnostic Assistant

A diagnostic assistant is intended to advise a human about some particular
system such as a medical patient, the electrical system in a home, or an au-
tomobile. The diagnostic assistant should advise about potential underlying
faults or diseases, what tests to carry out, and what treatment to prescribe. To
give such advice, the assistant requires a model of the system, including knowl-
edge of potential causes, available tests, available treatments, and observations
of the system (which are often called symptoms).

r131 r129 r127 r125 r123 r121 r119

r117

lab D lab C

r115

lab A lab B
r113

main
office stairs r101 r103 r105 r107 r109 r111

Figure 1.5: A typical laboratory environment for the delivery robot. This shows
the locations of the doors and which way they open.
18 1. Artificial Intelligence and Agents

To be useful, the diagnostic assistant must provide added value, be easy for
a human to use, and not be more trouble than it is worth. A diagnostic assistant
connected to the Internet can draw on expertise from throughout the world,
and its actions can be based on the most up-to-date research. However, it must
be able to justify why the suggested diagnoses or actions are appropriate. Hu-
mans are, and should be, suspicious of computer systems that are opaque and
impenetrable. When humans are responsible for what they do, even if their
actions are based on a computer system’s advice, the system needs to convince
the human that the suggested actions are defensible.
Example 1.4 Figure 1.6 shows an electrical distribution system in a home.
In this home, power comes into the home through circuit breakers and then it
goes to power outlets or to lights through light switches. For example, light l1
is on if there is power coming into the home, if circuit breaker cb1 is on, and if
switches s1 and s2 are either both up or both down. This is the sort of model that
someone may have of the electrical power in the home, which they could use
to determine what is wrong given evidence about the position of the switches
and which lights are on and which are off. The diagnostic assistant is there to
help a resident or an electrician troubleshoot electrical problems.

In terms of the black-box definition of an agent in Figure 1.4 (page 15), the
diagnostic assistant has as inputs:
• prior knowledge, such as how switches and lights normally work, how
diseases or malfunctions manifest themselves, what information tests pro-
vide, the effects of repairs or treatments, and how to find out information

outside_power
cb1
s1
w5
w1
circuit
s2 cb2 breaker
w2 w3
switch
s3 w6
w0

p2 light
w4
l1
p1 power
outlet
l2

Figure 1.6: An electrical environment for the diagnostic assistant

1.4. Prototypical Applications 19

• past experience, in terms of data of previous cases that include the effects
of repairs or treatments, the prevalence of faults or diseases, the preva-
lence of symptoms for these faults or diseases, and the accuracy of tests
• goals of fixing the device or preferences between repairing or replacing
components, or a patient’s preferences between living longer or reducing
pain
• stimuli that are observations of symptoms of a device or patient.

The output of the diagnostic assistant is in terms of recommendations of treat-

ments and tests, along with a rationale for its recommendations.

1.4.3 A Tutoring Agent

A tutoring agent tutors students in some domain of study. The environment
of the agent includes students who interact through a computer or tablet inter-
face, and perhaps the students’ parents and teachers.

Example 1.5 Consider a tutoring agent to teach elementary physics, such as

mechanics, that interacts with a student. In order to successfully tutor a stu-
dent, the agent needs to be able to solve problems in the physics domain, de-
termine the student’s knowledge and misunderstanding based on interacting
with them, and converse using natural language, mathematics, and diagrams.
In terms of the black-box definition of an agent in Figure 1.4 (page 15), a
tutoring agent has the following as inputs:

• prior knowledge, provided by the agent designer, about the subject matter
being taught, teaching strategies, possible student errors and misconcep-
tions.
• past experience, which the tutoring agent has acquired by interacting with
students, such as, what errors students make, how many examples and
problems it takes various students to learn various topics, and what stu-
dents forget; this can be information about students in general as well as
about a particular student.
• preferences about the importance of each topic, the level of achievement
of the student that is desired, and the importance given to student moti-
vation and engagement; there are often complex trade-offs among these.
• stimuli include observations of a student’s test results and observations of
the student’s interaction (or non-interaction) with the agent; students can
also ask questions or request help on new examples and problems.

The actions of the tutoring agent include presenting the theory and worked-
out examples, proposing suitable problems, providing help and feedback on
a student’s solution, asking the student questions, answering their questions,
and producing reports for parents and teachers.
20 1. Artificial Intelligence and Agents

1.4.4 A Trading Agent

A trading agent is like a robot, but instead of interacting with a physical en-
vironment, it interacts with an information environment. Its task is to pro-
cure goods and services for a user. It must be able to be told the needs of a
user, and it must interact with sellers (e.g., on the Web). The simplest trading
agent involves proxy bidding for a user on an auction site, where the system
will keep bidding until the user’s price limit is reached. A more complicated
trading agent will buy multiple complementary items, like booking a flight, a
hotel, and a rental car that fit together, in addition to trading off competing
preferences of the user. Web services provide tools on the Web designed to
be combined by trading agents. Another example of a trading agent is one
that monitors how much food and groceries are in a household, monitors the
prices, and orders goods before they are needed, while trying to keep costs to
a minimum.
In terms of the black-box definition of an agent in Figure 1.4 (page 15), the
trading agent has as inputs:
• prior knowledge about types of goods and services, selling practices, and
how auctions work
• past experience about where is the best place to look for specials, how
prices vary with time in an auction, and when specials tend to turn up
• preferences in terms of what the user wants and how to trade off compet-
ing goals
• stimuli including observations about what items are available, their price,
and, perhaps, how long they are available.
The output of the trading agent is either a recommendation the user can accept
or reject, or an actual purchase.
Because of the personalized nature of the trading agent, it should be able
to do better than a generic purchaser that, for example, only offers packaged
tours.

1.4.5 Smart Home

A smart home is a home that looks after itself and its inhabitants. It can be seen
as a mix of the other applications.
A smart home is an inside-out robot. It has physical sensors and actuators.
It should be able to sense where people, pets, and objects are. It should be able
to adjust lighting, sound, heat, etc., to suit the needs of its occupants, while
reducing costs and minimizing environmental impacts. A smart home will
not only have fixed sensors and actuators, but will be combined with mobile
robots, and other actuators, such as arms on the kitchen walls to help with
cooking, cleaning, and finding ingredients.
A purchaser of a smart home may expect it to be able to clean floors, dishes,
and clothes and to put things where they are kept. It is easy to clean a floor with
1.5. Agent Design Space 21

the assumption that everything small on the floor is garbage. It is much more
difficult to know which of the small items are precious toys and which are
junk that should be discarded, and this depends on the individual inhabitants
and their age. Each person may have their own categorization of objects and
where they are expected to be kept, which forces a smart home to adapt to the
inhabitants.
A smart home also must act as a diagnostician. When something goes
wrong, it should be able to determine what is the problem and fix it. It should
also be able to observe the inhabitants and determine if there is something
wrong, such as someone has been injured or there is a burglary.
Sometimes a smart home needs to act as a tutoring agent. It may have
to teach the occupants how the appliances work, and how to interact with the
home (e.g., what should an person expect to happen when they put their coffee
cup on the vacuum cleaner). In order to do this, it has to take into account the
knowledge and level of understanding of the person.
A smart home may also need to act as a purchasing agent. The home should
notice when items, such as toilet paper, soap, or essential foodstuffs, are run-
ning low and order more of them. Given a decision about what food each
inhabitant wants, it should make sure the ingredients are in stock. It might
even need to decide when inessential items, such as junk food, should be kept
in stock. It also might need to decide when to discard perishable items, without
creating too much waste or putting people’s health at risk.
A smart home would include energy management. For example, with solar
energy providing power during daylight hours, it could determine whether to
store the energy locally or buy and sell energy on the smart grid. It could
manage appliances to minimize the cost of energy, such as washing clothes
when water and electricity are cheaper.

1.5 Agent Design Space

Agents acting in environments range in complexity from thermostats to com-
panies with multiple goals acting in competitive environments. The ten di-
mensions of complexity in the design of intelligent agents below are designed
to help us understand work that has been done, as well as the potential and
limits of AI. These dimensions may be considered separately but must be com-
bined to build an intelligent agent. These dimensions define a design space
for AI; different points in this space are obtained by varying the values on each
dimension.
These dimensions give a coarse division of the design space for intelligent
agents. There are many other design choices that must also be made to build
an intelligent agent.
22 1. Artificial Intelligence and Agents

1.5.1 Modularity
The first dimension is the level of modularity.
Modularity is the extent to which a system can be decomposed into inter-
acting modules that can be understood separately.
Modularity is important for reducing complexity. It is apparent in the struc-
ture of the brain, serves as a foundation of computer science, and is an impor-
tant aspect of any large organization.
Modularity is typically expressed in terms of a hierarchical decomposition.
In the modularity dimension, an agent’s structure is one of the following:

• flat – there is no organizational structure

• modular – the system is decomposed into interacting modules that can
be understood on their own
• hierarchical – the system is modular, and the modules themselves are de-
composed into simpler modules, each of which are hierarchical systems
or simple components.

In a flat or modular structure the agent typically reasons at a single level of

abstraction. In a hierarchical structure the agent reasons at multiple levels of
abstraction. The lower levels of the hierarchy involve reasoning at a lower level
of abstraction.

Example 1.6 The delivery robot at the highest level has to plan its day, making
sure it can deliver coffee on time, but still has time for longer trips and cleaning
a room. At the lowest level, it needs to choose what motor controls to send to its
wheels, and what movement its gripper should do. Even a task like picking up
a glass involves many precise movements that need to be coordinated. Picking
up a glass may be just one part of the larger task of cleaning part of a room.
Cleaning the room might be one task that has to be scheduled into the robot’s
day.
In a flat representation, the agent chooses one level of abstraction and rea-
sons at that level. A modular representation would divide the task into a num-
ber of subtasks that can be solved separately (e.g., pick up coffee, move from
the corridor to lab B, put down coffee). In a hierarchical representation, the
agent will solve these subtasks in a hierarchical way, until the task is reduced
to simple tasks such a sending an http request or making a particular motor
control.

Example 1.7 A tutoring agent may have high-level teaching strategies, where
it needs to decide which topics are taught and in what order. At a much lower
level, it must design the details of concrete examples and specific questions for
a test. At the lowest level it needs to combine words and lines in diagrams to
express the examples and questions. Students can also be treated as learning in
a hierarchical way, with detailed examples as well as higher-level concepts.
1.5. Agent Design Space 23

Example 1.8 For the trading agent, consider the task of making all of the ar-
rangements and purchases for a custom holiday for a traveler. The agent should
be able to make bookings for flights that fit together. Only when it knows where
the traveller is staying and when, can it make more detailed arrangements such
as dinner and event reservations.

A hierarchical decomposition is important for reducing the complexity of

building an intelligent agent that acts in a complex environment. Large organi-
zations have a hierarchical organization so that the top-level decision makers
are not overwhelmed by details and do not have to micromanage all activities
of the organization. Procedural abstraction and object-oriented programming
in computer science are designed to enable simplification of a system by ex-
ploiting modularity and abstraction. There is much evidence that biological
systems are also hierarchical.
To explore the other dimensions, initially ignore the hierarchical structure
and assume a flat representation. Ignoring hierarchical decomposition is often
fine for small or moderately sized tasks, as it is for simple animals, small or-
ganizations, or small to moderately sized computer programs. When tasks or
systems become complex, some hierarchical organization is required.
How to build hierarchically organized agents is discussed in Section 2.2
(page 58).

1.5.2 Planning Horizon

The planning horizon dimension is how far ahead in time the agent plans. For
example, consider a dog as an agent. When a dog is called to come, it should
turn around to start running in order to get a reward in the future. It does not
act only to get an immediate reward. Plausibly, a dog does not act for goals
arbitrarily far in the future (e.g., in a few months), whereas people do (e.g.,
working hard now to get a holiday next year).
How far the agent “looks into the future” when deciding what to do is
called the planning horizon. For completeness, let’s include the non-planning
case where the agent is not reasoning in time. The time points considered by
an agent when planning are called stages.
In the planning horizon dimension, an agent is one of the following:
• A non-planning agent is an agent that does not consider the future when
it decides what to do or when time is not involved.
• A finite horizon planner is an agent that looks for a fixed finite number
of stages. For example, a doctor may have to treat a patient but may have
time for a test and so there may be two stages to plan for: a testing stage
and a treatment stage. In the simplest case, a greedy or myopic agent
only looks one time step ahead.
• An indefinite horizon planner is an agent that looks ahead some finite,
but not predetermined, number of stages. For example, an agent that
must get to some location may not know a priori how many steps it will
24 1. Artificial Intelligence and Agents

take to get there, but, when planning, it does not consider what it will do
after it gets to the location.
• An infinite horizon planner is an agent that plans on going on forever.
This is often called a process. For example, the stabilization module of
a legged robot should go on forever; it cannot stop when it has achieved
stability, because the robot has to keep from falling over.
The modules in a hierarchical decomposition may have different horizons,
as in the following example.

Example 1.9 For the delivery and helping agent, at the lowest level the mod-
ule that keeps the robot stable, safe, and attentive to requests may be on an
infinite horizon, assuming it is running forever. The task of delivering coffee to
a particular person may be an indefinite horizon problem. Planning for a fixed
number of hours may be a finite horizon problem.

Example 1.10 In a tutoring agent, for some subtasks, a finite horizon may be
appropriate, such as in a fixed teach, test, re-teach sequence. For other cases,
there may be an indefinite horizon where the system may not know at design
time how many steps it will take until the student has mastered some concept.
It may also be possible to model teaching as an ongoing process of learning and
testing with appropriate breaks, with no expectation of the system finishing.

1.5.3 Representation
The representation dimension concerns how the world is described.
The different ways the world could be are called states. A state of the world
specifies the agent’s internal state (its belief state) and the environment state.
At the simplest level, an agent can reason explicitly in terms of individually
identified states.

Example 1.11 A thermostat for a heater may have two belief states: off and
heating. The environment may have three states: cold, comfortable, and hot. There
are thus six states corresponding to the different combinations of belief and
environment states. These states may not fully describe the world, but they
are adequate to describe what a thermostat should do. The thermostat should
move to, or stay in, heating if the environment is cold and move to, or stay in,
off if the environment is hot. If the environment is comfortable, the thermostat
should stay in its current state. The thermostat agent turns or keeps the heater
on in the heating state and turns or keeps the heater off in the off state.

Instead of enumerating states, it is often easier to reason in terms of features

of the state or propositions that are true or false of the state. A state may be
described in terms of features, where a feature has a value in each state (see
Section 4.1, page 127).
1.5. Agent Design Space 25

Example 1.12 Consider designing an agent to diagnose electrical problems

in the home of Figure 1.6 (page 18). It may have features for the position of
each switch, the status of each switch (whether it is working okay, whether it
is shorted, or whether it is broken), and whether each light works. The feature
position s2 may be a feature that has value up when switch s2 is up and has
value down when the switch is down. The state of the home’s lighting may be
described in terms of values for each of these features. These features depend
on each other, but not in arbitrarily complex ways; for example, whether a light
is on may just depend on whether it is okay, whether the switch is turned on,
and whether there is electricity.

A proposition is a Boolean feature, which means that its value is either true
or false. Thirty propositions can encode 230 = 1, 073, 741, 824 states. It may be
easier to specify and reason with the thirty propositions than with more than a
billion states. Moreover, having a compact representation of the states indicates
understanding, because it means that an agent has captured some regularities
in the domain.

Example 1.13 Consider an agent that has to recognize digits. Suppose the
agent observes a binary image, a 28 × 28 grid of pixels, where each of the 282 =
784 grid points is either black or white. The action is to determine which of the
digits {0, . . . , 9} is shown in the image. There are 2784 different possible states
784
of the image, and so 102 different functions from the image state into the
characters {a, . . . , z}. You cannot represent such functions in terms of the state
space. Instead, handwriting recognition systems define features of the image,
such as line segments, and define the function from images to characters in
terms of these features. Modern implementations learn the features that are
useful; see Example 8.3 (page 336).

When describing a complex world, the features can depend on relations

and individuals. An individual is also called a thing, an object, or an entity. A
relation on a single individual is a property. There is a feature for each possible
relationship among the individuals.

Example 1.14 The agent that looks after a home in Example 1.12 could have
the lights and switches as individuals, and relations position and connected to.
Instead of the feature position s2 = up, it could use the relation position(s2 , up).
This relation enables the agent to reason about all switches or for an agent to
have general knowledge about switches that can be used when the agent en-
counters a switch.

Example 1.15 If an agent is enrolling students in courses, there could be a

feature that gives the grade of a student in a course, for every student–course
pair where the student took the course. There would be a passed feature for
every student–course pair, which depends on the grade feature for that pair. It
may be easier to reason in terms of individual students, courses, and grades,
and the relations grade and passed. By defining how passed depends on grade
26 1. Artificial Intelligence and Agents

once, the agent can apply the definition for each student and course. Moreover,
this can be done before the agent knows which individuals exist, and so before
it knows any of the features.
The two-argument relation passed, with 1000 students and 100 courses, can
represent 1000 ∗ 100 = 100, 000 propositions and so 2100,000 states.

By reasoning in terms of relations and individuals, an agent can reason

about whole classes of individuals without ever enumerating the features or
propositions, let alone the states. An agent may have to reason about infinite
sets of individuals, such as the set of all numbers or the set of all sentences. To
reason about an unbounded or infinite number of individuals, an agent cannot
reason in terms of states or features; it must reason at the relational level.
In the representation dimension, the agent reasons in terms of
• states
• features, or
• individuals and relations (often called relational representations).
Some of the frameworks will be developed in terms of states, some in terms of
features, and some in terms of individuals and relations.
Reasoning in terms of states is introduced in Chapter 3. Reasoning in terms
of features is introduced in Chapter 4. Relational reasoning is considered start-
ing from Chapter 15.

1.5.4 Computational Limits

Sometimes an agent can decide on its best action quickly enough for it to act.
Often there are computational resource limits that prevent an agent from car-
rying out the best action. That is, the agent may not be able to find the best
action quickly enough within its memory limitations to act while that action is
still the best thing to do. For example, it may not be much use to take 10 min-
utes to derive what was the best thing to do 10 minutes ago, when the agent
has to act now. Often, instead, an agent must trade off how long it takes to get
a solution with how good the solution is; it may be better to find a reasonable
solution quickly than to find a better solution later because the world will have
changed during the computation.
The computational limits dimension determines whether an agent has
• perfect rationality, where an agent reasons about the best action without
taking into account its limited computational resources, or
• bounded rationality, where an agent decides on the best action that it
can find given its computational limitations.
Computational resource limits include computation time, memory, and numer-
ical accuracy caused by computers not representing real numbers exactly.
An anytime algorithm is an algorithm where the solution quality improves
with time. In particular, it is one that can produce its current best solution at
1.5. Agent Design Space 27

any time, but given more time it could produce even better solutions. To ensure
that the quality does not decrease, the agent can store the best solution found
so far, and return that when asked for a solution. Although the solution quality
may increase with time, waiting to act has a cost; it may be better for an agent
to act before it has found what would be the best solution.

Example 1.16 The delivery robot cannot think for a long time about how to
avoid a person. There might be a best way to avoid the person and to achieve
its other goals, however it might take time to determine that optimal path, and
it might be better to act quickly and then recover from a non-optimal action. In
the simplest case, a robot could just stop if it encounters a person, but even that
is error prone as robots have momentum, so it cannot stop immediately and
people behind may run into it if it stops suddenly.

Example 1.17 Even a tutoring agent that can act at longer scales than a robot
sometimes has to act quickly. When a student has completed a task and wants
a new task, the agent needs to decide whether it should assign the student
the best task it has found so far, or compute for longer, trying to find an even
better task. As the student waits, they might become distracted, which might
be worse than giving them a non-optimal task. The computer can be planning
the next task when the student is working. Modern computers, as fast as they
may be, cannot find optimal solutions to difficult problems quickly.

Example 1.18 Figure 1.7 shows how the computation time of an anytime al-
gorithm can affect the solution quality. The agent has to carry out an action but
can do some computation to decide what to do. The absolute solution quality,
Value of Action

0 1 2 3 4 5
Time of Action

Figure 1.7: Solution quality as a function of time for an anytime algorithm. The
meaning is described in Example 1.18
28 1. Artificial Intelligence and Agents

had the action been carried out at time zero, shown as the dashed line at the
top, is improving as the agent takes time to reason. However, there is a penalty
associated with taking time to act. In this figure, the penalty, shown as the dot-
ted line at the bottom, is negative and proportional to the time taken before
the agent acts. These two values can be added to get the discounted quality,
the time-dependent value of computation; this is the solid line in the middle of
the graph. For the example of Figure 1.7 (page 27), an agent should compute
for about 2.5 time units, and then act, at which point the discounted quality
achieves its maximum value. If the computation lasts for longer than 4.3 time
units, the resulting discounted solution quality is worse than if the algorithm
outputs the initial guess it can produce with virtually no computation. It is typ-
ical that the solution quality improves in jumps; when the current best solution
changes, there is a jump in the quality. The penalty associated with waiting is
rarely a straight line; it is typically a function of deadlines, which may not be
known by the agent.

To take into account bounded rationality, an agent must decide whether it

should act or reason for longer. This is challenging because an agent typically
does not know how much better off it would be if it only spent a little bit more
time reasoning. Moreover, the time spent thinking about whether it should
reason may detract from actually reasoning about the domain.

1.5.5 Learning
In some cases, a designer of an agent may have a good model of the agent and
its environment. But often a designer does not have a good model, and so an
agent should use data from its past experiences and other sources to help it
decide what to do.
The learning dimension determines whether

• knowledge is given, or
• knowledge is learned (from prior knowledge and data or past experi-
ence).
Learning typically means finding the best model that fits the data. Some-
times this is as simple as tuning a fixed set of parameters, but it can also mean
choosing the best representation out of a class of representations. Learning is
a huge field in itself but does not stand in isolation from the rest of AI. There
are many issues beyond fitting data, including how to incorporate background
knowledge, what data to collect, how to represent the data and the resulting
representations, what learning biases are appropriate, and how the learned
knowledge can be used to affect how the agent acts.
Learning is considered in Chapters 7, 8, 10, 13, and 17.

Example 1.19 A robot has a great deal to learn, such as how slippery floors
are as a function of their shininess, where each person hangs out at different
1.5. Agent Design Space 29

parts of the day, when they will ask for coffee, and which actions result in the
highest rewards.
Modern vision systems are trained to learn good features (such as lines and
textures) on millions if not billions of images and videos. These features can
be used to recognize objects and for other tasks, even if there have been few
examples of the higher-level concepts. A robot might not have seen a baby
crawling on a highway, or a particular mug, but should be able to deal with
such situations.

Example 1.20 Learning is fundamental to diagnosis. It is through learning

and science that medical professionals understand the progression of diseases
and how well treatments work or do not work. Diagnosis is a challenging do-
main for learning, because all patients are different, and each individual doc-
tor’s experience is only with a few patients with any particular set of symp-
toms. Doctors also see a biased sample of the population; those who come to
see them usually have unusual or painful symptoms. Drugs are not given to
people randomly. You cannot learn the effect of treatment by observation alone,
but need a causal model of the causes and effects; see Chapter 11 for details
on building causal models. To overcome the limitations of learning from ob-
servations alone, drug companies spend billions of dollars doing randomized
controlled trials in order to learn the efficacy of drugs.

1.5.6 Uncertainty
An agent could assume there is no uncertainty, or it could take uncertainty in
the domain into consideration. Uncertainty is divided into two dimensions:
one for uncertainty from sensing and one for uncertainty about the effects of
actions.

Sensing Uncertainty
In some cases, an agent can observe the state of the world directly. For example,
in some board games or on a factory floor, an agent may know exactly the state
of the world. In many other cases, it may have some noisy perception of the
state and the best it can do is to have a probability distribution over the set
of possible states based on what it perceives. For example, given a patient’s
symptoms, a medical doctor may not actually know which disease a patient
has and may have only a probability distribution over the diseases the patient
may have.
The sensing uncertainty dimension concerns whether the agent can deter-
mine the state from the stimuli:

• Fully observable means the agent knows the state of the world from the
stimuli.
30 1. Artificial Intelligence and Agents

• Partially observable means the agent does not directly observe the state
of the world. This occurs when many possible states can result in the
same stimuli or when stimuli are misleading.
Assuming the world is fully observable is a common simplifying assumption
to keep reasoning tractable.

Example 1.21 The delivery robot does not know exactly where it is, or what
else there is, based on its limited sensors. Looking down a corridor does not
provide enough information to know where it is or who is behind the doors.
Knowing where it was a second ago will help determine where it is now, but
even robots can get lost. It may not know where the person who requested
coffee is. When it is introduced into a new environment, it may have much
more uncertainty.

Example 1.22 The tutoring agent cannot directly observe the knowledge of
the student. All it has is some sensing input, based on questions the student
asks or does not ask, facial expressions, distractedness, and test results. Even
test results are very noisy, as a mistake may be due to distraction or test anxiety
instead of lack of knowledge, and a correct answer might be due to a lucky
guess instead of real understanding. Sometimes students make mistakes in
testing situations they wouldn’t make at other times.

Example 1.23 A trading agent does not know all available options and their
availability, but must find out information that can become outdated quickly
(e.g., if a hotel becomes booked up). A travel agent does not know whether a
flight will be canceled or delayed, or whether the passenger’s luggage will be
lost. This uncertainty means that the agent must plan for the unanticipated.

Effect Uncertainty
A model of the dynamics of the world is a model of how the world changes as
a result of actions, including the case of how it changes if the action were to do
nothing. In some cases an agent knows the effects of its action. That is, given
a state and an action, the agent can accurately predict the state resulting from
carrying out that action in that state. For example, a software agent interacting
with the file system of a computer may be able to predict the effects of deleting
a file given the state of the file system. However, in many cases, it is difficult
to predict the effects of an action, and the best an agent can do is to have a
probability distribution over the effects. For example, a teacher may not know
the effects explaining a concept, even if the state of the students is known. At
the other extreme, if the teacher has no inkling of the effect of its actions, there
would be no reason to choose one action over another.
The dynamics in the effect uncertainty dimension can be
• deterministic when the state resulting from an action is determined by
an action and the prior state, or
1.5. Agent Design Space 31

• stochastic when there is a probability distribution over the resulting states.

Example 1.24 For the delivery robot, there can be uncertainty about the effects
of an action, both at the low level, say due to slippage of the wheels, or at the
high level because the agent might not know whether putting the coffee on a
person’s desk succeeded in delivering coffee to the person. This may depend
on the individual preferences of users.

Example 1.25 Even a trading agent does not know the effect of putting in
a trade order, such as booking a flight or a hotel room. These can become un-
available at very short notice (consider two trading agents trying to book the
same room at the same time), or the price can vary.

The effect dimension only makes sense when the world is fully observable.
If the world is partially observable, a stochastic system can be modeled as a
deterministic system where the effect of an action depends on unobserved fea-
tures. It is a separate dimension because many of the frameworks developed
are for the fully observable, stochastic action case.
Planning with deterministic actions is considered in Chapter 6. Planning
with stochastic actions is considered in Chapter 12.

1.5.7 Preference
Agents normally act to have better outcomes. The only reason to choose one
action over another is because the preferred action leads to more desirable out-
comes.
An agent may have a simple goal, which is a proposition the agent wants
to be true in a final state. For example, the goal of getting Sam coffee means
the agent wants to reach a state where Sam has coffee. Other agents may have
more complex preferences. For example, a medical doctor may be expected to
take into account suffering, life expectancy, quality of life, monetary costs (for
the patient, the doctor, and society), and the ability to justify decisions in case
of a lawsuit. The doctor must trade these considerations off when they conflict,
as they invariably do.
The preference dimension considers whether the agent has goals or richer
preferences:
• A goal is either an achievement goal, which is a proposition to be true in
some final state, or a maintenance goal, a proposition that must be true
in all visited states. For example, the goals for a robot may be to deliver
a cup of coffee and a banana to Sam, and not to make a mess or hurt
anyone.
• Complex preferences involve trade-offs among the desirability of vari-
ous outcomes, perhaps at different times. An ordinal preference is where
only the ordering of the preferences is important. A cardinal preference
is where the magnitude of the values matters. For example, an ordinal
32 1. Artificial Intelligence and Agents

preference may be that Sam prefers cappuccino over black coffee and
prefers black coffee over tea. A cardinal preference may give a trade-
off between the wait time and the type of beverage, and a mess versus
taste trade-off, where Sam is prepared to put up with more mess in the
preparation of the coffee if the taste of the coffee is exceptionally good.

Example 1.26 The delivery robot could be given goals, such as “deliver coffee
to Chris and make sure you always have power.” A more complex goal may be
to “clean up the lab, and put everything where it belongs”, which can only be
achieved to some degree. There can be complex preferences, such as “deliver
mail when it arrives and service coffee requests as soon as possible, but it is
more important to deliver messages marked as urgent, and Chris needs her
coffee quickly when she asks for it.”

Example 1.27 For the diagnostic assistant, the goal may be as simple as “fix
what is wrong,” but often there are complex trade-offs involving costs, pain,
life expectancy, and preferences related to the uncertainty that the diagnosis is
correct and uncertainty as to efficacy and side-effects of the treatment. There is
also a problem of whose preferences are to be taken into account; the patient,
the doctor, the payer, and society may all have different preferences that must
be reconciled.

Example 1.28 Although it may be possible for the tutoring agent to have
a simple goal such, as to teach some particular concept, it is more likely that
complex preferences must be taken into account. One reason is that, with un-
certainty, there may be no way to guarantee that the student knows the concept
being taught; any method that tries to maximize the probability that the stu-
dent knows a concept will be very annoying, because it will repeatedly teach
and test if there is a slight chance that the student’s errors are due to misunder-
standing as opposed to fatigue or boredom. More complex preferences would
enable a trade-off among fully teaching a concept, boring the student, the time
taken, and the amount of retesting. The student may also have a preference
for a teaching style that could be taken into account. The student, the teacher,
the parents, and future employers may have different preferences. The student
may have incompatible preferences, for example, to not work hard and to get
a good mark. If the teacher is optimizing student evaluations, it might both
allow the student to not work hard, and also give good marks. But that might
undermine the goal of the student actually learning something.

Example 1.29 For a trading agent, preferences of users are typically in terms
of functionality, not components. For example, typical computer buyers have
no idea of what hardware to buy, but they know what functionality they want
and they also want the flexibility to be able to use new software features that
might not even exist yet. Similarly, in a travel domain, what activities a user
wants may depend on the location. Users also may want the ability to partic-
ipate in a local custom at their destination, even though they may not know
what those customs are. Even a simple path-finding algorithm, such as Google
1.5. Agent Design Space 33

Maps, which, at the time of writing, assumes all users’ preferences are to min-
imize travel time, could take into account each individual user’s preferences
for diverse views or avoiding going too close to where some particular relative
lives.

Goals are considered in Chapters 3 and 6. Complex preferences are consid-

ered in Chapter 12, and the following chapters.

1.5.8 Number of Agents

An agent reasoning about what it should do in an environment where it is the
only agent is difficult enough. However, reasoning about what to do when
there are other agents who are also reasoning is much more difficult. An agent
in a multiagent setting may need to reason strategically about other agents;
the other agents may act to trick or manipulate the agent or may be available
to cooperate with the agent. With multiple agents, it is often optimal to act
randomly because other agents can exploit deterministic strategies. Even when
the agents are cooperating and have a common goal, the task of coordination
and communication makes multiagent reasoning more challenging. However,
many domains contain multiple agents and ignoring other agents’ strategic
reasoning is not always the best way for an agent to reason.
Taking the point of view of a single agent, the number of agents dimension
considers whether the agent explicitly considers other agents:
• Single agent reasoning means the agent assumes that there are no other
agents in the environment or that all other agents are part of nature, and
so are non-purposive. This is a reasonable assumption if there are no
other agents or if the other agents are not going to change what they do
based on the agent’s action.
• Adversarial reasoning considers another agent, where when one agent
wins, the other loses. This is sometimes called a two-player zero-sum
game, as the payoffs for the agents (e.g., +1 for a win and −1 for a loss)
sum to zero. This is a simpler case than allowing for arbitrary agents as
there is no need to cooperate or otherwise coordinate.
• Multiple agent reasoning (or multiagent reasoning) means the agent
takes the reasoning of other agents into account. This occurs when there
are other intelligent agents whose goals or preferences depend, in part,
on what the agent does or if the agent must communicate with other
agents. Agents may need to cooperate because coordinated actions can
result in outcomes that are better for all agents than each agent consider-
ing the other agents as part of nature.
Reasoning in the presence of other agents is much more difficult if the
agents can act simultaneously or if the environment is only partially observ-
able. Multiagent systems are considered in Chapter 14. Note that the adversar-
ial case is separate as there are some methods that only work for that case.
34 1. Artificial Intelligence and Agents

Example 1.30 There can be multiple delivery robots, which can coordinate to
deliver coffee and parcels more efficiently. They can compete for power outlets
or for space to move. Only one might be able to go closest to the wall when
turning a corner. There may also be children out to trick the robot, or pets that
get in the way.
When automated vehicles have to go on a highway, it may be much more
efficient and safer for them to travel in a coordinated manner, say one cen-
timeter apart in a convoy, than to travel three vehicle lengths apart. It is more
efficient because they can reduce wind drag, and many more vehicles can fit on
a highway. It is safer because the difference in speeds is small; if one vehicle
slams on its brakes or has engine problems, the car that might crash into the
back is going approximately the same speed.

Example 1.31 A trading agent has to reason about other agents. In commerce,
prices are governed by supply and demand; this means that it is important to
reason about the other competing agents. This happens particularly in a world
where many items are sold by auction. Such reasoning becomes particularly
difficult when there are items that must complement each other, such as flights
and hotel bookings, and items that can substitute for each other, such as bus
transport or taxis. You don’t want to book the flights if there is no accommoda-
tion, or book accommodation if there are no flights.

1.5.9 Interactivity
In deciding what an agent will do, there are three aspects of computation that
must be distinguished: (1) the design-time computation that goes into the de-
sign of the agent, carried out by the designer of the agent, not the agent itself;
(2) the computation that the agent can do before it observes the world and
needs to act; and (3) the computation that is done by the agent as it is acting.
The interactivity dimension considers whether the agent does

• only offline reasoning, where offline reasoning is the computation done

by the agent before it has to act, and can include compilation, learning
or finding solutions from every state the agent could find itself in; under
this assumption, the agent can carry out simple fixed-cost computation
while acting, sometimes even just looking up the action in a table

• significant online reasoning, where online computation is the computa-

tion done by the agent between observing the environment and acting.

An agent acting in the world usually does not have the luxury of having
the world wait for it to consider the best option. However, offline reasoning,
where the agent can reason about the best thing to do before having to act,
is often a simplifying assumption. Online reasoning can include long-range
strategic reasoning as well as determining how to react in a timely manner to
the environment; see Chapter 2.
1.5. Agent Design Space 35

Example 1.32 A delivery robot may be able to compute a plan for its day
offline, but then it needs to be able to adapt to changes, for example, when
someone wants coffee early or something urgent needs to be delivered. It can-
not plan for who it will meet and need to avoid in the corridors. It either needs
to be able to anticipate and plan for all possible eventualities, or it needs to
reason online when it finds something unexpected.

Example 1.33 A tutoring agent can determine the general outline of what
should be taught offline. But then it needs to be able to react to unexpected
behavior online when it occurs. It is difficult to be able to anticipate all eventu-
alities, and might be easier to deal with them online when it encounters them.

1.5.10 Interaction of the Dimensions

Figure 1.8 summarizes the dimensions of complexity.
In terms of the dimensions of complexity, the simplest case for the robot is
a flat system, represented in terms of states, with no uncertainty, with achieve-
ment goals, with no other agents, with given knowledge, and with perfect ra-
tionality. In this case, with an indefinite stage planning horizon, the problem
of deciding what to do is reduced to the problem of finding a path in a graph
of states. This is explored in Chapter 3.
In going beyond the simplest cases, these dimensions cannot be considered
independently because they interact in complex ways. Consider the following
examples of the interactions.
The representation dimension interacts with the modularity dimension in
that some modules in a hierarchy may be simple enough to reason in terms of
a finite set of states, whereas other levels of abstraction may require reasoning
about individuals and relations. For example, in a delivery robot, a module

Dimension Values
Modularity flat, modular, hierarchical
Planning horizon non-planning, finite stage,
indefinite stage, infinite stage
Representation states, features, relations
Computational limits perfect rationality, bounded rationality
Learning knowledge is given, knowledge is learned
Sensing uncertainty fully observable, partially observable
Effect uncertainty deterministic, stochastic
Preference goals, complex preferences
Number of agents single agent, adversaries, multiple agents
Interactivity offline, online

Figure 1.8: Dimensions of complexity

36 1. Artificial Intelligence and Agents

that maintains balance may only have a few states. A module that must pri-
oritize the delivery of multiple parcels to multiple people may have to reason
about multiple individuals (e.g., people, packages, and rooms) and the rela-
tions between them. At a higher level, a module that reasons about the activity
over the day may only require a few states to cover the different phases of the
day (e.g., there might be three states of the robot: busy, available for requests,
and recharging).
The planning horizon interacts with the modularity dimension. For exam-
ple, at a high level, a dog may be getting an immediate reward when it comes
and gets a treat. At the level of deciding where to place its paws, there may be
a long time until it gets the reward, and so at this level it may have to plan for
an indefinite stage.
Sensing uncertainty probably has the greatest impact on the complexity of
reasoning. It is much easier for an agent to reason when it knows the state of
the world than when it does not.
The uncertainty dimensions interact with the modularity dimension: at one
level in a hierarchy, an action may be deterministic, whereas at another level, it
may be stochastic. As an example, consider the result of flying to a particular
overseas destination with a companion you are trying to impress. At one level
you may know which country you are in. At a lower level, you may be quite
lost and not know where you are on a map of the airport. At an even lower
level responsible for maintaining balance, you may know where you are: you
are standing on the ground. At the highest level, you may be very unsure
whether you have impressed your companion.
Preference models interact with uncertainty because an agent needs to trade
off between satisfying a very desirable goal with low probability or a less de-
sirable goal with a higher probability. This issue is explored in Section 12.1
(page 518).
Multiple agents can also be used for modularity; one way to design a sin-
gle agent is to build multiple interacting agents that share a common goal of
making the higher-level agent act intelligently. Some researchers, such as Min-
sky [1986], argue that intelligence is an emergent feature from a “society” of
unintelligent agents.
Learning is often cast in terms of learning with features – determining which
feature values best predict the value of another feature. However, learning can
also be carried out with individuals and relations. Learning with hierarchies,
sometimes called deep learning, has enabled the learning of more complex
concepts. Much work has been done on learning in partially observable do-
mains, and learning with multiple agents. Each of these is challenging in its
own right without considering interactions with multiple dimensions.
The interactivity dimension interacts with the planning horizon dimension
in that when the agent is reasoning and acting online, it also needs to reason
about the long-term horizon. The interactivity dimension also interacts with
the computational limits; even if an agent is reasoning offline, it cannot take
hundreds of years to compute an answer. However, when it has to reason
1.6. Designing Agents 37

about what to do in, say, 1/10 of a second, it needs to be concerned about the
time taken to reason, and the trade-off between thinking and acting.
Two of these dimensions, modularity and bounded rationality, promise to
make reasoning more efficient. Although they make the formalism more com-
plicated, breaking the system into smaller components, and making the ap-
proximations needed to act in a timely fashion and within memory limitations,
should help build more complex systems.

1.6 Designing Agents

Artificial agents are designed for particular tasks. Researchers have not yet
got to the stage of designing an intelligent agent for the task of surviving and
reproducing in a complex natural environment.

1.6.1 Simplifying Environments and Simplifying Agents

It is important to distinguish between the knowledge in the mind of an agent
and the knowledge in the mind of the designer of the agent. Consider the
extreme cases:

• At one extreme is a highly specialized agent that works well in the envi-
ronment for which it was designed, but is helpless outside of this niche.
The designer may have done considerable work in building the agent,
but the agent can be extremely specialized to operate well. An example
is a traditional thermostat. It may be difficult to design a thermostat so
that it turns on and off at exactly the right temperatures, but the ther-
mostat itself does not have to do much computation. Another example
is a car-painting robot that always paints the same parts in an automo-
bile factory. There may be much design time or offline computation to
get it to work perfectly, but the painting robot can paint parts with little
online computation; it senses that there is a part in position, but then it
carries out its predefined actions. These very specialized agents do not
adapt well to different environments or to changing goals. The painting
robot would not notice if a different sort of part were present and, even
if it did, it would not know what to do with it. It would have to be re-
designed or reprogrammed to paint different parts or to change into a
sanding machine or a dog-washing machine.
• At the other extreme is a very flexible agent that can survive in arbitrary
environments and accept new tasks at run time. Simple biological agents
such as insects can adapt to complex changing environments, but they
cannot carry out arbitrary tasks. Designing an agent that can adapt to
complex environments and changing goals is a major challenge. The
agent will know much more about the particulars of a situation than the
designer. Even biology has not produced many such agents. Humans
38 1. Artificial Intelligence and Agents

may be the only extant example, but even humans need time to adapt to
new environments.
Even if the flexible agent is our ultimate dream, researchers have to reach this
goal via more mundane goals. Rather than building a universal agent, which
can adapt to any environment and solve any task, researchers have been re-
stricted to particular agents for particular environmental niches. The designer
can exploit the structure of the particular niche and the agent does not have to
reason about other possibilities.
Two broad strategies have been pursued in building agents:
• The first is to simplify environments and build complex reasoning sys-
tems for these simple environments. For example, factory robots can do
sophisticated tasks in the engineered environment of a factory, but they
may be hopeless in a natural environment. Much of the complexity of
the task can be reduced by simplifying the environment. This is also im-
portant for building practical systems because many environments can
be engineered to make them simpler for agents.
• The second strategy is to build simple agents in natural environments.
This is inspired by seeing how insects can survive in complex environ-
ments even though they have very limited reasoning abilities. Modern
language systems can predict the probability of the next word in an arbi-
trary text, but this does not mean they can be used for decision making.
Researchers then make the agents have more reasoning abilities as their
tasks become more complicated.
One of the advantages of simplifying environments is that it may enable us to
prove properties of agents or to optimize agents for particular situations. Prov-
ing properties or optimization typically requires a model of the agent and its
environment. The agent may do a little or a lot of reasoning, but an observer or
designer of the agent may be able to reason about the agent and the environ-
ment. For example, the designer may be able to prove whether the agent can
achieve a goal, whether it can avoid getting into situations that may be bad for
the agent (safety), whether it can avoid getting stuck somewhere (liveness),
or whether it will eventually get around to each of the things it should do
(fairness). Of course, the proof is only as good as the model.
The advantage of building agents for complex environments is that these
are the types of environments in which humans live and where agents could
be useful.
Even natural environments can be abstracted into simpler environments.
For example, for an autonomous car driving on public roads the environment
can be conceptually simplified so that everything is either a road, another car,
or something to be avoided. Although autonomous cars have sophisticated
sensors, they only have limited actions available, namely steering, accelerating,
and braking.
Fortunately, research along both lines, and between these extremes, is being
carried out. In the first case, researchers start with simple environments and
1.6. Designing Agents 39

make the environments more complex. In the second case, researchers increase
the complexity of the behaviors that the agents can carry out.

1.6.2 Tasks
One way that AI representations differ from computer programs in traditional
languages is that an AI representation typically specifies what needs to be com-
puted, not how it is to be computed. You might specify that the agent should
find the most likely disease a patient has, or specify that a robot should get
coffee, but not give detailed instructions on how to do these things. Much AI
reasoning involves searching through the space of possibilities to determine
how to complete a task.
Typically, a task is only given informally, such as “deliver parcels promptly
when they arrive” or “fix whatever is wrong with the electrical system of the
home.”
The general framework for solving tasks by computer is given in Figure 1.9.
To solve a task, the designer of a system must:

• determine what constitutes a solution

• represent the task in a way a computer can reason about
• use the computer to compute an output; either answers presented to a
user or actions to be carried out in the environment
• interpret the output as a solution to the task.
In AI, knowledge is long-term representation of a domain whereas belief is
about the immediate environment, for example where the agent is and where
other object are. In philosophy, knowledge is usually defined as justified true
belief, but in AI the term is used more generally to be any relatively stable infor-
mation, as opposed to belief, which is more transitory information. The reason
for this terminology is that it is difficult for an agent to determine truth, and
“justified” is subjective. Knowledge in AI can be represented in terms of logic,

solve
task solution

represent interpret informal

formal
compute
representation output

Figure 1.9: The role of representations in solving tasks

40 1. Artificial Intelligence and Agents

neural networks, or probabilistic models, but belief is typically represented as

a distribution over the states.
A representation of some piece of knowledge is the particular data struc-
tures used to encode the knowledge so it can be reasoned with.
The form of representation – what is represented – is a compromise among
many competing objectives. A representation should be:
• rich enough to express the knowledge needed to solve the task
• as close to a natural specification of the task as possible
• amenable to efficient computation
• able to be acquired from people, data, and past experiences.
Being as close to a natural specification of the task as possible means should
be compact, natural, and maintainable. It should be easy to see the relationship
between the representation and the domain being represented, so that it is easy
to determine whether the knowledge represented is correct; a small change
in the task should result in a small change in the representation of the task.
There is an active debate about how much of the internal structure of reasoning
should be explainable; the field of explainable AI is about how to make more
aspects of the decision making amenable to being explained to a person.
Efficient computation enables the agent to act quickly enough to be effec-
tive. A tractable algorithm is one with reasonable asymptotic complexity, of-
ten meaning the computation time is polynomial in the input size (page 95),
however often linear complexity is too slow. To ensure this, representations
exploit features of the task for computational gain and trade off accuracy and
computation time.
Many different representation languages have been designed. Many of
these start with some of these objectives and are then expanded to include
the other objectives. For example, some are designed for learning, perhaps
inspired by neurons, and then expanded to allow richer task-solving and in-
ference abilities. Some representation languages are designed with expressive-
ness in mind, and then inference and learning are added on. Some language
designers focus on tractability and enhance richness, naturalness, and the abil-
ity to be acquired.

1.6.3 Defining a Solution

Given an informal description of a task, before even considering a computer,
an agent designer should determine what would constitute a solution. This
question arises not only in AI but in any software design. Much of software
engineering involves refining the specification of the task.
Tasks are typically not well specified. Not only is there usually much left
unspecified, but also the unspecified parts cannot be filled in arbitrarily. For
example, if a user asks a trading agent to find out all the information about
resorts that may have unsanitary food practices, they do not want the agent to
return all the information about all resorts, even though all of the information
1.6. Designing Agents 41

requested is in the result. However, if the trading agent does not have complete
knowledge about the resorts, returning all of the information may be the only
way for it to guarantee that all of the requested information is there. Similarly,
one does not want a delivery robot, when asked to take all of the trash to the
garbage can, to take everything to the garbage can, even though this may be
the only way to guarantee that all of the trash has been taken. Much work in
AI is motivated by commonsense reasoning; the computer should be able to
reach commonsense conclusions about the unstated assumptions.
Given a well-defined task, the next issue is whether it matters if the answer
returned is incorrect or incomplete. For example, if the specification asks for
all instances, does it matter if some are missing? Does it matter if there are
some extra instances? Often a person does not want just any solution but the
best solution according to some criteria. There are four common classes of
solutions:

Optimal solution An optimal solution to a task is one that is the best solution
according to some measure of solution quality. This measure is typically
specified as an ordinal, where only the order matters. In some situations
a cardinal measure, where the relative magnitudes also matter, is used.
For example, a robot may need to take out as much trash as possible;
the more trash it can take out, the better. In a more complex example,
you may want the delivery robot to take as much of the trash as possi-
ble to the garbage can, minimizing the distance traveled, and explicitly
specify a trade-off between the effort required and the proportion of the
trash taken out. There are also costs associated with making mistakes
and throwing out items that are not trash. It may be better to miss some
trash than to waste too much time. One general measure of desirability
that interacts with probability is utility (page 518).
Satisficing solution Often an agent does not need the best solution to a task
but just needs some solution. A satisficing solution is one that is good
enough according to some description of which solutions are adequate.
For example, a person may tell a robot that it must take all of the trash
out, or tell it to take out three items of trash.
Approximately optimal solution One of the advantages of a cardinal mea-
sure of success is that it allows for approximations. An approximately
optimal solution is one whose measure of quality is close to the best that
could theoretically be obtained. Typically, agents do not need optimal
solutions to tasks; they only need to get close enough. For example, the
robot may not need to travel the optimal distance to take out the trash
but may only need to be within, say, 10% of the optimal distance. Some
approximation algorithms guarantee that a solution is within some range
of optimal, but for some algorithms no guarantees are available.
For some tasks, it is much easier computationally to get an approx-
imately optimal solution than to get an optimal solution. However, for
other tasks, it is just as difficult to find an approximately optimal solution
42 1. Artificial Intelligence and Agents

that is guaranteed to be within some bounds of optimal as it is to find an

optimal solution.
Probable solution A probable solution is one that, even though it may not
actually be a solution to the task, is likely to be a solution. This is one way
to approximate, in a precise manner, a satisficing solution. For example,
in the case where the delivery robot could drop the trash or fail to pick
it up when it attempts to, you may need the robot to be 80% sure that
it has picked up three items of trash. Often you want to distinguish a
false-positive error (positive answers that are not correct) from a false-
negative error (negative answers that are correct). Some applications are
much more tolerant of one of these types of errors than the other.

These categories are not exclusive. A form of learning known as probably

approximately correct (PAC) learning considers probably learning an approx-
imately correct concept.

1.6.4 Representations
Once you have some requirements on the nature of a solution, you must repre-
sent the task so a computer can solve it.
Computers and human minds are examples of physical symbol systems.
A symbol is a meaningful pattern that can be manipulated. Examples of sym-
bols are written words, sentences, gestures, marks on paper, or sequences of
bits. A symbol system creates, copies, modifies, and destroys symbols. Essen-
tially, a symbol is one of the patterns manipulated as a unit by a symbol system.
The term “physical” is used, because symbols in a physical symbol system are
physical objects that are part of the real world, even though they may be inter-
nal to computers and brains. They may also need to physically affect action or
motor control.
The physical symbol system hypothesis of Newell and Simon [1976] is
that:

A physical symbol system has the necessary and sufficient means

for general intelligent action.

This is a strong hypothesis. It means that any intelligent agent is necessarily a

physical symbol system. It also means that a physical symbol system is all that
is needed for intelligent action; there is no magic or as-yet-to-be-discovered
quantum phenomenon required. It does not imply that a physical symbol sys-
tem does not need a body to sense and act in the world.
One aspect of this hypothesis is particularly controversial, namely whether
symbols are needed at all levels. For example, consider recognizing a “cat” in
a picture. At the top level is the symbol for a cat. At the bottom level are pixels
from a camera. There are many intermediate levels that, for example, combine
pixels to form lines and textures. These intermediate features are learned from
1.6. Designing Agents 43

data, and are not learned with the constraint that they are interpretable. Al-
though some people have tried to interpret them, it is reasonable to say that
these are not symbols. However, at a high level, they are either trained to be
symbols (e.g., by learning a mapping between pixels and symbols, such as cat)
or can be interpreted as symbols.
An agent can use a physical symbol system to model the world. A model
of a world is a representation of an agent’s beliefs about what is true in the
world or how the world changes. The world does not have to be modeled at
the most detailed level to be useful. All models are abstractions; they represent
only part of the world and leave out many of the details. An agent can have
a very simplistic model of the world, or it can have a very detailed model of
the world. The level of abstraction provides a partial ordering of abstraction.
A lower-level abstraction includes more details than a higher-level abstraction.
An agent can have multiple, even contradictory, models of the world. Models
are judged not by whether they are correct, but by whether they are useful.

Example 1.34 A delivery robot can model the environment at a high level of
abstraction in terms of rooms, corridors, doors, and obstacles, ignoring dis-
tances, its size, the steering angles needed, the slippage of the wheels, the
weight of parcels, the details of obstacles, the political situation in Canada, and
virtually everything else. The robot could model the environment at lower lev-
els of abstraction by taking some of these details into account. Some of these
details may be irrelevant for the successful implementation of the robot, but
some may be crucial for the robot to succeed. For example, in some situations
the size of the robot and the steering angles may be crucial for not getting stuck
around a particular corner. In other situations, if the robot stays close to the
center of the corridor, it may not need to model its width or the steering angles.

Choosing an appropriate level of abstraction is difficult for the following

reasons:
• A high-level description is easier for a human to specify and understand.
• A low-level description can be more accurate and more predictive. Often,
high-level descriptions abstract away details that may be important for
actually solving the task.
• The lower the level, the more difficult it is to reason with. This is because
a solution at a lower level of detail involves more steps and many more
possible courses of action exist from which to choose.
• An agent may not know the information needed for a low-level descrip-
tion. For example, the delivery robot may not know what obstacles it will
encounter or how slippery the floor will be at the time that it must decide
what to do.
It is often a good idea to model an environment at multiple levels of abstrac-
tion. This issue is discussed further in Section 2.2 (page 58).
Biological systems, and computers, can be described at multiple levels of
abstraction. At successively lower levels of animals are the neuronal level,
44 1. Artificial Intelligence and Agents

the biochemical level (what chemicals and what electrical potentials are be-
ing transmitted), the chemical level (what chemical reactions are being carried
out), and the level of physics (in terms of forces on atoms and quantum phe-
nomena). What levels above the neuronal level are needed to account for intel-
ligence is still an open question. These levels of description are echoed in the
hierarchical structure of science itself, where scientists are divided into physi-
cists, chemists, biologists, psychologists, anthropologists, and so on. Although
no level of description is more important than any other, it is plausible that you
do not have to emulate every level of a human to build an AI agent but rather
you can emulate the higher levels and build them on the foundation of modern
computers. This conjecture is part of what AI studies.
The following are two levels that seem to be common to both biological and
computational entities:
• The knowledge level is the level of abstraction that considers what an
agent knows and believes and what its goals are. The knowledge level
considers what an agent knows, but not how it reasons. For example, the
delivery agent’s behavior can be described in terms of whether it knows
that a parcel has arrived or not and whether it knows where a particular
person is or not. Both human and robotic agents are describable at the
knowledge level. At this level, you do not specify how the solution will
be computed or even which of the many possible strategies available to
the agent will be used.
• The symbol level is a level of description of an agent in terms of the rea-
soning it does. To implement the knowledge level, an agent manipulates
symbols to produce answers. Many cognitive science experiments are
designed to determine what symbol manipulation occurs during reason-
ing. Whereas the knowledge level is about what the agent believes about
the external world and what its goals are in terms of the outside world,
the symbol level is about what goes on inside an agent to reason about
the external world.

1.7 Social Impact

AI systems are now widely deployed in society. Individuals, corporations,
governments, and other organizations are using AI for applications as var-
ied as voice dictation, text synthesis, text-to-video generation, movie recom-
mendations, personal finance, chatbots, credit scoring, screening employment
applications, social media propagation and monitoring, face recognition, semi-
autonomous cars, and warehouse automation. Many of these systems can be
broadly beneficial. However, there are often adverse impacts on people in
racialized populations and underserved communities, and on election results
and vaccination campaigns.
There are significant ethical and social impacts of AI systems, leading to
demands for human-centered AI that is explainable, transparent, and trust-
1.8. Overview of the Book 45

worthy. The inputs to an AI agent include the goals and preferences of the
agent, but it is not clear whose preferences they are or should be.
Each chapter concludes with a social impact section discussing issues di-
rectly relevant to that chapter’s topics. The social impact sections are of two
types, sometimes containing both:

• broader impacts of AI, which includes intended or unintended down-

stream consequences of upstream decisions on the design of the AI sys-
tem or on the choice of data

• use cases about user-facing applications of AI that have had an impact on

society or science, either positive or negative.

Chapter 18 on the social impact of AI considers the effects of AI on the

digital economy, work and automation, transportation and sustainability. It
highlights the roles of human-centered AI, values, bias, ethics, certification,
and regulation.

1.8 Overview of the Book

The rest of the book explores the design space defined by the dimensions of
complexity. It considers each dimension separately, where this can be done
sensibly.
Part I considers the big view of agents as a coherent vision of AI.
Chapter 2 analyzes what is inside the black box of Figure 1.4 (page 15) and
discusses the modular and hierarchical decomposition of intelligent agents.
Part II considers the case of no uncertainty, which is a useful abstraction of
many domains.
Chapter 3 considers the simplest case of determining what to do in the case
of a single agent that reasons with explicit states, no uncertainty, and has goals
to be achieved, but with an indefinite horizon. In this case, the task of solving
the goal can be abstracted to searching for a path in a graph. It is shown how
extra knowledge of the domain can help the search.
Chapters 4 and 5 show how to exploit features. In particular, Chapter 4
considers how to find possible states given constraints on the assignments of
values to features represented as variables. Chapter 5 presents reasoning with
propositions in various forms.
Chapter 6 considers the task of planning, in particular determining se-
quences of actions to solve a goal in deterministic domains.
Part III considers learning and reasoning with uncertainty. In particular, it
considers sensing uncertainty and effect uncertainty.
Chapter 7 shows how an agent can learn from past experiences and data.
It covers the most common case of learning, namely supervised learning with
features, where a function from input features into target features is learned
46 1. Artificial Intelligence and Agents

from observational data. Chapter 8 studies neural networks and deep learning
and how features themselves can be learned from sensory observation.
Chapter 9 shows how to reason with uncertainty, in particular with proba-
bility and graphical models of independence. Chapter 10 introduces learning
with uncertainty. Chapter 11 shows how to model causality and learn the ef-
fects of interventions (which cannot be learned from observation alone).
Part IV considers planning and acting with uncertainty.
Chapter 12 considers the task of planning with uncertainty. Chapter 13
deals with reinforcement learning, where agents learn what to do. Chapter 14
expands planning to deal with issues arising from multiple agents.
Part V extends the state and feature-based representations to deal with re-
lational representations, in terms of relations and individuals.
Chapter 15 shows how to reason in terms of individuals and relations.
Chapter 16 discusses how to enable semantic interoperability using knowledge
graphs and ontologies. Chapter 17 shows how reasoning about individuals
and relations can be combined with learning and probabilistic reasoning.
Part VI steps back from the details and gives the big picture.
In Chapter 18 on the social impact of AI, further ethical and social concerns
are addressed, by considering various questions, such as: What are the effects,
benefits, costs, and risks of deployed AI systems for society? What are the
ethical, equity, and regulatory considerations involved in building intelligent
agents? How can you ensure that AI systems are fair, transparent, explainable,
and trustworthy? How can AI systems be human-centered? What is the impact
on sustainability?
Chapter 19 reviews the design space of AI and shows how the material pre-
sented can fit into that design space. It also considers some likely and possible
future scenarios for the development of AI science and technology.

1.9 Review
The following are the main points you should have learned from this chapter:
• Artificial intelligence is the study of computational agents that act intel-
ligently.
• An agent acts in an environment and only has access to its abilities, its
prior knowledge, its history of stimuli, and its goals and preferences.
• A physical symbol system manipulates symbols to determine what to do.
• A designer of an intelligent agent should be concerned about modularity,
how to describe the world, how far ahead to plan, uncertainty in both
perception and the effects of actions, the structure of goals or preferences,
other agents, how to learn from experience, how the agent can reason
while interacting with the environment, and the fact that all real agents
have limited computational resources.
• To solve a task by computer, the computer must have an effective repre-
sentation with which to reason.
1.10. References and Further Reading 47

• To know when it has solved a task, an agent must have a definition of

what constitutes an adequate solution, such as whether it has to be op-
timal, approximately optimal, or almost always optimal, or whether a
satisficing solution is adequate.
• In choosing a representation, an agent designer should find a representa-
tion that is as close as possible to the task, so that it is easy to determine
what is represented and so it can be checked for correctness and be able
to be maintained. Often, users want an explanation of why they should
believe the answer.
• The social impacts, both beneficial and harmful, of pervasive AI applica-
tions are significant, leading to calls for ethical and human-centered AI,
certification and regulation.

1.10 References and Further Reading

The ideas in this chapter have been derived from many sources. Here, we try to
acknowledge those that are explicitly attributable to particular authors. Most
of the other ideas are part of AI folklore; trying to attribute them to anyone
would be impossible.
Levesque [2012] provides an accessible account of how thinking can be
seen in terms of computation. Haugeland [1997] contains a good collection
of articles on the philosophy behind artificial intelligence, including that clas-
sic paper of Turing [1950] that proposes the Turing test. Grosz [2012] and Co-
hen [2005] discuss the Turing test from a more recent perspective. Winograd
schemas are described by Levesque [2014]. Srivastava et al. [2022] provide a
Beyond the Imitation Game benchmark (BIG-bench) consisting of 204 tasks de-
signed to challenge modern learning systems. Grosz [2018] discusses research
on what it takes to implement dialog, not just answering one-off questions.
Zador et al. [2023] discuss an embodied Turing test, and the role of neuro-
science in AI.
Nilsson [2010] and Buchanan [2005] provide accessible histories of AI. Chris-
ley and Begeer [2000] present many classic papers on AI. Jordan [2019] and the
associated commentaries discuss intelligence augmentation.
For discussions on the foundations of AI and the breadth of research in
AI, see Kirsh [1991a], Bobrow [1993], and the papers in the corresponding vol-
umes, as well as Schank [1990] and Simon [1995]. The importance of knowl-
edge in AI is discussed in Lenat and Feigenbaum [1991], Sowa [2000], Dar-
wiche [2018], and Brachman and Levesque [2022b].
The physical symbol system hypothesis was posited by Newell and Simon
[1976]. Simon [1996] discusses the role of symbol systems in a multidisciplinary
context. The distinctions between real, synthetic, and artificial intelligence are
discussed by Haugeland [1985], who also provides useful introductory mate-
rial on interpreted, automatic formal symbol systems and the Church–Turing
thesis. Brooks [1990] and Winograd [1990] critique the symbol system hy-
48 1. Artificial Intelligence and Agents

pothesis. Nilsson [2007] evaluates the hypothesis in terms of such criticisms.

Shoham [2016] and Marcus and Davis [2019] argue for the importance of sym-
bolic knowledge representation in modern applications.
The use of anytime algorithms is due to Horvitz [1989] and Boddy and
Dean [1994]. See Dean and Wellman [1991], Zilberstein [1996], and Russell
[1997] for introductions to bounded rationality.
For overviews of cognitive science and the role that AI and other disciplines
play in that field, see Gardner [1985], Posner [1989], and Stillings et al. [1987].
Conati et al. [2002] describe a tutoring agent for elementary physics. du
Boulay et al. [2023] overview modern tutoring agents. Wellman [2011] overviews
research in trading agents. Sandholm [2007] describes how AI can be used for
procurement of multiple goods with complex preferences.
A number of AI texts are valuable as reference books complementary to this
book, providing a different perspective on AI. In particular, Russell and Norvig
[2020] give a more encyclopedic overview of AI. They provide an excellent
complementary source for many of the topics covered in this book and also an
outstanding review of the scientific literature, which we do not try to duplicate.
The Association for the Advancement of Artificial Intelligence (AAAI) pro-
vides introductory material and news at their AI Topics website (https://aitopics.
org/). AI Magazine, published by AAAI, often has excellent overview articles
and descriptions of particular applications. IEEE Intelligent Systems also pro-
vides accessible articles on AI research.
There are many journals that provide in-depth research contributions and
conferences where the most up-to-date research is found. These include the
journals Artificial Intelligence, the Journal of Artificial Intelligence Research, IEEE
Transactions on Pattern Analysis and Machine Intelligence, and Computational In-
telligence, as well as more specialized journals. Much of the cutting-edge re-
search is published first in conferences. Those of most interest to a general
audience are the International Joint Conference on Artificial Intelligence (IJ-
CAI), the AAAI Annual Conference, the European Conference on AI (ECAI),
the Pacific Rim International Conference on AI (PRICAI), various national con-
ferences, and many specialized conferences, which are referred to in the rele-
vant chapters.

1.11 Exercises
Exercise 1.1 For each of the following, give five reasons why:
(a) A dog is more intelligent than a worm.
(b) A human is more intelligent than a dog.
(c) An organization is more intelligent than an individual human.
Based on these, give a definition of what “more intelligent” may mean.
Exercise 1.2 Give as many disciplines as you can whose aim is to study intelligent
behavior of some sort. For each discipline, find out what aspect of behavior is
1.11. Exercises 49

investigated and what tools are used to study it. Be as liberal as you can regarding
what defines intelligent behavior.
Exercise 1.3 Find out about two applications of AI (not classes of applications,
but specific programs). For each application, write at most one typed page de-
scribing it. You should try to cover the following questions:
(a) What does the application actually do (e.g., control a spacecraft, diagnose a
photocopier, provide intelligent help for computer users)?
(b) What AI technologies does it use (e.g., model-based diagnosis, belief net-
works, semantic networks, heuristic search, constraint satisfaction)?
(c) How well does it perform? (According to the authors or to an independent
review? How does it compare to humans? How do the authors know how
well it works?)
(d) Is it an experimental system or a fielded system? (How many users does it
have? What expertise do these users require?)
(e) Why is it intelligent? What aspects of it make it an intelligent system?
(f) [optional] What programming language and environment was it written in?
What sort of user interface does it have?
(g) References: Where did you get the information about the application? To
what books, articles, or webpages should others who want to know about
the application refer?
Exercise 1.4 For each of the Winograd schemas in Example 1.2 (page 6), what
knowledge is required to correctly answer the questions? Try to find a “cheap”
method to find the answer, such as by comparing the number of results in a Google
search for different cases. Try this for six other Winograd schemas of Davis [2015].
Try to construct an example of your own.
Exercise 1.5 Choose four pairs of dimensions that were not compared in Sec-
tion 1.5.10 (page 35). For each pair, give one commonsense example of where the
dimensions interact.