Questions and Answers of Artificial Intelligence Modern

This exercise is concerned with filtering in an environment with no landmarks. Consider a vacuum robot in an empty room, represented by an n×mrectangular grid. The robot’s location is hidden; the
Let us examine the behavior of the variance update in Equation (15.20).a. Plot the value of Ïƒ2t as a function of t, given various values for Ïƒ2x and Ïƒ2z.b. Show that
A professor wants to know if students are getting enough sleep. Each day, the professor observes whether the students sleep in class, and whether they have red eyes. The professor has the following
For the DBN specified in Exercise 15.13 and for the evidence valuese1 = not red eyes, not sleeping in classe2 = red eyes, not sleeping in classe3 = red eyes, sleeping in classperform the following
Chris considers four used cars before buying the one with maximum expected utility. Pat considers ten cars and does the same. All other things being equal, which one is more likely to have the better
In 1713, Nicolas Bernoulli stated a puzzle, now called the St. Petersburg paradox, which works as follows. You have the opportunity to play a game in which a fair coin is tossed repeatedly until it
The Surprise Candy Company makes candy in two flavors: 70% are strawberry flavor and 30% are anchovy flavor. Each new piece of candy starts out with a round shape; as it moves along the production
Prove that the judgments B ≻ A and C ≻ D in the Allais paradox violate the axiom of substitutability.
Consider the Allais paradox described : an agent who prefers B over A (taking the sure thing), and C over D (taking the higher EMV) is not acting rationally, according to utility theory. Do you think
Let continuous variables X1, . . . ,Xk be independently distributed according to the same probability density function f(x). Prove that the density function for max{X1, . . . ,Xk} is given by
Economists often make use of an exponential utility function for money: U(x) = −ex/R, where R is a positive constant representing an individual’s risk tolerance. Risk tolerance reflects how
Recall the definition of value of information in Section 16.6.a. Prove that the value of information is nonnegative and order independent.b. Explain why it is that some people would prefer not to get
Select a specific member of the set of policies that are optimal for R(s) > 0 as shown in Figure 17.2(b), and calculate the fraction of time the agent spends in each state, in the limit, if the
For the environment shown in Figure 17.1, find all the threshold values for R(s) such that the optimal policy changes when the threshold is crossed. You will need a way to calculate the optimal
Consider the 3 Ã— 3 world shown in Figure 17.14(a). The transition model is the same as in the 4 Ã— 3 Figure 17.1: 80% of the time the agent goes in the direction it selects;
Consider the 101 Ã— 3 world shown in Figure 17.14(b). In the start state the agent has a choice of two deterministic actions, Up or Down, but in the other states the agent has one
Consider a version of the vacuum robot that has the policy of going straight for as long as it can; only when it encounters an obstacle does it change to a new (randomly selected) heading. To model
In Section 15.3.2, the prior distribution over locations is uniform and the transition model assumes an equal probability of moving to any neighboring square. What if those assumptions are wrong?
In this exercise, we examine what happens to the probabilities in the umbrella world in the limit of long time sequences.a. Suppose we observe an unending sequence of days on which the umbrella
The Metropolis€“Hastings algorithm is a member of the MCMC family; as such, it is designed to generate samples x (eventually) according to target probabilities Ï€(x). (Typically
This exercise explores the stationary distribution for Gibbs sampling methods.a. The convex composition [α, q1; 1 − α, q2] of q1 and q2 is a transition probability distribution that first chooses
Consider the variable elimination algorithm in Figure 14.11.a. Section 14.4 applies variable elimination to the query P(Burglary | JohnCalls = true,MaryCalls = true). Perform the
Consider the network shown in Figure 14.22 (ii), and assume that the two telescopes work identically. N ˆˆ{1, 2, 3} and M1, M2ˆˆ{0, 1, 2, 3, 4}, with the symbolic CPTs as
LetHx 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,
Suppose that in a Bayesian network containing an unobserved variable Y, all the variables in the Markov blanket MB(Y) have been observed.a. Prove that removing the node Y from the network will not
Consider the Bayesian network in Figure 14.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
The operation of arc reversal 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
Equation (14.1) on page 513 defines the joint distribution represented by a Bayesian network in terms of the parameters Î¸(Xi|Parents(Xi)). This exercise asks you to derive the
We have a bag of three biased coins a, b, and c with probabilities of coming up heads of 20%, 60%, and 80%, respectively. One coin is drawn randomly from the bag (with equal likelihood of drawing
Redo the probability calculation for pits in [1,3] and [2,2], assuming that each square contains a pit with probability 0.01, independent of the other squares. What can you say about the relative
Show that the statement of conditional independenceis equivalent to each of the statements P(X,Y |Z) = P(X Z)P(Y | Z) P(X |Y, Z) = P(X|Z) and P(BX,Z)= P(Y|Z). and P(B|X, Z) = P(Y | Z).
It is quite often useful to consider the effect of some specific propositions in the context of some general background evidence that remains fixed, rather than in the complete absence of
Suppose you are given a coin that lands heads with probability x and tails with probability 1 − x. Are the outcomes of successive flips of the coin independent of each other given that you know the
Consider two medical tests, A and B, for a virus. Test A is 95% effective at recognizing the virus when it is present, but has a 10% false positive rate (indicating that the virus is present, when it
Show that the three forms of independence in Equation (13.11) are equivalent.(13.11) Р(a|b) — Р(а) or P(b|а) —D Р(Ь) or Р(алЬ) — Р(а)Р()
We wish to transmit an n-bit message to a receiving agent. The bits in the message are independently corrupted (flipped) during transmission with ∈ probability each. With an extra parity bit sent
Deciding to put probability theory to good use, we encounter a slot machine with three independent wheels, each producing one of the four symbols BAR, BELL, LEMON, or CHERRY with equal probability.
In his letter of August 24, 1654, Pascal was trying to show how a pot of money should be allocated when a gambling game must end prematurely. Imagine a game where each turn consists of the roll of a
This question deals with the properties of possible worlds, defined on page 488 as assignments to all random variables. We will work with propositions that correspond to exactly one possible world
Suppose the Flip action always changes the truth value of variable L. Show how to define its effects by using an action schema with conditional effects. Show that, despite the use of conditional
In the blocks world we were forced to introduce two action schemas, Move and MoveToTable, in order to maintain the Clear predicate properly. Show how conditional effects can be used to represent both
Define an ontology in first-order logic for tic-tac-toe. The ontology should contain situations, actions, squares, players, marks (X, O, or blank), and the notion of winning, losing, or drawing a
Develop a representational system for reasoning about windows in a window-based computer interface. In particular, your representation should be able to describe:• The state of a window: minimized,
State the following in the language you developed for the previous exercise:a. In situation S0, window W1 is behind W2 but sticks out on the left and right. Do not state exact coordinates for these;
Write definitions for the following:a. ExhaustivePartDecompositionb. PartPartitionc. PartwiseDisjointThese should be analogous to the definitions for ExhaustiveDecomposition, Partition, and Disjoint
Add sentences to extend the definition of the predicate Name(s, c) so that a string such as “laptop computer” matches the appropriate category names from a variety of stores. Try to make your
Write event calculus axioms to describe the actions in the wumpus world.
State the interval-algebra relation that holds between every pair of the following real world events:LK: The life of President Kennedy.IK: The infancy of President Kennedy.PK: The presidency of
The assumption of logical omniscience, discussed, is of course not true of any actual reasoners. Rather, it is an idealization of the reasoning process that may be more or less acceptable depending
Translate the following description logic expression (from page 457) into first-order logic, and comment on the result:And(Man, AtLeast(3, Son), AtMost(2, Daughter),All(Son, And(Unemployed,Married,
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
One part of the shopping process that was not covered in this chapter is checking for compatibility between items. For example, if a digital camera is ordered, what accessory batteries, memory cards,
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
Suppose that a high-level action has exactly one implementation as a sequence of primitive actions. Give an algorithm for computing its preconditions and effects, given the complete refinement
You have a number of trucks with which to deliver a set of packages. Each package starts at some location on a grid map, and has a destination somewhere else. Each truck is directly controlled by
The goals we have considered so far all ask the planner to make the world satisfy the goal at just one time step. Not all goals can be expressed this way: you do not achieve the goal of suspending a
Consider how to translate a set of action schemas into the successor-state axioms of situation calculus.a. Consider the schema for Fly(p, from, to). Write a logical definition for the predicate
Up to now we have assumed that the plans we create always make sure that an action’s preconditions are satisfied. Let us now investigate what propositional successor-state axioms such as
Construct levels 0, 1, and 2 of the planning graph for the problem in Figure 10.1.Figure 10.1 Init(At (С1, SFO)л At(С>, JFK)л At(P, SFO) Л At(Р>, JFK) Л Сатgo (Cт) л Сargo(C>) ^ Plane
Prove that backward search with PDDL problems is complete.
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
Construct an example of two clauses that can be resolved together in two different ways giving two different outcomes.
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
Suppose a knowledge base contains just the following first-order Horn clauses:Ancestor(Mother(x), x)Ancestor(x, y) ∧ Ancestor(y, z) ⇒ Ancestor(x, z)Consider a forward chaining algorithm that, on
The following Prolog code defines a predicate P. (Remember that uppercase terms are variables, not constants, in Prolog.)P(X, [X|Y]).P(X, [Y|Z]) :- P(X, Z).a. Show proof trees and solutions for the
Suppose you are given the following axioms:1. 0 ≤ 3.2. 7 ≤ 9.3. ∀x x≤ x.4. ∀x x≤ x + 0.5. ∀x x+ 0 ≤ x.6. ∀ x, y x + y ≤ y + x.7. ∀ w, x, y, z w ≤ y ∧ x ≤ z ⇒ w + x ≤ y
These questions concern concern issues with substitution and Skolemization.a. Given the premise ∀ x ∃y P(x, y), it is not valid to conclude that ∃q P(q, q). Give an example of a predicate P
Suppose a knowledge base contains just one sentence, ∃ x AsHighAs(x, Everest). Which of the following are legitimate results of applying Existential Instantiation?a. AsHighAs(Everest, Everest ).b.
Write in first-order logic the assertion that every key and at least one of every pair of socks will eventually be lost forever, using only the following vocabulary: Key(x), x is a key; Sock(x), x is
In Chapter 6, we used equality to indicate the relation between a variable and its value. For instance, we wrote WA = red to mean that Western Australia is colored red. Representing this in
Arithmetic assertions can be written in first-order logic with the predicate symbol <, the function symbols + and ×, and the constant symbols 0 and 1. Additional predicates can also be defined
Assuming predicates Parent(p, q) and Female(p) and constants Joan and Kevin, with the obvious meanings, express each of the following sentences in first-order logic. (You may use the abbreviation
Equation (8.4) on page 306 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
Rewrite the first two Peano axioms in Section 8.3.3 as a single axiom that defines NatNum(x) so as to exclude the possibility of natural numbers except for those generated by the successor function.
Complete the following exercises about logical senntences:a. Translate into good, natural English (no xs or ys!): ∀ x, y, l SpeaksLanguage(x, l) ∧ SpeaksLanguage(y, l) ⇒ Understands (x, y) ∧
Consider a vocabulary with the following symbols:Occupation(p, o): Predicate. Person p has occupation o.Customer (p1, p2): Predicate. Person p1 is a customer of person p2.Boss(p1, p2): Predicate.
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
Does the fact ¬Spouse(George, Laura) follow from the facts Jim ≠ George and Spouse (Jim, Laura)? If so, give a proof; if not, supply additional axioms as needed. What happens if we use Spouse as a
Consider a version of the semantics for first-order logic in which models with empty domains are allowed. Give at least two examples of sentences that are valid according to the standard semantics
Consider the family of generalized tic-tac-toe games, defined as follows. Each particular game is specified by a set S of squares and a collection W of winning positions. Each winning position is a
Describe how the minimax and alpha–beta algorithms change for two-player, nonzero- sum games in which each player has a distinct utility function and both utility functions are known to both
Prove that alpha–beta pruning takes time O(2m/2) with optimal move ordering, where m is the maximum depth of the game tree.
This question considers pruning in games with chance nodes. Figure 5.19 shows the complete game tree for a trivial game. Assume that the leaf nodes are to be evaluated in left-to-right order, and
Consider the following procedure for choosing moves in games with chance nodes:Generate some dice-roll sequences (say, 50) down to a suitable depth (say, 8).With known dice rolls, the game tree
In the following, a "max" tree consists only of max nodes, whereas an "expectimax" tree consists of a max node at the root with alternating layers of chance and max nodes. At chance nodes, all
Which of the following are true and which are false? Give brief explanations.a. In a fully observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first
Consider the problem of placing k knights on an n×n chessboard such that no two knights are attacking each other, where k is given and k ≤ n2.a. Choose a CSP formulation. In your formulation, what
Consider the following logic puzzle: In five houses, each with a different color, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and
The TREE-CSP-SOLVER (Figure 6.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
We introduced Sudoku as a CSP to be solved by search over partial assignments because that is the way people generally undertake solving Sudoku problems. It is also possible, of course, to attack
Define in your own words the terms constraint, backtracking search, arc consistency, back jumping, min-conflicts, and cycle cutset.
Suppose the agent has progressed to the point shown in Figure 7.4(a), page 239, having perceived nothing in [1, 1], a breeze in [2, 1], and a stench in [1, 2], and is now concerned with the contents
Which of the following are correct?a. False ⊨ True.b. True ⊨ False.c. (A ∧ B) ⊨ (A ⇔ B).d. A ⇔ B ⊨ A ∨ B.e. A ⇔ B ⊨ ¬A ∨ B.f. (A ∧ B) ⇒ C ⊨ (A ⇒ C) ∨ (B ⇒ C).g. (C
Prove each of the following assertions:a. α is valid if and only if True ⊨ α.b. For any α, False ⊨ α.c. α ⊨ β if and only if the sentence (α ⇒ β) is valid.d. α ≡ β if and only if
Prove, or find a counterexample to, each of the following assertions:a. If α ⊨ γ or β |= γ (or both) then (α ∧ β) ⊨ γb. If α ⊨ (β ∧ γ) then α ⊨ β and α ⊨ γ.c. If α ⊨
Use resolution to prove the sentence ¬ A ∧¬ B from the clauses in Exercise 7.20.
According to some political pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), but otherwise is not electable.a. Which of the following are correct representations
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 ∨
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 exactly three
A propositional 2-CNF expression is a conjunction of clauses, each containing exactly 2 literals, e.g.,(A ∨ B) ∧ (¬ A ∨ C) ∧ (¬ B ∨ D) ∧ (¬ C ∨ G) ∧ (¬ D ∨ G).a. Prove using

Showing 1 - 100 of 150