# Textbook Exercises: Artificial Intelligence: CSC 242

The keys EX1, EX2... correspond to the entries in the syllabus. Some exercises may have their own links, others appear here directly. Chapter RN3 means Chapter 3 of Russell and Norvig.

In general it's a good idea to go through all the exercises in RN for the current chapter to make sure you feel comfortable with them. On the other hand, sometimes the problems are not directly from the chapter, and may require a little outside reading. If you are frustrated by a problem, see the Prof. or a TA. A list of exercises in parentheses like this: (1.9 -- 1.13) means work any one of the exercises in the list. [Square Brackets] mean "work any two". You can do extra problems if you like. Make sure we know which ones they are. If there is a lot of prose in your answers (as opposed to math), consider using a text-processor! Write mathematics correctly -- if in doubt see the Homework and writing tools helper page.

New in 2009. The Homework Korner might be insulting, might be helpful: feel free to let me know.

New in 2010. We probably have a mix of 2nd and 3rd edition texts in class, so we now have (basically the same) exercises differently numbered in the two editions. Be sure you pick the right one.

### EX1: Chapters RN1, RN2, RN3

2nd Edition Problems

RN1: (1.9 -- 1.13) that is do ONE of 1.9 -- 1.13. [Not quite same as 3nd ed. but that's OK]

RN2: 2.1, 2.3, (2.10, 2.11), 2.12 (5 points per answer). The book seems to want you to write and use a simulator for 2.10 -- 2.12 but all we need here is descriptions of programs, algorithms, etc. Clear thinking and persuasive writing but no programming.

RN3: 3.1, (3.4, 3.5) [fun for 173'ers], 3.6, 3.7(a,b), 3.7(c,d), (3.12, 3.13).
Also:
CB1: What's the difference between a world state, a state description, and a search node? [= 3.11, 3rd. Ed.].

3nd Edition Problems

RN1: (1.9 -- 1.13) that is do ONE of 1.9 -- 1.13. [Not quite same as 2nd ed. but that's OK]

RN2: 2.5, 2.6, (2.11, 2.12), 2.13 (5 points per answer). The book seems to want you to write and use a simulator for 2.11 -- 2.13 but all we need here is descriptions of programs, algorithms, etc. Clear thinking and persuasive writing but no programming.

RN3: 3.10, (3.4, 3.5) [fun for 173'ers], 3.11, 3.6(a,b), 3.6(c,d), (3.13, 3.18).

Common Problems

Scan the Quagent documentation and understand Quagent ontology and functionality (e.g. there's an environment with certain types of movable objects, Quagents can't fly or walk through walls, but but can walk and pick stuff up, do certain sorts of sensing of their own state and the outside world.) The Quagent Protocol documentation should help, and there may be more. You can ignore issues of actually accessing, downloading, running the system. For this exercise what is important is how we can reprogram the "monsters" to be agents under our control. Quagents have limited ability to do meaningful actions: (mainly moving and picking up things). With sensing we can do more: sense other players, proximity, distance, identification of objects, touching, etc. Make PEAS descriptions of two different sorts of quagents you would like to work with during the semester. We're looking for good ideas for quagent abilities, tasks, and personalities. (10 points for the PEAS)

Write a short paper (say 1 to 3 pages) on the usefulness of state-space problem solving for the quagents you wrote PEAS descriptions for. In the 2nd edition, Problems 3.15 (3.16) and 3.19 might be related (more or less). In the 3rd edition, possibly Problems 3.7, 3.9, 3.16, 3.20.

(15 points for the short paper).

### EX2: Chapters RN4, RN5, RN6

3rd edition swaps chapters 5 and 6.

2nd Edition Problems

RN4: (4.2, 4.7 [173'ers take note, you have seen a variant of the consistency issue under the name CB phenomenon in the N-puzzle, no? Except nobody did this problem...*snif*]), 4.3, 4.9, 4.11, 4.14 (here assume perception tells you the set of unblocked directions).

RN5: 5.5a. Check out this self-referential aptitude test! . Lots of points extra credit for a program to solve it. 173er's may want to consider Prolog's Constraint Handling Rules (type ?- help(7) for manual). (Strictly optional, but 25 points for this!).

RN6: 6.1 (a big one... 10 points), (6.2, 6.7) (5 points for your choice), 6.3 (bigger! 15 points).

3rd Edition Problems

CB1. The Heuristic path algorithm is a best-first search in which the objective funcion is f(n) = (2-w) g(n)+w(h(n)). For what values of w is this algorithm guaranteed to be optimal? (You may assume h is admissible). What kind of search does it perform when w=0? When w=2? [=4.2 2nd Ed.].

CB2. Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent [= 4.7 2nd Ed.]. [173'ers take note, you may have seen a variant of the consistency issue under the name CB phenomenon in the N-puzzle, no? Of course in 2009 nobody did the N-puzzle. *snif*].

RN4: 3.21 [not a misprint!], 4.8, 4.1, 4.12 (here assume perception tells you the set of unblocked directions).

RN6: 6.4a.

Check out this self-referential aptitude test! . Lots of points extra credit for a program to solve it. 173er's may want to consider Prolog's Constraint Handling Rules (type ?- help(7) for manual). (Strictly optional, but 25 points for this!).

RN5: 5.9 (a big one... 10 points), (5.7, 5.18) (5 points for your choice), 5.8 (bigger! 15 points).

Common Problems

Write a short paper (1-3 pages, or generally "as long as necessary, as short as possible") on the relevance of game-playing techniques to quagents engaged in some sort of Quake-like competitive activity like shooting or scavenging. (15 points for the short paper).

### EX3: Chapter RN7, RN8, RN9, (RN10)

A long one on important material: get started early. (5 points per answer and 15 for the essay).

2nd Edition Problems

RN7: 7.4 (work any 2 parts), 7.6, 7.8 (work any 4 parts), 7.9.

RN8: Five points per question:
(8.2, 8.3, 8.4) (work any 1), 8.6 (work any 3 parts), (8.7, 8.8, 8,9) (work any 1), 8.12, (8.13, 8.14, 8.15) (work any 1).

To see what test questions might be like, check out this AI Classic: An Assignment from 1999 .

RN9: Five points per question:
9.3, 9.4, (9.9, 9.11), 9.19.

3rd Edition Problems

RN7: 7.5 (work any 2 parts), 7.8, 7.10 (work any 4 parts), 7.2.

RN8: Five points per question:
(8.2, 8.3, 8.4) (work any 1), 8.24 (work any 3 parts but not part L), (8.24L, 8.25) (work any 1), 8.12, ( 8.16, 8.17, CB1 below) (work any 1).

CB1: Write down a sentence asserting that + is a commutative function. Does your sentence follow from the Peano axioms? If so, explain why: if not, give a model in which the acioms are true and your sentence is false.

To see what test questions might be like, check out this AI Classic: An Assignment from 1999 .

RN9: Five points per question:
9.3, 9.4, (9.6, 9.10), 9.24.

Common Problems

For the Quagents whose PEAS descriptions you wrote in EX1, or for a new Quagent you can now imagine thanks to your greater sophistication, give the PEAS description and then axiomatize the performance measure, environment, actuators and sensors. That is, describe how the world and intelligent agent work in first order predicate calculus. You may want to use situational calculus for the actuators at least (check out Section 10.3) . A complete axiomatization is unrealistic, but do enough axioms in each (P,E,A,S) category that we can tell you have the idea. Your (pretend) goal is that you can simulate the relevant aspects of the agent's universe (not the graphics!) using a theorem prover and your axioms.

### EX4: Chapters RN22, (RN23)

2nd Edition Problems

RN22: Five points per question except as noted:
[22.1, 22.7, 22.14] -- cute! look at for fun.
22.5, 22.6, 22.8, 22.9 (10 points).
22.12 Extra credit (max 10 pts)

22.10 and 22.11 seem related to programming project.

3rd Edition Problems

RN22: Five points per question except as noted:
[23.1, 23.14, 23.19] -- cute! look at for fun.
CB1 below, 23.5, 23.6 (10 points), 23.13.

CB1. Determine what semantic interpretation would be given to the following sentences by the grammar in this chapter:
a. It is a wumpus.
c. The wumpus is in 2,2.
Would it be a good idea to have the semantic interpretation for "It is a wumpus" be simply (predicate calculus for "There exists an x such that x is in the set of wumpii"? Consider alternative sentences such as "It was a wumpus".

### EX5: Chapters RN11, (RN12)

2nd Edition Problems

RN11: Five points apiece:
11,1, 11.3, (11.5, 11.6), 11.7(ignore part d.), 11.12.

3rd Edition Problems

RN11: Five points apiece:
10,1, 10.15, 10.6, 10.12, 10.16.

Common Problems

Short paper (this one may be more like 2-5 pages I'm thinking): I'm interested in whether it makes sense to apply AI planning to intelligent agents. Incorporate concepts from Chapter 12 (e.g. 12.7). Give your current favorite PEAS description and then consider how best to give the Quagent a planning capability. That is: What problems can planning be applied to? What planning functionalities make sense for your agent? What sort of planner do you need? Can you get such a planner from somewhere (like UCPOP or its descendents free off the web)? Is it practical?

### EX6: Chapters RN13, RN17, RN21

2nd Edition Problems

Five Points Apiece Except As Noted:

RN13: (13.1, 13.2), 13.3, 13.5, 13.6a,c,d, (13.9, 13.10), (13.11, 13.15) (13.16, 13.19.)

RN17: 17.1, 17.2, (17.4, 17.5)

RN21: (21.2, 21.4), (21.5, 21.8), 21.9. Extra Credit 10 points: 21.10.

3rd Edition Problems

Five Points Apiece Except As Noted:

RN13: (13.1, 13.2), 13.4, 13.7, 13.8a,c,d, (13.16, 13.17), (13.18, 13.21), 13.23.

RN17: 17.1, 17.3, (17.10, 17.4)

RN21: 21.2, 21.4, 21.6. Extra Credit 10 points: 21.8.

### EX7: RN20 [18], RN24, RN25

2nd Edition Problems

RN20: 20.11, [20.14 (Optional extra credit for you mathematicians or those who want to do a little research).]
RN24: 24.1, 24.4, (24.3, 24.5, 24.6), 24.8, 24.10.

Extra Credit, Optional only: From RN25, if any of this appeals to you, you might look at 25.1, 25.3, or 25.6 (10 points apiece!). 25.8 is great at frat parties.

Here's a Hint for Exercise 25.1 .

3rd Edition Problems

RN18: 18.19, [18.20 (Optional extra credit for you mathematicians or those who want to do a little research).]
RN24: 24.1, 24.4, (24.3, 24.5), 24.7.
CB1: Consider pictures like the middle one in fig. 24.22 or the right hand one in 25.6. What reasons does the view3s have to conclude some objects (cars, people, objects...) are closer than some others?

Extra Credit, Optional only: From RN25, if any of this appeals to you, you might look at 25.1, 25.5, or 25.9 (10 points apiece!). 25.11 is great at frat parties.

Here's a Hint for Exercise 25.1 .

\ Schedule and Syllabus 242 Home Honesty