Artificial Intelligence

Artificial Intelligence free pdf ebook was written by on July 24, 2003 consist of 181 page(s). The pdf file is provided by and available on pdfpedia since October 28, 2011.

library of congr ess catalo ging-in-publication data russell, stuart j. (stuart jonathan) instructor'ssolutionmanual for artificial intelligence: a modern approach ...

send send what is readshare?

Thank you for helping us grow by simply clicking on facebook like and google +1 button below ^^

Artificial Intelligence pdf

: 5883
: 688
: October 28, 2011
: anonymous
Total Page(s)
: 181
Artificial Intelligence - page 1
Instructor’s Manual: Exercise Solutions for Artificial Intelligence A Modern Approach Second Edition Stuart J. Russell and Peter Norvig Upper Saddle River, New Jersey 07458
You're reading the first 10 out of 181 pages of this docs, please download or login to readmore.
Artificial Intelligence - page 2
Library of Congress Cataloging-in-Publication Data Russell, Stuart J. (Stuart Jonathan) Instructor’s solution manual for artificial intelligence : a modern approach (second edition) / Stuart Russell, Peter Norvig. Includes bibliographical references and index. 1. Artificial intelligence I. Norvig, Peter. II. Title. Vice President and Editorial Director, ECS: Marcia J. Horton Publisher: Alan R. Apt Associate Editor: Toni Dianne Holm Editorial Assistant: Patrick Lindner Vice President and Director of Production and Manufacturing, ESM: David W. Riccardi Executive Managing Editor: Vince O’Brien Managing Editor: Camille Trentacoste Production Editor: Mary Massey Manufacturing Manager: Trudy Pisciotti Manufacturing Buyer: Lisa McDowell Marketing Manager: Pamela Shaffer c 2003 Pearson Education, Inc. Pearson Prentice Hall Pearson Education, Inc. Upper Saddle River, NJ 07458 All rights reserved. No part of this manual may be reproduced in any form or by any means, without permission in writing from the publisher. Pearson Prentice Hall R is a trademark of Pearson Education, Inc.   Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 ISBN: 0-13-090376-0 Pearson Education Ltd., London Pearson Education Australia Pty. Ltd., Sydney Pearson Education Singapore, Pte. Ltd. Pearson Education North Asia Ltd., Hong Kong Pearson Education Canada, Inc., Toronto Pearson Educacion de Mexico, S.A. de C.V. ´ Pearson Education—Japan, Tokyo Pearson Education Malaysia, Pte. Ltd. Pearson Education, Inc., Upper Saddle River, New Jersey  
Artificial Intelligence - page 3
Preface This Instructor’s Solution Manual provides solutions (or at least solution sketches) for almost all of the 400 exercises in Artificial Intelligence: A Modern Approach (Second Edi- tion). We only give actual code for a few of the programming exercises; writing a lot of code would not be that helpful, if only because we don’t know what language you prefer. In many cases, we give ideas for discussion and follow-up questions, and we try to explain why we designed each exercise. There is more supplementary material that we want to offer to the instructor, but we have decided to do it through the medium of the World Wide Web rather than through a CD or printed Instructor’s Manual. The idea is that this solution manual contains the material that must be kept secret from students, but the Web site contains material that can be updated and added to in a more timely fashion. The address for the web site is: and the address for the online Instructor’s Guide is: There you will find: ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ Instructions on how to join the aima-instructors discussion list. We strongly recom- mend that you join so that you can receive updates, corrections, notification of new versions of this Solutions Manual, additional exercises and exam questions, etc., in a timely manner. Source code for programs from the text. We offer code in Lisp, Python, and Java, and point to code developed by others in C++ and Prolog. Programming resources and supplemental texts. Figures from the text; for overhead transparencies. Terminology from the index of the book. Other courses using the book that have home pages on the Web. You can see example syllabi and assignments here. Please do not put solution sets for AIMA exercises on public web pages! AI Education information on teaching introductory AI courses. Other sites on the Web with information on AI. Organized by chapter in the book; check this for supplemental material. We welcome suggestions for new exercises, new environments and agents, etc. The book belongs to you, the instructor, as much as us. We hope that you enjoy teaching from it, that these supplemental materials help, and that you will share your supplements and experi- ences with other instructors. iii
Artificial Intelligence - page 4
Artificial Intelligence - page 5
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 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 ( went to Kevin Copple’s program E LLA . 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- 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 1
Artificial Intelligence - page 6
2 Chapter 1. Introduction 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. 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
Artificial Intelligence - page 7
3 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 be able to win a mate. Rationality just means optimizing performance measure, so this is in line with evolution. 1.10 Yes, they are rational, because slower, deliberative actions would tend to result in more damage to the hand. If “intelligent” means “applying knowledge” or “using thought and reasoning” then it does not require intelligence to make a reflex action. 1.11 This depends on your definition of “intelligent” and “tell.” In one sense computers only do what the programmers command them to do, but in another sense what the programmers consciously tells the computer to do often has very little to do with what the computer actually does. Anyone who has written a program with an ornery bug knows this, as does anyone who has written a successful machine learning program. So in one sense Samuel “told” the computer “learn to play checkers better than I do, and then play that way,” but in another sense he told the computer “follow this learning algorithm” and it learned to play. So we’re left in the situation where you may or may not consider learning to play checkers to be s sign of intelligence (or you may think that learning to play in the right way requires intelligence, but not in this way), and you may think the intelligence resides in the programmer or in the computer. 1.12 The point of this exercise is to notice the parallel with the previous one. Whatever you decided about whether computers could be intelligent in 1.9, you are committed to making the
Artificial Intelligence - page 8
4 Chapter 1. Introduction same conclusion about animals (including humans), unless your reasons for deciding whether something is intelligent take into account the mechanism (programming via genes versus programming via a human programmer). Note that Searle makes this appeal to mechanism in his Chinese Room argument (see Chapter 26). 1.13 Again, the choice you make in 1.11 drives your answer to this question.
Artificial Intelligence - page 9
Solutions for Chapter 2 Intelligent Agents 2.1 ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¦© ¨¥¦¤¢       § £ The following are just some of the many possible definitions that can be written: Agent: an entity that perceives and acts; or, one that can be viewed as perceiving and acting. Essentially any object qualifies; the key point is the way the object implements an agent function. (Note: some authors restrict the term to programs that operate on behalf of a human, or to programs that can cause some or all of their code to run on other machines on a network, as in mobile agents.) Agent function: a function that specifies the agent’s action in response to every possible percept sequence. Agent program: that program which, combined with a machine architecture, imple- ments an agent function. In our simple designs, the program takes a new percept on each invocation and returns an action. Rationality: a property of agents that choose actions that maximize their expected util- ity, given the percepts to date. Autonomy: a property of agents whose behavior is determined by their own experience rather than solely by their initial programming. Reflex agent: an agent whose action depends only on the current percept. Model-based agent: an agent whose action is derived directly from an internal model of the current world state that is updated over time. Goal-based agent: an agent that selects actions that it believes will achieve explicitly represented goals. Utility-based agent: an agent that selects actions that it believes will maximize the expected utility of the outcopme state. Learning agent: an agent whose behavior improves over time based on its experience. 2.2 A performance measure is used by an outside observer to evaluate how successful an agent is. It is a function from histories to a real number. A utility function is used by an agent itself to evaluate how desirable states or histories are. In our framework, the utility function may not be the same as the performance measure; furthermore, an agent may have no explicit utility function at all, whereas there is always a performance measure. 2.3 Although these questions are very simple, they hint at some very fundamental issues. Our answers are for the simple agent designs for static environments where nothing happens 5
Artificial Intelligence - page 10
6 Chapter 2. Intelligent Agents while the agent is deliberating; the issues get even more interesting for dynamic environ- ments. a. Yes; take any agent program and insert null statements that do not affect the output. b. Yes; the agent function might specify that the agent print when the percept is a Turing machine program that halts, and otherwise. (Note: in dynamic environ- ments, for machines of less than infinite speed, the rational agent function may not be implementable; e.g., the agent function that always plays a winning move, if any, in a game of chess.) c. Yes; the agent’s behavior is fixed by the architecture and program. d. There are agent programs, although many of these will not run at all. (Note: Any given program can devote at most bits to storage, so its internal state can distinguish among only past histories. Because the agent function specifies actions based on per- cept histories, there will be many agent functions that cannot be implemented because of lack of memory in the machine.) 2.4 Notice that for our simple environmental assumptions we need not worry about quanti- tative uncertainty. a. It suffices to show that for all possible actual environments (i.e., all dirt distributions and initial locations), this agent cleans the squares at least as fast as any other agent. This is trivially true when there is no dirt. When there is dirt in the initial location and none in the other location, the world is clean after one step; no agent can do better. When there is no dirt in the initial location but dirt in the other, the world is clean after two steps; no agent can do better. When there is dirt in both locations, the world is clean after three steps; no agent can do better. (Note: in general, the condition stated in the first sentence of this answer is much stricter than necessary for an agent to be rational.) b. The agent in (a) keeps moving backwards and forwards even after the world is clean. once the world is clean (the chapter says this). Now, since It is better to do the agent’s percept doesn’t say whether the other square is clean, it would seem that the agent must have some memory to say whether the other square has already been cleaned. To make this argument rigorous is more difficult—for example, could the agent arrange things so that it would only be in a clean left square when the right square was already clean? As a general strategy, an agent can use the environment itself as a form of external memory—a common technique for humans who use things like appointment calendars and knots in handkerchiefs. In this particular case, however, that is not possible. Consider the reflex actions for and . If either of , then the agent will fail in the case where that is the initial percept but these is the other square is dirty; hence, neither can be and therefore the simple reflex agent is doomed to keep moving. In general, the problem with reflex agents is that they have to do the same thing in situations that look the same, even when the situations are actually quite different. In the vacuum world this is a big liability, because every interior square (except home) looks either like a square with dirt or a square without dirt. ` X & #( dY1WUVcb R T ` X & #( U T aY1WV8S R A 9 7 Bfe6 A 9 7 B@86 A 9 7 B@86 # ! $"  # 0( & 1)'% 5 3 42 3 42 EP¤¨¦IH¨H¨FED QG £ ¢  ¢ ©  G  C
You're reading the first 10 out of 181 pages of this docs, please download or login to readmore.

People are reading about...