Description
Consider the C-space C = [−3, 3] × [−1, 1] and C-space obstacles shown in Figure 1.
The C-space obstacles are defined by two half circles centered at (0, −1) and (0, 1),
respectively, both having radius 1−dt, where dt = 0.02. (I suggest making dt a parameter
in your code. We will consider a similar configuration but with a different value of dt
in the next assignment.) Anything within the two half circles are considered obstacle
regions.
The initial configuration is qI = (−2, −0.5) and the goal configuration is qG =
(2, −0.5).
Figure 1: The C-space and C-space obstacles.
1. (10 points for COM S 4760, 7 points for COM S 5760) Exploring the C-space using
RRT:
Neglect the goal configuration. Use the Euclidean distance as the distance metric.
Explore the C-space using RRT and plot the resulting tree in the C-space for the
following cases.
The result should be similar to Figure 2.
(a) Neglect the obstacle and assume that Cfree = C.
(b) Take into account the obstacles. Use a step size of 0.1 for collision checking.
2. (10 points for COM S 4760, 7 points for COM S 5760) Solve the planning problem
using RRT:
Use the single-tree search outlined in Section 5.5.3. You should check periodically
if the tree can be connected to qG. This can be easily done by setting α(i) as qG
with a certain probability p. For example, the book recommends p = 0.01.
You
should have this as a parameter in your code. Once qG is successfully added to the
tree, quit the loop and compute the path from qI to qG. Plot both the resulting
tree and path. The result should be similar to Figure 3, which uses p = 0.1.
Figure 2: The result of RRT exploration. The black lines are the edges in the tree. The
blue cross and the blue dots are the initial and goal configuations, respectively. (top)
Problem 1(a), and (bottom) Problem 1(b).
3. (COM S 5760 only, 6 points) Solve the planning problem using PRM:
Use the algorithm described in Figure 5.25 in the textbook. As for the number of
nodes N, try a different value until you can solve the problem. When connecting
to the nodes in the neighborhood, use Nearest K and set K = 15. Figure 4 shows
a solution using N = 1000, including the roadmap and the path.
Submission: Please submit a single zip file on Canvas containing the followings
• your code (with comments, explaining clearly what each function/class is doing),
• the plots from each of the problems, similar to Figure 2-4, and
• a text file explaining clearly how to compile and run your code.
Figure 3: The result of RRT planning with p = 0.1 as described in Problem 2, showing
the tree and the path from qI to qG.
Figure 4: The roadmap and the path from qI to qG using PRM with N = 1000.