On problem 3.17, it is important to note that the number of iterations is a function of the optimal cost, C*, not just on the depth of the solution in the tree.

Note from Mike: I don't really care if you have the complexity exactly right on this problem, but I do want you to understand the relationship between the optimal cost and the exponential worst-case performance of the algorithm.

Question from student If (x,y) is in R^2, there is always going to be an infinite number of potential states. Should I assume that (x,y) is in Z^2 instead? Problem b asks about paths between polygon vertices, which makes sense, but then it asks me to redefine the state space with my answer to the question about the vertices in mind. I guess I just don't see how the question about paths between polygons is related to defining the state space. Since this is supposed to be a homework about probabilistic roadmaps, is the “state space” just the possible positions of some nodes that I would randomly throw in there?

Mike's answer Problem 3.7 a is intentionally ambiguous. How many points are there in the plane R^2? Uncountable. You should conclude that this kind of state space is not compatible with the informed and uninformed searches.

Problem 3.7 b wants you to use information about the corners of obstacles to come up with a better state space, one that you define. The hints about obstacle corners is intended to help you define a small, finite state space that is compatible with path planning.

Here is the 2nd problem, with my “muddy points” following it (that I just now figured out):

2. Suppose we have three random Variables A, B and C. Suppose that A and C are binary (True/False) and that B can take on three values (1,2,3). These variables are related in the following Bayesian Network (sorry for the crude arrows):

   A
  / \
 v   v
 B   C

Suppose also that the following (conditional) probabilities govern:

P(A=True)=0.4

P(B=1|A=True)=0.6 P(B=2|A=True)=0.1

P(B=1|A=False)=0.2 P(B=2|A=False)=0.7

P(C=True|A=True)=0.8

P(C=True|A=False)=0.9

Note that in each case I expect you to be able to figure out the “missing” probability.

A) Compute the Joint distribution for A, B and C.

Use this table to compute:

B) P(A=True|C=True) C) P(B=3|C=False) D) P(A=True|B=2,C=True)

Muddy points: I am unclear on what the problem is asking me to do. It appears that it has two parts, A and B. At the same time, it seems to be either missing the aforementioned table, or part B is the table. I am inclined to think that a table graphic was intended but not displayed. Another thing that is hard to discern is what the joint distribution should look like. I can tell that sets B and C are both conditional on A, but forming a single table for the Full Joint Distribution has proven confusing. It's easy to make tables for A vs C and A vs B separately, but that doesn't do much for me either. I noticed the problem didn't say full joint distribution. Is there an important distinction in the word “full” here?

Figured out: Looking at the source for the homework wiki page, I could more clearly read and discerned that the problem is indeed separated into parts A and B, as well as C and D. Part A has to be done first, because in it, you are creating the Joint Distribution table that parts B, C, and D need to compute their answers. I hope that helps others who may have been befuddled by the wiki's inadvertent lack of typesetting.

The Kalman.h Matlab file near line 277 says the following: “ Compare this equation to the second equation on page 554. Note that the above equation and the equation in the book say the same thing.” However, there is no equation listed on that page in the current edition of Artificial Intelligence: A Modern Approach. I think this was referring to another edition of the book. Is the equation on page 586? I see the discrepancy again near line 330 and line 764. Also, around line 389, is the equation supposed to be z = x + sigz^2 * randn(2,1) ? I would think the x should be a z.