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.