Programming Assignment 2
Due Monday, March 3, 12:00 pm (noon)
Overview
In this assignment you will implement and analyze two sampling-based planning algorithms: Bi-directional Rapidly-Exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRM) (additional PRM references). The RRT planner is a single-query planner that is intended to focus the computation on a single start-goal pair. The PRM is a multi-query planner, best used when multiple start-goal pairs are expected to be solved in the same environment, although it can also be used to solve a single query.
You'll be testing these planners in the environment from Assignment 1, so you should already have the forward kinematics and collision functions implemented and ready to work. For each planner, generate several problem instances and gather relevant statistics (planning times, number of collision checks, number of tree/graph nodes, number of nearest-neighbor calculations, etc.) to obtain a solution for each instance. Then make a histogram for planning times and compute the average planning times for each problem instance.
The purpose of this assignment is not only to get you to implement each planning algorithm, but also to think carefully about testing procedures and benchmarking. For example, think about what is required to fully benchmark a planning algorithm, even for the simple box domain used in Assignment 1.
Testing
Generate a random start and goal configuration in the sample environment found here and gather statistics about the time it takes to find a solution (make the start and goal substantially far apart from each other so that plans have to consider the obstacles). Do this as many times as you think are necessary in order to get good statistics (don't change the start and goal). How many samples did it take to get a good estimate of the mean running time of each planner? A good estimate is when your estimated mean is within 5\% of the real mean. The stopping condition can be easily detected by checking if the last n samples (where n is 10-100) changed the mean by less than 5\%.
Now do the same experiment but this time continue picking random, collision-free start and goal configurations for every new run. How many samples does it take now to get a good estimate of the mean? (should be more)
Now perform the same experiment except for every new run, sample new start and goals along with new locations for the three obstacles. In order to keep things simple, all obstacles should have extents of 0.1 and orientations of 0. The position should be uniformly sampled around (in a circle of radius 2. How many samples does it take to get a good estimate? (should be much more)
For all three cases, plot the histograms of running times for both planners. What can you say about them? Note that there's two options possible for PRMs: completely regenerate the map at each new run or cache the results once and resue them for each new run. The latter is obviously faster, but can only be applied when the environment does not change. Show results for both flavors of PRMs when applicable.
Deliverables
Short Questions
Please answer the following questions:
1. State and prove whether or not (5.28) yields a metric space on C = SE(3), assuming that the two sets (E and F) are rigid bodies. (#4, Planning Algorithms, pg. 244)
(Eq 5.28)
2. Explain the difference between searching an implicit, high-resolution grid and growing search trees directly on the C-space without a grid. (#18, Planning Algorithms, pg. 245)
3. Improve the bound in (5.31) by considering the fact that rotating points trace out a circle, instead of a straight line. (#19, Planning Algorithms, pg. 245)
(Eq 5.31)
What to turn in
- All code used for the planning algorithms and testing. Make sure to attach the code from Assignment 1 that you used for the forward kinematics and collision detection.
- A writeup of what you did including the answers to the short questions. Make sure to attach the histograms and average planning statistics for the two planners. Which factors have the greatest affect on planning times and why? What are the bottlenecks for the two planners? (you may want to consider your answer in terms of worst-case, best-case, and average-case performance)