Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition

Page 1 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 1 preview image

Exercise SolutionsforArtificial IntelligenceA Modern ApproachThird Edition (International Version)Stuart J. Russell and Peter Norvigwith contributions fromErnest Davis, Nicholas J. Hay, and Mehran Sahami

Page 2 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 2 preview image

Page 3 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 3 preview image

Solutions for Chapter 1Introduction1.1a. Dictionary definitions ofintelligencetalk about “the capacity to acquire and applyknowledge” or “the faculty of thought and reason” or “the ability to comprehend andprofit from experience.” These are all reasonable answers, but if we want somethingquantifiable we would use something like “the ability to apply knowledge in order toperform better in an environment.”b. We defineartificial intelligenceas the study and construction of agent programs thatperform well in a given environment, for a given agent architecture.c. We define anagentas an entity that takes action in response to percepts from an envi-ronment.d. We definerationalityas the property of a system which does the “right thing” givenwhat it knows. See Section 2.2 for a more complete discussion. Both describe perfectrationality, however; see Section 27.3.e. We definelogical reasoningas the a process of deriving new sentences from old, suchthat the new sentences are necessarily true if the old ones are true. (Notice that doesnot refer to any specific syntax oor formal language, but it does require a well-definednotion of truth.)1.2See 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 TuringTest) did fool one judge, although if you look at the transcript, it is hard to imagine whatthat judge was thinking.There certainly have been examples of a chatbot or other onlineagent fooling humans.For example, see See Lenny Foner’s account of the Julia chatbotat foner.www.media.mit.edu/people/foner/Julia/.We’d say the chance today is somethinglike 10%, with the variation depending more on the skill of the interrogator rather than theprogram. 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 credibleimpersonators.1.3Yes, they are rational, because slower, deliberative actions would tend to result in moredamage to the hand.If “intelligent” means “applying knowledge” or “using thought andreasoning” then it does not require intelligence to make a reflex action.1

Page 4 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 4 preview image

2Chapter1.Introduction1.4No. IQ test scores correlate well with certain other measures, such as success in college,ability to make good decisions in complex, real-world situations, ability to learn new skillsand subjects quickly, and so on, butonlyif they’re measuring fairly normal humans. The IQtest doesn’t measure everything. A program that is specialized only for IQ tests (and special-ized further only for the analogy part) would very likely perform poorly on other measuresof intelligence. Consider the following analogy: if a human runs the 100m in 10 seconds, wemight describe him or her asvery athleticand expect competent performance in other areassuch as walking, jumping, hurdling, and perhaps throwing balls; but we would not desscribea Boeing 747 asvery athleticbecause it can cover 100m in 0.4 seconds, nor would we expectit to be good at hurdling and throwing balls.Even for humans, IQ tests are controversial because of their theoretical presuppositionsabout innate ability (distinct from training effects) adn the generalizability of results.SeeThe Mismeasure of Manby Stephen Jay Gould, Norton, 1981 orMultiple intelligences: thetheory in practiceby Howard Gardner, Basic Books, 1993 for more on IQ tests, what theymeasure, and what other aspects there are to “intelligence.”1.5In order of magnitude figures, the computational power of the computer is 100 timeslarger.1.6Just as you are unaware of all the steps that go into making your heart beat, you arealso unaware of most of what happens in your thoughts. You do have a conscious awarenessof 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 toanalyze one’s own thoughts.1.7• Although bar code scanning is in a sense computer vision, these are not AI systems.The problem of reading a bar code is an extremely limited and artificial form of visualinterpretation, and it has been carefully designed to be as simple as possible, given thehardware.• In many respects. The problem of determining the relevance of a web page to a queryis a problem in natural language understanding, and the techniques are related to thosewe will discuss in Chapters 22 and 23.Search engines like Ask.com, which groupthe retrieved pages into categories, use clustering techniques analogous to those wediscuss in Chapter 20. Likewise, other functionalities provided by a search engines useintelligent techniques; for instance, the spelling corrector uses a form of data miningbased on observing users’ corrections of their own spelling errors. On the other hand,the problem of indexing billions of web pages in a way that allows retrieval in secondsis a problem in database design, not in artificial intelligence.• To a limited extent.Such menus tends to use vocabularies which are very limited –e.g. the digits, “Yes”, and “No” — and within the designers’ control, which greatlysimplifies the problem. On the other hand, the programs must deal with an uncontrolledspace of all kinds of voices and accents.

