CS326A – Motion Planning – Spring 2003HOMEWORK #2 – Due date: May 19Staple your solution with the text of the homework.Write your name here: _______________________Problem # Max grade Grade1 202 203 204 205 206 20TOTAL(*) 100(*): Sum of best five gradesProblem 1 (Expansiveness of free space): (20 points)Planning a collision-free path of a robot is known to take exponential time in the numberof dimensions of the C-space. PRM planners try to trade a limited amount ofcompleteness (by being only probabilistically complete) against a big gain incomputational time. This first problem is aimed at investigating, on a simple example,how the running time of a PRM planner may relate to the dimensionality of the C-space.Let C denote the n-dimensional C-space of a given robot and F its open collision-freesubset (the free space). The notion of expansiveness attempts to characterize thedifficulty that a PRM planner may have to find paths in F. Recall that the expansivenessof F is defined as follows:1. Two configurations q and q’ in F see each other if the line segment joining them iscompletely contained in F.2. For any q in F, let V(q) denote the set of all points that q sees (the visibility set ofq).3. For any given subset X  F, let (X) be the volume of X ( is an area if n = 2). 4. The -lookout of any X  F is the subset of all points q of X such that: (V(q)\X) > (F\X), where  is a positive real number (smaller than or equalto 1) and Y\X denotes the subset of all points in Y that are not in X.5. F is (,)-expansive if the volume of the -lookout of any X  F is greater than(X), where  is a positive real number (smaller than or equal to 1)Under some conditions (not made explicit here), the probability that a single-query PRMplanner fails to find a path when one exists goes to zero roughly as K(,)exp(-N),where N is the number of milestones and K(,) is proportional to (1/ln(1/). 1. What is the artifact that may hide the role of the dimensionality n of the C-space in thisresult?2. Consider the case where n = 2, and assume that the free space is the one shown inFigure 1 (two squares connected by a long narrow channel). Let L be the length of eachside of each of the two squares and also the length of the narrow channel. Let  be thewidth of the narrow channel.Compute an approximation of the values of  and  for which this free space isexpansive. [Hint: Consider one of the two squares as a worst-case choice of X.] Whathappens when  tends toward 0, with L being fixed?3. Assume the same example in n > 2 dimensions. Let the edges of the (hyper-)cubes stillbe L. Let the width of the channel be  along k (k = 1, 2, …, or n-1) dimensions and Lalong the n-k other dimensions. For which values of  and  is the free space expansive?How does the dimension n intervene? How does your result relate to your answer ofQuestion 1?Problem 2 (Nonholonomy of a mobile robot): (20 points)In this problem, we consider a cylindrical mobile robot with three wheels, two drivingwheels and a free wheel. We model the robot by a disc. Figure 2 shows this disc and thepositions of the wheels. The driving wheels are shaded. The midpoint between them isFigure 1exactly the center of the disc. Their angular velocities can be controlled independent ofeach other, with each wheel rotating at any velocity in [-, +]. The free wheel is notactuated, but can passively adjust its orientation. Its purpose is to prevent the robot fromtoppling over (if needed, we could have added a second free wheel). The two controls ofthe robot are the angular velocities of the two driving wheels. 1. Is this robot nonholonomic? Why? What is its turning radius? 2. Define the configuration of this robot to be the coordinates (x,y) of the disc’s center. Isa path generated by a classical holonomic planner (e.g., a PRM planner that connectsmilestones by straight line segments) feasible? Why? Compare the number of dimensionsof the C-space with the number of controls.3. Now, assume this robot is loaded with a large non-circular object (e.g., a rectangularbox) that extends beyond the disc’s boundary. What would be the C-space of the loadedrobot? Is a path generated by a classical holonomic planner feasible? Why? Again,compare the number of dimensions of the C-space with the number of controls.Problem 3 (On shortest paths): (20 points)1. Consider a two-dimensional C-space with polygonal obstacles. Show that the shortestpath between any two points is a polygonal line such that each intermediate vertex (ifany) is an obstacle vertex. (Here, we only require a path to be semi-free, that is, not topenetrate inside any obstacle. A semi-free path may lie partially outside the obstacles andpartially on their boundaries.)2. Let an obstacle vertex be convex if the angle (inside the obstacle) between the twoadjacent edges is less than , and concave otherwise. Can a convex vertex be on ashortest path? What about a concave vertex? Why?3. Now assume that the obstacles are “generalized” polygons whose boundaries consistof straight and circular edges. Characterize the shape of a shortest path between twopoints in free space. What points can be intermediate vertices on a shortest path?Figure 24. Let the C-space be three-dimensional and the obstacles polyhedral. Characterize theshape of a shortest path between two points in free space. Where may intermediatevertices of shortest paths lie?5. Finding the shortest path among polyhedral obstacles is NP-hard. So, let us use thefollowing two-phase planning method. First we generate an arbitrary semi-free pathbetween the two given points. Next, we use a variational technique that iterativelyshortens this path until it can no longer make it shorter.a) Is the path obtained at the end of the second phase the shortest one?b) If not, is it the shortest one in the homotopy class of the path generated in the firstphase? If your answer is yes, prove it. If your answer is no, show a counter-example.Problem 4 (Sampling a triangulated surface): (20 points)1. Give a simple method to sample N points uniformly at random in a triangle. (Thismethod should not use rejection techniques.)2. How would you sample