Artificial Intelligence: A Modern Approach, 4th Edition
Instructor’s Manual:
Exercise Solutions
for
Artificial Intelligence
A Modern Approach
Fourth Edition
Stuart J. Russell and Peter Norvig
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
Solutions for Chapter 1
Introduction
1.1
a. Dictionary definitions of intelligence talk about ―the capacity to acquire and apply
knowledge‖ or ―the faculty of thought and reason‖ or ―the ability to comprehend and
profit from experience.‖ These are all reasonable answers, but if we want something
quantifiable we would use something like ―the ability to apply knowledge in order to
perform better in an environment.‖
b. We define artificial intelligence as the study and construction of agent programs that
perform well in a given environment, for a given agent architecture.
c. We define an agent as an entity that takes action in response to percepts from an envi-
ronment.
1.2 See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the interroga-
tor is. One entrant in the 2002 Loebner prize competition (which is not quite a real Turing
Test) did fool one judge, although if you look at the transcript, it is hard to imagine what
that judge was thinking. There certainly have been examples of a chatbot or other online
agent fooling humans. For example, see See Lenny Foner’s account of the Julia chatbot
at foner.www.media.mit.edu/people/foner/Julia/. We’d say the chance today is something
like 10%, with the variation depending more on the skill of the interrogator rather than the
program. In 50 years, we expect that the entertainment industry (movies, video games, com-
mercials) will have made sufficient investments in artificial actors to create very credible
impersonators.
1.3 The 2002 Loebner prize (www.loebner.net) went to Kevin Copple’s program ELLA. It
consists of a prioritized set of pattern/action rules: if it sees a text string matching a certain
pattern, it outputs the corresponding response, which may include pieces of the current or
past input. It also has a large database of text and has the Wordnet online dictionary. It is
therefore using rather rudimentary tools, and is not advancing the theory of AI. It is provid-
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
ing evidence on the number and type of rules that are sufficient for producing one type of
conversation.
1.4 No. It means that AI systems should avoid trying to solve intractable problems. Usually,
this means they can only approximate optimal behavior. Notice that humans don’t solve NP-
complete problems either. Sometimes they are good at solving specific instances with a lot of
structure, perhaps with the aid of background knowledge. AI systems should attempt to do
the same.
1.5 No. IQ test scores correlate well with certain other measures, such as success in college,
but only if they’re measuring fairly normal humans. The IQ test doesn’t measure everything.
A program that is specialized only for IQ tests (and specialized further only for the analogy
part) would very likely perform poorly on other measures of intelligence. See The Mismea-
sure of Man by Stephen Jay Gould, Norton, 1981 or Multiple intelligences: the theory in
practice by Howard Gardner, Basic Books, 1993 for more on IQ tests, what they measure,
and what other aspects there are to ―intelligence.‖
1.6 Just as you are unaware of all the steps that go into making your heart beat, you are
also unaware of most of what happens in your thoughts. You do have a conscious awareness
of some of your thought processes, but the majority remains opaque to your consciousness.
The field of psychoanalysis is based on the idea that one needs trained professional help to
analyze one’s own thoughts.
1.7
a. (ping-pong) A reasonable level of proficiency was achieved by Andersson’s robot (An-
dersson, 1988).
b. (driving in Cairo) No. Although there has been a lot of progress in automated driving,
all such systems currently rely on certain relatively constant clues: that the road has
shoulders and a center line, that the car ahead will travel a predictable course, that cars
will keep to their side of the road, and so on. To our knowledge, none are able to avoid
obstacles or other cars or to change lanes as appropriate; their skills are mostly confined
to staying in one lane at constant speed. Driving in downtown Cairo is too unpredictable
for any of these to work.
c. (shopping at the market) No. No robot can currently put together the tasks of moving in
a crowded environment, using vision to identify a wide variety of objects, and grasping
the objects (including squishable vegetables) without damaging them. The component
pieces are nearly able to handle the individual tasks, but it would take a major integra-
tion effort to put it all together.
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
d. (shopping on the web) Yes. Software robots are capable of handling such tasks, par-
ticularly if the design of the web grocery shopping site does not change radically over
time.
e. (bridge) Yes. Programs such as GIB now play at a solid level.
f. (theorem proving) Yes. For example, the proof of Robbins algebra described on page
309.
g. (funny story) No. While some computer-generated prose and poetry is hysterically
funny, this is invariably unintentional, except in the case of programs that echo back
prose that they have memorized.
h. (legal advice) Yes, in some cases. AI has a long history of research into applications
of automated legal reasoning. Two outstanding examples are the Prolog-based expert
systems used in the UK to guide members of the public in dealing with the intricacies of
the social security and nationality laws. The social security system is said to have saved
the UK government approximately $150 million in its first year of operation. However,
extension into more complex areas such as contract law awaits a satisfactory encoding
of the vast web of common-sense knowledge pertaining to commercial transactions and
agreement and business practices.
i. (translation) Yes. In a limited way, this is already being done. See Kay, Gawron and
Norvig (1994) and Wahlster (2000) for an overview of the field of speech translation,
and some limitations on the current state of the art.
j. (surgery) Yes. Robots are increasingly being used for surgery, although always under
the command of a doctor.
1.8 Certainly perception and motor skills are important, and it is a good thing that the fields
of vision and robotics exist (whether or not you want to consider them part of ―core‖ AI).
But given a percept, an agent still has the task of ―deciding‖ (either by deliberation or by
reaction) which action to take. This is just as true in the real world as in artificial micro-
worlds such as chess-playing. So computing the appropriate action will remain a crucial part
of AI, regardless of the perceptual and motor system to which the agent program is ―attached.‖
On the other hand, it is true that a concentration on micro-worlds has led AI away from the
really interesting environments (see page 46).
1.9 Evolution tends to perpetuate organisms (and combinations and mutations of organ-
isms) that are succesful enough to reproduce. That is, evolution favors organisms that can
optimize their performance measure to at least survive to the age of sexual maturity, and then
Solution Manual Pag
Instructor’s Manual:
Exercise Solutions
for
Artificial Intelligence
A Modern Approach
Fourth Edition
Stuart J. Russell and Peter Norvig
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
Solutions for Chapter 1
Introduction
1.1
a. Dictionary definitions of intelligence talk about ―the capacity to acquire and apply
knowledge‖ or ―the faculty of thought and reason‖ or ―the ability to comprehend and
profit from experience.‖ These are all reasonable answers, but if we want something
quantifiable we would use something like ―the ability to apply knowledge in order to
perform better in an environment.‖
b. We define artificial intelligence as the study and construction of agent programs that
perform well in a given environment, for a given agent architecture.
c. We define an agent as an entity that takes action in response to percepts from an envi-
ronment.
1.2 See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the interroga-
tor is. One entrant in the 2002 Loebner prize competition (which is not quite a real Turing
Test) did fool one judge, although if you look at the transcript, it is hard to imagine what
that judge was thinking. There certainly have been examples of a chatbot or other online
agent fooling humans. For example, see See Lenny Foner’s account of the Julia chatbot
at foner.www.media.mit.edu/people/foner/Julia/. We’d say the chance today is something
like 10%, with the variation depending more on the skill of the interrogator rather than the
program. In 50 years, we expect that the entertainment industry (movies, video games, com-
mercials) will have made sufficient investments in artificial actors to create very credible
impersonators.
1.3 The 2002 Loebner prize (www.loebner.net) went to Kevin Copple’s program ELLA. It
consists of a prioritized set of pattern/action rules: if it sees a text string matching a certain
pattern, it outputs the corresponding response, which may include pieces of the current or
past input. It also has a large database of text and has the Wordnet online dictionary. It is
therefore using rather rudimentary tools, and is not advancing the theory of AI. It is provid-
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
ing evidence on the number and type of rules that are sufficient for producing one type of
conversation.
1.4 No. It means that AI systems should avoid trying to solve intractable problems. Usually,
this means they can only approximate optimal behavior. Notice that humans don’t solve NP-
complete problems either. Sometimes they are good at solving specific instances with a lot of
structure, perhaps with the aid of background knowledge. AI systems should attempt to do
the same.
1.5 No. IQ test scores correlate well with certain other measures, such as success in college,
but only if they’re measuring fairly normal humans. The IQ test doesn’t measure everything.
A program that is specialized only for IQ tests (and specialized further only for the analogy
part) would very likely perform poorly on other measures of intelligence. See The Mismea-
sure of Man by Stephen Jay Gould, Norton, 1981 or Multiple intelligences: the theory in
practice by Howard Gardner, Basic Books, 1993 for more on IQ tests, what they measure,
and what other aspects there are to ―intelligence.‖
1.6 Just as you are unaware of all the steps that go into making your heart beat, you are
also unaware of most of what happens in your thoughts. You do have a conscious awareness
of some of your thought processes, but the majority remains opaque to your consciousness.
The field of psychoanalysis is based on the idea that one needs trained professional help to
analyze one’s own thoughts.
1.7
a. (ping-pong) A reasonable level of proficiency was achieved by Andersson’s robot (An-
dersson, 1988).
b. (driving in Cairo) No. Although there has been a lot of progress in automated driving,
all such systems currently rely on certain relatively constant clues: that the road has
shoulders and a center line, that the car ahead will travel a predictable course, that cars
will keep to their side of the road, and so on. To our knowledge, none are able to avoid
obstacles or other cars or to change lanes as appropriate; their skills are mostly confined
to staying in one lane at constant speed. Driving in downtown Cairo is too unpredictable
for any of these to work.
c. (shopping at the market) No. No robot can currently put together the tasks of moving in
a crowded environment, using vision to identify a wide variety of objects, and grasping
the objects (including squishable vegetables) without damaging them. The component
pieces are nearly able to handle the individual tasks, but it would take a major integra-
tion effort to put it all together.
Solution Manual Pag
, Artificial Intelligence: A Modern Approach, 4th Edition
d. (shopping on the web) Yes. Software robots are capable of handling such tasks, par-
ticularly if the design of the web grocery shopping site does not change radically over
time.
e. (bridge) Yes. Programs such as GIB now play at a solid level.
f. (theorem proving) Yes. For example, the proof of Robbins algebra described on page
309.
g. (funny story) No. While some computer-generated prose and poetry is hysterically
funny, this is invariably unintentional, except in the case of programs that echo back
prose that they have memorized.
h. (legal advice) Yes, in some cases. AI has a long history of research into applications
of automated legal reasoning. Two outstanding examples are the Prolog-based expert
systems used in the UK to guide members of the public in dealing with the intricacies of
the social security and nationality laws. The social security system is said to have saved
the UK government approximately $150 million in its first year of operation. However,
extension into more complex areas such as contract law awaits a satisfactory encoding
of the vast web of common-sense knowledge pertaining to commercial transactions and
agreement and business practices.
i. (translation) Yes. In a limited way, this is already being done. See Kay, Gawron and
Norvig (1994) and Wahlster (2000) for an overview of the field of speech translation,
and some limitations on the current state of the art.
j. (surgery) Yes. Robots are increasingly being used for surgery, although always under
the command of a doctor.
1.8 Certainly perception and motor skills are important, and it is a good thing that the fields
of vision and robotics exist (whether or not you want to consider them part of ―core‖ AI).
But given a percept, an agent still has the task of ―deciding‖ (either by deliberation or by
reaction) which action to take. This is just as true in the real world as in artificial micro-
worlds such as chess-playing. So computing the appropriate action will remain a crucial part
of AI, regardless of the perceptual and motor system to which the agent program is ―attached.‖
On the other hand, it is true that a concentration on micro-worlds has led AI away from the
really interesting environments (see page 46).
1.9 Evolution tends to perpetuate organisms (and combinations and mutations of organ-
isms) that are succesful enough to reproduce. That is, evolution favors organisms that can
optimize their performance measure to at least survive to the age of sexual maturity, and then
Solution Manual Pag