Page 5 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 5 preview image

3The voice activated directory assistance programs used by telephone companies,which must deal with a large and changing vocabulary are certainly AI programs.• This is borderline. There is something to be said for viewing these as intelligent agentsworking in cyberspace. The task is sophisticated, the information available is partial, thetechniques are heuristic (not guaranteed optimal), and the state of the world is dynamic.All of these are characteristic of intelligent activities. On the other hand, the task is veryfar from those normally carried out in human cognition.1.8Presumably the brain has evolved so as to carry out this operations on visual images,but the mechanism is only accessible for one particular purpose in this particular cognitivetask of image processing. Until about two centuries ago there was no advantage in people (oranimals) being able to compute the convolution of a Gaussian for any other purpose.The really interesting question here is what we mean by saying that the “actual person”can do something. The person can see, but he cannot compute the convolution of a Gaussian;but computing that convolution ispartof seeing. This is beyond the scope of this solutionmanual.1.9Evolution tends to perpetuate organisms (and combinations and mutations of organ-isms) that are successful enough to reproduce. That is, evolution favors organisms that canoptimize their performance measure to at least survive to the age of sexual maturity, and thenbe able to win a mate. Rationality just means optimizing performance measure, so this is inline with evolution.1.10This question is intended to be about the essential nature of the AI problem and what isrequired to solve it, but could also be interpreted as a sociological question about the currentpractice of AI research.Ascienceis a field of study that leads to the acquisition of empirical knowledge by thescientific method, which involves falsifiable hypotheses about what is. A pureengineeringfield can be thought of as taking a fixed base of empirical knowledge and using it to solveproblems of interest to society. Of course, engineers do bits of science—e.g., they measure theproperties of building materials—and scientists do bits of engineering to create new devicesand so on.As described in Section 1.1, the “human” side of AI is clearly an empirical science—called cognitive science these days—because it involves psychological experiments designedout to find out how human cognition actually works.What about the the “rational” side?If we view it as studying the abstract relationship among an arbitrary task environment, acomputing device, and the program for that computing device that yields the best performancein the task environment, then the rational side of AI is really mathematics and engineering;it does not require any empirical knowledge about theactualworld—and theactualtaskenvironment—that we inhabit; that a given program will do well in a given environment is atheorem. (The same is true of pure decision theory.) In practice, however, we are interestedin task environments that do approximate the actual world, so even the rational side of AIinvolves finding out what the actual world is like. For example, in studying rational agentsthat communicate, we are interested in task environments that contain humans, so we have

Page 6 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 6 preview image

