Artificial Intelligence A Modern Approach 3rd Edition Stuart Russell - Solutions

1 Consider the family of linear Gaussian networks, as defined in section 3.a. In a two-variable network, let X1 be the parent of X2, let X1 have a Gaussian prior, and let P(X2 |X1) be a linear Gaussian distribution. Show that the joint distribution P(X1,X2) is a multivariate Gaussian, and calculate
1 The Markov blanket of a variable is defined in section 2.2. Prove that a variable is independent of all other variables in the network, given its Markov blanket and derive Equation (12). Radio Battery Ignition Starts Gas Moves Figure 21 A Bayesian network describing some features of a car's
1 Let H be a random variable denoting the handedness of an individual x, with possible values l or r. A common hypothesis is that left- or right-handedness is inherited by a simple mechanism; that is, perhaps there is a gene Gx, also with values l or r, and perhaps actual handedness turns out
1 Consider the Bayesian network in Figure 2.a. If no evidence is observed, are Burglary and Earthquake independent? Prove this from the numerical semantics and from the topological semantics.b. If we observe Alarm =true, are Burglary and Earthquake independent? Justify your answer by calculating
1 The operation of arc reversal in a Bayesian network allows us to change the direction of an arc X → Y while preserving the joint probability distribution that the network represents(Shachter, 1986). Arc reversal may require introducing new arcs: all the parents of X also become parents of Y ,
1 Equation (1) defines the joint distribution represented by a Bayesian network in terms of the parameters (X |Parents(X )). This exercise asks you to derive the equivalence between the parameters and the conditional probabilities P(X | Parents(X )) from this definition. a. Consider a simple
1 Implement a hybrid probabilistic agent for the wumpus world, based on a hybrid agent, which you should be familiar with, and the probabilistic inference procedure outlined in this chapter.
1 In our analysis of the wumpus world, we used the fact that each square contains a pit with probability 0.2, independently of the contents of the other squares. Suppose instead that exactly N/5 pits are scattered at random among the N squares other than [1,1]. Are the variables Pi,j and Pk,l still
1 Text categorization is the task of assigning a given document to one of a fixed set of categories on the basis of the text it contains. Naive Bayes models are often used for this task. In these models, the query variable is the document category, and the “effect” variables are the presence or
1 (Adapted from Pearl (1988).) Suppose you are a witness to a nighttime hit-and-run accident involving a taxi in Athens. All taxis in Athens are blue or green. You swear, under oath, that the taxi was blue. Extensive testing shows that, under the dim lighting conditions, discrimination between blue
1 In this exercise, you will complete the normalization calculation for the meningitis example. First, make up a suitable value for P(s |¬m), and use it to calculate unnormalized values for P(m| s) and P(¬m| s) (i.e., ignoring the P(s) term in the Bayes’ rule expression, Equation (14)). Now
1 Suppose you are given a bag containing n unbiased coins. You are told that n − 1 of these coins are normal, with heads on one side and tails on the other, whereas one coin is a fake, with heads on both sides.a. Suppose you reach into the bag, pick out a coin at random, flip it, and get a head.
1 Show that the statement of conditional independence P(X, Y | Z) = P(X | Z)P(Y | Z)is equivalent to each of the statements P(X | Y,Z) = P(X |Z) and P(B |X,Z) = P(Y | Z) .
1 Show that the three forms of independence in Equation (11) are equivalent.
1 Given the full joint distribution shown in Figure 3, calculate the following:a. P(toothache) .b. P(Cavity) .c. P(Toothache | cavity) .d. P(Cavity | toothache ∨ catch) .
1 Consider the set of all possible five-card poker hands dealt fairly from a standard deck of fifty-two cards.a. How many atomic events are there in the joint probability distribution (i.e., how many five-card hands are there)?b. What is the probability of each atomic event?c. What is the
1 Prove Equation (4) from Equations (1) and (2).
1 Would it be rational for an agent to hold the three beliefs P(A)=0.4, P(B)=0.3, and P(A∨B)=0.5? If so, what range of probabilities would be rational for the agent to hold for A∧B? Make up a table like the one in Figure 2, and show how it supports your argument about rationality. Then draw
1 For each of the following statements, either prove it is true or give a counterexample. a. If P(a b, c) = P(b|a, c), then P(a|c) = P(b|c) b. If P(a b, c) = P(a), then P(b|c) = P(b) c. If P(a b) = P(a), then P(a | b, c) = P(a|c)
1 Show from first principles that P(a | b ∧a) = 1.
1 A complete solution to the problem of inexact matches to the buyer’s description in shopping is very difficult and requires a full array of natural language processing and information retrieval techniques. One small step is to allow the user to specify minimum and maximum values for various
1 Recall that inheritance information in semantic networks can be captured logically by suitable implication sentences. This exercise investigates the efficiency of using such sentences for inheritance.a. Consider the information in a used-car catalog such as Kelly’s Blue Book—for example, that
1 Translate the following description logic expression into first-order logic, and comment on the result: And(Man, AtLeast (3, Son), AtMost(2, Daughter), All(Son, And (Unemployed, Married, All (Spouse, Doctor))), All(Daughter, And (Professor, Fills (Department, Physics, Math)))).
1 (Adapted from Fagin et al. (1995).) Consider a game played with a deck of just 8 cards, 4 aces and 4 kings. The three players, Alice, Bob, and Carlos, are dealt two cards each.Without looking at them, they place the cards on their foreheads so that the other players can see them. Then the players
1 Construct a representation for exchange rates between currencies that allows for daily fluctuations.
Represent the following seven sentences using and extending the representations developed in the chapter:a. Water is a liquid between 0 and 100 degrees.b. Water boils at 100 degrees.c. The water in John’s water bottle is frozen.d. Perrier is a kind of water.e. John has Perrier in his water
1 Some of the operations in standard programming languages can be modeled as actions that change the state of the world. For example, the assignment operation changes the contents of a memory location, and the print operation changes the state of the output stream. A program consisting of these
1 In the SATPLAN algorithm in Figure 22 of the chapter “Logical Agents,” each call to the satisfiability algorithm asserts a goal , where ranges from 0 to . Suppose instead that the satisfiability algorithm is called only once, with the goal g0∨ g1∨ · · · ∨ gTmax .a. Will this always
1 Up to now we have assumed that the plans we create always make sure that an action’spre conditions are satisfied. Let us now investigate what propositional successor-state axioms such as HaveArrowt+1⇔ (HaveArrowt ∧ ¬Shoot t) have to say about actions whose preconditions are not
1 We contrasted forward and backward state-space searchers with partial-order planners, saying that the latter is a plan-space searcher. Explain how forward and backward statespace search can also be considered plan-space searchers, and say what the plan refinement operators are.
1 Examine the definition of bidirectional search in the chapter “Solving Problems by Searching.”a. Would bidirectional state-space search be a good idea for planning?b. What about bidirectional search in the space of partial-order plans?c. Devise a version of partial-order planning in which an
1 The set-level heuristic uses a planning graph to estimate the cost of achieving a conjunctive goal from the current state. What relaxed problem is the set-level heuristic the solution to?
1 Construct levels 0, 1, and 2 of the planning graph for the problem in Figure 1.
1 Prove that backward search with PDDL problems is complete.
1 Figure 4 shows a blocks-world problem that is known as the Sussman anomaly. The problem was considered anomalous because the noninterleaved planners of the early 1970s could not solve it. Write a definition of the problem and solve it, either by hand or with a planning program.A noninterleaved
A finite Turing machine has a finite one-dimensional tape of cells, each cell containing one of a finite number of symbols. One cell has a read and write head above it. There is a finite set of states the machine can be in, one of which is the accept state. At each time step, depending on the
The original STRIPS planner was designed to control Shakey the robot. Figure 14 shows a version of Shakey’s world consisting of four rooms lined up along a corridor, where each room has a door and a light switch. The actions in Shakey’s world include moving from place to place, pushing movable
2 Given the action schemas and initial state from Figure 1, what are all the applicable concrete instances of Fly(p, from, to) in the state described by At(P1, JFK) ∧ At(P2, SFO) ∧ Plane(P1) ∧ Plane(P2)∧ Airport (JFK) ∧ Airport (SFO) ?3 The monkey-and-bananas problem is faced by a monkey
1 Let L be the first-order language with a single predicate S(p, q), meaning “p shaves q.” Assume a domain of people.a. Consider the sentence “There exists a person P who shaves every one who does not shave themselves, and only people that do not shave themselves.” Express this in L.b.
1 This exercise considers the implementation of search algorithms in Prolog. Suppose that successor(X,Y) is true when state Y is a successor of state X; and that goal(X)is true when X is a goal state. Write a definition for solve(X,P), which means that P is a path (list of states) beginning with X,
1 This exercise looks at the recursive application of rewrite rules, using logic programming. A rewrite rule (or demodulator in OTTER terminology) is an equation with a specified direction. For example, the rewrite rule x + 0 ! x suggests replacing any expression that matches x+0 with the
1 This exercise looks at sorting in Prolog.a. Write Prolog clauses that define the predicate sorted(L), which is true if and only if list L is sorted in ascending order.b. Write a Prolog definition for the predicate perm(L,M), which is true if and only if L is a permutation of M.c. Define sort(L,M)
1 Trace the execution of the backward-chaining algorithm in Figure 6 when it is applied to solve the crime problem. Show the sequence of values taken on by the variable, and arrange them into a tree
1 In this exercise, use the sentences you wrote in Exercise 6 to answer a question by using a backward-chaining algorithm.a. Draw the proof tree generated by an exhaustive backward-chaining algorithm for the query 9 h Horse(h), where clauses are matched in the order given.b. What do you notice
1 One might suppose that we can avoid the problem of variable conflict in unification during backward chaining by standardizing apart all of the sentences in the knowledge base once and for all. Show that, for some sentences, this approach cannot work. (Hint: Consider a sentence in which one part
1 Suppose we put into a logical knowledge base a segment of the U.S. census data listing the age, city of residence, date of birth, and mother of every person, using social security numbers as identifying constants for each person. Thus, George’s age is given by Age(443-65-1282, 56). Which of the
1 A popular children’s riddle is “Brothers and sisters have I none, but that man’s father is my father’s son.” Use the rules of the family domain (Section 3.2 of the chapter “First Order Logic”) to show who that man is. You may apply any of the inference methods described in this
1 Suppose you are given the following axioms: 1. 03. 2. 79. 3. Vxxx. 4. xxx +0. 5. Vx +0x. 6. x, y x+yy+x. 7. Vw,x,y,z wy^r
1 These questions concern concern issues with substitution and Skolemization. a. Given the premise Vx y P(x, y), it is not valid to conclude that q P(q, q). Give an example of a predicate P where the first is true but the second is false. b. Suppose that an inference engine is incorrectly written
1 Prove that Universal Instantiation is sound and that Existential Instantiation produces an inferentially equivalent knowledge base.
Consider a first-order logical knowledge base that describes worlds containing people, songs, albums (e.g., “Meet the Beatles”) and disks (i.e., particular physical instances of CDs).The vocabulary contains the following symbols:CopyOf (d, a): Predicate. Disk d is a copy of album a.Owns(p, d):
26 Extend the vocabulary from Section 4 to define addition for n-bit binary numbers. Then encode the description of the four-bit adder in Figure 8, and pose the queries needed to verify that it is in fact correct.
1 Represent the following sentences in first-order logic, using a consistent vocabulary (which you must define):a. Some students took French in spring 2001.b. Every student who takes French passes it.c. Only one student took Greek in spring 2001.d. The best score in Greek is always higher than the
1 For each of the following sentences in English, decide if the accompanying first-order logic sentence is a good translation. If not, explain why not and correct it. (Some sentences may have more than one error!) a. No two people have the same social security number. -x,y,n Person(r) A Person (y)
1 Equality can be used to indicate the relation between a variable and its value. For instance, WA = red means that Western Australia is colored red. Representing this in firstorder logic, we must write more verbosely ColorOf(WA) = red. What incorrect inference could be drawn if we wrote sentences
1 Write out the axioms required for reasoning about the wumpus’s location, using a constant symbol Wumpus and a binary predicate At(Wumpus, Location). Remember that there is only one wumpus.
1 Write axioms describing the predicates Grandchild , Greatgrandparent , Ancestor Brother , Sister , Daughter , Son, FirstCousin, BrotherInLaw, SisterInLaw, Aunt , and Uncle. Find out the proper definition of mth cousin n times removed, and write the definition in first-order logic. Now write down
1 Equation (4) defines the conditions under which a square is breezy. Here we consider two other ways to describe this aspect of the wumpus world.a. We can write diagnostic rules leading from observed effects to hidden causes. For finding pits, the obvious diagnostic rules say that if a square is
1 Complete the following exercises about logical senntences: a. Translate into good, natural English (no zs or ys!): Vx,y,l Speaks Language (x, 1) A Speaks Language (y,1) Understands (x, y) A Understands (y, x). b. Explain why this sentence is entailed by the sentence Vx,y,l Speaks Language (x, 1)
1 Consider a vocabulary with the following symbols: Occupation (p, o): Predicate. Person p has occupation o. Customer (p1, p2): Predicate. Person pl is a customer of person p2. Boss (p1, p2): Predicate. Person pl is a boss of person p2. Doctor, Surgeon, Lawyer, Actor: Constants denoting
9 This exercise uses the function MapColor and predicates In(x, y), Borders (x, y), and Country(x), whose arguments are geographical regions, along with constant symbols for various regions. In each of the following we give an English sentence and a number of candidate logical expressions. For each
1 Which of the following are valid (necessarily true) sentences? a. (xxx) (Vy 2y=2). b. Va P(x) V-P(x). c. Vr Smart (r) V (x=x).
1 Consider a symbol vocabulary that contains c constant symbols, pk predicate symbols of each arity k, and fk function symbols of each arity k, where 1 ≤ k ≤ A. Let the domain size be fixed at D. For any given model, each predicate or function symbol is mapped onto a relation or function,
1 Is the sentence ∃ x, y x=y valid? Explain.
1 A logical knowledge base represents the world using a set of sentences with no explicit structure. An analogical representation, on the other hand, has physical structure that corresponds directly to the structure of the thing represented. Consider a road map of your country as an analogical
1 The TREE-CSP-SOLVER (Figure 10) makes arcs consistent starting at the leaves and working backwards towards the root. Why does it do that? What would happen if it went in the opposite direction?
1 AC-3 puts back on the queue every arc (X ,X ) whenever any value is deleted from the domain of Xi, even if each value of Xk is consistent with several remaining values of Xi.Suppose that, for every arc (Xk,Xi), we keep track of the number of remaining values of Xi that are consistent with each
1 Use the AC-3 algorithm to show that arc consistency can detect the inconsistency of the partial assignment {WA=green, V =red} for the problem shown in Figure 1.
1 Generate random instances of map-coloring problems as follows: scatter n points on the unit square; select a point X at random, connect X by a straight line to the nearest point Y such that X is not already connected to Y and the line crosses no other line; repeat the previous step until no more
1 Consider the graph with 8 nodes A , A , A , A , H, T, F , F . is connected to Ai+1 for all i, each Ai is connected to H, H is connected to T, and T is connected to each Fi. Find a 3-coloring of this graph by hand using the following strategy: backtracking with conflict-directed backjumping, the
1 Solve the cryptarithmetic problem in Figure 2 by hand, using the strategy of back-tracking with forward checking and the MRV and least-constraining-value heuristics.6 Show how a single ternary constraint such as “A + B = C” can be turned into three binary constraints by using an auxiliary
1 Give precise formulations for each of the following as constraint satisfaction problems:a. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.b. Class scheduling: There is a fixed number of professors and classrooms, a list of classes
1 Consider the problem of constructing (not solving) crossword puzzles: fitting words into a rectangular grid. The grid, which is given as part of the problem, specifies which squares are blank and which are shaded. Assume that a list of words (i.e., a dictionary)is provided and that the task is to
1 How many solutions are there for the map-coloring problem in Figure 1? How many solutions if four colors are allowed? Two colors?
27 Modify the HYBRID-WUMPUS-AGENT to use the 1-CNF logical state estimation method. We noted on that page that such an agent will not be able to acquire,maintain, and usemore complex beliefs such as the disjunction P3,1 ∨P2,2 . Sug method for overcoming this problem by defining additional
26 Section 7.1 provides some of the successor-state axioms required for the wumpus world. Write down axioms for all remaining fluent symbols.
24 Trace the behavior of DPLL on the knowledge base in Figure 16 when trying to prove Q, and compare this behavior with that of the forward-chaining algorithm.
23 How long does it take to prove KB |= α using DPLL when α is a literal already contained in KB? Explain.
22 Minesweeper, the well-known computer game, is closely related to the wumpus world. A minesweeper world is a rectangular grid of N squares with M invisible mines scattered among them. Any square may be probed by the agent; instant death follows if a mine is probed. Minesweeper indicates the
19 A sentence is in disjunctive normal form (DNF) if it is the disjunction of conjunctions of literals. For example, the sentence (A ∧ B ∧ ￢C) ∨ (￢A ∧ C) ∨ (B ∧ ￢C) is in DNF.a. Any propositional logic sentence is logically equivalent to the assertion that some possible world in
16 Explain why every nonempty propositional clause, by itself, is satisfiable. Prove rigorously that every set of five 3-SAT clauses is satisfiable, provided that each clause mentions discrete, finite domains can be solved in time linear in the number of variables. Are these two facts connected?
15 This question considers representing satisfiability (SAT) problems as CSPs.a. Draw the constraint graph corresponding to the SAT problem(￢X1 ∨ X2) ∧ (￢X2 ∨ X3) ∧ . . . ∧ (￢Xn−1 ∨ Xn)for the particular case n=5.b. How many solutions are there for this general SAT problem as a
13 This exercise looks into the relationship between clauses and implication sentences.a. Show that the clause (￢P1 ∨ ・・・ ∨ ￢Pm ∨ Q) is logically equivalent to the implication sentence (P1 ∧ ・・・ ∧ Pm) ⇒ Q.b. Show that every clause (regardless of the number of
12 Use resolution to prove the sentence ￢A∧￢B from the clauses in Exercise 20.
10 Decide whether each of the following sentences is valid, unsatisfiable, or neither. Verify your decisions using truth tables or the equivalence rules of Figure 11.a. Smoke ⇒ Smokeb. Smoke ⇒ Firec. (Smoke ⇒ Fire) ⇒ (￢Smoke ⇒ ￢Fire)d. Smoke ∨ Fire ∨ ￢Firee. ((Smoke ∧ Heat)
9 Using amethod of your choice, verify each of the equivalences in Figure 11.
8 We have defined four binary logical connectives.a. Are there any others that might be useful?b. How many binary connectives can there be?c. Why are some of them not very useful?
7 Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentences?a. B ∨ C.b. ¬A ∨ ¬B ∨ ¬C ∨ ¬D.c. (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D.
22 Consider carefully the interplay of chance events and partial information in each of the games in Exercise 4.a. For which is the standard expectiminimax model appropriate? Implement the algorithm and run it in your game-playing agent, with appropriate modifications to the gameplaying
16 This question considers pruning in games with chance nodes. Figure 19 shows the complete game tree for a trivial game. Assume that the leaf nodes are to be evaluated in leftto-right order, and that before a leaf node is evaluated, we know nothing about its value—the range of possible values is
15 Suppose you have a chess program that can evaluate 10 million nodes per second.202. Decide on a compact representation of a game state for storage in a transposition table. About how many entries can you fit in a 2-gigabyte in-memory table? Will that be enough for the three minutes of search
14 Prove that alpha–beta pruning takes time O(2 ) with optimal move ordering, where m is the maximum depth of the game tree.
13 Develop a formal proof of correctness for alpha–beta pruning. To do this, consider the situation shown in Figure 18. The question is whether to prune node n , which is a max node and a descendant of node n1. The basic idea is to prune it if and only if the minimax value of n1 can be shown to
11 Develop a general game-playing program, capable of playing a variety of games.a. Implement move generators and evaluation functions for one or more of the following games: Kalah, Othello, checkers, and chess.b. Construct a general alpha–beta game-playing agent.c. Compare the effect of
8 Consider the two-player game described in Figure 17.a. Draw the complete game tree, using the following conventions: Write each state as (SA, SB), where SA and SB denote the token locations. Put each terminal state in a square box and write its game value in a circle. Put loop states (states that
4 Describe and implement state descriptions, move generators, terminal tests, utility functions, and evaluation functions for one or more of the following stochastic games: Monopoly, Scrabble, bridge play with a given contract, or Texas hold'em poker.
3 Imagine that, in Exercise 3 of the chapter “Solving Problems by Searching” one friend wants to avoid the other. The problem is a two-player pursuit–evasion game. We assume now that the players take turns moving. The game ends only when the players are on the same node; the terminal payoff
2 Consider the problem of solving two 8-puzzles.a. Give a complete problem formulation in the style of the chapter Solving Problems by Searching.b. How large is the reachable state space? Give an exact numerical expression.c. Suppose we make the problem adversarial as follows: the two players take
13 In this exercise, we examine hill climbing in the context of robot navigation, using the environment in Figure 31, from the chapter “Solving Problems by Searching”, as an example.a. Repeat Exercise 11 using hill climbing. Does your agent ever get stuck in a local minimum? Is it possible for
12 Suppose that an agent is in a 3×3 maze environment like the one shown in Figure 19. The agent knows that its initial location is (1,1), that the goal is at (3,3), and that the actions Up, Down, Left , Right have their usual effects unless blocked by a wall. The agent does not know where the

Showing 100 - 200 of 377

Artificial Intelligence A Modern Approach 3rd Edition Stuart Russell - Solutions

Step by Step Answers