4Chapter1.Introductionto find out what human language is like. In studying perception, we tend to focus on sensorssuch as cameras that extract useful information from the actual world. (In a world withoutlight, cameras wouldn’t be much use.) Moreover, to design vision algorithms that are goodat extracting information from camera images, we need to understand the actual world thatgenerates those images. Obtaining the required understanding of scene characteristics, objecttypes, surface markings, and so on is a quite different kind of science from ordinary physics,chemistry, biology, and so on, but it is still science.In summary, AI is definitely engineering but it would not be especially useful to us if itwere not also an empirical science concerned with those aspects of the real world that affectthe design of intelligent systems for that world.1.11This depends on your definition of “intelligent” and “tell.” In one sense computers onlydo what the programmers command them to do, but in another sense what the programmersconsciously tells the computer to do often has very little to do with what the computer actuallydoes.Anyone who has written a program with an ornery bug knows this, as does anyonewho has written a successful machine learning program. So in one sense Samuel “told” thecomputer “learn to play checkers better than I do, and then play that way,” but in anothersense he told the computer “follow this learning algorithm” and it learned to play. So we’releft in the situation where you may or may not consider learning to play checkers to be s signof 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 thecomputer.1.12The point of this exercise is to notice the parallel with the previous one.Whateveryou decided about whether computers could be intelligent in 1.11, you are committed tomaking the same conclusion about animals (including humans),unlessyour reasons for de-ciding whether something is intelligent take into account the mechanism (programming viagenes versus programming via a human programmer). Note that Searle makes this appeal tomechanism in his Chinese Room argument (see Chapter 26).1.13Again, the choice you make in 1.11 drives your answer to this question.1.14a. (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 hasshoulders and a center line, that the car ahead will travel a predictable course, that carswill keep to their side of the road, and so on. Some lane changes and turns can be madeon clearly marked roads in light to moderate traffic. Driving in downtown Cairo is toounpredictable for any of these to work.c. (driving in Victorville, California) Yes, to some extent, as demonstrated in DARPA’sUrban Challenge.Some of the vehicles managed to negotiate streets, intersections,well-behaved traffic, and well-behaved pedestrians in good visual conditions.

Page 7 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 7 preview image

5d. (shopping at the market) No. No robot can currently put together the tasks of moving ina crowded environment, using vision to identify a wide variety of objects, and graspingthe objects (including squishable vegetables) without damaging them. The componentpieces are nearly able to handle the individual tasks, but it would take a major integra-tion effort to put it all together.e. (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 overtime.f. (bridge) Yes. Programs such as GIB now play at a solid level.g. (theorem proving) Yes. For example, the proof of Robbins algebra described on page360.h. (funny story) No.While some computer-generated prose and poetry is hystericallyfunny, this is invariably unintentional, except in the case of programs that echo backprose that they have memorized.i. (legal advice) Yes, in some cases. AI has a long history of research into applicationsof automated legal reasoning. Two outstanding examples are the Prolog-based expertsystems used in the UK to guide members of the public in dealing with the intricacies ofthe social security and nationality laws. The social security system is said to have savedthe UK government approximately $150 million in its first year of operation. However,extension into more complex areas such as contract law awaits a satisfactory encodingof the vast web of common-sense knowledge pertaining to commercial transactions andagreement and business practices.j. (translation) Yes. In a limited way, this is already being done. See Kay, Gawron andNorvig (1994) and Wahlster (2000) for an overview of the field of speech translation,and some limitations on the current state of the art.k. (surgery) Yes. Robots are increasingly being used for surgery, although always underthe command of a doctor.Robotic skills demonstrated at superhuman levels includedrilling holes in bone to insert artificial joints, suturing, and knot-tying. They are notyet capable of planning and carrying out a complex operation autonomously from startto finish.1.15The progress made in this contests is a matter of fact, but the impact of that progress isa matter of opinion.•DARPA Grand Challenge for Robotic CarsIn 2004 the Grand Challenge was a 240km race through the Mojave Desert. It clearly stressed the state of the art of autonomousdriving, and in fact no competitor finished the race. The best team, CMU, completedonly 12 of the 240 km. In 2005 the race featured a 212km course with fewer curvesand wider roads than the 2004 race. Five teams finished, with Stanford finishing first,edging out two CMU entries. This was hailed as a great achievement for robotics andfor the Challenge format. In 2007 the Urban Challenge put cars in a city setting, wherethey had to obey traffic laws and avoid other cars. This time CMU edged out Stanford.

Page 8 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 8 preview image

6Chapter1.IntroductionThe competition appears to have been a good testing ground to put theory into practice,something that the failures of 2004 showed was needed.But it is important that thecompetition was done at just the right time, when there was theoretical work to con-solidate, as demonstrated by the earlier work by Dickmanns (whose VaMP car droveautonomously for 158km in 1995) and by Pomerleau (whose Navlab car drove 5000kmacross the USA, also in 1995, with the steering controlled autonomously for 98% of thetrip, although the brakes and accelerator were controlled by a human driver).•International Planning CompetitionIn 1998, five planners competed:Blackbox,HSP, IPP, SGP, and STAN. The result page (ftp://ftp.cs.yale.edu/pub/mcdermott/aipscomp-results.html) stated “all of these planners performedvery well, compared to the state of the art a few years ago.” Most plans found were 30 or40 steps, with some over 100 steps. In 2008, the competition had expanded quite a bit:there were more tracks (satisficing vs. optimizing; sequential vs. temporal; static vs.learning). There were about 25 planners, including submissions from the 1998 groups(or their descendants) and new groups. Solutions found were much longer than in 1998.In sum, the field has progressed quite a bit in participation, in breadth, and in power ofthe planners. In the 1990s it was possible to publish a Planning paper that discussedonly a theoretical approach; now it is necessary to show quantitative evidence of theefficacy of an approach. The field is stronger and more mature now, and it seems thatthe planning competition deserves some of the credit. However, some researchers feelthat too much emphasis is placed on the particular classes of problems that appear inthe competitions, and not enough on real-world applications.•Robocup Robotics SoccerThis competition has proved extremely popular, attracting407 teams from 43 countries in 2009 (up from 38 teams from 11 countries in 1997).The robotic platform has advanced to a more capable humanoid form, and the strategyand tactics have advanced as well. Although the competition has spurred innovationsin distributed control, the winning teams in recent years have relied more on individualball-handling skills than on advanced teamwork. The competition has served to increaseinterest and participation in robotics, although it is not clear how well they are advancingtowards the goal of defeating a human team by 2050.•TREC Information Retrieval ConferenceThis is one of the oldest competitions,started in 1992.The competitions have served to bring together a community of re-searchers, have led to a large literature of publications, and have seen progress in par-ticipation and in quality of results over the years.In the early years, TREC servedits purpose as a place to do evaluations of retrieval algorithms on text collections thatwere large for the time. However, starting around 2000 TREC became less relevant asthe advent of the World Wide Web created a corpus that was available to anyone andwas much larger than anything TREC had created, and the development of commercialsearch engines surpassed academic research.•NIST Open Machine Translation EvaluationThis series of evaluations (explicitlynot labelled a “competition”) has existed since 2001. Since then we have seen greatadvances in Machine Translation quality as well as in the number of languages covered.

Page 9 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 9 preview image

7The dominant approach has switched from one based on grammatical rules to one thatrelies primarily on statistics. The NIST evaluations seem to track these changes well,but don’t appear to be driving the changes.Overall, we see that whatever you measure is bound to increase over time. For most ofthese competitions, the measurement was a useful one, and the state of the art has progressed.In the case of ICAPS, some planning researchers worry that too much attention has beenlavished on the competition itself. In some cases, progress has left the competition behind,as in TREC, where the resources available to commercial search engines outpaced thoseavailable to academic researchers. In this case the TREC competition was useful—it helpedtrain many of the people who ended up in commercial search engines—and in no way drewenergy away from new ideas.

Page 10 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 10 preview image

Solutions for Chapter 2Intelligent Agents2.1This question tests the student’s understanding of environments, rational actions, andperformance measures. Any sequential environment in which rewards may take time to arrivewill work, because then we can arrange for the reward to be “over the horizon.” Suppose thatin any state there are two action choices,aandb, and consider two cases: the agent is in statesat timeTor at timeT−1. In states, actionareaches states′with reward 0, while actionbreaches statesagain with reward 1; ins′either action gains reward 10. At timeT−1,it’s rational to doains, with expected total reward 10 before time is up; but at timeT, it’srational to dobwith total expected reward 1 because the reward of 10 cannot be obtainedbefore time is up.Students may also provide common-sense examples from real life: investments whosepayoff occurs after the end of life, exams where it doesn’t make sense to start the high-valuequestion with too little time left to get the answer, and so on.The environment state can include a clock, of course; this doesn’t change the gist ofthe answer—now the action will depend on the clock as well as on the non-clock part of thestate—but it does mean that the agent can never be in the same state twice.2.2Notice 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 andinitial locations), this agent cleans the squares at least as fast as any other agent. This istrivially true when there is no dirt. When there is dirt in the initial location and none inthe other location, the world is clean after one step; no agent can do better. When thereis no dirt in the initial location but dirt in the other, the world is clean after two steps; noagent can do better. When there is dirt in both locations, the world is clean after threesteps; no agent can do better. (Note: in general, the condition stated in the first sentenceof 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.It is better to doNoOponce the world is clean (the chapter says this).Now, sincethe agent’s percept doesn’t say whether the other square is clean, it would seem thatthe agent must have some memory to say whether the other square has already beencleaned.To make this argument rigorous is more difficult—for example, could theagent arrange things so that it would only be in a clean left square when the right square8

Page 11 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 11 preview image

9was already clean? As a general strategy, an agentcanuse the environment itself asa form ofexternal memory—a common technique for humans who use things likeEXTERNAL MEMORYappointment calendars and knots in handkerchiefs. In this particular case, however, thatis not possible. Consider the reflex actions for[A,Clean]and[B,Clean]. If either ofthese isNoOp, then the agent will fail in the case where that is the initial percept butthe other square is dirty; hence, neither can beNoOpand therefore the simple reflexagent is doomed to keep moving. In general, the problem with reflex agents is that theyhave to do the same thing in situations that look the same, even when the situationsare actually quite different. In the vacuum world this is a big liability, because everyinterior square (except home) looks either like a square with dirt or a square withoutdirt.c. If we consider asymptotically long lifetimes, then it is clear that learning a map (insome form) confers an advantage because it means that the agent can avoid bumpinginto walls.It can also learn where dirt is most likely to accumulate and can devisean optimal inspection strategy. The precise details of the exploration method neededto construct a complete map appear in Chapter 4; methods for deriving an optimalinspection/cleanup strategy are in Chapter 21.2.3a.An agent that senses only partial information about the state cannot be perfectly ra-tional.False. Perfect rationality refers to the ability to make good decisions given the sensorinformation received.b.There exist task environments in which no pure reflex agent can behave rationally.True. A pure reflex agent ignores previous percepts, so cannot obtain an optimal stateestimate in a partially observable environment. For example, correspondence chess isplayed by sending moves; if the other player’s move is the current percept, a reflex agentcould not keep track of the board state and would have to respond to, say, “a4” in thesame way regardless of the position in which it was played.c.There exists a task environment in which every agent is rational.True. For example, in an environment with a single state, such that all actions have thesame reward, it doesn’t matter which action is taken. More generally, any environmentthat is reward-invariant under permutation of the actions will satisfy this property.d.The input to an agent program is the same as the input to the agent function.False.The agent function, notionally speaking, takes as input the entire percept se-quence up to that point, whereas the agent program takes the current percept only.e.Every agent function is implementable by some program/machine combination.False. For example, the environment may contain Turing machines and input tapes andthe agent’s job is to solve the halting problem; there is an agentfunctionthat specifiesthe right answers, but no agent program can implement it. Another example would bean agent function that requires solving intractable problem instances of arbitrary size inconstant time.

Page 12 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 12 preview image

10Chapter2.Intelligent Agentsf.Suppose an agent selects its action uniformly at random from the set of possible actions.There exists a deterministic task environment in which this agent is rational.True. This is a special case of (c); if it doesn’t matter which action you take, selectingrandomly is rational.g.It is possible for a given agent to be perfectly rational in two distinct task environments.True.For example, we can arbitrarily modify the parts of the environment that areunreachable by any optimal policy as long as they stay unreachable.h.Every agent is rational in an unobservable environment.False. Some actions are stupid—and the agent may know this if it has a model of theenvironment—even if one cannot perceive the environment state.i.A perfectly rational poker-playing agent never loses.False. Unless it draws the perfect hand, the agent can always lose if an opponent hasbetter cards. This can happen for game after game. The correct statement is that theagent’s expected winnings are nonnegative.2.4Many of these can actually be argued either way, depending on the level of detail andabstraction.A. Partially observable, stochastic, sequential, dynamic, continuous, multi-agent.B. Partially observable, stochastic, sequential, dynamic, continuous, single agent (unlessthere are alien life forms that are usefully modeled as agents).C. Partially observable, deterministic, sequential, static, discrete, single agent. This can bemulti-agent and dynamic if we buy books via auction, or dynamic if we purchase on along enough scale that book offers change.D. Fully observable, stochastic, episodic (every point is separate), dynamic, continuous,multi-agent.E. Fully observable, stochastic, episodic, dynamic, continuous, single agent.F. Fully observable, stochastic, sequential, static, continuous, single agent.G. Fully observable, deterministic, sequential, static, continuous, single agent.H. Fully observable, strategic, sequential, static, discrete, multi-agent.2.5The following are just some of the many possible definitions that can be written:•Agent: an entity that perceives and acts; or, one thatcan be viewedas perceiving andacting. Essentially any object qualifies; the key point is the way the object implementsan agent function. (Note: some authors restrict the term toprogramsthat operateonbehalf ofa human, or to programs that can cause some or all of their code to run onother machines on a network, as inmobile agents.)MOBILE AGENT•Agent function: a function that specifies the agent’s action in response to every possiblepercept 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 oneach invocation and returns an action.

Page 13 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 13 preview image

11•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 experiencerather 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 modelof the current world state that is updated over time.•Goal-based agent: an agent that selects actions that it believes will achieve explicitlyrepresented goals.•Utility-based agent:an agent that selects actions that it believes will maximize theexpected utility of the outcome state.•Learning agent: an agent whose behavior improves over time based on its experience.2.6Although these questions are very simple, they hint at some very fundamental issues.Our answers are for the simple agent designs forstaticenvironments where nothing happenswhile 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 printtruewhen the percept is aTuring machine program that halts, andfalseotherwise. (Note: in dynamic environ-ments, for machines of less than infinite speed, the rational agent function may not beimplementable; e.g., the agent function that always plays a winning move, if any, in agame of chess.)c. Yes; the agent’s behavior is fixed by the architecture and program.d. There are2nagent programs, although many of these will not run at all. (Note: Anygiven program can devote at mostnbits to storage, so its internal state can distinguishamong only2npast histories. Because the agent function specifies actions based on per-cept histories, there will be many agent functions that cannot be implemented becauseof lack of memory in the machine.)e. It depends on the program and the environment. If the environment is dynamic, speed-ing up the machine may mean choosing different (perhaps better) actions and/or actingsooner. If the environment is static and the program pays no attention to the passage ofelapsed time, the agent function is unchanged.2.7The design of goal- and utility-based agents depends on the structure of the task en-vironment. The simplest such agents, for example those in chapters 3 and 10, compute theagent’s entire future sequence of actions in advance before acting at all. This strategy worksfor static and deterministic environments which are either fully-known or unobservableFor fully-observable and fully-known static environments a policy can be computed inadvance which gives the action to by taken in any given state.

Page 14 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 14 preview image

12Chapter2.Intelligent AgentsfunctionGOAL-BASED-AGENT(percept)returnsan actionpersistent:state, the agent’s current conception of the world statemodel, a description of how the next state depends on current state and actiongoal, a description of the desired goal stateplan, a sequence of actions to take, initially emptyaction, the most recent action, initially nonestate←UPDATE-STATE(state,action,percept,model)ifGOAL-ACHIEVED(state,goal)then returna null actionifplanis emptythenplan←PLAN(state,goal,model)action←FIRST(plan)plan←REST(plan)returnactionFigure S2.1A goal-based agent.For partially-observable environments the agent can compute a conditional plan, whichspecifies the sequence of actions to take as a function of the agent’s perception. In the ex-treme, a conditional plan gives the agent’s response to every contingency, and so it is a repre-sentation of the entire agent function.In all cases it may be either intractable or too expensive to compute everything out inadvance.Instead of a conditional plan, it may be better to compute a single sequence ofactions which is likely to reach the goal, then monitor the environment to check whether theplan is succeeding, repairing or replanning if it is not. It may be even better to compute onlythe start of this plan before taking the first action, continuing to plan at later time steps.Pseudocode for simple goal-based agent is given in Figure S2.1.GOAL-ACHIEVEDtests to see whether the current state satisfies the goal or not, doing nothing if it does. PLANcomputes a sequence of actions to take to achieve the goal. This might return only a prefixof the full plan, the rest will be computed after the prefix is executed. This agent will act tomaintain the goal: if at any point the goal is not satisfied it will (eventually) replan to achievethe goal again.At this level of abstraction the utility-based agent is not much different than the goal-based agent, except that action may be continuously required (there is not necessarily a pointwhere the utility function is “satisfied”). Pseudocode is given in Figure S2.2.2.8The file"agents/environments/vacuum.lisp"in the code repository imple-ments the vacuum-cleaner environment. Students can easily extend it to generate differentshaped rooms, obstacles, and so on.2.9A reflex agent program implementing the rational agent function described in the chap-ter is as follows:(defun reflex-rational-vacuum-agent (percept)(destructuring-bind (location status) percept

Page 15 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 15 preview image

13functionUTILITY-BASED-AGENT(percept)returnsan actionpersistent:state, the agent’s current conception of the world statemodel, a description of how the next state depends on current state and actionutility−function, a description of the agent’s utility functionplan, a sequence of actions to take, initially emptyaction, the most recent action, initially nonestate←UPDATE-STATE(state,action,percept,model)ifplanis emptythenplan←PLAN(state,utility−function,model)action←FIRST(plan)plan←REST(plan)returnactionFigure S2.2A utility-based agent.(cond ((eq status ’Dirty) ’Suck)((eq location ’A) ’Right)(t ’Left))))For states 1, 3, 5, 7 in Figure 4.9, the performance measures are 1996, 1999, 1998, 2000respectively.2.10a. No; see answer to 2.4(b).b. See answer to 2.4(b).c. In this case, a simple reflex agent can be perfectly rational. The agent can consist ofa table with eight entries, indexed by percept, that specifies an action to take for eachpossible state. After the agent acts, the world is updated and the next percept will tellthe agent what to do next. For larger environments, constructing a table is infeasible.Instead, the agent could run one of the optimal search algorithms in Chapters 3 and 4and execute the first step of the solution sequence. Again, no internal state isrequired,but it would help to be able to store the solution sequence instead of recomputing it foreach new percept.2.11a. Because the agent does not know the geography and perceives only location and localdirt, and cannot remember what just happened, it will get stuck forever against a wallwhen it tries to move in a direction that is blocked—that is, unless it randomizes.b. One possible design cleans up dirt and otherwise moves randomly:(defun randomized-reflex-vacuum-agent (percept)(destructuring-bind (location status) percept(cond ((eq status ’Dirty) ’Suck)(t (random-element ’(Left Right Up Down))))))

Page 16 of 16

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 16 preview image

14Chapter2.Intelligent AgentsFigure S2.3An environment in which random motion will take a long time to cover allthe squares.This is fairly close to what the RoombaTMvacuum cleaner does (although the Roombahas a bump sensor and randomizes only when it hits an obstacle). It works reasonablywell in nice, compact environments. In maze-like environments or environments withsmall connecting passages, it can take a very long time to cover all the squares.c. An example is shown in Figure S2.3. Students may also wish to measure clean-up timefor linear or square environments of different sizes, and compare those to the efficientonline search algorithms described in Chapter 4.d. A reflex agent with state can build a map (see Chapter 4 for details). An online depth-first exploration will reach every state in time linear in the size of the environment;therefore, the agent can do much better than the simple reflex agent.The question of rational behavior in unknown environments is a complex one but it isworth encouraging students to think about it. We need to have some notion of the priorprobability distribution over the class of environments; call this the initialbelief state.Any action yields a new percept that can be used to update this distribution, movingthe agent to a new belief state. Once the environment is completely explored, the beliefstate collapses to a single possible environment.Therefore, the problem of optimalexploration can be viewed as a search for an optimal strategy in the space of possiblebelief states. This is a well-defined, if horrendously intractable, problem. Chapter 21discusses some cases where optimal exploration is possible. Another concrete exampleof exploration is the Minesweeper computer game (see Exercise 7.22). For very smallMinesweeper environments, optimal exploration is feasible although the belief state

Preview Mode

This document has 234 pages. Sign in to access the full document!

Report

Learning Tools

Writing Tools

Browse Resources

Solution Manual For Artificial Intelligence: A Modern Approach, 3rd Edition - Page 1

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools